The Kalai Prize 2024 for the best paper at the interface of game theory and computer science is awarded to:

The Unreasonable Fairness of Maximum Nash Welfare
by
  • Ioannis Caragiannis, Professor of Computer Science, Aarhus University
  • David Kurokawa, Software engineer, Google
  • Herve Moulin, Donald J Robertson Professor of Economics, University of Glasgow
  • Ariel Procaccia, Gordon McKay Professor of Computer Science at Harvard University.
  • Nisarg Shah, Associate Professor of Computer Science, University of Toronto,
  • Junxing Wang, National University of Defense Technology, China
published in the ACM Transactions on Economics and Computation, Vol. 7, No. 3, 2019.

Abstract

The maximum Nash welfare (MNW) solution—which selects an allocation that maximizes the product of utilities—is known to provide outstanding fairness guarantees when allocating divisible goods. And while it seems to lose its luster when applied to indivisible goods, we show that, in fact, the MNW solution is strikingly fair even in that setting. In particular, we prove that it selects allocations that are envy-free up to one good—a compelling notion that is quite elusive when coupled with economic efficiency. We also establish that the MNW solution provides a good approximation to another popular (yet possibly infeasible) fairness property, the maximin share guarantee, in theory and—even more so—in practice. While finding the MNW solution is computationally hard, we develop a nontrivial implementation and demonstrate that it scales well on real data. These results establish MNW as a compelling solution for allocating indivisible goods and underlie its deployment on a popular fair-division website.
Significance of the work
 
“Unreasonable fairness…” provides a striking result on the fairness properties of the Nash bargaining solution when applied to settings of indivisible goods. Its properties for divisible goods were well known, but “Unreasonable fairness…” established its role for indivisible goods. The paper has consequently had a clear impact on the literature on fair division, and in particular on the interdisciplinary work at the intersection of economics and computer science. Maximum Nash Welfare has emerged as the workhorse behind the majority of positive results.

The fairness notion of “envy-freeness up to one good (EF1),” which can be traced back to work by R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi (EC 2004) and E. Budish (JPE 2011), gained significant traction as a prominent notion of fairness for indivisible items following “Unreasonable fairness…“. The paper also introduced a stronger fairness notion, “envy-freeness up to any good (EFX).” The problem of whether EFX allocations of indivisible goods under additive utilities always exist has become the biggest open problem in fair division, and it has motivated a large body of work in recent years.

“Unreasonable fairness” paper has also made a significant practical impact. Based on the work described in the paper, the Maximum Nash welfare solution was deployed on the not-for-profit website Spliddit.org in 2015 and was used for allocating indivisible goods until Spliddit went offline at the end of 2022. By the end of its run, Spliddit had served more than 250,000 users.
 
Nisarg Shah will present the paper and receive the prize in a plenary session at GAMES 2024.

 
Congratulations to the authors for their well deserved Kalai Prize!