A “fractal” solution to the chopstick auction

Abstract

This paper constructs a novel equilibrium in the chopstick auction of Szentes and Rosenthal (Games Econ Behav 44(1):114–133, 2003a). In contrast to the existing solution, the identified equilibrium strategy allows a simple and intuitive characterization. Moreover, its best-response set has the same Hausdorff dimension as its support, which may be seen as a robustness property. The analysis also reveals some new links to the literature on Blotto games.

1 Introduction

Despite being one of the main mechanism for allocating multiple objects, simultaneous auctions are notorious for exposing bidders to the risk of ending up overpaying for the combination of objects ultimately won.¹ Much of the basic intuition is captured by the example of the so-called first-price chopstick auction (Szentes and Rosenthal 2003a; see also Postlewaite and Wilson 2003). In that auction, two bidders simultaneously place bids on three identical objects. Moreover, the value of winning at most one object is zero, whereas the value of winning at least two objects is positive. For the first-price chopstick auction, Szentes and Rosenthal constructed a doubly symmetric mixed-strategy equilibrium, henceforth referred to as the Szentes–Rosenthal equilibrium (SRE), in which bidders randomize according to a uniform distribution over the surface of a tetrahedron.

The structure of the SRE is intriguing, in particular because it features a two-dimensional equilibrium support enclosing a three-dimensional best-response set. As Szentes and Rosenthal (2003b) noted, however, their solution has two drawbacks. First, the equilibrium strategy is surprisingly complicated. Second, given that the best-response set has a higher dimension than the equilibrium support, it seems unlikely that the SRE would be the result of a process that is aligned with some kind of better- or best-response dynamics.

The present paper documents the existence of a new type of equilibrium for the chopstick auction. In the sequel, this equilibrium will be referred to as the self-similar equilibrium (SSE). To construct the SSE, we consider a variant of the chopstick auction, using an approach due to Sion and Wolfe (1957).² In that variant, the decision-making process of each bidder is stretched out over infinitely many stages. Moreover, at each stage, a choice is made between merely two alternatives for each object (hold vs. raise). Below, we will interpret, in an admittedly generous way, the resulting multistage game as a dynamic auction.³ The equilibrium bid distribution of the SSE will then be characterized as the measure-theoretic image of a simple stationary strategy in the dynamic auction, where the stationarity property in the dynamic auction translates into a self-similarity property in the simultaneous game.

Related literature “Fractal” solutions to noncooperative games of the Blotto type have been identified by Gross and Wagner (1950) and Kvasov (2007). However, neither of these papers considered the case of the chopstick auction.⁴ Gross (1954) has constructed an example of a zero-sum game on the square with rational payoff functions and the Cantor distribution as the unique equilibrium.⁵ Related is also the recent paper by Topolyan (2014). She uses the binary expansion of a uniformly distributed random bid to construct a continuum of equilibria in an all-pay team contest with additive contributions. Ok (2004) proved a fixed-point theorem for correspondences and applied it to rationalizability as well as to self-similar sets.

The remainder of the present paper is organized as follows. Section 2 describes the set-up. In Sect. 3, the dynamic variant of the chopstick auction is introduced, and the SSE constructed. A proof of the equilibrium property is provided in Sect. 4. Section 5 deals with the dimension of the best-response set. In Sect. 6, the SSE is characterized as a self-similar probability measure. Section 7 concludes.

2 Set-up

In the chopstick auction considered by Szentes and Rosenthal (2003a), a seller offers three identical objects, A, B, and C, via simultaneous sealed-bid auctions to a given population of two bidders. Each of the two bidders $i=1,2$ submits a vector of bids,

$$\begin{aligned} X^{i}=\left( X_{A}^{i},X_{B}^{i},X_{C}^{i}\right) \in {\mathbb {R}}_{+}^{3}. \end{aligned}$$

(1)

For each object $\nu \in \{A,B,C\}$, the bidder $i\equiv i_{\nu }\in \{1,2\}$ submitting the highest bid on object $\nu$ wins that object and pays her bid $X_{\nu }^{i}$ to the seller, where ties are broken randomly, fairly, and independently across objects.⁶ Bidder i’s valuation of winning a total of $q^{i}\in \{0,1,2,3\}$ objects is

$$\begin{aligned} V(q^{i})=\left\{ \begin{array} [c]{cl} 0 &{}\quad \text {if }q^{i}\le 1\\ 2 &{}\quad \text {if }q^{i}\ge 2\text {,} \end{array} \right. \end{aligned}$$

(2)

i.e., a bidder has a valuation of zero if she wins at most one object, and a valuation of two if she wins at least two objects. This specification of bidders’ valuations corresponds to the so-called pure chopstick case discussed in Szentes and Rosenthal (2003a, Ch. 2). In the first-price chopstick auction, bidder i’s expected payoff equals her valuation $V(q^{i})$ less the sum of her winning bids. In the second-price chopstick auction, the bidder winning any object $\nu$ (with $\nu =A,B,C$) pays only the second-highest bid on that object. Finally, in the all-pay chopstick auction, bidders pay their bids unconditionally rather than conditionally on winning. However, the term chopstick auction, i.e., without qualification, will be reserved for the first-price format.⁷

3 A variant of the chopstick auction

As outlined in the Introduction, we will now modify the set-up introduced above and assume that each player’s decision regarding her respective bid strategy is decomposed into infinitely many choices that are taken in a sequential manner, yet still before the release of any information about the opponent’s strategy.

The formal framework is as follows. At any stage $t\in {\mathbb {N}} =\{1,2,\ldots \}$, each bidder $i\in \{1,2\}$ chooses, for each object $\nu \in \{A,B,C\}$ separately, whether to hold ($x_{\nu }^{i}(t)=0$) or to raise her bid ($x_{\nu }^{i}(t)=1$). Thus, at any $t\in {\mathbb {N}}$, each bidder $i\in \{1,2\}$ is assumed to select the binary vector

$$\begin{aligned} x^{i}(t)=\left( x_{A}^{i}(t),x_{B}^{i}(t),x_{C}^{i}(t)\right) \end{aligned}$$

(3)

from the set $D_{t}=\{0,1\}\times \{0,1\}\times \{0,1\}$. Bidder $i\in \{1,2\}$ will be said to win object $\nu \in \{1,2,3\}$ against bidder $j\ne i$ if there is a stage $T_{\nu }\in {\mathbb {N}}$ such that $x_{\nu }^{i}(t)=x_{\nu }^{j}(t)$ for all $t<T_{\nu }$, and $x_{\nu }^{i}(T_{\nu })=1>0=x_{\nu }^{j}(T_{\nu })$. If such $T_{\nu }<\infty$ does not exist, then we will say that there is a tie on object $\nu$. Thus, the allocation of the three objects is determined either after finitely many stages at $T\equiv \max \{T_{A},T_{B},T_{C}\}<\infty$, or the bidding develops entirely in parallel on at least one object. As discussed, however, there is no updating, i.e., the binary vector $x^{i}(t)\in D_{t}$ chosen by bidder $i\in \{1,2\}$ at any stage $t\in {\mathbb {N}}$ is assumed to remain unobservable for bidder $j\ne i$ during the entire auction. By a (reduced-form) pure strategy for bidder $i\in \{1,2\}$, we mean a sequence $x^{i}=\{x^{i}(t)\}_{t=1}^{\infty }$ consisting of choices $x^{i}(t)\in D_{t}$ for all $t\in {\mathbb {N}}$. Alternatively, a pure strategy may be written as a vector $x^{i}=(x_{A} ^{i},x_{B}^{i},x_{C}^{i})$, where $x_{\nu }^{i}=\{x_{\nu }^{i}(t)\}_{t=1} ^{\infty }$ is a binary sequence for each object $\nu \in \{A,B,C\}$. The set of pure strategies will be denoted by $D= {\textstyle \prod \nolimits _{t=1}^{\infty }} D_{t}$. Payoffs in the dynamic game are derived from the simultaneous first-price chopstick auction, where bidder i’s bid $X_{\nu }^{i}$ on object $\nu \in \{A,B,C\}$ is replaced by

$$\begin{aligned} \rho (x_{\nu }^{i})=\sum _{t=1}^{\infty }\frac{x_{\nu }^{i}(t)}{2^{t}}\in [0,1]\text {.} \end{aligned}$$

(4)

Thus, the binary choices made by a bidder for an object in the course of the dynamic bidding process are interpreted as digits in the binary expansion of the corresponding bid in the simultaneous auction.⁸ The thereby defined infinite-horizon game will be referred to as the dynamic (first-price) chopstick auction. Thus, intuitively, the dynamic auction is equivalent to the original chopstick auction, except that any bid vector in ${\mathbb {R}}_{+}^{3}$ may possess up to $2^{3}=8$ binary representations, and that bids in the dynamic auction cannot exceed one.

Next, we define two mixed extensions of the dynamic chopstick auction, following essentially Kuhn (1953).⁹ A mixed strategy in the dynamic auction is a probability measure on D, where the Borel sets on D are derived from the product of the discrete topologies on each factor $D_{t}$.¹⁰ Bidder i’s expected payoff resulting from a pair of mixed strategies is defined as usual in terms of the bilinear extension of i’s payoff function. This extension is well-defined because payoffs are bounded. Moreover, by the substitution rule (Kallenberg 1997, Lemma 1.22), expected payoffs in the dynamic auction may be determined alternatively by considering the image measures of the players’ mixed strategies in the simultaneous auction and calculating expected payoffs there. A (path-independent) behavior strategy $\xi =\{\xi (t)\}_{t=1}^{\infty }$ in the dynamic auction specifies an independent random variable with values in the finite choice set $D_{t}$ at each stage $t\in {\mathbb {N}}$. By taking the product measure over the component distributions of a given behavior strategy $\xi$, we obtain a unique mixed strategy in the dynamic auction, which will be denoted as $\widetilde{\xi }$. In particular, expected payoffs resulting, say, from a pair of behavior strategies are well-defined. A behavior strategy $\xi$ is a symmetric equilibrium strategy (in the dynamic auction) if the associated mixed strategy $\widetilde{\xi }$ maximizes any bidder i’s expected payoffs, within the set of all mixed strategies, under the condition that bidder i’s opponent $j\ne i$ adheres to $\widetilde{\xi }$.

A specific behavior strategy $\xi ^{\text {SSE}}$ in the dynamic chopstick auction is defined by the requirement that, at each stage $t\in {\mathbb {N}}$, the bidder samples her choices independently and according to the following probability distribution:

$$\begin{aligned} \begin{array} [c]{lcccc} &{} &{} &{} &{} \\ \text {State }\omega (t) &{} \omega _{0} &{} \omega _{1} &{} \omega _{2} &{} \omega _{3}\\ &{} &{} &{} &{} \\ \text {Probability pr}(\omega (t)) &{} 1/4 &{} 1/4 &{} 1/4 &{} 1/4\\ &{} &{} &{} &{} \\ \text {Binary vector }x(t) &{} (0,0,0) &{} (0,1,1) &{} (1,0,1) &{} (1,1,0)\\ &{} &{} &{} &{} \end{array} \end{aligned}$$

(5)

Thus, adhering to $\xi ^{\text {SSE}}$ means that, at each stage, the bidder either holds her bids on all three objects, or raises her bids on precisely two randomly selected objects. Moreover, each of these altogether four possibilities is selected with equal probability, and independently across stages.

The following observation is key to most of the results of the present paper.

Lemma 1

$\xi ^{\text {SSE}}$ is a symmetric equilibrium strategy in the dynamic chopstick auction.

A proof will be provided in the next section. Lemma 1 is useful because it allows constructing a new type of equilibrium in the simultaneous chopstick auction. To see this, start from the mixed strategy $\widetilde{\xi }^{\text {SSE}}$ induced by the behavior strategy $\xi ^{\text {SSE}}$. Note next that any pure strategy $x=(x_{A},x_{B},x_{C})\in D$ in the dynamic chopstick auction may be transformed, by component-wise application of the mapping $\rho$, into a bid vector

$$\begin{aligned} X=(X_{A},X_{B},X_{C})=(\rho (x_{A}),\rho (x_{B}),\rho (x_{C}))\in [0,1]^{3} \end{aligned}$$

(6)

in the simultaneous auction. Since this transformation is continuous, the measure-theoretic image of the mixed strategy $\widetilde{\xi }^{\text {SSE}}$ under the transformation is a well-defined mixed strategy $\mu ^{\text {SSE}}$ in the simultaneous auction. Moreover, as stated in the following proposition, the image distribution inherits from $\xi ^{\text {SSE}}$ the property of being a symmetric equilibrium strategy.

Proposition 1

$\mu ^{\text {SSE}}$ is a symmetric equilibrium strategy in the simultaneous first-prize chopstick auction.

Proof

The claim follows directly from Lemma 1. Indeed, any bid exceeding one against $\mu ^{\text {SSE}}$ is suboptimal, because $X_{\nu }=1$ wins object $\nu$ with probability one. It therefore suffices to note that the component-wise application of the mapping $\rho$ is surjective on $[0,1]^{3}$. $\square$

Szentes and Rosenthal (2003b, p. 293) conjectured that the SRE is unique within the class of symmetric equilibria of the chopstick auction. Proposition 1 above shows that this is not the case. Instead, the chopstick auction admits at least one alternative symmetric solution, viz., the SSE. With the help of additional arguments that will be detailed elsewhere, one can even show that any convex combination of the SSE and the SRE is again a symmetric equilibrium. However, as will be explained in Sect. 6, there is no easy way to construct additional equilibria in the chopstick auction using the replacement techniques known from the literature on the Blotto game.

Similarities between SSE and SRE In the remainder of this section, it will be shown that the SSE shares some of the remarkable properties of the SRE.

First, most obviously, the SSE is a doubly symmetric equilibrium, i.e., symmetric both with respect to the bidders and with respect to the objects. This is true also for the SRE.

Second, as in the case of the SRE, any bivariate marginal distribution of the SSE, i.e., any distribution of bids on any given pair of objects, is uniform. To see this, denote by $F(X_{A},X_{B},X_{C})$ the probability that $\mu ^{\text {SSE}}$ is component-wise weakly smaller than $(X_{A},X_{B} ,X_{C})\in {\mathbb {R}}_{+}^{3}$. Thus, F is the distribution function of $\mu ^{\text {SSE}}$. Then, integrating out the last component, we obtain $F(X_{A},X_{B},1)=X_{A}X_{B}$, as follows directly from considering the projection of the probability distribution (5) on the first two coordinates. Thus, the bivariate marginal distributions of the SSE are indeed uniform on $[0,1]^{2}$.¹¹

Next, the expected payoff in the SSE is zero. Indeed, by symmetry, each bidder wins two or more objects with probability $\frac{1}{2}$, and therefore has an expected valuation of $\frac{1}{2}\cdot 2=1$. Moreover, each bidder wins any given object with probability $\frac{1}{2}$, and the winning bid corresponds in distribution to the maximum of two independent draws from the uniform distribution on the unit interval, so that the mean winning bid equals $\frac{2}{3}$, and the expected payment per bidder is $3\cdot \frac{1}{2} \cdot \frac{2}{3}=1$. Thus, bidders’ rents are entirely extracted not only in the SRE, but also in the SSE.

Finally, as in the case of the SRE, the pricing rule may be modified. For example, when any bid realization in $\mu ^{\text {SSE}}$ is multiplied with the factor two, one obtains an equilibrium in the second-prize auction. Indeed, when bids are distributed uniformly, the expected losing bid corresponds to one half of the winning bid (Szentes and Rosenthal 2003a). Similarly, an equilibrium in the all-pay auction may be found by replacing any bid realization in $\mu ^{\text {SSE}}$ by its second power (Szentes 2005; Kovenock and Roberson 2012).

4 Proof of Lemma 1

The idea of the proof is it to exploit the stationarity of the behavior strategy $\xi ^{\text {SSE}}$ as much as possible.

We start by deriving an explicit expression for the bidder’s expected payoff from playing an arbitrary pure strategy $x\in D$ against the behavior strategy $\xi ^{\text {SSE}}$ in the dynamic chopstick auction. Given two pure strategies $x=\{x(t)\}_{t=1}^{\infty }\in D$ and $\widehat{x}=\{\widehat{x}(t)\}_{t=1}^{\infty }\in D$ in the dynamic chopstick auction, we shall say that x weakly wins all the objects against $\widehat{x}$, in short $x\ge \widehat{x}$, if for all three objects $v=A,B,C$, the bid $x_{\nu }=\{x_{\nu }(t)\}_{t=1}^{\infty }$ either wins or ties against $\widehat{x}_{\nu }=\{\widehat{x}_{\nu }(t)\}_{t=1}^{\infty }$. We may then define, for the behavior strategy $\xi ^{\text {SSE}}$ in the dynamic chopstick auction, its “distribution function”

$$\begin{aligned} \Phi (x)=\text {pr}(\xi ^{\text {SSE}}\le x)\text {.} \end{aligned}$$

(7)

Then, noting that ties occur with probability zero, a bidder’s expected payoff from playing the pure strategy $x=(x_{A},x_{B},x_{C})\in D$ against the behavior strategy $\xi ^{\text {SSE}}$ may be expressed as

$$\begin{aligned} \Pi (x)&=2\{\Phi (x_{A},x_{B},1)+\Phi (x_{A},1,x_{C})+\Phi (1,x_{B} ,x_{C})-2\Phi (x)\}\nonumber \\&\quad -\,\rho (x_{A})\Phi (x_{A},1,1)-\rho (x_{B})\Phi (1,x_{B},1)-\rho (x_{C} )\Phi (1,1,x_{C})\text {.} \end{aligned}$$

(8)

Exploiting further the fact that all bivariate marginals of $\Phi$ are products of independent uniform distributions, as discussed in the previous section, Eq. (8) may be written alternatively as

$$\begin{aligned} \Pi (x)&=2\rho (x_{A})\rho (x_{B})+2\rho (x_{A})\rho (x_{C})+2\rho (x_{B} )\rho (x_{C})\nonumber \\&\quad -\,\rho (x_{A})^{2}-\rho (x_{B})^{2}-\rho (x_{C})^{2}-4\Phi (x). \end{aligned}$$

(9)

This is the desired explicit expression for a bidder’s expected payoff resulting from a pure-strategy deviation $x\in D$ in the dynamic chopstick auction.

Next, to exploit the stationarity of the behavior strategy $\xi ^{\text {SSE}}$, we note that any given pure strategy $x=\{x(t)\}_{t=1}^{\infty }\in D$ in the dynamic chopstick auction may be decomposed into a first-stage choice

$$\begin{aligned} x(1)\in D_{1}=\{0,1\}\times \{0,1\}\times \{0,1\}\text {,} \end{aligned}$$

(10)

and a shifted pure strategy

$$\begin{aligned} x^{+}=\{x^{+}(t)\}_{t=1}^{\infty }=\{x(t+1)\}_{t=1}^{\infty }\in D. \end{aligned}$$

(11)

This decomposition, which can be accomplished in an analogous fashion for any bid on an individual object, proves very useful for all that follows. For instance, one may readily check that $\rho$ satisfies the recursive relationship

$$\begin{aligned} \rho (x_{\nu })=\frac{x_{\nu }(1)+\rho (x_{\nu }^{+})}{2}\text {,} \end{aligned}$$

(12)

for any object $\nu \in \{A,B,C\}$ and for any pure strategy $x\in D$.

Simple recursive relationships can be derived now for the function $\Phi =\Phi (x)$, which will enable us to evaluate the sign of $\Pi (x)$. The following lemma states those relationships, where the symmetry of the behavior strategy $\xi ^{\text {SSE}}$ across objects allows restricting attention to a subset of values for the first-stage choice x(1).

Lemma 2

For any pure strategy $x\in D$ in the dynamic chopstick auction,

$$\begin{aligned} \Phi (x)=\frac{1}{4}\cdot \left\{ \begin{array} [c]{ll} \Phi (x^{+}) &{} \text {if }x(1)=(0,0,0)\\ &{} \\ \rho (x_{A}^{+})\rho (x_{B}^{+}) &{} \text {if }x(1)=(0,0,1)\\ &{} \\ \rho (x_{A}^{+})+\Phi (x^{+}) &{} \text {if }x(1)=(0,1,1)\\ &{} \\ 1+\rho (x_{A}^{+})\rho (x_{B}^{+})+\rho (x_{A}^{+})\rho (x_{C}^{+})+\rho (x_{B} ^{+})\rho (x_{C}^{+}) &{} \text {if }x(1)=(1,1,1)\text {.} \end{array} \right. \end{aligned}$$

(13)

Proof

Let $x\in D$ be an arbitrary pure strategy in the dynamic chopstick auction. As explained above, we may decompose x into a first-stage choice $x(1)\in D_{1}$ and a shifted pure strategy $x^{+}\in D$. The four cases in Eq. (13) are now dealt with one at a time:

Case 1 Suppose first that the first-period choice prescribed by the pure strategy x is $x(1)=(0,0,0)$. Intuitively, strategy x speculates on $\omega (1)$ realizing to $\omega _{0}$, because in all other cases, it becomes impossible to weakly win all three objects. Put more formally, x weakly wins all the objects against a specific realization $\widehat{x}\in D$ of the behavior strategy $\xi ^{\text {SSE}}$ if and only if the following two conditions hold: (i) the first-period choice prescribed by the realized pure strategy $\widehat{x}$ is $\widehat{x}(1)=(0,0,0)$, and (ii) the shifted strategy $x^{+}$ weakly wins all objects against the shifted realization

$$\begin{aligned} \widehat{x}^{+}=\{\widehat{x}^{+}(t)\}_{t=1}^{\infty }=\{\widehat{x}(t+1)\}_{t=1}^{\infty }\in D. \end{aligned}$$

(14)

But, by definition, the behavior strategy $\xi ^{\text {SSE}}$ is stationary, i.e., its realizations $\widehat{x}=\{\widehat{x}(t)\}_{t=1}^{\infty }\in D$ are distributed independently across stages. Therefore, the shifted realization $\widehat{x}^{+}$ follows the same stochastic distribution as $\widehat{x}$, viz. $\xi ^{\text {SSE}}$. Moreover, the shifted realizations $\widehat{x}^{+}$ are distributed independently from the first-period choice $\widehat{x}(1)$ prescribed by the realized pure strategy $\widehat{x}$. Hence, noting that $\widehat{x}(1)$ follows the distribution (5), we arrive at $\Phi (x)=\frac{1}{4}\cdot \Phi (x^{+})$, as claimed.

Case 2 Next, suppose that the first-period choice prescribed by the pure strategy x is $x(1)=(0,0,1)$. This case is similar to the previous one insofar that strategy x loses the possibility of winning all three objects unless $\omega (1)$ realizes to $\omega _{0}$. But, in contrast to the previous case, if indeed $\omega (1)=\omega _{0}$, then strategy x has already won object C at stage $t=1$, so that the allocation remains undetermined only for objects A and B. Hence, in this case, x weakly wins all three objects against a specific pure-strategy realization $\widehat{x}\in D$ from the distribution $\xi ^{\text {SSE}}$ if and only if the following two conditions hold: (i) the first-stage choice prescribed by $\widehat{x}$ satisfies $\widehat{x}(1)=(0,0,0)$, and (ii) the shifted realization $\widehat{x}^{+}$ satisfies $\widehat{x}^{+}\le (x_{A}^{+},x_{B}^{+},1)$. Exploiting again the stationarity of $\xi ^{\text {SSE}}$, it follows that

$$\begin{aligned} \Phi (x)=\frac{1}{4}\cdot \Phi (x_{A}^{+},x_{B}^{+},1)=\frac{\rho (x_{A}^{+} )\rho (x_{B}^{+})}{4}\text {.} \end{aligned}$$

(15)

Case 3 Suppose now that $x(1)=(0,1,1)$. Then, following the same reasoning as above, it can be checked that strategy x weakly wins all the objects against a specific realization $\widehat{x}\in D$ of the behavior strategy $\xi ^{\text {SSE}}$ if either (i) $\omega (1)=\omega _{0}$ and $\widehat{x}^{+}\le$ $(x_{A}^{+},1,1)$, or (ii) $\omega (1)=\omega _{1}$ and $\widehat{x}^{+}\le x^{+}$. Hence,

$$\begin{aligned} \Phi (x)=\frac{1}{4}\cdot \rho (x_{A}^{+})+\frac{1}{4}\cdot \Phi (x^{+})\text {,} \end{aligned}$$

(16)

as claimed.

Case 4 Finally, suppose that $x(1)=(1,1,1)$. In this case, it is obvious that strategy x weakly wins all the objects against a specific realization $\widehat{x}\in D$ of the behavior strategy $\xi ^{\text {SSE}}$ if $\omega (1)=\omega _{0}$. But strategy x likewise weakly wins all the objects if either (i) $\omega (1)=\omega _{1}$ and $\widehat{x}^{+}\le$ $(1,x_{B} ^{+},x_{C}^{+})$, or (ii) $\omega (1)=\omega _{2}$ and $\widehat{x}^{+}\le$ $(x_{A}^{+},1,x_{C}^{+})$, or (iii) $\omega (1)=\omega _{3}$ and $\widehat{x}^{+}\le$ $(x_{A}^{+},x_{B}^{+},1)$. The assertion follows now as before.

Since all cases have been covered, this proves relationship (13). $\square$

Next, returning to the proof of Lemma 1, it will be checked that there are no profitable deviations. As noted in the previous section, the expected payoff of $\xi ^{\text {SSE}}$ against itself is zero. Hence, a profitable deviation must yield a strictly positive expected payoff. One can check that the dynamic chopstick auction is not continuous at infinity (Fudenberg and Tirole 1991, p. 110), so that the one-stage deviation principle cannot be invoked. Fortunately, however, the arguments remain manageable because of the stationarity of $\xi ^{\text {SSE}}$. The following cases need to be considered.

Case A Suppose first that a pure strategy $x\in D$ exists such that

$$\begin{aligned} x(1)\in S_{1}^{*}\equiv \{(0,0,0),(0,1,1),(1,0,1),(0,1,1)\}\text {,} \end{aligned}$$

(17)

and such that $\Pi (x)>0$. Thus, intuitively, there is a profitable deviation that does not start right away, but only at a later stage. Then, in any of these cases, a straightforward calculation using Lemma 2 as well as Eqs. (9) and (12) delivers $\Pi (x)=\frac{1}{4}\cdot \Pi (x^{+})$. For example, if $x(1)=(0,1,1)$, then

$$\begin{aligned} \Pi (x)&=\frac{\rho (x_{A}^{+})(1+\rho (x_{B}^{+}))}{2}+\frac{\rho (x_{A} ^{+})(1+\rho (x_{C}^{+}))}{2}+\frac{(1+\rho (x_{B}^{+}))(1+\rho (x_{C}^{+}))}{2}\nonumber \\&-\frac{\rho (x_{A}^{+})^{2}}{4}-\frac{(1+\rho (x_{B}^{+}))^{2}}{4} -\frac{(1+\rho (x_{C}^{+}))^{2}}{4}-\rho (x_{A}^{+})-\Phi (x^{+})\text {.} \end{aligned}$$

(18)

Collecting terms, we find that, indeed,

$$\begin{aligned} \Pi (x)&=\frac{\rho (x_{A}^{+})\rho (x_{B}^{+})}{2}+\frac{\rho (x_{A}^{+} )\rho (x_{C}^{+})}{2}+\frac{\rho (x_{B}^{+})\rho (x_{C}^{+})}{2}\nonumber \\&-\frac{\rho (x_{A}^{+})^{2}}{4}-\frac{\rho (x_{B}^{+})^{2}}{4}-\frac{\rho (x_{C}^{+})^{2}}{4}-\Phi (x^{+}) \end{aligned}$$

(19)

$$\begin{aligned}&=\frac{1}{4}\cdot \Pi (x^{+})\text {.} \end{aligned}$$

(20)

The other cases are similar. Thus, even though there is no discounting, delaying a profitable deviation would only lower expected payoffs. Conversely, this shows that the deviation $x^{+}\in D$, if used from stage $t=1$ onwards, would magnify the strictly positive expected payoff from strategy x by the factor 4. Iterating this argument, if necessary, and using the fact that expected payoffs in the chopstick auction are bounded, we find after finitely many applications of the shift operator that there necessarily exists also a profitable pure-strategy deviation $\widehat{x}\in D$ that does not satisfy (17). Thus, it suffices to consider the remaining cases.

Case B Suppose next that

$$\begin{aligned} x(1)\in \{(1,0,0),(0,1,0),(0,0,1)\}. \end{aligned}$$

(21)

By renaming the objects, if necessary, one may assume without loss of generality that $x(1)=(0,0,1)$. But then, using Eqs. (9) and (12), as well as Lemma 2, one obtains

$$\begin{aligned} \Pi (x)&=\frac{\rho (x_{A}^{+})\rho (x_{B}^{+})}{2}+\frac{\rho (x_{A} ^{+})(1+\rho (x_{C}^{+}))}{2}+\frac{\rho (x_{B}^{+})(1+\rho (x_{C}^{+}))}{2}\nonumber \\&\quad -\frac{\rho (x_{A}^{+})^{2}}{4}-\frac{\rho (x_{B}^{+})^{2}}{4}-\frac{\left( 1+\rho (x_{C}^{+})\right) ^{2}}{4}-\rho (x_{A}^{+})\rho (x_{B}^{+}) \end{aligned}$$

(22)

$$\begin{aligned}&=(-\frac{1}{4})\cdot (\rho (x_{A}^{+})+\rho (x_{B}^{+})-\rho (x_{C}^{+} )-1)^{2} \end{aligned}$$

(23)

$$\begin{aligned}&\le 0\text {.} \end{aligned}$$

(24)

Thus, there is no profitable deviation x satisfying (21).¹²

Case C Finally, consider the case where

$$\begin{aligned} x(1)=(1,1,1)\text {.} \end{aligned}$$

(25)

In this case, one again makes use of Eqs. (9) and (12) as well as of Lemma 2, and finds

$$\begin{aligned} \Pi (x)&=\frac{(1+\rho (x_{A}^{+}))(1+\rho (x_{B}^{+}))}{2}\nonumber \\&\quad +\,\frac{(1+\rho (x_{A}^{+}))(1+\rho (x_{C}^{+}))}{2}\nonumber \\&\quad +\,\frac{(1+\rho (x_{B}^{+}))(1+\rho (x_{C}^{+}))}{2}\nonumber \\&\quad -\,\frac{(1+\rho (x_{A}^{+}))^{2}}{4}-\frac{(1+\rho (x_{B}^{+}))^{2}}{4} -\,\frac{(1+\rho (x_{C}^{+}))^{2}}{4}\nonumber \\&\quad -\,1-\rho (x_{A}^{+})\rho (x_{B}^{+})-\rho (x_{A}^{+})\rho (x_{C}^{+})-\rho (x_{B}^{+})\rho (x_{C}^{+})\text {.} \end{aligned}$$

(26)

Rearranging yields

$$\begin{aligned} \Pi (x)=\left( -\frac{1}{4}\right) \cdot \left( \rho \left( x_{A}^{+}\right) +\rho \left( x_{B}^{+}\right) +\rho \left( x_{C} ^{+}\right) -1\right) ^{2}\le 0\text {.} \end{aligned}$$

(27)

Hence, it is weakly suboptimal to use a pure strategy $x\in D$ satisfying (25) against $\xi ^{\text {SSE}}$.

Since there is no profitable pure-strategy deviation, the behavior strategy $\xi ^{\text {SSE}}$ defines a symmetric equilibrium in the dynamic chopstick auction. This completes the proof of Lemma 1. $\square$

5 Analysis of the best-response set

This section discusses issues related to the dimensionality of the SSE. More precisely, we will follow Szentes and Rosenthal (2003a) in comparing the respective dimensions of the equilibrium support and the best-response set. For the SRE, the equilibrium support has dimension 2, which is strictly smaller than the dimension of the corresponding best-response set, which is 3. To deal with the SSE, obviously, the traditional definition of dimensionality in terms of degrees of freedom, which is very suitable for smooth objects such as simplices and manifolds, needs to be extended. Below, we shall therefore make use of a more general notion of dimensionality.

We first recall the notion of the Hausdorff dimension.¹³ Given a bounded subset $S\subseteq {\mathbb {R}} ^{L}$, with $L\ge 1$, and some nonnegative real number $d\ge 0$, the d -dimensional Hausdorff content of S is defined as the infimum of the set of numbers $\delta \ge 0$ such that there exist sequences $\{z_{n}\}_{n=1}^{\infty }$ in ${\mathbb {R}} ^{L}$ and $\{r_{n}\}_{n=1}^{\infty }$ in ${\mathbb {R}}_{++}$ such that (i) for any $z\in S$, there is some index n such that $\left| z-z_{n}\right| \le r_{n}$, and (ii) $\sum _{n=1}^{\infty } r_{n}^{d}<\delta$. The Hausdorff dimension of S, denoted by $\dim _{H}(S)$, is the infimum of all d for which the d-dimensional Hausdorff content of S is zero.

Let $S^{*}$ denote the support of the equilibrium bid distribution $\mu ^{\text {SSE}}$. One can convince oneself that the set $S^{*}$ consists precisely of those bid vectors $X=(X_{A},X_{B},X_{C})\in {\mathbb {R}}_{+}^{3}$ that are contained in the component-wise image of the support of $\widetilde{\xi }^{\text {SSE}}$ under the mapping $\rho$.¹⁴ Thus, the set $S^{*}$ is the popular self-similar structure known as the Sierpinski tetrahedron. Rather than offering a formal description, we will provide a geometric description of $S^{*}$. The Sierpinski tetrahedron may be constructed from its solid counterpart by first carving out a regular octahedron (see Fig. 1), then repeating that task on each of the resulting four smaller tetrahedra, and finally iterating this step at infinitum.

The set $S^{*}$ is compact and of the same cardinality as the unit cube $[0,1]^{3}$, but its Lebesgue measure is zero, and it is not dense in any non-degenerate interval. The Hausdorff dimension of the Sierpinski tetrahedron $S^{*}$ is

$$\begin{aligned} \dim _{H}(S^{*})=\frac{\ln 4}{\ln 2}=2\text {,} \end{aligned}$$

(28)

as follows from standard results on the dimensionality of self-similar sets (see, e.g., Falconer 2014, Theorem 9.3; cf. also Kvasov 2007). Since the Sierpinski tetrahedron contains its four outer vertices, the convex hull of $S^{*}$ is just the solid tetrahedron-shaped best-response set considered by Szentes and Rosenthal (2003a).

Fig. 1

Construction of the Sierpinski tetrahedron

We can show now the following:

Proposition 2

In the simultaneous chopstick auction, the set of pure best responses to $\mu ^{\text {SSE}}$ has Hausdorff dimension two.

Proof

As seen in Sect. 4, a pure best response $x\in D$ to $\xi ^{\text {SSE}}$ in the dynamic chopstick auction is either a pure strategy in the support of $\xi ^{\text {SSE}}$, or a finite sequence in the set

$$\begin{aligned} S_{1}^{*}=\{(0,0,0),(0,1,1),(1,0,1),(0,1,1)\}\text {,} \end{aligned}$$

(29)

followed by a pure strategy $\widehat{x}\in D$ such that either, up to a renaming of objects, $\widehat{x}(1)=(0,0,1)$ and

$$\begin{aligned} \rho (\widehat{x}_{A}^{+})+\rho (\widehat{x}_{B}^{+})-\rho (\widehat{x}_{C} ^{+})-1=0\text {,} \end{aligned}$$

(30)

or $\widehat{x}(1)=(1,1,1)$ and

$$\begin{aligned} \rho (\widehat{x}_{A}^{+})+\rho (\widehat{x}_{B}^{+})+\rho (\widehat{x}_{C} ^{+})-1=0. \end{aligned}$$

(31)

In the former case, relationship (12) implies

$$\begin{aligned} \rho (\widehat{x}_{A})=\frac{\rho (\widehat{x}_{A}^{+})}{2}\text {, } \rho (\widehat{x}_{B})=\frac{\rho (\widehat{x}_{B}^{+})}{2}\text {, and } \rho (\widehat{x}_{C})=\frac{1+\rho (\widehat{x}_{C}^{+})}{2}\text {,} \end{aligned}$$

(32)

so that Eq. (30) becomes equivalent to

$$\begin{aligned} \rho (\widehat{x}_{A})+\rho (\widehat{x}_{B})=\rho (\widehat{x}_{C})\text {,} \end{aligned}$$

(33)

where

$$\begin{aligned} \rho (\widehat{x}_{A})\le \frac{1}{2}\text {, }\rho (\widehat{x}_{B})\le \frac{1}{2}\text {, and }\rho (\widehat{x}_{C})\ge \frac{1}{2}. \end{aligned}$$

In the latter case,

$$\begin{aligned} \rho (\widehat{x}_{A})=\frac{1+\rho (\widehat{x}_{A}^{+})}{2}\text {, } \rho (\widehat{x}_{B})=\frac{1+\rho (\widehat{x}_{B}^{+})}{2}\text {, and } \rho (\widehat{x}_{C})=\frac{1+\rho (\widehat{x}_{C}^{+})}{2}\text {,} \end{aligned}$$

(34)

so that Eq. (31) is equivalent to

$$\begin{aligned} \rho (\widehat{x}_{A})+\rho (\widehat{x}_{B})+\rho (\widehat{x}_{C})=2\text {,} \end{aligned}$$

(35)

where

$$\begin{aligned} \rho (\widehat{x}_{A})\ge \frac{1}{2}\text {, }\rho (\widehat{x}_{B})\ge \frac{1}{2}\text {, and }\rho (\widehat{x}_{C})\ge \frac{1}{2}. \end{aligned}$$

(36)

Moreover, the best-response set in the simultaneous chopstick auction is the image under the component-wise application of the mapping $\rho$ of the best-response set in the dynamic auction. Thus, invoking some geometric intuition, the best-response set of the SSE may be thought of as adding to the equilibrium support the four faces of each of the tetrahedra considered during the iterative construction of the Sierpinski tetrahedron. The set of best responses to $\mu ^{\text {SSE}}$ is, therefore, the denumerable union of two-dimensional sets, and as such, two-dimensional. $\square$

Thus, in contrast to the SRE, the best-response set of the SSE is indeed of the same dimension as its equilibrium support. Still, it is hard to tell in the abstract if this property makes it more likely that a process favoring better or best responses would lead to the SSE rather than to the SRE.¹⁵

6 Relationship to the literature on “fractal” solutions

In this section, it will be shown that the SSE may be characterized as a measure invariant under a simple replacement operation. This way, we can also explain how the SSE relates to “fractal” solutions considered in prior work on the Blotto game.

Consider the following four contraction mappings on the unit cube $[0,1]^{3}$:

$$\begin{aligned} C_{0}(X)&=\frac{1}{2}X \end{aligned}$$

(37)

$$\begin{aligned} C_{1}(X)&=\frac{1}{2}\left\{ X+(0,1,1)\right\} \end{aligned}$$

(38)

$$\begin{aligned} C_{2}(X)&=\frac{1}{2}\left\{ X+(1,0,1)\right\} \end{aligned}$$

(39)

$$\begin{aligned} C_{3}(X)&=\frac{1}{2}\left\{ X+(1,1,0)\right\} \end{aligned}$$

(40)

Then, by construction, $\mu ^{\text {SSE}}$ is an invariant measure (Hutchinson 1981) with respect to the above family of contractions $\{C_{k}\}_{k=1}^{4}$. In other words, the probability distribution $\mu ^{\text {SSE}}$ is identical to the equally-weighted convex combination of the four image measures of $\mu ^{\text {SSE}}$ with respect to the contractions (37)–(40). This property can actually be used to characterize the SSE.

Proposition 3

The probability distribution $\mu ^{\text {SSE}}$ is characterized by the property that it is invariant with respect to the family of contractions $\{C_{k}\}_{k=1}^{4}$ .

Proof

The claim follows immediately from the fact that the invariant measure is unique (Hutchinson 1981, Sec. 4). $\square$

The relationship to existing work on “fractal” solutions will be discussed now. Gross and Wagner (1950) constructed new classes of equilibria of Colonel Blotto games by replacing a given hexagon in the hexagonal solution by a convex combination of six smaller replicas. Iterating this replacement operation a finite number of times, absolutely continuous bid distributions of arbitrary geometric complexity (the so-called snowflake solutions) have be constructed. The main purpose of such constructions, however, was it to show that solutions exist with a support of Lebesgue measure smaller than any given $\varepsilon >0$. It was also noted that the respective smallest building blocks in this construction, obtained after a finite number of operations, may be replaced by suitably demagnified disk solutions.¹⁶

More recently, the same approach of iteratively deriving new equilibria from existing ones has been used by Kvasov (2007) to construct “fractal” solutions to Colonel Blotto games with costly resources. Thereby, it has been shown that, also in this case, there are solutions with the property that the support of the symmetric equilibrium strategy has an arbitrarily small but positive Lebesgue measure. The family of contractions (37)–(40) considered above for the chopstick auction is obviously a variant of the Gross–Wagner–Kvasov replacement operation for Blotto games.

However, it remains an open question whether a finite iteration of applying the replacement operation (37)–(40) to the SRE would similarly lead to new classes of equilibria in the chopstick auction. Indeed, while the equilibrium property in a Blotto game may be verified quite easily by checking that univariate marginals are uniform (Roberson 2006), no such simple test is available in the case of the chopstick auction. Instead, geometric considerations of substantial complexity would be needed.¹⁷ In particular, the results of the present paper do not easily follow from existing work.¹⁸

7 Conclusion

A new type of equilibrium has been identified for an important prototype model of the simultaneous auction, the so-called chopstick auction. A somewhat unusual aspect of the equilibrium bid distribution is that it may be characterized as a self-similar probability measure. Even though similar “fractal” solutions have been constructed before in the class of Blotto games and in games with rational payoff functions, this possibility was (to the author’s knowledge) not a well-known feature of the class of simultaneous auctions. The observation must, therefore, be added, to the collection of perplexing properties of this interesting class of auctions.

It is tempting to consider any “fractal” solution as irrelevant on the grounds that it is too complicated. The analysis above has shown that this conclusion might be unwarranted. After all, using the dynamic transcription of the simultaneous auction, the self-similar equilibrium constructed in the body of the present paper may be described in simple and intuitive terms. Moreover, there is some evidence (work in progress) that the theoretical robustness property established in the present paper actually matters for numerical computations of the equilibrium strategy, which is also consistent with the prediction of Szentes and Rosenthal (2003b). Thus, the self-similar equilibrium may, paradoxically perhaps, be thought of as being both simpler and more robust than the known solution.

There are large classes of games in political economy, including in particular the interesting class of majority auctions, that may be seen as direct generalizations of the two-bidder three-object auction and for which, in some important special cases, essentially nothing is known about the equilibrium set (cf. Szentes and Rosenthal 2003b). Unfortunately, a direct extension of the methods developed in the present paper is not fruitful. For example, in a majority auction with five objects, raising the bids dynamically on a randomly selected subset of, say, three objects does not constitute an equilibrium. Therefore, more refined methods are necessary to construct equilibria in those games. A more or less obvious case in which the methods developed in the present paper can actually be used to construct new and interesting equilibria is the class of continuous Colonel Blotto and Colonel Lotto games.¹⁹ However, elaborating further on this extension would go beyond the scope of the present paper. We hope to be able to document these findings more explicitly in future research.