When Do Envy-Free Allocations Exist?

Authors

  • Pasin Manurangsi University of California, Berkeley
  • Warut Suksompong Stanford University

DOI:

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

Abstract

We consider a fair division setting in which m indivisible items are to be allocated among n agents, where the agents have additive utilities and the agents’ utilities for individual items are independently sampled from a distribution. Previous work has shown that an envy-free allocation is likely to exist when m = Ω (n log n) but not when m = n + o (n), and left open the question of determining where the phase transition from non-existence to existence occurs. We show that, surprisingly, there is in fact no universal point of transition— instead, the transition is governed by the divisibility relation between m and n. On the one hand, if m is divisible by n, an envy-free allocation exists with high probability as long as m ≥ 2n. On the other hand, if m is not “almost” divisible by , an envy-free allocation is unlikely to exist even when m = Θ(n log n)/log log n).

Downloads

Published

2019-07-17

How to Cite

Manurangsi, P., & Suksompong, W. (2019). When Do Envy-Free Allocations Exist?. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2109-2116. https://doi.org/10.1609/aaai.v33i01.33012109

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms