Sharing pie in an Open Game
(This is an update on my Ethereum Protocol Fellowship. More updates can be found here ).
In order to get more familiar with the Open Game Engine, I wanted to implement a game myself. One of my favourite games is sharing birthday cake, which—in the unfortunate case that only one person shows up to your party—has beautiful mechanism design. Namely: One person gets to cut the cake, and the other gets to choose a piece first, leading to an equilibrium where both players get half the cake. I want to generalise this to a birthday with more visitors, using the following rules:
 Player 1 cuts the cake in two.
 Player 2 gets to choose one of the two pieces.
 Let BigPlayer be the player who ended up with the largest of the two pieces. BigPlayer then has to cut their piece in two.
 A next player—one that does not have any cake yet—gets to choose one of BigPlayer’s pieces.
 Move to 3 if there are any players left without cake.
This changes the equilibrium. Player 1 no longer wants to cut the cake in half, since they would then end up with at most a quarter of the cake. What does the new equilibrium look like? Let’s use the Open Game engine to find out.
Since the game outlined above is essentially just a composition of the same 2player game multiple times, let’s define the 2player game first, and make sure it works properly.
I start by defining the object that the players care about: pies, sharing proposals, and decisions on which piece to take. Since a player who chooses a piece always makes a binary decision, implementing this as a binary data type suffices:
type Pie = Double
type Proposal = Double
data ResponderAction = Accept  Reject
deriving (Eq,Ord,Show)
The payoff for both players depends on the size of the full cake, the proposed pieces, and the decision by the responding player:
pieSharingGamePayoff_proposer,pieSharingGamePayoff_responder :: Pie > Proposal > ResponderAction > Payoff
pieSharingGamePayoff_proposer pie proposal reaction =
if reaction == Accept then (pie  proposal) else proposal
pieSharingGamePayoff_responder pie proposal reaction =
if reaction == Accept then proposal else (pie  proposal)
The structure of the game is then very similar to the previously covered sequential decision games.
pieSharingGame pie = [opengame
inputs : ;
feedback : ;
::
inputs : ;
feedback : ;
operation : dependentDecision "proposer" (const [0..pie]);
outputs : proposal ;
returns : pieSharingGamePayoff_proposer pie proposal reaction;
inputs : proposal ;
feedback : ;
operation : dependentDecision "responder" (const [Accept,Reject]);
outputs : reaction ;
returns : pieSharingGamePayoff_responder pie proposal reaction ;
::
outputs : ;
returns : ;
]
Note that this is still a trivial open game—i.e. a closed game—since it has no exposed wires. This obviously has to change if we want to compose these, but for now let’s just verify that this leads to the expected behaviour. To verify this, we need a pie and a collection of strategies.
fullPieSize :: Double
fullPieSize = 10
As for the strategies, consider the following few examples:

A very selfish proposer that always only offers a slice of size 2 (out of a pie of size 10)
 proposer plays selfish proposerStrategyPCG_Selfish :: Kleisli Stochastic () Proposal proposerStrategyPCG_Selfish = pureAction 2

Alternatively, consider a fair proposer that always offers exactly half of the pie:
 proposer plays fair proposerStrategyPCG_Fair :: Kleisli Stochastic () Proposal proposerStrategyPCG_Fair = pureAction (fullPieSize/2)

As for the responder, let’s create one that is too nice, and always accepts whatever they are offered:
 responder always accepts responderStrategyPCG_Accept :: Kleisli Stochastic Proposal ResponderAction responderStrategyPCG_Accept = pureAction Accept

Or a hungrier one that picks whichever piece is biggest:
 responder accepts iff piece is at least half of the pie) responderStrategyPCG_BiggestPiece :: Kleisli Stochastic Proposal ResponderAction responderStrategyPCG_BiggestPiece = Kleisli $ chooseBiggestPiece fullPieSize where chooseBiggestPiece :: Pie > Proposal > Stochastic ResponderAction chooseBiggestPiece fullPie proposal = if (proposal >= (fullPie/2)) then playDeterministically Accept else playDeterministically Reject
A full strategy is a tuple of proposer and responder strategies, so let’s create all 4 combinations of these strategies:
stratTuplePCG_selfishProposer_acceptingResponder = proposerStrategyPCG_Selfish :: responderStrategyPCG_Accept :: Nil
stratTuplePCG_fairProposer_acceptingResponder = proposerStrategyPCG_Fair :: responderStrategyPCG_Accept :: Nil
stratTuplePCG_selfishProposer_selfishResponder = proposerStrategyPCG_Selfish :: responderStrategyPCG_BiggestPiece :: Nil
stratTuplePCG_fairProposer_selfishResponder = proposerStrategyPCG_Fair :: responderStrategyPCG_BiggestPiece :: Nil
Instantiate an equilibrium checker:
isEquilibriumPieSharingGame pie strat = generateIsEq $ evaluate (pieSharingGame pie) strat void
And check each of the full strategy profiles:
1. Selfish proposer vs. Accepting responder
λ: isEquilibriumPieSharingGame 10 stratTuplePCG_selfishProposer_acceptingResponder
Analytics begin
Strategies are NOT in equilibrium. Consider the following profitable deviations:
Player: proposer
Optimal Move: 0.0
Current Strategy: fromFreqs [(2.0,1.0)]
Optimal Payoff: 10.0
Current Payoff: 8.0
Observable State: ()
Unobservable State: "((),())"
other game
No more information
NEWGAME:
Strategies are NOT in equilibrium. Consider the following profitable deviations:
Player: responder
Optimal Move: Reject
Current Strategy: fromFreqs [(Accept,1.0)]
Optimal Payoff: 8.0
Current Payoff: 2.0
Observable State: 2.0
Unobservable State: "((),2.0)"
other game
No more information
NEWGAME:
Analytics end
That is, the engine tells our selfish proposer (that offers 2/10ths of the pie) that they are, in fact, not selfish enough. A responder that always accepts can be easily exploited by offering nothing at all (a piece of size 0.0). Furthemore, the engine also warns the responder that they should reject the measly offer they are currently getting, which would give them 8/10ths of the pie, instead of 2/10ths.
2. Fair proposer vs. Accepting responder
What if the accepting responder encounters a fair proposer?
λ: isEquilibriumPieSharingGame 10 stratTuplePCG_fairProposer_acceptingResponder
Analytics begin
Strategies are NOT in equilibrium. Consider the following profitable deviations:
Player: proposer
Optimal Move: 0.0
Current Strategy: fromFreqs [(5.0,1.0)]
Optimal Payoff: 10.0
Current Payoff: 5.0
Observable State: ()
Unobservable State: "((),())"
other game
No more information
NEWGAME:
Strategies are in equilibrium
NEWGAME:
Analytics end
That is, the responder is in equilibrium—they have no reason to stop accepting, but the engine still sees opportunities for the proposer to maximally exploit this agreeable responder.
3. Selfish proposer vs. Selfish responder
What if both are selfish?
λ: isEquilibriumPieSharingGame 10 stratTuplePCG_selfishProposer_selfishResponder
Analytics begin
Strategies are NOT in equilibrium. Consider the following profitable deviations:
Player: proposer
Optimal Move: 5.0
Current Strategy: fromFreqs [(2.0,1.0)]
Optimal Payoff: 5.0
Current Payoff: 2.0
Observable State: ()
Unobservable State: "((),())"
other game
No more information
NEWGAME:
Strategies are in equilibrium
NEWGAME:
Analytics end
This is good news for the responder. By offering a small piece to the responder, the proposer makes it very easy for the responder to choose the biggest piece. The suggested equilibrium for the proposer is the one we want: the optimal move is 5.0, or half exactly half of the pie.
4. Fair proposer vs. Selfish responder
This final suggested optimal move is implemented by a fair proposer:
λ: isEquilibriumPieSharingGame 10 stratTuplePCG_fairProposer_selfishResponder
Analytics begin
Strategies are in equilibrium
NEWGAME:
Strategies are in equilibrium
NEWGAME:
Analytics end
This shows that indeed, the incentives are such that the optimal move for the proposer is to be fair, at which point the strategy of the responder does not matter any more.
Next step
Now, the game listed above needs to be ‘opened up’ to become properly composable. My idea was to make size of the pie an input to the game, so that chosen pieces could be input into the next game as the new full pie size. A naive implementation would look like:
pieSharingGame_compositional = [opengame
inputs : pie ;
feedback : ;
::
inputs : pie ;
feedback : ;
operation : dependentDecision "proposer" (const [0..pie]);
outputs : proposal ;
returns : pieSharingGamePayoff_proposer pie proposal reaction;
inputs : proposal ;
feedback : ;
operation : dependentDecision "responder" (const [Accept,Reject]);
outputs : reaction ;
returns : pieSharingGamePayoff_responder pie proposal reaction ;
::
outputs : (proposal,reaction) ;
returns : ;
]
But this lead to the compiler error:
• Variable not in scope: pie :: Double
Why? What is the proper way to open up the pieSharingGame?
UPDATE: this is now implemented here
maths
categorytheory
gametheory