Fairly Allocating Many Goods with Few Queries

Authors

  • Hoon Oh Carnegie Mellon University
  • Ariel D. Procaccia Carnegie Mellon University
  • Warut Suksompong Stanford University

DOI:

https://doi.org/10.1609/aaai.v33i01.33012141

Abstract

We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic valuations, we design an algorithm that computes an allocation satisfying envy-freeness up to one good (EF1), a relaxation of envy-freeness, using a logarithmic number of queries. We show that the logarithmic query complexity bound also holds for three agents with additive valuations. These results suggest that it is possible to fairly allocate goods in practice even when the number of goods is extremely large. By contrast, we prove that computing an allocation satisfying envyfreeness and another of its relaxations, envy-freeness up to any good (EFX), requires a linear number of queries even when there are only two agents with identical additive valuations.

Downloads

Published

2019-07-17

How to Cite

Oh, H., Procaccia, A. D., & Suksompong, W. (2019). Fairly Allocating Many Goods with Few Queries. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2141-2148. https://doi.org/10.1609/aaai.v33i01.33012141

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms