Compositionally sharing pie fairly
(This is an update on my Ethereum Protocol Fellowship. More updates can be found here ).
Last week, I constructed an Open Game that described players sharing a pie using the ‘I cut you choose’ rule. The compositional rules and strategies led to an exponentially unfair final pie distribution. In this post, I will outline the BigPlayer rule that should fix this and has a Nash equilibrium at a fair distribution of pie among the players. Furthermore, the final fair distribution among $n$ players is the result of only $n-1$ cuts, so each player has a contiguous piece of pie.
Definition The BigPlayer rule is defined by the following rules:
- $P_1$ cuts the pie in two pieces, resulting in two pieces of sizes $(\alpha C, (1-\alpha )C)$, where $\alpha \in [0, 1]$.
- $P_2$ chooses one of the two pieces.
- If there are any players left who did not play yet: Let the last cutter and the chooser be $(P_a, P_b)$, respectively, and the size of their pieces $(a, b)$, respectively. Then, let $P_\text{BP}=P_a$ if $a\geq b$, and $P_\text{BP}=P_b$ otherwise. $P_\text{BP}$ then has to cut their piece in two.
- A player that did not play yet chooses one of $P_\text{BP}$’s pieces.
- Move to 3 if there are any players that have not played yet.
This aligns the incentives so that each player ends up with an equal share of the pie. For example, say that there are 3 players in total, and Player 1 cuts a cake of size 10 into two pieces of sizes 4.9 and 5.1. Player 2 might be tempted to pick the piece of size 5.1, but this would mean that Player 2 would have to share this piece with Player 3, and surely would end up with at most a piece of size 2.55. Alternatively, if Player 2 picks the piece of size 4.9, then that is great news for Player 2, but terrible for Player 1 who would end up with at most 2.55 after sharing with Player 3. Therefore, Player 1 would never make the 4.9 and 5.1 cut in the first place. Player 1 maximises their piece of pie by cutting the cake into 1/3 and 2/3, at which point Player 1 does not care anymore which piece Player 2 chooses. In fact, each player will end up with 1/3 of the cake. Even better, the cake has been fairly shared using only 2 cuts! This is remarkable as this is supposed to be forbidden by the following famous theorem:
Theorem No finite algorithm can guarantee each of $n$ players at least $1/n$ of the cake using only $n - 1$ cuts when $n > 2$.
The BigPlayer rule seems to contradict this fundamental theorem of cake-cutting. However, the above theorem applies to the more general case where each player has a different valuation function for the cake, and the players do not have access to each other’s valuation functions. That is obviously a much more challenging problem, and not addressed by the BigPlayer rule. In fact, deciding who the big player is requires a shared valuation function to begin with.
Update: in this post, I show that the BigPlayer rule indeed has a proportional equilibrium for $n$ players.
To investigate the equilibria in this system, I encoded it in the Open Game engine as follows. Just like in last week’s games, the fundamental actions are a) responding to an offered piece of pie, and b) cutting a pie to create a new offer. I had defined the following data types and helper functions:
type Pie = Double
type Offer = (Double, Double)
data ResponderAction = Accept | Reject
deriving (Eq,Ord,Show)
propagateChosenPiece :: Offer -> ResponderAction -> Double
propagateChosenPiece offer response = if response == Accept then (fst offer) else (snd offer)
fromOfferedPieceToOffer :: Double -> Double -> Offer
fromOfferedPieceToOffer chosenPiece offeredPiece = (offeredPiece, chosenPiece - offeredPiece)
However, for this game, the identities of the players are dynamic, since it is not a priori clear which players will play in the current round. The Open Game DSL allows for strategic decisions that depend on the player identity through a dependentRoleDecision, so I defined dependent versions of the fundamental games from last week:
respondToOffer_dependent = [opengame|
inputs : playerName, offer ;
feedback : response;
:----------------------------:
inputs : playerName, offer ;
feedback : ;
operation : dependentRoleDecision (\(x, y) -> [Accept,Reject]) ;
outputs : response ;
returns : 0;
// Postpone payoff calculation, so here just return a payoff of 0.
:----------------------------:
outputs : response ;
returns : ;
|]
offerNewSlice_dependent = [opengame|
inputs : playerName, offer, response ;
feedback : ;
:----------------------------:
inputs : offer, response ;
feedback : ;
operation : forwardFunction $ uncurry propagateChosenPiece;
outputs : chosenPiece ;
returns : ;
inputs : playerName, chosenPiece ;
feedback : ;
operation : dependentRoleDecision (\(playerName, x) -> actionSpace x) ;
outputs : newOfferedPiece ;
returns : 0 ;
inputs : chosenPiece, newOfferedPiece ;
feedback : ;
operation : forwardFunction $ uncurry fromOfferedPieceToOffer;
outputs : newOffer ;
returns : ;
:----------------------------:
outputs : newOffer ;
returns : newResponse;
|]
where
actionSpace x = [0, 0.1 .. x]
As you can see, the decisions and the action space do not actually depend on the player identity, but since they are now explicitly linked to it, the engine can keep track of which player is making which decision, so payoffs and strategies can be analysed and matched. I’ve also implicitly added a cutting precision by specifying the action space as having a resolution of 0.1.
Crucially, we need to find out which of the two players in a game ended up with the biggest piece. For this I defined the following helper function that orders the players and their pieces by size (not very Haskelly—but it works):
orderBySize :: (Agent, Agent, Offer, ResponderAction) -> ((Agent, Payoff), (Agent, Payoff))
orderBySize (p1Name, p2Name, offer, response) = if (pieceP1 >= pieceP2)
then ((p1Name, pieceP1), (p2Name, pieceP2))
else ((p2Name, pieceP2), (p1Name, pieceP1))
where
pieceP1 = if response==Accept then (snd offer) else (fst offer)
pieceP2 = if response==Accept then (fst offer) else (snd offer)
This allowed me to write down a game that describes two players sharing pie with the BigPlayer rule:
bigPlayer_unit player2Name payoffBP = [opengame|
inputs : inputBigPlayer, inputOffer ;
feedback : ;
:----------------------------:
//Player 1 is last round's BigPlayer, so quickly "accepts" the full piece
//to propagate their piece into this round.
//They offer a slice to Player 2, but get no payoff yet!
inputs : inputBigPlayer, inputOffer, Accept ;
feedback : ;
operation : offerNewSlice_dependent;
outputs : offerP1 ;
returns : responseP2_backwards ;
//Player 2 responds
inputs : player2Name, offerP1 ;
feedback : responseP2_backwards;
operation : respondToOffer_dependent ;
outputs : responseP2 ;
returns : ;
//Find the smallest player and give them their payoff
inputs : inputBigPlayer, player2Name, offerP1, responseP2;
feedback : ;
operation : forwardFunction $ orderBySize ;
outputs : (bigPlayerName, biggestPiece), (smallPlayerName, smallestPiece);
returns : ;
inputs : smallPlayerName, smallestPiece ;
feedback : ;
operation : addRolePayoffs;
outputs : ;
returns : ;
//The bigPlayer only gets a payoff if they are the last player
inputs : bigPlayerName, biggestPiece * payoffBP ;
feedback : ;
operation : addRolePayoffs;
outputs : ;
returns : ;
:----------------------------:
outputs : bigPlayerName, fromOfferedPieceToOffer biggestPiece biggestPiece ;
returns : ;
|]
The game needs the two identities of the players who will be playing. The identity of Player 1 is fed in as an input from the context so that it can be propagated through sequential compositions. The identity of Player 2 can simply be set through an exogenous parameter of the game. Instead of setting the payoffs of the players with a payoff function fed into the returns field, I decided to use the addRolePayoffs functionality that allows the payoffs to be directly written to the hidden state. Note that the game takes a second parameter called payoffBP. Each round, the player with the smallest piece exits the game, so can immediately get their payoff. In contrast, the BigPlayer will need to play another round, so cannot get a payoff yet. To enforce this, the payoff of the BigPlayer is multiplied by payoffBP, usually set to zero. However, in the final round of the game, the BigPlayer also exits with their piece, so payoffBP should be set to one.
This bigPlayer_unit game is not very interesting in itself. In a context that offers a pie (and simply discards the output), it is equivalent to the two-player ‘I cut you choose’ game from last week. This context can be constructed as follows:
contextContPie :: Double -> StochasticStatefulContext
(String, Offer)
()
(String, Offer)
()
contextContPie fullPieSize = StochasticStatefulContext
(pure ((),("p1", (fullPieSize, 0)))) (\_ _-> pure ())
However, the bigPlayer_unit game can be easily composed into more complex situations. Composing it twice gives a game with 3 players:
bigPlayers_composed_3Players = [opengame|
inputs : inputBigPlayer, inputOffer ;
feedback : ;
:----------------------------:
inputs : inputBigPlayer, inputOffer ;
feedback : ;
operation : bigPlayer_unit "p2" 0 ;
outputs : bigPlayer1, offer1 ;
returns : ;
inputs : bigPlayer1, offer1;
feedback : ;
operation : bigPlayer_unit "p3" 1 ;
outputs : bigPlayer2, newOffer ;
returns : ;
:----------------------------:
outputs : bigPlayer2, newOffer ;
returns : ;
|]
To analyse the dynamics, consider the following strategy functions:
varAccept :: Double -> Offer -> Stochastic ResponderAction
varAccept r x = if (fst x) >= r then playDeterministically Accept else playDeterministically Reject
varAccept_conditional :: Double -> Double -> Offer -> Stochastic ResponderAction
varAccept_conditional r s x = if (fst x) >= r && (fst x) < (snd x) || (fst x) >= s then playDeterministically Accept else playDeterministically Reject
varOffer :: Double -> Double -> Stochastic Double
varOffer r x = playDeterministically $ r*x
varOffer_abs :: Double -> Double -> Stochastic Double
varOffer_abs r x = playDeterministically r
The offer strategies speak for themselves, and the varAccept strategy simply accepts all offers beyond a certain threshold. In contrast, varAccept_conditional accepts only if 1. the offer is large enough but smaller than the second piece (so that the payout is immediate) or 2. the offer is above some second threshold (usually set high enough so that even sharing ends of being profitable).
To create a full strategy profile, we need to provide strategies for the whole sequence of events: Player1 offers -> Player2 responds -> BigPlayer offers -> Player3 responds.
Let’s consider a slightly naive strategy: always offer half of your piece to the next player, and accept everything that is more than $C/N$, where $N$ is the total number of players:
strat_bigPlayer_3Players_test =
Kleisli (varOffer $ 1/2) ::- Kleisli (varAccept $ 10/3) ::-
Kleisli (varOffer $ 1/2) ::- Kleisli (varAccept $ 10/3) ::- Nil
Evaluating this gives the following output (showing only the relevant info):
λ: isEquilibrium_BigPlayer_3Players strat_bigPlayer_3Players_test
----Analytics begin----
Strategies are NOT in equilibrium. Consider the following profitable deviations:
Player: p1
Optimal Move: 5.1000000000000005
Current Strategy: fromFreqs [(5.0,1.0)]
Optimal Payoff: 4.8999999999999995
Current Payoff: 2.5
--other game--
--No more information--
NEWGAME:
Strategies are in equilibrium
NEWGAME:
Strategies are NOT in equilibrium. Consider the following profitable deviations:
Player: p1
Optimal Move: 3.3000000000000003
Current Strategy: fromFreqs [(2.5,1.0)]
Optimal Payoff: 3.3000000000000003
Current Payoff: 2.5
--other game--
--No more information--
NEWGAME:
Strategies are in equilibrium
NEWGAME:
----Analytics end----
When offering half, the cutter is chosen as the big player, so it is more profitable for Player 1 to offer 0.51 of the cake, so that Player 2 accepts and Player 1 can walk away with 0.49 of the cake. Furthermore, the second time Player 1 had to play, it would be best to order slightly less than $\frac{1}{3}$ of the cake, since then Player 3 would reject (stupidly).
Alternatively, consider the case in which each player plays fairly—offering 1/3 of the cake to each next player, and accepting any offer that is at least 1/3 of the cake and does not have to be shared, or so big that sharing it would still be profitable (more than 2/3 in this case):
strat_bigPlayer_3Players_eq =
Kleisli (varOffer_abs $ 10/3) ::- Kleisli (varAccept_conditional (10/3) (2*10/3)) ::-
Kleisli (varOffer_abs $ 10/3) ::- Kleisli (varAccept $ 10/3) ::- Nil
The analysis shows that this is indeed an equilibrium:
λ: isEquilibrium_BigPlayer_3Players strat_bigPlayer_3Players_eq
----Analytics begin----
Strategies are in equilibrium
NEWGAME:
Strategies are in equilibrium
NEWGAME:
Strategies are in equilibrium
NEWGAME:
Strategies are in equilibrium
NEWGAME:
----Analytics end----
Similarly, one can define the 4-player game by composing bigPlayer_unit three times:
bigPlayers_composed_4Players = [opengame|
inputs : inputBigPlayer, inputOffer ;
feedback : ;
:----------------------------:
inputs : inputBigPlayer, inputOffer ;
feedback : ;
operation : bigPlayer_unit "p2" 0 ;
outputs : bigPlayer1, offer1 ;
returns : ;
inputs : bigPlayer1, offer1;
feedback : ;
operation : bigPlayer_unit "p3" 0 ;
outputs : bigPlayer2, offer2 ;
returns : ;
inputs : bigPlayer2, offer2;
feedback : ;
operation : bigPlayer_unit "p4" 1 ;
outputs : bigPlayer3, newOffer ;
returns : ;
:----------------------------:
outputs : bigPlayer3, newOffer ;
returns : ;
|]
The perfectly fair strategy profile is given by:
strat_bigPlayer_4Players_eq =
Kleisli (varOffer_abs $ 10/4) ::- Kleisli (varAccept_conditional (10/4) (3*10/4)) ::-
Kleisli (varOffer_abs $ 10/4) ::- Kleisli (varAccept_conditional (10/4) (10/2)) ::-
Kleisli (varOffer_abs $ 10/4) ::- Kleisli (varAccept $10/4) ::- Nil
And indeed leads to an equilibrium:
λ: isEquilibrium_BigPlayer_4Players strat_bigPlayer_4Players_eq
----Analytics begin----
Strategies are in equilibrium
NEWGAME:
Strategies are in equilibrium
NEWGAME:
Strategies are in equilibrium
NEWGAME:
Strategies are in equilibrium
NEWGAME:
Strategies are in equilibrium
NEWGAME:
Strategies are in equilibrium
NEWGAME:
----Analytics end----
This shows that the ‘I cut you choose’ rule, composed with the ‘BigPlayer’ rule leads to a fair way to distribute pie among $n$ players using $n-1$ cuts. This extends to sharing any valuable resource, as long as the valuations of the different players agree. Where naively composing the ‘I cut you choose’ rule led to an exponentially unfair distribution with a Gini coefficient of $1/2$, adding the BigPlayer rule resulted in a perfectly fair Gini coefficient that is (asymptotically) zero.
maths category-theory game-theory