# the_dollar_auction_with_spiteful_players__d7788101.pdf

The Dollar Auction with Spiteful Players

Marcin Waniek University of Warsaw vua@mimuw.edu.pl

Long Tran-Thanh University of Southampton ltt08r@ecs.soton.ac.uk

Tomasz P. Michalak University of Oxford & University of Warsaw tomasz.michalak@cs.ox.ac.uk

Nicholas R. Jennings Imperial College London n.jennings@imperial.ac.uk

The dollar auction is an auction model used to analyse the dynamics of conflict escalation. In this paper, we analyse the course of an auction when participating players are spiteful, i.e., they are motivated not only by their own profit, but also by the desire to hurt the opponent. We investigate this model for the complete information setting, both for the standard scenario and for the situation where auction starts with nonzero bids. Our results give us insight into the possible effects of meanness onto conflict escalation.

Introduction More often than not, conflict situations require all the opposing parties to commit considerable resources which are then unrecoverable for those who were unlucky to win the stake. Such sunk costs occur, for instance, when lobbyist compete for a public contract (Fang 2002), oligopolists engage in the R&D race (Dasgupta 1986), or military powers engage in the arm race (Mahnken et al. 2016). When the conflict progresses the resources of all parties deplete but it is typically only the winner who is able to recover them, and this sometimes only partially. Shubik (1971) proposed a simple yet powerful model to study such conflict situations. In his so-called dollar auction, two bidders compete for a dollar bill. Similarly to an English auction, the highest bidder wins the prize, but, unlike in the English auction, both the winner and the loser have to pay their bids to the auctioneer. Is it not then better not to participate in the above all-pay auction and to avoid potential conflict situations? Unfortunately, while such an approach should certainly be given a serious consideration, it is not always possible to escape from conflicts. In particular, the possibility that a player may refrain from bidding creates an incentive for the other player to bid and to become a winner at a very low cost. For instance, if no other competitor invest in R&D, an oligopolistic company has an incentive to make a small investment and dominate the market. However, since such a situation can be life-threatening, the competitors have no choice but to bid and the conflict escalations begins. To illustrate this point, let us assume that the auction has started with player 1 bidding $.05, and player 2 raising the

Copyright c 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

price to $.10. Player 1 faces the following dilemma: withdraw from the auction and lose $.05 with certainty, or increase the bid to $.15 with the hope of gaining $.85. Since the same reasoning holds at any stage during the auction, the bidding may continue well past the bill of $1.00 to be won. While past this point the bidders can only seek to minimize losses, they are still incentivized to increase their bids rather than drop out and lose everything. Indeed, in experiments with the dollar auction a dollar bill is sold for considerably more than a dollar (Kagel and Levin 2008). This paradox of escalation (Shubik 1971) can be explained by that a rational strategy for the dollar auction is, unfortunately, far from obvious. Matter-of-factly, the optimal solution remained unknown for fifteen years after the publication of Shubik s original work. A solution was eventually given by O Neill (1986) who proved that, assuming pure strategies and finite budgets of players, there exists the unique first bid (smaller than a dollar) that guarantees winning the dollar. The exact amount of such a golden bid is a non-trivial function of the stake, the budgets, and the minimum allowable increment. O Neill s result implies that, given his assumptions, the conflict in the dollar auction should not escalate: there should be always a single winner (a player who has a chance to move first). Hence, the escalation observed in real-life experiments is due to some factors not present in the model. Given this, O Neill s results were reconsidered by Leininger (1989) who showed that the escalation occurs when we allow for mixed strategies.1 Next, Demange (1992) proved the same if there is some uncertainty about the strength of the players. Similar concept to the dollar auction is the war of attrition (Smith 1982; Bishop and Cannings 1978; Krishna and Morgan 1997), although most war of attrition models assume that each player makes only one move. In the dollar auction players make their moves sequentially, which allows for studying conflict escalation. As for experimental research, Dechenaux et al. (2015) offer a survey of such literature on contests, all-pay auctions, and tournaments. In this paper, we reconsider O Neill s results in pure equilibria from a different perspective. Following recent liter-

1We note that the result very similar to Leininger (1989) were obtained more recently by Dekel (2007).

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

ature on spiteful bidders (Brandt, Sandholm, and Shoham 2005; Sharma and Sandholm 2010; Tang and Sandholm 2012), we ask the question whether the escalation in the dollar auction may actually be caused by the meanness of the participants who are happy to lose some of the invested resources as long as the opposing party also does so. In other words, do we allow ourselves to be dragged along to the abyss because we know that we will not go there alone? Reagan s policy to accelerate the USA-USSR arms race can be seen as the prime example of such a situation. It is widely believed that it was a blunt move aimed at winning the Cold War by destabilizing Soviet economy that was not flexible enough to tackle the technological challenge (Wirls 2010). Similarly, the recent policy of Saudi Arabia of excessive oil production is aimed to hurt major market competitors. In both cases, an important element of one player utility was the other player disutility the phenomenon modelled in the literature as the spiteful utility function. Previous results on spite in the dollar auction (Waniek et al. 2015) indicate that it can lead to conflict escalations. However, those results were obtained only for a restrictive setting in which a spiteful player challenged a non-spiteful one, and the non-spiteful player did not suspect the meanness of his opponent, meaning that she followed the strategy proposed by O Neill (1986). In other words, only one player behaved strategically. In what follows, we extend the setting of Waniek et al. (2015) by analysing the dollar auction where both players act strategically and can have any values of spite coefficient. In particular, we consider the complete knowledge case, when both players know each other spite coefficients. Furthermore, we extend the classic analysis by considering not only the dollar auctions starting from the very beginning (when bids of both players are (0, 0)) but also auctions that start in any state. This corresponds to the situations when players face the conflict escalation situation but they were not the ones who started it, e.g., new governments and the on-going arms race. Our objective here is to identify the set of equilibrium states (x, y) from which if the auction is started, the optimal decision would be to stop increasing the bid. These equilibria represent the states from where further conflict escalation is not expected.

Preliminaries

In this section, we formally describe the dollar auction model, the concept of spitefulness and regret, as well as different types of spiteful players.

The Dollar Auction

Two players, N = {1, 2}, participate in an auction in which the winner receives the stake s N. Every bid made during the auction must be a multiplicity of a minimal bid increment Δ. Without the loss of generality, we assume that Δ = 1. Each player has a certain budget denoted b1 and b2, respectively, and, unless stated otherwise, we assume that both are equal, i.e., b1 = b2 = b and that b > s > Δ. We will often refer to players as i and j when their exact identities are irrelevant.

1 2 3 4 5 6 7

Player s 1 bid

Player s 2 bid

Figure 1: Example of the dollar auction graph, with player 1 (blue) as starting player.

The players make bids in turns. The starting player is determined randomly at the beginning of the auction. She can either make the first bid or pass. If she decides the latter, then the other player can either make the first bid or pass. If neither of the players decides to make the first bid, the auction ends without giving the stake to anyone. Once the first bid has been made, any player to move can either make a bid higher than the opponent, or pass. If the latter happens, the turn is not offered to the opponent but the auction ends with the opponent being the winner. The auction also ends when one of the players makes the bid that her opponent cannot top. Let xi and xj be the final bids of the players such that xi + xj > 0. The profit of player i, denoted pi, is either

pi = s xi if xi > xj, or xi if xi < xj.

The dollar auction can be conveniently presented as a graph in which nodes represent states of the auction (they correspond, in particular, to a pair of bids that have been made by both players) and edges outgoing from a node represent bids that the players can make. We call it a dollar auction graph, or simply a graph. A sample dollar auction graph for the auction with budget b = 7 and for player 1 starting the auction is shown in Figure 1. The initial state is marked with the letter S. The blue nodes are the states in which the bid of player 2 is higher than the bid of player 1. Hence, in the blue nodes, player 1 makes a decision about her next move. If she passes then player 2 wins the auction. Otherwise, any bid available to player 1 is represented with a blue edge outgoing from the given node. At the same token, the red nodes in the graph correspond to the states where player 2 has to either pass or make her bid, and the red edges correspond to the bids available. We use Xi to denote the set of states of the auction in which player i can make the bid, i.e., Xi = {(xi, xj)

{0, . . . , b 1} {0, . . . , b 1} : xj > xi} {(0, 0), ( 1, 0)}, where xi is the last bid of the player currently choosing her bid and xj is the last bid of her opponent. State ( 1, 0) represents the decision to be made when starting the auction and state (0, 0) represents the decision to be made when given the chance to start by the opponent. Having described the graphical representation of an auction, we move on to formally defining the set of all possible strategies. We will denote this set by S. Following O Neill (1986), we assume that all the strategies are deterministic. In particular, the strategy of player i is a function f : Xi {0, . . . , b}, where value f(xi, xj) represents the bid to be made by the player in state (xi, xj). For valid strategies we have f(xi, xj) xj, where f( 1, 0) = 0 represents the decision to let the opponent move first when the player starts, and f(xi, xj) = xj represents the decision to pass in all other cases. The solution concept we use, following the work of O Neill (1986), is subgame perfect equilibrium. Moreover, we assume (again, following O Neill (1986)) that players are risk-averse. Given a choice of two strategies holding the same utility outcome, the player will choose the strategy with lower final bid against given opponent.

Spitefulness and Types of Spiteful Players

Spitefulness (Levine 1998) is a desire of a player to hurt her opponents, and this possibly by incurring some cost. A spiteful player i is characterised by a spite coefficient αi [0, 1] which represents the weight that player i attributes to own profit in relation to the opponent profit. The higher the spite coefficient, the more the player i is interested in minimizing the profit of her opponent and less in maximizing own profit. In what follows, we assume that a spiteful player i maximizes the utility function (Brandt et al. 2005):

ui = (1 αi)pi αipj,

where pi and pj are the profits of players i and j, respectively. Given this, the utility of a spiteful player i in an auction that ended with bids xi and xj (xi + xj > 0) is:

ui(xi, xj) = αixj + (1 αi)(s xi) if xi > xj, αi(xj s) (1 αi)xi if xi < xj.

When αi = 0, player i only cares about her own profit, i.e., she is a non-spiteful player. We call a player with the spite coefficient 0 < αi < 1

2 a weakly spiteful player. Conversely, we call a player with the spite coefficient αi 1

2 a strongly spiteful player. A player with a spite coefficient αi = 1 is called a malicious player. She is only interested in minimizing the profit of her opponent. It is interesting to map utility to the nodes in the dollar auction graph. Figure 2 presents such a mapping for players with different values of spite coefficient. The figure shows that while weakly spiteful players are generally more interested in ending the auction in states with low sum of the bids, strongly spiteful players prefer states with higher sum of the bids. Our analysis will show that the optimal strategies of weakly and strongly spiteful players are indeed different.

Regret In settings with uncertainty it is common to evaluate different strategies based on regret (Loomes and Sugden 1982; Boutilier et al. 2006). Assume that the opponent s strategy is fixed. Let U(f) be the utility gained from using an auction strategy f and let f be an optimal strategy in the given auction. Regret R(f) from using strategy f is the difference between the utility given the optimal strategy and the utility given strategy f:

R(f) = U( f) U(f).

Having presented the basic concepts of our setting, we move to the analysis of optimal strategies of different kinds of players during the auction.

Optimal Strategies We assume that both players participating in the dollar auction have complete information of the opponent, i.e., they know each other spite coefficients. We start with introducing the concept of the maximal preserving increase which will be used later on in the description of optimal strategies. We then derive the maximal preserving increase for each type of a player (i.e., her spite coefficient). Definition 1 (Maximal preserving increase). The maximal preserving increase δi of a player i with spite coefficient αi is the maximal increase of her bid such that her utility increases, i.e.:

δi = argmax δ (xi,xj) Xi: 0<xj xi<δ ui(min(xi + δ, b), xj) > ui(xi, xj)

Lemma 1. The value of the maximal preserving increase of a player i with the spite coefficient αi is:

δi = min( s 1 αi 1 , b).

Proof. From the definition, the utility of player i in a state (xi, xj) where she is able to make a bid (i.e., (xi, xj) Xi) is: ui(xi, xj) = αi(xj s) (1 αi)xi. By definition, the state (xi, xj) is winning for j. Furthermore, her utility after raising the bid by δ and transferring to the winning state (xi + δ, xj) is:

ui(xi + δ, xj) = αixj + (1 αi)(s xi δ).

Let us now consider when ui(xi + δ, xj) > ui(xi, xj), i.e., when it is more profitable to bid. After using the definition of a spiteful player utility presented in Section and solving this inequality we obtain the following condition:

(1 αi)δ < s.

However, according to the rules of the dollar auction, any bid has to be a multiplicity of the minimal bid increment, i.e., Δ = 1. The bid increase of s 1 αi would give exactly the same utility (i.e., player i could pass with the same result); hence, to guarantee the increase in utility, the value s 1 αi 1 is needed. Furthermore, for a malicious player i (i.e., αi = 1) we need an upper bound; hence, min( s 1 αi 1 , b).

Player s 1 bid (ߙଵ ͲǤʹͷ)

Player s 2 bid

(a) Weakly-spiteful player with α1 = 1

Player s 1 bid (ߙଵ ͲǤͷ)

Player s 2 bid

(b) Strongly-spiteful player with α1 = 1

Player s 1 bid (ߙଵ ͲǤ ͷ)

Player s 2 bid

(c) Strongly-spiteful player with α1 = 3

4 Note: The black lines represent the same utility, the blue lines represents zero utility. The red areas represent negative utility, while the green areas represent positive utility. The darker the color, the higher the absolute utility value.

Figure 2: Utility of a spiteful player 1 for different values of the spite coefficient.

We now describe a strategy which we then show to be the optimal one for a strongly-spiteful player in every setting. Definition 2 (Malicious strategy). The malicious strategy of a player i in a dollar auction is:

ˆf(xi, xj) = xj + 1 if xj < b s, b otherwise.

Next, we consider the dollar auction between two strongly spiteful players. As mentioned before, the solution concept we use throughout the paper is subgame perfect equilibrium. Theorem 1. Assume that both players participating in the dollar auction are strongly spiteful, i.e., αi, αj 1 2. It is optimal for both of them to use the malicious strategy.

Proof. The following two lemmas will be used in the proof.

Lemma 2. If the dollar auction is in the state (xi, xj) such that xi b s and xj b s then it is optimal for the player who makes a bid to bid b (which ends the auction).

Proof. Due to space constraints, some proofs (namely the proofs of Lemmas 2 and 3, as well as the proof of Theorem 3) are placed in the on-line additional materials at www.tomaszmichalak.net.

Lemma 3. In an auction between two strongly spiteful players ending in state (xi, xj), we have that if ui(xi, xj) > (2αi 1)(b s) then uj(xi, xj) < (2αj 1)(b s).

If player i uses the malicious strategy, then a strongly spiteful player j never has the incentive to pass, as her maximal preserving increase δj is always higher than 2 (which is the increase needed to be made in order to continue the auction when i uses the malicious strategy). If player i follows the malicious strategy and her opponent does not pass at any point, she gets utility (2αi 1)(b s) at the end of the auction, as from Lemma 2 continuing the auction past the bid of b s would not bring her higher utility. Assume that player i can end an auction against j with utility higher than (2αi 1)(b s) in some state (xi, xj). If

(xi, xj) is winning for player i then player j will not pass in this state since by Lemma 3 she gets there lower utility than achieved by continuing with malicious strategy. If (xi, xj) is losing for player i then the auction can get to that state only by the move of player j. However, j would not make such a move, since by Lemma 3 she gets lower utility than achieved by using malicious strategy. Therefore, there is no state where i can end the auction and get higher utility than by using malicious strategy. The analogous analysis holds for a strongly spiteful player j.

As a result of Theorem 1 a dollar auction between two strongly spiteful player ends either in state (b, b s) or (b s, b), i.e., in a state where both players spend most of their budgets. Interestingly, rather than continue the auction after the bid reaches b s and try to force the opponent to pay more, both players prefer to end the auction by biding whole budget. We now move on to the case of an auction between a strongly spiteful and a weakly spiteful player.

Theorem 2. Assume that out of players participating in a dollar auction, player i is strongly spiteful, i.e., αi 1 2, and player j is weakly spiteful, i.e., αj < 1 2. It is optimal for player i to use the malicious strategy. It is optimal for player j to use a malicious strategy if b < 1 αj 1 2αj s αj 1 2αj and pass whenever given the chance to bid otherwise.

Proof. Since αi > αj, then for the maximal preserving increases the following holds δi δj. Therefore, player j will never raise her bid by a value so high that player i would not be able to outbid her without getting a lower utility. Hence, if player j continues to bid during the auction, player i can get the same result as against the strongly spiteful player. However, unlike the strongly spiteful player i, the weakly spiteful player j may decide to pass. Outbidding by higher value than 1 may cause the necessary increase of player j to exceed her maximal preserving increase and end the auction prematurely, while strongly spiteful player i is interested in

prolonging the auction. Following Lemma 2 it is still optimal for her to end the auction when value of the bid reaches b s. Therefore, the malicious strategy is still optimal for the strongly spiteful player. Since player i uses the malicious strategy, the auction can either end in one of the states (b, b s), (b s, b) or in a state winning for i, where i outbids j by 1. The utility of player j in states (b, b s) and (b s, b) is:

uj(b, b s) = uj(b s, b) = (2αj 1)(b s).

The utility of player j in state (xj, xj + 1) winning for i is:

uj(xj, xj + 1) = (2αj 1)xj αj(s 1).

Since for a weakly spiteful player 2αj 1 < 0, the utility is maximal for xj = 0. Therefore, it is optimal for player j to end the auction either in states (b, b s) or (b s, b) (she can accomplish that by following the malicious strategy) or in state (0, 1) (she can accomplish that by passing when given a chance to). Finally, expanding utilities and solving the inequality we have that uj(b, b s) > uj(0, 1) when:

1 2αj s αj 1 2αj ,

which concludes the proof.

As can be seen from Theorem 2 the optimal strategy of a strongly spiteful player is again the malicious strategy. In most cases the best choice for a weakly spiteful player facing a strongly spiteful opponent is to never make any bids. The strongly spiteful player gets the stake paying just 1. However, in some specific cases (intuitively, when budget is small in comparison to the stake), the weakly spiteful player prefers to also use the malicious strategy, as the utility gained from loss of her opponent outweighs the price she has to pay herself. In that case the auction ends in the same states as the auction between two strongly spiteful players. Finally, we describe the optimal strategies in a dollar auction between two weakly spiteful players.

Theorem 3. Assume that both players participating in the dollar auction are weakly spiteful and spite coefficient of player i is not lower than that of player j, i.e., αj αi < 1

2. Let d = δi δj, where δi and δj are the maximal preserving increases of players i and j, respectively. Also, let k = b 1

δi and x = (b 1) mod δi + 1, i.e., kδi + x = b, where 0 < x δi. Let w = 1 if x > δj kd, and let w = x otherwise. Finally, let W = min(x + kd, δi). If player i makes the first bid (either by a random roll or by the opponent passing her the first bid) and w < s, she should bid w. Otherwise she should pass. If player j makes the first bid and W < s αjw

1 αj and w < s, she should bid W. Otherwise she should pass.

As shown in Theorem 3, the dollar auction between two weakly spiteful players usually ends after making just a single bid. When one of the players bids a value, that is a very specific combination of stake, budget and spite coefficients of both players, optimal decision of her opponent is to pass.

This is the extension of result shown by O Neill (1986) for two non-spiteful players. Perhaps the most interesting is the case when w s. In such situation both players pass and the auction ends without giving the stake to anyone. This happens because initial bid necessary to secure the win is higher than the stake itself, and would bring the bidder a negative utility. At the same time however, bidding a lower amount would just encourage the opponent to retaliate, starting conflict escalation and bringing even lower utility to both players. Instead of this, both players are forced to give up the stake and accept zero utility. This result gives new insight into the dynamics of the dollar auction. Having described optimal strategies for all types of players, we move to describing the concept of equilibrium states.

Equilibrium States We now propose a slightly different setting. Let us assume, that the dollar auction does not start in state (0, 0), but rather in some other state (x1, x2), where x1 + x2 > 0. Such setting might model a confrontation, where one player has advantage at the beginning or was forced into unfavourable situation, for example a new government that has to take part in a conflict started by their predecessors. In order to model such situations we propose the concept of equilibria states. Definition 3 (Equilibrium state). We call the dollar auction state (x1, x2), such that x1 + x2 > 0, an equilibrium state when player who can make a bid in that state (i.e., player i such that xi < xj) decides to pass, knowing her opponent s spite coefficient. We consider state (0, 0) an equilibrium state when both players decide to pass in that state. In other words, an equilibrium state is the state of the auction where a player that can make a bid decides not to do so and finish the auction, either because she is satisfied with the outcome or because she does not wish to escalate the conflict. As mentioned before, the solution concept we use throughout the paper is subgame perfect equilibrium. First, we solve the case of an auction between two strongly spiteful players. Theorem 4. Consider a dollar auction between two strongly spiteful players, i.e., α1, α2 1

2. State (xi, xj) such that xi + xj > 0 and xi < xj is an equilibrium state if and only if xi(1 αi) αi(xj s) + (1 2αi)(b s) or xj = b. State (0, 0) is never an equilibrium state.

Proof. From Lemma 3 we know that player j will not pass in any state where utility of player i is higher than in states (b s, b) and (b, b s), but she would rather continue with malicious strategy. Therefore, player i should pass in state (xi, xj) only if ui(xi, xj) ui(b s, b). After expanding the utilities from definition and solving the inequality we get the following: xi(1 αi) αi(xj s) + (1 2αi)(b s). Analogical analysis holds for player j. Now, as shown in the previous section, it is optimal for strongly spiteful player to use malicious strategy when auction starts in state (0, 0). Therefore it is never an equilibrium state.

Player s 1 bid

Player s 2 bid

(a) Two strongly spiteful players, with α1 > α2 > 1

Player s 1 bid

Player s 2 bid

(b) A strongly spiteful player 1 and a weakly spiteful player 2.

Player s 1 bid

Player s 2 bid

(c) Two weakly spiteful players, with 1

2 > α1 > α2.

Figure 3: Examples of equilibrium states in a dollar auction (equilibrium states marked with blue color).

Figure 3a presents an example of equilibrium states in an auction between two strongly spiteful players. The higher the spite coefficient, the smaller the equilibria area corresponding to the states where player should not make a bid. Strongly spiteful player facing a strongly spiteful opponent passes only in states where she gets higher utility than in states (b, b s) and (b s, b), in which the auction will end if continued. Now we move to a case of an auction between a weakly and a strongly spiteful player. Theorem 5. Consider a dollar auction between a strongly spiteful player i and a weakly spiteful player j, i.e., αi 1 2 > αj. State (xi, xj) such that xi + xj > 0 and xi < xj is an equilibrium state if and only if xj xi +δi or xi(1 αi) αi(xj s)+(1 2αi)(b s) αj(xi +δi) < (1 αj)xj + (2αj 1)b + (1 αj)s or xj = b. State (xi, xj) such that xi + xj > 0 and xj < xi is an equilibrium state if and only if xj(1 αj) αj(xi s) + (1 2αj)(b s) or xi = b. State (0, 0) is never an equilibrium state.

Proof. From the perspective of a weakly spiteful player j, if she continues the auction, player i will never pass before reaching states (b s.b) or (b, b s), as in the proof of Theorem 2. Therefore player j should pass in state (x1, x2) if her utility is at least the same as in (b s.b) and (b, b s). As shown in the proof of Theorem 3a, this is equivalent to:

xj(1 αj) αj(xi s) + (1 2αj)(b s).

The same is generally true for a strongly spiteful player i. However, in that case it might happen, that i can make a bid lesser or equal to δi (thus increasing her utility) and still get to an equilibrium state, i.e., a state that j passes in. States where i can make such a bid are those where uj(xi + δi, xj) uj(b s, b) and xj < xi + δi. After expanding utilities in the first condition and solving the inequality we get:

αj(xi + δi) (1 αj)xj + (2αj 1)b + (1 αj)s.

As shown in Theorem 2, it is optimal for a strongly spiteful player to use malicious strategy when auction starts in state (0, 0). Therefore it is never an equilibrium state.

Figure 3b presents an example of the equilibrium states in an auction between a strongly spiteful player 1 and a weakly spiteful player 2. Weakly spiteful player continues to bid only when the auction is close to the end. White triangular area under the diagonal corresponds to the states in which player 1 can make a move to states where she gets a higher utility than in states (b s.b) and (b, b s), but her opponent still passes. We now move to the case where both players are weakly spiteful.

Theorem 6. Assume that both players participating in the dollar auction are weakly spiteful and spite coefficient of player i is not lower than that of player j, i.e., 1

2 > αi αj. Let d = δi δj, where δi and δj are the maximal preserving increases of players i and j respectively. Also, let k = b 1

δi and x = (b 1) mod δi + 1, i.e., kδi + x = b, where 0 < x δi. Let w = 1 if x > δj kd, and let w = x otherwise. Finally, let W = min(x + kd, δ1). State (xi, xj) such that xi + xj > 0 and xi < xj is an equilibrium state if and only if xj = b or xj xi + δi or l {0,...,k 1}xi x + lδi xj x + lδi + (k l)d. State (xi, xj) such that xi + xj > 0 and xj < xi is an equilibrium state if and only if xi = b or xi xj + δj or xj x (δj kd) or l {0,...,k 1}xi x + lδi xj x + lδi + (k l)d. State (0, 0) is an equilibrium state if and only if w s.

Proof. State (xi, xj) such that xi + xj > 0 is an equilibrium state if and only if it is a losing state for a player that can make a bid in it. Such states are described by the formulas in the theorem. Categorization of all states as losing and winning for both players is described in the proof of Theorem 3.

State (0, 0) is an equilibrium state when optimal strategies of both players are to pass in their first move, i.e., when w s, as proved in Theorem 3.

Figure 3c presents an example of equilibrium states in an auction between two weakly spiteful players. Weakly spiteful player passes, unless she is in her winning state (as classified in the proof of Theorem 3). In that case she makes the bid keeping her in her winning states an forcing the opponent to pass.

Conclusions We investigated the problem of a dollar auction between two spiteful players. We described the optimal strategy for each type of player in a complete information setting, i.e., when each player knows the value of spite coefficient of her opponent. Our results indicate, that while the optimal strategy of a strongly spiteful player remains the same in most settings, the optimal strategy of a weakly spiteful player highly depends on the available information. We also showed which of the initial states are stable, i.e., an auction started in one of them ends without a single bid being made. Again, those equilibrium points proved to be highly dependent on the levels of spitefulness of both players. As a potential future work, we intend to analyse the general incomplete information setting where none of the players has any knowledge about their opponent s spitefulness. The theoretical investigation of equilibrium concepts in the Bayesian framework might require novel analytical tools. An alternative feasible way is to use on-line learning theory to provide convergence to such solutions. However, to the best of our knowledge, such an approach has been successfully applied only to repeated games, and not to their sequential counterparts, such as the dollar auction (see also Waniek et al. 2016).

Acknowledgements We thank the anonymous reviewers for their comments which greatly improved this work. Marcin Waniek was supported by the ORCHID Project funded by EPSRC (Engineering and Physical Sciences Research Council), grant EP/I011587/1. Long Tran-Thanh was supported by the EPSRC funded project STRICT (EP/N02026X/1). Tomasz Michalak was supported by the European Research Council under Advanced Grant 291528 ( RACE ).

References Bishop, D., and Cannings, C. 1978. A generalized war of attrition. Journal of Theoretical Biology 70(1):85 124. Boutilier, C.; Patrascu, R.; Poupart, P.; and Schuurmans, D. 2006. Constraint-based optimization and utility elicitation using the minimax decision criterion. Artificial Intelligence 170(8):686 713. Brandt, F.; Sandholm, T.; and Shoham, Y. 2005. Spiteful bidding in sealed-bid auctions. In Computing and Markets. Dasgupta, P. 1986. The theory of technological competition. In New developments in the analysis of market structure. Cambridge: Cambridge: MIT Press.

Dechenaux, E.; Kovenock, D.; and Sheremeta, R. M. 2015. A survey of experimental research on contests, all-pay auctions and tournaments. Experimental Economics 18(4):609 669. Dekel, E.; Jackson, M. O.; and Wolinsky, A. 2007. Jump bidding and budget constraints in all-pay auctions and wars of attrition. Technical report, Discussion paper//Center for Mathematical Studies in Economics and Management Science. Demange, G. 1992. Rational escalation. Annales d conomie et de Statistique (25/26):pp. 227 249. Fang, H. 2002. Lottery versus all-pay auction models of lobbying. Public Choice 112(3-4):351 371. Kagel, J. H., and Levin, D. 2008. Auctions: a survey of experimental research, 1995 2008. Krishna, V., and Morgan, J. 1997. An analysis of the war of attrition and the all-pay auction. journal of economic theory 72(2):343 362. Leininger, W. 1989. Escalation and cooperation in conflict situations the dollar auction revisited. Journal of Conflict Resolution 33(2):231 254. Levine, D. K. 1998. Modeling altruism and spitefulness in experiments. Review of economic dynamics 1(3):593 622. Loomes, G., and Sugden, R. 1982. Regret theory: An alternative theory of rational choice under uncertainty. The economic journal 805 824. Mahnken, T.; Maiolo, J.; Stevenson, D.; et al. 2016. Arms Races in International Politics: From the Nineteenth to the Twenty-First Century. Oxford University Press. O Neill, B. 1986. International escalation and the dollar auction. Journal of Conflict Resolution 30(1):33 50. Sharma, A., and Sandholm, T. 2010. Asymmetric spite in auctions. In AAAI. Shubik, M. 1971. The dollar auction game: A paradox in noncooperative behavior and escalation. Journal of Conflict Resolution 109 111. Smith, J. M. 1982. Evolution and the Theory of Games. Cambridge university press. Tang, P., and Sandholm, T. 2012. Optimal auctions for spiteful bidders. Waniek, M.; Niescieruk, A.; Michalak, T.; and Rahwan, T. 2015. Spiteful bidding in the dollar auction. In Proceedings of the 24th International Conference on Artificial Intelligence, 667 673. AAAI Press. Waniek, M.; Tran-Thanh, L.; and Michalak, T. 2016. Repeated dollar auctions: A multi-armed bandit approach. In Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems. Wirls, D. 2010. Irrational Security: The Politics of Defense from Reagan to Obama. JHU Press.