“A Noncooperative View of Coalition Formation and the Core,” M. Perry & P. Reny (1994)

Cooperative games are often justified by noting that, really, they are just noncooperative games where the exact nature of stages where bargaining and contracting among a potential coalition occur are assumed away. To my knowledge, no major game theory text spells out precisely how this equivalence might be shown. Today’s paper, from Perry and Reny, is as close as I’ve seen.

Perry and Reny show a game where the core can be implemented (meaning, the unique equilibrium outcomes will be the core) in a noncooperative equilibrium concept.

Consider a continuous time game. At any time, a player can choose how to divide a surplus v(S) among a coalition S of the N players. If a current proposal is on the table, members of the proposed coalition can choose to accept it at any time (with one caveat to be mentioned); the proposer is anonymous, so she must also “accept” her own proposal. If all members have accepted, we say a proposal is binding, any member of the coalition can take their allocation off the table, at which point the proposed allocation is eaten by all members of the accepting coalition and they leave the game forever. Only one non-binding proposal may be on the table at any time, no player may make a proposal to a strict subset of an existing binding proposal, and no player who has accepted a proposal may make a proposal. For a technical reason to be discussed, given a history h which comes into being at time t, players’ equilibrium strategies may not make a proposal, accept a proposal, or leave and consume until at least t+epsilon for some epsilon. Basically, this ensures that players can “react” to what other players do; for instance, if a proposal becomes binding, some agent not in the coalition has time to make a counterproposal before the coalition leaves and consumes.

The equilibrium concept is stationary subgame perfection (SSPE). Stationarity means, roughly, that history-dependent strategies depend only on the set of players remaining, the current proposal, the set of players who have accepted the current proposal, and the set of binding proposals. This rules out treating identical proposals by two different players as different nodes in the game tree.

The main theorem is this: every SSPE is in the core, and if the game is totally balanced, meaning that the game and every subgame (S,n) is balanced, then everything in the core is an SSPE. The proof is a bit long, but the intuition is exactly the story motivating the core: if a proposal is non-core, a blocking coalition can organize in time before the proposed allocation is eaten.

Here’s an example of how the proof works: Consider a seller-buyer game, with one seller holding one good he values at zero, and two potential buyers, both of which value the seller’s good at 1. You have probably seen that the only core allocation of this game is x*={1,0,0}. We can prove that x* is also the only SSPE. Assume not, and that x1 is less than 1 and WLOG x2 is less than or equal to x3. All players do not act in [0,epsilon] by the timing restriction. Consider a deviation by 1 at t1=epsilon where 1 proposes that he and player 2 just split the surplus currently going to player 3. At some time t2 after t1, player 1 accepts this. Player 2 can guarantee a payoff of x2+x3/2 by accepting, then leaving and eating, which would contradict {x1,x2,x3} being an SSPE. Therefore, 2 must not be accepting this proposal, and instead 3 must be making a proposal (y,T) in (t2,t3) such that, according to the equilibrium strategies, 2 gets at least x2+x3/2. By stationarity, then, if (x1,x2,x3) is an equilibrium, 2 has a deviation at time t in (0,epsilon) where he proposes (y,T) and gets at least x2+x3/2. This contradicts (x1,x2,x3) being an equilibrium. So (1,0,0) is the only candidate SSPE.

We can construct that SSPE. If time is not an integer, everyone is quiet. If the time is an integer and 1 is not a member of any coalition yet formed, then if the current proposal is (x*,N), anyone who has not yet accepted it does so. If all players have accepted (x*,N), they all leave. If (x*,N) is not the current proposal, 1 proposes it and the others do nothing. All that’s needed now are continuation strategies after a coalition other than (x*,N) has formed that player 1 has accepted. Call this (y,S). Consider the following strategies. If time is not an integer, still, everyone is quiet. Let d=1-y1-y2-y3 be the amount of surplus “wasted” by proposal (y,S), where y(i)=0 for all i if 1 is not in the coalition S. Let Y={y1+d,y2,y3}. If the current proposal is (Y,N), then each player who has not yet accepted does so. If the players have all accepted it, they leave. If the current proposal is not {Y,N} and player 1 has not accepted it, then player one proposes (Y,N) and the others are quiet. If player 1 has accepted the current proposal which is not {Y,N}, then player 2 (3) either accepts the current proposal or proposes (Y,N) depending on which gives her a higher payoff.

The intuition on why those strategies works is exactly the same as the usual intuition for the core in the seller-buyer game. You might think the buyers could form a coalition and extract some rent form the seller. But in any proposal where the buyers are extracting surplus, the seller can just offer slightly more surplus to one of the buyers, and by stationarity, the buyer will have to accept it. Hence, the proposal where the buyer extract surplus is neither core in the cooperative game nor an SSPE in the continuous game.

One final note: why a continuous game? Consider a discrete time game. When a proposal is made, the game can either be modeled such that any player can reject the proposal, or such that only members of the targeted coalition can do so. But both are problematic: the first because any player could hold out for any amount, giving the core no chance, and the second because if there is a core where player A needs players B and C to get A’s core allocation, but B and C do not need A in return, then B and C will form a coalition and A will have no chance of reaching an allocation where he gets his core payoff. In continuous time, any player can block a proposed coalition by making a counterproposal – there is always an epsilon length of time before the proposal is eaten after it is accepted – but they cannot hold out forever for an arbitrary payoff since the “blocking counterproposal” must be made only after a delay of epsilon following the original proposal, giving players time to accept the original one (though not to consumate it).

http://micro5.mscc.huji.ac.il/~economics/facultye/perry/view.pdf (Final Econometrica version)

Advertisements
%d bloggers like this: