Spiteful Bidding in Sealed-Bid Auctions

1 Introduction

Over the last few years, game theory has widely been adopted as a tool to formally model and analyze interactions between rational agents in the field of AI. One of the fundamental assumptions in game theory is that agents are self-interested, i.e., they maximize their own utility without considering the utility of other agents. However, there is some evidence that certain types of behavior in the real world as well as in artificial societies can be better explained by models in which agents have other-regarding preferences. While there are settings where agents exhibit altruism, there are also others where agents intend to degrade competitors in order to improve their own standing. This is typically the case in competitive situations such as in closed markets where the loss of Yoav Shoham Computer Science Department Stanford University Stanford CA 94305, USA

shoham@cs.stanford.edu

a competitor will likely result in future gains for oneself (e.g., when a competitor is driven out of business) or, more generally, when agents intend to maximize their relative rather than their absolute utility. To give an example, consider the popular Trading Agent Competition (TAC) where an agent's goal (in order to win the competition) should be to accumulate more revenue than his competitors instead of maximizing his own revenue. Other examples include the German 3G mobile phone spectrum license auction 1 in 2000, where one of the network providers (German Telekom) kept raising the price in an (unsuccessful) attempt to crowd out one of the weaker competitors (Grimm et al., 2002), and sponsored search auctions where similar behavior has been reported (Zhou and Lukose, 2006). Clearly, a reduced number of competitors is advantageous for the remaining companies because it increases their market share.

Sealed-bid auctions are an example of well-understood competitive economic processes where questioning the assumption of self-interest is particularly pertinent. For instance, in a 2 nd -price auction, it is a dominant strategy for a self-interested agent to truthfully submit his valuation, even if he is informed about the other bids. However, a competitive agent who knows he cannot win might feel tempted to place his bid right below the winning bid in order to minimize the winner's profit. In order to account for the behavior of such spiteful agents, which are interested in minimizing the returns to their competitors as well as in maximizing their own profits, we incorporate other-regarding preferences in the utility function. To this end, we define a new utility measure for agents with negative externalities (Section 3). The tradeoff between both goals is controlled by a parameter α called spite coefficient. Setting α to zero yields self-interested agents whereas a spite coefficient of one defines completely malicious agents, whose only goal is to reduce others' profit. We find that the well-known equilibria for 1 st - and 2 nd -price auctions no longer apply if α > 0. In Sections 4 and 5, respectively, we derive symmetric Bayes Nash equilibria of both auction types in the case of spiteful agents. With respect to these equilibria, we obtain further results on auction revenue and the impact of common knowledge in Section 6. The paper concludes with Section 7.

1 With respect to the revenue generated (50.8 billion Euro), this auction is one of the most successful auctions to date.

2 RelatedWork

Numerous authors in experimental economics (Fehr and Schmidt, 2006; Saijo and Nakamura, 1995; Levine, 1998), game theory (Sobel, 2005), social psychology (Messick and Sentis, 1985; Loewenstein et al., 1989), and multiagent systems (Brainov, 1999) have observed and explored otherregarding preferences, usually with an emphasis on altruism. Levine (1998) introduced a model in which utility is defined as a linear function of both the agent's monetary payoff and his opponents' payoff, controlled by a parameter called "altruism coefficient". This model was used to explain data obtained in ultimatum bargaining and centipede experiments. One surprising outcome of that study was that an overwhelming majority of individuals possess a negative altruism coefficient, corresponding to spiteful behavior. He concludes that "one explanation of spite is that it is really 'competitiveness', that is, the desire to outdo opponents" (Levine, 1998). Most papers, including Levine's, also consider elements of fairness in the sense that agents are willing to be more altruistic/spiteful to an opponent who is more altruistic/spiteful towards them. Brainov (1999) defines a generic type of "antisocial" agent by letting ∂Ui ∂u j < 0 for any j nequal i (using the notation defined in Section 3.1). A game-theoretic model in which buyers have negative identity-dependent externalities which "can stand for expected profits in future interaction" has been studied by Jehiel et al. (1996).

We extend our previous work on spitefulness in auctions (Brandt and Weiß, 2001), where we have already given an equilibrium strategy for spiteful agents in 2 nd -price auctions with complete information. Recently, other authors have studied the effects of negative externalities in auctions (Morgan et al., 2003; Maasland and Onderstal, 2003). Perhaps closest to our work is the work by Morgan et al. (2003). Although we derived our results independently, there are some similarities as well as differences, and so we should make both clear. In contrast to Morgan et al., we model spite as a convex combination of utilities which allows us to capture malicious agents who possess no self-interest at all (permitting results like Corollary 1). Morgan et al.'s definition approaches this case in the limit, but such limits are not considered in their paper. The main benefit of our definition of spite is the re-translation of bidding equilibria from bulky integrals to more intuitive conditional expectations which in turn greatly facilitates the proof of the main result (Theorem 3). Furthermore, we quantify the difference of revenue in both auctions types (Theorem 4), analyze the impact of common knowledge by computing equilibria for the complete information setting (Section 6.2), and find that the difference in revenue stems from the uncertainty about others' valuations. Morgan et al., on the other hand, also provide an equilibrium strategy for English auctions and discuss risk aversion, interpersonal comparisons, and "the love of winning" as alternative explanations for overbidding in auctions.

Interestingly, a special case of our results-the Bayes Nash equilibrium for two spiteful bidders in Vickrey auctions with a uniform prior (see Corollary 3)-was found independently by an algorithmic best-response solver (Reeves and Wellman, 2004).

3 Preliminaries

In this section, we define the utility function of rational spiteful agents and the framework of our auction setting.

3.1 Spiteful Agents

A spiteful agent i maximizes the weighted difference of his own utility ui and his competitors' utilities uj for all j nequal i. In general, it would be reasonable to take the average or maximum of the competitors' utilities. However, since we only consider single-item auctions where all utilities except the winner's are zero, we can simply employ the sum of all remaining agents' utilities.

Definition 1 The utility of a spiteful agent is given by

where αi ∈ [0, 1] is a parameter called spite coefficient.

In the following, we speak of "utility" when referring to spiteful utility Ui and use the term "profit" to denote conventional utility ui. Obviously, setting αi to zero yields a self-interested agent (whose utility equals his profit) whereas αi = 1 defines a completely malicious agent whose only goal is to minimize the profit of other agents. When αi = 1 2 , we say an agent is balanced spiteful. 2

As mentioned in Section 2, other authors have suggested utility functions with a linear trade-off between self-interest and others' well-being. In contrast to these proposals, our definition differs in that the weight of one's own utility is not normalized to 1, allowing us to capture malicious agents who have no self-interest at all. This opens interesting avenues for future research like the possibility to analyze the robustness of mechanisms in the presence of worst-case adversaries.

3.2 Auction Setting

Except for a preliminary result in Section 6.3, we assume that bidders are symmetric, in particular they all have the same spite coefficient α. Before each auction, private values vi are drawn independently from a commonly known probability distribution over the interval [0, 1] defined by the cumulative distribution function (cdf) F(v). The cdf is defined as the probability that a random sample V drawn from the distribution does not exceed v: F(v) = Pr(V ≤ v). Its derivative, the probability density function (pdf), is denoted by f (v).

Once the auction starts, each bidder submits a bid based on his private value. The bidder who submitted the highest bid wins the auction. In a 1 st -price auction, he pays the amount he bid whereas in a 2 nd -price (or Vickrey) auction he pays the amount of the second highest bid. Extending the notation of Krishna (2002), we will denote equilibrium strategies of 1 st - and 2 nd -price auctions by b I α (v) and b II α (v), respectively. When bidders are self-interested (α = 0), there are wellknown equilibria for both auction types. The unique Bayes Nash equilibrium strategy for 1 st -price auctions is to bid at the expectation of the second highest private value, conditional on one's own value being the highest, b I 0 (v) = E[X | X < v] where X is distributed according to G(x) = F(x) n-1 (Vickrey, 1961; Riley and Samuelson, 1981). 2 nd -price auctions are strategy-proof, i.e., b II 0 (v) = v for any distribution of values (Vickrey, 1961). Vickrey also first made the observation that expected revenue in both auction types is identical which was later generalized to a whole class of auctions in the revenue equivalence theorem (Myerson, 1981; Riley and Samuelson, 1981).

2 In the case of only two balanced spiteful agents, the game at hand becomes a zero-sum game.

4 First-Price Auctions

As is common in auction theory, we study symmetric equilibria, that is, equilibria in which all bidders use the same bidding function (mapping from valuations to bids). Symmetric equilibria are considered the most reasonable equilibria, but in principle need not be the only ones (we will later provide an asymmetric equilibrium in auctions with malicious bidders). Furthermore, we guess that the bidding function is strictly increasing and differentiable over [0, 1]. These assumptions impose no restriction on the general setting. They are only made to reduce the search space.

Theorem 1 A Bayes Nash equilibrium for spiteful bidders in 1 st -price auctions is given by the bidding strategy

where X is drawn from G I α (x) = F(x) n-1 1-α .

Proof: We start by introducing some notation. Let Wi = ( bi(vi) > b(1)(v-i) ) be the event that bidder i wins the auction, b(1)(v-i) be the highest of all bids except i's, v(1) be the highest private value, and ¯vi(b) denote the inverse function of bi(v). We will use the short notation ¯v for ¯v(1)(bi(vi)) to improve readability. It is important to keep in mind that ¯v is a function of bi(vi), e.g., when taking the derivative of the expected utility.

Recall that agent i knows his own private value vi, but only has probabilistic beliefs about the remaining n-1 private values (and bids). Thus, the expected utility of a spiteful agent in a 1 st -price auction is given by

We can ignore ties in this formulation because they are zero probability events in the continuous setting we consider. By definition, the probability that any private value is lower than i's value is given by F(vi). Since all values are independently distributed, the probability that bidder i has the highest private value is F(vi) n-1 . Thus, the probability that i submits the highest bid can be expressed by using the inverse bid function

The cd f of the highest of n - 1 private values is F(1)(v) = F(v) n-1 . The associated pd f is f(1)(v) = (n-1)F(v) n-2 · f (v). Using standard formulas for the conditional expectation (see Appendix A), this allows us to compute both expectation values on the right-hand side of Equation 1. The expectation of the highest private value is

whereas the expectation of the highest bid is

Inserting these expectations in Equation 1 and simplifying the result yields

When taking the derivative with respect to bi(vi), both integrals vanish due to the fundamental theorem of calculus and the observation that

In order to obtain the strategy that generates maximum utility we take the derivative and set it to zero. Thus,

From this point on, we treat vi as a variable (instead of bi(vi)) and assume that all bidding strategies are identical, i.e., ¯v = ¯v(1)(bi(vi)) = vi. Using the fact that the derivative of the inverse function is the reciprocal of the original function's derivative (¯v ′ (bi(vi)) = 1 b ′ i (vi ) ), we can rearrange terms to obtain the differential equation

It follows that b(v) ≤ v because the fraction on the right-hand side is always non-negative (recall that the bidding function is strictly increasing). Since we assume that there are no negative bids, this yields the boundary condition b(0) = 0. The solution of Equation 5 with boundary condition b(0) = 0 is

Strikingly, the right-hand side of this equation is a conditional expectation (see Appendix A). More precisely, it is the expectation of the highest of n-1 1-α private values below v (ignoring the fact n-1 1-α is not necessarily an integer), i.e.,

where the cd f of X is given by G I α (x) = F(x) n-1 1-α . It remains to be shown that the resulting strategy is indeed a mutual best response. We omit this step for reasons of limited space. □

In 1 st -price auctions, bidders face a tradeoff between the probability of winning and the profit conditional on winning. An intuition behind the equilibrium for spiteful agents is that the more spiteful a bidder is, the less emphasis he puts on his expected profit. Whereas a self-interested bidder bids at the expectation of the highest of n - 1 private values below his own value, a balanced spiteful agents bids at the expectation of the highest of 2(n - 1) private values below his value. Interestingly, agents are "least truthful" when they are selfinterested. Any level of spite makes themmore truthful. Furthermore, parameter α defines a continuum of Nash equilibria between the well-known standard equilibria of 1 st -price and 2 nd -price auctions. Even though G I α (x) is not defined for α = 1, it can easily be seen from Equation 5, that b I 1 (v) = v.

Corollary 1 The 1 st -price auction is (Bayes Nash) incentivecompatible for malicious bidders (α = 1).

This result is perhaps surprising because one might expect that always bidding 1 is an optimal strategy for malicious bidders. The following consideration shows why this is not the case. Assume that all agents are bidding 1. Agent i's expected utility depends on the tie resolution policy. If another bidder is chosen as the winner, i's expected utility is positive. If he wins the auction, his utility is zero. By bidding less than 1, he can ensure that his expected utility is always positive.

Curiously, there are other, asymmetric, equilibria for malicious bidders, e.g., a "threat" equilibrium where one designated bidder always bids 1 and everybody else bids some value below his private value. It is well-known that asymmetric equilibria like this exist in 2 nd -price auctions (see Blume and Heidhues, 2004, for a complete characterization). However, asymmetric equilibria in 2 nd -price auctions are (weakly) dominated whereas the one given above is not, making it more reasonable.

One way to gain more insight in the equilibrium strategy is to instantiate F(v) with the uniform distribution.

Corollary 2 A Bayes Nash equilibrium for spiteful bidders in 1 st -price auctions with uniformly distributed private values is given by the bidding strategy

Whereas one can get full intuition in the extreme points of the strategy (α ∈ {0, 1}), the fact that the scaling between both endpoints of the equilibrium spectrum is not linear in α, even for a uniform prior, is somewhat surprising.

5 Second-Price Auctions

In this section, we derive an equilibrium strategy for spiteful agents in 2 nd -price auctions using the same set of assumptions made in Section 4.

Theorem 2 A Bayes Nash equilibrium for spiteful bidders in 2 nd -price auctions is given by the bidding strategy

where X is drawn from G II α (x) = 1 - (1 - F(x)) 1 α .

Proof: We use the same notation introduced in the proof of Theorem 1. The expected utility of spiteful agent i in 2 nd - price auctions can be described as follows. There are two general cases depending on whether bidder i wins or loses. In the former case, the utility is simply vi minus the expected highest bid (except i's). In the latter case, we have to compute the expectations of the winner's private value and the selling price. In order to specify the selling price, we need to distinguish between two subcases: If bidder i submitted the second highest bid, the selling price is his bid bi. Otherwise, i.e., if the second highest of all remaining bids is greater than bi, we can again give a conditional expectation. Thus, the overall expected utility of agent i is

According to the formula given in Appendix A, the conditional expectation of the remaining highest bid, in case bidder i wins, is

We have already given a formula for E [ v(1) | ¬Wi ] in Equation 3. The probability that bi is the second highest bid equals the probability that exactly one bid is greater than bi and n-2 bids are less than bi. Depending on who submitted the highest bid, there are n - 1 different ways in which this can occur, yielding

The cd f of the second highest private value (of n - 1 values) can be derived by computing the probability that the second highest value is less than or equal to a given v. Either all n-1 values are lower than v, or n - 2 values are lower and one is greater than v. As above, there are n-1 different possibilities in the latter case. Thus,

It follows that the pd f is f(2)(v) = (n - 1) · (n - 2) · (1 - F(v)) · F(v) n-3 · f (v). Finally, the conditional expectation of the second highest bid times the probability of this bid being higher than bi is

Inserting both expectations and the probability of winning (see Equation 2) into Equation 6 yields

As in the previous section, we now take the derivative with respect to bi(vi) and set it to zero. All integrals vanish due to the Fundamental Theorem of Calculus and the formula given in Equation 4. We get

Using the fact that the derivative of the inverse function is the reciprocal of the original function's derivative (¯v ′ (bi(vi)) = 1 b ′ i (vi) ) and ¯v = vi, we can simplify and rearrange terms to obtain the differential equation

It turns out that b(0) = 0 does not hold for 2 nd -price auctions. However, a boundary condition can easily be obtained by letting v = 1. By definition, F(1) = 1 which yields b(1) = 1. Given this boundary condition, the solution of Equation 8 is

Like in proof of Theorem 1, the right-hand side of Equation 9 resembles a conditional expectation. In fact, the bidding strategy can be reformulated as the expectation of some random variable X, given that X > v,

where the cd f of X is given by G II α (x) = 1 - (1 - F(x)) 1 α .

It can easily be checked that G II α (x) is indeed a valid cd f (G II α (0) = 0, G II α (1) = 1, and G II α (x) is non-decreasing and differentiable). By inserting this cd f in Equation 12, we obtain the equilibrium bidding strategy. The resulting expectation is the expected value of the lowest of 1 α values above v. G II α (x) is not defined for α = 0, but the correct, well-known, equilibrium can quickly be read from Equation 8. It remains to be shown that the resulting strategy is indeed a mutual best response. We omit this step for reasons of limited space. □

Remarkably, the resulting equilibrium strategy is independent of the number of bidders n (though it does depend on the prior distribution of private values). For example, a balanced spiteful bidder bids at the expectation of the lowest of two private values above his own value. As in the previous section, we try to get more insight in the equilibrium by instantiating the uniform distribution.

Corollary 3 A Bayes Nash equilibrium for spiteful bidders in 2 nd -price auctions with uniformly distributed private values is given by the bidding strategy

For example, given a uniform prior, the optimal strategy for balanced spiteful agents is b(v) = 2 3 · v + 1 3 , regardless of the number of bidders. As in the 1 st -price auction setting, the surprising equilibrium strategies are those for 0 < α < 1. There is no linear scaling between both extreme points of the equilibrium spectrum. As we will see in the following section, this leads to important consequences on auction revenue.

6 Consequences

In order to obtain instructive results from these equilibria, we compare a key measure in auction theory-the seller's revenue-and investigate the impact of common knowledge on bidding and revenue.

6.1 Revenue Comparison

The well-known revenue equivalence theorem, which states that members of a large class of auctions all yield the same revenue under certain conditions, does not hold when agents are spiteful. Figure 1 shows the expected revenue in both auction types when agents are balanced spiteful and private values are uniformly distributed.

It can be shown that the revenue gap visible in the figure exists for any prior and spite coefficient as long as agents are neither self-interested nor malicious.

Theorem 3 For the same spite coefficient 0 < α < 1, the 2 nd - price auction yields more expected revenue than the 1 st -price auction. When α ∈ {0, 1}, expected revenue in both auction types is equal in the symmetric equilibrium.

Proof: The statement can be deduced from the following three observations:

• When agents are malicious, expected revenue in both auction types is identical. In the 1 st -price auction, truthful bidding is in equilibrium. In the 2 nd -price auction, the second highest bidder bids at the expectation of the highest private value. In both cases, revenue equals the expectation of the highest value.
• b I
• α (v) and b II α (v) are strictly increasing in α. In the 1 st -price auction, bidders bid at the (conditional) expectation of the highest value of a number of private values that increases as α grows. In the 2 nd -price auction, bidders bid at the expectation of the lowest

value of a number of private values that decreases as α grows. Obviously, both expectations are increasing in α. More formally, G I α stochastically dominates G I β and G II α stochastically dominates G II β for any α > β.

• b I α (v) is convex in α. b II α (v) is concave in α. Since both equilibria are symmetric, we just need to consider the curvature of expectations distributed according to G I α (X) and G II α (X) for variable α. Bids in 1 st -price auctions are the (conditional) expectation of the highest of 1 1-α values. The slope of this expectation increases as α rises. In 2 nd -price auctions, bids are the expectation of the lowest of 1 α values. If it were the highest value, the slope would be increasing too. However, since it is the expectation of the lowest value, the slope is strictly decreasing in α.

Let E[R I α ] and E[R II α ] be the expected revenue in 1 st - and 2 nd - price auctions, respectively, and consider these as functions of α. So far, we know that both functions are equal for α ∈ {0, 1} and strictly increasing. Furthermore, E[R I α ] is convex and E[R II α ] is concave. These facts imply that E[R II α ] > E[R I α ] for any 0 < α < 1 (see Figure 2). □

Naturally, more revenue for the seller results in less profit for the bidders. However, if you look at (spiteful) utility, the utility of winning bidders in 2 nd -price auctions is lower than in 1 st -price auctions, whereas the utility of losing bidders is higher in 2 nd -price auctions. As a consequence, social welfare (if one is willing to consider such a notion in a setting of spitefulness) is higher in 2 nd -price auctions than in 1 st -price auctions if the number of bidders is sufficiently large.

Revenue inequalities for other special conditions such as when bidders or the seller are risk-averse have been used to argue in favor of one auction form over another. Hence, Theorem 3 can be interpreted as an advantage of the 2 nd -price auction (from the perspective of a seller) because it yields more revenue than the 1 st -price auction whenever bidders exhibit the slightest interest in reducing their competitors' profit

(and they still care about their own profit). On the other hand, the difference in expected revenue is relatively small, even for just few bidders. For example, the difference in expected revenue for ten bidders with uniformly distributed private values is less than 2% for any α. Interestingly, the revenue difference is maximal for some α slightly below 0.5.

Theorem 4 The difference in expected revenue between 2 nd - price and 1 st -price auctions is maximal for some α ≤ 0.5 that approaches 1 1+ √2 ≈ 0.4142 in the limit as n rises, when private values are uniformly distributed.

Proof: By definition, the revenue difference is the difference of the expectation of the second highest bid in 2 nd -price auctions minus the highest expected bid in 1 st -price auctions. Instantiating with the uniform distribution, we get

In order to obtain the maximal revenue difference, we take the derivative of the expression given in Equation 10 with respect to α and set it to zero:

When there are only two bidders, αmax = 0.5. αmax is strictly decreasing as n increases and

6.2 Complete Information

In this section, we give bidding equilibria for spiteful agents in a model with complete information, i.e., all private values are common knowledge. This allows us to examine the influence of uncertainty on spiteful bidding.

Theorem 5 A Nash equilibrium for both 1 st - and 2 nd -price auctions in a model of complete information is given by the bidding strategy profile

where 1 and 2 are the indices of the bidder with the highest and second highest valuation, respectively. 3

Proof: Let us first consider why bidder 1 and 2 would not deviate from the given strategy profile in a 1 st -price auction. Bidder 1's utility for bidding b1, given that bidder 2 bids according to the equilibrium strategy is

Bidder 1 cannot increase his utility by deviating from the equilibrium strategy. If he bids less, his utility stays the same. If he bids more, his utility is diminishing (it is less than (1 - α) 2 (v1 - v2)). The same holds for bidder 2 whose utility is

The equilibrium point is exactly the strategy for which bidder 2 is indifferent between winning and losing since both payoffs are equal. It also coincides with his maximin strategy, i.e., the strategy that guarantees the highest payoff regardless of other players' rationality (see also Brandt and Weiß, 2001). It follows that the remaining bidders have no incentive to interfere (by bidding at least as much as bidder 1 and 2) because their utility would only decrease.

In 2 nd -price auctions, the argumentation is analogous. When the other bidders employ the equilibrium strategy, bidder 1's utility is

3 Handling ties introduces some unnecessary complications to the equilibrium strategy (involving the minimum bid increment ϵ). We brush aside these complications by assuming that whenever α < 0.5, bidder 1 wins and whenever α > 0.5, bidder 2 wins in the case of a tie. If α = 0.5, ties can be resolved either way.

Bidding more will not change anything and bidding less results in less utility (U II α (b1) < α 2 (v1 -v2)). Like above, bidder 2, whose utility is

is indifferent between winning and losing in equilibrium. □

Since the main purpose of considering the complete information model is a comparison with the equilibria given in Sections 4 and 5, we just provided an equilibrium for symmetric spite. Computing equilibria for any given profile of spite coefficients is straightforward in the complete information model.

Apparently, equilibria for 1 st - and 2 nd -price auctions are identical and scale linearly between the second highest and highest valuation (see Figure 2). This has interesting consequences on the availability of information and expected revenue: Whereas revealing private values increases expected revenue in 1 st -price auctions, it decreases revenue in 2 nd -price auctions, whenever 0 < α < 1. This effect is quite surprising because expected revenue in a setting with self-interested bidders is identical in the incomplete and complete information model (see e.g., Osborne, 2004).

6.3 Asymmetries

An important extension of our setting is one that deals with asymmetries in spitefulness. For example, it would be very desirable to extend the revenue inequality (Theorem 3) to arbitrary profiles of spite coefficients (α1, α2, . . . , αn) or a general prior from which each αi is drawn. A first step towards this direction can be made by observing that the equilibrium strategies of self-interested bidders are in a sense "robust" against spiteful bidding.

Proposition 1 Rational self-interested bidders will stick with their bidding strategy when other agents bid according to the strategies given in Theorems 1 and 2, respectively, and private values are uniformly distributed.

Proof: The statement for 1 st -price auctions follows from a result by Porter and Shoham (2003) who proved that bidders in 1 st -price auctions will stick with their equilibrium strategy even when other bidders bid constant fractions of their private value larger than n-1 n · v (in the case of a uniform prior). This holds for a certain class of probability distributions, including the uniform distribution.

The statement for 2 nd -price auctions trivially follows from the fact that bidding truthfully is a dominant strategy for selfinterested agents and therefore holds for any given prior. □

The previous proposition can be interpreted as a setting in which there are self-interested and spiteful agents participating in the same auction. Self-interested agents are aware of this asymmetry whereas spiteful agents believe that everybody is spiteful.

7 Conclusion

We studied the bidding behavior of spiteful agents who, contrary to the common assumption of self-interest, maximize a convex combination of their own profit and their competitors' losses. We derived symmetric Bayes Nash equilibria for spiteful agents in 1 st -price and 2 nd -price sealed-bid auctions. The main results are as follows. In 1 st -price auctions, bidders become "more truthful" the more spiteful they are. When bidders are completely malicious, truth-telling is in Nash equilibrium. Surprisingly, the equilibrium strategy in 2 nd -price auctions does not depend on the number of bidders. Based on these equilibria, we compared the revenue in both auction types. It turned out that revenue equivalence breaks down for this setting. Expected revenue in 2 nd -price auctions is higher than revenue in 1 st -price auctions whenever the spite coefficient α satisfies 0 < α < 1. However, revenue equivalence holds at each extreme: auctions where all agents are selfinterested (α = 0) and auction where all agents are malicious (α = 1). We showed that the difference in revenue stems from the uncertainty about others' valuations. Whereas revealing private values increases expected revenue in 1 st -price auctions, it decreases revenue in 2 nd -price auctions if 0 < α < 1.

There are several open problems left for future work. Most importantly, we intend to extend the revenue inequality (Theorem 3) to settings with asymmetric spite and investigate the mechanism design problem for spiteful agents.

Acknowledgements

We thank Christina Fong, Kate Larson, Chris Luhrs, Ryan Porter, Michael Rothkopf, Moshe Tennenholtz, Gerhard Weiß, and Michael Wellman for valuable comments.

This material is based upon work supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/1-1 and by the National Science Foundation under ITR grants IIS0121678, IIS-0427858, and IIS-0205633, and a Sloan Fellowship.

A Conditional Expectations

Let X be a random variable drawn from the interval [0, 1] according to the cumulative distribution function F(x). The expectation of X is E[X] = ∫ 1 0 t · f (t) dt. The conditional expectation that X is smaller or greater than some constant x, respectively, is given by