Fair Enough Kurokawa, David; Procaccia, Ariel D.; Wang, Junxing
Journal of the ACM,
03/2018, Volume:
65, Issue:
2
Journal Article
Peer reviewed
We consider the problem of fairly allocating indivisible goods, focusing on a recently introduced notion of fairness called
maximin share guarantee
: each player’s value for his allocation should be ...at least as high as what he can guarantee by dividing the items into as many bundles as there are players and receiving his least desirable bundle. Assuming additive valuation functions, we show that such allocations may not exist, but allocations guaranteeing each player 2/3 of the above value always exist. These theoretical results have direct practical implications.
We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work ...has focused on unanimous fairness, in which all agents in each group must agree that their group's share is fair. Under this strict requirement, fair allocations exist only for small groups. We introduce the concept of democratic fairness, which aims to satisfy a certain fraction of the agents in each group. This concept is better suited to large groups such as cities or countries. We present protocols for democratic fair allocation among two or more arbitrarily large groups of agents with monotonic, additive, or binary valuations. For two groups with arbitrary monotonic valuations, we give an efficient protocol that guarantees envy-freeness up to one good for at least 1/2 of the agents in each group, and prove that the 1/2 fraction is optimal. We also present other protocols that make weaker fairness guarantees to more agents in each group, or to more groups. Our protocols combine techniques from different fields, including combinatorial game theory, cake cutting, and voting.
The maximin share guarantee is, in the context of allocating indivisible goods to a set of agents, a recent fairness criterion. A solution achieving a constant approximation of this guarantee always ...exists and can be computed in polynomial time. We extend the problem to the case where the goods collectively received by the agents satisfy a matroidal constraint. Polynomial approximation algorithms for this generalization are provided: a 1/2-approximation for any number of agents, a (1- ε)-approximation for two agents, and a (8/9 - ε) -approximation for three agents. Apart from the extension to matroids, the (8/9 - ε) -approximation for three agents improves on a (7-8 - ε) -approximation by Amanatidis et al. (ICALP 2015). Some special cases are also presented and some extensions of the model are discussed.
Fair division is a fundamental problem in various multi-agent settings, where the goal is to divide a set of resources among agents in a fair manner. We study the case where m indivisible items need ...to be divided among n agents with additive valuations using the popular fairness notion of maximin share (MMS). An MMS allocation provides each agent a bundle worth at least her maximin share. While it is known that such an allocation need not exist 1,2, a series of remarkable work 1,3–6 provided approximation algorithms for a 23-MMS allocation in which each agent receives a bundle worth at least 23 times her maximin share. More recently, Ghodsi et al. 7 showed the existence of a 34-MMS allocation and a PTAS to find a (34−ϵ)-MMS allocation for an ϵ>0. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain.
In this paper, we develop a new approach that gives a simple algorithm for showing the existence of a 34-MMS allocation. Furthermore, our approach is powerful enough to be easily extended in two directions: First, we get a strongly polynomial time algorithm to find a 34-MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that there always exists a (34+112n)-MMS allocation, improving the best previous factor. This improves the approximation guarantee, most notably for small n. We note that 34 was the best factor known for n>4.
We study the problem of fair division when the set of resources contains both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good ...(EF1) cannot be directly applied to this mixed goods setting. In this work, we propose a new fairness notion, envy-freeness for mixed goods (EFM), which is a direct generalization of both EF and EF1 to the mixed goods setting. We prove that an EFM allocation always exists for any number of agents with additive valuations. We also propose efficient algorithms to compute an EFM allocation for two agents with general additive valuations and for n agents with piecewise linear valuations over the divisible goods. Finally, we relax the envy-freeness requirement, instead asking for ϵ-envy-freeness for mixed goods (ϵ-EFM), and present an efficient algorithm that finds an ϵ-EFM allocation.
We consider the ε-Consensus-Halving problem, in which a set of heterogeneous agents aim at dividing a continuous resource into two (not necessarily contiguous) portions that all of them ...simultaneously consider to be of approximately the same value (up to ε). This problem was recently shown to be PPA-complete, for n agents and n cuts, even for very simple valuation functions. In a quest to understand the root of the complexity of the problem, we consider the setting where there is only a constant number of agents, and we consider both the computational complexity and the query complexity of the problem.
For agents with monotone valuation functions, we show a dichotomy: for two agents the problem is polynomial-time solvable, whereas for three or more agents it becomes PPA-complete. Similarly, we show that for two monotone agents the problem can be solved with polynomially-many queries, whereas for three or more agents, we provide exponential query complexity lower bounds. These results are enabled via an interesting connection to a monotone Borsuk-Ulam problem, which may be of independent interest. For agents with general valuations, we show that the problem is PPA-complete and admits exponential query complexity lower bounds, even for two agents.
Several relaxations of envy-freeness, tailored to fair division in settings with indivisible goods, have been introduced within the last decade. Due to the lack of general existence results for most ...of these concepts, great attention has been paid to establishing approximation guarantees. In this work, we propose a simple algorithm that is universally fair in the sense that it returns allocations that have good approximation guarantees with respect to four such fairness notions at once. In particular, this is the first algorithm achieving a (ϕ−1)-approximation of envy-freeness up to any good (▪) and a 2ϕ+2-approximation of groupwise maximin share fairness (▪), where ϕ is the golden ratio (ϕ≈1.618). The best known approximation factor, in polynomial time, for either one of these fairness notions prior to this work was 1/2. Moreover, the returned allocation achieves envy-freeness up to one good (▪) and a 2/3-approximation of pairwise maximin share fairness (▪). While ▪ is our primary focus, we also exhibit how to fine-tune our algorithm and further improve the guarantees for ▪ or ▪.
Finally, we show that ▪—and thus ▪ and ▪—allocations always exist when the number of goods does not exceed the number of agents by more than two.
Fair division of indivisible resources is a fundamental problem in many disciplines, including computer science, economy, operations research, etc. The existence of PMMS allocations of goods is a ...major open problem in fair division, even for additive valuations. At the state of the art, there is no identified setting where PMMS allocations are deemed impossible, and the known existing results regarding their existence are limited to highly constrained settings. In this paper, we provide an algorithm for computing a PMMS allocation for identical variant. We also use the algorithm to find the PMMS allocations for 3 agents in line graphs. Moreover, we show that a 45-PMMS allocation can be computed in polynomial time when agents agree on the ordinal ranking of the goods. A quantitative gauge for assessing the impact on social welfare is known as the price of fairness, which quantifies the maximum possible reduction in social welfare due to the imposition of fairness constraints. Originally explored in the context of divisible goods, the concept of the price of fairness continues to be a pivotal metric for evaluating the effect of fairness considerations on overall social welfare. Consequently, we study the efficiency decrease under PMMS allocations and prove a tight upper bound on the price of PMMS allocations.
•We present an algorithm to compute a PMMS allocation if agents' valuation functions are identical.•We analyze an existing algorithm terminates with a 45-PMMS allocation in polynomial time when agents have identical ordinal ranking values of the goods.•We also examine the efficiency loss associated with PMMS allocations and establish their precise price bound.
We study the fair division problem on divisible heterogeneous resources (the cake cutting problem) with strategic agents, where each agent can manipulate his/her private valuation to receive a better ...allocation. A (direct-revelation) mechanism takes agents' reported valuations as input and outputs an allocation that satisfies a given fairness requirement. A natural and fundamental open problem, first raised by Chen, Lai, Parkes, and Procaccia 1 and subsequently raised in reference 2–7, etc., is whether there exists a deterministic, truthful, and envy-free (or even proportional) cake cutting mechanism. In this paper, we resolve this open problem by proving that there does not exist a deterministic, truthful and proportional cake cutting mechanism, even in the special case where all of the following hold:•there are only two agents;•each agent's valuation is a piecewise-constant function;•each agent is hungry: each agent has a strictly positive value on any part of the cake. The impossibility result extends to the case where the mechanism is allowed to leave some part of the cake unallocated.
We also present a truthful and envy-free mechanism when each agent's valuation is piecewise-constant and monotone. However, if we require Pareto-optimality, we show that truthful is incompatible with approximate proportionality for any positive approximation ratio even for piecewise-constant and monotone value density functions.
To circumvent the main impossibility result, we aim to design mechanisms that possess a certain degree of truthfulness. Motivated by the kind of truthfulness possessed by the classical I-cut-you-choose protocol, we propose a weaker notion of truthfulness, the proportional risk-averse truthfulness. We show that the well-known moving-knife (Dubins-Spanier) procedure and Even-Paz algorithm do not have this truthful property. We propose a mechanism that is proportionally risk-averse truthful and envy-free, and a mechanism that is proportionally risk-averse truthful that always outputs allocations with connected pieces.
Reallocating resources to get mutually beneficial outcomes is a fundamental problem in various multi-agent settings. While finding an arbitrary Pareto optimal allocation is generally easy, checking ...whether a particular allocation is Pareto optimal can be much more difficult. This problem is equivalent to checking that the allocated objects cannot be reallocated in such a way that at least one agent prefers her new allocation to her old one, and no agent prefers her old allocation to her new one. We consider the problem for two related types of preference relations over sets of objects. In the first part of the paper we focus on the setting in which agents express additive cardinal utilities over objects. We present computational hardness results as well as polynomial-time algorithms for testing Pareto optimality under different restrictions such as two utility values or lexicographic utilities. In the second part of the paper we assume that agents express only their (ordinal) preferences over individual objects, and that their underlying preferences are additively separable. In this setting, we present characterizations and polynomial-time algorithms for possible and necessary Pareto optimality.
PDF
