The Computational Rise and Fall of Fairness


  • John Dickerson Carnegie Mellon University
  • Jonathan Goldman Carnegie Mellon University
  • Jeremy Karp Carnegie Mellon University
  • Ariel Procaccia Carnegie Mellon University
  • Tuomas Sandholm Carnegie Mellon University



Fair division, Social choice, Envy-free allocation, Phase transition


The fair division of indivisible goods has long been an important topic in economics and, more recently, computer science. We investigate the existence of envy-free allocations of indivisible goods, that is, allocations where each player values her own allocated set of goods at least as highly as any other player's allocated set of goods. Under additive valuations, we show that even when the number of goods is larger than the number of agents by a linear fraction, envy-free allocations are unlikely to exist. We then show that when the number of goods is larger by a logarithmic factor, such allocations exist with high probability. We support these results experimentally and show that the asymptotic behavior of the theory holds even when the number of goods and agents is quite small. We demonstrate that there is a sharp phase transition from nonexistence to existence of envy-free allocations, and that on average the computational problem is hardest at that transition.




How to Cite

Dickerson, J., Goldman, J., Karp, J., Procaccia, A., & Sandholm, T. (2014). The Computational Rise and Fall of Fairness. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1).



AAAI Technical Track: Multiagent Systems