Almost Envy-Freeness with General Valuations

By Benjamin Plaut, Tim Roughgarden. ACM-SIAM Symposium on Discrete Algorithms, 2017

296 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Economics and Econometrics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/a7883632855502d7ee4fc480eea3cf94c0b5284a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Kamesh Munagala
2. Brandon Fain

In Economics and Econometrics

1. Nisarg Shah
2. Kamesh Munagala
3. Brandon Fain

In Management Science and Operations Research

1. Nisarg Shah
2. Kamesh Munagala
3. Brandon Fain

Citations in the corpus

• Fair Allocation of Indivisible Public Goods (2018, background): “agent, and would be deemed equally good according to such fairness criteria. 1.1 Public Goods Model We consider a fairly broad model for public goods allocation that generalizes much of previous work [24, 10, 11, 3, 12, 9, 30]. There is a set of voters (or agents) N = [n]. Public goods are modeled a”