Finding Fair and Efficient Allocations

Authors

Siddharth Barman, Sanath Kumar Krishnamurthy, Rohit Vaish

Type: Article

Publication Date: 2018-06-11

Citations: 166

DOI: https://doi.org/10.1145/3219166.3219176

Ask PDF

Abstract

We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if it is envy-free up to one good (EF1), which means that each agent prefers its own bundle over the bundle of any other agent up to the removal of one good. In addition, an allocation is deemed efficient if it satisfies Pareto efficiency. While each of these well-studied properties is easy to achieve separately, achieving them together is far from obvious. Recently, Caragiannis et al. (2016) established the surprising result that when agents have additive valuations for the goods, there always exists an allocation that simultaneously satisfies these two seemingly incompatible properties. Specifically, they showed that an allocation that maximizes the Nash social welfare objective is both EF1 and Pareto efficient. However, the problem of maximizing Nash social welfare is NP-hard. As a result, this approach does not provide an efficient algorithm for finding a fair and efficient allocation. In this paper, we bypass this barrier, and develop a pseudopolynomial time algorithm for finding allocations that are EF1 and Pareto efficient; in particular, when the valuations are bounded, our algorithm finds such an allocation in polynomial time. Furthermore, we establish a stronger existence result compared to Caragiannis et al. (2016): For additive valuations, there always exists an allocation that is EF1 and fractionally Pareto efficient. Another key contribution of our work is to show that our algorithm provides a polynomial-time 1.45-approximation to the Nash social welfare objective. This improves upon the best known approximation ratio for this problem (namely, the 2-approximation algorithm of Cole et al., 2017), and also matches the lower bound on the integrality gap of the convex program of Cole et al. (2017). Unlike many of the existing approaches, our algorithm is completely combinatorial, and relies on constructing integral Fisher markets wherein specific equilibria are not only efficient, but also fair.

Locations

arXiv (Cornell University)
View PDF

Ask a Question About This Paper

Summary

None

2025-04-30

Alfin Luluk Kamalia , Nina Queena Hadi Putri

None

2025-05-13

None

2022-06-15

None

2025-05-13

None

2025-04-30

None

2025-05-20

None

2025-04-30

None

2024-06-01

None

2025-05-21

None

2025-02-28

None

2022-12-03

None

2025-05-20

None

2025-05-01

None

2025-05-13

None

2014-07-02

None

2025-05-16

None

2025-05-15

None

2024-08-12

None

2023-06-27

None

2011-08-01

Maximum Nash welfare and other stories about EFX

2021-02-09

Georgios Amanatidis , Georgios Birmpas , Aris Filos-Ratsikas +2 more

View PDF Chat

Fairly Allocating Many Goods with Few Queries

2021-01-01

Hoon Oh , Ariel D. Procaccia , Warut Suksompong

Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 16 January 2020Accepted: 10 January 2021Published online: 15 April 2021Keywordsenvy-freeness, fair division, algorithms, … Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 16 January 2020Accepted: 10 January 2021Published online: 15 April 2021Keywordsenvy-freeness, fair division, algorithms, query complexityAMS Subject Headings68Q25, 91B32Publication DataISSN (print): 0895-4801ISSN (online): 1095-7146Publisher: Society for Industrial and Applied MathematicsCODEN: sjdmec

View PDF Chat

Existence of EFX for two additive valuations

2023-07-20

Ryoga Mahara

View PDF Chat

Efficient Fair Division with Minimal Sharing

2022-05-01

Fedor Sandomirskiy , Erel Segal-Halevi

When assets are to be divided among several partners, for example, a partnership split, fair division theory can be used to determine a fair allocation. The applicability of existing approaches … When assets are to be divided among several partners, for example, a partnership split, fair division theory can be used to determine a fair allocation. The applicability of existing approaches is limited as they either treat assets as divisible resources that end up being shared among participants or deal with indivisible objects providing only approximate fairness. In practice, sharing is often possible but undesirable, and approximate fairness is not adequate, particularly for highly valuable assets. In “Efficient Fair Division with Minimal Sharing,” Sandomirskiy and Segal-Halevi introduce a novel approach offering a middle ground: the number of shared objects is minimized while maintaining exact fairness and economic efficiency. This minimization can be conducted in polynomial time for generic instances if the number of agents or objects is fixed. Experiments on real data demonstrate a substantial improvement over current methods.

View PDF Chat

The Price of Quota-based Diversity in Assignment Problems

2020-08-31

Nawal Benabbou , Mithun Chakraborty , Xuan-Vinh Ho +2 more

We introduce and analyze an extension to the matching problem on a weighted bipartite graph: Assignment with Type Constraints. The two parts of the graph are partitioned into subsets called … We introduce and analyze an extension to the matching problem on a weighted bipartite graph: Assignment with Type Constraints. The two parts of the graph are partitioned into subsets called types and blocks; we seek a matching with the largest sum of weights under the constraint that there is a pre-specified cap on the number of vertices matched in every type-block pair. Our primary motivation stems from the public housing program of Singapore, accounting for over 70% of its residential real estate. To promote ethnic diversity within its housing projects, Singapore imposes ethnicity quotas: each new housing development comprises blocks of flats and each ethnicity-based group in the population must not own more than a certain percentage of flats in a block. Other domains using similar hard capacity constraints include matching prospective students to schools or medical residents to hospitals. Limiting agents' choices for ensuring diversity in this manner naturally entails some welfare loss. One of our goals is to study the trade-off between diversity and social welfare in such settings. We first show that, while the classic assignment program is polynomial-time computable, adding diversity constraints makes it computationally intractable; however, we identify a $\tfrac{1}{2}$-approximation algorithm, as well as reasonable assumptions on the weights that permit poly-time algorithms. Next, we provide two upper bounds on the price of diversity -- a measure of the loss in welfare incurred by imposing diversity constraints -- as functions of natural problem parameters. We conclude the paper with simulations based on publicly available data from two diversity-constrained allocation problems -- Singapore Public Housing and Chicago School Choice -- which shed light on how the constrained maximization as well as lottery-based variants perform in practice.

View PDF Chat

Computing Welfare-Maximizing Fair Allocations of Indivisible Goods

2020-01-01

Haris Aziz , Xin Huang , Nicholas Mattei +1 more

We analyze the run-time complexity of computing allocations that are both fair and maximize the utilitarian social welfare, defined as the sum of agents' utilities. We focus on two tractable … We analyze the run-time complexity of computing allocations that are both fair and maximize the utilitarian social welfare, defined as the sum of agents' utilities. We focus on two tractable fairness concepts: envy-freeness up to one item (EF1) and proportionality up to one item (PROP1). We consider two computational problems: (1) Among the utilitarian-maximal allocations, decide whether there exists one that is also fair; (2) among the fair allocations, compute one that maximizes the utilitarian welfare. We show that both problems are strongly NP-hard when the number of agents is variable, and remain NP-hard for a fixed number of agents greater than two. For the special case of two agents, we find that problem (1) is polynomial-time solvable, while problem (2) remains NP-hard. Finally, with a fixed number of agents, we design pseudopolynomial-time algorithms for both problems. We extend our results to the stronger fairness notions envy-freeness up to any item (EFx) and proportionality up to any item (PROPx).

View PDF Chat

Fair Division with Two-Sided Preferences

2022-01-01

Ayumi Igarashi , Yasushi Kawase , Warut Suksompong +1 more

We study a fair division setting in which participants are to be fairly distributed among teams, where not only do the teams have preferences over the participants as in the … We study a fair division setting in which participants are to be fairly distributed among teams, where not only do the teams have preferences over the participants as in the canonical fair division setting, but the participants also have preferences over the teams. We focus on guaranteeing envy-freeness up to one participant (EF1) for the teams together with a stability condition for both sides. We show that an allocation satisfying EF1, swap stability, and individual stability always exists and can be computed in polynomial time, even when teams may have positive or negative values for participants. When teams have nonnegative values for participants, we prove that an EF1 and Pareto optimal allocation exists and, if the valuations are binary, can be found in polynomial time. We also show that an EF1 and justified envy-free allocation does not necessarily exist, and deciding whether such an allocation exists is computationally difficult.

View PDF Chat

On the Proximity of Markets with Integral Equilibria

2019-07-17

Siddharth Barman , Sanath Kumar Krishnamurthy

We study Fisher markets that admit equilibria wherein each good is integrally assigned to some agent. While strong existence and computational guarantees are known for equilibria of Fisher markets with … We study Fisher markets that admit equilibria wherein each good is integrally assigned to some agent. While strong existence and computational guarantees are known for equilibria of Fisher markets with additive valuations (Eisenberg and Gale 1959; Orlin 2010), such equilibria, in general, assign goods fractionally to agents. Hence, Fisher markets are not directly applicable in the context of indivisible goods. In this work we show that one can always bypass this hurdle and, up to a bounded change in agents’ budgets, obtain markets that admit an integral equilibrium. We refer to such markets as pure markets and show that, for any given Fisher market (with additive valuations), one can efficiently compute a “near-by,” pure market with an accompanying integral equilibrium.Our work on pure markets leads to novel algorithmic results for fair division of indivisible goods. Prior work in discrete fair division has shown that, under additive valuations, there always exist allocations that simultaneously achieve the seemingly incompatible properties of fairness and efficiency (Caragiannis et al. 2016); here fairness refers to envyfreeness up to one good (EF1) and efficiency corresponds to Pareto efficiency. However, polynomial-time algorithms are not known for finding such allocations. Considering relaxations of proportionality and EF1, respectively, as our notions of fairness, we show that fair and Pareto efficient allocations can be computed in strongly polynomial time.

View PDF Chat

A Little Charity Guarantees Almost Envy-Freeness

2019-12-23

Bhaskar Ray Chaudhury , Telikepalli Kavitha , Kurt Mehlhorn +1 more

Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)A Little Charity Guarantees Almost Envy-FreenessBhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini SgouritsaBhaskar … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)A Little Charity Guarantees Almost Envy-FreenessBhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini SgouritsaBhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsapp.2658 - 2672Chapter DOI:https://doi.org/10.1137/1.9781611975994.162PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract Fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute m goods to n agents in a “fair” manner, where every agent has a valuation for each subset of goods. We assume general valuations. Envy-freeness is the most extensively studied notion of fairness. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is “envy-freeness up to any good” (EFX) where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists even when n = 3. We show there is always a partition of the set of goods into n + 1 subsets (X1, …, Xn, P) where for i ϵ [n], Xi is the bundle allocated to agent i and the set P is unallocated (or donated to charity) such that we have: (1)envy-freeness up to any good,(2)no agent values P higher than her own bundle, and(3)fewer than n goods go to charity, i.e., |P| < n (typically m ≫ n). Our proof is constructive. When agents have additive valuations and |P| is large (i.e., when |P| is close to n), our allocation also has a good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm also shows the existence of an allocation which is 4/7 groupwise maximin share (GMMS): this is a notion of fairness stronger than MMS. This improves upon the current best bound of 1/2 known for an approximate GMMS allocation. Previous chapter Next chapter RelatedDetails Published:2020eISBN:978-1-61197-599-4 https://doi.org/10.1137/1.9781611975994Book Series Name:ProceedingsBook Code:PRDA20Book Pages:xxii + 3011

View PDF Chat

Maximizing Determinants under Matroid Constraints

2020-11-01

Vivek Madan , Aleksandar Nikolov , Mohit Singh +1 more

Given a set of vectors v1, ... , v n ∈ R d and a matroid M=([n],I), we study the problem of finding a basis S … Given a set of vectors v1, ... , v n ∈ R d and a matroid M=([n],I), we study the problem of finding a basis S of M such that det(Σ i ∈s v i v i T ) is maximized. This problem appears in a diverse set of areas, such as experimental design, fair allocation of goods, network design, and machine learning. The current best results include an e 2k -estimation for any matroid of rank k [8] and a (1+ε) d -approximation for a uniform matroid of rank k ≥ d+[d/(ε)] [30], where the rank k ≥ d denotes the desired size of the optimal set. Our main result is a new approximation algorithm for the general problem with an approximation guarantee that depends only on the dimension d of the vectors, and not on the size k of the output set. In particular, we show an (O(d)) d -estimation and an (O(d)) d3 -approximation for any matroid, giving a significant improvement over prior work when k ≫ d. Our result relies on showing that there exists an optimal solution to a convex programming relaxation for the problem which has sparse support; in particular, no more than O(d 2 ) variables of the solution have fractional values. The sparsity results rely on the interplay between the first order optimality conditions for the convex program and matroid theory. We believe that the techniques introduced to show sparsity of optimal solutions to convex programs will be of independent interest. We also give a new randomized rounding algorithm that crucially exploits the sparsity of solutions to the convex program. To show the approximation guarantee, we utilize recent works on strongly log-concave polynomials [8], [4] and show new relationships between different convex programs [33], [6] studied for the problem. Finally, we show how to use the estimation algorithm to give an efficient deterministic approximation algorithm. Once again, the algorithm crucially relies on sparsity of the fractional solution to guarantee that the approximation factor depends solely on the dimension d.

View PDF Chat

On Improving Resource Allocations by Sharing

2022-06-28

Robert Bredereck , Andrzej Kaczmarczyk , Junjie Luo +2 more

Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to higher social welfare, our goal is to improve the … Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where a resource may be shared by two neighbors in a social network and each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and tree-like (hierarchical) social networks.

View PDF Chat

Approximating Nash Social Welfare under Rado Valuations

2020-09-30

Jugal Garg , Edin Husić , László A. Végh

We consider the problem of approximating maximum Nash social welfare (NSW) while allocating a set of indivisible items to $n$ agents. The NSW is a popular objective that provides a … We consider the problem of approximating maximum Nash social welfare (NSW) while allocating a set of indivisible items to $n$ agents. The NSW is a popular objective that provides a balanced tradeoff between the often conflicting requirements of fairness and efficiency, defined as the weighted geometric mean of agents' valuations. For the symmetric additive case of the problem, where agents have the same weight with additive valuations, the first constant-factor approximation algorithm was obtained in 2015. This led to a flurry of work obtaining constant-factor approximation algorithms for the symmetric case under mild generalizations of additive, and $O(n)$-approximation algorithms for more general valuations and for the asymmetric case. In this paper, we make significant progress towards both symmetric and asymmetric NSW problems. We present the first constant-factor approximation algorithm for the symmetric case under Rado valuations. Rado valuations form a general class of valuation functions that arise from maximum cost independent matching problems, including as special cases assignment (OXS) valuations and weighted matroid rank functions. Furthermore, our approach also gives the first constant-factor approximation algorithm for the asymmetric case under Rado valuations, provided that the maximum ratio between the weights is bounded by a constant.

Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination

2020-07-16

Georgios Amanatidis , Evangelos Markakis , Apostolos Ntokos

View PDF Chat

Fair division of mixed divisible and indivisible goods

2021-01-05

Xiaohui Bei , Zihao Li , Jinyan Liu +2 more

View PDF Chat

Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination

2020-04-03

Georgios Amanatidis , Evangelos Markakis , Apostolos Ntokos

Several relaxations of envy-freeness, tailored to fair division in settings with indivisible goods, have been introduced within the last decade. Due to the lack of general existence results for most … Several relaxations of envy-freeness, tailored to fair division in settings with indivisible goods, have been introduced within the last decade. Due to the lack of general existence results for most of these concepts, great attention has been paid to establishing approximation guarantees. In this work, we propose a simple algorithm that is universally fair in the sense that it returns allocations that have good approximation guarantees with respect to four such fairness notions at once. In particular, this is the first algorithm achieving a (φ−1)-approximation of envy-freeness up to any good (EFX) and a 2/φ+2 -approximation of groupwise maximin share fairness (GMMS), where φ is the golden ratio. The best known approximation factor, in polynomial time, for either one of these fairness notions prior to this work was 1/2. Moreover, the returned allocation achieves envy-freeness up to one good (EF1) and a 2/3-approximation of pairwise maximin share fairness (PMMS). While EFX is our primary focus, we also exhibit how to fine-tune our algorithm and improve further the guarantees for GMMS or PMMS.Finally, we show that GMMS—and thus PMMS and EFX—allocations always exist when the number of goods does not exceed the number of agents by more than two.

View PDF Chat

A Little Charity Guarantees Almost Envy-Freeness

2019-07-10

Bhaskar Ray Chaudhury , T. Kavitha , Kurt Mehlhorn +1 more

Fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute $m$ goods to $n$ agents in a fair manner, where every agent … Fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute $m$ goods to $n$ agents in a fair manner, where every agent has a valuation for each subset of goods. We assume general valuations. Envy-freeness is the most extensively studied notion of fairness. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is up to any (EFX) where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists even when $n=3$. We show there is always a partition of the set of goods into $n+1$ subsets $(X_1,\ldots,X_n,P)$ where for $i \in [n]$, $X_i$ is the bundle allocated to agent $i$ and the set $P$ is unallocated (or donated to charity) such that we have$\colon$ 1) envy-freeness up to any good, 2) no agent values $P$ higher than her own bundle, and 3) fewer than $n$ goods go to charity, i.e., $|P| < n$ (typically $m \gg n$). Our proof is constructive. When agents have additive valuations and $\lvert P \rvert$ is large (i.e., when $|P|$ is close to $n$), our allocation also has a good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm also shows the existence of an allocation which is $4/7$ groupwise maximin share (GMMS): this is a notion of fairness stronger than MMS. This improves upon the current best bound of $1/2$ known for an approximate GMMS allocation.

Finding Fair and Efficient Allocations When Valuations Don’t Add Up

2020-01-01

Nawal Benabbou , Mithun Chakraborty , Ayumi Igarashi +1 more

View PDF Chat

An Additive Approximation Scheme for the Nash Social Welfare Maximization with Identical Additive Valuations

2022-01-01

Asei Inoue , Yusuke Kobayashi

View PDF Chat

Approximating Nash Social Welfare Under Binary XOS and Binary Subadditive Valuations

2022-01-01

Siddharth Barman , Paritosh Verma

View PDF Chat

Nash Welfare Guarantees for Fair and Efficient Coverage

2022-01-01

Siddharth Barman , Anand Krishna , Y. Narahari +1 more

View PDF Chat

On the number of almost envy-free allocations

2020-04-07

Warut Suksompong

View PDF Chat

A characterization of maximum Nash welfare for indivisible goods

2022-12-08

Warut Suksompong

In the allocation of indivisible goods, the maximum Nash welfare (MNW) rule, which chooses an allocation maximizing the product of the agents' utilities, has received substantial attention for its fairness. … In the allocation of indivisible goods, the maximum Nash welfare (MNW) rule, which chooses an allocation maximizing the product of the agents' utilities, has received substantial attention for its fairness. We characterize MNW as the only additive welfarist rule that satisfies envy-freeness up to one good. Our characterization holds even in the simplest setting of two agents.

View PDF Chat

Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings

2023-08-16

Jugal Garg , Pooja Kulkarni , Rucha Kulkarni

We study the problem of approximating maximum Nash social welfare (NSW) when allocating m indivisible items among n asymmetric agents with submodular valuations. The NSW is a well-established notion of … We study the problem of approximating maximum Nash social welfare (NSW) when allocating m indivisible items among n asymmetric agents with submodular valuations. The NSW is a well-established notion of fairness and efficiency, defined as the weighted geometric mean of agents’ valuations. For special cases of the problem with symmetric agents and additive(-like) valuation functions, approximation algorithms have been designed using approaches customized for these specific settings, and they fail to extend to more general settings. Hence, no approximation algorithm with a factor independent of m was known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(-like) valuations before this work. In this article, we extend our understanding of the NSW problem to far more general settings. Our main contribution is two approximation algorithms for asymmetric agents with additive and submodular valuations. Both algorithms are simple to understand and involve non-trivial modifications of a greedy repeated matchings approach. Allocations of high-valued items are done separately by un-matching certain items and re-matching them by different processes in both algorithms. We show that these approaches achieve approximation factors of O ( n ) and O ( n log n ) for additive and submodular cases, independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envy-free up to one item ( EF1 ). Furthermore, we show that the NSW problem under submodular valuations is strictly harder than all currently known settings with an $\frac{\mathrm{e}}{\mathrm{e}-1}$ factor of the hardness of approximation, even for constantly many agents. For this case, we provide a different approximation algorithm that achieves a factor of $\frac{\mathrm{e}}{\mathrm{e}-1}$ , hence resolving it completely.

View PDF Chat

Fast and Interpretable Dynamics for Fisher Markets via Block-Coordinate Updates

2023-06-26

Tianlong Nan , Yuan Gao , Christian Kroer

We consider the problem of large-scale Fisher market equilibrium computation through scalable first-order optimization methods. It is well-known that market equilibria can be captured using structured convex programs such as … We consider the problem of large-scale Fisher market equilibrium computation through scalable first-order optimization methods. It is well-known that market equilibria can be captured using structured convex programs such as the Eisenberg-Gale and Shmyrev convex programs. Highly performant deterministic full-gradient first-order methods have been developed for these programs. In this paper, we develop new block-coordinate first-order methods for computing Fisher market equilibria, and show that these methods have interpretations as tâtonnement-style or proportional response-style dynamics where either buyers or items show up one at a time. We reformulate these convex programs and solve them using proximal block coordinate descent methods, a class of methods that update only a small number of coordinates of the decision variable in each iteration. Leveraging recent advances in the convergence analysis of these methods and structures of the equilibrium-capturing convex programs, we establish fast convergence rates of these methods.

View PDF Chat

Unified Fair Allocation of Goods and Chores via Copies

2023-09-22

Yotam Gafni , Xin Huang , Ron Lavi +1 more

We consider fair allocation of indivisible items in a model with goods, chores, and copies, as a unified framework for studying: (1) the existence of EFX and other solution concepts … We consider fair allocation of indivisible items in a model with goods, chores, and copies, as a unified framework for studying: (1) the existence of EFX and other solution concepts for goods with copies; (2) the existence of EFX and other solution concepts for chores. We establish a tight relation between these issues via two conceptual contributions: First, a refinement of envy-based fairness notions that we term envy without commons (denoted EFX WC when applied to EFX). Second, a formal duality theorem relating the existence of a host of (refined) fair allocation concepts for copies to their existence for chores. We demonstrate the usefulness of our duality result by using it to characterize the existence of EFX for chores through the dual environment, as well as to prove EFX existence in the special case of leveled preferences over the chores. We further study the hierarchy among envy-freeness notions without commons and their α-MMS guarantees, showing, for example, that any EFX WC allocation guarantees at least $\frac{4}{11}$ -MMS for goods with copies.

View PDF Chat

Fair and Efficient Allocations under Subadditive Valuations

2021-05-18

Bhaskar Ray Chaudhury , Jugal Garg , Ruta Mehta

We study the problem of allocating a set of indivisible goods among agents with subadditive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is the … We study the problem of allocating a set of indivisible goods among agents with subadditive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is the most compelling notion of fairness in the context of indivisible goods. Although the existence of EFX is not known beyond the simple case of two agents with subadditive valuations, some good approximations of EFX are known to exist, namely 1/2-EFX allocation and EFX allocations with bounded charity. Nash welfare (the geometric mean of agents' valuations) is one of the most commonly used measures of efficiency. In case of additive valuations, an allocation that maximizes Nash welfare also satisfies fairness properties like Envy-Free up to one good (EF1). Although there is substantial work on approximating Nash welfare when agents have additive valuations, very little is known when agents have subadditive valuations. In this paper, we design a polynomial-time algorithm that outputs an allocation that satisfies either of the two approximations of EFX as well as achieves an O(n) approximation to the Nash welfare. Our result also improves the current best-known approximation of O(n log n) and O(m) to Nash welfare when agents have submodular and subadditive valuations, respectively. Furthermore, our technique also gives an O(n) approximation to a family of welfare measures, p-mean of valuations for p in (-\infty, 1], thereby also matching asymptotically the current best approximation ratio for special cases like p = -\infty while also retaining the remarkable fairness properties.

View PDF Chat

Fair allocation of combinations of indivisible goods and chores

2018-01-01

Haris Aziz , Ioannis Caragiannis , Ayumi Igarashi

We consider the problem of fairly dividing a set of items. Much of the fair division literature assumes that the items are `goods' i.e., they yield positive utility for the … We consider the problem of fairly dividing a set of items. Much of the fair division literature assumes that the items are `goods' i.e., they yield positive utility for the agents. There is also some work where the items are `chores' that yield negative utility for the agents. In this paper, we consider a more general scenario where an agent may have negative or positive utility for each item. This framework captures, e.g., fair task assignment, where agents can have both positive and negative utilities for each task. We show that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We present several new and efficient algorithms for finding fair allocations in this general setting. We also point out several gaps in the literature regarding the existence of allocations satisfying certain fairness and efficiency properties and further study the complexity of computing such allocations.

Estimating the Nash Social Welfare for coverage and other submodular valuations

2021-01-01

Wenzheng Li , Jan Vondrák

We study the Nash Social Welfare problem: Given $n$ agents with valuation functions $v_i:2^{[m]} \rightarrow {\mathbb R}$, partition $[m]$ into $S_1,\ldots,S_n$ so as to maximize $(\prod_{i=1}^{n} v_i(S_i))^{1/n}$. The problem has … We study the Nash Social Welfare problem: Given $n$ agents with valuation functions $v_i:2^{[m]} \rightarrow {\mathbb R}$, partition $[m]$ into $S_1,\ldots,S_n$ so as to maximize $(\prod_{i=1}^{n} v_i(S_i))^{1/n}$. The problem has been shown to admit a constant-factor approximation for additive, budget-additive, and piecewise linear concave separable valuations; the case of submodular valuations is open. We provide a $\frac{1}{e} (1-\frac{1}{e})^2$-approximation of the {\em optimal value} for several classes of submodular valuations: coverage, sums of matroid rank functions, and certain matching-based valuations.

View PDF Chat

Budget-feasible Maximum Nash Social Welfare Allocation is Almost Envy-free

2020-01-01

Xiaowei Wu , Bo Li , Jiarui Gan

The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has … The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. (EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up to one good (EF1). In this paper, we are interested in the fairness of the NSW in a budget-feasible allocation problem, in which each item has a cost that will be incurred to the agent it is allocated to, and each agent has a budget constraint on the total cost of items she receives. We show that a budget-feasible allocation that maximizes the NSW achieves a 1/4-approximation of EF1 and the approximation ratio is tight. The approximation ratio improves gracefully when the items have small costs compared with the agents' budgets; it converges to 1/2 when the budget-cost ratio approaches infinity.

Almost Envy-freeness, Envy-rank, and Nash Social Welfare Matchings

2021-05-18

Alireza Farhadi , MohammadTaghi Hajiaghayi , Mohamad Latifian +2 more

Envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) are two well-known extensions of envy-freeness for the case of indivisible items. It is shown that EF1 … Envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) are two well-known extensions of envy-freeness for the case of indivisible items. It is shown that EF1 can always be guaranteed for agents with subadditive valuations. In sharp contrast, it is unknown whether or not an EFX allocation always exists, even for four agents and additive valuations. In addition, the best approximation guarantee for EFX is (φ − 1) ≃ 0.61 by Amanitidis et al.. In order to find a middle ground to bridge this gap, in this paper we suggest another fairness criterion, namely envy-freeness up to a random good or EFR, which is weaker than EFX, yet stronger than EF1. For this notion, we provide a polynomial-time 0.73-approximation allocation algorithm. For our algorithm we introduce Nash Social Welfare Matching which makes a connection between Nash Social Welfare and envy freeness.

View PDF Chat

Nash Social Welfare Approximation for Strategic Agents

2021-02-17

Simina Brânzei , Vasilis Gkatzelis , Ruta Mehta

We study the problem of allocating divisible resources to agents with different preferences. We analyze a market game known as Trading Post, first considered by Shapley and Shubik, where each … We study the problem of allocating divisible resources to agents with different preferences. We analyze a market game known as Trading Post, first considered by Shapley and Shubik, where each agent gets a budget of virtual currency to bid on goods: after bids are placed, goods are allocated to players in proportion to their bids. In this setting, the agents choose their bids strategically, aiming to maximize their utility, and this gives rise to a game. We study the equilibrium allocations of this game, measuring the quality of an allocation via the Nash social welfare, the geometric mean of utilities (a measure of aggregate welfare that respects individual needs). We show that any Nash equilibrium of Trading Post approximates the optimal Nash welfare within a factor of two for all concave valuations, and the mechanism is essentially optimal for Leontief valuations.

View PDF Chat

Computing welfare-Maximizing fair allocations of indivisible goods

2022-10-13

Haris Aziz , Xin Huang , Nicholas Mattei +1 more

View PDF Chat

Fair and Efficient Allocations under Lexicographic Preferences

2021-05-18

Hadi Hosseini , Sujoy Sikdar , Rohit Vaish +1 more

Envy-freeness up to any good (EFX) provides a strong and intuitive guarantee of fairness in the allocation of indivisible goods. But whether such allocations always exist or whether they can … Envy-freeness up to any good (EFX) provides a strong and intuitive guarantee of fairness in the allocation of indivisible goods. But whether such allocations always exist or whether they can be efficiently computed remains an important open question. We study the existence and computation of EFX in conjunction with various other economic properties under lexicographic preferences--a well-studied preference restriction model in artificial intelligence and economics. In sharp contrast to the known results for additive valuations, we not only prove the existence of EFX and Pareto optimal allocations, but in fact provide an algorithmic characterization of these two properties. We also characterize the mechanisms that are, in addition, strategyproof, non-bossy, and neutral. When the efficiency notion is strengthened to rank-maximality, we obtain non-existence and computational hardness results, and show that tractability can be restored when EFX is relaxed to another well-studied fairness notion called maximin share guarantee (MMS).

View PDF Chat

On Fair and Efficient Allocations of Indivisible Goods

2021-05-18

Aniket Murhekar , Jugal Garg

We study the problem of fair and efficient allocation of a set of indivisible goods to agents with additive valuations using the popular fairness notions of envy-freeness up to one … We study the problem of fair and efficient allocation of a set of indivisible goods to agents with additive valuations using the popular fairness notions of envy-freeness up to one good (EF1) and equitability up to one good (EQ1) in conjunction with Pareto-optimality (PO). There exists a pseudo-polynomial time algorithm to compute an EF1+PO allocation, and a non-constructive proof of existence of allocations that are both EF1 and fractionally Pareto-optimal (fPO). We present a pseudo-polynomial time algorithm to compute an EF1+fPO allocation, thereby improving the earlier results. Our techniques also enable us to show that an EQ1+fPO allocation always exists when the values are positive, and that it can be computed in pseudo-polynomial time. We also consider the class of k-ary instances where k is a constant, i.e., each agent has at most k different values for the goods. We show that for such instances an EF1+fPO allocation can be computed in polynomial time. When all values are positive, we show that an EQ1+fPO allocation for such instances can be computed in polynomial time. Next, we consider instances where the number of agents is constant, and show that an EF1+PO (also EQ1+PO) allocation can be computed in polynomial time. These results significantly extend the polynomial-time computability beyond the known cases of binary or identical valuations. Further, we show that the problem of computing an EF1+PO allocation polynomial-time reduces to a problem in the complexity class PLS. We also design a polynomial-time algorithm that computes Nash welfare maximizing allocations when there are constantly many agents with constant many different values for the goods.

View PDF Chat

Achieving Proportionality up to the Maximin Item with Indivisible Goods

2021-05-18

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. The indivisibility of the goods is long known to pose highly non-trivial … We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. The indivisibility of the goods is long known to pose highly non-trivial obstacles to achieving fairness, and a very vibrant line of research has aimed to circumvent them using appropriate notions of approximate fairness. Recent work has established that even approximate versions of proportionality (PROPx) may be impossible to achieve even for small instances, while the best known achievable approximations (PROP1) are much weaker. We introduce the notion of proportionality up to the maximin item (PROPm) and show how to reach an allocation satisfying this notion for any instance involving up to five agents with additive valuations. PROPm provides a well-motivated middle-ground between PROP1 and PROPx, while also capturing some elements of the well-studied maximin share (MMS) benchmark: another relaxation of proportionality that has attracted a lot of attention.

View PDF Chat

Infinite-Dimensional Fisher Markets and Tractable Fair Division

2022-09-21

Yuan Gao , Christian Kroer

Fisher market equilibrium models have long been a central topic in economics and computation. Recently, they have been widely used in the design and implementation of Internet marketplaces. Although the … Fisher market equilibrium models have long been a central topic in economics and computation. Recently, they have been widely used in the design and implementation of Internet marketplaces. Although the classical models are well studied and can be solved via tractable optimization characterizations, they only allow a finite number of items and thus face scalability issues when the item space is huge or even continuous. In “Infinite-Dimensional Fisher Markets and Tractable Fair Division,” Gao and Kroer propose infinite-dimensional convex programs and show that they capture market equilibria for infinite and possibly continuous item spaces, extending the classical Eisenberg-Gale framework. Using these results, the authors show that a challenging cake-cutting problem for piecewise linear agent valuations is equivalent to finding a market equilibrium and admits a tractable convex optimization characterization. Thus, it can be solved in polynomial time in theory and highly efficiently by numerical optimization software.

View PDF Chat

Satiation in Fisher Markets and Approximation of Nash Social Welfare

2023-07-18

Jugal Garg , Martin Hoefer , Kurt Mehlhorn

We study linear Fisher markets with satiation. In these markets, sellers have earning limits, and buyers have utility limits. Beyond applications in economics, they arise in the context of maximizing … We study linear Fisher markets with satiation. In these markets, sellers have earning limits, and buyers have utility limits. Beyond applications in economics, they arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not guaranteed. We identify a natural property of markets (termed money clearing) that implies existence. We show that the set of equilibria is not always convex, answering a question posed in the literature. We design an FPTAS to compute an approximate equilibrium and prove that the problem of computing an exact equilibrium lies in the complexity class continuous local search ([Formula: see text]; i.e., the intersection of polynomial local search ([Formula: see text]) and polynomial parity arguments on directed graphs ([Formula: see text])). For a constant number of buyers or goods, we give a polynomial-time algorithm to compute an exact equilibrium. We show how (approximate) equilibria can be rounded and provide the first constant-factor approximation algorithm (with a factor of 2.404) for maximizing Nash social welfare when agents have capped linear (also known as budget-additive) valuations. Finally, we significantly improve the approximation hardness for additive valuations to [Formula: see text]. Funding: J. Garg was supported by the National Science Foundation [Grant CCF-1942321 (CAREER)]. M. Hoefer was supported by Deutsche Forschungsgemeinschaft [Grants Ho 3831/5-1, Ho 3831/6-1, and Ho 3831/7-1].

View PDF Chat

On Optimal Tradeoffs between EFX and Nash Welfare

2024-03-24

Michal Feldman , Simon Mauras , Tomasz Ponitka

A major problem in fair division is how to allocate a set of indivisible resources among agents fairly and efficiently. The goal of this work is to characterize the tradeoffs … A major problem in fair division is how to allocate a set of indivisible resources among agents fairly and efficiently. The goal of this work is to characterize the tradeoffs between two well-studied measures of fairness and efficiency --- envy freeness up to any item (EFX) for fairness, and Nash welfare for efficiency --- by saying, for given constants α and β, whether there exists an α-EFX allocation that guarantees a β-fraction of the maximum Nash welfare (β-MNW). For additive valuations, we show that for any α ∈ [0,1], there exists a partial allocation that is α-EFX and 1/(α+1)-MNW. This tradeoff turns out to be tight (for every α) as demonstrated by an impossibility result that we give. We also show that for α ∈ [0, φ-1 ≃ 0.618] these partial allocations can be turned into complete allocations where all items are assigned. Furthermore, for any α ∈ [0, 1/2], we show that the tight tradeoff of α-EFX and 1/(α+1)-MNW with complete allocations holds for the more general setting of subadditive valuations. Our results improve upon the current state of the art, for both additive and subadditive valuations, and match the best-known approximations of EFX under complete allocations, regardless of Nash welfare guarantees. Notably, our constructions for additive valuations also provide EF1 and constant approximations for maximin share guarantees.

View PDF Chat

Two Algorithms for Additive and Fair Division of Mixed Manna

2020-07-08

Martin Aleksandrov , Toby Walsh

We consider a fair division model in which agents have positive, zero and negative utilities for items. For this model, we analyse one existing fairness property - EFX - and … We consider a fair division model in which agents have positive, zero and negative utilities for items. For this model, we analyse one existing fairness property - EFX - and three new and related properties - EFX$_0$, EFX$^3$ and EF1$^3$ - in combination with Pareto-optimality. With general utilities, we give a modified version of an existing algorithm for computing an EF1$^3$ allocation. With $-\alpha/0/\alpha$ utilities, this algorithm returns an EFX$^3$ and PO allocation. With absolute identical utilities, we give a new algorithm for an EFX and PO allocation. With $-\alpha/0/\beta$ utilities, this algorithm also returns such an allocation. We report some new impossibility results as well.

Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints

2019-07-17

Ayumi Igarashi , Dominik Peters

We study the problem of allocating indivisible items to agents with additive valuations, under the additional constraint that bundles must be connected in an underlying item graph. Previous work has … We study the problem of allocating indivisible items to agents with additive valuations, under the additional constraint that bundles must be connected in an underlying item graph. Previous work has considered the existence and complexity of fair allocations. We study the problem of finding an allocation that is Pareto-optimal. While it is easy to find an efficient allocation when the underlying graph is a path or a star, the problem is NP-hard for many other graph topologies, even for trees of bounded pathwidth or of maximum degree 3. We show that on a path, there are instances where no Pareto-optimal allocation satisfies envy-freeness up to one good, and that it is NP-hard to decide whether such an allocation exists, even for binary valuations. We also show that, for a path, it is NP-hard to find a Pareto-optimal allocation that satisfies maximin share, but show that a moving-knife algorithm can find such an allocation when agents have binary valuations that have a non-nested interval structure.

View PDF Chat

Using the Borsuk–Ulam Theorem

2008-01-01

Jiřı́ Matoušek

Using the Borsuk-Ulam theorem : lectures on topological methods in combinatorics and geometry

2008-01-01

Jiřı́ Matoušek , Anders Björner , Günter M. Ziegler

Consensus of Subjective Probabilities: The Pari-Mutuel Method

1959-03-01

E. Eisenberg , David Gale

Abstract : Under the pari-mutuel system of betting on horse races the final track's odds are in some sense a consensus of the 'subjective odds' of the individual bettors weighted … Abstract : Under the pari-mutuel system of betting on horse races the final track's odds are in some sense a consensus of the 'subjective odds' of the individual bettors weighted by the amounts of their bets. The properties which this consensus must possess and prove that there always exists a unique set of odds having the required properties are formulated. (Author)

View PDF Chat

Convex Program Duality, Fisher Markets, and Nash Social Welfare

2017-06-20

Richard Cole , Nikhil R. Devanur , Vasilis Gkatzelis +4 more

No abstract available. No abstract available.

View PDF Chat

Approximating the Nash Social Welfare with Budget-Additive Valuations

2017-07-14

Jugal Garg , Martin Hoefer , Kurt Mehlhorn

We present the first constant-factor approximation algorithm for maximizing the Nash social welfare when allocating indivisible items to agents with budget-additive valuation functions. Budget-additive valuations represent an important class of … We present the first constant-factor approximation algorithm for maximizing the Nash social welfare when allocating indivisible items to agents with budget-additive valuation functions. Budget-additive valuations represent an important class of submodular functions. They have attracted a lot of research interest in recent years due to many interesting applications. For every $\varepsilon > 0$, our algorithm obtains a $(2.404 + \varepsilon)$-approximation in time polynomial in the input size and $1/\varepsilon$. Our algorithm relies on rounding an approximate equilibrium in a linear Fisher market where sellers have earning limits (upper bounds on the amount of money they want to earn) and buyers have utility limits (upper bounds on the amount of utility they want to achieve). In contrast to markets with either earning or utility limits, these markets have not been studied before. They turn out to have fundamentally different properties. Although the existence of equilibria is not guaranteed, we show that the market instances arising from the Nash social welfare problem always have an equilibrium. Further, we show that the set of equilibria is not convex, answering a question of [Cole et al, EC 2017]. We design an FPTAS to compute an approximate equilibrium, a result that may be of independent interest.

Finding Fair and Efficient Allocations

2017-07-15

Siddharth Barman , Sanath Kumar Krishnamurthy , Rohit Vaish

We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if … We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if it is envy-free up to one good (EF1), which means that each agent prefers its own bundle over the bundle of any other agent up to the removal of one good. In addition, an allocation is deemed efficient if it satisfies Pareto optimality (PO). While each of these well-studied properties is easy to achieve separately, achieving them together is far from obvious. Recently, Caragiannis et al. (2016) established the surprising result that when agents have additive valuations for the goods, there always exists an allocation that simultaneously satisfies these two seemingly incompatible properties. Specifically, they showed that an allocation that maximizes the Nash social welfare (NSW) objective is both EF1 and PO. However, the problem of maximizing NSW is NP-hard. As a result, this approach does not provide an efficient algorithm for finding a fair and efficient allocation. In this paper, we bypass this barrier, and develop a pseudopolynomial time algorithm for finding allocations that are EF1 and PO; in particular, when the valuations are bounded, our algorithm finds such an allocation in polynomial time. Furthermore, we establish a stronger existence result compared to Caragiannis et al. (2016): For additive valuations, there always exists an allocation that is EF1 and fractionally PO. Another contribution of our work is to show that our algorithm provides a polynomial-time 1.45-approximation to the NSW objective. This improves upon the best known approximation ratio for this problem (namely, the 2-approximation algorithm of Cole et al. (2017)). Unlike many of the existing approaches, our algorithm is completely combinatorial.

APX-hardness of maximizing Nash social welfare with indivisible items

2017-02-23

Euiwoong Lee

View PDF Chat