An Algorithmic Framework for Strategic Fair Division

A large body of literature deals with the so-called cake cutting So how would strategic agents behave when faced with problem -- a misleadingly childish metaphor for the the cut and choose protocol? A standard way of answering challenging and important task of fairly dividing a heterogeneous this question employs the notion of Nash equilibrium: each divisible good among multiple agents (see the recent agent would use a strategy that is a best response to the other survey by Procaccia (2013) and the books by Brams agent's strategy. To set up a Nash equilibrium, suppose that and Taylor (1996) and Robertson and Webb (1998)). In particular, the first agent cuts two pieces that the second agent values there is a significant amount of AI work on cake cutting equally; the second agent selects its more preferred piece, (Procaccia 2009; Caragiannis, Lai, and Procaccia 2011; and the one less preferred by the first agent in case of a tie. Brams et al. 2012; Bei et al. 2012; Aumann, Dombb, Clearly, the second agent cannot gain from deviating, as it is and Hassidim 2013; Kurokawa, Lai, and Procaccia 2013; selecting a piece that is at least as preferred as the other. As Brânzei, Procaccia, and Zhang 2013; Brânzei and Miltersen for the first agent, if it makes its preferred piece even bigger, 2013; Chen et al. 2013; Balkanski et al. 2014; Brânzei the second agent would choose that piece, making the and Miltersen 2015; Segal-Halevi, Hassidim, and Aumann first agent worse off. Interestingly enough, in this equilibrium 2015), which is closely intertwined with emerging realworld the tables are turned; now it is the second agent who applications of fair division more broadly (Goldman is getting exactly half of its value for the whole cake, while and Procaccia 2014; Kurokawa, Procaccia, and Shah 2015).