Proceedings of the AAAI Conference on Artificial Intelligence · 2020 · 20 citations · 18 references
Social SciencesEconomicsBehavioral EconomicsDecision TheoryGame TheoryAlgorithmic FairnessInformation AsymmetrySocial PreferencesUtility TheoryAllocation Of Indivisible GoodsBargaining Over Indivisible GoodsFair DivisionFairnessFairness In Valuation
Envy-freeness up to one good (EF1) is a well-studied fairness notion for indivisible goods that addresses pairwise envy by the removal of at most one good. In the worst case, each pair of agents might require the (hypothetical) removal of a different good, resulting in a weak aggregate guarantee. We study allocations that are nearly envy-free in aggregate, and define a novel fairness notion based on information withholding. Under this notion, an agent can withhold (or hide) some of the goods in its bundle and reveal the remaining goods to the other agents. We observe that in practice, envy-freeness can be achieved by withholding only a small number of goods overall. We show that finding allocations that withhold an optimal number of goods is computationally hard even for highly restricted classes of valuations. In contrast to the worst-case results, our experiments on synthetic and real-world preference data show that existing algorithms for finding EF1 allocations withhold a close-to-optimal amount of information.
18
Resource allocation and the public sector
Delia Foley · Medical Entomology and Zoology · 1967 · 1.1K citations
On approximately fair allocations of indivisible goods
R.J. Lipton, Evangelos Markakis, Elchanan Mossel et al. · 2004 · 530 citations
Analytical approach to parallel repetition
Irit Dinur, David Steurer · 2014 · 422 citations