Kalai Prize

The awarded paper studies allocations that maximize the product of participants’ utilities when goods are indivisible. It shows that such allocations meet a strong fairness guarantee, provide an approximation to the maximin-share benchmark, and can be computed at useful scale with the authors’ implementation.

For a constant ε, we prove a P(N) lower bound on the (randomized) communication complexity of ε-Nash equilibrium in two-player N by N games. For n-player binary-action games we prove an exp(n) lower bound for the (randomized) communication complexity of ε-Nash equilibrium. The implications of these results on the rate of convergence of dynamics to Nash equilibria are discussed.

The price of anarchy is a measure of the inefficiency of selfish behavior that has been successfully analyzed in many applications, including network routing, resource allocation, auctions, and even models of basketball. It is defined as the worst-case ratio between the welfare of a Nash equilibrium and that of an optimal (first-best) solution. Seemingly, a bound on the price of anarchy is meaningful only if players successfully reach some Nash equilibrium. The main result of this paper is that for many of the classes of games in which the price of anarchy has been studied, results are “intrinsically robust”: a bound on the worst-case price of anarchy for pure Nash equilibria necessarily implies the exact same worst-case bound for much larger sets of outcomes, including mixed Nash equilibria, correlated equilibria, and sequences of outcomes generated by natural experimentation strategies (such as successive best responses or simultaneous regret-minimization). We also discuss subsequent developments, such as generalizations to incomplete-information games with applications to mechanism design.

The prize lecture discusses the two awarded analyses of sponsored-search auctions, the history behind them, and later developments in the theory and practice of these auctions.

The awarded paper shows that finding a Nash equilibrium in a game with four or more players is complete for the complexity class PPAD. Thus the existence of an equilibrium, guaranteed by Nash’s theorem, does not itself give an efficient way to compute one.