Spiteful Bidding in the Dollar Auction

1 Introduction

On the surface, many social situations appear to be a trap, where it seems a bad idea to invest further resources, but also seems bad to retract and lose already-invested resources. Such dilemmas are often faced by lobbyists who battle with each other in a costly and seemingly endless process of acquiring a public contract [Fang, 2002], by oligopolistic companies pressured to invest in R&D only because the competitors have done so [Dasgupta, 1986], or by many ready-to-marry people who feel trapped in their relationships [Rhoades et al., 2010].

Mimicking human societies, conflicts also abound in AI and in Multi-Agent Systems (MAS) [M¨uller and Dieng, 2000; Vasconcelos et al., 2009; Castelfranchi, 2000]. While such conflicts often used to be considered in the literature as failures or synchronisation problems [Weyns and Holvoet, 2003; Tessier et al., 2002], it has been recently argued that there is a need for more advanced studies, including analyses of conflict generation, escalation, or detection in MAS [Campos et al., 2013].

In this paper, we study Shubik's [1971] dollar auction-a simple yet powerful all-pay auction model that aims to shed light on the motives and dynamics of conflict escalation. In this auction, two bidders i and j compete for a dollar; the highest bidder wins the prize, but both the winner and the

Agata Nie´scieruk

Polish-Japanese Academy of Information Technology agata.niescieruk@pjwstk.edu.pl

Talal Rahwan

Masdar Institute of Science and Technology trahwan@gmail.com

loser have to pay their bids to the auctioneer. One might argue that it is best not to participate in this auction. However, this is not always possible. Furthermore, the possibility that a player may choose not to bid creates a clear incentive for the other player to bid and get the prize. Matter-of-factly, this reasoning is the centrepiece of the entire dollar auction mechanism that ultimately pushes players towards conflict escalation.

The above dollar auction game has become an influential abstraction of conflict escalation processes. It shows that conflicts may reach irrational levels despite the fact that, locally, every single participant makes a rational decision. Similar patterns of behaviour are observed in "clinical" experiments with the dollar auction-more often than not, a dollar bill is sold for considerably more than a dollar [Shubik, 1971; Kagel and Levin, 2008]. One of the key reasons behind this "paradox of escalation" is that a rational strategy to play this game is far from obvious; it is difficult to make an optimal choice between when "to quit" and when "to bid" (which is also true in many real-life situations).

In his beautiful paper, O'Neill [1986] offered a surprising solution to the dollar auction-he proved that, assuming finite budgets of players, in all equilibria in pure strategies, only one player bids and wins the prize. The exact amount of such a "golden" bid is a non-trivial function of the stake, the budgets, and the minimum allowable increment.

Does O'Neill's result mean that the conflict in the dollar auction does not escalate after all? The issue was revisited by Leininger [1989], who showed that the escalation can be justified in this game because there exist equilibria with escalation in mixed strategies. Later on, Demange [1992] proved that, if there is some uncertainty about the strength of the players, then the only stable equilibrium may entail escalation.

In this paper, we reconsider O'Neill's results in pure equilibria from a different perspective. Following recent literature on spiteful bidders (e.g. [Brandt et al., 2005]), we ask whether the escalation in the dollar auction may actually be caused by the meanness of some participants. Do some of us put others in an inauspicious position simply because of spite, rather than greed? Do we allow ourselves to be dragged along simply because we do not expect a spiteful opponent? Our results confirm this conjecture in various scenarios.

2 Preliminaries

In this section, we formally introduce the notation and rules of the dollar auction and the concept of spitefulness.

The Dollar Auction: The auction setting proposed by Shubik [1971] consists of two players, N = {1, 2}. We will often refer to one of them as i and the other as j. The players can declare bids xi and xj , respectively, that are multiples of a unit c ∈ N. The winner of the auction receives the stake s ∈ N. Without loss of generality, unless stated otherwise, we assume that c = 1. Some arbitrary mechanism chooses the player who places the first bid (from this moment on we call him player 1). Player 1 can either place a bid or pass the turn to player 2. If player 2 does not want to bid either, the auction ends. Otherwise, the turn moves back to player 1 and so on and so forth. At any moment, if a player quits, he receives nothing, while the other receives the stake s. After the auction, both players must pay their bids to the auctioneer, regardless of the identity of the winner. Players cannot make deals, form a coalition or make threats.

O'Neill [1986] extended the above model by explicitly assuming that the players have finite budgets b1, b2 ∈ N, where b1 > s > c and b2 > s > c. These budgets naturally constrain the players, e.g., if xi ≥ bj then player j cannot outbid player i, in which case i wins. Figure 2 presents an example of the dollar auction where b1 = b2 = 7. Each node represents a pair of bids (x1, x2). In the black nodes, player 1 chooses his bid and each solid arrow corresponds to one of his possible decisions. Analogically, the white nodes are the decision nodes of player 2 and the dotted arrows represent his possible bids. The nodes without an outgoing arrow represent situations in which the corresponding player has spent his entire budget. The auction ends either when one of the players chooses not to make his move, or when a node is reached that has no outgoing arrows.

O'Neill [1986] showed that in an auction with limited budgets, the starting player has a winning strategy; he should make a bid of (b-1)mod(s-1)+1 and his opponent should pass, as he will never win the stake. We sketch a proof of this result in the proof of Theorem 1.

Spitefulness: Following, e.g. Brandt et al. [2005], we assume that a spiteful agent is interested in increasing his own profit while at the same time decreasing the profit of his opponent. More formally, the utility of player i is:

where pi and pj are the profits of the respective players, and αi ∈ [0, 1] is the spite coefficient of player i. This coefficient indicates how important to player i is the loss of the opponent. When αi = 0, player i simply maximizes his own profit, in which case i is said to be a non-spiteful player. When 0 < αi ≤ 1, player i is said to be a spiteful player. Finally, when αi = 1, player i is said to be a malicious player, since he is solely interested in maximizing the loss of the opponent.

The concept of spitefulness is somewhat related to inequity aversion [Fehr and Schmidt, 1999], since a spiteful player suffers from any advantage of his opponent.

Let us define the profit of player i in the dollar auction as the difference between his initial budget bi and his balance after the auction. More formally, let us denote by (x1, x2) the final bids of the players, where x1 + x2 > 0. 1 Then, assuming that xi > xj , the profit of the winner of the auction is pi = s - xi, while the "profit" of the loser is pj = -xj. Formally, the utility of player i in the dollar auction is:

3 Auction Settings

We studied various ways in which spitefulness can be introduced to the dollar auction. In particular, we considered:

• (a) auctions in which one player is non-spiteful (α = 0) and the other is spiteful/malicious (α ∈ (0, 1]).
• (b) auctions in which both players are spiteful/malicious;

Moreover, we considered two alternative assumptions about knowledge/rationality of the players. First, for setting (a) we assumed that the non-spiteful player does not suspect the spitefulness of his opponent, and so uses a strategy that is optimal against a non-spiteful opponent. After that, for both settings (a) and (b) we considered the case in which both players are aware of each others' spite coefficients. Finally, we considered all cases assuming both equal and unequal budgets. For all of the aforementioned settings ,we consider subgame perfect equilibria.

Due to space constraints we focus below on setting (a) assuming limited knowledge of the non-spiteful player, results of which we found most interesting. However, at the end we briefly summarise the results for alternative settings.

4 An Auction with Equal Budgets

In this section, we analyze the dollar auction between players with equal budgets, i.e., bi = bj = b where b > s. A spiteful player has a spite coefficient ranging from 1, if he is malicious, to (almost) 0. On the other hand, a non-spiteful player has a spite coefficient of 0.

4.1 AMalicious Player (αj = 1)

If αi = 0 and αj = 1, then player i (whom we assume to be non-spiteful and does not suspect the spitefulness of his opponent), is challenged by player j who is actually malicious, meaning that the goal of j is to maximize the loss of i, no matter what the cost. In the theorem below, we show that the optimal strategy of the malicious player is to lure the nonspiteful player to continue bidding as long as possible. Still, it is the malicious bidder who gets the stake at the end.

Theorem 1. Let i be a non-spiteful player (αi = 0) who follows the strategy by O'Neill [1986], and let player j be malicious (αj = 1). The optimal strategy of j is to bid:

1 The assumption that x1 + x2 > 0 guarantees that the bidding has actually started, i.e., at least one bid has been made.

(a) At the end of the auction

(b) Backtracking and expanding

(c) At the beginning of the auction

Figure 1: Winning and losing areas during different moments of the auction.

Proof. We begin the proof by presenting the optimal strategy of a non-spiteful player who does not suspect spitefulness from the other player. This strategy was derived by O'Neill [1986]. To this end, consider the graph-based representation of the dollar auction, an example of which was discussed earlier in Section 2 and illustrated in Figure 2. Recall that every node in this graph represents a pair of bids. We call node (x1, x2) a winning node for player i if, by starting the game from this node, player i is guaranteed to eventually win the stake s. Importantly, while the bid of player i may exceed s, we note that it would be irrational to do so (the only way to increase a non-spiteful player's utility is to win the auction and get the stake s; increasing the bid by more than s outweighs any possible profit). Finally, recall that the game ends if one player exceeds his budget.

We will now analyze each node of the graph to determine whether it is a winning node for player i. Figure 1a highlights the parts of the graph that consist of winning nodes. Specifically, the width of area Ci is one node, while the widths of areas Bi, Di and Ei are s-1 nodes each. Any node in Cj is a winning one for player i, since player j cannot bid more than b and his only choice is to pass. Moreover, area Ei consists of winning nodes for i, since by raising his bid by less than s, he can move to area Cj , win the stake s and finish the auction. Nodes in area Di are losing nodes for i, since by raising his bid by less than s he can only move to area Ej, which is a winning area for j. Thus, i's optimal move in area Di is to pass. Finally, in area Bi, the only valid bid increments are those greater than, or equal to s, so it is also optimal for i to pass. The analysis for areas Cj, Bj, Dj, Ej is identical.

We can now move on to the analysis of the areas of the graph that are gradually closer to (0, 0), as illustrated in Figure 1b. The areas that we have just analyzed now play the role of areas C1 and C2. One could, of course, bid higher, but moving into Ci always optimizes cost. All arguments previously stated for areas Bi, Di, Ei still stand.

We can repeat this process until we reach an area whose dimensions are less than s × s, as illustrated in Figure 1c. In this case, areas C1 and C2 are winning areas for players 2 and 1, respectively. Consequently, area Ei is winning for player i, where his optimal choice is to make the bid (b - 1)mod(s - 1)+1 and move to area Cj . As a result, the non-spiteful player who makes the first move is always able to ensure his own victory in the auction against the other non-spiteful player.

Figure 3 depicts the winning (shaded) areas for player 1 and the winning moves for each such area, as well as the losing (white) areas for player 1, where the optimal choice for him is to pass.

Let us now assume that player i is non-spiteful and player j is malicious. Recall that the utility of the malicious player is: umal j = -pi. Naturally, the malicious player cannot make the first move and arrive at an area that is outside of the winning areas of the non-spiteful player. If he did so, then the nonspiteful player would simply pass, leaving both players with zero utility.

Next, we will show that the malicious player maximizes his utility if he plays as the second player. Hence, given the chance to move first, he will always pass the move to the opponent. Thus, throughout the remainder of this proof, player 2 will be the malicious one (i.e., i = 1 and j = 2).

Since the utility of the malicious player j is: umal j = -pi, it is maximized when the game ends in area E1, or in the adjacent nodes of area C1 in Figure 1a. However, player i will not stay in area E1, but will rather make a move towards C2. On the other hand, nodes from C1 can only be reached via a move from B1 or D1. As visible in Figure 3, (b - (s - 1), b) is the only node that player j is able to reach. His utility at this node is b - s + 1.

The next best group of nodes in terms of utility umal j are those in C2 from Figure 1a; player i wins the stake, but is forced to use all of his budget. The utility of player j is therefore b-s, which is lower than in the node (b-(s-1), b).

A bid by a malicious player j that is always one unit higher than the bid of a non-spiteful player i keeps the game in the nodes that player i considers to be "winning" nodes. When the bid of player i reaches b - (s - 1), player j should bid b, thereby reaching the node in which he achieves his highest possible utility.

4.2 A Spiteful Player (0 < αj < 1)

This subsection describes strategies for player j who is spiteful but not malicious (i.e., 0 < αj < 1). His opponent is player i, who is non-spiteful (i.e., αi = 0) and does not suspect the spitefulness of his opponent, meaning that he is following the strategy proposed by O'Neill [1986]. We divide our analysis into three parts: weakly spiteful player with αj ∈ (0, 12 ), moderately spiteful player with with αj = 12 and strongly spiteful player with αj ∈ ( 1 2 , 1). First, let us start with the following two lemmas, which hold for all of the aforementioned three cases.

Lemma 1. Let i = 1 be a non-spiteful player (αi = 0) who follows the strategy by O'Neill [1986], and let j = 2 be a spiteful player (0 < αj < 1). Furthermore, let x be the optimal initial bid of player i, and:

The optimal end-node for player j (that maximizes his utility) is among nodes X0, ..., Xn, Y0, ..., Yn.

Proof. First, let us define areas marked in Figure 4 as:

where (xk,1, xk,2) = Xk and (yk,1, yk,2) = Yk. These are the only possible end nodes of the auction. In particular, the auction cannot end in any of the unmarked nodes under the diagonal, because they can only be reached by a move by player i, but he will never make such a move (see the proof of Theorem 1). The auction can end in the marked areas under the diagonal, since player j can choose to pass at these nodes.

The auction cannot end in any of the areas marked E1. This is because player i can make moves that he considers winning from these nodes. Conversely, player i passes in all other areas above the diagonal. Now, we observe that the only difference between the nodes in marked areas is the value of the bid made by player j. For any d ∈ N we have uj ((y, x + d)) ≤ uj ((y, x)).

Lemma 2. Let i = 1 be a non-spiteful player following the strategy by O'Neill [1986], and let j = 2 be a spiteful player. The end-nodes X1, ..., Xn and Y0, ..., Yn (defined in Lemma 1) can be reached by player j regardless of who starts the game, while X0 can be reached by player j if he starts the game.

Yn Bn

Figure 4: Non-spiteful player 1, spiteful player 2. End-nodes marked in red.

Proof. Player j can reach any node Y0, ..., Yn by bidding always one unit more than the non-spiteful player i. This way, in every move player i will make his optimal bid to enter Yk. Now, player j can pass in node Yk, or bid x + s - 1 in node Yk-1 = (x, y) to reach Xk (for k > 0). Moreover, if player j starts, he can reach X0 by making the bid (b-1)mod(s-1)+1. As shown in Theorem 1, in every node Xk it is optimal for a non-spiteful player to pass.

Weakly-spiteful player with αj ∈ (0, 12 ): As it turns out, a player with a small (i.e., below 12 ) spite coefficient behaves like a non-spiteful player if he starts the bidding. Otherwise, after his opponent's move, he passes or forces his opponent to pass. Figure 5a presents an example of a utility map for a weakly-spiteful player.

Theorem 2. Let i be a non-spiteful player following the strategy by O'Neill [1986], and let j be a weakly-spiteful player (i.e., αj ∈ (0, 12 )). If j starts the bidding, it is optimal for him to bid like a non-spiteful player. If i moves first and makes bid x, then the optimal strategy for player j is to make the bid x+ s -1 when x < αjs 1-αj + 1, and pass otherwise.

Proof. Let x be the optimal initial move of a non-spiteful player, i.e., x = (b-1)mod(s-1)+1. Note that x ∈ [1, s-1]. Based on Lemma 1, the optimal end of an auction for player j is one of the nodes from the set {X0, ...,Xn, Y0, ..., Yn}. Moreover, Lemma 2 states that all of these nodes can be reached by player j. Consider the utility function of player j in nodes Xk and Xk+1 for k ≥ 1. If Xk = (a, b), then Xk+1 = (a + (s - 1), b + (s - 1)). Hence,

Analogously, the utility function of player j is lower in Yk+1 than in Yk. Thus, the optimal solution that can be reached by player j is in one of the nodes: X0 = (0, x),X1 = (x, x + s - 1), Y0 = (x, 0), Y1 = (x + s - 1, x + 1). Now, we have:

Thus, if player j starts the bidding, he prefers to bid x and end the game in X0. By comparing X1 and Y0 we have:

(a) Weakly-spiteful player (αj = 0.25)

(b) Moderately-spiteful player (αj = 0.5)

(c) Strongly-spiteful player (αj = 0.75)

Note: Blue lines represent the same utility, red lines represents zero utility. The darker the color, the higher the utility.

Figure 5: Utility maps for a spiteful player j = 2 with different values of spite coefficient.

Thus, if x < αjs 1-αj +1, then it is better for player j to bid and end the game in the state X1; otherwise, player j passes.

Moderately-spiteful player with αj = 12 : The following theorem implies that a moderately-spiteful player, whose spite coefficient is 12 , acts like a non-spiteful player if he starts the auction, but can act like a malicious player otherwise. A sample utility map for such a player is depicted in Figure 5b.

Theorem 3. Let i be a non-spiteful player (i.e., αi = 0) who is following the strategy by O'Neill [1986], and let j be a moderately-spiteful player, i.e., αj = 12 . If j starts the bidding, it is optimal for him to bid like a non-spiteful player. On the other hand, if i starts the bidding, the optimal strategy for j is to outbid i by 1 for any number of turns and finally raise his bid by s - 1.

Proof. Let us denote by x the optimal initial move of a nonspiteful player, i.e., x = (b-1)mod(s-1)+1. Note, that x ∈ [1, s - 1]. Now, based on Lemmas 1 and 2, we can consider only nodes X1, ...,Xn, Y0, ..., Yn as the optimal end points of the auction. Since uj(Xk+1) = uj(Xk) and uj(Yk+1) = uj(Yk) for k ≥ 1, the optimal reachable solution can be found by considering the nodes X0 = (0, x),X1 = (x, x + s - 1), Y0 = (x, 0), Y1 = (x + s - 1, x + 1).

Now, we have: uj(X0) = s-x 2 , uj(X1) = 1 2 , uj(Y0) = x-s 2 , uj(Y1) = -1. Therefore, the following three inequalities hold: uj(X0) ≥ uj(X1), uj(X1) > uj(Y1), uj(X1) > uj(Y0). Thus, if player j starts, it is optimal for him to end the auction in the state X0; otherwise, he should end in any of the nodes Xk.

Strongly-spiteful player with αj ∈ ( 12 , 1): A player with a high (i.e., > 12 ) spite coefficient can act like a non-spiteful player if he starts the auction for very specific values of b and s. However, in most cases he acts like a malicious player; he forces a non-spiteful player to raise his bids and then wins the stake in the end. Figure 5c presents an example of a utility map for such a strongly-spiteful player.

Theorem 4. Let i be a non-spiteful player (i.e., αi = 0) who is following the strategy by O'Neill [1986], and let j be a strongly-spiteful player (i.e., αj ∈ ( 12 , 1)). Furthermore, let x be the optimal initial bid of a non-spiteful player. If j starts the bidding and x < αj 1-αj (s - 1) - 2αj-1 1-αj b, then the optimal strategy for him is to make the bid x. Otherwise, if i starts the bidding, then it is optimal for j to follow the optimal strategy of a malicious player, described in Theorem 1.

Proof. Let us denote by x the optimal initial move of a nonspiteful player, i.e., x = (b - 1)mod(s - 1) + 1. Note, that x ∈ [1, s-1]. Again, we will limit our analysis to nodes from the set {X1, ..., Xn, Y0, ..., Yn} based on Lemmas 1 and 2.

Consider the utility function of player j in nodes Xk and Xk+1 for k ≥ 1. If Xk = (a, b), then Xk+1 = (a + (s - 1), b + (s - 1)). Here, unlike the previous cases, we have:

An analogous analysis can be obtained for nodes Yk and Yk+1, Thus, the optimal reachable solution is one of the following four nodes: X0 = (0, x),Xn = (b - (s - 1), b), Y0 = (x, 0), Yn = (b, b - (s - 2)). Now, we have:

Thus, it is always better for player j to end the game in node X0 or in node Xn, rather than in node Y0 or in node Yn. Moreover,

Therefore, if x < αj 1-αj (s-1)- 2αj-1 1-αj b holds, then it is better for player 1 to end the game with the first bid (if player j starts). Otherwise, Xn is the optimal solution.

4.3 Alternative Settings

Here, we report results for the alternative auction settings in which both players know each others' spite coefficients, αi and αj . We omit proofs due to space constraints.

Theorem 5. Let i be a non-spiteful, weakly-spiteful or moderately-spiteful player (i.e., αi ≤ 12 ) and let j be a spiteful player with αj ∈ (0, 1]. The optimal strategy for player i is to either follow the strategy proposed by O'Neill (if αj ≤ 12 ) or pass (if αj > 12 ). The optimal strategy for player j when αj ≤ 12 is the same as for player i, and when αj > 12 is to bid 1 and continue with overbidding if player i bids.

Theorem 6. Let i be a strongly-spiteful or malicious player (αi > 12 ) and let j be a spiteful player with αj ∈ (0, 1]. The optimal strategy for player i is to follow the strategy of a malicious player, described in Theorem 1. The optimal strategy for player j when αj > 12 is the same as for player i, and when αj ≤ 12 is to pass.

5 An Auction with Unequal Budgets

We now consider auctions where player budgets are unequal.

5.1 Strategies of a non-spiteful player

As shown by O'Neill [1986], a non-spiteful player has a certain strategy for an auction with unequal budgets. If he starts the game with a higher budget, he makes a bid of just one unit and expects a non-spiteful player to pass. If he starts the game with a lower budget, he makes a bid of s - 1 and expects a non-spiteful player to pass.

5.2 Strategies of a malicious player

Now let us consider an auction with a malicious player j and a non-spiteful player i (who does not suspect the spitefulness of his opponent). As it turns out, a malicious player with a higher budget can force a non-spiteful opponent to pay s - 1 and then force him to lose the stake; in this case the utility of j is umal j = s -1. On the other hand, if a malicious player starts an auction with a lower budget bj , he can force a non-spiteful opponent to pay bj + 1 in order to win the stake; in this case the utility of j is umal j = bj +1- s. Counter-intuitively, this means that a malicious player with lower budget can actually be more powerful than with higher budget; this is the case when: bj > 2s -2.

Surprisingly, if a malicious player starts an auction with a lower budget bj, he can force a non-spiteful opponent to pay bj + 1 and then force him to lose. In other words, counterintuitively, a malicious player with lower budget can actually be more powerful than a malicious one with higher budget.

Theorem 7. Let i be non-spiteful, and j be malicious. If bj > bi, and j moves second, his optimal strategy is to bid s as an answer to i's bid of s - 1. Player i then passes. If j starts the auction, it is better for him to let i move first.

Proof. (Sketch) Player i makes the bid s - 1 because it is an optimal bid against a non-spiteful player. He can gain the utility of 1, when player j passes. If player j bids s or higher, then player i passes, as he cannot win due to having a smaller budget. This yields his minimal utility of -(s - 1), and the maximal utility of a malicious player j.

Suppose j starts the auction and bids at least 1. Since i has a smaller budget, he knows he cannot win. To cut his losses, he passes at the very beginning, giving malicious player j zero utility. On the other hand, if player j lets his opponent move first, he gets positive utility, as shown above.

Theorem 8. Consider the dollar auction with a malicious player j, a non-spiteful player i and budgets bj < bi. Player j can force player i to pay bj + 1 in order to acquire the stake.

Proof. (Sketch) Player j prefers to continue the auction, as his utility rises as the auction progresses. The optimal strategy for player j is to always outbid his opponent by 1. Since player i can always win, he can make a minimum raise of 1 to minimize his losses. When the bid of player i exceeds bj - (s - 2), player j should raise his bid to bj . Player i can then get the stake s by raising his bid by s-1 to bj +1. Since it is never rational for player i to bid more than bj + 1, this strategy of player j grants him maximal utility.

5.3 Alternative Settings

Here, we report again results for the alternative auction settings in which both players know each others' spiteful coefficients, αi and αj . We omit proofs due to space constraints.

Theorem 9. Let i be a non-spiteful, weakly-spiteful, or moderately-spiteful player (i.e., αi ≤ 12 ) and let j be a spiteful player with αj ∈ (0, 1]. The optimal strategy for player i is to either follow the strategy of O'Neill (if αj ≤ 12 ) or pass (if αj > 12 ). The optimal strategy for player j when αj ≤ 12 is the same as for player i, and when αj > 12 is to bid 1 and then to continue overbidding if player i bids.

Theorem 10. Let i be a strongly-spiteful or malicious player (αi > 12 ) and let j be a spiteful player with αj ∈ (0, 1]. When αj ≥ 12 and bi < bj the optimal strategy for i is to bid bi (regardless of whether he starts). When αj ≥ 12 and bi > bj the optimal strategy for i is to start bidding with bj - 1 and answer with bj + 1 to the opponent's bid of bj . When αj < 1 2 player j will not enter the auction, so player i should simply bid 1. The optimal strategy for player j when αj > 12 is the same as for player i, and when αj ≤ 12 is to pass.

6 Related work

In this section we comment on the bodies of literature related to the key characteristics of our auction setting: spitefulness, all-pay format, and the assumption of the finite budget.

Spitefulness in auctions: On top of some work in game theory [Baye et al., 1996], and experimental game theory [Bolle et al., 2013] in particular, the analysis of spitefulness in simple types of auctions can be found, among others, in the works by Morgan et al. [2003], Brandt and Weiß [2002], Brandt et al. [2005], Babaioff et al. [2007], and Sharma and Sandholm [2010]. An interesting study of vindictive bahaviours in auction-like settings (where rivals engage in aggressive retaliatory behaviors) can be found in [Bolle et al., 2013]. Similarly, vindictive bidding in keyword auctions was studied by Zhou and Lukose [2007].

All pay auctions: While all-pay auctions are a relatively rare auction format, they have been extensively studied [DiPalantino and Vojnovic, 2009; Lewenberg et al., 2013] as they model various realistic settings in which the prize is awarded, often implicitly, on the basis of contestants' efforts. These include lobbying, job-promotion competitions, political campaigns, and R&D competitions, to name a few [Lev et al., 2013]. For an overview of experimental research on all-pay auctions see [Dechenaux et al., 2012].

The finite budget: While in many studies on auctions the existence of the budget can be neglected, this is not necessarily so in all-pay auctions. The budget constrains in all-pay auctions were studied by Che and Gale [1996].

7 Conclusions

Our results suggest that the escalation in real-life experiments with the dollar auction could be related not only to the desire to win but also (at least to some extent) to human meanness. In various scenarios in which a non-spiteful bidder unwittingly bids against a spiteful one, the conflict escalates. Not only can the spiteful bidder force the non-spiteful opponent to spend most of the budget but he also often wins the prize. Surprisingly, a malicious player with a smaller budget is likely to plunge the opponent more than a malicious player with a bigger budget. Thus, a malicious player should not only hide his real preferences but also the real amount of his budget. Intuitively, a weak, easy-to-overcome bait may seem more attractive than a stronger one.

For future work, it would be interesting to study how the results of the dollar auction change if bidders are not spiteful but rather altruistic [Chen et al., 2011], to model auctions with communication between players, or to model players with bounded rationality.

Acknowledgements

This work was supported by the Polish National Science Centre grant 2012/05/B/ST6/03364. Tomasz Michalak was supported by the European Research Council under Advanced Grant 291528 ("RACE").