Jump to ContentJump to Main Navigation
A Game-Theoretic Perspective on Coalition Formation$

Debraj Ray

Print publication date: 2007

Print ISBN-13: 9780199207954

Published to Oxford Scholarship Online: January 2008

DOI: 10.1093/acprof:oso/9780199207954.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 05 December 2021

Reversible Agreements With Externalities

Reversible Agreements With Externalities

(p.183) CHAPTER 10 Reversible Agreements With Externalities
A Game-Theoretic Perspective on Coalition Formation

Debraj Ray (Contributor Webpage)

Oxford University Press

Abstract and Keywords

This chapter takes the second step in the study of reversible commitments by extending the framework given in Chapter 9 to cover situations with externalities across coalitions. Matters are quite different now; the ubiquitous absorption results reported for characteristic functions break down in this setting. Equilibrium payoffs may cycle, and even if they don't, inefficient outcomes may arise and persist. Indeed, the ability to make sidepayments — presumably to eliminate such inefficiencies — may actually worsen the situation. In particular, the variant of this book's model with upfront transfers can heighten the prevalence of inefficiency.

Keywords:   inefficiency, renegotiation, bargaining, value functions, farsightedness

In the last chapter, we showed that with no externalities across coalitions, a model of reversible commitments may display inefficiencies, but these are transitional. Over time, payoffs must converge to an efficient outcome. This result holds over a broad class of equilibria, including all equilibria with history-dependent strategies that satisfy a mild benignness restriction.

The purpose of this chapter is to argue that matters could be quite different when there are externalities. The ubiquitous absorption results reported for characteristic functions break down in this setting. Equilibrium payoffs may cycle, and even if they don't, inefficient outcomes may arise and persist. Finally — and in sharp contrast to characteristic functions — such outcomes are not driven by the self-fulfilling contortions of history-dependence. They occur even for Markovian equilibria.

Indeed, the ability to make sidepayments — presumably to eliminate such inefficiencies — may actually worsen the situation. In particular, the variant of our model with upfront transfers, which has thus far played a quiet and perfectly undistinguished role, now exhibits very distinctive properties.

Let's sidestep a common pitfall right away. It is tempting to think of inefficiencies as entirely “natural” equilibrium outcomes when externalities exist. Such an observation is true, of course, for games in which there are no binding agreements. Nash equilibria are “generally” inefficient, an assertion which can be given a precise formulation (see, e.g., Dubey (1986)). When agreements can be (p.184) costlessly written, however, no such presumption can and should be entertained. These are models of binding agreements, a world in which the so-called “Coase theorem” is relevant. For instance, in all that we've done so far, two-player games invariably yield efficiency, quite irrespective of whether there are externalities across the two players. This is not to say that the “usual intuition” has no role to play in the events of this chapter. It must, because the process of negotiation is itself modeled as a noncooperative game. But that is a very different object from the “stage game” over which agreements are sought to be written.

For the material in this chapter, I continue to rely on Gomes and Jehiel (2005) and Hyndman and Ray (2007). We begin with the baseline model and then move on to the variant with upfront transfers.

10.1 The Baseline Model for Three-Player Games

Three-player games represent an interesting special case. Even when externalities are allowed for, such games share a central feature with their characteristic function counterparts: each player possesses, in effect, a high degree of veto power in all moves that alter her payoff. This will allow us to prove a limited efficiency result, even when externalities are widespread.

It is worth noting that three-player situations have been the focus of study in several applied models of coalition formation (see, e.g., Krishna (1998), Aghion, Antras and Helpman (2004), Kalandrakis (2004) and Seidmann (2005)).

10.1.1 The Failed Partnership.

Begin with an example. Suppose that there are three agents, any two of whom can become “partners”. For instance, two of three countries could form a customs union, or a pair of firms could set up a production cartel or an R&D coalition with a commitment to share ideas. I presume that the outsider to the partnership gets a “low” payoff: zero, say. Finally, a three-player partnership is assumed not to be feasible (or has very low payoffs).

The crucial feature of this example is that player 1 is a bad partner, or — for the purposes of better interpretation — a failed partner. Partnerships between him and any other individual are dominated — both for the partners themselves and for the outsider — by all (p.185) three standing alone. In contrast, the partnership between agents 2 and 3 is rewarding (for those agents).

We formalize this as a partition function game. In the examples that follow, we simply record those states with nontrivial payoff vectors, and omit any mention of the remaining states, with the presumption that the payoffs in those states are zero to all concerned. We shall also be somewhat cavalier in our description of equilibrium and ignore these trivial states: equilibrium transitions from those states are implicitly defined in obvious ways.

EXAMPLE 10.1. Consider the following three-player game with minimal approval committees:

x 0 : π 0 = { { 1 } , { 2 } , { 3 } } , u ( x 0 ) = ( 6 , 6 , 6 ) x 1 : π 1 = { { 1 } , { 23 } } , u ( x 1 ) = ( 0 , 10 , 10 ) x 2 : π 2 = { { 2 } , { 13 } } , u ( x 2 ) = ( 5 , 0 , 5 ) x 3 : π 3 = { { 12 } , { 3 } } , u ( x 3 ) = ( 5 , 5 , 0 ) .

OBSERVATION 10.1. For δ‎ sufficiently close to 1 in Example 10.1, the outcomes x 2 and x 3which are inefficientmust be absorbing states in every equilibrium.

A formal proof of this observation isn't needed; the discussion to follow will suffice. Why might x 2 and x 3 be absorbing? The reason is very simple. Despite the fact that x 2 (or x 3) is Pareto-dominated by x 0, player 1 won't accept a transition to x 0. If she did, players 2 and 3 would initiate a further transition to x 1. Player 1 might accept such a transition if she is very myopic and prefers the short-term payoff offered by x 0, but if she is patient enough she will see ahead to the infinite phase of “outsidership” that will surely follow the short-term gain. In that situation it will be impossible to negotiate one's way out of x 2 or x 3. This inefficiency persists in all equilibria, history-dependent or otherwise.

Notice that x 2 or x 3 wouldn't be reached starting from any other state. This is why the interpretation, the “failed partnership”, is useful. The example makes sense in a situation in which players have been locked in with 1 on a past deal, on expectations which have failed since. To be sure, this interpretation is unnecessary for the formal demonstration of persistent inefficiency from some initial state.

(p.186) Notice that the players could negotiate themselves out of x 2 if 2 and 3 could credibly agree never to write an agreement while at x 0. Are such promises reasonable in their credibility? One could certainly assume that they are (economists and game theorists have been known to assume worse). However, it may be difficult to imagine that from a legal point of view, player 1, who has voluntarily relinquished all other contractual agreements between 2 and 3, could actually hold 2 and 3 to such a meta-agreement.

This example raises three important points. The first is an immediate outgrowth of the previous discussion. Does one interpret the standalone option (x 0) as an agreement from which further deviations require universal permission? Or does “stand-alone” mean freedom from all formal agreement, in which case further bilateral deals only need the consent of the two parties involved? Our discussion takes the latter view.

Second, observe that the lack of superadditivity in this example is important. If the grand coalition can realize the Pareto-improvement then player 1 can control any subsequent shenanigans by 2 and 3, and he will therefore permit the improvement. The issue of superadditivity is one to which we shall return below.

Finally, recall that upfront transfers are not permitted in this example. Were they allowed in unlimited measure, players 2 and 3 could reimburse player 1 for the present discounted value of his losses in relinquishing his partner. Depending on the discount factor, the amounts involved may be considerable. But they would break the deadlock. But upfront transfers have other, more subtle implications, and here too we must postpone the discussion to a later stage. An Efficiency Result for Three-Person Games.

The failed partnership or its later variant is not the only form of inefficiency that can arise. Appendix A to this chapter records three other forms of inefficiency, including one which can even arise from the stand-alone starting point of no agreements: the structure of singletons. In the light of these several examples, it is perhaps of interest that a positive (though limited) efficiency result holds for every three-person game satisfying a “minimal transferability” restriction. To state this restriction, let ū(i, π‎) be the maximum one-period payoff to player i over all states with the same coalition structure π‎.

(p.187) [T] If two players i and j both belong to the same coalition in coalition structure π‎, then ū(i, π‎) and ū(j, π‎) are achieved at different states.

PROPOSITION 10.1. Consider a three-person game with a finite number of states and satisfying condition T, with history-independent proposer protocols and minimal approval committees. Then for all δ‎ close enough to 1, there exists an initial state and a stationary Markov equilibrium with efficient absorbing payoff limit from that state.

The proof of Proposition 10.1 exhaustively studies different cases, and is therefore relegated to Appendix B.1 But we can provide some broad intuition for the result. Pick any player i and consider her maximum payoff over all conceivable states. If this maximum is attained at a state x * in which i belongs to a coalition with two or more players, then observe that i's consent must be given for the state to change. (This step is not true when there are four or more players, and invalidates the proposition, as we shall see later.) Because the payoff in question is i's maximum, it is easy enough to construct an equilibrium in which x * is an absorbing state.

It therefore remains to consider games in which for every player, the maximum payoff is attained at states in which that player stands alone. If no such state is absorbing in an equilibrium, one can establish the existence of a cyclical equilibrium path, the equilibrium payoffs along which are uniquely pinned down by the payoffs at the state in which all players stand alone. With the transferability condition T, one can now find payoff vectors for other coalitions (doubletons or more) such that some player in those coalitions prefer these payoffs to the cyclical equilibrium payoffs. The associated states then become absorbing, and a simple additional step establishes their efficiency.

We conjecture that neither the minimality of approval committees nor the history-independence of proposer protocols is needed for this result, but do not have a proof.

10.2 The Baseline Model for Four or More Players

The analysis in the previous section shows that once externalities are introduced, a failure of efficiency is a distinct possibility. In (p.188) the example of the failed partnership, one agent holds his partner hostage in the fear that if the partner is relinquished (so as to create a Pareto improvement), other deals will subsequently be struck that leave our agent with very low payoffs.

Yet, as Proposition 10.1 goes on to show, it isn't possible to create this phenomenon from every initial state. In the example of the failed partnership, the very state that the failed partner fears is undeniably Pareto-efficient. It's true that the failed partner suffers in this state, but the other two agents are certainly as well off as they can be. If negotiations were to commence with this state as initial condition, the resulting outcome must be efficient. In short, if one state isn't efficient something else must be, and we must ultimately arrive at some such state that's absorbing. This is the content of Proposition 10.1.

But don't make the mistake of supposing that such a proposition must follow from a simple process of eliminating inefficient states. Indeed, the proposition fails when the number of players exceeds three. To show this, I present an example that displays the most severe form of inefficiency: every absorbing state in every Markovian equilibrium is static inefficient, and every nonconvergent equilibrium path in every Markovian equilibrium is dynamically inefficient.

EXAMPLE 10.2. Consider the following four-player game with minimal approval committees:

x 1 : π 1 = { { 12 } , { 3 } , { 4 } } , u ( x 1 ) = ( 4 , 4 , 4 , 4 ) x 2 : π 2 = { { 1 } , { 2 } , { 3 } , { 4 } } , u ( x 2 ) = ( 5 , 5 , 5 , 5 ) x 3 : π 3 = { { 1 } , { 2 } , { 34 } } , u ( x 3 ) = ( 0 , 0 , 10 , 10 ) x 4 : π 4 = { { 12 } , { 34 } } , u ( x 4 ) = ( 2 , 2 , 2 , 2 ) .

Assume that a fresh proposer is chosen with uniform probability at each proposal stage.

OBSERVATION 10.2. For δ‎ sufficiently close to 1 in Example 10.2, every stationary Markov equilibrium is inefficient starting from any initial state.

The proof of this result may be found in Appendix C.

As we've already discussed, the fact that some absorbing state in some equilibrium may be Pareto-dominated is not too surprising. In part, a similar logic is at work here. Begin with the state x 1, in which players 1 and 2 are partners and 3 and 4 are separate. This is a failed partnership (at least in a context in which players 3 and (p.189) 4 are not partners themselves): if the {12}-partnership disbands, the state moves to x 2 which is better for all concerned. But once at x 2, we see other latent, beneficial aspects of the erstwhile partnership between 1 and 2: if players 3 and 4 now form a coalition, they can exploit 1 and 2 for their own gain; this is the state x 3.

So far, the story isn't too different from that of the failed partnership. But the similarity ends as we take up the story from the point at which 3 and 4 fashion their counterdeviation to x 3. Their gains can be reversed if players 1 and 2 form (or depending on the dynamics, re-form) a coalition. Balance is now restored; this is the state x 4.2 Finally, in this context, the partnership between 3 and 4 is more a hindrance than a help (just as {12} was in the state x 1), and they have an incentive to disband. We are then “back” to x 1.

This reasoning appears circular, and indeed in a sense it is, but such a circularity is in fact the essential content of Observation 10.2: as long as equilibria are Markovian, there is asymptotic inefficiency from every initial condition, despite the ability to write and renegotiate permanently binding agreements.

One might suspect that the Observation is vacuous in that no Markov equilibrium, efficient or not, exists. I could allay such suspicions by appealing to the existence theorem mentioned in Chapter 8, but it may be better to display such equilibria explicitly. Here is one. In it:

State x 1 is absorbing.

State x 2 moves back to x 1 when 1 or 2 propose, and on to x 3 whenever 3 or 4 propose.

State x 3 moves to x 4 when 1 or 2 propose, and remains unchanged otherwise.

State x 4 moves to x 1 no matter who proposes.

Observe that the state x 1, which is plainly Pareto-dominated, is not just absorbing but “globally” absorbing.3

To verify that this description constitutes an equilibrium, begin with state x 1. Obviously players 3 and 4 do not benefit from changing the (p.190) state to x 4, which is all they can unilaterally do. Players 1 and 2 can (bilaterally) change the state to x 2, by the presumed minimality of approval committees. If they do so, the subsequent trajectory will involve a stochastic path back to x 1.4 Some fairly obvious but tedious algebra reveals that the Markov value function V i(x,δ‎) satisfies

V i ( x 2 ) = 5 3 δ + δ 2 ( 1 + δ ) 2 ( 1 δ 2 )

for i = 1, 2. This value converges (as it must) to that of the absorbing state — 4 — as delta goes to 1, but the important point is that the convergence occurs “from below”, which means that V i(x 2, δ‎) is strictly smaller than V i(x 1, δ‎) = 4 for all delta close enough to 1.5 Perhaps more intuitively but certainly less precisely, the move to state x 2 starts off a stochastic cycle through the payoffs 5, 0 and 2 before returning to absorption at 4, which is inferior to being at 4 throughout. This verifies that players 1 and 2 will relinquish the opportunity at x 1 to switch the state to x 2. It also proves that once at state x 2, players 1 and 2 will want to return to the safety of x 1 if they get a chance to move.

On the other hand, players 3 and 4 will want to move the state from x 2 to x 3. Proving this requires more value-function calculation. A second round of tedious algebra reveals that

V i ( x 3 , δ ) V i ( x 2 , δ ) = 5 6 δ + δ 2

for i = 3, 4. This difference vanishes (as it must) as δ‎ approaches 1, but once again the important point is that the difference is strictly positive for all δ‎ close to 1 (indeed, for all δ‎), which justifies the move of 3 and 4.

That 1 and 2 must want to move away as quickly as possible from state x 3, and 3 and 4 not at all, is self-evident. That leaves x 4. At this state players 3 and 4 receive their worst payoffs, and will surely (p.191) want to move to x 1, and indeed, players 1 and 2 will want that as well.6 Our verification is complete.

There is actually a second equilibrium with no absorbing states, in which players 1 and 2 randomize between states x 1 and x 2, while players 3 and 4 randomize between states x 3 and x 4. While we omit the details, it is easy to check that such an equilibrium displays (dynamic) inefficiency from every initial condition, because it must spend nonnegligible time at the inefficient states x 1 and x 4. We omit the details.

Two final remarks are in order regarding this example. First, the strong form of inefficiency is robust to (at least) a small amount of transferability in payoffs. The reason is simple; given the payoffs at x 3 (resp. x 4), the payoffs to players 1 and 2 (resp. 3 and 4) are still minimal. Therefore, these states cannot be absorbing. But then, even with a little transferability, we are in the same situation as in the example.

Second, the example is not robust to the use of history dependent strategies. Indeed, x 2 can be supported as an absorbing state provided that deviations from x 2 are punished by a return to the inefficient stationary equilibrium in which x 1 is absorbing.

This last remark creates an interesting contrast between models based on characteristic functions and those based on partition functions. In the former class of models, the work of Seidmann and Winter (1988) and Okada (2000) assure us that ongoing negotiations lead to efficiency under Markovian equilibrium. It's the possibility of history-dependence that creates the inefficiency problem, albeit one that we successfully resolved in Chapter 9 with the help of the benignness condition. In contrast, partition functions are prone to inefficiency under Markovian equilibrium, as Examples 10.1 and 10.2 illustrate. History-dependence might help to alleviate this problem (it does in Example 10.2, though not in Example 10.1).

(p.192) 10.3 Superadditive Games

An important feature of the examples in Section 10.2 is that they employ a subadditive payoff structure. Is that a reasonable assumption? This is a subtle question that recalls the discussion in Section 3.4 of Chapter 3. We continue that discussion here.

First, it should be noted that in games with externalities superadditivity is generally not to be expected. For instance, recall the example of the Cournot oligopoly studied in detail in Chapter 6. Using the partition function developed there, it is easy to see that if there are just three firms, firms 1 and 2 do worse together than apart, provided that firm 3 stands separately in both cases.

At the same time, this argument does not apply to the grand coalition of all firms. Indeed, every partition function derived from a game in strategic form must satisfy grand coalition superadditivity (GCS):

[GCS] For every state x = (u, π‎), there is x′ = (u′, {N}) such that u′ ≥ u.

Is GCS a reasonable assumption? In Chapter 3 we've argued that in many cases it may not be. To continue that discussion without undue repetition, one possible interpretation of GCS is that it is a “physical” phenomenon; e.g., larger groups organizing transactions more efficiently, or sharing the fixed costs of public good provision. Yet such superadditivities are often the exception rather than the rule. After all, the entire doctrine of healthy competition is based on the notion that physical superadditivity, after a point, is not to be had. In general, too many cooks do spoil the broth: competition among groups can lead to efficiency gains not possible when there is a single, and perhaps larger, group attempting to act cooperatively. In addition to competition, Section 3.4 lists a host of other reasons for lack of physical superadditivity.7

But some game theorists might argue that this isn't what is meant by superadditivity at all. They have in mind a different notion of GCS, which is summarized in the notion of the superadditive cover. After all, the grand coalition can write a contract which (p.193) exactly replicates the payoffs obtainable in some other coalition structure. For instance, companies do spin off certain divisions, and organizations do set up competing R&D groups. In a word, the grand coalition can agree not to cooperate, if need be.

In a static setting, such a position represents, perhaps, no loss of generality. But in a dynamic setting this view embodies a crucial assumption: that future changes in the strategy of (or in the alliances formed by) one of the subgroups will require the consent of the entire grand coalition of which that group was supposedly a part. For example, consider contracts between senior executives and firms. They typically contain a clause enjoining the executive from working for a competitor firm for a number of years — so-called no compete clauses. To some extent, this reflects the notion of the superadditive cover: surely, if all parties agreed, the executive would be free to work for the competitor, while if the original firm dissents, she would not — at least for a certain length of time. To the extent that such contracts cannot be enforced for an infinite duration, the model without grand-coalition superadditivity can be viewed as a simplification of this, and other, real-world situations.

Nevertheless, GCS applies without reservation to many other cases. So it is worth recording that GCS restores (Markovian) efficiency, at least if the existence of an absorbing limit payoff is assumed:

PROPOSITION 10.2. Under GCS, every absorbing payoff limit of every Markovian equilibrium must be static efficient.

The proof follows a much simpler version of the argument for Proposition 9.2 and we omit it.

It must be noted, however, that GCS does not guarantee long-run efficiency in all situations: Example 10.2 can be modified so that GCS holds but there is an inefficient cycle over states that do not involve the grand coalition. In order to guarantee that even this form of inefficiency does not persist in the long-run, one needs enough transferability of payoffs within the grand coalition. Indeed, it can be proved that under GCS and the additional assumption that the payoff frontier for the grand coalition is continuous and concave, every Markov equilibrium must be absorbing — and therefore asymptotically efficient.

(p.194) 10.4 Upfront Transfers and the Failure of Efficiency

How does the ability to make transfers affect the examples? It is important to distinguish between two kinds of transfers. Coalitional or partnership worth could be freely transferred between the players within a coalition. Additionally, players might be able to make large upfront payments in order to induce certain coalitions to form. In all cases, of course, the definition of efficiency should match the transfer environment.8

Within-coalition transferability often does nothing to remove inefficiency. For instance, nothing changes in the failed partnership of Example 10.1. On the other hand, upfront transfers across coalitions have an immediate and salubrious effect in that example. Efficiency is restored from every initial state. The reason is simple. If player 1 is offered any (discount-normalized) amount in excess of 5, he will “release” player 2. In view of the large payoffs that players 2 and 3 enjoy at state x 1, they will be only too pleased to make such a payment. The final outcome, then, from any initial condition is the state x 1, and we have asymptotic efficiency. It is true that the amount of the transfer may have to be enormous when the discount factor is close to 1, but we've already discussed that (see Section 8.2.2 in Chapter 8). Our concern here is with the implications of the upfront-transfer scenario.

The beauty of the Gomes-Jehiel (2005) paper, on which I now proceed to rely, is that it unearths an entirely different face of upfront transfers. To see this, I introduce a seemingly innocuous variant of Example 10.1:

EXAMPLE 10.3. Consider the following three-player game with minimal approval committees:

x 0 : π 0 = { { 1 } , { 2 } , { 3 } } , u ( x 0 ) = ( 6 , 6 , 1 ) x 1 : π 1 = { { 1 } , { 23 } } , u ( x 1 ) = ( 0 , 7 , 2 ) x 3 : π 3 = { { 12 } , { 3 } } , u ( x 3 ) = ( 5 , 5 , 0 )

and all other states have payoff 0.

(p.195) First, take a quick look at this example without introducing upfront transfers and compare it with its predecessor, Example 10.1. Little of substance has been changed, though we've broken symmetry by assigning zero to any partnership between Players 1 and 3. Players 1 and 2 still form a “failed partnership” at x 3, yet at that state player 1 continues to cling to player 2. They would prefer to move to state x 1, but player 1 rationally fears the subsequent switch to x 2, something that is out of his control.

But the introduction of upfront transfers in this example has a perverse effect. Instead of taking the inefficiency away (as it does in Example 10.1), it generates inefficiency from every initial condition.

OBSERVATION 10.3. In Example 10.3, every stationary Markov equilibrium is inefficient starting from any initial state.

It isn't hard to see what drives the assertion. With unlimited upfront transfers, we are entitled to add payoffs across players to derive our efficiency criterion. Only the state x 0 is efficient on this score, and if an equilibrium is to display asymptotic efficiency — whether dynamic or static — it can stay away from x 0 for a finite number of dates at best. Now the root of the trouble is clear: players 2 and 3 invariably have the incentive to move away from x 0 to x 1. Not that matters will come to an end there: the fact that x 1 is itself inefficient will cause further movement across states as upfront transfers continue to be made along an infinite subsequence of time periods. The precise computation of such transfers is delicate,9 but the assertion that efficiency cannot be attained should be clear.

Actually, Example 10.3, while it makes the point well enough, obscures a matter of some interest. In that example, players 2 and 3 gain on two counts when they move the state from x 0 to x 1. They make an immediate gain in payoffs, and then they gain even more subsequently as they are paid additional ransom in the form of upfront transfers. The point of the next example is that the “ransom effect” dominates, at least when discount factors are close to 1.

(p.196) EXAMPLE 10.4. Consider the following three-player game with minimal approval committees:

x 0 : π 0 = { { 1 } , { 2 } , { 3 } } , u ( x 0 ) = ( b , b , b ) x 1 : π 1 = { { 1 } , { 23 } } , u ( x 1 ) = ( 0 , a , a ) x 2 : π 2 = { { 2 } , { 13 } } , u ( x 1 ) = ( a , 0 , a ) x 3 : π 3 = { { 12 } , { 3 } } , u ( x 3 ) = ( a , a , 0 )

and all other states have payoff zero. Assume that b > a > 0.

This example has none of the asymmetries of Example 10.3. There is a unique efficient state by any criterion. It is state x 0. It Pareto-dominates every other state. Players moving away from this state suffer an immediate and unambiguous loss in payoffs. Yet we have

OBSERVATION 10.4. In Example 10.4, every stationary Markov equilibrium under the uniform proposer protocol is inefficient starting from any initial state: the state x 0 can never be absorbing.

This observation highlights very cleanly the negative effects of upfront transfers. Players may deliberately generate inefficient outcomes to seek such transfers as ransom. This effect is particularly clear in Example 10.4 because each of the states x 1, x 2 and x 3 are Pareto-inferior to x 0.

It will be instructive to work through this example by informally proving Observation 10.4. For simplicity, we will spell out the details for all symmetric Markovian equilibria.

Suppose, contrary to the claim, that x 0 is absorbing. Then the (discount-normalized) value to each player is just b: V i(x 0) = b for all i. In each of the other states x i, player i is an “outsider” currently earning 0; denote her lifetime payoff by c, evaluated ex ante, before a proposer has been determined. The other two players are partners, denote by d their corresponding payoffs.

It is very easy to see that d is at least as large as c: the partners can make all the acceptable proposals that the outsider can make, while enjoying a current payoff which exceeds that of the outsider. Moreover, because x 0 is absorbing, it must be that bd, otherwise some pair would surely destabilize x 0.

The last of our preliminary observations is that no proposer in any of the nonabsorbing states x i stands to gain anything by switching the state to another nonabsorbing state x j: the sum of all payoffs is constant (at 2d + c) so there is no surplus to be grasped. On the other (p.197) hand, both the partners and the outsiders make a gain by steering the state back to x 0. Consequently, recalling that proposer protocol is uniform, we have

d = 1 3 [ b + { b ( 1 δ) a δ d } + ( b δ c ) ] + 2 3 [ ( 1 δ ) a + δ d ] .

The reason is simple. Take any partner at one of the nonabsorbing states. With probability 1/3, she gets to propose. She successfully moves the state straight away to x 0, earning a lifetime payoff of b, and can demand an upfront transfer of up to b − (1 − δ‎)aδ‎d from her partner, and up to bδ‎c from the outsider.10 With remaining probability 2/3, she is proposed to, in which case she will be driven down to her reservation value, which is precisely (1 − δ‎)a + δ‎d. Together, this gives us (10.1).

A parallel argument tells us that as far as the outsider is concerned,

c = 1 3 [ b + 2 { b ( 1 δ ) a δ d } + 2 3 δ c .

The reasoning is very similar to that underlying (10.1), and we'll skip the repetition.

Now combine (10.1) and (10.2) and simplify to see that

d = b + a 3 ,

which contradicts our initial presumption that bd. We have therefore proved that the unique efficient outcome cannot be stable. Consequently, the equilibrium path, no matter what it looks like, must display persistent inefficiency.

Notice that (in contrast to Example 10.3), the deviating players do suffer a loss in current payoff when they move away from the efficient state. But the prospect of inflicting a still greater loss on the outsider raises the possibility that the outsider will pay to have the state moved back — albeit temporarily — to the efficient point. This is a new angle on upfront transfers. They may lubricate the path to efficiency, but they might encourage deviations from efficient paths as well, in order to secure a ransom. Thus the presumption that unlimited transfers act to restore or maintain efficiency is wrong.

(p.198) One more feature of Example 10.4 is worth mentioning. The efficient state is one in which all three players stand apart. This is precisely what makes that state persistently unstable, for two players can always form an inefficient coalition. If this contractual right can be eliminated in the act of making an upfront transfer, then efficiency can be restored: once state x 0 is regained, there can be no further deviations from it. This line of discussion is exactly the same as in Section 10.3, and there is nothing further to add here.

More generally, the efficient state in this example has the property that a subset of agents can move away from that state (i.e., they can act as approval committee for a move) such that some other agents — not on the approval committee — are thereby rendered worse off in terms of current payoffs. Whenever this is possible, there is scope for collecting a ransom, and the potential for a breakdown in efficiency. Gomes and Jehiel (2005) develop this idea further.

10.5 Summary

Our study of coalitional bargaining problems in “real time” yields a number of implications. For characteristic function form games, a very general result for all pure-strategy equilibria (whether history-dependent or not) can be established: every equilibrium path of states must eventually converge to some absorbing state, and this absorbing state must be static efficient. This was the subject of Chapter 9.

In contrast, in games with externalities, matters are more complicated and none of the results for characteristic function games continue to hold without further conditions. It is easy enough to find a three-person example in which there is persistent inefficiency from some initial state, whether or not equilibria are allowed to be history-dependent. At the same time, we also show that in every three-person game, there is some Markovian equilibrium which yields asymptotic efficiency from some initial condition.

Yet even this limited efficiency result is not to be had in fourperson games. Section 10.2 demonstrates the existence of games in which every absorbing state in every Markovian equilibrium exhibits asymptotic static inefficiency.

(p.199) The situation is somewhat alleviated if the game in question exhibits grand coalition superadditivity. In that case, it is possible to recover efficiency, provided that the equilibrium is absorbing.

Finally, we show that the ability to make unlimited upfront transfers may worsen the efficiency problem.

The main open question for games with externalities is whether there always exists some history-dependent equilibrium which permits the attainment of asymptotic efficiency from some initial state (that there is no hope in obtaining efficiency from every initial state is made clear in Section 0.1.1). I am pretty sure that the answer should be in the affirmative: assuming — by way of contradiction — that equilibria are inefficient from every initial state, one should be able to employ such equilibria as continuation punishments in the construction of some efficient strategy profile. Such a result would be intuitive: after all, one role of history-dependent strategies is to restore efficiency when simpler strategy profiles fail to do so.

Finally, the general setup in Section 8.2 may be worthy of study, with or without binding agreements. For instance, the general setup is applicable to games in which agreements are only temporarily binding, or in which unanimity is not required in the implementation of a proposal. There is merit in exploring these applications in future work.

Other Examples For Three-Player Games.

In the examples below, if a coalition structure is omitted, it means that either every player obtains an arbitrarily large negative payoff or there is some legal impediment to the formation of that coalition structure. In all of the examples of this section, we assume minimal approval committees; for example, from the singletons, players 1 and 2 can approve a transition to any state y with coalition structure {{12}, {3}}.

More on Inefficiency. One response to the inefficiency example of Section 4.1.1 in the main text is that the inefficient state described there will never be reached starting from the singletons. Setting the initial state to the singletons has special meaning: presumably this is the state from which all negotiations commence. However, this is wrong on two fronts (at least for Markov equilibria) as we now show.

(p.200) Coordination Failures. Coordination failures, leading to inefficiency from every initial state, are a distinct possibility, even in three player games. Consider the following:

x 0 : π 0 = { { 1 } , { 2 } , { 3 } } , u ( x 0 ) = ( 2 , 2 , 2 ) x 1 : π 1 = { { 1 } , { 23 } } , u ( x 1 ) = ( 1 , 1 , 1 ) x 2 : π 2 = { { 2 } , { 13 } } , u ( x 2 ) = ( 1 , 1 , 1 ) x 3 : π 3 = { { 12 } , { 3 } } , u ( x 3 ) = ( 1 , 1 , 1 ) .

OBSERVATION 10.5. Suppose that everyone proposes with equal probability at every date. Then, for δ [ 3 5 , 1 ) there is an MPE in which x i is absorbing, and from x 0, there is a transition to x i with probability 1 3 for i = 1, 2, 3.

The proof is simple and we omit it.

Convergence to Inefficiency From The Singletons. Consider the following example, which is a variation on the “failed partnership” example of Section 4.1.1.

x 0 : π 0 = { { 1 } , { 2 } , { 3 } } , u ( x 0 ) = ( 5 , 5 , 5 ) x 1 : π 1 = { { 1 } , { 23 } } , u ( x 1 ) = ( 0 , 6 , 8 ) x 2 : π 2 = { { 2 } , { 13 } } , u ( x 2 ) = ( 3 , 0 , 10 ) x 3 : π 3 = { { 12 } , { 3 } } , u ( x 3 ) = ( 4 , 4 , 0 ) .

OBSERVATION 10.6. For any history-independent proposer protocol such that at x 0 each player has strictly positive probability of proposing, there exists δ‎̄ ∈ (0, 1) such that if, δ‎ ≥ δ‎̄, all stationary Markovian equilibria involve a transition from x 0 to x 3and full absorption into x 3 thereafterwith strictly positive probability.

Proof. Let α‎ = (α‎ 1, α‎ 2, α‎ 3) ∈ int(Δ‎) denote the proposers’ protocol at x 0. First notice that in every equilibrium x 1 and x 2 must be absorbing. The states x 1 and x 2 give players 2 and 3, respectively, their unique maximal payoff. Moreover, at x 1 (resp. x 2) player 2 (resp. player 3) has veto power over any transition. Second, in every equilibrium, x 0 cannot be absorbing. This follows because players 2 and 3 can always initiate a transition to x 1 and earn a higher payoff.

We now proceed with the rest of the proof. First, we rule out a “cycle” by proving the following: If there is a positive probability transition from x 0 to x 3, then x 3 must be absorbing. Indeed, suppose not. Then for i = 1, 2, V i(x 0) = V i(x 3) = 4. But then, from x 0, player 1 will always reject a transition to x 2, which means that V 2(x 0) ≥ 5, a contradiction.

Next suppose that the probability of reaching x 3 from the singletons is zero. Observe that V 1(x 0) ≤ 3, for if not, x 1 is the only absorbing state reachable from x 0, implying that V 1(x 0) → 0 for δ‎ sufficiently high, a contradiction. Similarly, V 3(x 0) ≤ 8, for if not, x 2 is the only absorbing state reachable from the singletons. But then for δ‎ sufficiently high, V 2(x 0) ≤ 4, implying that (p.201) players 1 and 2 would initiate a transition to x 3, a contradiction. Finally, observe that since x 3 is not reached with positive probability, it must be that V 2(x 0) ≥ 4, since otherwise, 1 would offer x 3 and it would be accepted.

Let p i denote the probability of a transition from x 0 to x i for i = 0, 1, 2. By assumption, p 3 = 0 and we have just shown that p 1, p 2 > 0. Given p i, write the equilibrium value functions and take the limit as δ‎ → 1 to obtain:

V ¯ 1 ( x 0 ) = 3 p 2 1 p 0 3 V ¯ 2 ( x 0 ) = 6 p 1 1 p 0 4 V ¯ 3 ( x 0 ) = 8 p 1 + 10 p 2 1 p 0 8.

From the third equation in (10.3), we see that p 2 = 0, which then implies that the first equation is satisfied with strict inequality. Therefore, player 1 strictly prefers to propose x 2, and the offer will be accepted by player 3. Hence, p 2 > α‎ 1 > 0, a contradiction. It then follows that for δ‎ sufficiently high the same conclusion may be drawn.

Cyclical Equilibria. Next, equilibrium cycles become a distinct possibility:

x 0 : π 0 = { { 1 } , { 2 } , { 3 } } , u ( x 0 ) = ( 1 , 1 , 1 ) x 1 : π 1 = { { 1 } , { 23 } } , u ( x 1 ) = ( 0 , 2 , 1 ) x 2 : π 2 = { { 2 } , { 13 } } , u ( x 2 ) = ( 1 2 , 4 , 1 ) .

OBSERVATION 10.7. Suppose that everyone proposes with equal probability at every date. Then there is an equilibrium with the following transitions:

x 0 2 / 3 x 1 1 x 2 2 / 3 x 0 .

Dynamic Inefficiency In Every Equilibrium. Though we did not formally prove this for characteristic functions, every Markovian equilibrium must exhibit full dynamic efficiency from some initial state. This is no longer true for games with externalities:

x 0 : π 0 = { { 1 } , { 2 } , { 3 } } , u ( x 0 ) = ( 1 , 1 , 1 ) x 1 : π 1 = { { 1 } , { 23 } } , u ( x 1 ) = ( 10 , 0 , 0 ) x 2 : π 2 = { { 2 } , { 13 } } , u ( x 2 ) = ( 0 , 10 , 0 ) x 3 : π 3 = { { 12 } , { 3 } } , u ( x 3 ) = ( 0 , 0 , 10 ) .

If x i, i = 1, 2, 3 were absorbing, then for ji, V j(x i) = 0. However, notice that in every Markovian equilibrium, for all i = 1, 2, 3, V i(x 0) ≥ 1. Therefore, j must accept a proposal from x i to x 0, hence a profitable deviation exists. Finally, it can be shown that any cyclical Markovian equilibrium must necessarily spend time at x 0. We have therefore proved:

(p.202) OBSERVATION 10.8. Suppose that everyone proposes with equal probability at every date. Then every Markovian equilibrium exhibits dynamic inefficiency from every initial state.

Proof of Proposition 10.1.

In what follows, we denote by π‎0 a singleton coalition structure, by π‎ i a coalition structure of the form {{i}, {j, k}}, and by π‎ G the structure consisting of the grand coalition alone. Use the notation π‎(x) for the coalition structure at state x and S i(x) for the coalition to which i belongs at x. Subscripts will also be attached to states (e.g., x i) to indicate the coalition structure associated with them (e.g., π‎(x i) = π‎ i).

For each i, let X * i argmax{u i(x)|xX}, with x * i a generic element. Finally, we will refer to π‎(x * i) = π‎ as a maximizing (coalition) structure (for i).

Case 1: There exists i = 1, 2, 3 and x * iX * i such that |S i(x * i)| ≥ 2.

Pick x * iX * i as described and consider the following “pseudo-game”. From x * i, there does not exist an approval committee capable of initiating a transition to any other state. Notice that a Markovian equilibrium exists for this pseudo-game (see the Supplementary Notes for the general existence proof) and that x * i is absorbing. Denote by σ‎* the equilibrium strategies for the pseudo-game. Return now to the actual game and suppose that players use the strategies σ‎*; suppose also from x * i that player i always proposes x * i and rejects any other transition. For other players ji, any proposal and response strategies may be specified. Denote this new strategy profile σ‎′. Notice that σ‎* and σ‎′ specify the same transitions for the pseudo-game and actual game and no player has a profitable deviation from x * i. Therefore, σ‎′ constitutes an equilibrium of the actual game. This equilibrium has an efficient absorbing state, x * i.

Case 2: For all i and for all x * iX * i, |S i(x * i)| = 1. A number of subcases emerge:

  1. (a) π‎(x * 1) = π‎(x * 2) = π‎(x * 3) = π‎ 0 for some (x * 1, x * 2, x * 3), but the maximizing structures are not necessarily unique.

  2. (b) π‎(x * 1) = π‎(x * 2) = π‎ 0 and π‎(x * 3) = π‎ 3, and while the maximizing structures are not necessarily unique, Case 2(a) does not apply.

  3. (c) For all players i = 1, 2, 3, π‎ i is the unique maximizing structure.

  4. (d) π‎(x * 1) = π‎ 0, π‎(x * j) = π‎ j, j = 2, 3 and each maximizing structure is unique.

(p.203) We now prove the proposition for each of these cases.

Case (a). Here x 0, the unique state corresponding to π‎ 0, is weakly Pareto-dominant and we construct an equilibrium as follows. From any state x, every player proposes a transition to x 0 and every player accepts this proposal. A deviant proposal y is accepted if V i(y) ≥ V i(x) = (1 − δ‎)u i(x) + δ‎u i(x 0). This is clearly an equilibrium with x 0 efficient and absorbing.

Case (b). The proof is similar to Case 1. Consider a pseudo-game in which there is no approval committee that can initiate a transition away from x 0. Again, we are assured of a Markovian equilibrium for the pseudo-game; denote the equilibrium strategies by σ‎* and notice that x 0 is absorbing. In the actual game, suppose that all players use the strategies given by σ‎*, and suppose that, at x 0, players 1 and 2 always propose x 0 and reject any transition from x 0. Call these strategies σ‎′.

As in Case 1, notice that σ‎* and σ‎′ specify the same transitions for the pseudo-game and the actual game, and no player has a profitable deviation from x 0. Therefore, σ‎′ constitutes an equilibrium of the actual game.

The following preliminary result will be useful for cases (c) and (d):

LEMMA 10.1. Suppose that player i's maximizing structure π‎^ is unique, and that π‎^ ∈ {π‎ 0, π‎ i}. Let Y = {y | π‎(y) ∈ {π‎ 0, π‎ i} − π‎^}. Then in any equilibrium such that xX * i is not absorbing, V i(x) > V i(y) for all yY.

Proof. We prove the case for which π‎^ = π‎ i. The proof of the case for which π‎^ = π‎ 0 is identical. Let xX * i. Note that Y = {x 0}. Suppose on the contrary that V i(x 0) ≥ V i(x). We know that

V i ( x ) = ( 1 δ ) u ¯ i + δ X V i ( z ) P ( x , d z ) .

Now, there could be — with probability μ‎ — a transition to the singletons, which player i need not approve. All other transitions must be approved by i, and she must do weakly better after such transitions. Using V i(x 0) ≥ V i(x), it follows that

V i ( x ) ( 1 δ ) u ¯ i + δ[ μ V i ( x 0 ) + ( 1 μ ) V i ( x ) ] ( 1 δ ) u ¯ i + δ V i ( x ) ,

so that V i(x) ≥ ū i. Strict inequality is impossible since ū i is i’s maximal payoff. So V i(x) = ū i, but this means that x is absorbing.

The next two lemmas prepare the ground for case (c).

LEMMA 10.2. Assume Case 2(c). Let y be not absorbing, and π‎(y) = π‎ j. Then y transits one-step to x 0 with positive probability.

(p.204) Proof. Suppose not. Then player j is on the approval committee for every equilibrium transition from y. Therefore

V j ( y ) u j ( y ) .

At the same time, y is not absorbing by assumption. But then the above inequality is impossible, since u j(y) is the uniquely defined maximal payoff for j across all coalition structures.

LEMMA 10.3. Assume Case 2(c). Suppose that a state x i, with coalition structure π‎ i, is part of a nondegenerate recurrence class (starting from x i). Then V j(x 0) = V j(x i) for all ji.

Proof. First, since x i is not absorbing, by Lemma 10.2, x i transits one-step to x 0 (with positive probability) and both players ji must approve this transition. Therefore

V j ( x 0 ) V j ( x i ) .

Next, consider a path that starts at x 0 and passes through x i (there must be one because x i is recurrent). Assume without loss of generality that it does not pass through x 0 again. If both individuals ji must approve every transition between x 0 and x i, we see that V j(x 0) ≤ V j(x i), and combining this with (10.4), the proof is complete.

Otherwise, some ki does not need to approve some transition. This can only be a transition from x 0 to a state x k with coalition structure π‎ k, with subsequent movement to x i without reentering x 0. So V k(x i) ≥ V k(x k). But x k itself is not absorbing and so by Lemma 10.2 transits one-step to x 0 (with positive probability). By Lemma 10.1, V k(x k) > V k(x 0). Combining these two inequalities, V k(x i) > V k(x 0), but this contradicts (10.4).

Case (c). We divide up the argument into two parts. In the first part, we assume that for some i, some state x i (with coalition structure π‎ i) is part of a nondegenerate recurrence class. Suppose that no efficient payoff limit exists. We first claim that

V j ( x 0 ) = V j ( x i ) = u j ( x i ) for all j i .

To prove this, consider an equilibrium path from x i. If this path never passes through x 0, then it is easy to see that all three players must have their value functions monotonically improving throughout, so one-period payoffs converge. Moreover, the limit payoff for player i must be at the maximum, so this limit is efficient. Given our presumption that there is no efficient limit, the path does pass through x 0, so consider these alternatives:

  1. (i) For some ji, the path passes a state y j (with structure π‎ j) before it hits x 0. Moreover, y j is not absorbing, and so by Lemma 10.2 it must transit one-step to x 0 with positive probability. However, player i must approve (p.205) all these moves; so V i(x 0) ≥ V i(y j) ≥ V i(x i). But this contradicts Lemma 10.1. So this alternative is ruled out.

  2. (ii) Otherwise, the path either transits one-step to x 0, or passes through a sequence of moves, all of which must be approved by both players ji. So for any one-step transition from x i to a state y, we have

    V j ( x 0 ) V j ( y ) V j ( x i )

    for ji. But by Lemma 10.3, V j(x 0) equals V j(x i) for ji. It follows that for every one-step transit y,

    V j ( y ) = V j ( x i )

    for ji. Consequently, for each such j,

    V j ( x i ) = ( 1 δ ) u j ( x i ) + δ V j ( y ) P ( x i , d y ) = ( 1 δ ) u j ( x i ) + δ V j ( x i ) .

    Using this, and V j(x 0) = V j(x i) for ji, the claim is proved.

We now show that there is an efficient absorbing state, contrary to our initial presumption. Consider a state x i (with structure π‎ i) to which the claim just established applies. By condition T, there is some other state x *, also with coalition structure π‎ i, such that for some ji, u j(x *) > u j(x i). Because j must approve every transition from x *, V j(x *) ≥ u j(x *) > u j(x i) = V j(x 0), where this last equality uses the claim. So x * cannot have an equilibrium transition to x 0, but then i must approve every equilibrium transition. However, since π‎ i gives player i his unique maximal payoff, he will reject every transition to a different coalition structure. Therefore, x * is both absorbing and efficient.

For the second part of case (c), suppose now that all recurrence classes are singletons. Assume by way of contradiction that all these are inefficient. This immediately rules out all absorbing states x i with π‎(x i) = π‎ i for some i, and it also rules out x 0.11

Now consider any state x i with π‎(x i) = π‎ i. Since it is not absorbing, V j(x i) ≥ u j(x i) for ji. Also Lemma 10.2 tells us that x i transits one-step to x 0 with positive probability, so V j(x 0) ≥ V j(x i) ≥ u j(x i). In particular, V j(x 0) ≥ max{ū(j, π‎ i), ij} for all j = 1, 2, 3. Moreover, because π‎ j is maximal for j and j must approve all other transitions from x 0 (as well as to all states from the structure π‎ j except for x 0), we have V j(x 0) ≥ u j(x 0), so V j(x 0) ≥ max{u j(x 0), ū(j, π‎ i), ij} for all j = 1, 2, 3. Since x 0 and x i are transient, there must be a path from x 0 to an absorbing state x G, but this implies that any (p.206) such absorbing state must satisfy u j(x G) ≥ max{u j(x 0), ū(j, π‎ i), ij} for all j = 1, 2, 3. Therefore, x G is efficient, contradicting our initial supposition.

Case (d). Proceed again by way of contradiction; assume there is no Markov equilibrium with efficient absorbing payoff limit. It is immediate, then, that any state x such that π‎(x) ∈ {π‎ 0, π‎ 2, π‎ 3} is not absorbing. It also gives us the following preliminary result:

LEMMA 10.4. If any state x 1 with π‎(x 1) = π‎ 1 is absorbing, then x 1 is not dominated by any state y with π‎(y) ∈ {π‎ 0, π‎ G}.

Proof. Suppose this is false for some x 1. It is trivial that x 1 cannot be dominated by any grand coalition state; otherwise x 1 wouldn't be absorbing. So x 0 dominates x 1. Consider any player j ≠ 1. From x 0, there may be a transition to z j with π‎(z j) = π‎ j, which j need not approve. She must approve all other transitions from x 0. Thus, along the lines of Lemma 10.1, we see that V j(x 0) ≥ u j(x 0) > u j(x 1) = V j(x 1) for j = 2, 3, but this contradicts the presumption that x 1 is absorbing (given the minimality of approval committees, 2 and 3 will jointly deviate).

As in case (c), divide the analysis into different parts.

(i) All recurrence classes are singletons.

Since all absorbing states are assumed inefficient, it is clear that all absorbing states must either have coalition structure π‎ 1 or π‎ G (since all states with coalition structures π‎ 0, π‎ 2 and π‎ 3 are efficient). Consider x 0; it is transient. Let be an absorbing state reached from x 0. By Lemma 10.2, we know that there must be a transition from any state with coalition structure π‎ 2 or π‎ 3 to x 0, and — because π‎ 0 is maximal for player 1 — from x 0 to some state with coalition structure π‎ 1 with strictly positive probability. Therefore, we may conclude that

V 1 ( x 0 ) max { u ¯ ( 1 , π 2 ) , u ¯ ( 1 , π 3 ) } V 2 ( x ^ ) V 2 ( x 0 ) max { { u ¯ ( 2 , π 3 ) , u 2 ( x 0 ) } V 3 ( x ^ ) V 3 ( x 0 ) max { { u ¯ ( 3 , π 2 ) , u 3 ( x 0 ) } .

This implies that is not Pareto-dominated by π‎ 0, π‎ 2 or π‎ 3.

Now, if π‎() = π‎ 1, then Lemma 10.4, the fact that π‎ 0, π‎ 2 and π‎ 3 are not absorbing, and (10.6) allow us to conclude that must be efficient, a contradiction. So suppose that π‎() = π‎ G. Note that cannot be dominated by a state y such that π‎(y) = π‎ 1. For V i(y) ≥ u i(y) for i = 2, 3. Moreover, an argument along the same lines as Lemma 10.1 easily shows that V 1(y) ≥ u 1(y). Therefore, if were dominated by y, there would be a profitable move from , contradicting the presumption that it is absorbing. Therefore, (p.207) must be efficient, but this contradicts our assumption that no absorbing state is efficient.

(ii) There is some nondegenerate recurrence class (and all other states are either transient or inefficient).

Observe that analogues to Lemmas 10.2 and 10.3, and the first part of case 2(c) can be established for case (d). However, whereas in case 2(c), we were able to pin down the equilibrium payoff of two players along some nondegenerate recurrence class, now we can only pin down the equilibrium payoff of one player; that is, for a recurrent class which transits from x 0 to x i, i ≠ 1, we have: V j(x 0) = V j(x i) and V j(x 0) = u j(x i) for j ≠ 1, i.

Observe that if, for the player j whose payoffs we have pinned down, u j(x i) equals ū(j, π‎ i) and for the other player k who is part of the doubleton coalition with j, V i(x 0) ≥ ū(k, π‎ i), the argument based on condition [T] will not go through.12 That is, we cannot find another efficient state which one player (whose consent would be required for any transition) prefers to x 0. In this case, we must construct an equilibrium with some efficient absorbing state, and this is our remaining task.

First suppose that there does not exist a state x such that u i(x) > u i(x 0) for i = 2, 3 and for all y such that π‎(y) = π‎1, u 1(x) ≥ u 1(y).13 In the construction of the equilibrium, the following sets of states will be important: {x 0} and

S 2 u = { x | π( x ) = π 2 , u 3 ( x ) > u 3 ( x 0 ) } , S 2 d = { x | π( x ) = π 2 , u 3 ( x 0 ) u 3 ( x ) } , S 3 u = { x | π( x ) = π 3 , u 2 ( x ) > u 2 ( x 0 ) } , S 3 d = { x | π( x ) = π 3 , u 2 ( x 0 ) u 2 ( x ) } , S u = { x | π( x ) 1 , π G }, x efficient } , S 1 D = { x | π( x ) 1 , π G }, there is z { S 2 u , S 3 u , S u , x 0 } with u ( z ) u ( x ) } , S 2 D = { x | π( x ) 1 , π G }, there is z { S 2 d , S 3 d } with u ( z ) > u ( x ) ; and there is j { 23 } such that u j ( x 0 ) < u j ( x ) } S 1 D

Consider the following description of strategies:

  1. (a) For all players i = 1, 2, 3, from x 0 all players offer x 0 and accept a transition to another state y only if V i(y) > V i(x 0).


  1. (b) From all states x S 2 d S 3 d players i such that |S i(x) = 2| propose and accept x 0, while player i such that |S i(x)| = 1 proposes the status quo. An arbitrary player k accepts a transition to another state y only if V k(y) > V k(x).

  2. (c) From all states x S 2 u S 3 u S u all players propose the status quo and an arbitrary player k accepts a transition to another state y only if V k(y) > V k(x).

  3. (d) From all states x S 1 D all players propose a state z ( x ) S 2 u S 3 u S u { x 0 } and an arbitrary player k accepts a transition to another state y only if V k(y) > V k(x). If x is dominated by x 0, we require z(x) = x 0.

  4. (e) From all states x S 2 D all players propose the status quo and an arbitrary player k accepts a transition to another state y only if V k(y) > V k(x).

It is easy to see that these strategies constitute an equilibrium in which the singletons are absorbing. Moreover, every other state is either absorbing itself or transits (one-step with positive probability) to some absorbing state. Note that the states in S 2 D are absorbing for δ‎ high enough and are inefficient. The reason they are absorbing is clear: if a transition to a dominating state were allowed, there would eventually be a transition to the singletons, which, by assumption, hurts one of the players whose original consent is needed. That the actions defined in (e) above constitute best responses for δ‎ high enough follows from arguments similar to van Damme, Selten and Winter (1990): with a finite number of states and sufficiently patient players any such absorbing state could be implemented; one player will always prefer to reject any other offer.

Now suppose that there exists a state x such that u i(x) > u i(x 0) for i = 2, 3 and for some y such that π‎(y) = π‎1, u 1(x) ≥ u 1(y). In this case, the singletons clearly cannot be absorbing for δ‎ high enough. However, with a finite number of states one can easily construct an equilibrium with a positive probability path from x 0 to some efficient absorbing state for δ‎ high enough. In particular, from x 0, there is a positive probability transition to a state y ∈ π‎1; from y there is a probability 1 transition to some efficient state y′ which dominates y (if such a state exists; if not, y is absorbing).14

Proof of Observation 10.2.

(p.209) Step 1: x 3 and x 4 are not absorbing.

It is easy to see that V i(x 4) ≥ 2 for i = 1, 2. Moreover, since players 1 and 2 can initiate a transition from x 3 to x 4, x 3 is easily seen to be not absorbing. Similarly, V j(x 1) ≥ 4 for j = 3, 4; therefore, since players 3 and 4 can achieve x 1 from x 4, x 1 is not absorbing.

Step 2: x 2 absorbing implies x 2 is globally absorbing.

Suppose that x 2 is absorbing. Then clearly from x 1, players 1 and 2 would induce x 2. Moreover, since x 3 and x 4 are not absorbing, if x 2 is not reached, then x 1 must be reached infinitely often. But then 1 or 2 would get a chance to propose with probability 1 and would then take the state to x 2, a contradiction.

Step 3: x 2 cannot be globally absorbing.

If x 2 is globally absorbing then, from x 2, players 3 and 4 can get a payoff of 10 for some period of time, by initiating a transition to x 3, followed by, at worst, 2 for one period and 4 for another period, before returning to x 2, where it will get 5 forever thereafter.15 This sequence of events is clearly better for players 3 and 4 than remaining at x 2.

Step 4: x 1 absorbing implies x 1 globally absorbing.

Steps 2 and 3 imply that x 2 cannot be absorbing. Moreover, Step 1 tells us that neither x 3 nor x 4 can be absorbing. In particular, from x 2 players 3 and 4 initiate a transition to x 3, from x 3 players 1 and 2 initiate a transition to x 4 and (at least) players 3 and 4 initiate a transition back to x 1. Therefore, if x 1 is absorbing, it is globally absorbing.

Step 5: Every equilibrium is inefficient.

First suppose that we had an equilibrium in which x 1 is not absorbing. Then from the above analysis, nothing is absorbing. Now consider x 2. If players 1 and 2 always accept an offer of a transition from x 1 to x 2, then 3 and 4 will strictly prefer to initiate a transition from x 2 to x 3: in so doing, they can achieve an average payoff of at least 10 + 2 + 4 3 = 16 3 > 5. However, it is easily seen that players 1 and 2 earn an average payoff strictly less than 4 in this case. Therefore, players 1 and 2 would rather keep the state at x 1, contradicting the presumption that x 1 was not absorbing.

(p.210) The only remaining possibility is one in which players 1 and 2 are indifferent between a x 1 and x 2 and players 3 and 4 are indifferent between x 2 and x 3. If such an equilibrium were to exist, it must be that V i(x 1) = V i(x 2) = 4 for i = 1, 2, and V j(x 2) = V j(x 3) = 5 for j = 3, 4. Therefore, if such an equilibrium were to exist, it would also be inefficient since players spend a non-negligible amount of time at the inefficient states x 1 and x 4.

Thus either x 1 is the unique absorbing state or there is a sequence of inefficient cyclical equilibria depending on δ‎ n ↗ 1 such that players 1 and 2 are indifferent between x 1 and x 2 and players 3 and 4 are indifferent between x 2 and x 3.


(1) It should be noted that in most cases the result is stronger in that it does not insist upon δ‎ → 1; in only one case do we rely on δ‎ → 1.

(2) So the partnership {12} is not entirely a failure; it depends on the context.

(3) We are neglecting the trivial states with zero payoffs for all. Including them would obviously make no difference.

(4) We are arguing in the spirit of the one-shot deviation principle, in which the putative equilibrium strategies are subsequently followed. Even though the one-shot deviation principle needs to be applied with care when coalitions are involved, there are no such dangers here as all coalitional members have common payoffs.

(5) We verify this by differentiating V i(x 2, δ‎) with respect to δ‎ and evaluating the derivative at δ‎ = 1.

(6) Because we've developed the state space model at some degree of abstraction, we've allowed any player to make a proposal to any coalition, whether or not she is a member of that coalition. This is why players 1 and 2 ask 3 and 4 to move along. Nothing of qualitative import hinges on allowing or disallowing this feature. The transition from x 4 back to x 1 would still happen, but more slowly.

(7) In all of the cases, the argument must be based on some noncontractible factor, such as the creativity or productivity created by the competitive urge, or ideological differences, or the presence of stand-alone players who are outside the definition of our set of players but nevertheless have an effect on their payoffs.

(8) For instance, if transfers are not permitted, it would be inappropriate to demand efficiency in the sense of aggregate surplus maximization. If an NTU game displays inefficiency in the sense that “aggregate surplus” is not maximized, this is of little interest: aggregate surplus is simply the wrong criterion.

(9) Such transfers will have to be made with a rational eye on the fact that an endless cycle across states will, in fact, happen.

(10) If her partner refuses, she enjoys (1 − δ‎)a today and starting tomorrow, a present discounted value of δ‎d. She will therefore agree to any proposal that gives her more than this amount. A similar argument holds for the outsider, whose payoff conditional on refusal is just δ‎c.

(11) If x 0 is absorbing and inefficient, then it is dominated either by a state for the grand coalition or by a state with coalition structure π‎ i for some i. Either way, by minimality of approval committees, x 0 will surely fail to be absorbing.

(12) Of course, if these conditions are not satisfied, the same argument as in 2(c) implies the existence of an efficient absorbing state.

(13) That is, there is no state that players 2 and 3 prefer to the singletons which they can achieve, either directly or indirectly (by initiating a preliminary transition to the coalition structure π‎1).

(14) From x 0, there may also be a positive probability transition to some other state z. However, if π‎(z) ∈ {π‎2, π‎3} it is clearly efficient since at these states players 2 and 3 obtain their unique maximum. Moreover, for δ‎ high enough, it cannot be that π‎(z) = π‎G, since then this would imply that z Pareto-dominates y′.

(15) Surely, players 1 and 2 must initiate a transition to x 4 with some positive probability; otherwise, x 3 would be absorbing (which Step 1 shows to be impossible). However, once at x 4, under the assumption that any player can propose to move to any state, and the fact that (by Step 2) from x 1 there would be an immediate transition to x 2, there is no need to even pass through the intermediate state x 1.