value $9/4$ with probability $94/100$; for any other $i^{\prime}\neq i,j$,
$F_{ji^{\prime}}$ is the discrete distribution that assumes value $0$ with
probability $1$. At the same time, $i$’s subjective prior is given by:
$F_{ij}$ is the discrete distribution that assumes value $0$ with probability
$6/100$ and value $9/4$ with probability $94/100$; for any other
$j^{\prime}\neq i,j$, $F_{ij^{\prime}}$ is the discrete distribution that
assumes value $0$ with probability $1$.

Using the analysis from Section C.1.1, we can list all the best-responses of
$j$ in a potential PBNE:

$i$’s strategy |  $j$’s best-response
---|---
$(0,0,x)$ | $(0,1,1)$
$(0,1,x)$ | $(0,1,2)$
$(0,2,x)$ | $(0,2,3)$
$(0,3,x)$ | $(0,1,3)$

Table 1: Bidder $j$’s best-responses given $i$’s strategies

Also, from previous sections, we know that there are no other strategies that
result in utility are within $\varepsilon=1/18$ of that of the best-responses.
It is evident that, due to the symmetric nature of the input gadget, the best-
responses of $i$ to the strategies of $j$ are symmetrical to the ones in the
above table. Therefore, in all PBNE $i$ and $j$ would have to play the same
strategy, which would be either $s_{0}$ or $s_{1}$, thus yielding the intended
behaviour of the circuit’s input gates.

######  Lemma C.4.

If $i$ and $j$ are the bidders corresponding to some input of the circuit (as
described in the construction of the input gadget), then, in all
$\varepsilon$-PBNE for $\varepsilon\in[0,1/18)$, $i$ and $j$ both play the
same strategy, which can be either $s_{0}$ or $s_{1}$.

Combining Lemmas C.1 to C.4, we deduce the following:

######  Corollary C.5.

Using the above mapping from a circuit to a DFPA, all induced bidders are
simultaneously $\varepsilon$-best-responding (for $\varepsilon\in[0,1/18)$) to
each other if and only if the values that their strategies map to satisfy the
gates of the circuit.

###  C.3 Output Gadget

Thus far, our construction ensures that at a PBNE it is necessary that all the
gates are correctly simulated. As we are reducing from the Circuit-SAT
problem, we want a PBNE to exist only in cases where the output of the circuit
can take _true_ as a value. This leads us to the last gadget of our
construction - the _output_ gadget. This introduces two new bidders to the
auction, $k$ and $\ell$, which (given their subjective priors, which assume
value $0$ with probability $1$ for every bidder other than each other) cannot
play best-responses simultaneously. Then, we also add $k$’s prior distribution
for bidder $i$ (the bidder corresponding to the output of the circuit), such
that now the bidders can simultaneously play $\varepsilon$-best-responses if
and only if bidder $i$’s strategy represents the value _true_.

Next, we provide the details of the construction of the output gadget. We
introduce the two new bidders $k$ and $\ell$ with the following prior
distributions: $F_{k\ell}$ and $F_{\ell k}$ are discrete distributions that
assume value $0$ with probability $8/11$ and value $10$ with probability
$3/11$. Bidder $k$’s prior for bidder $i$ (corresponding to the circuit’s
output) is $F_{ki}$, the discrete distribution that assumes value $0$ with
probability $1/2$ and value $9/4$ with probability $1/2$. For any other
$k^{\prime}\neq k,\ell$ and $\ell^{\prime}\neq k,\ell,i$, $F_{\ell
k^{\prime}}$ and $F_{k\ell^{\prime}}$ are discrete distributions that assume
value $0$ with probability $1$.

We will begin our analysis by calculating bidder $\ell$’s best-responses
depending on $k$’s strategies. Note that, since $F_{\ell k}$ only has mass at
$0$ and $10$, it doesn’t matter what $\hat{\beta}_{k}(9/4)$ is for strategy
$\hat{\beta}_{k}$, hence we will denote this as $x$ in our analysis. As our
aim is to compare how $k$ and $\ell$ best-respond to each other, and the
subjective prior of each puts positive probability only on $0$ and $10$, we
will only analyse what $u_{\ell}(b;10)$ will be. We begin by noting that all
of $\ell$’s best-responses must satisfy $\hat{\beta}_{\ell}(0)=0$, due to the
no-overbidding assumption. Then:

  1. 1.

Suppose bidder $k$ plays some strategy of the form $(0,x,0)$. We can compute
the winning probabilities and utilities for bidder $\ell$ when bidding $0$,
$1$, $2$, or $3$ and having value $10$:

$b$ | $0$ | $1$ | $2$ | $3$
---|---|---|---|---
$H_{\ell}(b)$ | $\frac{1}{n}$ | $1$ | $1$ | $1$
$u_{\ell}(b;10)$ | $\frac{10}{n}$ | $9$ | $8$ | $7$

Since $n\geq 2$, we have the bound $u_{\ell}(0;10)\leq 5$. Comparing the
values in the table, we conclude that it is optimal for bidder $\ell$ to bid
$\hat{\beta}_{\ell}(10)=1$. Also, we can see that there is no other
$\varepsilon$-best-response for $\varepsilon<\frac{1}{18}$.

  2. 2.

Suppose bidder $k$ plays some strategy of the form $(0,x,1)$. We can compute
the winning probabilities and utilities for bidder $\ell$ when bidding $0$,
$1$, $2$, or $3$ and having value $10$:

$b$ | $0$ | $1$ | $2$ | $3$
---|---|---|---|---
$H_{\ell}(b)$ | $\frac{8}{11n}$ | $\frac{19}{22}$ | $1$ | $1$
$u_{\ell}(b;10)$ | $\frac{80}{11n}$ | $\frac{171}{22}$ | $8$ | $7$

Since $n\geq 2$, we have the bound $u_{\ell}(0;10)\leq\frac{40}{11}$.
Comparing the values in the table, we conclude that it is optimal for bidder
$\ell$ to bid $\hat{\beta}_{\ell}(10)=2$. Also, we can see that there is no
other $\varepsilon$-best-response for $\varepsilon<\frac{1}{18}$.

  3. 3.

Suppose bidder $k$ plays some strategy of the form $(0,x,2)$. We can compute
the winning probabilities and utilities for bidder $\ell$ when bidding $0$,
$1$, $2$, or $3$ and having value $10$:

$b$ | $0$ | $1$ | $2$ | $3$
---|---|---|---|---
$H_{\ell}(b)$ | $\frac{8}{11n}$ | $\frac{8}{11}$ | $\frac{19}{22}$ | $1$
$u_{\ell}(b;10)$ | $\frac{80}{11n}$ | $\frac{72}{11}$ | $\frac{76}{11}$ | $7$

Since $n\geq 2$, we have the bound $u_{\ell}(0;10)\leq\frac{40}{11}$.
Comparing these values, we conclude that it is optimal for bidder $l$ to bid
$\hat{\beta}_{l}(9/4)=1$, $\hat{\beta}_{l}(10)=3$. Also, we can see that there
is no other $\varepsilon$-best-response for $\varepsilon<\frac{1}{18}$.

  4. 4.

Suppose bidder $k$ plays some strategy of the form $(0,x,3)$. We can compute
the winning probabilities and utilities for bidder $\ell$ when bidding $0$,
$1$, $2$, or $3$ and having value $10$:

$b$ | $0$ | $1$ | $2$ | $3$
---|---|---|---|---
$H_{\ell}(b)$ | $\frac{8}{11n}$ | $\frac{8}{11}$ | $\frac{8}{11}$ | $\frac{19}{22}$
$u_{\ell}(b;10)$ | $\frac{80}{11n}$ | $\frac{72}{11}$ | $\frac{64}{11}$ | $\frac{133}{22}$

Since $n\geq 2$, we have the bound $u_{\ell}(0;10)\leq\frac{40}{11}$.
Comparing these values, we conclude that it is optimal for bidder $\ell$ to
bid $\hat{\beta}_{\ell}(10)=1$. Also, we can see that there is no other
$\varepsilon$-best-response for $\varepsilon<\frac{1}{18}$.

We can note that $k$’s strategy at an equilibrium (from $\ell$’s point of
view) can be represented by just $\hat{\beta}_{k}(10)$, since
$\hat{\beta}_{k}(0)=0$ at all PBNE due to the no-overbidding assumption. We
can do the same thing for $\ell$, since $k$’s prior for her has mass at a
point other than $0$, and that is at $10$, so we get the following table
representing $\ell$’s best-responses to $k$:

$\hat{\beta}_{k}(10)$ | $0$ | $1$ | $2$ | $3$
---|---|---|---|---
$\hat{\beta}_{\ell}(10)$ | $1$ | $2$ | $3$ | $1$

Table 2: Bidder $\ell$’s best-responses to bidder $k$’s strategies

We will now look at $k$’s best-response. Since $k$ has a non-zero prior for
both $i$ and $\ell$, her best-response will depend on two other bidders,
resulting in more cases. We begin our analysis with the ones where $i$ plays
$(0,1,2)$. Our goal is to show that none of them can lead to a PBNE of the
DFPA. It is also safe to assume that, at all PBNE, $i$ plays either $(0,1,2)$
or $(0,2,3)$, using the analysis of the simulation of the circuit’s gates, as
$i$ corresponds to the output of the circuit. Start by fixing $i$’s strategy
to $s_{0}=(0,1,2)$. By the no-overbidding assumption, $k$’s best-response must
satisfy $\hat{\beta}_{k}(0)=0$. Then, we consider the following cases:

  1. 1.

Suppose bidder $\ell$ plays some strategy of the form $(0,x,0)$. We can
compute the winning probabilities and utilities for bidder $k$ when bidding
$0$, $1$, $2$, or $3$ and having value $10$:

$b$ | $0$ | $1$ | $2$ | $3$
---|---|---|---|---
$H_{k}(b)$ | $\frac{1}{2n}$ | $\frac{3}{4}$ | $1$ | $1$
$u_{k}(b;10)$ | $\frac{5}{n}$ | $\frac{27}{4}$ | $8$ | $7$

Since $n\geq 3$, we have the bound $u_{k}(0;10)\leq\frac{5}{3}$. Comparing the
values in the table, we conclude that it is optimal for bidder $k$ to bid
$\hat{\beta}_{k}(10)=2$.

  2. 2.

Suppose bidder $\ell$ plays some strategy of the form $(0,x,1)$. We can
compute the winning probabilities and utilities for bidder $k$ when bidding
$0$, $1$, $2$, or $3$ and having value $10$:

$b$ | $0$ | $1$ | $2$ | $3$
---|---|---|---|---
$H_{k}(b)$ | $\frac{4}{11n}$ | $\frac{29}{44}$ | $1$ | $1$
$u_{k}(b;10)$ | $\frac{40}{11n}$ | $\frac{261}{44}$ | $8$ | $7$

Since $n\geq 3$, we have the bound $u_{k}(0;10)\leq\frac{40}{33}$. Comparing
the values in the table, we conclude that it is optimal for bidder $k$ to bid
$\hat{\beta}_{k}(10)=2$. Also, we can see that there is no other
$\varepsilon$-best-response for $\varepsilon<\frac{1}{18}$.

  3. 3.

Suppose bidder $\ell$ plays some strategy of the form $(0,x,2)$. We can
compute the winning probabilities and utilities for bidder $k$ when bidding
$0$, $1$, $2$, or $3$ and having value $10$:

$b$ | $0$ | $1$ | $2$ | $3$
---|---|---|---|---
$H_{k}(b)$ | $\frac{4}{11n}$ | $\frac{6}{11}$ | $\frac{19}{22}$ | $1$
$u_{k}(b;10)$ | $\frac{40}{11n}$ | $\frac{72}{11}$ | $\frac{76}{11}$ | $7$

Since $n\geq 3$, we have the bound $u_{k}(0;10)\leq\frac{40}{33}$. Comparing
the values in the table, we conclude that it is optimal for bidder $k$ to bid
$\hat{\beta}_{k}(10)=3$. Also, we can see that there is no other
$\varepsilon$-best-response for $\varepsilon<\frac{1}{18}$.

  4. 4.

Suppose bidder $\ell$ plays some strategy of the form $(0,x,3)$. We can
compute the winning probabilities and utilities for bidder $k$ when bidding
$0$, $1$, $2$, or $3$ and having value $10$:

$b$ | $0$ | $1$ | $2$ | $3$
---|---|---|---|---
$H_{k}(b)$ | $\frac{4}{11n}$ | $\frac{6}{11}$ | $\frac{8}{11}$ | $\frac{19}{22}$
$u_{k}(b;10)$ | $\frac{40}{11n}$ | $\frac{54}{11}$ | $\frac{64}{11}$ | $\frac{133}{22}$

Since $n\geq 3$, we have the bound $u_{k}(0;10)\leq\frac{65}{33}$. Comparing
the values in the table, we conclude that it is optimal for bidder $k$ to bid
$\hat{\beta}_{k}(10)=3$. Also, we can see that there is no other
$\varepsilon$-best-response for $\varepsilon<\frac{1}{18}$.

Hence, $k$’s ($\varepsilon$-) best-responses to $\ell$’s strategies when $i$
plays $(0,1,2)$ are the ones demonstrated in the following table:

$\hat{\beta}_{\ell}(10)$ | $0$ | $1$ | $2$ | $3$
---|---|---|---|---
$\hat{\beta}_{k}(10)$ | $2$ | $2$ | $3$ | $3$

Table 3: Bidder $k$’s best-responses given $\ell$’s strategies when $i$ plays
$(0,1,2)$

Comparing this table with the one describing $\ell$’s best-responses, we can
easily see that there is no equilibrium when $i$ plays $(0,1,2)$. We now
examine the case where $i$ plays $(0,2,3)$. It suffices to show that there is
some strategy of $\ell$ for which $k$’s best-response leads to both playing
best-responses simultaneously. To this end, we consider the case where $\ell$
plays some strategy $(0,x,1)$. Then, $k$’s utility for each possible bid is
the following:

$b$ | $0$ | $1$ | $2$ | $3$
---|---|---|---|---
$H_{k}(b)$ | $\frac{4}{11n}$ | $\frac{19}{44}$ | $\frac{3}{4}$ | $1$
$u_{k}(b;10)$ | $\frac{40}{11n}$ | $\frac{171}{44}$ | $6$ | $7$

Since $n\geq 3$, we have the bound $u_{k}(0;10)\leq\frac{40}{33}$. Comparing
the values in the table, we conclude that it is optimal for bidder $k$ to bid
$\hat{\beta}_{k}(10)=3$. Also, we can see that there is no other
$\varepsilon$-best-response for $\varepsilon<\frac{1}{18}$. Consequently,
there is a strategy profile with $k$ and $\ell$ simultaneously playing best-
responses, where $\ell$ plays some strategy $(0,x,1)$ and $k$ plays some
strategy $(0,x^{\prime},3)$. This concludes our proof of the following lemma:

######  Lemma C.6.

Given the construction of the output gadget, agents $k$ and $\ell$ can best-
respond to every agent simultaneously if and only if the bidder corresponding
to the output of the circuit plays the strategy $s_{1}=(0,2,3)$.

Combining the results of Sections C.1 to C.3, we complete the proof of the NP-
hardness result. Note that this will hold for $1/10$ of the value of
$\varepsilon$ we used in the reduction, due to the scaling argument that we
mentioned in the beginning of Appendix C. We will demonstrate that there is a
satisfying assignment to the circuit’s inputs if and only if there is a PBNE
in the resulting DFPA.

Assume the circuit is satisfiable and let $\bm{\alpha}$ be a satisfying
assignment to it inputs. Then, using Corollary C.5 and Lemma C.6, the
resulting DFPA has an exact PBNE where for each input $\alpha_{i}$ to the
circuit, the corresponding bidders $i$ and $j$ (as described in Section C.2)
both play strategy $s_{0}$ if ${\alpha_{i}}=\text{false}$, and $s_{1}$
otherwise.

If on the other hand the circuit is unsatisfiable, then the output bidder
would always play $s_{0}$ in order to best-respond to the previous bidders
while satisfying the circuit’s gates, so there can be no $\varepsilon$-PBNE in
the resulting DFPA, due to Lemma C.6. This concludes our proof of NP-hardness
in the auction we introduced for $\varepsilon=\frac{1}{18}$, thus yielding NP-
hardness for $\varepsilon=\frac{1}{180}$ in the original auction.

##  Appendix D PPAD-Hardness of Finding Mixed Equilibria

In this section, we prove the following result:

######  Theorem D.1.

For any $\varepsilon<1/36$, it is PPAD-hard to compute an $\varepsilon$-well-
supported MBNE in a DFPA, even when the auction has interaction degree bounded
by $d=2$.

By Lemma 4.1 we also obtain the following.

######  Corollary D.2.

For any $\varepsilon<1/(3^{4}\cdot 2^{8})$, it is PPAD-hard to compute an
$\varepsilon$-approximate MBNE in a DFPA.

###  D.1 The Pure-Circuit Problem

An instance of the Pure-Circuit problem is given by a node set $X$ and a set
$G$ of gates. Each gate $g\in G$ is of the form $g=(T,x,y,z)$ where $x,y,z\in
X$ are distinct nodes, and
$T\in\\{\textup{{NOT}},\textup{{AND}},\textup{{PURIFY}}\\}$ is the type of the
gate, with the following interpretation.

  * —

If $T=\textup{{NOT}}$, then $x$ is the input of the gate, and $y$ is its
output. ($z$ is unused)

  * —

If $T=\textup{{AND}}$, then $x$ and $y$ are the inputs of the gate, and $z$ is
its output.

  * —

If $T=\textup{{PURIFY}}$, then $x$ is the input of the gate, and $y$ and $z$
are its outputs.

We require that each node is the output of exactly one gate.

A solution to instance $(X,G)$ is an assignment
$\bm{\mathrm{A}}:X\to\\{0,1,\bot\\}$ that satisfies all the gates, i.e., for
each gate $g=(T,x,y,z)\in G$ we have the following.

  * —

If $T=\textup{{NOT}}$ in $g=(T,x,y)$, then $\bm{\mathrm{A}}$ satisfies

$\displaystyle\bm{\mathrm{A}}[x]=0\implies\bm{\mathrm{A}}[y]=1$
$\displaystyle\bm{\mathrm{A}}[x]=1\implies\bm{\mathrm{A}}[y]=0.$

  * —

If $T=\textup{{AND}}$ in $g=(T,x,y,z)$, then $\bm{\mathrm{A}}$ satisfies

$\displaystyle\bm{\mathrm{A}}[x]=\bm{\mathrm{A}}[y]=1$
$\displaystyle\implies\bm{\mathrm{A}}[z]=1$
$\displaystyle\bm{\mathrm{A}}[x]=0\lor\bm{\mathrm{A}}[y]=0$
$\displaystyle\implies\bm{\mathrm{A}}[z]=0.$

  * —

If $T=\textup{{PURIFY}}$, then $\bm{\mathrm{A}}$ satisfies

$\displaystyle\\{\bm{\mathrm{A}}[y],\bm{\mathrm{A}}[z]\\}\cap\\{0,1\\}\neq\emptyset$
$\displaystyle\bm{\mathrm{A}}[x]\in\\{0,1\\}\implies\bm{\mathrm{A}}[y]=\bm{\mathrm{A}}[z]=\bm{\mathrm{A}}[x].$

######  Theorem D.3 ([DFHM22]).

The Pure-Circuit problem is PPAD-complete.

###  D.2 Construction of the Auction

Consider an instance $(X,G)$ of Pure-Circuit. We now describe how to construct
an instance of the discrete FPA that encodes the Pure-Circuit instance. In the
next section, we will then argue that any approximate equilibrium of the
auction must yield a solution to $(X,G)$.

The auction consists of one bidder for each of the variables in $X$, along
with a number of additional auxiliary bidders. Each bidder $i$ has a value
space consisting of two values, $V_{i}=\\{0,v_{i}\\}$, where $v_{i}\in(0,1]$
depends on $i$. The bidding space is
$B=\\{b_{0},b_{1},b_{2},b_{3}\\}=\\{0,1/4,1/2,3/4\\}$. We now describe the
bidders in the auction.

##### Constant bidders

The purpose of this part of the construction is to have a bidder const who
bids $b_{2}$ with probability $1$ when its value is $v_{\textsf{const}}$ in
any approximate equilibrium. In order to achieve this, we introduce a set $C$
of two additional bidders and ensure that they always bid $b_{1}$ when their
value is non-zero. In more detail, each bidder $i\in C$ has value space
$V_{i}=\\{0,v_{i}\\}$ with $v_{i}=1/2$, and we set
$f_{i,j}(0)=1,f_{i,j}(v_{j})=0$ for all other bidders $j$ in the auction. The
bidder const has value space $V_{\textsf{const}}=\\{0,v_{\textsf{const}}\\}$
with $v_{\textsf{const}}=1$, and we set
$f_{\textsf{const},j}(0)=0,f_{\textsf{const},j}(v_{j})=1$ for all $j\in C$,
and $f_{i,j}(0)=1,f_{i,j}(v_{j})=0$ for all other bidders $j$ in the auction.
We show that this construction indeed satisfies the desired properties in the
next section.

##### Variable bidders

For every variable $x\in X$ of the Pure-Circuit instance, we introduce a
corresponding bidder $x$ in the auction. The value space $V_{x}$ and
distributions $f_{x,j}$ depend on the type of gate that uses $x$ as output.

##### AND gate

For every variable $z\in X$ that is the output of an AND gate with inputs $x$
and $y$, we set the value space to be $V_{z}=\\{0,v_{z}\\}$, where
$v_{z}=7/12$. The distributions are $f_{z,j}(0)=0,f_{z,j}(v_{j})=1$ for
$j\in\\{x,y\\}$, and $f_{z,j}(0)=1,f_{z,j}(v_{j})=0$ for all other bidders $j$
in the auction.

##### PURIFY gate

For every variable $y\in X$ that is the _first_ output of a PURIFY gate with
input $x$, we set the value space to be $V_{y}=\\{0,v_{y}\\}$, where
$v_{y}=9/16$. The distributions are $f_{y,x}(0)=0,f_{y,x}(v_{x})=1$, and
$f_{y,j}(0)=1,f_{y,j}(v_{j})=0$ for all other bidders $j$ in the auction.

For every variable $z\in X$ that is the _second_ output of a PURIFY gate with
input $x$, we set the value space to be $V_{z}=\\{0,v_{z}\\}$, where
$v_{z}=11/16$. The distributions are $f_{z,x}(0)=0,f_{z,x}(v_{x})=1$, and
$f_{z,j}(0)=1,f_{z,j}(v_{j})=0$ for all other bidders $j$ in the auction.

##### NOT gate

For every variable $y\in X$ that is the output of a NOT gate with input $x$,
we introduce an additional auxiliary bidder $y^{\prime}$ to help with the
implementation of the gate. The value space of bidder $y^{\prime}$ is
$V_{y^{\prime}}=\\{0,v_{y^{\prime}}\\}$, where $v_{y^{\prime}}=13/14$. The
distributions are $f_{y^{\prime},x}(0)=0,f_{y^{\prime},x}(v_{x})=1$,
$f_{y^{\prime},\textsf{const}}(0)=0,f_{y^{\prime},\textsf{const}}(v_{\textsf{const}})=1$,
and $f_{y^{\prime},j}(0)=1,f_{y^{\prime},j}(v_{j})=0$ for all other bidders
$j$ in the auction.

The value space of bidder $y$ is $V_{y}=\\{0,v_{y}\\}$, where $v_{y}=5/8$. The
distributions are
$f_{y,y^{\prime}}(0)=1/9,f_{y,y^{\prime}}(v_{y^{\prime}})=8/9$, and
$f_{y,j}(0)=1,f_{y,j}(v_{j})=0$ for all other bidders $j$ in the auction.

##### Properties

This instance of the auction problem can clearly be constructed in polynomial
time given an instance $(X,G)$ of Pure-Circuit. Furthermore, by construction
the auction has interaction degree bounded by $d=2$.

###  D.3 Analysis

Fix any constant $\varepsilon<1/36$. Without loss of generality, we can assume
that $|X|$ is sufficiently large so that the number of bidders in the auction,
denoted by $n$, satisfies $n\geq\max\\{1000,1/(1/36-\varepsilon)\\}$.

Consider any $\varepsilon$-well-supported equilibrium $\bm{\beta}$ of the
auction. In this section, we show how to extract a solution to the Pure-
Circuit instance $(X,G)$ from $\bm{\beta}$ in polynomial time.

##### Extraction

We construct an assignment $\bm{\mathrm{A}}:X\to\\{0,1,\bot\\}$ to the
variables of Pure-Circuit by letting

  * —

$\bm{\mathrm{A}}[x]=1$ if $\beta_{x}(v_{x})(b_{1})=1$,

  * —

$\bm{\mathrm{A}}[x]=0$ if $\beta_{x}(v_{x})(b_{1})=0$,

  * —

$\bm{\mathrm{A}}[x]=\bot$ otherwise.

In the remainder of this section, we argue that this assignment satisfies all
the gates of the Pure-Circuit instance $(X,G)$. Note that by construction we
have $v_{x}<b_{3}$ for all $x\in X$, so we will necessarily have
$\beta_{x}(v_{x})(b_{3})=0$. For a bidder $x\in X$, we say that $x$ is _valid_
, if, in addition, $\beta_{x}(v_{x})(b_{0})=0$, or, in other words,

$\beta_{x}(v_{x})(b_{1})+\beta_{x}(v_{x})(b_{2})=1.$

Ultimately, we will argue that all bidders $x\in X$ must be valid.

##### Constant bidders

We start by showing that the constant bidders have the desired behaviour.

######  Lemma D.4.

We have $\beta_{\textsf{const}}(v_{\textsf{const}})(b_{2})=1$.

###### Proof.

We first analyse the behaviour of the bidders in set $C$. Consider any bidder
$i\in C$ and note that since $f_{i,j}(0)=1$ for all $j\neq i$, bidder $i$
believes that all other bidders have value $0$. As a result, by the no-
overbidding assumption, bidder $i$ believes that all other bidders will bid
$b_{0}=0$. This yields the following utilities for bidder $i$ at value
$v_{i}=1/2$:

$\begin{split}u_{i}(b_{0},\bm{\beta}_{-i};v_{i})&=(v_{i}-b_{0})\cdot
H_{i}(b_{0},\bm{\beta}_{-i})=\frac{1}{2}\cdot\frac{1}{n}\\\
u_{i}(b_{1},\bm{\beta}_{-i};v_{i})&=(v_{i}-b_{1})\cdot
H_{i}(b_{1},\bm{\beta}_{-i})=\frac{1}{4}\\\
u_{i}(b_{2},\bm{\beta}_{-i};v_{i})&=(v_{i}-b_{2})\cdot
H_{i}(b_{2},\bm{\beta}_{-i})=0\end{split}$

and bid $b_{3}$ is not playable because $b_{3}>v_{i}$. Since $n\geq 1000$, we
have $1/4>1/2n+\varepsilon$, and thus $b_{1}$ is the only $\varepsilon$-best-
response, i.e., $\beta_{i}(v_{i})(b_{1})=1$.

Now we turn our attention to the bidder const. Recall that
$f_{\textsf{const},j}(0)=0,f_{\textsf{const},j}(v_{j})=1$ for all $j\in C$,
and $f_{i,j}(0)=1,f_{i,j}(v_{j})=0$ for all other bidders $j$ in the auction.
As a result, since $\beta_{j}(v_{j})(b_{1})=1$ for all $j\in C$, bidder const
believes that all bidders $j\in C$ bid $b_{1}$. Furthermore, by the same
argument as above, bidder const believes that all other bidders outside $C$
bid $b_{0}=0$. This yields the following utilities for bidder
$i=\textsf{const}$ at value $v_{i}=v_{\textsf{const}}=1$:

$\begin{split}u_{i}(b_{0},\bm{\beta}_{-i};v_{i})&=(v_{i}-b_{0})\cdot
H_{i}(b_{0},\bm{\beta}_{-i})=0\\\
u_{i}(b_{1},\bm{\beta}_{-i};v_{i})&=(v_{i}-b_{1})\cdot
H_{i}(b_{1},\bm{\beta}_{-i})=\frac{3}{4}\cdot\frac{1}{|C|+1}\\\
u_{i}(b_{2},\bm{\beta}_{-i};v_{i})&=(v_{i}-b_{2})\cdot
H_{i}(b_{2},\bm{\beta}_{-i})=\frac{1}{2}\\\
u_{i}(b_{3},\bm{\beta}_{-i};v_{i})&=(v_{i}-b_{3})\cdot
H_{i}(b_{3},\bm{\beta}_{-i})=\frac{1}{4}\\\ \end{split}$

Recalling that $|C|=2$, we see that $b_{2}$ is the only $\varepsilon$-best-
response, since $\varepsilon<1/4$. ∎

##### AND gate

Next, we consider bidders corresponding to an AND gate.

######  Lemma D.5.

For any AND gate with inputs $x$ and $y$, and output $z$, we have that

  * —

$z$ is valid,

  * —

if $x$ and $y$ are valid, then $\bm{\mathrm{A}}$ satisfies the conditions of
the AND gate.

###### Proof.

Let us first show that $z$ is valid. By construction, bidder $z$ believes that
all other bidders, except $x$ and $y$, will bid $b_{0}$. Furthermore, $z$
believes that $x$ and $y$ will bid according to $\beta_{x}(v_{x})$ and
$\beta_{y}(v_{y})$, respectively. Recalling that
$\beta_{x}(v_{x})(b_{3})=\beta_{y}(v_{y})(b_{3})=0$, and using the notation
$p_{j}=\beta_{x}(v_{x})(b_{j})$, $q_{j}=\beta_{y}(v_{y})(b_{j})$, for
$j\in\\{0,1,2\\}$, we can write the utilities of bidder $i=z$ at value
$v_{i}=v_{z}=7/12$:

$\begin{split}u_{i}(b_{0},\bm{\beta}_{-i};v_{i})&=(v_{i}-b_{0})\cdot
H_{i}(b_{0},\bm{\beta}_{-i})=\frac{7}{12}p_{0}q_{0}/n\\\
u_{i}(b_{1},\bm{\beta}_{-i};v_{i})&=(v_{i}-b_{1})\cdot
H_{i}(b_{1},\bm{\beta}_{-i})=\left(\frac{7}{12}-\frac{1}{4}\right)(p_{0}q_{0}+p_{1}q_{0}/2+p_{0}q_{1}/2+p_{1}q_{1}/3)\\\
u_{i}(b_{2},\bm{\beta}_{-i};v_{i})&=\left(\frac{7}{12}-\frac{1}{2}\right)((1-p_{2})(1-q_{2})+(1-p_{2})q_{2}/2+p_{2}(1-q_{2})/2+p_{2}q_{2}/3)\end{split}$

and bid $b_{3}$ is not playable because $b_{3}>v_{i}$. Note that we always
have $u_{i}(b_{2},\bm{\beta}_{-i};v_{i})\geq(7/12-1/2)/3=1/36$, because
$(1-p_{2})(1-q_{2})+(1-p_{2})q_{2}/2+p_{2}(1-q_{2})/2+p_{2}q_{2}/3\geq 1/3$.
Furthermore, $u_{i}(b_{0},\bm{\beta}_{-i};v_{i})\leq 7/12n<1/n\leq
1/36-\varepsilon$, since $n\geq 1/(1/36-\varepsilon)$. As a result, $b_{0}$
can never be an $\varepsilon$-best-response for $z$, and thus $z$ is valid.

Now consider the case where $x$ and $y$ are valid, i.e., $p_{0}=q_{0}=0$. In
that case, the utilities can be simplified to

$\begin{split}u_{i}(b_{0},\bm{\beta}_{-i};v_{i})&=0\\\
u_{i}(b_{1},\bm{\beta}_{-i};v_{i})&=\left(\frac{7}{12}-\frac{1}{4}\right)p_{1}q_{1}/3\\\
u_{i}(b_{2},\bm{\beta}_{-i};v_{i})&=\left(\frac{7}{12}-\frac{1}{2}\right)(p_{1}q_{1}+p_{1}(1-q_{1})/2+(1-p_{1})q_{1}/2+(1-p_{1})(1-q_{1})/3)\end{split}$

If $\bm{\mathrm{A}}[x]=\bm{\mathrm{A}}[y]=1$, i.e., $p_{1}=q_{1}=1$, then

$u_{i}(b_{1},\bm{\beta}_{-i};v_{i})-u_{i}(b_{2},\bm{\beta}_{-i};v_{i})=\left(\frac{7}{12}-\frac{1}{4}\right)\frac{1}{3}-\left(\frac{7}{12}-\frac{1}{2}\right)=\frac{1}{36}>\varepsilon$

and so $b_{1}$ is the only $\varepsilon$-best-response, i.e.,
$\bm{\mathrm{A}}[z]=1$.

Finally, consider the case where $\bm{\mathrm{A}}[x]=0$ or
$\bm{\mathrm{A}}[y]=0$. Without loss of generality, given the symmetry of the
construction, assume that $\bm{\mathrm{A}}[x]=0$, i.e., $p_{1}=0$. In that
case, we have

$u_{i}(b_{2},\bm{\beta}_{-i};v_{i})-u_{i}(b_{1},\bm{\beta}_{-i};v_{i})=\frac{1}{12}(q_{1}/2+(1-q_{1})/3)-0\geq\frac{1}{36}>\varepsilon$

and so $b_{2}$ is the only $\varepsilon$-best-response, i.e.,
$\bm{\mathrm{A}}[z]=0$. ∎

##### PURIFY gate

Next, we consider bidders corresponding to a PURIFY gate.

######  Lemma D.6.

For any PURIFY gate with input $x$ and outputs $y$ and $z$, we have that

  * —

$y$ and $z$ are valid,

  * —

if $x$ is valid, then $\bm{\mathrm{A}}$ satisfies the conditions of the PURIFY
gate.

###### Proof.

Let us first show that $y$ and $z$ are valid. By construction, bidder $y$
believes that all other bidders except $x$ will bid $b_{0}$. Furthermore, $y$
believes that $x$ will bid according to $\beta_{x}(v_{x})$. Recalling that
$\beta_{x}(v_{x})(b_{3})=0$, and using the notation
$p_{j}=\beta_{x}(v_{x})(b_{j})$ for $j\in\\{0,1,2\\}$, we can write the
utilities of bidder $i=y$ at value $v_{i}=v_{y}=9/16$:

$\begin{split}u_{i}(b_{0},\bm{\beta}_{-i};v_{i})&=(v_{i}-b_{0})\cdot
H_{i}(b_{0},\bm{\beta}_{-i})=\frac{9}{16}p_{0}/n\\\
u_{i}(b_{1},\bm{\beta}_{-i};v_{i})&=(v_{i}-b_{1})\cdot
H_{i}(b_{1},\bm{\beta}_{-i})=\left(\frac{9}{16}-\frac{1}{4}\right)(p_{0}+p_{1}/2)\\\
u_{i}(b_{2},\bm{\beta}_{-i};v_{i})&=(v_{i}-b_{2})\cdot
H_{i}(b_{2},\bm{\beta}_{-i})=\left(\frac{9}{16}-\frac{1}{2}\right)(p_{0}+p_{1}+p_{2}/2)\end{split}$

and bid $b_{3}$ is not playable because $b_{3}>v_{i}$. Since
$p_{0}+p_{1}+p_{2}/2\geq 1/2$, we can write

$u_{i}(b_{2},\bm{\beta}_{-i};v_{i})-u_{i}(b_{0},\bm{\beta}_{-i};v_{i})\geq\left(\frac{9}{16}-\frac{1}{2}\right)\frac{1}{2}-\frac{9}{16}p_{0}/n=\frac{1}{32}-\frac{9}{16}p_{0}/n>\varepsilon$

because $n\geq 1000$. As a result, $b_{0}$ can never be an $\varepsilon$-best-
response for $y$, and thus $y$ is valid. The same reasoning for $i=z$, with
$v_{i}=v_{z}=11/16$, yields

$u_{i}(b_{2},\bm{\beta}_{-i};v_{i})-u_{i}(b_{0},\bm{\beta}_{-i};v_{i})\geq\left(\frac{11}{16}-\frac{1}{2}\right)\frac{1}{2}-\frac{11}{16}p_{0}/n=\frac{3}{32}-\frac{11}{16}p_{0}/n>\varepsilon$

because $n\geq 1000$. Thus, $b_{0}$ can never be an $\varepsilon$-best-
response for $z$, and $z$ is also valid.

Now consider the case where $x$ is valid, i.e., $p_{0}=0$. In that case, the
utilities for $i\in\\{y,z\\}$ at value $v_{i}$ can be simplified to

$\begin{split}u_{i}(b_{0},\bm{\beta}_{-i};v_{i})&=0\\\
u_{i}(b_{1},\bm{\beta}_{-i};v_{i})&=\left(v_{i}-\frac{1}{4}\right)p_{1}/2\\\
u_{i}(b_{2},\bm{\beta}_{-i};v_{i})&=\left(v_{i}-\frac{1}{2}\right)(1/2+p_{1}/2)\end{split}$

We can write

$\Delta:=u_{i}(b_{1},\bm{\beta}_{-i};v_{i})-u_{i}(b_{2},\bm{\beta}_{-i};v_{i})=\left(v_{i}-\frac{1}{4}\right)p_{1}/2-\left(v_{i}-\frac{1}{2}\right)(1/2+p_{1}/2)=p_{1}/8-v_{i}/2+1/4.$

Now for $i=y$, and thus $v_{i}=9/16$, we obtain that

  * —

if $\bm{\mathrm{A}}[x]=0$, i.e., $p_{1}=0$, then
$\Delta=p_{1}/8-1/32=-1/32<-\varepsilon$, and $b_{2}$ is the only
$\varepsilon$-best-response, i.e., $\bm{\mathrm{A}}[y]=0$.

  * —

if $\bm{\mathrm{A}}[x]\geq 1/2$, i.e., $p_{1}\geq 1/2$, then
$\Delta=p_{1}/8-1/32\geq 1/32>\varepsilon$, and $b_{1}$ is the only
$\varepsilon$-best-response, i.e., $\bm{\mathrm{A}}[y]=1$.

Similarly, for $i=z$, and thus $v_{i}=11/16$, we obtain that

  * —

if $\bm{\mathrm{A}}[x]\leq 1/2$, i.e., $p_{1}\leq 1/2$, then
$\Delta=p_{1}/8-3/32\leq-1/32<-\varepsilon$, and $b_{2}$ is the only
$\varepsilon$-best-response, i.e., $\bm{\mathrm{A}}[z]=0$.

  * —

if $\bm{\mathrm{A}}[x]=1$, i.e., $p_{1}=1$, then
$\Delta=p_{1}/8-3/32=1/32>\varepsilon$, and $b_{1}$ is the only
$\varepsilon$-best-response, i.e., $\bm{\mathrm{A}}[z]=1$.

As a result, the conditions of the PURIFY gate are indeed satisfied. In
particular, we always have that at least one of $\bm{\mathrm{A}}[y]$ or
$\bm{\mathrm{A}}[z]$ lies in $\\{0,1\\}$. ∎

##### NOT gate

Finally, we consider bidders corresponding to a NOT gate.

######  Lemma D.7.

For any NOT gate with input $x$ and output $y$, we have that

  * —

$y$ is valid,

  * —

if $x$ is valid, then $\bm{\mathrm{A}}$ satisfies the conditions of the NOT
gate.

###### Proof.

We first show that $y$ is valid. By construction, bidder $y$ believes that all
other bidders except $y^{\prime}$ will bid $b_{0}$. Furthermore, $y$ believes
that $y^{\prime}$ will bid according to $\beta_{y^{\prime}}(0)$ with
probability $1/9$ (namely when $y^{\prime}$ has value $0$), and according to
$\beta_{y^{\prime}}(v_{y^{\prime}})$ with probability $8/9$ (namely when
$y^{\prime}$ has value $v_{y^{\prime}}$). By the no-overbidding assumption,
$\beta_{y^{\prime}}(0)$ is the distribution with
$\beta_{y^{\prime}}(0)(b_{0})=1$. Using the notation
$q_{j}=\beta_{y^{\prime}}(v_{y^{\prime}})(b_{j})$ for $j=0,1,2,3$, we can
write the utilities of bidder $i=y$ at value $v_{i}=v_{y}=5/8$:

$\begin{split}u_{i}(b_{0},\bm{\beta}_{-i};v_{i})&=\frac{5}{8}\left(\frac{1}{9}\cdot\frac{1}{n}+\frac{8}{9}\cdot\frac{q_{0}}{n}\right)\\\
u_{i}(b_{1},\bm{\beta}_{-i};v_{i})&=\left(\frac{5}{8}-\frac{1}{4}\right)\left(\frac{1}{9}+\frac{8}{9}(q_{0}+q_{1}/2)\right)\\\
u_{i}(b_{2},\bm{\beta}_{-i};v_{i})&=\left(\frac{5}{8}-\frac{1}{2}\right)\left(\frac{1}{9}+\frac{8}{9}(q_{0}+q_{1}+q_{2}/2)\right)\end{split}$

and bid $b_{3}$ is not playable because $b_{3}>v_{i}$. We always have

$u_{i}(b_{1},\bm{\beta}_{-i};v_{i})-u_{i}(b_{0},\bm{\beta}_{-i};v_{i})\geq\frac{3}{8}\cdot\frac{1}{9}-\frac{5}{8}\cdot\left(\frac{1}{9}\cdot\frac{1}{n}+\frac{8}{9}\cdot\frac{1}{n}\right)=\frac{3}{72}-\frac{5}{8n}>\varepsilon$

because $n\geq 1000$. As a result, $b_{0}$ is never an $\varepsilon$-best-
response for $y$ at value $v_{y}$, and thus $y$ is valid. Furthermore, we note
the following, which will be useful below

  * —

if $\beta_{y^{\prime}}(v_{y^{\prime}})(b_{2})=1$, i.e., $q_{2}=1$, then

$u_{i}(b_{2},\bm{\beta}_{-i};v_{i})-u_{i}(b_{1},\bm{\beta}_{-i};v_{i})=\frac{1}{8}\left(\frac{1}{9}+\frac{8}{9}\cdot\frac{1}{2}\right)-\frac{3}{8}\cdot\frac{1}{9}=\frac{1}{36}>\varepsilon$

and thus $b_{2}$ is the only $\varepsilon$-best-response, i.e.,
$\bm{\mathrm{A}}[y]=0$.

  * —

if $\beta_{y^{\prime}}(v_{y^{\prime}})(b_{3})=1$, i.e., $q_{3}=1$, then

$u_{i}(b_{1},\bm{\beta}_{-i};v_{i})-u_{i}(b_{2},\bm{\beta}_{-i};v_{i})=\frac{3}{8}\cdot\frac{1}{9}-\frac{1}{8}\cdot\frac{1}{9}=\frac{1}{36}>\varepsilon$

and thus $b_{1}$ is the only $\varepsilon$-best-response, i.e.,
$\bm{\mathrm{A}}[y]=1$.

From now on, we assume that $x$ is valid, and aim to show that the constraints
of the NOT gate are satisfied. By construction, bidder $y^{\prime}$ believes
that all other bidders except $x$ and const will bid $b_{0}$. By Lemma D.4 we
know that bidder $y^{\prime}$ believes that bidder const will bid $b_{2}$.
Finally, bidder $y^{\prime}$ believes that $x$ will bid according to
$\beta_{x}(v_{x})$, where $\beta_{x}(v_{x})(b_{0})=\beta_{x}(v_{x})(b_{3})=0$,
since $x$ is valid. Using the notation $p_{1}=\beta_{x}(v_{x})(b_{1})$, and
thus $1-p_{1}=\beta_{x}(v_{x})(b_{2})$, we can write the utilities of bidder
$i=y^{\prime}$ at value $v_{i}=v_{y^{\prime}}=13/14$:

$\begin{split}u_{i}(b_{0},\bm{\beta}_{-i};v_{i})&=\frac{13}{14}\cdot 0=0\\\
u_{i}(b_{1},\bm{\beta}_{-i};v_{i})&=\left(\frac{13}{14}-\frac{1}{4}\right)\cdot
0=0\\\
u_{i}(b_{2},\bm{\beta}_{-i};v_{i})&=\left(\frac{13}{14}-\frac{1}{2}\right)(p_{1}/2+(1-p_{1})/3)\\\
u_{i}(b_{3},\bm{\beta}_{-i};v_{i})&=\left(\frac{13}{14}-\frac{3}{4}\right)\cdot
1\end{split}$

Now, we have

  * —

if $\bm{\mathrm{A}}[x]=0$, i.e., $p_{1}=0$, then

$u_{i}(b_{3},\bm{\beta}_{-i};v_{i})-u_{i}(b_{2},\bm{\beta}_{-i};v_{i})=\frac{5}{28}-\frac{3}{7}\cdot\frac{1}{3}=\frac{1}{28}>\varepsilon$

and thus $b_{3}$ is the only $\varepsilon$-best-response, i.e.,
$\beta_{y^{\prime}}(v_{y^{\prime}})(b_{3})=1$. As proved above in the analysis
of bidder $y$, this implies $\bm{\mathrm{A}}[y]=1$.

  * —

if $\bm{\mathrm{A}}[x]=1$, i.e., $p_{1}=1$, then

$u_{i}(b_{2},\bm{\beta}_{-i};v_{i})-u_{i}(b_{3},\bm{\beta}_{-i};v_{i})=\frac{3}{7}\cdot\frac{1}{2}-\frac{5}{28}=\frac{1}{28}>\varepsilon$

and thus $b_{2}$ is the only $\varepsilon$-best-response, i.e.,
$\beta_{y^{\prime}}(v_{y^{\prime}})(b_{2})=1$. As proved above in the analysis
of bidder $y$, this implies $\bm{\mathrm{A}}[y]=0$.

As a result, the conditions of the NOT gate are indeed satisfied. ∎

To complete the proof, note that by Lemmas D.5, D.6 and D.7 all bidders $x\in
X$ are valid, and thus, again by these lemmas, the constructed assignment
$\bm{\mathrm{A}}$ satisfies all the gates of the Pure-Circuit instance
$(X,G)$.

##  Appendix E Existence of Symmetric Equilibria in IID Auctions

This section is dedicated to proving Theorem 5.2. En route, we establish two
results that could be of independent interest, namely that (a) symmetric
continuous first-price auctions (with discrete bidding space) always have pure
symmetric equilibria (see Theorem E.1), and (b) the structure and
approximability of (mixed) equilibria is preserved, in the limit, in discrete
auctions (see Lemma E.2).

######  Theorem E.1.

Any first-price auction with continuous iid priors and discrete bids has a
symmetric and monotone pure equilibrium.

###### Proof.

Our proof follows closely that of [Ath01] for the existence of (pure)
equilibria in continuous auctions for general (i.e., not necessarily
symmetric) priors. We need to take care in handling correctly the symmetry of
the underlying strategies, but this turns out to be straightforward.

Fix a CFPA $\mathcal{A}$ with iid priors over $[0,1]$ and discrete bidding
space $B=\\{b_{1}\leq b_{2}\leq\dots\leq b_{m}\\}$. It is known that, in this
continuous setting, any monotone strategy $\beta:[0,1]\rightarrow B$ can be
represented by a non-decreasing sequence of break points
$\alpha=\alpha(\beta)=(\alpha_{1},\alpha_{2},\dots,\alpha_{m})$ such that
$\alpha_{\ell}=\sup\\{v\in[0,1]\;\left|\;\beta(v)\leq b_{\ell}\right.\\}$, for
$\ell\in[m]$ (for a more detailed discussion, see [FGHLP23, Sec. 2]). For
simplicity, in the following we will slightly abuse notation, and sometimes
use directly the jump-point representation $\alpha=\alpha(\beta)$ instead of a
bidding strategy $\beta$.

Then, let us also denote the corresponding space of all feasible, no-
overbidding (jump-point representation) strategies by

$\Omega=\left\\{\alpha\in[0,1]^{m}\;\left|\;\alpha_{\ell}\leq\alpha_{\ell+1}\;\;\forall\ell\in[m-1]\quad\land\quad
b_{\ell}\leq\alpha_{\ell}\;\;\forall\ell\in[m]\right.\right\\}.$

Notice that the linearity of the inequalities defining $\Omega$ imply that it
is a polytope, and thus $\Omega$ is convex and compact subspace of the
Euclidean space $\mathbb{R}^{m}$. Also, it is easy to see that $\Omega$ is
nonempty, since $(1,1,\dots,1)\in\Omega$ (corresponding to the strategy of
always bidding $\min B=b_{1}$).

Next, given a symmetric and monotone strategy profile
$\bm{\alpha}=(\alpha,\alpha,\dots,\alpha)$, we define (the set of) its best-
responses by

$\mathsf{BR}(\alpha)\coloneqq\left\\{\alpha^{\prime}\in\Omega\;\left|\;u_{i}\left(\alpha^{\prime}(v_{i}),\bm{\alpha}_{-i};v_{i}\right)\geq\max_{b\in
B}u_{i}\left(b,\bm{\alpha}_{-i};v_{i}\right)\quad\forall v_{i}\in
V\right.\right\\}$

Notice that, since auction $\mathcal{A}$ has iid priors, the specific choice
of the bidder $i$ in the above definition is irrelevant. This gives rise to a
correspondence $\mathsf{BR}:\Omega\rightarrow 2^{\Omega}$ with the property
that: a symmetric and monotone strategy profile, where all bidders play a
strategy $\alpha$, is an (exact) PBNE of $\mathcal{A}$, if and only if
$\alpha\in\mathsf{BR}(\alpha)$.

Using this property, we can establish the existence of a symmetric PBNE by
means of Kakutani’s fixed-point theorem (see, e.g., [AB06, p. 583]). Towards
that end, we need to establish the following properties:

  * —

$\mathsf{BR}(\alpha)\neq\emptyset$ for all $\alpha\in\Omega$.

  * —

$\mathsf{BR}(\alpha)$ is a convex set, for all $\alpha\in\Omega$.

  * —

$\mathsf{BR}$ has a closed graph.

The above properties can be proved in an identical way to that of the existing
results for general priors, and we refer the interested reader to [Ath01,
Lemma 3] or [Kri09, p. 302]. ∎

######  Lemma E.2 (Convergence Lemma).

Consider a DFPA $\mathcal{A}$ with iid priors. Assume that $\mathcal{A}$ has a
symmetric monotone $\varepsilon$-approximate MBNE, for all $\varepsilon>0$.
Then, $\mathcal{A}$ has an _exact_ , symmetric and monotone, MBNE.

###### Proof.

Fix a DFPA $\mathcal{A}$ with iid priors over a common value space $V$, and
bidding space $B$. By the assumptions of our lemma, there exists a sequence of
strategy profiles
$\\{\bm{\beta}_{n}=(\beta_{n},\beta_{n},\dots,\beta_{n})\\}$,
$n\in\mathbb{N}$, where each bidder plays according to the same, monotone,
strategy $\beta_{n}:V\rightarrow\Delta(B)$, such that $\bm{\beta}_{n}$ is a
$\frac{1}{n}$-approximate MBNE of $\mathcal{A}$ for all positive integers $n$.
For our proof, we will show that

  * (a)

there exists a subsequence $\\{\bar{\beta}_{n}\\}$ of $\\{\beta_{n}\\}$, such
that $\bar{\beta}_{n}\to\beta^{*}$ (as $n\to\infty$), where $\beta$ is a
monotone strategy.

  * (b)

$\bm{\beta}^{*}=(\beta^{*},\beta^{*},\dots,\beta^{*})$ is an _exact_ MBNE.

Starting on (a), first observe that since we are at a discrete auction, there
are finitely many different supports that a bidding strategy can have.
Formally, since sets $V,B$ are finite, the set $\left\\{\times_{v\in
V}\operatorname*{\mathrm{supp}}\left(\beta(v)\right)\right\\}_{\beta\in\Delta(B)^{V}}$
is also finite. Therefore, there has to exist a subsequence
$\\{\tilde{\beta_{n}}\\}$ of $\\{\beta_{n}\\}$ such that all its elements have
exactly the same support.

Let $\tilde{p}_{n}=\left(\tilde{p}_{n}(v,b)\right)_{v\in V,b\in B}$ denote the
canonical representation of strategy $\tilde{\beta}_{n}$; that is,
$\tilde{p}_{n}(v,b)$ is the probability of submitting bid $b$ when having true
value $v$, under strategy $\tilde{\beta}_{n}$ (see Section 2.1), for all
$n\in\mathbb{N}$. Observe that all these probabilities must satisfy the
feasibility constraints

$\displaystyle\tilde{p}_{n}(v,b)$ $\displaystyle\geq
0,\quad\sum_{b^{\prime}\in
B}\tilde{p}_{n}(v,b^{\prime})=1,\quad\text{and}\quad\tilde{p}_{n}(v,b)(v-b)\geq
0$ $\displaystyle\quad\forall{v\in V,b\in B},$

which define a polytope, and thus a compact subspace, of the Euclidean metric
space $\mathbb{R}^{V\times B}$. Therefore, there has to exist a subsequence
$\\{\bar{p}_{n}\\}$ of $\\{\tilde{p}_{n}\\}$ that converges to a feasible
representation $\bar{p}^{*}$ of bidding strategy $\beta^{*}\in\Delta(B)^{V}$.

The only thing remaining in order to establish point (a) is the monotonicity
of $\beta^{*}$. Indeed, since all strategies of $\\{\tilde{\beta}_{n}\\}$ has
the same support, it must be that _all_ elements of the sequence
$\\{\bar{p}_{n}\\}$ have exactly the same zero components. Therefore, due to
compactness, the only way in which the supports of limiting strategy
$\beta^{*}$ may differ from the supports of all strategies in
$\\{\bar{\beta}_{n}\\}$ is if for a probability component it is $p^{*}(v,b)=0$
but $\bar{p}_{n}(v,b)\neq 0$ (for all $n\in\mathbb{N}$). But then, this
implies that the supports may only _shrink_ in the limit; that is,
$\operatorname*{\mathrm{supp}}\left(\beta^{*}(v)\right)\subseteq\operatorname*{\mathrm{supp}}\left(\bar{\beta}_{n}(v)\right)$
for all $n\in\mathbb{N}$. So, given that $\bar{\beta}_{n}$’s are monotone,
$\beta^{*}$ must also be monotone; see Definition 3.

Moving now to point (b), for a symmetric strategy profile
$\bm{\beta}=(\beta,\beta,\dots,\beta)$, let

$Z(\beta)\coloneqq\max_{v\in V,b\in
B}u_{i}(b,\bm{\beta}_{-i};v_{i})-u_{i}(\beta(v_{i}),\bm{\beta}_{-i};v_{i})$
(43)

denote the maximum utility improvement that a bidder $i$ can achieve by
unilaterally deviating, from the bid $\beta(v_{i})$ dictated by $\beta$, to
any other bid, while all other bidders play according to the symmetric profile
$\bm{\beta}=(\beta,\beta,\dots,\beta)$, across all possible true values
$v_{i}$. Note that, due to symmetry, the specific choice of the bidder $i$ in
the above definition (43) is irrelevant. Then, $\bm{\beta}$ is an
$\varepsilon$-approximate MBNE of $\mathcal{A}$, if and only if
$Z(\beta)\leq\varepsilon$; see Definition 1 Obviously, $Z(\beta)\geq 0$ for
any strategy profile $\bm{\beta}$.

Observe that, as defined by (43), $Z:\Delta(B)^{V}\rightarrow[0,1]$ is a
continuous function: bidder utilities are continuous (see (2)) and (finitely
many) max-operators preserve continuity. So,

$Z(\beta^{*})=\lim_{n\to\infty}Z(\bar{\beta}_{n})\leq\lim_{n\to\infty}\frac{1}{n}=0,$

meaning that indeed $\bm{\beta}^{*}$ is an exact MBNE of $\mathcal{A}$. ∎

Now we have all the necessary machinery in order to prove Theorem 5.2:

###### Proof of Theorem 5.2.

Fix a DFPA $\mathcal{A}$ with iid priors and choose an arbitrary
$\varepsilon\in(0,1)$. Then, by making use of our computational
equivalence111111As a matter of fact, in this proof we make use of the
reduction from discrete to continuous auctions by deploying Lemma 4.2 with
$\varepsilon\leftarrow 0$ and $\delta\leftarrow\varepsilon$ in its statement.
between discrete and continuous auctions from Section 4.2, we can construct a
CFPA $\mathcal{A}^{\prime}$ with iid priors (and the same, discrete, bidding
space as $\mathcal{A}$) such that, any $\varepsilon$-approximate symmetric
(and monotone) PBNE of $\mathcal{A}^{\prime}$ can be translated back to a
symmetric and monotone $\varepsilon$-approximate MBNE of $\mathcal{A}$.

Thus, given that such $\varepsilon$-approximate symmetric PBNE are guaranteed
to exist, due to Theorem E.1, we also get guaranteed existence of an
$\varepsilon$-approximate, symmetric and monotone MBNE in our original
discrete auction $\mathcal{A}$. Since we chose $\varepsilon>0$ arbitrarily,
our Convergence Lemma E.2 gives us the desired existence of a monotone _exact_
MBNE in $\mathcal{A}$. ∎

## References

  * [AB06] Charalambos D. Aliprantis and Kim C. Border  “Infinite Dimensional Analysis: A Hitchhiker’s Guide”  Springer-Verlag, 2006  DOI: 10.1007/3-540-29587-9
  * [AB24] Mete Şeref Ahunbay and Martin Bichler  “On the Uniqueness of Bayesian Coarse Correlated Equilibria in Standard First-Price and All-Pay Auctions”  In _CoRR_ abs/2401.01185, 2024  arXiv:2401.01185
  * [ACLS22] Michael Albert, Vincent Conitzer, Giuseppe Lopomo and Peter Stone  “Mechanism design for correlated valuations: Efficient methods for revenue maximization”  In _Operations Research_ 70.1 INFORMS, 2022, pp. 562–584  DOI: 10.1287/OPRE.2020.2092
  * [Ath01] Susan Athey  “Single Crossing Properties and the Existence of Pure Strategy Equilibria in Games of Incomplete Information”  In _Econometrica_ 69.4, 2001, pp. 861–889  DOI: 10.1111/1468-0262.00223
  * [Aum61] Robert J Aumann  “Mixed and behavior strategies in infinite extensive games”  Princeton University Princeton, 1961
  * [Aum74] Robert J. Aumann  “Subjectivity and correlation in randomized strategies”  In _Journal of Mathematical Economics_ 1.1, 1974, pp. 67–96  DOI: 10.1016/0304-4068(74)90037-8
  * [Aum87] Robert J Aumann  “Correlated equilibrium as an expression of Bayesian rationality”  In _Econometrica: Journal of the Econometric Society_ JSTOR, 1987, pp. 1–18  DOI: 10.2307/1911154
  * [BDMMZ21] Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni and Song Zuo  “Robust Auction Design in the Auto-bidding World”  In _Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS)_ , 2021
  * [BG97] Pierpaolo Battigalli and Danilo Guaitoli  “Conjectural Equilibria and Rationalizability in a Game with Incomplete Information”  In _Decisions, Games and Markets_ Springer, 1997, pp. 97–124  DOI: 10.1007/978-1-4615-6337-2˙4
  * [BGM92] Pierpaolo Battigalli, Mario Gilli and M. Molinari  “Learning and Convergence to Equilibrium in Repeated Strategic Interactions: An Introductory Survey”  In _Ricerche Economiche_ 46, 1992, pp. 335–378
  * [BM13] Dirk Bergemann and Stephen Morris  “Robust predictions in games with incomplete information”  In _Econometrica_ 81.4 Wiley Online Library, 2013, pp. 1251–1308  DOI: 10.2139/ssrn.2163606
  * [BM16] Dirk Bergemann and Stephen Morris  “Bayes correlated equilibrium and the comparison of information structures in games”  In _Theoretical Economics_ 11.2 Wiley Online Library, 2016, pp. 487–522
  * [Cas67] Ralph Cassady  “Auctions and auctioneering”  University of California Press, 1967
  * [CDT09] Xi Chen, Xiaotie Deng and Shang-Hua Teng  “Settling the Complexity of Computing Two-player Nash Equilibria”  In _Journal of the ACM_ 56.3, 2009, pp. 14:1–14:57  DOI: 10.1145/1516512.1516516
  * [CDW12] Yang Cai, Constantinos Daskalakis and S. Weinberg  “An algorithmic characterization of multi-dimensional mechanisms”  In _Proceedings of the 44th Annual ACM Aymposium on Theory of Computing (STOC)_ , 2012, pp. 459–478  DOI: 10.1145/2213977.2214021
  * [CH13] Shuchi Chawla and Jason D. Hartline  “Auctions with unique equilibria”  In _Proceedings of the 14th ACM conference on Electronic Commerce (EC)_ , 2013, pp. 181–196  DOI: 10.1145/2492002.2483188
  * [Chw89] Michael Suk-Young Chwe  “The Discrete Bid First Auction”  In _Economics Letters_ 31.4, 1989, pp. 303–306  DOI: 10.1016/0165-1765(89)90019-0
  * [CKSS22] Vincent Conitzer, Christian Kroer, Eric Sodomka and Nicolas E Stier-Moses  “Multiplicative pacing equilibria in auction markets”  In _Operations Research_ 70.2, 2022, pp. 963–989  DOI: 10.1287/opre.2021.2167
  * [CP14] Yang Cai and Christos Papadimitriou  “Simultaneous Bayesian auctions and computational complexity”  In _Proceedings of the 15th ACM Conference on Economics and Computation (EC)_ , 2014, pp. 895–910  DOI: 10.1145/2600057.2602877
  * [CP23] Xi Chen and Binghui Peng  “Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules”  In _Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC)_ , 2023, pp. 698–709  DOI: 10.1145/3564246.3585195
  * [CRS82] James C Cox, Bruce Roberson and Vernon L Smith  “Theory and behavior of single object auctions”  In _Research in experimental economics_ 2.1, 1982, pp. 1–43  DOI: 10.1017/CBO9780511528354.031
  * [CS08] Vincent Conitzer and Tuomas Sandholm  “New complexity results about Nash equilibria”  In _Games and Economic Behavior_ 63.2, 2008, pp. 621–641  DOI: 10.1016/j.geb.2008.02.015
  * [CST80] Vicki M Coppinger, Vernon L Smith and Jon A Titus  “Incentives and behavior in english, dutch and sealed-bid auctions”  In _Economic inquiry_ 18.1 Wiley Online Library, 1980, pp. 1–22  DOI: 10.1111/J.1465-7295.1980.TB00556.X
  * [CSW83] James C Cox, Vernon L Smith and James M Walker  “Tests of a heterogeneous bidders theory of first price auctions”  In _Economics Letters_ 12.3-4 Elsevier, 1983, pp. 207–212  DOI: 10.1016/0165-1765(83)90039-3
  * [CSW88] James C Cox, Vernon L Smith and James M Walker  “Theory and individual behavior of first-price auctions”  In _Journal of Risk and uncertainty_ 1 Springer, 1988, pp. 61–99  DOI: 10.1007/BF00055565
  * [DFHM22] Argyrios Deligkas, John Fearnley, Alexandros Hollender and Themistoklis Melissourgos  “Pure-circuit: Strong inapproximability for PPAD”  In _Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS)_ , 2022, pp. 159–170  DOI: 10.1109/FOCS54457.2022.00022
  * [DFP06] Constantinos Daskalakis, Alex Fabrikant and Christos H. Papadimitriou  “The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games”  In _Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming (ICALP)_ , 2006, pp. 513–524  DOI: 10.1007/11786986˙45
  * [DGP09] Constantinos Daskalakis, Paul W. Goldberg and Christos H. Papadimitriou  “The complexity of computing a Nash equilibrium”  In _SIAM Journal on Computing_ 39.1, 2009, pp. 195–259  DOI: 10.1137/070699652
  * [Dig19] Digiday.com  “Digiday Research: Header bidding and first-price auctions boost publisher revenues” Accessed: 2019-01-14, 2019  URL: https://digiday.com/media/digiday-research-header-bidding-and-first-price-auctions-boost-publisher-revenues/?utm_medium=email&utm_campaign=digidaydis&utm_source=uk&utm_content=190114
  * [DRS21] Stylianos Despotakis, Ramamoorthi Ravi and Amin Sayedi  “First-price auctions in online display advertising”  In _Journal of Marketing Research_ 58.5 SAGE Publications Sage CA: Los Angeles, CA, 2021, pp. 888–907  DOI: 10.1177/00222437211030201
  * [EMS09] Guillaume Escamocher, Peter Bro Miltersen and Rocio Santillan R.  “Existence and Computation of Equilibria of First-price Auctions with Integral Valuations and Bids”  In _Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_ , 2009, pp. 1227–1228  URL: https://dl.acm.org/doi/10.5555/1558109.1558225
  * [FGHLP23] Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, Philip Lazos and Diogo Poças  “On the Complexity of Equilibrium Computation in First-Price Auctions”  In _SIAM Journal on Computing_ 52.1, 2023, pp. 80–131  DOI: 10.1137/21M1435823
  * [FHHK14] Hu Fu, Nima Haghpanah, Jason Hartline and Robert Kleinberg  “Optimal auctions for correlated buyers with sampling”  In _Proceedings of the fifteenth ACM conference on Economics and computation_ , 2014, pp. 23–36  DOI: 10.1145/2600057.2602895
  * [FL86] Drew Fudenberg and David Levine  “Limit Games and Limit Equilibria”  In _Journal of Economic Theory_ 38.2, 1986, pp. 261–279  DOI: 10.1016/0022-0531(86)90118-3
  * [For06] Francoise Forges  “Correlated equilibrium in games with incomplete information revisited”  In _Theory and Decision_ 61, 2006, pp. 329–344  DOI: 10.1007/s11238-006-9005-3
  * [For23] Françoise Forges  “Correlated equilibrium in games with incomplete information”  In _Revue Économique_ 74, 2023, pp. 529–539  DOI: 10.3917/reco.744.0529
  * [For93] Françoise Forges  “Five legitimate definitions of correlated equilibrium in games with incomplete information”  In _Theory and Decision_ 35, 1993, pp. 277–310  URL: https://api.semanticscholar.org/CorpusID:119900539
  * [FW16] Rafael Frongillo and Jens Witkowski  “A Geometric Method to Construct Minimal Peer Prediction Mechanisms”  In _Proceedings of the 30th AAAI Conference on Artificial Intelligence_ , 2016, pp. 502–508  DOI: 10.5555/3015812.3015888
  * [GGM07] Georg Gottlob, Gianluigi Greco and Toni Mancini  “Complexity of Pure Equilibria in Bayesian Games”  In _Proceedings of the 20th International Joint Conference on Artifical Intelligence (IJCAI)_ , 2007, pp. 1294–1299  DOI: 10.5555/1625275.1625485
  * [GJ79] M.. Garey and D.. Johnson  “Computers and Intractability: A Guide to the Theory of NP-Completeness”  In _Computers and Intractability: A Guide to the Theory of NP-Completeness_ W. H. Freeman & Co., 1979
  * [GLS67] James H. Griesmer, Richard E. Levitan and Martin Shubik  “Toward a Study of Bidding Processes Part IV – Games With Unknown Costs”  In _Naval Research Logistics_ 14.4, 1967, pp. 415–433  DOI: 10.1002/nav.3800140402
  * [Gol11] Paul W. Goldberg  “A survey of PPAD-completeness for computing Nash equilibria”  In _Surveys in Combinatorics 2011_ , London Mathematical Society Lecture Note Series  Cambridge University Press, 2011, pp. 51–82  DOI: 10.1017/CBO9781139004114.003
  * [GV88] D.. Grigor’ev and N.N. Vorobjov  “Solving systems of polynomial inequalities in subexponential time”  In _Journal of Symbolic Computation_ 5.1-2, 1988, pp. 37–64  DOI: 10.1016/s0747-7171(88)80005-1
  * [Hah73] Frank Hahn  “On the Notion of Equilibrium in Economics: An Inaugural Lecture by F.H. Hahn”  Cambridge University Press, 1973
  * [Har67] John C. Harsanyi  “Games With Incomplete Information Played by “Bayesian” Players, I–III: Part I. The Basic Model”  In _Management Science_ 14.3, 1967, pp. 159–182  DOI: 10.1287/mnsc.1040.0270
  * [Har89] Glenn W Harrison  “Theory and misbehavior of first-price auctions”  In _The American Economic Review_ JSTOR, 1989, pp. 749–762
  * [HST15] Jason Hartline, Vasilis Syrgkanis and Eva Tardos  “No-regret learning in Bayesian games”  In _Advances in Neural Information Processing Systems_ 28, 2015
  * [JL15] Albert Xin Jiang and Kevin Leyton-Brown  “Polynomial-time computation of exact correlated equilibrium in compact games”  In _Games and Economic Behavior_ 91, 2015, pp. 347–359  DOI: 10.1016/j.geb.2013.02.002
  * [JR01] Geoffrey A. Jehle and Philip J. Reny  “Advanced Microeconomic Theory”  Financial Times/Prentice Hall, 2001
  * [Kak41] Shizuo Kakutani  “A generalization of Brouwer’s fixed point theorem”  In _Duke Mathematical Journal_ 8.3, 1941  DOI: 10.1215/s0012-7094-41-00838-4
  * [KBP18] Çağıl Koçyiğit, Halil I Bayrak and Mustafa Ç Pınar  “Robust auction design under multiple priors by linear and integer programming”  In _Annals of Operations Research_ 260.1-2 Springer, 2018, pp. 233–253  DOI: 10.1007/s10479-017-2416-4
  * [KL93] Ehud Kalai and Ehud Lehrer  “Rational Learning Leads to Nash Equilibrium”  In _Econometrica_ 61.5, 1993, pp. 1019–1045  DOI: 10.2307/2951492
  * [Kri09] Vijay Krishna  “Auction Theory”  Academic Press, 2009
  * [LB17] Brendan Lucier and Allan Borodin  “Equilibria of greedy combinatorial auctions”  In _SIAM Journal on Computing_ 46.2 SIAM, 2017, pp. 620–660  DOI: 10.1137/15M1048720
  * [Leb06] Bernard Lebrun  “Uniqueness of the equilibrium in first-price auctions”  In _Games and Economic Behavior_ 55.1, 2006, pp. 131–151  DOI: 10.1016/j.geb.2005.01.006
  * [Leb96] Bernard Lebrun  “Existence of an Equilibrium in First Price Auctions”  In _Economic Theory_ 7, 1996, pp. 421–443  DOI: 10.1007/BF01213659
  * [Leb99] Bernard Lebrun  “First Price Auctions in the Asymmetric N Bidder Case”  In _International Economic Review_ 40.1, 1999, pp. 125–142  DOI: 10.1111/1468-2354.00008
  * [LP00] Alessandro Lizzeri and Nicola Persico  “Uniqueness and Existence of Equilibrium in Auctions with a Reserve Price”  In _Games and Economic Behavior_ 30.1, 2000, pp. 83–114  DOI: 10.1006/game.1998.0704
  * [MNT09] Peter Bro Miltersen, Jesper Buus Nielsen and Nikos Triandopoulos  “Privacy-enhancing auctions using rational cryptography”  In _Annual International Cryptology Conference_ , 2009, pp. 541–558  Springer  DOI: 10.1145/1807406.1807496
  * [MP91] Nimrod Megiddo and Christos H. Papadimitriou  “On total functions, existence theorems and computational complexity”  In _Theoretical Computer Science_ 81.2, 1991, pp. 317–324  DOI: 10.1016/0304-3975(91)90200-l
  * [MR00] Eric Maskin and John Riley  “Equilibrium in Sealed High Bid Auctions”  In _The Review of Economic Studies_ 67.3, 2000, pp. 439–454  DOI: 10.1111/1467-937X.00138
  * [MR03] Eric Maskin and John Riley  “Uniqueness of equilibrium in sealed high-bid auctions”  In _Games and Economic Behavior_ 45.2, 2003, pp. 395–409  DOI: 10.1016/S0899-8256(03)00150-7
  * [MR85] Eric S. Maskin and John G. Riley  “Auction theory with private values”  In _The American Economic Review_ 75.2, 1985, pp. 150–155  URL: https://www.jstor.org/stable/1805587
  * [MW85] Paul R. Milgrom and Robert J. Weber  “Distributional strategies for games with incomplete information”  In _Mathematics of Operations Research_ 10.4 INFORMS, 1985, pp. 619–632  DOI: 10.1287/moor.10.4.619
  * [Mye97] Roger B. Myerson  “Game Theory: Analysis of Conflict”  Harvard University Press, 1997
  * [Nas51] John Nash  “Non-cooperative games”  In _Annals of mathematics_ JSTOR, 1951, pp. 286–295
  * [Pap94] Christos H. Papadimitriou  “On the complexity of the parity argument and other inefficient proofs of existence”  In _Journal of Computer and System Sciences_ 48.3, 1994, pp. 498–532  DOI: 10.1016/s0022-0000(05)80063-7
  * [Plu92] Michael Plum  “Characterization and Computation of Nash-Equilibria for Auctions with Incomplete Information”  In _International Journal of Game Theory_ 20.4, 1992, pp. 393–418  DOI: 10.1007/bf01271133
  * [PP15] Christos Papadimitriou and George Pierrakos  “Optimal deterministic auctions with correlated priors”  In _Games and Economic Behavior_ 92 Elsevier, 2015, pp. 430–454  DOI: 10.1016/j.geb.2013.08.009
  * [PR08] Christos H. Papadimitriou and Tim Roughgarden  “Computing Correlated Equilibria in Multi-Player Games”  In _Journal of the ACM_ 55.3, 2008, pp. 141–1429  DOI: 10.1145/1379759.1379762
  * [PST20] Renato Paes Leme, Balasubramanian Sivan and Yifeng Teng  “Why Do Competitive Markets Converge to First-Price Auctions?”  In _Proceedings of The World Wide Web Conference (WWW)_ , 2020, pp. 596–605  DOI: 10.1145/3366423.3380142
  * [RS81] John G. Riley and William F. Samuelson  “Optimal Auctions”  In _The American Economic Review_ 71.3, 1981, pp. 381–392  URL: https://www.jstor.org/stable/1802786
  * [RW94] Ariel Rubinstein and Asher Wolinsky  “Rationalizable Conjectural Equilibrium: Between Nash and Rationalizability”  In _Games and Economic Behavior_ 6.2, 1994, pp. 299–311  DOI: 10.1006/game.1994.1016
  * [Sta24] Statista.com  “Annual revenue of Alphabet from 2017 to 2023, by segment” Accessed: 2024-02-12, 2024  URL: https://www.statista.com/statistics/633651/alphabet-annual-global-revenue-by-segment/
  * [Vic61] William Vickrey  “Counterspeculation, Auctions and Competitive Sealed Tenders”  In _Journal of Finance_ 16.1, 1961, pp. 8–37  DOI: 10.1111/j.1540-6261.1961.tb02789.x
  * [WP12] Jens Witkowski and David C. Parkes  “Peer prediction without a common prior”  In _Proceedings of the 13th ACM Conference on Electronic Commerce (EC)_ , 2012, pp. 964–981  DOI: 10.1145/2229012.2229085
  * [WSZ20] Zihe Wang, Weiran Shen and Song Zuo  “Bayesian Nash Equilibrium in First-Price Auction with Discrete Value Distributions”  In _Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_ , 2020, pp. 1458–1466  URL: https://dl.acm.org/doi/abs/10.5555/3398761.3398929