An Algorithmic Framework for Strategic Fair Division

Abstract

We study the paradigmatic fair division problem of fairly allocating a divisible good among agents with heterogeneous preferences, commonly known as cake cutting. Classic cake cutting protocols are susceptible to manipulation. Do their strategic outcomes still guarantee fairness? To address this question we adopt a novel algorithmic approach, proposing a concrete computational model and reasoning about the game-theoretic properties of algorithms that operate in this model. Specifically, we show that each protocol in the class of generalized cut and choose (GCC) protocols --- which includes the most important discrete cake cutting protocols --- is guaranteed to have approximate subgame perfect Nash equilibria, or even exact equilibria if the protocol's tie-breaking rule is flexible. We further observe that the (approximate) equilibria of proportional protocols --- which guarantee each of the n agents a 1/n-fraction of the cake --- must be (approximately) proportional, thereby answering the above question in the positive (at least for one common notion of fairness).