The Generalized War of Attrition

A slightly revised version is published in American Economic Review, 1999, 89(1), 175-89.

Jeremy Bulow

Graduate School of Business, Stanford University, USA

and

Paul Klemperer

Nuffield College, Oxford University Oxford OX1 1NF England

Int Tel: +44 1865 278588 Int Fax: +44 1865 278557

email: paul.klemperer@economics.ox.ac.uk

November 1997

\underline{Abstract:}

We model a War of Attrition with N +K firms competing for N prizes. If firms must pay their full costs until the whole game ends, even after dropping out themselves (as in a standard-setting context), each firm’s exit time is independent both of K and of other players’ actions. If, instead, firms pay no costs after dropping out (as in a natural oligopoly), the field is immediately reduced to N + 1 firms. Furthermore, in this limit it is always the K − 1 lowest-value firms who drop out in zero time, even though each firm’s value is private information to itself. (100 words)

\underline{Keywords:} War of Attrition, Auctions, Standards, Natural Monopoly, Oligopoly, “Twoness”, “Strategic Independence”.

\underline{JEL Nos:} D43, D44, L13, O30

\underline{Acknowledgment}: We are extremely grateful to Faruk Gul for extensive conversations about the war of attrition. We also received very valuable help from other colleagues and seminar participants, especially Alan Beggs, Meg Meyer and Markus Möbius.

This paper analyzes wars of attrition with many players. Examples of such wars are common, and are sometimes referred to as “industry shakeouts”. For example, five to six firms are committed to making major investments in wireless phone service in each United States market. While Los Angeles and New York will be able to accomodate this number, many other markets are probably natural oligopolies that can profitably support only three or four firms. A similar battle is taking place in the Canadian long distance market.^{1}

Battles to control new technologies often resemble wars of attrition. For example, five firms—Zenith, Thomson, AT&T, General Instruments, and Philips Electronics, initially worked on competing HDTV standards, and Microsoft, Netscape, and Lotus are fighting to dominate the “groupware” that is used within corporate intranets. In interactive Videotex, the seven or more competing national standards that emerged in the 1970s were reduced to three by 1984 after long negotiations in the CCITT (the international standards organization in telecommunications), but the battle between these three incompatible systems is still unresolved. Remarkably, we have gone from over 300 word processing programs ten years ago to just WordPerfect and Word.^{2}

There are now three competing standards for digital wireless phone systems in the United States—CDMA (code division multiple access), TDMA (time division multiple access), and GSM (global system for mobile communications, the European standard). Consumers who purchase one type of handset will not be able to make or receive calls over a network that uses a different technology. While several large manufacturers have now decided to incur the expense of producing to three standards, others have a vested interest in the outcome; an estimated $29 billion annual market for equipment is at stake. The simultaneous development of three standards has deprived the industry of the scale and manufacturing economies of a single standard, and reduced demand by increasing consumer uncertainty. The result has been much lower volumes and slower growth than in Europe for the whole industry—including firms that have no interest in which standard is adopted.^{3}, ^{4}

1The battle for long distance market share [in Canada] has turned into a war of attrition....... Losses are piling up ....... Analysts and industry officials predict the ranks of Canada’s long distance companies will shrink sharply.” See The Wall Street Journal, July 25, 1997 p. B4.

2Some specialized programs like Scientific Word also exist, but the other mass-market word processors, like Xywrite and Wordstar, have vanished.

Multiple-player wars of attrition are also prominent in politics. In August, 1993 the United States Congress passed the Clinton Administration’s budget by the narrowest possible margin; if a single supporter in either the House or Senate had switched their vote, the plan would have been defeated. But although many Democrats would have preferred to vote against this unpopular bill, they were unwilling to see the new Democratic President defeated on a measure of such importance so, in the words of the New York Times “one member after another reluctantly fell into line to provide the 218-216 victory” in the House of Representatives.^{5}^{,}^{6} The last Congresswoman to vote for the budget bill virtually ensured her defeat in the next election by supporting the President;^{7} while she was promised a good job in the Administration in return for sacrificing her seat in Congress, it seems clear that she was a big loser relative to other Democrats who were then able to vote against the bill without affecting the outcome.^{8} Similarly, the bill was approved by the Senate, after an unusually protracted debate, by 50 votes plus

3We are grateful to Preston McAfee for suggesting this example.

The Cellular Telephone Industry Association decided in 1989 to adopt TDMA as the U.S. standard but was persuaded in 1993 to sanction CDMA as an alternative standard, contributing to the current upheaval. Obviously it will be better for the industry if the “right” standard wins, but many firms would be better off with any of the three standards than with the current confusion. See Business Week, February 24, 1997, p. 44, and June 2, 1997 p.132.

4Two recent papers, Farrell (1993) and David and Monroe (1994), have already argued that the way firms negotiate in industry standard-setting committees is most appropriately modeled as a war of attrition. See also Farrell and Saloner (1988).

5This is the narrowest possible margin, since in the U.S., unlike some other countries, representatives do not wish to abstain on a measure of this importance.

6See The New York Times, August 6, 1993, section 1 p.7.

7The bill was especially unpopular in very affluent districts like Marjorie Margolies-Mezvinsky’s. The Republicans chanted “Bye-bye Marjorie” as she cast the final vote in favour, and she was indeed comfortably defeated in the 1994 election.

8It is not known how many additional representatives would have voted for the President if their votes had been required. Representatives’ incentives were, of course, to deny any willingness to do this, but even so it was reported that Thornton of Arkansas and, perhaps, Minge of Minnesota were available to vote yes if necessary.

the Vice-President’s casting vote to 50.^{9}

Until now, the war of attrition literature^{10} has focused on games with two players, or the straightforward generalization to N + 1 players competing for N prizes. While many of the best examples do involve only two players, multiple player games are also important. We consider a generalized war of attrition in which N +K players are competing for N prizes, so that K must exit for the game to end.

Our examples have highlighted an important issue in modeling the generalized war of attrition. In a natural monopoly (or oligopoly) setting, once a firm has conceded defeat it drops out of the game and stops paying costs. In a battle over standards, as with PCS, even a firm that does not try to enforce its own standard will continue to bear higher costs until the remaining firms agree on a common standard (because of reluctance of consumers to buy and potentially higher manufacturing costs). With just two firms (or N +1), this problem never arises because once any firm drops out the war automatically ends.

To make the distinction clear, consider the following example: The chairman of the economics department calls a meeting, and says that he needs five volunteers to serve on a committee. The meeting will not end until the committee is chosen. In the “natural oligopoly” game, a faculty member is allowed to leave the meeting as soon as he agrees to serve on the committee. In the “standards” game, everyone must stay in the meeting until the whole committee is selected. Obviously, there is much less incentive to concede quickly in the second game.

9In our interpretation of this as a war of attrition for the prizes of being among the non-supporters of a successful bill, individual Democrats’ costs of holding out included the private costs of enduring pressure from the Administration, and the public costs, borne by all the Democrats, of delaying passage of the bill. The delay increased public frustration with the political process, delayed the bill’s benefits, increased the probability of the bill failing (perhaps through the President giving up on it) and left the Democrats less time to work on the rest of their agenda.

Of course, we are abstracting away from many important features of the problem such as coalition-formation, vote-buying, and bargaining in which the legislators can actually affect the details of the bill. For an excellent survey of the rent-seeking literature, which encompasses some of the collective aspects, see Nitzan (1994).

10The war of attrition has also been used to describe labor strikes (see, e.g. Kennan and Wilson (1989)), litigation, and biological competition (see, e.g. Maynard Smith (1974), and Riley (1980)), and the process of agreement to macroeconomic stabilizations (see, e.g.

Alesina and Drazen (1991) and Casella and Eichengreen (1990)). The classic reference on industrial competition is Fudenberg and Tirole (1986). For a more general survey of rent seeking see Nitzan (1994).

The natural oligopoly case yields a striking result: K − 1 firms will exit immediately, leaving only N + 1, or one too many firms to battle for the N prizes.^{11} To understand the result, imagine that when K > 1 exits are still required for the game to end, a player is within ε of his planned dropout time. Then the player’s cost of waiting as planned is of order ε, but his benefit is of order ε^{K} since only when K other players are within ε of giving up will he ultimately win. So for small ε he will prefer to quit now rather then wait, but in this case he should of course have quit ε earlier, and so on. So only when K = 1 is delay possible. This result helps explain why so many wars of attrition, like Kodak vs. Polaroid in instant photography and Microsoft vs. Netscape in web browsers, quickly devolved into two-horse races.

In the standards version of the game, in which all players pay until the game ends, even if they have already conceded, the result is perhaps equally surprising: players’ strategies are independent of K and of other players’ dropout behaviour. Why does this kind of strategic independence arise? Because, as before, when there are still K > 1 too many firms, a player within ε of his planned exit knows he has no chance (to first order) of winning. So since in this case quitting early does not affect the rate at which the firm pays costs, the firm would quit early if he thereby shortened the expected length of the whole game. Only if the firm’s exit decision has no effect on the length of the whole game will it be willing to exit at the “correct” equilibrium time. So no firm can either affect, or be affected by, any other firm’s dropout behaviour.

In our general model, which encompasses both the natural oligopoly and the standards versions as special cases, each player’s value of surviving in the market is private information to that player. However we always get perfect sorting. Thus even in the one too many limit in which the field is immediately sorted down to N + 1 players, it is the K − 1 weakest players that leave in zero time.

11One example of this game is that Avinash Dixit every year offers a $20 prize to the student who continues clapping the longest at the end of his game theory course. Our analysis shows that if they have understood the material, no more than two students should continue applauding after the time when everyone would otherwise have stopped.

Section 1 presents the model. Section 2 analyses the general case. Sections 3 and 4 discuss the one too many result and strategic independence respectively. Section 5 illustrates the analysis with an example inspired by the 1993 budget battle, and Section 6 concludes. Formal proofs are collected in the Appendix.

1 The model

There are N + K risk-neutral firms in a market. As long as a firm continues to compete, it pays a cost that is normalized to 1 per unit time. If it exits, it subsequently pays a cost c > 0 per unit time until a total of K firms have quit.^{12} If a firm i is one of the N firms which survives, then it wins a prize of v^{i} which is private information to firm i at the beginning of the game.^{13} The values v^{i} are drawn independently from the distribution F (v), with F (\underline{V}) = 0, F (\overline{V}) = 1, \underline{V} > 0 and \overline{V} < ∞. We assume F (·) has a strictly positive finite derivative everywhere. It will be convenient to write h(v) for the “hazard rate” \frac{f(v)}{1−F (v)}. We also write v_{j} for the j^{th} highest of the N + K firms’ values, and E(v_{j}) for the expectation of this value. We restrict attention to symmetric equilibria.

At any point of the game let N + k be the remaining number of firms (so k more firms must exit before the game finishes), let \underline{v} be the lowest possible remaining type conditional on all other firms having thus far followed (symmetric) equilibrium strategies, write T (v; \underline{v}, k) for the additional amount of time a still-surviving firm of type v will wait before exiting if none of the other remaining N + k firms exits beforehand, and P (v; \underline{v}, k) for the firm’s probability of being among the N ultimate survivors.

12Typically we expect c to be no more than 1, but note 30 suggets a context in which it might exceed 1. Another example in which c would exceed 1 is a “contributions” game in which N people must each pay for one stage of a building project before it yields any benefits, and discounting means earlier contributions cost more than later ones.

13If flow costs differ among firms, we can simply reinterpret v^{i} as the ratio for player i of the prize value to the flow cost, since this ratio is all that matters to any firm. So all our results will still go through. (Units for measuring costs are of course then different for different firms so that the flow rate of costs is measured as 1 per unit time for each.)

2 The general solution

Lemma 1: In any equilibrium, for all \underline{v} and all k, T (v; \underline{v}, k) is strictly in-

creasing in v and P (v; \underline{v}, k) equals the probability that v is one of the N

highest values conditional on N + k − 1 other firms’ values exceeding \underline{v}.^{14}

Lemma 1 follows because higher-valued firms exit later in a symmetric

equilibrium.

Lemma 2: There is at most one equilibrium of the game.

The reason for Lemma 2 is that the difference between the expected sur-

pluses of any two types is uniquely determined by standard incentive com-

patibility arguments.^{15} But, since any type’s probability of winning a prize

is fixed by Lemma 1, the difference between the two types’ waiting costs

is therefore also uniquely determined. However, if there were two different

equilibria specifying different quitting times T (v; \underline{v}, k), these two equilibria

would yield different differences between types’ waiting costs, for at least one

pair of types.^{16}

Lemma 3:^{17} The unique symmetric perfect Bayesian equilibrium^{18} of the

subgame in which just one more exit is required to end the game is defined by

T (v; \underline{v}, 1) = ∫ v ; \underline{v} Nxh(x)dx  (1)

14So P (v; \underline{v}, k) = ∑_{j=k}^{N+k−1} \frac{(N+k−1)!}{(N+k−1−j)!j!} (\frac{F (v)−F (\underline{v})}{1−F (\underline{v})})^{j} (\frac{1−F (v)}{1−F (\underline{v})})^{N+k−1−j}

15The absolute level of a player’s surplus cannot be determined prior to determining the actual equilibrium because, in contrast to many problems in which the bottom type’s surplus is fixed at zero, in our problem the bottom type receives negative surplus for c > 0.

16This is easy to see if k = 1 (i.e. when the game ends after one more quit). So the k = 1 subgame is unique. But then if k = 2, waiting costs are fixed after one more quit, so two different functions T (v; \underline{v}, 2) would yield different differences in total waiting costs for some pair of types, so the k = 2 subgame is also unique. And so on.

17This result can also be found in Bliss and Nalebuff (1984), Nalebuff (1982), and elsewhere.

18For this (k = 1) case this is also the unique symmetric Nash equilibrium, since each firm knows that its decision to exit is only relevant in the case in which no other firm has previously exited, so the game is strategically equivalent to a static game in which firms simultaneously choose exit times.

The intuition is straightforward: at each moment the marginal firm with type v faces the prospect of paying an extra T′(v; \underline{v}, 1)dv to outlast any firms with types between v and v+dv, and equates these costs to the value of being a winner, v, times the probability, \frac{Nf(v)dv}{1 − F (v)} = Nh(v)dv, that one of the other N remaining firms will in fact be revealed to have a type below v + dv. So T′(v; \underline{v}, 1) = Nvh(v). Furthermore T (\underline{v}; \underline{v}, 1) = 0, since a player of type \underline{v} will never win and so exits immediately. So T (v; \underline{v}, 1) = 0 + ∫ v ; \underline{v} T′(x; \underline{v}, 1)dx =

∫ v ; \underline{v} Nxh(x)dx.

We can now state our main result.

Proposition: The unique symmetric perfect Bayesian equilibrium of the Generalized War of Attrition is defined by

T (v; \underline{v}, k) = c^{k−1} ∫ v ; \underline{v} Nxh(x)dx  (2)

The intuition is that when k > 1, quitting ε early or late would not, to first order, affect type v’s probability of winning (since only when k other firms are within ε of quitting can v win in the next ε). But quitting does slow down the rate at which v pays costs to fraction c of the previous rate, so for v to be indifferent about quitting, it must also slow down other players’ rates of quitting by the same fraction c.^{19} That is, T′(v; \underline{v}, k) = cT′(v; \underline{v}, k − 1), hence also T′(v; \underline{v}, k) = c^{k−1}T′(v; \underline{v}, 1) = c^{k−1}Nvh(v).

So, for example, if N = 1, K = 3 and c = \frac{1}{2}, the equilibrium goes through types four times as fast as in the two firm game (N = K = 1) until one firm drops out, then twice as fast as the two firm game until a second firm drops out, and then finally at the speed of the two firm game until the final exit.

Notice that a feature of the equilibrium is that the K − 1 lowest-valued firms are actually indifferent about staying past their equilibrium dropout points; each would be willing to delay until K −1 others have quit (assuming each thought the others were following the equilibrium strategies). Of course, if any one of these firms were to delay its departure until K − 1 others had left, that would speed the game and benefit everyone else.^{20}

19Of course, this argument is not complete since it only shows other players slow down to fraction c on average.

Note also that, by contrast, the highest-valued losing firm (the only loser in the standard N + 1 firm model) would hurt everyone else by delaying its exit, so the equilibrium length of the game is non-monotonic in players’ valuations. For example, a game with two “tough” players and one “weak” player competing for one prize takes longer than either a game with three tough players or a game with one tough player and two weak players.

Expected Time Between Exits

The expected time between successive departures increases in later stages for three separate reasons. First, there are fewer players who might leave (N + k falls). Second, the remaining players are stronger (E(v_{N+k}) rises as k falls). And third, each exit must slow the game (c^{k−1} rises as k falls) in order to make the next firm which drops out indifferent between paying the full costs of remaining in the game a little longer or paying the lower costs per period of being out. The Corollary to our Proposition demonstrates exactly these features: Corollary: The expected time taken to reduce from N + k firms to N + k − 1 firms is

Nc^{k−1} \frac{E(v_{N+k})}{N + k}  (3)

The Appendix offers a purely algebraic proof of the Corollary. However, an approach that is more economic (and economical) is to consider a game in which, after all but j players have been revealed as having values above v_{j+1}, as in our problem, the remaining players fight a standard one-stage war of attrition for j − 1 prizes. Since this game requires just one more exit, lemma 3 tells us that the time until the lowest of the j remaining firms (with value v_{j}) quits is ∫_{v_{j+1}}^{v_{j}}(j −1)xh(x)dx. But by the Revenue Equivalence Theorem the expected costs per player must be the same as in an English auction, in which (j −1) players win at price v_{j}, that is, E{(j −1)v_{j}/j}.^{21} So, E \{∫_{v_{j+1}}^{v_{j}} xh(x)dx\} = \frac{E(v_{j})}{j}. Now in our problem the expected time between the exits of the (j + 1)^{st} and j^{th} highest-value firms (who have actual values v_{j+1} and v_{j}) is, from (2), E {c^{j−(N+1)} ∫_{v_{j+1}}^{v_{j}} Nxh(x)dx} , so substitution yields the corollary.

20Of course, if c > 1 each firm that leaves speeds up the game, so leaving late hurts others.

Expected Length of the Game

Simple summation of (3) yields Corollary: The expected length of the Generalized War of Attrition is

N ∑_{j=N+1}^{N+K} c^{j−(N+1)} \frac{E(v_{j})}{j}  (4)

Firms’ Costs Varying with k

It is easy to extend the model to allow firms’ costs to be a function of k. (For example, in an oligopoly context losses are probably increasing in k.) If costs are ℓ_{k} times as great as in our model when k more firms are required to exit, then equilibrium requires that types leave ℓ_{k} times as fast at any point of time. Thus the total costs firms incur in the war of attrition are independent of ℓ_{k}.

Discounting

It is also easy to see that discounting would have no effect on how firms play the game at any moment of time, since discounting is just equivalent to there being some exogenous flow of probability that the game will end and firms will stop accruing further costs or benefits. So our results and our formulae for T (v; \underline{v}, k) are unchanged by discounting, but discounting makes the costs of the war of attrition even greater relative to the discounted value of the prizes.

21We can use the Revenue Equivalence Theorem because in both a one-stage war of attrition and an English auction a player who quits immediately receives an expected surplus of zero.

Deadlines

In many contexts there is a deadline at which the game ends and no-one

wins a prize.^{22} Since this corresponds to infinitely heavy discounting taking

place at the moment of the deadline, this too has no effect on how the game

is played prior to the deadline.

3 The special case c = 0: “ One Too Many”

In the limit as c approaches 0, firms drop out arbitrarily fast until only N +1

remain. That is, if N firms can be profitable in a market and dropouts pay

no costs after exiting, then competition in the symmetric equilibrium will

immediately shake out to just one too many firms to be profitable.^{23}

For example, when there is just one winner, competition effectively re-

veals the third-highest value, that is, v_{3}, immediately, and then yields a

conventional two firm game beginning with \underline{v} = v_{3}.

An alternative way of deriving this result that should appeal to auction

theorists is to consider the expected total costs paid by the remaining two

firms after the buyer with the third-highest value drops out. The Revenue

Equivalence Theorem tells us that these costs must be the same as the ex-

pected costs in a second-price auction between these firms, namely the ex-

pectation of the second-highest value, v_{2}.^{24} Compare this with the expected

22For example, the government imposes a standard that is no-one’s preference, or firms go their separate ways and choose different standards, or the industry dies. Of course there are other possible models of deadlines e.g. winners are chosen randomly (e.g. by whips in a voting context), or everyone pays a cost at the deadline (e.g. the bill fails to pass which is everyone’s worst outcome).

23In an open-loop equilibrium (i.e., when firms choose an exit time at the start of the game that cannot be revised based on when other firms quit) the one too many result does not arise; see Krishna and Morgan (1997) who analyse an open-loop c = 0 model. Hillman and Riley (1989) analyse an all-pay auction without private information but with asymmetric bidders and show that just two bidders make positive bids. However, this “twoness” result does not survive if the bidders are symmetric (as ours are); in this case there is a symmetric equilibrium in which all bidders make positive bids (see also Baye et al (1996)). Nor does Hillman and Riley’s “twoness” result survive in a “second-price all-pay” auction, i.e. an all-pay auction except that the winner pays only the second bid (as in our war of attrition), since this is equivalent to the open-loop c=0 model analysed by Krishna and Morgan.

24See Myerson (1981) and Riley and Samuelson (1981) for the earliest statements of the Revenue Equivalence Theorem. Our 1994 paper, Bulow and Klemperer (1994), states and

total costs paid by all the firms in the initial game with K eventual losers. Again by Revenue Equivalence with the second-price auction, total expected costs must be the expectation of v_{2} in the initial game. So the expected costs paid to get from the initial game to the subgame with two firms remaining must be zero.^{25}

To understand the result observe that if there were positive delay while K > 1 exits were still required, then a firm that quit ε earlier than it had originally planned would save ε in waiting costs but would reduce its probability of winning by an amount of order ε^{K}. So all firms would drop out at least a little earlier than planned, so firms must in fact quit without delay until only a single firm remains in excess of the number who can ultimately survive.

Fudenberg and Kreps (1987) and Haigh and Cannings (1989) have already considered the case c = 0 in the special case in which all firms’ values are equal (i.e., every firm i has value v^{i} = \underline{V} = \overline{V}), so there is no private information.^{26} Then the symmetric equilibrium (again in continuous time) is in mixed strategies, and all firms mix across all possible dropout times.^{27} In this case, if a firm survives to be one of the final N + 1 firms in the market, its expected future payoff is zero (since it is indifferent to dropping out immediately). But it can also earn zero by dropping out at the beginning of the entire game. Therefore, firms will only be willing to wait to become one of the final N + 1 firms if the cost of waiting is zero—that is, the time that it takes to reduce the field to N + 1 must be zero regardless of K.

applies the theorem for a setting which, like this one, has multiple objects that are sold in a dynamic game.

25The reason this logic only holds when c → 0 is that this assures that the expected surplus of a firm with type \underline{v} is zero, since the firm can exit immediately at no further cost. This in turn guarantees that the expected surplus of a firm with type v equals ∫ v ; \underline{v} P (x; \underline{v}, k)dx (see equation (8) in the appendix), and hence that the expected total costs paid by all firms (which must equal the sum of the expected gross income to the survivors less the sum of firms’ expected surpluses) are the same regardless of whether there is a second-price auction or a symmetric war of attrition in any subgame. If c > 0, then the expected surplus of a firm with the lowest possible type is negative, so the war of attrition will be more costly to the firms, in expectation, than a second-price auction.

26Haigh and Cannings consider exactly this game. Fudenberg and Kreps’ model is more complex, but the situation their weak entrants face has essentially these features (see their section 5).

27See Fudenberg and Tirole (1991, p230-232) for discussion of how the mixed strategy equilibrium of the two-player war of attrition with complete information corresponds to the equilibria of wars of attrition with incomplete information in which every type plays a (different) pure strategy.

Note that, strictly speaking, the game has no symmetric equilibrium actually at the limit c = 0. Our argument has made clear that there cannot be an equilibrium in which the types separate with all except the lowest type waiting a strictly positive length of time. But nor can there be positive probability of any firm quitting in zero time, since in symmetric equilibrium this would imply positive probability of all firms quitting in zero time, so every firm would do better to wait a little (see Lemma 1).^{28}

4 The special case c = 1: “ Strategic Independence”

Now consider the special case in which all firms pay full costs until the game is resolved. This is the polar opposite of the previous case, and can be thought of as the standards case, where all firms lose until a standard is established, with losses independent of whether a firm is one of the remaining competitors for establishing the standard.

When c = 1, the Proposition yields that types leave at the rate

\frac{1}{T′(v; \underline{v}, k)} = \frac{1}{Nvh(v)}

when the marginal remaining type is v, so we have “strategic independence”. That is, each firm chooses the same dropout time as if it were in a game with just N +1 firms and N prizes, independent of the actual number of remaining firms. Having chosen its dropout time at the beginning of the game, the firm then sticks with it.

The intuition is that because a firm’s flow costs are unaffected by dropping out before the end of the game, and its probability of winning is also unaffected (to first order) by small changes in its exit time when K > 1 exits are still required to end the game, the firm’s exit decision cannot affect the length of the game. So other firms’ decisions are unaffected by this firm’s actions.

28Haigh and Cannings get around the problem of the absence of a symmetric equilibrium in their model by imposing a series of instantaneous randomizations to eliminate k − 1 bidders in zero time (and Fudenberg and Kreps take a similar approach). This seems very natural in their special case in which all players have identical values. To the best of our knowledge our paper is the first to allow c > 0, and so to interpret the c = 0 case as the limit as c→ 0.

As for the “one too many” case, it may help in understanding this result to consider the mixed strategy equilibrium of the limiting case of our game in which all firms’ values are known to be equal. In this case firms must be indifferent to dropping out at any time prior to the end of the game. Thus a firm must be indifferent between dropping out now, when more than N + 1 firms remain, or waiting until exactly N + 1 remain and then dropping out immediately, or dropping out at any time in between. Since in any of these cases the firm does not win and pays costs proportional to the length of the game, the length of the game must be independent of the firm’s choice. So the dropout decisions of the first K−1 firms to exit do not affect the decisions of the remaining firms.

The length of the “strategic independence” game is strictly a function of the N + 1^{st} highest value, but the larger K is the longer the game will take in expectation, because the expected value of the N + 1^{st} highest value rises as N + K rises.

Both the “one too many” and the “strategic independence” games take equally long to reduce from N + 1 firms down to N. The difference is that in the “one too many” game we get down to N+1 firms immediately, and so only have to incur costs running through the types between the N + 2^{nd} highest value and N + 1^{st} highest value. However, with “strategic independence” all types must be run through in real time, and the amount of time required for the industry to shake down from N + K firms to N + 1 may far exceed the time needed to get from N + 1 to N.

5 An example

We illustrate our model with an example inspired by the 1993 budget battle. Assume 51 senators would each like to see a bill passed but would prefer not to have to vote for it. Each senator has a value independently drawn from a uniform distribution on [0,\overline{V}] of being the one person who need not vote for the bill. So N = 1 and K = 50. We normalise units of time so that the

costs of holding out are 1 per unit time for those who have not yet pledged

support.

In the “strategic independence” case all 51 senators suffer political costs

equally until the impasse is resolved, whether or not they have themselves

given in. In this case c = 1, so using (4) the expected delay before passage of

the bill is ≈2.55 \overline{V} .^{29} So even the “winner” suffers costs that are on average

more than two and one half times as great as his prize!^{30} Obviously players

should do everything they possibly can to change such games.^{31}

At the other extreme, consider the “one too many” case in which a sen-

ator’s only costs are his personal costs of withstanding administration pres-

sure, and these costs stop as soon as he knuckles under. In this case, as

we have seen, 49 senators give in to the administration immediately, while

the two with the highest values hold out in a standard two-player war of

attrition. Here c = 0, so using (4) the total expected time is just half of

the expected value of the lower of the holdouts, \frac{1}{2}E(v_{2}), that is, since F (·) is

uniform, \frac{25}{52} \overline{V} .^{32},^{33}

29For the uniform distribution E(v_{j}) = (1 − \frac{j}{N+K+1}) \overline{V} , so (4) implies the ex-

pected delay is N\overline{V} ∑_{N+1}^{N+K} (\frac{1}{j} − \frac{1}{N+K+1})which with N = 1 and K = 50 yields

\overline{V} (−\frac{50}{52} + ∑_{j=2}^{51} \frac{1}{j}) ≈ \overline{V} (−2 + ∑_{j=1}^{53} \frac{1}{j}) ≈ \overline{V} (−2 + log 53 + γ)in which γ (≈ .58) is the

Euler number.

30Of course, this does not mean that a player should refuse to play. It is common knowledge that each player anticipates negative surplus relative to the bill passing immediately with his vote, but legislators may still obtain positive surplus relative to the bill not passing at all.

In fact, the legislators would be in an even worse game than this if c > 1. For example, if pledging one’s vote increases the lobbying pressure and hostility one faces from those opposed to the bill, then costs are largest for those who have already pledged.

31This may help explain the institution of whips, whose job it is to determine the allocation of prizes (that is, who should be permitted not to vote for a particular measure) without recourse to a war of attrition. Whips will not necessarily select the highest valuers of the prizes but even uninformed randomisation is highly desirable relative to these games. Whips seem to be more effective in resolving smaller issues than larger ones, such as the budget bill, for which it is harder to persuade losers that they will be compensated on future issues.

32We can also obtain this result directly without need of (4) by using the Revenue Equivalence Theorem which says that the expected total costs incurred (that is, twice the expected time) must be the same as in an English auction, that is, E(v_{2}) = \frac{50}{52} \overline{V}. (The Revenue Equivalence Theorem applies here because a player who quits immediately gets zero surplus in this case.)

33With c = 0, the total resources used are E(v_{2}) while the expected value of the prize is

In the “one too many” case, of course, all the time is spent waiting for the last vote, but observe that even in the “strategic independence” case, the first few votes come in relatively quickly (the first 10 votes take less than 1% of the total time on average) while the last few votes take much longer (the last 4 votes take almost half the total time in expectation). The typical case will lie between these extremes. Thus our model both explains why political decision making can sometimes take so long, and why, even when agreements seem close to complete, the hunt for the last few votes can often seem so excruciatingly slow.^{34}

6 Conclusion

We study wars of attrition in which two or more players must exit. Except in the final stage, a player’s departure will not end the game, and a player may continue to incur at least some costs even after he has conceded. Therefore, except in the final stage, by the time a player exits he knows a small delay in conceding will not allow him to win, because it is so unlikely that two or more others will exit before him. So the player becomes solely interested in minimizing his costs, and in equilibrium a small change in exit strategy must have no effect on his expected costs.

If costs are as high for those who have already conceded as for those who continue to fight, then there is no incentive to drop out early. For a player to be satisfied with his equilibrium exit time, his departure must neither speed nor slow the ultimate resolution of the game. So each player’s exit behavior is unaffected by the number of other competitors and their actions. We call this “strategic independence.” Examples where this may occur are battles over standard setting and building voting majorities.

If a player does not pay any costs after he has conceded, as in a natural monopoly game, the market will immediately and efficiently sort down to the final stage. That is, in equilibrium we should never observe more than “one too many” firms competing for the prizes.

E(v_{1}), so in the limit in which all players’ values are equal there is complete rent dissipation independent of the number of competitors, just as in rent-seeking models such as Hillman and Samet (1987) who analyse an all-pay auction for a prize that is worth the same to all. Of course for larger values of c, and k > 1, expected rent dissipation in our model typically exceeds the expected value of the prize, as in the c = 1 example above. Expected rent dissipation, as a fraction of the value of the prize, is typically increasing in k and is always increasing in c.

34Multilateral international treaties (e.g. GATT) often seem to illustrate this.

Even with strategic independence, departures occur at a faster rate in the early stages, because at the beginning of the game there are more, and weaker, players who might concede. If costs are lower for those who have exited than for those still fighting, so there is an incentive to depart early, this effect becomes even more pronounced. Each exit must slow the game sufficiently to make the next dropout indifferent between paying the full costs of remaining in the game a little longer or paying the lower costs per period of being out. Of course in the limit when players pay no costs after conceding, all but the last departure is instantaneous. So the model explains why rounding up most of the necessary votes for a bill might take very little time, but gathering the last few votes may be time-consuming and costly.

Appendix

We write C(v; \underline{v}, k) for the firm’s expected future delay costs over the whole of the rest of the game (net of delay costs thus far incurred), and S(v; \underline{v}, k) for the firm’s expected future surplus over the whole of the rest of the game (so S(v; ·, ·) ≡ vP (v; ·, ·) − C(v; ·, ·)).

Proof of Lemma 1: A higher-value type of a firm cannot exit before a lowervalue type of the same firm would exit. (If a low type gets the same expected surplus from strategies with two different probabilities of being an ultimate survivor, the high type strictly prefers the high-probability strategy, so the high type cannot choose a strategy with a lower probability of survival than the low type.) Also, at no moment of time does any firm exit with strictly positive probability. (By symmetry, all firms would have strictly positive probability of exit, but then any firm would strictly prefer exiting just after this time to exiting at this time). So T (·; ·, ·) is strictly increasing in v for all \underline{v} and k, and a firm ultimately survives if and only if k or more of the remaining N + k − 1 other current survivors have lower values than it. So

P (v; \underline{v}, k) = ∑_{j=k}^{N+k−1} \frac{(N + k − 1)!}{(N + k − 1 − j)!j!} (\frac{F (v) − F (\underline{v})}{1 − F (\underline{v})})^{j} (\frac{1 − F (v)}{1 − F (\underline{v})})^{N+k−1−j} (5)

□

Proof of Lemma 2:^{35} The proof is by induction. We assume that there is at most one equilibrium of any subgame in which there are N + k − 1 firms left, and show that this implies at most one equilibrium with N + k firms remaining.

Consider the subgame defined by k and \underline{v}. (This is well-defined by Lemma 1). There is no finite period of time in which there is zero probability of exit. (If there was, then a type that was due to exit at the end of this period would do better to exit at the beginning of this period; because there is a unique equilibrium after the next exit, its time cannot affect the subsequent development of the game.) So T (v; \underline{v}, k) is continuous, and

T (\underline{v}; \underline{v}, k) = 0  (6)

so also S(\underline{v}; \underline{v}, k) = −C(\underline{v}; \underline{v}, k).  (7)

Now note that since in equilibrium no type of firm can gain by following any other type’s exit rule,

S(v^{a}; \underline{v}, k) ≥ S(v^{b}; \underline{v}, k) + P (v^{b}; \underline{v}, k)(v^{a} − v^{b})  for all  v^{a}, v^{b} ∈ [\underline{v}, \overline{V}].

35This is the most elegant proof we know. An alternative, but here rather cumbersome, approach is to first show the monotonicity and continuity of T (·; ·, ·) in v and using these show the differentiability of T (v), so that the first-order conditions characterize the equilibrium uniquely. (As in our proof, an inductive argument is required; for arguments along these alternative lines see the Appendix of Gul and Lundholm (1995) or our own working paper (joint with Huang), Bulow et al (1996).)

So S(v; \underline{v}, k) has derivative dS/dv = P (v; \underline{v}, k) and therefore

S(v; \underline{v}, k) = S(\underline{v}; \underline{v}, k) + ∫ v ; \underline{v} P (x; \underline{v}, k)dx  (8)

and, noting (7),

C(v; \underline{v}, k) = C(\underline{v}, \underline{v}, k) + vP (v; \underline{v}, k) − ∫ v ; \underline{v} P (x; \underline{v}, k)dx.  (9)

So (9) and (5) uniquely determine C(v; \underline{v}, k), since C(\underline{v}; \underline{v}, k) equals c times the expected length of the subgame after \underline{v} quits and leaves (N +k −1) firms remaining, and the equilibrium of this subgame is, by assumption, unique.

We can now show that there is at most one equilibrium T (v; v̂, k). Suppose instead that there are two equilibria with T̃(\overline{v}; v̂, k) <T^{≈} (\overline{v}; v̂, k) for some \overline{v}. Then by the continuity of T̃(v; v̂, k) and T^{≈} (v; v̂, k), there exists

\underline{v} ∈ [v̂, \overline{v}) such that T̃(\underline{v}; v̂, k) =T^{≈} (\underline{v}; v̂, k) = τ and T̃(v; v̂, k) <T^{≈} (v; v̂, k)

for all v ∈ (\underline{v}, \overline{v}]. But if T̃(v; v̂, k) and T^{≈} (v; v̂, k) are both equilibria, then T̃(v; \underline{v}, k) = T̃(v; v̂, k) − τ and T^{≈} (v; \underline{v}, k) = T^{≈} (v; v̂, k) − τ must be equilibria of the subgame defined by \underline{v} and k. But then T̃(v; \underline{v}, k) < T^{≈} (v; \underline{v}, k) for all v ∈ (\underline{v}, \overline{v}], so any v ∈ (\underline{v}, \overline{v}] would expect lower waiting costs under T̃(v; \underline{v}.k) than under T^{≈} (v; \underline{v}, k) before the next drop out (whether by this firm or another firm) and the same waiting costs thereafter, since by assumption equilibrium is unique after the next dropout. But this contradicts the fact that C(v; \underline{v}, k) is the same for both equilibria T̃(v; \underline{v}, k) and T^{≈} (v; \underline{v}, k). This completes the inductive step, and so proves the result, since it holds trivially when just N firms remain. □. Proof of Lemma 3: Given that all other firms use this exit rule, the expected future surplus of a type v who behaves as a type v^{∗} is

U(v, v^{∗}) = −(1 − P (v^{∗}; \underline{v}, 1))T (v^{∗}; \underline{v}, 1) + ∫ v^{∗} ; \underline{v} \frac{∂P (x; \underline{v}, 1)}{∂x}(v − T (x; \underline{v}, 1))dx

in which the first and second terms are v’s payoffs from the events that he quits and survives, respectively, P (v^{∗}; \underline{v}, k) is defined by (5) and equals

1−(\frac{1 − F (v^{∗})}{1 − F (\underline{v})})^{N} when k = 1, and \frac{∂P (x; \underline{v}, 1)}{∂x} = \frac{Nf(x)}{1 − F (x)} (\frac{1 − F (x)}{1 − F (\underline{v})})^{N}is

the density with which v wins and the lowest of the other N firms is of type x. Thus (1) satisfies v’s first-order condition

\frac{∂U}{∂v^{∗}} (v, v^{∗}) = 0 ⇒

\begin{matrix}− & (1 − P (v^{∗}; \underline{v}, 1))T′(v^{∗}; \underline{v}, 1) + \frac{∂P (v^{∗}; \underline{v}, 1)}{∂v^{∗}}v \\ = & [− (\frac{1 − F (v^{∗})}{1 − F (\underline{v})})^{N} \{T′(v^{∗}; \underline{v}, 1) − \frac{Nvf(v^{∗})}{1 − F (v^{∗})}\}] = 0 \end{matrix}

at v^{∗} = v. It satisfies the second-order conditions since it implies

sign\frac{∂U}{∂v^{∗}} (v, v^{∗}) = sign(v − v^{∗}).

And it also satisfies the boundary condition, (6), T (\underline{v}; \underline{v}, 1) = 0. □.

Proof of Proposition: Since Lemma 2 has shown that there is at most one equilibrium, it suffices to show that no type, say ṽ, of any player wishes to deviate from the strategy specified in (2), assuming all other players follow the strategies specified in (2):

Assume ṽ stays in beyond the time when (2) requires him to quit. This makes no difference to the costs the firm incurs in waiting for other players to quit, since quitting would reduce its cost per unit time to a fraction c of its pre-exit rate but would also multiply T′(·, ·, ·) by \frac{1}{c} so the density of others’ types that exit per unit time would be c times as great. So type ṽ is indifferent about waiting until k = 1, and if ṽ quits before k = 1 he will have neither gained nor lost from his deviation assuming other players play according to the conjectured equilibrium. But at k = 1 type ṽ will strictly wish to exit rather than stay, since ṽ will now be lower than the marginal type, \underline{v}, who exits immediately in the unique equilibrium of the remaining subgame, and staying beyond this time would lose money in expectation (see Lemma 3).

If instead ṽ quits before the time specified by (2), this would also make no difference to the costs incurred in waiting for other players to quit, since both this firm’s costs and the rate at which the other firms are exiting would be multiplied by c. If by the end of the game (when k = 0) ṽ is lower than the marginal type, \underline{v}, who just exited (assuming equilibrium behaviour) then ṽ’s total costs are unaffected by his deviation. If, however, ṽ > \underline{v} then ṽ would have lost money in expectation by its deviation, since by Lemma 3 it would now prefer to still be in the game (with k = 1) and remain until the time specified by (2).

So ṽ cannot gain by deviating from the strategy specified by (2), and (2) specifies the unique equilibrium. □.

Algebraic Proof of First Corollary: Using (2), the expected time between the exits of the (j + 1)^{st} and j^{th} highest-value firms (who have actual values v_{j+1} and v_{j}) is, E \{c^{j−(N+1)} ∫_{v_{j+1}}^{v_{j}} Nxh(x)dx\} , (in which v_{N+K+1} ≡ \underline{V}). Now,

E ∫ v_{j} ; \underline{V} Nxh(x)dx

= lim_{ε→0} ∫ \overline{V} −ε ; \underline{V} \binom{N + K − 1}{j − 1} (F (v))^{N+K−j}(1 − F (v))^{j−1}(N + K)f(v) ∫ v ; \underline{V} Nxh(x)dxdv

which, integrating by parts,

=lim_{ε→0} \{[[ ∑_{i=N+K+1−j}^{N+K} \binom{N + K}{i} (F (v))^{i}(1 − F (v))^{N+K−i}] ∫ v ; \underline{V} Nxh(x)dx]\overline{V} −ε ; \underline{V}

− ∫ \overline{V} −ε ; \underline{V} [ ∑_{i=N+K+1−j}^{N+K} \binom{N + K}{i} (F (v))^{i}(1 − F (v))^{N+K−i}] Nvh(v)dv\} .^{36}

So

E ∫_{v_{j+1}}^{v_{j}} Nxh(x)dx

= E ∫ v_{j} ; \underline{V} Nxh(x)dx − E ∫ v_{j+1} ; \underline{V} Nxh(x)dx

=lim_{ε→0} \{∫ \overline{V} −ε ; \underline{V} \binom{N + K}{N + K − j} (F (v))^{N+K−j}(1 − F (v))^{j}Nvh(v)dv+

[\binom{N + K}{N + K − j} (F (v))^{N+K−j}(1 − F (v))^{j} ∫ v ; \underline{V} Nxh(x)dx]\overline{V} −ε ; \underline{V}\}

which after noting that the second term is zero,^{37} and substituting h(v) ≡ \frac{f(v)}{1−F (v)} and \binom{N+K}{N+K−j} = \frac{N+K}{j} \binom{N+K−1}{j−1}into the first term,

= ∫ \overline{V} ; \underline{V} \binom{N + K − 1}{j − 1} (F (v))^{N+K−j}(1 − F (v))^{j−1}(N + K)f(v)\frac{N}{j} dv,

= \frac{N}{j} E(v_{j}),

which yields the result. □.

36We are being careful to take lim_{ε→0} ∫^{\overline{V} −ε} since lim_{ε→0} ∫^{\overline{V} −ε} Nxh(x)dx may be ∞.

37To show the second term is zero, it suffices to show that

lim_{ε→0} [1 − F (\overline{V} − ε)] ∫ \overline{V} −ε ; \underline{V} Nxh(x)dx = 0.

A careful proof of this is as follows: define

g_{ε}(x) = \{ \begin{matrix}[1 − F (\overline{V} − ε)]Nxh(x) & for & \underline{V} < x < \overline{V} − ε \\ 0 & for & \overline{V} − ε < x < \overline{V} . \end{matrix}

So [1 − F (\overline{V} − ε)] ∫ \overline{V} −ε ; \underline{V} Nxh(x)dx = ∫ \overline{V} ; \underline{V} g_{ε}(x). Also note that g_{ε}(x) ≤ Nxf(x) = G(x) for all x ∈ [\underline{V} , \overline{V}], as \frac{1−F (\overline{V} −ε)}{1−F (x)} ≤ 1 for 0< x < \overline{V} − ε. Now note that for all x ∈ [\underline{V} , \overline{V}] we have lim_{ε→0} g_{ε}(x) = 0. Finally note that g_{ε} ≤ g′_{ε} for ε < ε′. This implies that for any δ > 0 we can find ε_{0} > 0, such that g_{ε}(x) < δ for all 0 < x < \overline{V} − δ and all ε < ε_{0}. Therefore we can deduce 0 < ∫ \overline{V} ; \underline{V} g_{ε}(x) < δ\overline{V} + ∫ \overline{V} ; \underline{V} −δ G(x). As we can get the right-hand side as small as we desire, we obtain finally

lim_{ε→0} ∫ \overline{V} ; \underline{V} g_{ε}(x) = 0.

References

Alesina, Alberto and Drazen, Allan, “Why are Stabilizations Delayed?” American Economic Review, December 1991, 81, pp. 1170-88.

Baye, Michael R., Kovenock, Dan and de Vries, Casper, G, “The All-Pay Auction with Complete Information,” Economic Theory, Spring 1996, 8, pp. 291-305.

Bliss, Christopher and Nalebuff, Barry, “Dragon-Slaying and Ballroom Dancing: The Private Supply of a Public Good”, Journal of Public Economics, 1984, 25, pp.1-12.

Bulow, Jeremy and Klemperer, Paul, “Rational Frenzies and Crashes,” Journal of Political Economy, February 1994, 102 (1), pp. 1-23.

Bulow, Jeremy and Klemperer, Paul, “The Generalized War of Attrition,” Stanford University and University of Oxford Working Paper, 1996.

Bulow, Jeremy, Huang, Ming, and Klemperer, Paul, “Toeholds and Takeovers”, Stanford University and University of Oxford Working Paper, 1996.

Casella, Alessandra and Eichengreen, Barry, “Can Foreign Aid Accelerate Stabilisation?”, The Economic Journal, May 1996, 106, pp. 605-619.

David, Paul A. and Monroe, Hunter K., “Standards Development Strategies Under Incomplete Information - Isn’t the “Battle of the Sexes” Really a Revelation Game?” All Souls College and International Monetary Fund, Working Paper, December 1994.

Farrell, Joseph, “Choosing the Rules for Formal Standardization”, University of California, Berkeley, Working Paper, August 1993.

Farrell, Joseph and Saloner, Garth, “Coordination through Committees and Markets”, RAND Journal of Economics, Summer 1988, 19(2), pp. 235-252.

Fudenberg, Drew and Tirole, Jean, “A Theory of Exit in Duopoly”, Econometrica, July 1986, 54(4) pp.943-960.

Fudenberg, Drew and Tirole, Jean, Game Theory, M.I.T. Press, 1991.

Fudenberg, Drew and Kreps, David M., “Reputation in the Simultaneous Play of Multiple Opponents”, Review of Economic Studies, 1987, 54, pp. 541-568.

Gul, Faruk and Lundholm, Russell, “Endogenous Timing and the Clustering of Agents’ Decisions”, Journal of Political Economy, October 1995, 103(5), pp. 1039-1066.

Haigh, John and Cannings, Chris, “The n-Person War of Attrition”, Acta Applicandae Mathematicae, 1989, 14, pp. 59-74.

Hillman, Arye L. and Riley, John G., “Politically Contestable Rents and Transfers”, Economics and Politics, Spring 1989, 1, pp.17-39.

Hillman, Arye L. and Samet, Dov “Dissipation of Contestable Rents by Small Numbers of Contenders” Public Choice, 1987, 54, pp. 63-82.

Kennan, John and Wilson, Robert, “Strategic Bargaining Models and Interpretation of Strike Date”, Journal of Applied Econometrics, December 1989, 4 pp. S87-S130.

Krishna, Vijay and Morgan, John, “An Analysis of the War of Attrition and the All-Pay Auction”, Journal of Economic Theory, 1997, 72, pp. 343-362.

Maynard Smith, John, “The Theory of Games and the Evolution of Animal Conflicts,” Journal of Theoretical Biology, 1974, 47, pp. 209-???.

Myerson, Roger B., “Optimal Auction Design,” Mathematics of Operations Research, February 1981, 6(1), pp. 58-73. Nalebuff, Barry, “Prizes and Incentives,” D.Phil thesis, University of Oxford, 1982. Nitzan, Shmuel, “Modelling Rent-Seeking Contests,” European Journal of Political Economy, 1994, 10, pp. 41-60. Riley, John G., “Strong Evolutionary Equilibrium and The War of Attrition,” Journal of Theoretical Biology, 1980, 82, pp. 383-400. Riley, John G. and Samuelson, William F., “Optimal Auctions,” American Economic Review, June 1981, 71(3), pp. 381-92.