# A Compositional Game to Fairly Divide Homogeneous Cake

Source: https://arxiv.org/pdf/2301.02281.pdf
Kiwi News: https://news.kiwistand.com/stories/A-Compositional-Game-to-Fairly-Divide-Homogeneous-Cake?index=0x657cd5d3c353b5670e2f48bb3d2337dcb5f7562a00ca4eecd99eedc2382c5e29c043991e
Submitted by misha on 2023-12-15 UTC, 1 upvote, 0 comments

## Summary

The author argues that even homogeneous cake, which has no differences in player valuations, can raise interesting mechanism design questions. Abel Jansma introduces a compositional game based on iterated cake-cutting in which, for a homogeneous cake, a Nash equilibrium gives each of n players 1/n of the cake using just n-1 cuts, so each player receives a contiguous piece. Naive composition of the "I cut you choose" rule produces an exponentially unfair distribution with a Gini coefficient approaching 1, while the proposed Biggest Player rule removes this cost and achieves decentralised, asynchronous fairness at linear Robertson-Webb complexity. The game is also implemented in Haskell and the Open Game engine.

## Article

A compositional game to fairly divide homogeneous cake

Authors: Abel Jansma

The central question in the game theory of cake-cutting is how to fairly distribute a finite resource among multiple players. 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 with a Gini-coefficient that approaches 1, and suffers from a high Price of Anarchy. This cost is completely eliminated by the proposed \textit{Biggest Player} rule for composition which achieves decentralised and asynchronous fairness at linear Robertson-Webb complexity. After introducing the game, proving the fairness of the equilibrium, and analysing the incentive structure, the game is implemented in Haskell and the Open Game engine to make the compositional structure explicit.