Fairly Allocating Many Goods with Few Queries

Authors

Hoon Oh, Ariel D. Procaccia, Warut Suksompong

Type: Article

Publication Date: 2019-07-17

Citations: 17

DOI: https://doi.org/10.1609/aaai.v33i01.33012141

View Ask PDF

Abstract

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.

Locations

Proceedings of the AAAI Conference on Artificial Intelligence
View PDF
arXiv (Cornell University)
View PDF
Oxford University Research Archive (ORA) (University of Oxford)
View PDF

Ask a Question About This Paper

Summary

Fair Division of Indivisible Goods with Comparison-Based Queries

2024-04-28

Xiaolin Bu , Zihao Li , Shengxin Liu +2 more

We study the problem of fairly allocating $m$ indivisible goods to $n$ agents, where agents may have different preferences over the goods. In the traditional setting, agents' valuations are provided … We study the problem of fairly allocating $m$ indivisible goods to $n$ agents, where agents may have different preferences over the goods. In the traditional setting, agents' valuations are provided as inputs to the algorithm. In this paper, we study a new comparison-based query model where the algorithm presents two bundles of goods to an agent and the agent responds by telling the algorithm which bundle she prefers. We investigate the query complexity for computing allocations with several fairness notions including proportionality up to one good (PROP1), envy-freeness up to one good (EF1), and maximin share (MMS). Our main result is an algorithm that computes an allocation satisfying both PROP1 and $\frac12$-MMS within $O(\log m)$ queries with a constant number of $n$ agents. For identical and additive valuation, we present an algorithm for computing an EF1 allocation within $O(\log m)$ queries with a constant number of $n$ agents. To complement the positive results, we show that the lower bound of the query complexity for any of the three fairness notions is $\Omega(\log m)$ even with two agents.

View PDF Chat

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

Fairly Allocating (Contiguous) Dynamic Indivisible Items with Few Adjustments

2022-01-01

Mingwei Yang

We study the problem of dynamically allocating $T$ indivisible items to $n$ agents with the restriction that the allocation is fair all the time. Due to the negative results to … We study the problem of dynamically allocating $T$ indivisible items to $n$ agents with the restriction that the allocation is fair all the time. Due to the negative results to achieve fairness when allocations are irrevocable, we allow adjustments to make fairness attainable with the objective to minimize the number of adjustments. For restricted additive or general identical valuations, we show that envy-freeness up to one item (EF1) can be achieved with no adjustments. For additive valuations, we give an EF1 algorithm that requires $O(mT)$ adjustments, improving the previous result of $O(nmT)$ adjustments, where $m$ is the maximum number of different valuations for items among all agents. We further impose the contiguity constraint on items such that items are arranged on a line by the order they arrive and require that each agent obtains a consecutive block of items. We present extensive results to achieve either proportionality with an additive approximate factor (PROPa) or EF1, where PROPa is a weaker fairness notion than EF1. In particular, we show that for identical valuations, achieving PROPa requires $\Theta(nT)$ adjustments. Moreover, we show that it is hopeless to make any significant improvement for either PROPa or EF1 when valuations are nonidentical. Our results exhibit a large discrepancy between the identical and nonidentical cases in both contiguous and noncontiguous settings. All our positive results are computationally efficient.

Fairly Allocating Goods in Parallel

2023-01-01

Rohan Garg , Alexandros Psomas

We initiate the study of parallel algorithms for fairly allocating indivisible goods among agents with additive preferences. We give fast parallel algorithms for various fundamental problems, such as finding a … We initiate the study of parallel algorithms for fairly allocating indivisible goods among agents with additive preferences. We give fast parallel algorithms for various fundamental problems, such as finding a Pareto Optimal and EF1 allocation under restricted additive valuations, finding an EF1 allocation for up to three agents, and finding an envy-free allocation with subsidies. On the flip side, we show that fast parallel algorithms are unlikely to exist (formally, $CC$-hard) for the problem of computing Round-Robin EF1 allocations.

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.

Almost envy-freeness with general valuations

2018-01-07

Benjamin Plaut , Tim Roughgarden

The goal of division is to distribute resources among competing players in a fair way. Envy-freeness is the most extensively studied fairness notion in division. Envy-free allocations do not always … The goal of division is to distribute resources among competing players in a fair way. Envy-freeness is the most extensively studied fairness notion in 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 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 division of indivisible goods with different classes of player valuations.

Almost Envy-Freeness with General Valuations

2017-07-15

Benjamin Plaut , Tim Roughgarden

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

Almost Envy-Freeness with General Valuations

2018-01-01

Benjamin Plaut , Tim Roughgarde

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

Almost Envy-Freeness with General Valuations

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

Computing envy-freeable allocations with limited subsidies

2020-02-06

Ioannis Caragiannis , Stavros D. Ioannidis

Fair division has emerged as a very hot topic in multiagent systems, and envy-freeness is among the most compelling fairness concepts. An allocation of indivisible items to agents is envy-free … Fair division has emerged as a very hot topic in multiagent systems, and envy-freeness is among the most compelling fairness concepts. An allocation of indivisible items to agents is envy-free if no agent prefers the bundle of any other agent to his own in terms of value. As envy-freeness is rarely a feasible goal, there is a recent focus on relaxations of its definition. An approach in this direction is to complement allocations with payments (or subsidies) to the agents. A feasible goal then is to achieve envy-freeness in terms of the total value an agent gets from the allocation and the subsidies. We consider the natural optimization problem of computing allocations that are {\em envy-freeable} using the minimum amount of subsidies. As the problem is NP-hard, we focus on the design of approximation algorithms. On the positive side, we present an algorithm that, for a constant number of agents, approximates the minimum amount of subsidies within any required accuracy, at the expense of a graceful increase in the running time. On the negative side, we show that, for a super-constant number of agents, the problem of minimizing subsidies for envy-freeness is not only hard to compute exactly (as a folklore argument shows) but also, more importantly, hard to approximate.

Computing envy-freeable allocations with limited subsidies

2020-01-01

Ioannis Caragiannis , Stavros Ioannidis

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

Epistemic EFX Allocations Exist for Monotone Valuations

2024-05-23

Hannaneh Akrami , Nidhi Rathi

We study the fundamental problem of fairly dividing a set of indivisible items among agents with (general) monotone valuations. The notion of envy-freeness up to any item (EFX) is considered … We study the fundamental problem of fairly dividing a set of indivisible items among agents with (general) monotone valuations. The notion of envy-freeness up to any item (EFX) is considered to be one of the most fascinating fairness concepts in this line of work. Unfortunately, despite significant efforts, existence of EFX allocations is a major open problem in fair division, thereby making the study of approximations and relaxations of EFX a natural line of research. Recently, Caragiannis et al. introduced a promising relaxation of EFX, called epistemic EFX (EEFX). We say an allocation to be EEFX if, for every agent, it is possible to shuffle the items in the remaining bundles so that she becomes "EFX-satisfied". Caragiannis et al. prove existence and polynomial-time computability of EEFX allocations for additive valuations. A natural question asks what happens when we consider valuations more general than additive? We address this important open question and answer it affirmatively by establishing the existence of EEFX allocations for an arbitrary number of agents with general monotone valuations. To the best of our knowledge, EEFX is the only known relaxation of EFX to have such strong existential guarantees. Furthermore, we complement our existential result by proving computational and information-theoretic lower bounds. We prove that even for an arbitrary number of (more than one) agents with identical submodular valuations, it is PLS-hard to compute EEFX allocations and it requires exponentially-many value queries to do so.

View PDF Chat

Computing Pareto-Optimal and Almost Envy-Free Allocations of Indivisible Goods

2024-05-10

Jugal Garg , Aniket Murhekar

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 the existence of allocations that are both EF1 and fractionally Pareto-optimal (fPO), which is a stronger notion than PO. We present a pseudopolynomial 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. For such instances, we show that an EF1+fPO allocation can be computed in strongly polynomial time. When all values are positive, we show that an EQ1+fPO allocation for such instances can be computed in strongly polynomial time. Next, we consider instances where the number of agents is constant and show that an EF1+PO (likewise, an 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. We also design a polynomial-time algorithm that computes a Nash welfare maximizing allocation when there are constantly many agents with constant many different values for the goods. Finally, on the complexity side, we show that the problem of computing an EF1+fPO allocation lies in the complexity class PLS.

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.

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

2019-01-01

Ioannis Caragiannis , Nick Gravin , Xin Huang

View PDF Chat

Fair Division Beyond Monotone Valuations

2025-01-24

Siddharth Barman , Paritosh Verma

This paper studies the problem of fairly dividing resources -- a cake or indivisible items -- amongst a set of agents with heterogeneous preferences. This problem has been extensively studied … This paper studies the problem of fairly dividing resources -- a cake or indivisible items -- amongst a set of agents with heterogeneous preferences. This problem has been extensively studied in the literature, however, a majority of the existing work has focused on settings wherein the agents' preferenes are monotone, i.e., increasing the quantity of resource doesn't decrease an agent's value for it. Despite this, the study of non-monotone preferences is as motivated as the study of monotone preferences. We focus on fair division beyond monotone valuations. We prove the existence of fair allocations, develop efficient algorithms to compute them, and prove lower bounds on the number of such fair allocations. For the case of indivisible items, we show that EF3 and EQ3 allocations always exist as long as the valuations of all agents are nonnegative. While nonnegativity suffices, we show that it's not required: EF3 allocations exist even if the valuations are (possibly negative) subadditive functions that satisfy a mild condition. In route to obtaining these results, we establish the existence of envy-free cake divisions for burnt cakes when the valuations are subadditive and the entire cake has a nonnegative value. This is in stark contrast to the well-known nonexistence of envy-free allocations for burnt cakes. In addition to the existence results, we develop an FPTAS for computing equitable cake divisions for nonnegative valuations. For indivisible items, we give an efficient algorithm to compute nearly equitable allocations which works when the valuations are nonnegative, or when they are subadditive subject to a mild condition. This result has implications beyond fair division, e.g., in facility, graph partitioning, among others. Finally, we show that such fair allocations are plenty in number, and increase exponentially (polynomially) in the number of agents (items).

View PDF Chat

Pushing the Frontier on Approximate EFX Allocations

2024-06-18

Georgios Amanatidis , Aris Filos-Ratsikas , Alkmini Sgouritsa

We study the problem of allocating a set of indivisible goods to a set of agents with additive valuation functions, aiming to achieve approximate envy-freeness up to any good ($\alpha$-EFX). … We study the problem of allocating a set of indivisible goods to a set of agents with additive valuation functions, aiming to achieve approximate envy-freeness up to any good ($\alpha$-EFX). The state-of-the-art results on the problem include that (exact) EFX allocations exist when (a) there are at most three agents, or (b) the agents' valuation functions can take at most two values, or (c) the agents' valuation functions can be represented via a graph. For $\alpha$-EFX, it is known that a $0.618$-EFX allocation exists for any number of agents with additive valuation functions. In this paper, we show that $2/3$-EFX allocations exist when (a) there are at most \emph{seven agents}, (b) the agents' valuation functions can take at most \emph{three values}, or (c) the agents' valuation functions can be represented via a \emph{multigraph}. Our results can be interpreted in two ways. First, by relaxing the notion of EFX to $2/3$-EFX, we obtain existence results for strict generalizations of the settings for which exact EFX allocations are known to exist. Secondly, by imposing restrictions on the setting, we manage to beat the barrier of $0.618$ and achieve an approximation guarantee of $2/3$. Therefore, our results push the \emph{frontier} of existence and computation of approximate EFX allocations, and provide insights into the challenges of settling the existence of exact EFX allocations.

View PDF Chat

Nearly Equitable Allocations Beyond Additivity and Monotonicity

2023-01-01

Siddharth Barman , Umang Bhaskar , Yeshwant Pandit +1 more

Equitability (EQ) in fair division requires that items be allocated such that all agents value the bundle they receive equally. With indivisible items, an equitable allocation may not exist, and … Equitability (EQ) in fair division requires that items be allocated such that all agents value the bundle they receive equally. With indivisible items, an equitable allocation may not exist, and hence we instead consider a meaningful analog, EQx, that requires equitability up to any item. EQx allocations exist for monotone, additive valuations. However, if (1) the agents' valuations are not additive or (2) the set of indivisible items includes both goods and chores (positively and negatively valued items), then prior to the current work it was not known whether EQx allocations exist or not. We study both the existence and efficient computation of EQx allocations. (1) For monotone valuations (not necessarily additive), we show that EQx allocations always exist. Also, for the large class of weakly well-layered valuations, EQx allocations can be found in polynomial time. Further, we prove that approximately EQx allocations can be computed efficiently under general monotone valuations. (2) For non-monotone valuations, we show that an EQx allocation may not exist, even for two agents with additive valuations. Under some special cases, however, we establish existence and efficient computability of EQx allocations. This includes the case of two agents with additive valuations where each item is either a good or a chore, and there are no mixed items. In addition, we show that, under nonmonotone valuations, determining the existence of EQx allocations is weakly NP-hard for two agents and strongly NP-hard for more agents.

View PDF Chat

Almost envy-freeness in group resource allocation

2020-07-15

Maria Kyropoulou , Warut Suksompong , Alexandros A. Voudouris

View PDF Chat

Almost envy-free allocations with connected bundles

2021-11-30

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

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

Equitable Division of a Path

2021-01-01

Neeldhara Misra , Chinmay Sonar , Vaidyanathan Peruvemba Ramaswamy +1 more

We study fair resource allocation under a connectedness constraint wherein a set of indivisible items are arranged on a path and only connected subsets of items may be allocated to … We study fair resource allocation under a connectedness constraint wherein a set of indivisible items are arranged on a path and only connected subsets of items may be allocated to the agents. An allocation is deemed fair if it satisfies equitability up to one good (EQ1), which requires that agents' utilities are approximately equal. We show that achieving EQ1 in conjunction with well-studied measures of economic efficiency (such as Pareto optimality, non-wastefulness, maximum egalitarian or utilitarian welfare) is computationally hard even for binary additive valuations. On the algorithmic side, we show that by relaxing the efficiency requirement, a connected EQ1 allocation can be computed in polynomial time for any given ordering of agents, even for general monotone valuations. Interestingly, the allocation computed by our algorithm has the highest egalitarian welfare among all allocations consistent with the given ordering. On the other hand, if efficiency is required, then tractability can still be achieved for binary additive valuations with interval structure. On our way, we strengthen some of the existing results in the literature for other fairness notions such as envy-freeness up to one good (EF1), and also provide novel results for negatively-valued items or chores.

Fairly allocating contiguous blocks of indivisible items

2019-02-22

Warut Suksompong

View PDF Chat

On the number of almost envy-free allocations

2020-04-07

Warut Suksompong

View PDF Chat

Developments in Multi-Agent Fair Allocation

2020-04-03

Haris Aziz

Fairness is becoming an increasingly important concern when designing markets, allocation procedures, and computer systems. I survey some recent developments in the field of multi-agent fair allocation. Fairness is becoming an increasingly important concern when designing markets, allocation procedures, and computer systems. I survey some recent developments in the field of multi-agent fair allocation.

View PDF Chat

The Convergence of Finite-Averaging of AIMD for Distributed Heterogeneous Resource Allocations

2020-01-19

Syed Eqbal Alam , Fabian Wirth , Jia Yuan Yu +1 more

In several social choice problems, agents collectively make decisions over the allocation of multiple divisible and heterogeneous resources with capacity constraints to maximize utilitarian social welfare. The agents are constrained … In several social choice problems, agents collectively make decisions over the allocation of multiple divisible and heterogeneous resources with capacity constraints to maximize utilitarian social welfare. The agents are constrained through computational or communication resources or privacy considerations. In this paper, we analyze the convergence of a recently proposed distributed solution that allocates such resources to agents with minimal communication. It is based on the randomized additive-increase and multiplicative-decrease (AIMD) algorithm. The agents are not required to exchange information with each other, but little with a central agent that keeps track of the aggregate resource allocated at a time. We formulate the time-averaged allocations over finite window size and model the system as a Markov chain with place-dependent probabilities. Furthermore, we show that the time-averaged allocations vector converges to a unique invariant measure, and also, the ergodic property holds.

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

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

The Price of Fairness for Indivisible Goods

2021-03-29

Xiaohui Bei , Xinhang Lu , Pasin Manurangsi +1 more

View PDF Chat

Almost Envy-Freeness in Group Resource Allocation

2019-07-28

Maria Kyropoulou , Warut Suksompong , Alexandros A. Voudouris

We study the problem of fairly allocating indivisible goods between groups of agents using the recently introduced relaxations of envy-freeness. We consider the existence of fair allocations under different assumptions … We study the problem of fairly allocating indivisible goods between groups of agents using the recently introduced relaxations of envy-freeness. We consider the existence of fair allocations under different assumptions on the valuations of the agents. In particular, our results cover cases of arbitrary monotonic, responsive, and additive valuations, while for the case of binary valuations we fully characterize the cardinalities of two groups of agents for which a fair allocation can be guaranteed with respect to both envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX). Moreover, we introduce a new model where the agents are not partitioned into groups in advance, but instead the partition can be chosen in conjunction with the allocation of the goods. In this model, we show that for agents with arbitrary monotonic valuations, there is always a partition of the agents into two groups of any given sizes along with an EF1 allocation of the goods. We also provide an extension of this result to any number of groups.

View PDF Chat

Consensus Halving for Sets of Items

2020-07-14

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 has shown that when the resource is … Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work has shown 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 where the resource consists of a set of items without a linear ordering. When agents have additive 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 drawn from probabilistic distributions. On the other hand, we show that for a simple class of monotonic utilities, the problem already becomes PPAD-hard. Furthermore, we compare and contrast consensus halving with the more general problem of consensus $k$-splitting, where 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.

PROPm Allocations of Indivisible Goods to Multiple Agents

2021-08-01

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.

View PDF Chat

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

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

Egalitarian Price of Fairness for Indivisible Goods

2023-11-10

Karen Frilya Celine , Muhammad Ayaz Dzulfikar , Ivan Koswara

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

Fairly Allocating Contiguous Blocks of Indivisible Items

2017-01-01

Warut Suksompong

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

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

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

Almost Envy-Freeness with General Valuations

2018-01-01

Benjamin Plaut , Tim Roughgarde

View PDF Chat