Agent Failures in All-Pay Auctions

1 Introduction

Auctions have been the focus of much research in economics, mathematics and computer science, and have received attention in the AI and multi-agent communities as a significant tool for resource and task allocation. Beyond explicit auctions, as are performed on the web (e.g., eBay) and in auction houses, auctions also model various real-life situations, in which people (and machines) interact and compete for some valuable item. Companies advertising during the U.S. Superbowl are, in effect, bidding to be remembered by the viewer, and are thus putting in tremendous amounts of money in order to create a memorable and unique event for the viewer, overshadowing the other advertisers.

A particularly suitable auction for modeling various scenarios in the real world is the all-pay auction. In this type of auction, all participants announce bids, and all of them pay those bids, while only the highest bid wins the product. Candidates applying for a job are, in a sense, participating in such a bidding process, as they put in time and effort preparing for the job interview, while only one of them is selected for the job. This is a "max-profit" auction, as the auctioneer (employer, in this case), receives only the top bid. In comparison, a workplace with an "employee of the month" competition is a "sum-profit" auctioneer, as it enjoys the fruits of all employees' labour, regardless of who won the competition.

The explosion in mass usage of the web has enabled many more all-pay auction-like interactions, including some involving an extremely large number of participants. For example, various crowdsourcing contests, such as the Netflix challenge [Bennett and Lanning, 2007], involve many participants putting in effort, with only the one that performs best winning a prize. Similar efforts can be seen throughout the web, in TopCoder.com, Amazon Mechanical Turk, Bitcoin mining, and other frameworks.

However, despite the research done on all-pay auctions in the past few years [DiPalantino and Vojnovi´c, 2009; Chawla et al., 2012; Lev et al., 2013], some basic questions about all-pay auctions remain - in a full information setting, the only symmetric equilibrium has bidders' expected profit at 0, raising, naturally, the question of why bidders would participate. Allowing bidders to cooperate does not alleviate this problem (at best, it enables a bidder to have a positive expected profit, at the expense of others' negative profit [Lev et al., 2013]).

This paper enriches the all-pay auction model by allowing the possibility of bidders' failure. This means that there is a probability that a bidder will not be able to participate in the auction. As most large-scale all-pay auction mechanisms have variable participation, we believe this helps capture a large family of scenarios, particularly for web-based situations and the uncertainty they contain. We propose a symmetric equilibrium for this situation, and show its various properties. Somewhat surprisingly, allowing failures makes the expected profit for bidders positive, justifying their participation.

We first examine the case where each bidder has a different failure probability, and the potential manipulations possible in this case, such as announcing a false probability (e.g., saying that you will put all your time into a TopCoder.com project) and changing the probability of others (e.g., sabotaging their car). As calculations in this general case are complex, we examine situations where bidders have the same failure probability (as is possible when weather, for example, is the main determinant of participation), enabling us to detail more information about the equilibrium in this state. We note that due to the lengthiness of many of the calculations, we omit most steps, and show the mathematical results directly.

2 RelatedWork

Initial research on all-pay auction was in the political sciences, modeling lobbying activities [Hillman and Riley, 1989; Baye et al., 1993], but since then, much analysis (especially that dealing with the Revenue Equivalence Theorem) has been done on game-theoretic auction theory [Krishna, 2002; Klemperer, 2004]. When bidders have the same value distribution for the item, [Maskin and Riley, 2003] showed that there is a symmetric equilibrium in auctions where the winner is the bidder with the highest bid. A significant analysis of all-pay auctions in full information settings was [Baye et al., 1996], showing (aided by [Hillman and Riley, 1989]) the equilibrium states in various cases of all-pay auctions, and noting that most valuations (apart from the top two), are not relevant to the winner's strategies.

More recent work has extended the basic model. [Lev et al., 2013] addressed issues of mergers and collusions, while several others directly addressed crowdsourcing models. [DiPalantino and Vojnovi´c, 2009] detailed the issues stemming from needing to choose one auction from several, and [Chawla et al., 2012] dealt with optimal mechanisms for crowdsourcing. Using both theoretical and empirical tools, [Gao et al., 2012] examined whether several stages were better for crowdsourcing, while [Archak and Sundararajan, 2009] addressed issues related to designing the award of the crowdsourcing contest.

The early major work on failures in auctions was [McAfee and McMillan, 1987], followed soon after by [Matthews, 1987], which introduced bidders who are not certain of how many bidders there will actually be at the auction. Their analysis showed that in first-price auctions (like our all-pay auction), risk averse bidders prefer to know the numbers, while it is the auctioneer's interest to hide that number. In the case of neutral bidders (such as ours), their model claimed that bidders were unaffected by the numerical knowledge. [Dyer et al., 1989] claimed that experiments that allowed "contingent" bids (i.e., one submits several bids, depending on the number of actual participants) supported these results. [Menezes and Monteiro, 2000] presented a model where auction participants know the maximal number of bidders, but not how many will ultimately participate. However, the decision in their case was endogenous to the bidder, and therefore a reserve price has a significant effect in their model (though ultimately without change in expected revenue, in comparison to full-knowledge models). In contrast to that, our model, 1 which assumes a little more information is available to the bidders (they know the maximal number of bidders, and the probability of failure), finds that in such a scenario, bidders are better off not having everyone show up, rather than knowing the real number of contestants appearing. Empirical work done on actual auctions [Lu and Yang, 2003] seems to support some of our theoretical findings (though not specifically in all-pay auction settings).

1 We use a framework similar to the one in [Meir et al., 2012], albeit there it was used in congestion games.

3 Model

We consider an all-pay auction with a single auctioned item that is commonly valued by all the participants. This is a restricted case of the model in [Baye et al., 1996], where players' item valuation could be different.

Formally, we assume that each of the n bidders issues a bid of bi, i = 1, . . . , n, and all bidders value the item at 1. The highest bidders win the item and divide it among themselves, while the rest lose their bid. Thus, bidder i's utility from a combination of bids (b1, . . . , bn) is given by:

We are interested in a symmetric equilibrium, which in this case, without possibility of failure, is unique [Baye et al., 1996; Maskin and Riley, 2003]. It is a mixed equilibrium with full support of [0, 1], so that each bidder's bid is distributed in [0, 1] according to the same cumulative distribution function F, with the density function f (since it is non-atomic, tie-breaking is not an issue). As we compare this case to that of no-failures, this is a case similar to that presented in [Baye et al., 1996; Gao et al., 2012; DiPalantino and Vojnovi´c, 2009], where various results on the behavior of non-cooperative bidders have been provided. We briefly give an overview of the results without failures in Subsection 3.1.

When we allow bidders to fail, we assume that each of them has a probability of participating - pi ∈ [0, 1]. As a matter of convenience, we shall order the bidders according to their probabilities, so 0 ≤ p1 ≤ p2 ≤ . . . ≤ pn ≤ 1. If a bidder fails to participate, its utility is 0. 2

3.1 Auctions without Failures

The expected utility of any participant with a bid b is:

where Pr(winning|b) and Pr(losing|b) are the probabilities of winning or losing the item when bidding b, respectively. In a symmetric equilibrium with n players, each of the bidders chooses his bid from a single bid distribution with a probability density function fn(x) and a cumulative distribution function Fn(x). A player who bids b can only win if all the other n - 1 players bid at most b, which occurs with probability F n-1 n (b). Thus, the expected utility of a player bidding b is given by:

In a mixed Nash equilibrium, all points in the support yield the same expected utility to a player; thus, as the equilibrium has full support, π(0) = π(x) for all x ∈ [0, 1]. Since π(0) = 0, this means that for all bids, F n-1 n (b) = b. Thus,

2 The calculations utilize an average probability, so if every bidder has a distribution function on its probability to fail, these results still stand.

x 2-n n-1 n-1 . The various properties of an auction without failures can be found in Table 1.

4 Every Bidder with Own Failure Probability

We assume that each bidder has its own probability of participating in the auction, with 0 ≤ p1 ≤ . . . ≤ pn ≤ 1. We shall now present a symmetric equilibrium for this case, with a positive expected utility for the bidders.

We begin by defining a few helpful functions. First, we de-

fine λ = n-1 ∏ j=1 (1-pj ), and we define the following expressions

for all 1 ≤ k ≤ n - 1:

For the virtual "0" index, we use s0 = 1 - λ. Note that because the pis are ordered, so are the si s: 1 ≥ s0 ≥ s1 ≥ . . . ≥ sn-1 = 0.

4.1 Equilibrium

We are now ready to define the c.d.f.s for our equilibrium, for every player 1 ≤ i ≤ n - 1:

Fn, uniquely, while it is very similar to Fn-1 in its piecewise composition, has an atomic point in the distribution at 0 of 1 - pn-1 pn , so:

Note that all c.d.f.s are continuous and piecewise differentiable, 3 and when pi = pj it follows that Fi = Fj; therefore, this is a symmetric equilibrium. In the course of proving this is indeed an equilibrium, we shall calculate the expected utility of the bidders when they participate.

The logic behind this equilibrium is that bidders that participate rarely will usually bid high, while those that frequently participate in auctions with less competition would more commonly bid low.

When bidder i bids according to this distribution, i.e., x ∈ [sk , sk-1 ) for 1 ≤ k ≤ i:

If bidder i bids outside his support, i.e., x ∈ [sk , sk-1 ) for i + 1 ≤ k ≤ n - 1, the same equation becomes:

3 When ∏k-1 j=1 (1 - pj) = 0, and Hk is undefined for some k, then there is no range for which that Hk is used.

Finally, as i + 1 ≤ k, pi ≤ pk-1, hence pi - pk-1 ≤ 0, and πi(x) < λ.

4.2 Profits

When a bidder actually participates his expected utility is λ, and therefore the overall expected utility for bidder i is piλ (which, naturally, decreases with n). Notice that, as is to be expected, a bidder's profit rises the less reliable his fellow bidders are, or the fewer participants the auction has. However, the most reliable of the bidders does not affect the profits of the rest. If a bidder can set his own participation rate, if there is no bidder with pj = 1, that is the best strategy; otherwise, his optimal probability should be 12 , as that maximizes

In order to calculate the auctioneer's profit in a sum-profit model, we need to calculate the expected bid by each bidder, and for that we need to calculate the bidders' p.d.f. For 1 ≤ i ≤ n - 1:

The expected bid by each bidder, for 1 ≤ i ≤ n - 1:

and E [bidn] = pn-1 pn E [bidn-1].

This expression decreases with n, indicating, as in the nofailure model, that as more bidders participate, the chance of losing increases, causing bidders to lower their exposure. Surprisingly, when summing over all bidders, we receive a much simpler expression, and the sum-profit auctioneer's profits are:

In this case, growth with n is monotonic, and hence, any addition to n is a net positive for the sum-profit auctioneer.

To calculate a max-profit auctioneer's profits, we need to first define the auctioneer's c.d.f.:

That is,

This is differentiable, and hence we can find g(x) = d dx G(x); looking for the expected profit, we have:

This means that the max-profit auctioneer would prefer to have two reliable players (pn = pn-1 = 1), and the other n - 2 bidders as unreliable as possible.

Example 4.1. Consider how four bidders interact. Our bidders have participation probability of p1 = 13 , p2 = 12 , p3 = 3 4 and p4 = 1. Let us look at each bidder's c.d.f.s:

The expected utility for bidder 1 is 1 36 , for expected bid of 14 27 ; for bidder 2, 1 24 for expected bid of 0.394; for bidder 3, 1 16 for expected bid of 0.277; and for the last bidder, 1 12 for expected bid of 0.207.

A sum-profit auctioneer will see an expected profit of 113 144 , while a max-profit one will get, in expectation, 0.490.

As a comparison, in the case where we do not allow failures, the c.d.f. of the bidders is x 13 with expected bid of 14 and expected utility of 0. The expected profit of the sum-profit auctioneer is 1, while the expected profit of the max-profit auctioneer is 4 7 .

5 False Identity and Sabotage

Suppose our bidder can influence others' perceptions, and create a false sense of its participation probability. What would its best strategy be, and how should the participation probability be altered? Any bid beyond s0 is sure to win, but as that would give profit of less than λ, which is less than the expected profit for non-manipulators, it is not worthwhile. So our bidder will bid in its support, with the expected profit being λ. Thus, our bidder will strive to increase λ, and would do so by trying to portray its participation probability as being as low as possible, thus lulling the other bidders with a false sense of security. Of course, this reduces the payment to auctioneers of any type, and therefore, they would try to expose such manipulation.

More interesting is the possibility of a player's changing another player's participation probability by using sabotage; thus our bidder would be the only bidder knowing the real participation probability. Our bidder, i, sabotages bidder r, with a perceived participation probability of pr, changing his real participation probability to p′r . Bidder i's expected profit with bid x is:

The values of this function change according to the relation between r, i and x. To find the optimal strategy for a player, we will examine all the options. When x is in bidder i's support and not in bidder r's support, i.e., there is a k < i for which x ∈ [sk , sk-1 ) and r < k:

In this case, this is larger than λ only if pr > p′r , and grows with the bid, though the maximal bid (due to the fact that r < k) is sr .

If k < r (i.e., k is in i and r's support):

Since x < sk-1 , this means that λ + x < (1 -

pk-1)n-k ∏k-1 j=1 (1 - pj ), hence ∏k-1 j=1 (1-pj ) λ+x 1 n-k > 1; again, if pr > p′r , this is an increase over λ - the position without sabotaging.

Due to space constraints we do not detail here the calculations for the other cases for i and r, as they collapse to the above equations. The saboteur's optimal bid is dependent on the specific makeup of the auction, and hence, so is the value of the sabotage action. For x ∈ [sk , sk-1 ], if 1 n-k is in the range (pk, pk-1), the optimal bid is (1- 1 n-k )n-k ∏k-1 j=1 (1-pj)-λ, while if 1 n-k ≤ pk-1, the optimal bid is sk-1 , and if 1 n-k ≥ pk, sk is optimal. However, one must go through every range in player i's support to decide what is the optimal bid for a particular auction. Note that the same equations are true for every bidder that is not r (i.e., not just the manipulator i). Since at every point in i's support, it will be better than before the manipulation, that is true also for the other bidders; therefore, the manipulation has benefited not only the saboteur (though it will be able to optimize its strategy towards it), but also all other bidders other than bidder r.

6 UniformFailure Probabilities

If we allow our bidders to have the same probability of failure (e.g., when failures stem from weather conditions), many of the calculations become more tractable, and we are able to further understand the scenario.

6.1 Profit Variance

As this case is a particular instance of the general case presented above, we know the expected utilities. However, the simplification of the identical probabilities allows us to examine the variance as well. For each bidder, the expected utility is p(1 - p)n-1 , monotonically decreasing in n. Using the c.d.f. calculated in the general case, we can also calculate the expected utility squared, and we use it to calculate the utility variation:

The variance increases with p.

The expected bid is 1 np (1 - (1 - p)n-1 (1 + p (n - 1))), which is neither monotonic in n nor in p. Hence, the expected profit of the sum-profit auctioneer is 1 - (1 - p)n-1 (1+p (n-1)) which is monotonically increasing in p and in n. The profit variance is np(1-(1-p)2n-1 ) 2n-1 - (1-(1-p)n )2 n . Note that as n grows, the auctioneer's expected revenue approaches that of the no-failure case.

In the case of the max-profit auctioneer, the expected profit is n 2n-1 + n-1 2n-1 (1-p)2n-1 - (1-p)n-1 , which is monotonically increasing in p; while not monotonic in n, for large enough n it approaches the expected revenue in the no-failure case. The variance is (1-p)2n-2 - 2n(1-p)n-1 2n-1 + n 3n-2 - 2(n-1)2 (1-p)3n-2 (3n-2)(2n-1) - ( n 2n-1 + n-1 2n-1 (1 - p)2n-1 - (1 - p)n-1)2 .

7 Conclusion and Discussion

Bidders failing to participate in auctions happen commonly, as people choose to apply to one job but not another, or to participate in the Netflix challenge but not a similar challenge offered by a competitor. Examining these scenarios enables us to understand certain fundamental issues in all-pay auctions. In the pure information, classical versions, bidders each have an expected revenue of 0; in a limited information scenario, such as the one we dealt with, bidders have positive expected revenue, and are strongly incentivized to participate in the auction. Auctioneers, on the other hand, mostly lose their strong control of the auction, and no longer pocket almost all revenues involved in the auction. However, by influencing participation probabilities, max-profit auctioneers can effectively increase their revenue in comparison to the no-failure model. A short summary of our results appears in Table 2.

The basic idea of the equilibrium we explored here was that frequent participants could allow themselves to bid lower, as there would be plenty of contests where they would be one of the few participants, and hence win with smaller bids. Infrequent bidders, on the other hand, would wish to maximize the few times they participate, and hence bid fairly high bids. As exists in the no-failure case as well, as more and more participants join, there is a concentration of bids at lower price points, as bidders are more afraid of the fierce competition. Hence, it is fairly easy to see in all of our results that as n approached larger numbers, the various variables were closer and closer to their no-failure brethren.

There is still much left to explore in these models - not only more techniques of manipulation by bidders and potential incentives by auctioneers, but also further enrichment of the model. Currently, participation rates are not influenced by other bidders' probability of participation, but, obviously, many scenarios in real-life have, effectively, a feedback loop in this regard. Finding a suitable model for such interactions, while an ambitious goal, might help us gain even further insight into these types of interactions.

Acknowledgments

This research was supported in part by Israel Science Foundation grant #1227/12, the Google Inter-University Center for Electronic Markets and Auctions, and the Intel Collaborative Research Institute for Computational Intelligence (ICRI-CI).