Fairly Allocating Many Goods with Few Queries

Authors

Hoon Oh, Ariel D. Procaccia, Warut Suksompong

Type: Article

Publication Date: 2021-01-01

Citations: 7

DOI: https://doi.org/10.1137/20m1313349

View Ask PDF

Abstract

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

Locations

SIAM Journal on Discrete Mathematics
View
arXiv (Cornell University)
View PDF
Oxford University Research Archive (ORA) (University of Oxford)
View PDF
DataCite API
View

Ask a Question About This Paper

Summary

Fairly Allocating Many Goods with Few Queries

2019-07-17

Hoon Oh , Ariel D. Procaccia , Warut Suksompong

We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic valuations, we design an algorithm that computes an allocation satisfying envy-freeness up … We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic valuations, we design an algorithm that computes an allocation satisfying envy-freeness up to one good (EF1), a relaxation of envy-freeness, using a logarithmic number of queries. We show that the logarithmic query complexity bound also holds for three agents with additive valuations. These results suggest that it is possible to fairly allocate goods in practice even when the number of goods is extremely large. By contrast, we prove that computing an allocation satisfying envyfreeness and another of its relaxations, envy-freeness up to any good (EFX), requires a linear number of queries even when there are only two agents with identical additive valuations.

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

Fair Division: The Computer Scientist’s Perspective

2020-07-01

Toby Walsh

I survey recent progress on a classic and challenging problem in social choice: the fair division of indivisible items. I discuss how a computational perspective has provided interesting insights into … I survey recent progress on a classic and challenging problem in social choice: the fair division of indivisible items. I discuss how a computational perspective has provided interesting insights into and understanding of how to divide items fairly and efficiently. This has involved bringing to bear tools such as those used in knowledge representation, computational complexity, approximation methods, game theory, online analysis and communication complexity.

View PDF Chat

Balanced Allocations with Incomplete Information: The Power of Two Queries

2021-01-01

Dimitrios Los , Thomas Sauerwald

We consider the allocation of $m$ balls into $n$ bins with incomplete information. In the classical Two-Choice process a ball first queries the load of two randomly chosen bins and … We consider the allocation of $m$ balls into $n$ bins with incomplete information. In the classical Two-Choice process a ball first queries the load of two randomly chosen bins and is then placed in the least loaded bin. In our setting, each ball also samples two random bins but can only estimate a bin's load by sending binary queries of the form "Is the load at least the median?" or "Is the load at least 100?". For the lightly loaded case $m=O(n)$, Feldheim and Gurel-Gurevich (2021) showed that with one query it is possible to achieve a maximum load of $O(\sqrt{\log n/\log \log n})$, and posed the question whether a maximum load of $m/n+O(\sqrt{\log n/\log \log n})$ is possible for any $m = \Omega(n)$. In this work, we resolve this open problem by proving a lower bound of $m/n+\Omega( \sqrt{\log n})$ for a fixed $m=\Theta(n \sqrt{\log n})$, and a lower bound of $m/n+\Omega(\log n/\log \log n)$ for some $m$ depending on the used strategy. We complement this negative result by proving a positive result for multiple queries. In particular, we show that with only two binary queries per chosen bin, there is an oblivious strategy which ensures a maximum load of $m/n+O(\sqrt{\log n})$ for any $m \geq 1$. Further, for any number of $k = O(\log \log n)$ binary queries, the upper bound on the maximum load improves to $m/n + O(k(\log n)^{1/k})$ for any $m \geq 1$. Further, this result for $k$ queries implies (i) new bounds for the $(1+\beta)$-process introduced by Peres et al (2015), (ii) new bounds for the graphical balanced allocation process on dense expander graphs, and (iii) the bound of $m/n+O(\log \log n)$ on the maximum load achieved by the Two-Choice process, including the heavily loaded case $m=\Omega(n)$ derived by Berenbrink et al. (2006). One novel aspect of our proofs is the use of multiple super-exponential potential functions, which might be of use in future work.

View PDF Chat

Problem Solutions

2022-04-25

Richard J. Rossi

SOLUTIONS FOR CHAPTER 1 1.1Biostatistics is the area of statistics that deals with the methodology for collecting and analyzing biomedical or healthcare data.1.3 NIH, CDC, FDA 1.4 (a) The population … SOLUTIONS FOR CHAPTER 1 1.1Biostatistics is the area of statistics that deals with the methodology for collecting and analyzing biomedical or healthcare data.1.3 NIH, CDC, FDA 1.4 (a) The population of interest; (b) A subset of the units of the population; (c) A sample consisting of the entire population.1.6 (a) A numerical measure of a population characteristic; (b) A value computed from only the information in the sample and known values.

View PDF Chat

A Simple Search Problem.

2021-05-17

Marshall W. Buck , Douglas H. Wiedemann

A simple problem is studied in which there are N boxes and a prize known to be in one of the boxes. Furthermore, the probability that the prize is in … A simple problem is studied in which there are N boxes and a prize known to be in one of the boxes. Furthermore, the probability that the prize is in any box is given. It is desired to find the prize with minimal expected work, where it takes one unit of work to open a box and look inside. The paper establishes bounds on the minimal work in terms of the $p=1/2$ Holder norm of the probability density and in terms of the entropy of the probability density. We also introduce the notion of Cartesian product of problems, and determine the asymptotic behavior of the minimal work for the $n$th power of a problem. (This article is a newly typeset version of an internal publication written in 1984. The second author passed away on November 12, 2020, and his estate has approved the submission of this paper.)

Fair Division: The Computer Scientist's Perspective

2020-05-11

Toby Walsh

Fair Division: The Computer Scientist's Perspective

2020-01-01

Toby Walsh

On Connected Strongly-Proportional Cake-Cutting

2024-10-16

Zsuzsanna Jankó , Attila Joó , Erel Segal-Halevi +1 more

We investigate the problem of fairly dividing a divisible heterogeneous resource, also known as a cake, among a set of agents who may have different entitlements. We characterize the existence … We investigate the problem of fairly dividing a divisible heterogeneous resource, also known as a cake, among a set of agents who may have different entitlements. We characterize the existence of a connected strongly-proportional allocation—one in which every agent receives a contiguous piece worth strictly more than their proportional share. The characterization is supplemented with an algorithm that determines its existence using O(n·2n) queries. We devise a simpler characterization for agents with strictly positive valuations and with equal entitlements, and present an algorithm to determine the existence of such an allocation using O(n2) queries. We provide matching lower bounds in the number of queries for both algorithms. When a connected strongly-proportional allocation exists, we show that it can also be computed using a similar number of queries. The full version is available at https://arxiv.org/abs/2312.15326.

View PDF Chat

A simple Online Fair Division problem.

2019-01-01

Anna Bogomolnaia , Hervé Moulin , Fedor Sandomirskiy

Beyond Cake Cutting: Allocating Homogeneous Divisible Goods

2022-01-01

Ioannis Caragiannis , Vasilis Gkatzelis , Alexandros Psomas +1 more

The problem of fair division known as "cake cutting" has been the focus of multiple papers spanning several decades. The most prominent problem in this line of work has been … The problem of fair division known as "cake cutting" has been the focus of multiple papers spanning several decades. The most prominent problem in this line of work has been to bound the query complexity of computing an envy-free outcome in the Robertson-Webb query model. However, the root of this problem's complexity is somewhat artificial: the agents' values are assumed to be additive across different pieces of the "cake" but infinitely complicated within each piece. This is unrealistic in most of the motivating examples, where the cake represents a finite collection of homogeneous goods. We address this issue by introducing a fair division model that more accurately captures these applications: the value that an agent gains from a given good depends only on the amount of the good they receive, yet it can be an arbitrary function of this amount, allowing the agents to express preferences that go beyond standard cake cutting. In this model, we study the query complexity of computing allocations that are not just envy-free, but also approximately Pareto optimal among all envy-free allocations. Using a novel flow-based approach, we show that we can encode the ex-post feasibility of randomized allocations via a polynomial number of constraints, which reduces our problem to solving a linear program.

View PDF Chat

Fair division of indivisible goods: Recent progress and open questions

2023-06-16

Georgios Amanatidis , Haris Aziz , Georgios Birmpas +5 more

Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources … Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources that are infinitely divisible. Over the last decade, there has been a surge of papers studying computational questions regarding the indivisible case, for which exact fairness notions such as envy-freeness and proportionality are hard to satisfy. One main theme in the recent research agenda is to investigate the extent to which their relaxations, like maximin share fairness (MMS) and envy-freeness up to any good (EFX), can be achieved. In this survey, we present a comprehensive review of the recent progress made in the related literature by highlighting different ways to relax fairness notions, common algorithm design techniques, and the most interesting questions for future research.

View PDF Chat

Fair Division of Indivisible Goods: Recent Progress and Open Questions

2022-01-01

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

View PDF Chat

ONE-SIDED WEIGHTED APPROXIMATION

2008-01-01

Oleksandr Maizlish

Don’t Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond

2024-03-12

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

.In most social choice settings, the participating agents express their preferences over the different alternatives in the form of linear orderings. While this clearly simplifies preference elicitation, it inevitably leads … .In most social choice settings, the participating agents express their preferences over the different alternatives in the form of linear orderings. While this clearly simplifies preference elicitation, it inevitably leads to poor performance with respect to optimizing a cardinal objective, such as the social welfare, since the values of the agents remain virtually unknown. This loss in performance because of lack of information is measured by the notion of distortion. A recent array of works put forward the agenda of designing mechanisms that learn the values of the agents for a small number of alternatives via queries, and use this limited extra information to make better-informed decisions, thus improving distortion. Following this agenda, in this work we focus on a class of combinatorial problems that includes most well-known matching problems and several of their generalizations. For problems such as One-Sided Matching, Two-Sided Matching, General Graph Matching, and Short Cycle Packing, we design two-query mechanisms that achieve the best-possible worst-case distortion in terms of social welfare, and outperform the best-possible expected distortion achieved by randomized ordinal mechanisms. Our results extend to problems like $k$-Constrained Resource Allocation, General Graph $k$-Matching, and $k$-Clique Packing, when $k$ is restricted to be any constant.Keywordsdistortionqueriesmatchingsocial choicegraph problemsMSC codes68Q2568W2568W4091B1291B1491B68

View PDF Chat

Fair Division with Allocator's Preference

2023-01-01

Xiaolin Bu , Zihao Li , Shengxin Liu +2 more

We consider the fair allocation problem of indivisible items. Most previous work focuses on fairness and/or efficiency among agents given agents' preferences. However, besides the agents, the allocator as the … We consider the fair allocation problem of indivisible items. Most previous work focuses on fairness and/or efficiency among agents given agents' preferences. However, besides the agents, the allocator as the resource owner may also be involved in many real-world scenarios, e.g., heritage division. The allocator has the inclination to obtain a fair or efficient allocation based on her own preference over the items and to whom each item is allocated. In this paper, we propose a new model and focus on the following two problems: 1) Is it possible to find an allocation that is fair for both the agents and the allocator? 2) What is the complexity of maximizing the allocator's social welfare while satisfying the agents' fairness? We consider the two fundamental fairness criteria: envy-freeness and proportionality. For the first problem, we study the existence of an allocation that is envy-free up to $c$ goods (EF-$c$) or proportional up to $c$ goods (PROP-$c$) from both the agents' and the allocator's perspectives, in which such an allocation is called doubly EF-$c$ or doubly PROP-$c$ respectively. When the allocator's utility depends exclusively on the items (but not to whom an item is allocated), we prove that a doubly EF-$1$ allocation always exists. For the general setting where the allocator has a preference over the items and to whom each item is allocated, we prove that a doubly EF-$1$ allocation always exists for two agents, a doubly PROP-$2$ allocation always exists for binary valuations, and a doubly PROP-$O(\log n)$ allocation always exists in general. For the second problem, we provide various (in)approximability results in which the gaps between approximation and inapproximation ratios are asymptotically closed under most settings. Most results are based on novel technical tools including the chromatic numbers of the Kneser graphs and linear programming-based analysis.

Fair Allocation of goods and chores -- Tutorial and Survey of Recent Results

2023-01-01

Shaily Mishra , Manisha Padala , Sujit Gujar

Fair resource allocation is an important problem in many real-world scenarios, where resources such as goods and chores must be allocated among agents. In this survey, we delve into the … Fair resource allocation is an important problem in many real-world scenarios, where resources such as goods and chores must be allocated among agents. In this survey, we delve into the intricacies of fair allocation, focusing specifically on the challenges associated with indivisible resources. We define fairness and efficiency within this context and thoroughly survey existential results, algorithms, and approximations that satisfy various fairness criteria, including envyfreeness, proportionality, MMS, and their relaxations. Additionally, we discuss algorithms that achieve fairness and efficiency, such as Pareto Optimality and Utilitarian Welfare. We also study the computational complexity of these algorithms, the likelihood of finding fair allocations, and the price of fairness for each fairness notion. We also cover mixed instances of indivisible and divisible items and investigate different valuation and allocation settings. By summarizing the state-of-the-art research, this survey provides valuable insights into fair resource allocation of indivisible goods and chores, highlighting computational complexities, fairness guarantees, and trade-offs between fairness and efficiency. It serves as a foundation for future advancements in this vital field.

View PDF Chat

Mixed Fair Division: A Survey

2024-08-10

Shengxin Liu , Xinhang Lu , Mashbat Suzuki +1 more

Fair division considers the allocation of scarce resources among agents in such a way that every agent gets a fair share. It is a fundamental problem in society and has … Fair division considers the allocation of scarce resources among agents in such a way that every agent gets a fair share. It is a fundamental problem in society and has received significant attention and rapid developments from the game theory and artificial intelligence communities in recent years. The majority of the fair division literature can be divided along at least two orthogonal directions: goods versus chores, and divisible versus indivisible resources. In this survey, besides describing the state of the art, we outline a number of interesting open questions and future directions in three mixed fair division settings: (i) indivisible goods and chores, (ii) divisible and indivisible goods (mixed goods), and (iii) indivisible goods with subsidy which can be viewed like a divisible good.

View PDF Chat

Mixed Fair Division: A Survey

2023-01-01

Shengxin Liu , Xinhang Lu , Mashbat Suzuki +1 more

View PDF Chat

A Simple Search Problem

2021-01-01

Marshall W. Buck , Doug Wiedemann

A simple problem is studied in which there are N boxes and a prize known to be in one of the boxes. Furthermore, the probability that the prize is in … A simple problem is studied in which there are N boxes and a prize known to be in one of the boxes. Furthermore, the probability that the prize is in any box is given. It is desired to find the prize with minimal expected work, where it takes one unit of work to open a box and look inside. The paper establishes bounds on the minimal work in terms of the $p=1/2$ Hölder norm of the probability density and in terms of the entropy of the probability density. We also introduce the notion of "Cartesian product" of problems, and determine the asymptotic behavior of the minimal work for the $n$th power of a problem. (This article is a newly typeset version of an internal publication written in 1984. The second author passed away on November 12, 2020, and his estate has approved the submission of this paper.)

Consensus Halving for Sets of Items

2022-02-10

Paul W. Goldberg , Alexandros Hollender , Ayumi Igarashi +2 more

Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work shows that, when the resource is represented … Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work shows that, when the resource is represented by an interval, a consensus halving with at most n cuts always exists but is hard to compute even for agents with simple valuation functions. In this paper, we study consensus halving in a natural setting in which the resource consists of a set of items without a linear ordering. For agents with linear and additively separable utilities, we present a polynomial-time algorithm that computes a consensus halving with at most n cuts and show that n cuts are almost surely necessary when the agents’ utilities are randomly generated. On the other hand, we show that, for a simple class of monotonic utilities, the problem already becomes polynomial parity argument, directed version–hard. Furthermore, we compare and contrast consensus halving with the more general problem of consensus k-splitting, with which we wish to divide the resource into k parts in possibly unequal ratios and provide some consequences of our results on the problem of computing small agreeable sets.

View PDF Chat

Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints

2018-01-01

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

PROPm Allocations of Indivisible Goods to Multiple Agents

2021-05-24

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior … We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior work showed that there exists an allocation that satisfies this notion of fairness for instances involving up to five agents, but fell short of proving that this is true in general. We extend this result to show that a PROPm allocation is guaranteed to exist for all instances, independent of the number of agents or goods. Our proof is constructive, providing an algorithm that computes such an allocation and, unlike prior work, the running time of this algorithm is polynomial in both the number of agents and the number of goods.

The Price of Connectivity in Fair Division

2022-05-19

Xiaohui Bei , Ayumi Igarashi , Xinhang Lu +1 more

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected … We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest multiplicative gap between the graph-specific and the unconstrained maximin share and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.

View PDF Chat

Almost Envy-Free Allocations with Connected Bundles

2018-08-28

Vittorio Bilò , Ioannis Caragiannis , Michele Flammini +5 more

We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an … We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph G. When the items are arranged in a path, we show that EF1 allocations are guaranteed to exist for arbitrary monotonic utility functions over bundles, provided that either there are at most four agents, or there are any number of agents but they all have identical utility functions. Our existence proofs are based on classical arguments from the divisible cake-cutting setting, and involve discrete analogues of cut-and-choose, of Stromquist's moving-knife protocol, and of the Su-Simmons argument based on Sperner's lemma. Sperner's lemma can also be used to show that on a path, an EF2 allocation exists for any number of agents. Except for the results using Sperner's lemma, all of our procedures can be implemented by efficient algorithms. Our positive results for paths imply the existence of connected EF1 or EF2 allocations whenever G is traceable, i.e., contains a Hamiltonian path. For the case of two agents, we completely characterize the class of graphs $G$ that guarantee the existence of EF1 allocations as the class of graphs whose biconnected components are arranged in a path. This class is strictly larger than the class of traceable graphs; one can be check in linear time whether a graph belongs to this class, and if so return an EF1 allocation.

Approximation Algorithms for Computing Maximin Share Allocations

2017-10-31

Georgios Amanatidis , Evangelos Markakis , Afshin Nikzad +1 more

We study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of $n$ agents and a set of goods, the maximin share of a … We study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of $n$ agents and a set of goods, the maximin share of a single agent is the best that she can guarantee to herself, if she would be allowed to partition the goods in any way she prefers, into $n$ bundles, and then receive her least desirable bundle. The objective then in our problem is to find a partition, so that each agent is guaranteed her maximin share. In settings with indivisible goods, such allocations are not guaranteed to exist, so we resort to approximation algorithms. Our main result is a $2/3$-approximation, that runs in polynomial time for any number of agents. This improves upon the algorithm of Procaccia and Wang, which also produces a $2/3$-approximation but runs in polynomial time only for a constant number of agents. To achieve this, we redesign certain parts of their algorithm. Furthermore, motivated by the apparent difficulty, both theoretically and experimentally, in finding lower bounds on the existence of approximate solutions, we undertake a probabilistic analysis. We prove that in randomly generated instances, with high probability there exists a maximin share allocation. This can be seen as a justification of the experimental evidence reported in relevant works. Finally, we provide further positive results for two special cases that arise from previous works. The first one is the intriguing case of $3$ agents, for which it is already known that exact maximin share allocations do not always exist (contrary to the case of $2$ agents). We provide a $7/8$-approximation algorithm, improving the previously known result of $3/4$. The second case is when all item values belong to $\{0, 1, 2\}$, extending the $\{0, 1\}$ setting studied in Bouveret and Lema\^itre. We obtain an exact algorithm for any number of agents in this case.

View PDF Chat

A discrete and bounded envy-free cake cutting protocol for four agents

2016-06-10

Haris Aziz , Simon Mackenzie

We consider the well-studied cake cutting problem in which the goal is to identify an envy-free allocation based on a minimal number of queries from the agents. The problem has … We consider the well-studied cake cutting problem in which the goal is to identify an envy-free allocation based on a minimal number of queries from the agents. The problem has attracted considerable attention within various branches of computer science, mathematics, and economics. Although, the elegant Selfridge-Conway envy-free protocol for three agents has been known since 1960, it has been a major open problem to obtain a bounded envy-free protocol for more than three agents. The problem has been termed the central open problem in cake cutting. We solve this problem by proposing a discrete and bounded envy-free protocol for four agents.

View PDF Chat

Approximation Algorithms for Maximin Fair Division

2017-06-20

Siddharth Barman , Sanath Kumar Krishna Murthy

We consider the problem of dividing indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin … We consider the problem of dividing indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share, that is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into n bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focussed on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations a 2/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee.

View PDF Chat

The Query Complexity of Cake Cutting.

2017-05-08

Simina Brânzei , Noam Nisan

We study the query complexity of cake cutting and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower … We study the query complexity of cake cutting and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower bounds are tight for computing connected envy-free allocations among n=3 players and for computing perfect and equitable allocations with minimum number of cuts between n=2 players. We also formalize moving knife procedures and show that a large subclass of this family, which captures all the known moving knife procedures, can be simulated efficiently with arbitrarily small error in the Robertson-Webb query model.

Almost envy-freeness in group resource allocation

2020-07-15

Maria Kyropoulou , Warut Suksompong , Alexandros A. Voudouris

View PDF Chat

Envy-freeness up to any item with high Nash welfare: The virtue of donating items

2019-02-12

Ioannis Caragiannis , Nick Gravin , Xin Huang

Several fairness concepts have been proposed recently in attempts to approximate envy-freeness in settings with indivisible goods. Among them, the concept of envy-freeness up to any item (EFX) is arguably … Several fairness concepts have been proposed recently in attempts to approximate envy-freeness in settings with indivisible goods. Among them, the concept of envy-freeness up to any item (EFX) is arguably the closest to envy-freeness. Unfortunately, EFX allocations are not known to exist except in a few special cases. We make significant progress in this direction. We show that for every instance with additive valuations, there is an EFX allocation of a subset of items with a Nash welfare that is at least half of the maximum possible Nash welfare for the original set of items. That is, after donating some items to a charity, one can distribute the remaining items in a fair way with high efficiency. This bound is proved to be best possible. Our proof is constructive and highlights the importance of maximum Nash welfare allocation. Starting with such an allocation, our algorithm decides which items to donate and redistributes the initial bundles to the agents, eventually obtaining an allocation with the claimed efficiency guarantee. The application of our algorithm to large markets, where the valuations of an agent for every item is relatively small, yields EFX with almost optimal Nash welfare. To the best of our knowledge, this is the first use of large market assumptions in the fair division literature. We also show that our algorithm can be modified to compute, in polynomial-time, EFX allocations that approximate optimal Nash welfare within a factor of at most $2\rho$, using a $\rho$-approximate allocation on input instead of the maximum Nash welfare one.

Fairly allocating contiguous blocks of indivisible items

2019-02-22

Warut Suksompong

View PDF Chat

Fair Allocation of Indivisible Goods: Improvement and Generalization

2017-01-01

Mohammad Ghodsi , Mohammad Taghi Hajiaghayi , Masoud Seddighin +2 more

We study the problem of fair allocation for indivisible goods. We use the the maxmin share paradigm introduced by Budish as a measure for fairness. Procaccia and Wang (EC'14) were … We study the problem of fair allocation for indivisible goods. We use the the maxmin share paradigm introduced by Budish as a measure for fairness. Procaccia and Wang (EC'14) were first to investigate this fundamental problem in the additive setting. In contrast to what real-world experiments suggest, they show that a maxmin guarantee (1-MMS allocation) is not always possible even when the number of agents is limited to 3. While the existence of an approximation solution (e.g. a $1/2$-MMS allocation) is quite straightforward, improving the guarantee becomes subtler for larger constants. Procaccia provide a proof for existence of a $2/3$-MMS allocation and leave the question open for better guarantees. Our main contribution is an answer to the above question. We improve the result of [Procaccia and Wang] to a $3/4$ factor in the additive setting. The main idea for our $3/4$-MMS allocation method is clustering the agents. To this end, we introduce three notions and techniques, namely reducibility, matching allocation, and cycle-envy-freeness, and prove the approximation guarantee of our algorithm via non-trivial applications of these techniques. Our analysis involves coloring and double counting arguments that might be of independent interest. One major shortcoming of the current studies on fair allocation is the additivity assumption on the valuations. We alleviate this by extending our results to the case of submodular, fractionally subadditive, and subadditive settings. More precisely, we give constant approximation guarantees for submodular and XOS agents, and a logarithmic approximation for the case of subadditive agents. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for additive, submodular, and XOS settings in polynomial time.

Approximation Algorithms for Maximin Fair Division

2020-02-29

Siddharth Barman , Sanath Kumar Krishnamurthy

We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin … We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share , which is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into n bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focused on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations, a 2/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee. Furthermore, we initiate the study of approximate maximin fair division under submodular valuations . Specifically, we show that when the valuations of the agents are nonnegative , monotone , and submodular, then a 0.21-approximate maximin fair allocation is guaranteed to exist. In fact, we show that such an allocation can be efficiently found by using a simple round-robin algorithm. A technical contribution of the article is to analyze the performance of this combinatorial algorithm by employing the concept of multilinear extensions .

View PDF Chat

An Improved Envy-Free Cake Cutting Protocol for Four Agents

2018-01-01

Georgios Amanatidis , George Christodoulou , John Fearnley +3 more

View PDF Chat

Finding Fair and Efficient Allocations

2018-06-11

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 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.

View PDF Chat

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

2016-10-01

Haris Aziz , Simon Mackenzie

We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from n agents. The problem has received attention in computer … We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from n agents. The problem has received attention in computer science, mathematics, and economics. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. We resolve the problem by proposing a discrete and bounded envy-free protocol for any number of agents. The maximum number of queries required by the protocol is nnnnnn. Even if we do not run our protocol to completion, it can find in at most n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n+1</sup> queries an envy-free partial allocation of the cake in which each agent gets at least 1/n of the value of the whole cake.

View PDF Chat

Comparing Approximate Relaxations of Envy-Freeness

2018-07-01

Georgios Amanatidis , Georgios Birmpas , Vangelis Markakis

In fair division problems with indivisible goods it is well known that one cannot have any guarantees for the classic fairness notions of envy-freeness and proportionality. As a result, several … In fair division problems with indivisible goods it is well known that one cannot have any guarantees for the classic fairness notions of envy-freeness and proportionality. As a result, several relaxations have been introduced, most of which in quite recent works. We focus on four such notions, namely envy-freeness up to one good (EF1), envy-freeness up to any good (EFX), maximin share fairness (MMS), and pairwise maximin share fairness (PMMS). Since obtaining these relaxations also turns out to be problematic in several scenarios, approximate versions of them have also been considered. In this work, we investigate further the connections between the four notions mentioned above and their approximate versions. We establish several tight or almost tight results concerning the approximation quality that any of these notions guarantees for the others, providing an almost complete picture of this landscape. Some of our findings reveal interesting and surprising consequences regarding the power of these notions, e.g., PMMS and EFX provide the same worst-case guarantee for MMS, despite PMMS being a strictly stronger notion than EFX. We believe such implications provide further insight on the quality of approximately fair solutions.

View PDF Chat

Fair Division Under Cardinality Constraints

2018-07-01

Arpita Biswas , Siddharth Barman

We consider the problem of fairly allocating indivisible goods, among agents, under cardinality constraints and additive valuations. In this setting, we are given a partition of the entire set of … We consider the problem of fairly allocating indivisible goods, among agents, under cardinality constraints and additive valuations. In this setting, we are given a partition of the entire set of goods---i.e., the goods are categorized---and a limit is specified on the number of goods that can be allocated from each category to any agent. The objective here is to find a fair allocation in which the subset of goods assigned to any agent satisfies the given cardinality constraints. This problem naturally captures a number of resource-allocation applications, and is a generalization of the well-studied unconstrained fair division problem. The two central notions of fairness, in the context of fair division of indivisible goods, are envy freeness up to one good (EF1) and the (approximate) maximin share guarantee (MMS). We show that the existence and algorithmic guarantees established for these solution concepts in the unconstrained setting can essentially be achieved under cardinality constraints. Furthermore, focusing on the case wherein all the agents have the same additive valuation, we establish that EF1 allocations exist even under matroid constraints.

View PDF Chat

Almost Envy-Freeness with General Valuations

2020-01-01

Benjamin Plaut , Tim Roughgarden

The goal of fair division is to distribute resources among competing players in a “fair" way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do … The goal of fair division is to distribute resources among competing players in a “fair" way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do not always exist with indivisible goods, motivating the study of relaxed versions of envy-freeness. We study the envy-freeness up to any good (EFX) property, which states that no player prefers the bundle of another player following the removal of any single good, and prove the first general results about this property. We use the leximin solution to show existence of EFX allocations in several contexts, sometimes in conjunction with Pareto optimality. For two players with valuations obeying a mild assumption, one of these results provides stronger guarantees than the currently deployed algorithm on Spliddit, a popular fair division website. Unfortunately, finding the leximin solution can require exponential time. We show that this is necessary by proving an exponential lower bound on the number of value queries needed to identify an EFX allocation, even for two players with identical valuations. We consider both additive and more general valuations, and our work suggests that there is a rich landscape of problems to explore in the fair division of indivisible goods with different classes of player valuations.

View PDF Chat

On the number of almost envy-free allocations

2020-04-07

Warut Suksompong

View PDF Chat

Communication Complexity of Discrete Fair Division

2020-01-01

Benjamin Plaut , Tim Roughgarden

We initiate the study of the communication complexity of fair division with indivisible goods. We focus on some of the most well studied fairness notions (envy-freeness, proportionality, and approximations thereof) … We initiate the study of the communication complexity of fair division with indivisible goods. We focus on some of the most well studied fairness notions (envy-freeness, proportionality, and approximations thereof) and valuation classes (submodular, subadditive, and unrestricted). We show that for more than two players (and any combination of other parameters), determining whether a fair allocation exists requires exponential communication (in the number of goods). For two players, tractability depends heavily on the specific combination of parameters, and most of the paper is focused on the two-player setting. Taken together, our results completely resolve whether the communication complexity of computing a fair allocation (or determining that none exists) is polynomial or exponential, for every combination of fairness notion, valuation class, and number of players, for both deterministic and randomized protocols.

View PDF Chat

The Price of Fairness for Indivisible Goods

2019-07-28

Xiaohui Bei , Xinhang Lu , Pasin Manurangsi +1 more

We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and … We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and equitability. However, these notions cannot always be satisfied for indivisible goods, leading to certain instances being ignored in the analysis. In this paper, we focus instead on notions with guaranteed existence, including envy-freeness up to one good (EF1), balancedness, maximum Nash welfare (MNW), and leximin. We mostly provide tight or asymptotically tight bounds on the worst-case efficiency loss for allocations satisfying these notions.

View PDF Chat

Mind the gap: Cake cutting with separation

2022-09-09

Edith Elkind , Erel Segal-Halevi , Warut Suksompong

We study the problem of fairly allocating a divisible resource, also known as cake cutting, with an additional requirement that the shares that different agents receive should be sufficiently separated … We study the problem of fairly allocating a divisible resource, also known as cake cutting, with an additional requirement that the shares that different agents receive should be sufficiently separated from one another. This captures, for example, constraints arising from social distancing guidelines. While it is sometimes impossible to allocate a proportional share to every agent under the separation requirement, we show that the well-known criterion of maximin share fairness can always be attained. We then provide algorithmic analysis of maximin share fairness in this setting -- for instance, the maximin share of an agent cannot be computed exactly by any finite algorithm, but can be approximated with an arbitrarily small error. In addition, we consider the division of a pie (i.e., a circular cake) and show that an ordinal relaxation of maximin share fairness can be achieved. We also prove that an envy-free or equitable allocation that allocates the maximum amount of resource exists under separation.

View PDF Chat

The Price of Connectivity in Fair Division

2021-05-18

Xiaohui Bei , Ayumi Igarashi , Xinhang Lu +1 more

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected … We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on the well-studied fairness notion of maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.

View PDF Chat

Weighted Envy-freeness in Indivisible Item Allocation

2021-08-16

Mithun Chakraborty , Ayumi Igarashi , Warut Suksompong +1 more

We introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up … We introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up to one item (WEF1): strong , where envy can be eliminated by removing an item from the envied agent’s bundle, and weak , where envy can be eliminated either by removing an item (as in the strong version) or by replicating an item from the envied agent’s bundle in the envying agent’s bundle. We show that for additive valuations, an allocation that is both Pareto optimal and strongly WEF1 always exists and can be computed in pseudo-polynomial time; moreover, an allocation that maximizes the weighted Nash social welfare may not be strongly WEF1, but it always satisfies the weak version of the property. Moreover, we establish that a generalization of the round-robin picking sequence algorithm produces in polynomial time a strongly WEF1 allocation for an arbitrary number of agents; for two agents, we can efficiently achieve both strong WEF1 and Pareto optimality by adapting the adjusted winner procedure. Our work highlights several aspects in which weighted fair division is richer and more challenging than its unweighted counterpart.

View PDF Chat

Approximation Algorithms for Computing Maximin Share Allocations

2017-01-01

Georgios Amanatidis , Evangelos Markakis , Afshin Nikzad +1 more

View PDF Chat

Communication Complexity of Discrete Fair Division

2019-01-01

Benjamin Plaut , Tim Roughgarden

We initiate the study of the communication complexity of fair division with indivisible goods. We focus on some of the most well-studied fairness notions (envy-freeness, proportionality, and approximations thereof) and … We initiate the study of the communication complexity of fair division with indivisible goods. We focus on some of the most well-studied fairness notions (envy-freeness, proportionality, and approximations thereof) and valuation classes (submodular, subadditive and unrestricted). Within these parameters, our results completely resolve whether the communication complexity of computing a fair allocation (or determining that none exist) is polynomial or exponential (in the number of goods), for every combination of fairness notion, valuation class, and number of players, for both deterministic and randomized protocols.

View PDF Chat

The Query Complexity of Cake Cutting

2017-01-01

Simina Brânzei , Noam Nisan

View PDF Chat