“Mirror, mirror, on the wall, who is the fairest of them all?”
The Evil Queen
What is a
fair
way to assign rooms to several housemates and divide the rent between them? This is not just a theoretical ...question: many people have used the
Spliddit
website to obtain
envy-free
solutions to rent division instances. But envy freeness, in and of itself, is insufficient to guarantee outcomes that people view as intuitive and acceptable. We therefore focus on solutions that optimize a criterion of social justice, subject to the envy-freeness constraint, in order to pinpoint the “fairest” solutions. We develop a general algorithmic framework that enables the computation of such solutions in polynomial time. We then study the relations between natural optimization objectives and identify the
maximin
solution, which maximizes the minimum utility subject to envy freeness, as the most attractive. We demonstrate, in theory and using experiments on real data from Spliddit, that the maximin solution gives rise to significant gains in terms of our optimization objectives. Finally, a user study with Spliddit users as subjects demonstrates that people find the maximin solution to be significantly fairer than arbitrary envy-free solutions; this user study is unprecedented in that it asks people about their real-world rent division instances. Based on these results, the maximin solution has been deployed on Spliddit since April 2015.
We consider the discrete assignment problem in which agents express ordinal preferences over objects and these objects are allocated to the agents in a fair manner. We use the stochastic dominance ...relation between fractional or randomized allocations to systematically define varying notions of proportionality and envy-freeness for discrete assignments. The computational complexity of checking whether a fair assignment exists is studied for these fairness notions. We also characterize the conditions under which a fair assignment is guaranteed to exist. For a number of fairness concepts, polynomial-time algorithms are presented to check whether a fair assignment exists. Our algorithmic results also extend to the case of unequal entitlements of agents. Our NP-hardness result, which holds for several variants of envy-freeness, answers an open question posed by Bouveret, Endriss, and Lang (ECAI 2010). We also propose fairness concepts that always suggest a non-empty set of assignments with meaningful fairness properties. Among these concepts, optimal proportionality and optimal weak proportionality appear to be desirable fairness concepts.
We study the allocation of indivisible goods among groups of agents using well-known fairness notions such as envy-freeness and proportionality. While these notions cannot always be satisfied, we ...provide several bounds on the optimal relaxations that can be guaranteed. For instance, our bounds imply that when the number of groups is constant and the n agents are divided into groups arbitrarily, there exists an allocation that is envy-free up to Θ(n) goods, and this bound is tight. Moreover, we show that while such an allocation can be found efficiently, it is NP-hard to compute an allocation that is envy-free up to o(n) goods even when a fully envy-free allocation exists. Our proofs make extensive use of tools from discrepancy theory.
In two-sided assignment markets with transferable utility, we first introduce two weak monotonicity properties that are compatible with stability. We show that for a fixed population, the ...sellers-optimal (respectively the buyers-optimal) stable rules are the only stable rules that satisfy object-valuation antimonotonicity (respectively buyer-valuation monotonicity). Essential in these properties is that, after a change in valuations, monotonicity is required only for buyers that stay matched with the same seller. Using Owen's derived consistency, the two optimal rules are characterized among all allocation rules for two-sided assignment markets with a variable population, without explicitly requiring stability.
Whereas these two monotonicity properties suggest an asymmetric treatment of the two sides of the market, valuation fairness axioms require a more balanced effect on the payoffs of buyers and sellers when the valuation of buyers for the objects owned by the sellers change. For assignment markets with a variable population, we introduce grand valuation fairness requiring that, if all valuations decrease by the same amount, as long as all optimal matchings still remain optimal, this leads to equal changes in the payoff of all agents. We show that the fair division rules are the only rules that satisfy this grand valuation fairness and a weak derived consistency property.
Fair allocation of indivisible goods and chores Aziz, Haris; Caragiannis, Ioannis; Igarashi, Ayumi ...
Autonomous agents and multi-agent systems,
04/2022, Volume:
36, Issue:
1
Journal Article
Peer reviewed
Open access
We consider the problem of fairly dividing a set of indivisible items. Much of the fair division literature assumes that the items are “goods” that yield positive utility for the agents. There is ...also some work in which the items are “chores” that yield negative utility for the agents. In this paper, we consider a more general scenario in which an agent may have positive or negative utility for each item. This framework captures, e.g., fair task assignment, where agents can experience both positive and negative utility for each task. We demonstrate that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We present several new and efficient algorithms for finding fair allocations in this general setting. We also point out several gaps in the literature regarding the existence of allocations that satisfy certain fairness and efficiency properties and examine the complexity of computing such allocations.
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 also introduce the concept of
strong price of fairness
, which captures the efficiency loss in the worst fair allocation as opposed to that in the best fair allocation as in the price of fairness. We mostly provide tight or asymptotically tight bounds on the worst-case efficiency loss for allocations satisfying these notions, for both the price of fairness and the strong price of fairness.
Redividing the cake Segal-Halevi, Erel
Autonomous agents and multi-agent systems,
04/2022, Volume:
36, Issue:
1
Journal Article
Peer reviewed
Open access
The paper considers fair allocation of resources that are already allocated in an unfair way. This setting requires a careful balance between the fairness considerations and the rights of the present ...owners. The paper presents re-division algorithms that attain various trade-off points between fairness and ownership rights, in various settings differing in the geometric constraints on the allotments: (a) no geometric constraints; (b) connectivity—the cake is a one-dimensional interval and each piece must be a contiguous interval; (c) rectangularity—the cake is a two-dimensional rectangle or rectilinear polygon and the pieces should be rectangles; (d) convexity—the cake is a two-dimensional convex polygon and the pieces should be convex. These re-division algorithms have implications on another problem: the price-of-fairness—the loss of social welfare caused by fairness requirements. Each algorithm implies an upper bound on the price-of-fairness with the respective geometric constraints.
PDF
