Discrete Two Player All-Pay Auction with Complete Information

1 Introduction

All-pay auction constitutes a fundamental game theoretic model of contests where players exert effort in order to win a prize and only the player exerting the most effort wins the prize while other players effort is lost without a reward. This form of strategic interaction underlies economic activities such as bitcoin mining [Dimitri, 2017], crowdsourcing [DiPalantino and Vojnovic, 2009; Chawla et al., 2019], political campaigns [Snyder, 1989], R&D races [Dasgupta, 1986], rent seeking and lobbying activities [Moulin, 1986; Hillman and Samet, 1987; Hillman and Riley, 1989; Baye et al., 1993], competition for a monopoly position [Ellingsen, 1991], as well as sport competition [Szymanski, 2003].

Full characterisation of equilibria in a variant of all-pay auction where effort of players is continuous was obtained by [Baye et al., 1996; Hillman and Riley, 1989]. In many situations, however, it is natural to assume that effort is discrete: amount of computational resources, monetary expenditure, activists in political campaining, the time spend on projects, or man-power are usually measured in discrete units. This raises a number of questions: How does the discrete character of effort affect equilibrium behaviour of auction participants? Does it benefit the stronger or the weaker side of an auction? How well does equilibrium characterisation based on the continuous model approximates equilibria in the discrete model?

Although resources like money or man-power could be (and often are) modelled as continuous, they are intrinsically discrete. The assumption of continuity is often made to make the problem tractable. But this may be at the expense of accuracy of the results obtained. To know whether the assumption is indeed without any unexpected side effects we need to understand the consequences of the constraint of discreteness. Suppose for example that we apply the result based on the assumption of continuous resources to the model where resources are, in fact, discrete. Consider the weaker player with a valuation that is not an even number. The result obtained for the continuous model calls for investing zero with some probability and, with the remaining probability, mixing uniformly on an interval [0, v2], where v2 is the value of winning for the weaker player. Choosing effort levels according to this result would lead to non-equilibrium investment under the discrete model, because the weaker player should choose with probability greater than 0 only even valued investment levels. Complete characterization or equilibria in the discrete model allows us to see, in particular, when and to what extent the assumption of continuity is harmless and leads to adequate results.

Our contribution. In this paper we address these and similar questions by providing a complete characterisation of mixed strategy Nash equilibria of discrete all-pay auctions. We show that certain qualitative features of these equilibria are similar to features of equilibria in continuous all-pay auctions. Let v1 and v2 be valuations of the prize by the two auction participants. Suppose that v1 ≥ v2, so that the second participant is the weaker one. In equilibrium of the continuous model the weaker player chooses zero effort with probability 1-v2/v1 and, with probability v2/v1 chooses her effort level by mixing uniformly on the interval [0, v2]. The stronger player mixes uniformly on the interval [0, v2]. We show that in the discrete model the weaker player chooses zero effort with probability close to 1 - v2/v1 and chooses her effort level by mixing on the interval [0, v2] with distributions which are convex combinations of distributions which are uniform on even and odd number in an interval close to [0, v2] or are distorted variants of such distributions. Equilibrium payoffs are generically unique. Discreteness of effort levels benefits the weaker player allowing her to obtain a positive payoff when her prize valuation is close to the prize valuation of the stronger player. In the case of the stronger player, discreteness of effort levels may be beneficial or not, depending on the prize valuation of the weaker player.

1.1 Related Literature

All-pay auctions with discrete effort levels were studied by [Cohen and Sela, 2007]. The focus of their paper is the effect of different tie-breaking policies. In the case of the tie breaking policy where each of the two players wins the prize with probability half in case of a tie, as considered in our paper, they provide partial characterisation of equilibria in the cases where players valuations are integer numbers. All-pay auctions are closely related to General Lotto games [Hart, 2008]. Continuous variant of these games was considered by [Bell and Cover, 1980; Myerson, 1993; Sahuguet and Persico, 2006]. In particular, [Sahuguet and Persico, 2006] show that equilibria in these games are related to equilibria in continuous all pay auctions and exploit this connection to obtain equilibrium characterisation. In this paper we take a reverse approach. We show that equilibria in discrete all-pay auctions are a subset of equilibria in the corresponding discrete General Lotto games. We then use the full characterisation of equilibria in discrete General Lotto games obtained by [Hart, 2008] and [Dziubi ´nski, 2012] to obtain full characterisation of equilibria in discrete all-pay auctions.

Due to applications in computer based systems, more recently all-pay auctions attracted attention from researchers in computer science and AI. [Dimitri, 2017] models proof of work based bitcoin mining as an all-pay auction. [Lev et al., 2013] study an extension of the basic model allowing for collusion, [Lewenberg et al., 2017] consider an extension of the model with agent failures. [DiPalantino and Vojnovic, 2009] apply all-pay auction models to study crowdsourcing while [Chawla et al., 2019] use all-pay auctions models to study optimal mechanisms in the context of crowdsourcing.

The rest of the paper is organized as follows. In Section 2 we define the model of discrete all-pay auctions. Section 3 contains the characterisation results as well as discussion of relation to the continuous variant of all-pay auctions. We conclude in Section 4. Omitted proofs are available at https://arxiv.org/abs/2305.04696.

2 The Model

There are two players, 1 and 2, competing for a prize that is worth v2 > 0 for player 2 and v1 ≥ v2 for player 1. Player 2, who values the prize not more than player 1 is called the weaker player and player 1 is called the stronger player. Each player i ∈ {1, 2}, not observing the choice of other player, chooses an effort level xi ∈ Z≥0 in competition for the prize. The player choosing the higher effort level wins the prize and, in the cases of a tie in effort levels, one of the players receives the prize with probability 1/2. Both player pay the price equal to their chosen effort levels. Payoff to player i from effort the pair of effort choices (x1, x2) ∈ Z2≥0 is equal to

where x-i denotes the effort level chosen by the other player. We allow the players to make randomize choices, so that each player i chooses a probability distribution on non-negative integer numbers ξi ∈ ∆(Z≥0). 1 For simplicity and notational convenience, with a probability distribution on Z≥0, ξ, we will identify a non-negative integer valued random variable Xi distributed according to ξi, so that for each k ∈ Z≥0, P(Xi = k) = ξ ik . We will also use the random variables to refer to the associated probability distributions. Expected payoff to player i from randomized effort choices (X1, X2) ∈ ∆(Z≥0)2 is equal to

We assume that the players are risk neutral and each of them aims to maximise her expected payoff. A pair of mixed strategies (X1,X2) is a mixed strategy Nash equilibrium if and only if for any mixed strategies X′1 and X′2 on non-negative integers, P 1 (X1,X2) ≥ P 1 (X′1 ,X2) and P 2 (X1,X2) ≥ P 2 (X1, X′2 ). We are interested in mixed strategy Nash equilibria of this game, called Nash equilibria or equilibria, for short, throughout the paper.

3 The Analysis

Payoff to player i from strategy profile (X1, X2) can be written as

Given probability distributions (X1,X2), the quantity H(Xi,X-i) is payoff to the player choosing Xi against the choice X-i of the other player is the discrete General Lotto game defined in [Hart, 2008]. The game is played by two players, 1 and 2, who simultaneously and independently chooses probability distributions on non-negative integers. Each player i is characterized by a number bi where b1 ≥ b2 > 0. Choices of player i are constrained so that the player chooses probability distributions Xi with E(Xi) = bi. We use Γ(b1, b2) to denote the discrete General Lotto game with parameters b1 and b2.

The connection between continuous all-pay auctions and continuous General Lotto games is well known in the literature and complete characterisation of equilibria in continuous all-pay auctions, obtained by [Baye et al., 1996] was used by [Myerson, 1993] and [Sahuguet and Persico, 2006] to obtain characterisation of equilibria in continuous General Lotto games. In the case of discrete all-pay auctions we proceed in the reverse direction and use the complete characterisation of equilibria obtained by [Hart, 2008] and [Dziubi´nski, 2012] to obtain complete characterisation of equilibria in discrete all-pay auctions.

1 Given a set S, ∆(S) denotes the set of all probability distributions on S.

First, we establish that the set of equilibria in discrete allpay auctions is a subset of equilibria in discrete General Lotto games with properly chosen constraints (b1, b2).

Proposition 1. If a strategy profile (X, Y ) is a Nash equilibrium of all pay auction then it is also a Nash equilibrium of the General Lotto game Γ (E(X), E(Y )).

Proof. Suppose that (X, Y ) is a Nash equilibrium of all pay auction and let v1 be the valuation of player 1 and v2 be the valuation of player 2. Since (X, Y ) is a Nash equilibrium so, for any strategy X′ of player 1 with E(X′ ) = E(X),

By (3) and E(X′ ) = E(X) this is equivalent to

Similarly, for any strategy Y ′ of player 2 with E(Y ′ ) = E(Y ),

Since H is the payoff function in the General Lotto game and strategies in Γ(E(X),E(Y )) of each player are restricted to distributions with the same expected value, (X, Y ) is a Nash equilibrium of Γ (E(X), E(Y )).

The set of equilibria in a discrete all-pay auction is (usually, i.e. for most values of v1 and v2) a proper subset of equilibria in the corresponding General Lotto games. Before we provide the characterisation of this set, we introduce the probability distributions that are the building blocks of equilibria in General Lotto games.

[Hart, 2008] defines the following probability distributions. Given m≥ 1, let

and, given m≥ 0, let

where, given an integer j, 1j is the Dirac's measure putting probability 1 on j. Distributions U m O andU m E are "uniformon odd numbers" and "uniform on even numbers", respectively. We will use

to denote the set of these distributions. [Dziubi´nski, 2012] defines the following distributions. First, given m ≥ 1, let

which is a uniform distribution on even numbers from 2 to 2m - 2. Given m ≥ 2 and 1 ≤ j ≤ m - 1, let

Each distribution W m j is the distribution U m O distorted at the first 2j + 1 positions with a 2-moving average, so that P(W m j = i) = (P(U jO = i - 1) +P(U jO = i + 1))/2, for 0 ≤ i ≤ 2j (where P(U jO = -1) = 0). We will use

to denote the set of distributions W m j . Given m ≥ 1 and 1 ≤ j ≤m, let

Each distribution V m j is the distribution U m E distorted at the first 2j positions with a 2-moving average, so that P(V m j = i) = (P(U j-1 E = i-1)+P(U j-1 E = i+1))/2, for 0 ≤ i ≤ 2j - 1 (where P(U j-1 E = -1) = 0). We will use

to denote the set of distributions V m j .

With these distributions in hand, we are ready to state our main results. We divide the characterisation of equilibria in discrete all-pay auctions into two cases, covered by Theorems 1 and 2 below. The first is the case where half of the valuation of the prize by the second (weaker) player is an integer number and the second is the case where it is not an integer number and it is greater than 1. 2

Theorem 1. Strategy profile (X, Y ) is a Nash equilibrium of all-pay auction with players valuations v1 ≥ v2 and v2/2 ∈ Z≥1 if and only if

(i) if v1 = v2 then

with m = v2/2 - 1, α ∈ [0, 1], and β ∈ [0, 1]. Equilibrium payoffs are

2 For completeness, in the supplementary material we provide an additional Theorem 4 which covers the case of v2/2 ∈ (0, 1).

where b ∈ (0, 1] and

Equilibrium payoffs are

(iii) if v1 > v2 ≥ 3 then

where m = v2/2, b ∈ [v2(v2 - 2)/(2v1), min(m, v2(v2 + 2)/(2v1))], and

with

and

Equilibrium payoffs are

The first point of the theorem covers the symmetric case where both players value the prize equally. In this case each of the players uses a convex combination of the uniform probability distribution on even numbers from 0 to 2m and the uniform probability distribution on odd numbers from 0 to 2m+1, where m = v2/2-1. There are continuum of possible equilibrium payoffs and payoff of each player is equal to 1 minus the probability with which the opponent uses the uniform on odd numbers probability distribution. In particular, payoff of 0 as well as payoff of 1 is possible for each player, depending on the strategy used by the opponent.

The second and the third points of the theorem cover the asymmetric case where the valuation of player 2 is strictly smaller than the valuation of player 1. The second point covers the subcase where m = v2/2 takes value 1 and the third point covers the remaining subcases. In each case the stronger player mixes uniformly on odd numbers between 1 and 2m - 1 while the weaker player chooses effort 0 with probability 1 - b/m and, with probability b/m, uses a strategy which picks positive effort levels with probability greater than 0. Like in the case of the first point of the theorem, there is continuum of equilibria and continuum of equilibrium payoffs. The equilibrium expected payoff to the stronger player depends on the expected value, b, of the strategy chosen by the weaker player. The expected equilibrium payoff of the weaker player is equal to 0 in all the cases.

Although there is continuum of equilibria and continuum of equilibrium payoffs when valuation of the prize by the weaker player is an even number, the equilibria exhibit the interchangeability property: if (X, Y ) and (X′ , Y ′ ) are both equilibria of all-pay auction, (X, Y ′ ) and (X′ , Y ) are equilibria as well. Thus so long as each player chooses an equilibrium strategy, none of them has an incentive to deviate to a different strategy. In addition, the sets of equilibrium strategies of the players are convex.

Proof of Theorem 1 is lengthy and we give most of it in the supplementary material. The general structure of the proof is to first establish the necessary and sufficient properties of equilibria in discrete all-pay auction under different combinations of expected values of equilibrium strategies X and Y . These characterizations are then used to obtain the final result. To give the reader some idea of how these necessary and sufficient properties are established we provide a proof for the symmetric case of E(X) = E(Y ) = m with m ∈ Z≥0. In the proof we use the following simple but useful properties of function H.

For any strategies X and Y ,

and for any strategies X1, X2, Y and any λ ∈ [0, 1],

Proposition 2. A strategy profile (X, Y ) such that E(X) = E(Y ) = m, m ∈ Z≥1, is a Nash equilibrium of all pay auction with both players valuations v1 ≥ v2 > 0 if and only if,

·

·

Equilibrium payoffs of the players are

Proof. For the left to right implication, suppose that (X, Y ) satisfying the condition stated in the theorem is a Nash equilibrium of all pay auction with both players valuations v1, v2 > 0. Then, by Proposition 1, it is a Nash equilibrium of general Lotto game Γ(m, m). Hence, by [Hart, 2008, Theorem 2],

with λ, κ ∈ [0, 1], and

Given c ∈ (-m,m) let

where

so that E(X′ ) = m+c. Since c ∈ (-m, m) and m ∈ Z≥1, so ⌊m+c⌋ ≥ 0 and ⌈m+c⌉ ≤ 2m. Hence P(X′ ≥ 2m+1) = 0. Thus, by (6), (4), and (5),

By (3), (7), and (8)

and

Since (X, Y ) is a Nash equilibrium so P (X, Y ) ≥ P (X′ , Y ). Hence

and, since v1 > 0, so

Since v1 > 0, m ≥ 0, κ ∈ (0, 1), and (9) holds for any c ∈ (-m, m) so v1/2 = m(m + 1)/(m + κ). By analogous derivation we also get v2/2 = m(m+1)/(m+λ). From this we also get

Since κ ∈ [0, 1] so m(m + 1)/(m + κ) ∈ [m,m + 1]. Hence either m = ⌊v1/2⌋ or m = ⌈v1/2⌉ - 1. Similarly, either m = ⌊v2/2⌋ or m = ⌈v2/2⌉ - 1.

For the left to right implication, consider a strategy X′ with E(X′ ) ≥ 0 of player 1. By (8) and (3),

Similarly, by (7) and (3),

Since v1/2 = m(m + 1)/(m + κ) so P 1 (X′ , Y ) = 0 = P 1 (X, Y ) and there is no profitable deviation for player 1 from (X, Y ). By analogous derivation, using v2/2 = m(m+ 1)/(m+λ), we conclude that there is no profitable deviation for player 2 from (X, Y ) either. Hence (X, Y ) is a Nash equilibrium.

The next theorem provides complete characterisation of equilibria in the case where the valuation of the prize by the weaker player is not an even (integer) number.

Theorem 2. Strategy profile (X, Y ) is a Nash equilibrium of all-pay auction with players valuations v1 ≥ v2 > 2 and v2/2 /∈ Z if and only if

Equilibrium payoffs of the players are

with

Equilibrium payoffs of the players are

(iii) if v1/2 > ⌊v2/2⌋ +1 then

where

and

where

Equilibrium payoffs of the players are

The first point of the theorem covers the case where valuations of the prize for the two players are close to each other: the difference between them is less than 1 and the closest integer value not greater than half of each valuation is the same for both of them. Similarly to the first point of Theorem 1, each of the players uses a convex combination of the uniform probability distribution on even numbers from 0 to 2m and the uniform probability distribution on odd numbers from 0 to 2m+ 1, where m = ⌊v2/2⌋. This time, however, equilibrium is unique.

The second and the third point of the theorem cover the case where floors of the valuations of the prize for the two players are not equal. The second point covers the case where half of the valuation of the stronger player is the smallest integer number greater than half of the valuation of the weaker player. The weaker player has a unique equilibrium strategy: mixing uniformly on even numbers between 0 and 2⌊v2/2⌋. The stronger player has continuum of equilibrium strategies depending on the fraction α by which the expected value of the strategy of the stronger player exceeds the expected value of the equilibrium strategy of the weaker player, ⌊v2/2⌋. Payoff of the stronger player is equal to 1 for all equilibria. Payoff of the weaker player is positive unless α attains its highest value. The third point covers the case where half of the valuation of the stronger player exceeds the ceiling of the half the valuation of the weaker player. In this case there is a unique equilibrium strategy of the weaker player: the player chooses effort 0 with probability 1 - b/m and, with probability b/m, mixes uniformly on even numbers from 0 to 2⌊v2/2⌋. The stronger player has a continuum of equilibrium strategies. All the equilibria are payoff equivalent and so equilibrium payoffs are unique. Equilibrium payoff of the weaker player is 0 and the stronger player obtains a positive equilibrium payoff. Like in the case of Theorem i, equilibria are interchangebla end set of equilibrium strategies of the players are convex.

Notice that if the space of possible prize valuations, v1 and v2, is a subset of real numbers then equilibrium payoffs are generically unique: the cases where equilibrium payoffs are not unique require one of the players to have a prize valuation which is an even number.

3.1 Comparison with Continuous All-Pay Auction

In this section we compare equilibrium characterisation in discrete case with equilibrium characterisation in the continuous case. The following result, stated in [Hillman, 1988] and [Hillman and Riley, 1989] and rigorously proven in [Baye et al., 1996], provides full characterisation of equilibria for continuous all-pay auction.

Theorem 3 (Hillman and Riley). A strategy profile (X, Y ) is a Nash equilibrium of all-pay auction with continuous strategies and players valuations v1 ≥ v2 > 0 if and only if X is distributed uniformly on the interval [0, v2] while Y is distributed on [0, v2] with a distribution with CDF F2(x) = (x - v2)/v1 + 1. Equilibrium payoffs of the players are P 1 cont. (X, Y ) = v1 - v2 and P 2 cont. (X, Y ) = 0.

One feature of equilibrium strategies that is present in both the discrete and the continuous case is that the weaker player exerts zero effort with probability close to (v1 - v2)/2 and then mixes with the remaining probability on the interval close to [0, v2]. In the case of the discrete model the interval is [0, v2] when v2 is even and [0, 2⌊v2/2⌋ + 1] when v2 is not an even number. The probability distribution on the interval, in the discrete case, is not uniform on discrete values, in general. However it is a convex combination of probability distributions which are uniform on odd number, uniform on even number, or distorted such uniform distributions. In particular in the case of the valuation of the weaker player, v2, that is not even and is less than the valuation of the stronger player by more than 2 (point (iii) of Theorem 2) the set of equilibrium strategies of the stronger player contains probability distribution that is uniform on integer values in the interval [0, 2⌊v2/2⌋ +1].

Comparative Statics

Fixing the valuation of player 1, we analyse the effect of increasing the valuation of player 2. Consider first the case when the valuation of player 1, v1, is not an even number, illustrated in Figures 1 and 2. In this case equilibrium payoffs of player 2 are unique for all values of v2. Notice that the difference in payoffs under the discrete and continuous case is equal to 0 when v2 ≤ 2⌊v1/2⌋, equal to v2/2 - ⌊v2/2⌋ when 2⌊v1/2⌋ < v2 ≤ v1, equal to v1 -⌊v1/2⌋-v2/2 when v1 < v2 ≤ 2⌈v1/2⌉, and equal to 2(v1/2 - ⌊v1/2⌋ - 1/2) when v2 > 2⌈v1/2⌉. In particular, discreteness of strategy space benefits player 2 when she is weaker but her valuation is close to the valuation of player 1: v2 ∈ (2⌊v1/2⌋, v1]. Depending on whether the valuation of player 1 is smaller or greater than the closest odd integer number, the discreteness of strategy space disbenefits or benefits player 2, respectively, when she is stronger than player 1, v2 > v1.

Second consider the case when valuation of player 1, v1, is an even number, illustrated in Figure 3. In this case payoffs to player 2 under the discrete and the continuous case are equal when v2 ≤ 2⌊v1/2⌋. When v2 > 2⌊v1/2⌋ there is a continuum of possible equilibrium payoffs and, depending on the strategy chosen by player 1, player 2 obtains lower or higher payoff under discrete strategy space as compared to the payoff under the continuous case.

4 Conclusions

In this paper we studied two player all-pay auctions with discrete strategies of the players. We provided full characterisation of equilibria as well as of equilibrium payoffs. We discussed how they are related to equilibria and equilibrium payoffs in the continuous variant of all-pay auctions. We show that equilibria in the discrete variant are not unique, in general, but the are interchangeable. Equilibrium payoffs are unique, as long as none of the players has valuation of the prize that is an even number. In case it is for at least one of the players, there is continuum of possible equilibrium payoffs. Equilibrium strategies involve convex combinations of uniform distributions on even or odd numbers as well as distorted versions of such distributions.

Acknowledgements

This work was supported by Polish National Science Centre through grant 2018/29/B/ST6/00174.