A compositional game to fairly divide homogeneous cake
share
The central question in the game theory of cake-cutting is how to distribute a finite resource among players in a fair way. Most research has focused on how to do this for a heterogeneous cake in a situation where the players do not have access to each other's valuation function, but I argue that even sharing homogeneous cake can have interesting mechanism design. Here, I introduce a new game, based on the compositional structure of iterated cake-cutting, that in the case of a homogeneous cake has a Nash equilibrium where each of n players gets 1/n of the cake. Furthermore, the equilibrium distribution is the result of just n-1 cuts, so each player gets a contiguous piece of cake. Naive composition of the `I cut you choose' rule leads to an exponentially unfair cake distribution so suffers from a high price of anarchy. This cost is completely eliminated by the BigPlayer rule. After introducing the game and proving the fairness of the equilibrium, the game is implemented in Haskell and the Open Game engine to make the compositional structure explicit.
READ FULL TEXT