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 2-player game multiple times, let’s define the 2-player 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