We investigate five different fairness criteria in a simple model of fair resource allocation of indivisible goods based on additive preferences. We show how these criteria are connected to each ...other, forming an ordered scale that can be used to characterize how conflicting the agents’ preferences are: for a given instance of a resource allocation problem, the less conflicting the agents’ preferences are, the more demanding criterion this instance is able to satisfy, and the more satisfactory the allocation can be. We analyze the computational properties of the five criteria, give some experimental results about them, and further investigate a slightly richer model with
k
-additive preferences.
In fair division problems, we are given a set S of m items and a set N of n agents with individual preferences, and the goal is to find an allocation of items among agents so that each agent finds ...the allocation fair. There are several established fairness concepts and envy-freeness is one of the most extensively studied ones. However envy-free allocations do not always exist when items are indivisible and this has motivated relaxations of envy-freeness: envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are two well-studied relaxations. We consider the problem of finding EF1 and EFX allocations for utility functions that are not necessarily monotone, and propose four possible extensions of different strength to this setting.
In particular, we present a polynomial time algorithm for finding an EF1 allocation for two agents with arbitrary utility functions. An example is given showing that EFX allocations need not exist for two agents with non-monotone, non-additive, identical utility functions. However, when all agents have monotone (not necessarily additive) identical utility functions, we give a pseudo-polynomial time algorithm that always finds an EFX allocation of chores. As a step toward understanding the general case, we discuss two subclasses of utility functions: Boolean utilities that are {0,+1}-valued functions, and negative Boolean utilities that are {0,−1}-valued functions. For the latter, we give a polynomial time algorithm that finds an EFX allocation when the utility functions are identical.
Fair division with multiple pieces Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira
Discrete Applied Mathematics,
09/2020, Volume:
283
Journal Article
Peer reviewed
Open access
Given a set of p players, we consider problems concerning envy-free allocation of collections of k pieces from given sets of goods or chores. We show that if p=n and each player prefers k pieces in ...any division of a cake into n pieces, then there exists a division of the cake where at least pk2−k+1 players get their desired k pieces each. We further show that if p=k(n−1)+1 and each player prefers k pieces, one piece from each of k cakes, in any division of the k cakes into n pieces each, then there exists a division of the cakes where at least pk2−k players get their desired k pieces each. Finally we prove that if p≥k(n−1)+1 and each player prefers one shift in each of k days that are partitioned into n shifts each, then, given that players prefer empty shifts if possible (e.g., if salaries are fixed and do not depend on the number of working hours), there exist n(1+lnk) players covering all the shifts, and moreover, if k=2 then n players suffice. Our proofs combine topological methods and theorems of Füredi, Lovász and Gallai from hypergraph theory.
•Ω(n2) lower bound for query complexity of local proportionality in the Robertson-Webb cake-cutting model.•Separation of query complexities of proportionality and local proportionality.•Family of ...graphs over which guaranteeing local proportionality is difficult.
We prove an Ω(n2) lower bound on the query complexity of local proportionality in the Robertson-Webb cake-cutting model. Local proportionality requires that each agent prefer their allocation to the average of their neighbors' allocations in some undirected social network. It is a weaker fairness notion than envy-freeness, which also has query complexity Ω(n2), and generally incomparable to proportionality, which has query complexity Θ(nlogn). This result separates the complexity of local proportionality from that of ordinary proportionality, confirming the intuition that finding a locally proportional allocation is a more difficult computational problem.
A matching in a bipartite graph with parts X and Y is called envy-free, if no unmatched vertex in X is a adjacent to a matched vertex in Y. Every perfect matching is envy-free, but envy-free ...matchings exist even when perfect matchings do not. We prove that every bipartite graph has a unique partition such that all envy-free matchings are contained in one of the partition sets. Using this structural theorem, we provide a polynomial-time algorithm for finding an envy-free matching of maximum cardinality. For edge-weighted bipartite graphs, we provide a polynomial-time algorithm for finding a maximum-cardinality envy-free matching of minimum total weight. We show how envy-free matchings can be used in various fair division problems with either continuous resources (“cakes”) or discrete ones. In particular, we propose a symmetric algorithm for proportional cake-cutting, an algorithm for 1-out-of-(2n-2) maximin-share allocation of discrete goods, and an algorithm for 1-out-of-⌊2n/3⌋ maximin-share allocation of discrete bads among n agents.
Abstract In the literature, many desirable properties for allocations of indivisible goods have been proposed, including envy-freeness, Pareto optimality, and maximization of either the total welfare ...of all agents, the welfare of the worst-off agent, or the Nash product of agents’ welfares. In the two-person context, we study relationships among these properties using both analytical models and simulation in a setting where individual preferences are given by additive cardinal utilities. We provide several new theorems linking these criteria and use simulation to study how their values are related to problem characteristics, assuming that utilities are assigned randomly. We draw some conclusions concerning the relation of problem characteristics to the availabilty of allocations with particular properties.
•We aim to allocate items in a fair and efficient way.•“Fair” means proportional or envy-free up to one item.•“Efficient” means maximizing the sum of agents’ utilities.•We determine the cases that ...can be solved in polynomial time and the cases that are NP-hard
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).
Distributed fair allocation of indivisible goods Chevaleyre, Yann; Endriss, Ulle; Maudet, Nicolas
Artificial intelligence,
January 2017, 2017-01-00, 20170101, 2017-01, Volume:
242
Journal Article
Peer reviewed
Open access
Distributed mechanisms for allocating indivisible goods are mechanisms lacking central control, in which agents can locally agree on deals to exchange some of the goods in their possession. We study ...convergence properties for such distributed mechanisms when used as fair division procedures. Specifically, we identify sets of assumptions under which any sequence of deals meeting certain conditions will converge to a proportionally fair allocation and to an envy-free allocation, respectively. We also introduce an extension of the basic framework where agents are vertices of a graph representing a social network that constrains which agents can interact with which other agents, and we prove a similar convergence result for envy-freeness in this context. Finally, when not all assumptions guaranteeing envy-freeness are satisfied, we may want to minimise the degree of envy exhibited by an outcome. To this end, we introduce a generic framework for measuring the degree of envy in a society and establish the computational complexity of checking whether a given scenario allows for a deal that is beneficial to every agent involved and that will reduce overall envy.
PDF
