# First Price Auction is $1-1/e^{2}$ Efficient

Yaonan Jin Columbia University. Email<EMAIL_ADDRESS>Pinyan Lu Shanghai
University of Finance and Economics. Email<EMAIL_ADDRESS>
###### Abstract

We prove that the PoA of First Price Auctions is $1-1/e^{2}\approx 0.8647$,
closing the gap between the best known bounds $[0.7430,\,0.8689]$.

###### Contents

  1. 1 Introduction
    1. 1.1 Technical overview
  2. 2 Structural Results
    1. 2.1 The forward direction: Bayesian Nash Equilibria
    2. 2.2 The inverse direction: Bid-to-value mappings
    3. 2.3 Reformulation for the Price of Anarchy problem
  3. 3 Preprocessing Valid Instances
    1. 3.1 The concept of valid pseudo instances
    2. 3.2 Discretize: Towards (approximate) discrete pseudo instances
    3. 3.3 Translate: Vanishing the minimum winning bids
    4. 3.4 Layer: Rearranging the bid-to-value mappings
    5. 3.5 Polarize: Derandomizing the conditional values under zero bids
    6. 3.6 The floor/ceiling pseudo instances
  4. 4 Towards the Worst Case Pseudo Instances
    1. 4.1 Twin ceiling, strong ceiling, jumps, and potentials
    2. 4.2 Slice: From floor to ceiling
    3. 4.3 Collapse: From ceiling to strong ceiling
    4. 4.4 Halve: From strong ceiling towards twin ceiling, under pseudo jumps
    5. 4.5 Ascend-Descend: From strong ceiling towards twin ceiling, under real jumps
    6. 4.6 The main algorithm: From floor/ceiling to twin ceiling
  5. 5 Lower Bound Analysis
    1. 5.1 The expected auction Social Welfare
    2. 5.2 The optima are solutions to an ODE
    3. 5.3 Optimizing the parameters $(\lambda,\,\mu)$
  6. 6 Upper Bound Analysis

##  1 Introduction

In 1961, Vickrey [Vic61], a Nobel laureate in Economics, initiated auction
theory. At the center of his work was the solution concept of Nash equilibrium
[Nas50] for auctions as non-cooperative games. This game-theoretical approach
has shaped modern auction theory and has a tremendous influence also on other
areas in mathematical economics [HR04]. In particular, Vickrey systematically
investigated the first-price auction (or its equivalent, the Dutch auction),
the most common auction format in real business.

In the first-price auction, the auctioneer (seller) sells an indivisible item
to $n$ potential bidders (buyers). The rule is as simple as it is: All bidders
simultaneously submit bids to the auctioneer (each of which is unknown to the
other bidders); the highest bidder wins the item, paying his/her own bid.
Simple as the rule is, the bidders’ optimal bidding strategies can be
sophisticated. From one bidder’s own perspective, a higher bid means a higher
payment on winning but also a better chance of winning. Accordingly, this
bidder’s optimal bidding strategy depends on the competitive environment,
which in turn is determined by the other bidders’ bidding strategies. This
situation is perfectly a non-cooperative game and the standard solution
concept is Bayesian Nash equilibrium. To get a better sense, let us show a
warm-up example from Vickrey’s original work.

######  Example 1 ([Vic61]).

Consider two bidders: Alice and Bob have (independent) uniform random values
$v_{1},\,v_{2}\sim U[0,\,1]$ and respectively bid $b_{1}=\frac{v_{1}}{2}$ and
$b_{2}=\frac{v_{2}}{2}$. The value distributions and bidding strategies
determine the (independent) bid distributions of bidders. In this example,
they are (independent) uniform random bids $b_{1},\,b_{2}\sim
U[0,\,\frac{1}{2}]$, whose CDFs are $B_{1}(b)=B_{2}(b)=\min(2b,\,1)$. By
bidding $b\geq 0$, Alice wins with probability $\min(2b,\,1)$ and gains a
utility $(v_{1}-b)$ conditioned on winning. Her expected utility is
$(v_{1}-b)\cdot\min(2b,\,1)$, which is maximized when $b=\frac{v_{1}}{2}$.
Thus, her current strategy $b_{1}=\frac{v_{1}}{2}$ is optimal. By symmetry,
Bob’s current strategy $b_{2}=\frac{v_{2}}{2}$ is also optimal. In sum, the
above strategy profile $(b_{1},\,b_{2})=(\frac{v_{1}}{2},\,\frac{v_{2}}{2})$
is an equilibrium, in a sense that no bidder can gain a better utility by
deviating from his/her current strategy.

For clarity, let us formalize the model. Each bidder $i\in[n]$ independently
draws his/her value from a distribution $v_{i}\sim V_{i}$. Only with this
knowledge and depending on his/her own strategy $s_{i}$, bidder $i$ submits a
possibly random bid $b_{i}=s_{i}(v_{i})$. Then over the randomness of the
other bidders’ values $\boldsymbol{v}_{-i}=(v_{k})_{k\neq i}$ and strategies
$\boldsymbol{s}_{-i}=\\{s_{k}\\}_{k\neq i}$, bidder $i$ wins with probability
$\mathrm{x}_{i}(b_{i})\in[0,\,1]$ and gains an expected utility
$u_{i}(v_{i},\,b_{i})=(v_{i}-b_{i})\cdot\mathrm{x}_{i}(b_{i})$.

######  Definition 1.1 (Equilibria).

A strategy profile $\boldsymbol{s}=\\{s_{i}\\}_{i\in[n]}$ is a Bayesian Nash
Equilibrium when: For each bidder $i\in[n]$ and any possible value
$v\in\mathrm{supp}(V_{i})$, the current strategy $s_{i}(v)$ is optimal, namely
$\mathop{{\bf E}\/}_{s_{i}}\big{[}u_{i}(v,\,s_{i}(v))\big{]}\geq u_{i}(v,\,b)$
for any deviation bid $b\geq 0$.

Example 1 is special in that bidders have identically distributed values. This
symmetric setting is well understood: The first-price auction has a unique
Bayesian Nash equilibrium [CH13], which is fully efficient – The bidder with
the highest value always wins the item. Instead, the current trend focuses
more on the asymmetric setting, where bidders’ values are distinguished by
their distributions. Again, let us get a better sense through two concrete
examples.

######  Example 2.

Consider two bidders: Alice has a fixed value $v_{1}\equiv 2$ and always bids
$s_{1}(v_{1})\equiv 1$. Bob has a uniform random value $v_{2}\sim U[0,\,1]$
and truthfully bids his value $s_{2}(v_{2})=v_{2}$, namely the distribution
$B_{2}(b)=\min(b,\,1)$. By bidding $b\geq 0$, Alice gains an expected utility
$(v_{1}-b)\cdot\min(b,\,1)$, for which her current strategy
$s_{1}(v_{1})\equiv 1$ is optimal. Bob cannot gain a positive utility because
his value $v_{2}\sim U[0,\,1]$ is at most Alice’s bid $s_{1}(v_{1})\equiv 1$;
thus his current strategy $s_{2}(v_{2})=v_{2}$ is also optimal. In sum, this
strategy profile $(s_{1},s_{2})$ is an equilibrium.

Unlike the symmetric setting, this auction game has multiple equilibria. E.g.,
it is easy to verify that the same strategy $s_{1}(v_{1})\equiv 1$ for Alice
and a different strategy
$\widetilde{s}_{2}(v_{2})=\max(\frac{2v_{2}-1}{v_{2}},\,0)$ for Bob (namely
the distribution $\widetilde{B}_{2}(b)=\frac{1}{2-b}$ for $b\in[0,\,1]$) are
another equilibrium.

The both equilibria $(s_{1},\,s_{2})$ and $(s_{1},\,\widetilde{s}_{2})$ given
in Example 2 have two features: (i) The strategies $s_{1}(v_{1})$,
$s_{2}(v_{2})$ and $\widetilde{s}_{2}(v_{2})$ are pure strategies – Each of
them has no randomness, just the function of a value. (ii) The both equilibria
are fully efficient akin to the symmetric setting – Alice always has the
highest value $\equiv 2$ and always wins the item. However, these are not
always the case in the asymmetric setting, such as in the following example,
which only slightly modifies Example 2 by changing the fixed value of Alice
from $2$ to $1$.

######  Example 3.

Consider two bidders: Alice has a fixed value $v_{1}\equiv 1$ and bids
$s_{1}(v_{1})\sim B_{1}$ following the distribution
$B_{1}(b)=\frac{\exp((4b-3)/(2b-1))}{2\sqrt{4b^{2}-4b+1}}$ for
$b\in[\frac{1}{2},\,\frac{3}{4}]$. Bob has a uniform random value $v_{2}\sim
U[0,\,1]$ and bids $s_{2}(v_{2})=\max(\frac{4v_{2}-1}{4v_{2}},\,0)$, namely
the distribution $B_{2}(b)=\frac{1}{4-4b}$ for $b\in[0,\,\frac{3}{4}]$. By
bidding $b\geq 0$, Alice gains an expected utility $(v_{1}-b)\cdot B_{2}(b)$,
which is maximized $=\frac{1}{4}$ anywhere between $b\in[0,\,\frac{3}{4}]$, so
her current strategy $s_{1}(v_{1})\sim B_{1}$ is optimal. By elementary
calculus, we can see that Bob’s current strategy
$s_{2}(v_{2})=\max(\frac{4v_{2}-1}{4v_{2}},\,0)$ also is optimal. In sum, this
strategy profile $(s_{1},s_{2})$ is an equilibrium.

In Example 3: Alice has a mixed strategy – A fixed value $v_{1}\equiv 1$ but a
random bid $s_{1}(v_{1})\sim B_{1}$. Furthermore, the equilibrium
$(s_{1},\,s_{2})$ is not fully efficient. E.g., with a value
$v_{2}=\frac{3}{4}$, although not the highest value $<v_{1}\equiv 1$, Bob bids
$s_{2}(v_{2})=\frac{2}{3}$ and wins with probability
$B_{1}(\frac{2}{3})=\frac{3}{2e}\approx 0.5518$. Indeed, Example 3 has
infinite equilibria, among which the given one $(s_{1},s_{2})$ has the
relatively “simplest” format. But none of those equilibria is a pure
equilibrium or is fully efficient, despite that Example 3 is only a minor
modification of Example 2.

From the above examples, we observe that Bayesian Nash equilibria can be very
complicated and sensitive to the value distributions, despite the intrinsic
simple rule of the first-price auction. After an extensive study for more than
60 years, the first-price auction and its equilibria remain the centerpiece of
modern auction theory and have promoted a rich literature; see [SZ90, Leb06,
Leb96, Leb99, MR00a, MR00b, JSSZ02, MR03, HKMN11, CH13, ST13, Syr14, HHT14,
FLN16, HTW18, WSZ20, FGH+21] etc. These efforts are justifiable since the
study of the first-price auction and its equilibria is both theoretically
challenging and practically important.

Among various aspects of the first-price auction, efficiency at equilibria is
of primary interest. In economics, efficiency measures to what extent a
recourse can be allocated to the persons who value it the most, thus
maximizing the social welfare, particularly in a competitive environment. As
shown above (Example 3), the first-price auction generally is not fully
efficient at an equilibrium: The winner has the highest bid but possibly not
the highest value; this crucially depends on both (i) the instance
$\boldsymbol{V}$ itself and (ii) which Bayesian Nash equilibrium
$\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V})$ it falls into. Earlier works
in economics focus on (generalizing) the conditions for the value distribution
$\boldsymbol{V}=\\{V_{i}\\}_{i\in[n]}$ that guarantee the full efficiency.

However, the quality of (in)efficiency should not be all-or-nothing. E.g.,
when the highest value is $1$, a value-$0.99$ bidder versus a value-$0.01$
bidder is very different, although neither of them is fully efficient. Towards
a quantitative analysis, Koutsoupias and Papadimitriou introduced a new
measure on the efficiency degradation under selfish behaviors, the Price of
Anarchy [KP99] (which is an analog of the “approximation ratio” in theoretical
computer science). For the first-price auction, denote by ${\sf
OPT}(\boldsymbol{V})$ the expected optimal social welfare from an instance
$\boldsymbol{V}$, and by ${\sf FPA}(\boldsymbol{V},\,\boldsymbol{s})$ the
expected social welfare at an equilibrium
$\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V})$, then the Price of Anarchy is
defined to be the minimum possible ratio, as follows.

######  Definition 1.2 (Price of Anarchy).

Regarding First Price Auctions, the Price of Anarchy is given by

${\sf PoA}~{}:=~{}\inf\bigg{\\{}\,\frac{{\sf
FPA}(\boldsymbol{V},\,\boldsymbol{s})}{{\sf
OPT}(\boldsymbol{V})}\,\,\bigg{|}\,\bigg{.}\,\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V})~{}\text{and}~{}{\sf
OPT}(\boldsymbol{V})<+\infty\,\bigg{\\}}.$

The Price of Anarchy is bounded between $[0,\,1]$. Namely, a larger ratio
means a higher efficiency and the $=1$ ratio means the full efficiency. For
the first-price auction, Syrgkanis and Tardos first proved that the PoA is at
least $1-1/e\approx 0.6321$ [ST13]. Later, Hoy, Taggart and Wang derived an
improved lower bound of $\approx 0.7430$ [HTW18]. On the other hand, Hartline,
Hoy and Taggart gave a concrete instance of ratio $\approx 0.8689$ [HHT14],
which remains the best known upper bound.

Despite the prevalence of the first-price auction and much effort in studying
its efficiency, there has been a persistent gap in the state of the art. In
the current paper, we will completely solve this long-standing open problem.

######  Theorem 1 (Tight PoA).

The Price of Anarchy in First Price Auctions is $1-1/e^{2}\approx 0.8647$.

Remarkably, neither the best known lower bound $\approx 0.7430$ nor the upper
bound $\approx 0.8689$ is tight; we close the gap by improving both of them.
Our tight bound $1-1/e^{2}\approx 0.8647$ not only is a mathematically elegant
result but has further implications in real business since it is fairly close
to $1$. Namely, at any equilibrium, the efficiency degradation in the first-
price auction is small, no worse than 13.53%, which might be acceptable given
other merits of the first-price auction.

En route to the tight PoA, we obtain many new important perspectives,
characterizations, and properties of equilibria in the first-price auction.
These might be of independent interest and find applications in the future
study of other aspects of the first-price auction, e.g., the complexity of
computing equilibria. Beyond the first-price auction, our overall approach is
general enough and might help determine the Price of Anarchy in other
auctions.

###  1.1 Technical overview

This subsection sketches our high-level proof ideas. To ease the readability,
some descriptions are roughly accurate but not perfectly, and most technical
details are deferred to Sections 2, 3, 4, 5 and 6. Our approach is very
different from the prior works [ST13, HTW18], which mainly adopt the
smoothness techniques or the extension. More concretely, we employ the first
principle approach that, directly characterizes the worst-case instance and
the worst-case Bayesian Nash equilibrium regarding the definition of the Price
of Anarchy. To this end, we step by step narrow down the search space of the
worst case by proving more and more necessary conditions it must satisfy.
Finally, we capture the exact worst case and thus derive the tight PoA bound.

### Changing the viewpoints (Section 2)

Regarding the PoA definition, we need to prove that the auction social welfare
${\sf FPA}(\boldsymbol{V},\,\boldsymbol{s})$ is within a certain ratio of the
optimal social welfare ${\sf OPT}(\boldsymbol{V})$, given any value
distribution $\boldsymbol{V}=\\{V_{i}\\}_{i\in[n]}$ and any equilibrium
thereof $\boldsymbol{s}=\\{s_{i}\\}_{i\in[n]}$.

Two difficulties emerge immediately: (i) One value distribution
$\boldsymbol{V}\in\mathbb{V}$ generally has multiple or even infinite
equilibria. (ii) One equilibrium
$\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V})$ generally has no analytic
solution; even an efficient algorithm for computing (approximate) equilibria
from value distributions is unknown.

To the rescue, instead of the original value-strategy representation
$(\boldsymbol{V},\,\boldsymbol{s})\in\mathbb{V}\times\mathbb{BNE}$ of
equilibria, we use another representation, the bid distributions
$\boldsymbol{B}(\boldsymbol{V},\,\boldsymbol{s})$ resulted from equilibria.
These two representations and their relationship are demonstrated in Figure 1.
Given one equilibrium bid distribution
$\boldsymbol{B}(\boldsymbol{V},\,\boldsymbol{s})=\\{B_{i}\\}_{i\in[n]}$: (i)
One equilibrium
$(\boldsymbol{V},\,\boldsymbol{s})\in\mathbb{V}\times\mathbb{BNE}$ is uniquely
determined. (ii) The reconstruction of the $(\boldsymbol{V},\,\boldsymbol{s})$
essentially has an analytic solution, through the bid-to-value mappings
$\varphi_{i}(b):=b+(\sum_{k\neq i}B^{\prime}_{k}(b)/B_{k}(b))^{-1}$ that are
almost the inverse functions of the strategies
$\boldsymbol{s}=\\{s_{i}\\}_{i\in[n]}$.111Although the mapping formulas
$\varphi_{i}(b)=b+(\sum_{k\neq i}B^{\prime}_{k}(b)/B_{k}(b))^{-1}$ are
previously known, NO prior work takes ANY further step. Even this structure
result is unknown: “One (valid) bid distribution
$\boldsymbol{B}\in\mathbb{B}_{\sf valid}$ backward uniquely decides the
underlying value-strategy tuple
$(\boldsymbol{V},\,\boldsymbol{s})\in\mathbb{V}\times\mathbb{BNE}$”; let alone
techniques towards the tight ${\sf PoA}=1-1/e^{2}$. These mitigate the above
two difficulties.

In sum, there is a bijection between the space of equilibria
$\mathbb{V}\times\mathbb{BNE}\ni(\boldsymbol{V},\,\boldsymbol{s})$ and the
space of equilibrium bid distributions
$\\{\boldsymbol{B}(\boldsymbol{V},\,\boldsymbol{s})\\}$. Further, the new
representation $\\{\boldsymbol{B}(\boldsymbol{V},\,\boldsymbol{s})\\}$ is
mathematically equivalent but technically easier – this is one infinite set
instead of the Cartesian product $\mathbb{V}\times\mathbb{BNE}$ of two
infinite sets – showing an avenue towards the tight PoA. (Later in Sections 2,
3, 4, 5 and 6, we will see more advantages.)

Space $\mathbb{V}$Space $\mathbb{B}_{\sf
valid}$$\boldsymbol{V}$$\boldsymbol{B}$$\overline{\boldsymbol{B}}$$\widehat{\boldsymbol{B}}$$\widetilde{\boldsymbol{V}}$$\widetilde{\boldsymbol{B}}$$\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V})$$\overline{\boldsymbol{s}}\in\mathbb{BNE}(\boldsymbol{V})$$\widehat{\boldsymbol{s}}\in\mathbb{BNE}(\boldsymbol{V})$$\widetilde{\boldsymbol{s}}\in\mathbb{BNE}(\boldsymbol{V})$

(a) Forward direction: $\mathbb{V}\times\mathbb{BNE}\mapsto\mathbb{B}_{\sf
valid}$

Space $\mathbb{V}\times\mathbb{BNE}$Space $\mathbb{B}_{\sf
valid}$$(\boldsymbol{V},\,\boldsymbol{s})$$\boldsymbol{B}$$(\boldsymbol{V},\,\overline{\boldsymbol{s}})$$\overline{\boldsymbol{B}}$$(\boldsymbol{V},\,\widehat{\boldsymbol{s}})$$\widehat{\boldsymbol{B}}$$(\widetilde{\boldsymbol{V}},\,\widetilde{\boldsymbol{s}})$$\widetilde{\boldsymbol{B}}$

(b) Inverse direction: $\mathbb{B}_{\sf
valid}\mapsto\mathbb{V}\times\mathbb{BNE}$

Figure 1: Demonstration for the two representations of equilibrium, (i) the
value-strategy representation
$(\boldsymbol{V},\,\boldsymbol{s})\in\mathbb{V}\times\mathbb{BNE}$ versus (ii)
the bid distribution representation
$\boldsymbol{B}=\boldsymbol{B}(\boldsymbol{V},\,\boldsymbol{s})\in\mathbb{B}_{\sf
valid}$. One value distribution $\boldsymbol{V}$ has multiple or even infinite
equilibria $\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V})$; each equilibrium
induces one valid bid distribution
$\boldsymbol{B}=\boldsymbol{B}(\boldsymbol{V},\,\boldsymbol{s})\in\mathbb{B}_{\sf
valid}$. Backward, the $\boldsymbol{B}$ decides the underlying tuple
$(\boldsymbol{V},\,\boldsymbol{s})\in\mathbb{V}\times\mathbb{BNE}$ via the
bid-to-value mappings $\boldsymbol{\varphi}$. Hence, there is a bijection
between the two spaces $\mathbb{V}\times\mathbb{BNE}$ and $\mathbb{B}_{\sf
valid}$.

Nonetheless, there is no free lunch. The new representation has two drawbacks.
(i) Unlike that any value distribution $\boldsymbol{V}\in\mathbb{V}$ must be
feasible since the existence of an equilibrium
$\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V})$ is promised [Leb96],222This
existence result requires suitable tie-breaking rules in the first-price
auction; see Section 2 for more details. a generic bid distribution
$\boldsymbol{B}$ not necessarily induces an equilibrium. To remedy this issue,
we introduce the notion of validity, which almost refers to monotonicity of
the bid-to-value mappings $\boldsymbol{\varphi}=\\{\varphi_{i}\\}_{i\in[n]}$.
In addition, (ii) a mapping $\varphi_{i}$ is undefined at a singular point
where the equilibrium bid distribution $B_{i}$ of that bidder $i\in[n]$ has a
probability mass, which must be handled separately. Luckily, such probability
masses are possible only at the left endpoint of the distribution’s support.
So, we further consider the conditional value distribution $P$ given one’s bid
being at the left endpoint. Indeed, the concept of validity refers to a tuple
$(\boldsymbol{B},\,P)$ of equilibrium bid distributions and a conditional
value distribution.

More rigorously, our new representation considers all the valid
tuples/instances $(\boldsymbol{B},\,P)\in\mathbb{B}_{\sf valid}$. Here, the
valid distributions $\boldsymbol{B}$ can be replaced with the increasing bid-
to-value mappings $\boldsymbol{\varphi}$: One decides the other and vice versa
(Lemma 3.4). More importantly, monotonicity of the mappings
$\boldsymbol{\varphi}$ gives a strong geometric intuition, making the third
representation $(\boldsymbol{\varphi},\,P)$ of equilibrium more convenient for
our later use. Especially, in what follows, the figures of the mappings
$\boldsymbol{\varphi}=\\{\varphi_{i}\\}_{i\in[n]}$ play the role of visual
demonstrations, i.e., horizontal bid axes and vertical value axes, where each
mapping $\varphi_{i}$ denotes one bidder $i\in[n]$.

### The worst-case instance (Section 6)

Our overall approach is to reduce any given instance to the worst-case
instance step by step. Thus, it is helpful to describe the worst case in
advance, which explains why we design those reductions since our target is
very specific.

The worst case has $n+1$ bidders, one bidder $H$ with a fixed high value
$v_{H}\equiv 1$ and sufficiently many $n\gg 1$ identical low-value bidders
$\\{\sqrt[n]{L}\\}^{\otimes n}$. Among the low-value bidders, the highest
value $v_{L}\sim V_{L}$ is distributed following the parametric equation
$V_{L}(1-t\cdot e^{2-2t})=4/t^{2}\cdot e^{2t-4}$ for $t\in[1,\,2]$, over the
value support $v_{L}\in\mathrm{supp}(V_{L})=[0,\,1-2/e^{2}]$. See Figure 2a
for a visual aid, based on the bid-to-value mappings
$\varphi_{H}\otimes\\{\varphi_{L}\\}^{\otimes n}$.

The equilibrium strategies $s_{H}\otimes\\{s_{L}\\}^{\otimes n}$ and the bid
distributions $H\otimes\\{\sqrt[n]{L}\\}^{\otimes n}$ are less important for
understanding our approach; we defer a description and the proof of the tight
PoA $=1-1/e^{2}$ to Section 6. The parametric equation $V_{L}$ also is less
important, included just for completeness.

In contrast, the point is the underlying structure: The bidder $H$ always
contributes the optimal social welfare $\equiv 1$. The low-value bidders
$\\{\sqrt[n]{L}\\}^{\otimes n}$ individually have negligible effects (the
winning probabilities etc) but collectively make the auction game less
efficient.

We are inspired by the instance due to Hartline, Hoy and Taggart [HHT14],
which has the same $H\otimes\\{\sqrt[n]{L}\\}^{\otimes n}$ structure. Our
construction differs from theirs in the concrete distributions, hence a
slightly worse PoA of $1-1/e^{2}\approx 0.8647$ in comparison with their ratio
of $\approx 0.8689$.333[HHT14] “just” considered a reasonable instance
$H(b)=\sqrt{b/\lambda}$ and $L(b)=\frac{1-\lambda}{1-b}$ for $\lambda=0.57$,
but neither gave argument/evidence for “worstness” of the instance family
$H\otimes\\{\sqrt[n]{L}\\}^{\otimes n}$, nor searched the worst case
$(H^{*},\,\lambda^{*})$. In contrast, our contributions are twofold: (primary)
“worstness” of this family; (secondary) the nontrivial worst case
$b=1-{4H^{*}}\cdot{e^{2-4\sqrt{H^{*}}}}$ and
$L^{*}(b)=\frac{1-\lambda^{*}}{1-b}$ for $\lambda^{*}=1-4/e^{2}$. In this
family, the PoA is less sensitive to different instances, hence two
numerically close bounds $0.8689$ versus $0.8647$.

(a)  The worst-case pseudo instance $H\otimes L$

(b)  A non collapsed nearly worst-case instance

Figure 2: Demonstration for the worst-case pseudo instance and the Collapse
reduction.
Figure 2a: The bidder $H$ has a fixed high value $\varphi_{H}(b)\equiv 1$ for
$b\in[0,\,1-4/e^{2}]$ and the pseudo bidder $L$ has the (parametric) bid-to-
value mapping $\varphi_{L}(1-t^{2}\cdot e^{2-2t})=1-t\cdot e^{2-2t}$ for
$t\in[1,\,2]$.
Figure 2b: When a specific bidder $i\in[n]$ has a fixed high value
$\varphi_{i}(b)\equiv v_{i}\geq\max\\{\varphi_{k}(b):k\neq i\\}$, over the bid
support $b\in[\gamma,\,\lambda]$, the Collapse reduction transforms this
instance $\boldsymbol{B}=B_{i}\otimes\boldsymbol{B}_{-i}$ to a two-bidder
pseudo instance $B_{i}\otimes\widetilde{L}$ that yields a worse-or-equal PoA.

### The pseudo instances (Section 3.1) and LABEL:alg:collapse (Section 4.3)

Rigorously, the worst case $H\otimes\\{\sqrt[n]{L}\\}^{\otimes n}$ for $n\gg
1$ described above is not a specific instance, but a sequence of instances
with the limit $n\to+\infty$ being the worst case. This incurs some notational
inconvenience. When such issues occur in real/complex analysis, the standard
method is to add the infinite point(s) to the space of the real/complex
numbers, making the space more complete. In the same spirit, we introduce the
notion of pseudo bidders and pseudo instances (Definition 3.1), thus including
the above limit to our search space.

In our extended language, the worst case has a succinct format: one high-value
bidder $H$ and one pseudo bidder $L$, namely a two-bidder pseudo instance
(Figure 2a). Beyond notational brevity, the notion of pseudo bidders/instances
also simplifies our proof in several places.

This extension does not hurt our proof, given that pseudo instances are only
considered in the lower-bound analysis. Precisely, we show that even the worst
case in the extended search space has the PoA $\geq 1-1/e^{2}$, implying a
lower bound of $1-1/e^{2}$ for the original problem. In addition, the upper-
bound analysis leverages the above instance sequence
$H\otimes\\{\sqrt[n]{L}\\}^{\otimes n}$. Precisely, we show that when the
$n\gg 1$ is sufficiently large, the PoA can be arbitrarily close to
$1-1/e^{2}$. As a combination, the tight PoA in Theorem 1 gets established.

Another related thing is the LABEL:alg:collapse reduction. As Figure 2b shows,
when a specific bidder $i\in[n]$ has a fixed high value $\varphi_{i}(b)\equiv
v_{i}\geq\max\\{\varphi_{k}(b):k\neq i\\}$ over the bid support
$b\in[\gamma,\,\lambda]$, the LABEL:alg:collapse reduction can replace all the
other bidders $\\{B_{k}\\}_{k\neq i}$ by one pseudo bidder $\widetilde{L}$,
resulting in a two-bidder pseudo instance $B_{i}\otimes\widetilde{L}$ that has
a worse-or-equal PoA. Such a pseudo instance $B_{i}\otimes\widetilde{L}$ will
be easy to handle since it has the same shape as the worst case $H\otimes L$.

In sum, the remaining task is to transform every valid instance
$\in\mathbb{B}_{\sf valid}$ into a specific instance that the Collapse
reduction can work on, i.e., an instance that has one fixed-high-value bidder.

###  LABEL:alg:layer (Section 3.4): Hierarchizing the bidders

(a)  The input increasing mappings $\boldsymbol{\varphi}$

(b)  The output layered mappings $\widetilde{\boldsymbol{\varphi}}$

Figure 3: The Layer reduction. Each color corresponds to a bidder. After the
reduction, the bidders are ordered. For example, the red bidder is the highest
bidder.

To transform a given instance into the worst case, we shall identify one
special high-value bidder $H\in[n]$ and “derandomize” his/her value, i.e.,
making the bid-to-value mapping a constant function $\varphi_{H}(b)\equiv
v_{H}$. (If so, upon scaling, we can normalize this fixed value $v_{H}=1$.)
But it is even unclear which bidder $i\in[n]$ should be the candidate: The
highest-value bidder $\mathop{\mathrm{argmax}}\\{\varphi_{i}(b):i\in[n]\\}$ at
different bids $b\in[\gamma,\,\lambda]$ can be different. More concretely,
consider the example in Figure 3a, the highest-value bidder is the red bidder
$B_{1}$ initially for small bids, but changes to the blue bidder $B_{2}$ later
for large bids.

We can segment the bid-to-value mappings into pieces and rearrange them, in a
sense of Figure 3b, making them ordered point-wise
$\widetilde{\varphi}_{1}(b)\geq\dots\geq\widetilde{\varphi}_{n}(b)$. Then, the
candidate high-value bidder clearly is the index-$1$ bidder
$\widetilde{B}_{1}$ (i.e., the red one in Figure 3b). We call this reduction
LABEL:alg:layer.

Under the LABEL:alg:layer reduction, the auction/optimal social welfares FPA
and OPT each remain the same, so the PoA is invariant. This proof is not that
technically involved, once we formalize the reduction. However, without
switching our viewpoint to the bid-to-value mappings
$\boldsymbol{\varphi}=\\{\varphi_{i}\\}_{i\in[n]}$, even describing this
reduction seems difficult.

In sum, we narrow down the search space to the “layered” instances and the
remaining task to address the candidate high-value bidder $B_{1}$, especially
derandomizing his/her value $\varphi_{1}(b)\equiv v_{1}$.

###  LABEL:alg:discretize and LABEL:alg:translate (Sections 3.2 and 3.3): Two
simplifications

(a)  The input increasing mappings $\boldsymbol{\varphi}$

(b)  The out discretized/translated mappings
$\widetilde{\boldsymbol{\varphi}}$

Figure 4: The Discretize and Translate reductions

Our main reduction is an iterative algorithm; thus it is convenient to work
with bounded discrete instances, for which the main reduction will terminate
in finite iterations. Such an idea appears in many prior works [CGL14, AHN+19,
JLTX20, JLQ+19, JJLZ21], and the proof plan is twofold: (i) For any bounded
discrete instance, the PoA is at least $1-1/e^{2}$. (ii) For any valid
instance, there exists a bounded discrete instance approximating the PoA, up
to an arbitrary but fixed error $\varepsilon>0$. As a combination, the PoA for
any valid instance is at least $1-1/e^{2}$.

However, our discretization scheme is subtle. First, we cannot discretize the
valid bid distributions $\boldsymbol{B}$ given that they must be continuous
everywhere except the left endpoint of the bid support. Second, we cannot
discretize the value distributions and the strategies
$(\boldsymbol{V},\,\boldsymbol{s})$. Although bounded discrete value
distributions $\widetilde{\boldsymbol{V}}$ that well approximate the given
ones $\boldsymbol{V}$ are trivial, it is unclear how to obtain desirable
strategies
$\widetilde{\boldsymbol{s}}\in\mathbb{BNE}(\widetilde{\boldsymbol{V}})$: No
algorithm for computing equilibria from value distributions is available.
Also, with modified value distributions, even the existence of
$\widetilde{\boldsymbol{s}}\in\mathbb{BNE}(\widetilde{\boldsymbol{V}})$ that
is “close enough” to the given equilibrium
$\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V})$ is doubtful.

We circumvent these issues by discretizing the bid-to-value mappings
$\boldsymbol{\varphi}$ instead (Figure 4), i.e., approximating them through
piecewise constant functions $\widetilde{\boldsymbol{\varphi}}$.444In real
analysis, for various purposes, piecewise constant functions (a.k.a. simple
functions) are widely used as approximations to general functions. The
benefits are threefold: (i) The valid bid distributions
$\widetilde{\boldsymbol{B}}$, the value distributions
$\widetilde{\boldsymbol{V}}$, and the equilibrium strategies
$\widetilde{\boldsymbol{s}}\in\mathbb{BNE}(\widetilde{\boldsymbol{V}})$ can be
reconstructed from the new mappings $\widetilde{\boldsymbol{\varphi}}$,
through analytic expressions. (ii) The piecewise constancy of the new mappings
$\widetilde{\boldsymbol{\varphi}}$ makes the value distribution
$\widetilde{\boldsymbol{V}}$ bounded and discrete. (iii) More importantly, we
are able to obtain a sequence of piecewise constant mappings
$\\{\widetilde{\boldsymbol{\varphi}}\\}$ that pointwise converge to the given
ones $\boldsymbol{\varphi}$. The corresponding
$\\{\widetilde{\boldsymbol{B}}\\}$, $\\{\widetilde{\boldsymbol{V}}\\}$, and
$\\{\widetilde{\boldsymbol{s}}\\}$ can be arbitrarily close to the given
$\boldsymbol{B}$, $\boldsymbol{V}$, and $\boldsymbol{s}$, approximating the
PoA up to any fixed error $\varepsilon>0$. This exactly implements the second
part of our proof plan.

Afterward, the LABEL:alg:translate reduction further vanishes the lowest bid,
through shifting both the value space and the bid space by the same distance
(Figure 4) – Again, a worse-or-equal PoA.

In sum, we can focus on piecewise constant and increasing mappings
$\boldsymbol{\varphi}$ over a bounded support $b\in[0,\,\lambda]$, together
with the conditional value $P$ given the nil bid $b=0$ (i.e., the left
endpoint).

###  LABEL:alg:polarize and LABEL:alg:slice (Sections 3.5 and 4.2): Dealing
with the probability masses

Now we address the probability masses and the conditional value $P$. (This is
the only information that cannot be reconstructed from the bid-to-value
mappings $\boldsymbol{\varphi}$ and must be handled separately.) Our main
observation is (Lemma 2.16) that at most one bidder can have a nontrivial
conditional value $P$, who will be called the monopolist $H$. (After the
LABEL:alg:layer reduction, this monopolist $H$ will be the high-value bidder;
cf. Figure 3.) That is why we can use a single conditional value $P$, instead
of $n$ values akin to the distributions $\boldsymbol{V}$ or $\boldsymbol{B}$.
Moreover, following the monotonicity, this value $P$ is supported on
$[0,\varphi_{H}(0)]$.

The LABEL:alg:polarize reduction derandomizes the conditional value by moving
all the probabilities to either $P\equiv 0$ or $P\equiv\varphi_{H}(0)$.
Namely, this is a win-win reduction, in a sense that at least one of the two
possibilities $P\equiv 0$ and $P\equiv\varphi_{H}(0)$ induces a worse-or-equal
PoA than the given instance. Later, such win-win reductions also appear in
several other places.

Further, the LABEL:alg:slice reduction totally determines the conditional
value $P\equiv\varphi_{H}(0)$ by eliminating the other possibility. This
reduction modifies both the conditional value $P$ and the mappings
$\boldsymbol{\varphi}$, thus far more complicated than the LABEL:alg:polarize
reduction, which only modifies the $P$.555For very technical reasons, we
should not unify LABEL:alg:polarize and LABEL:alg:slice into a single
reduction (cf. Sections 3 and 4).

In conclusion, we can drop the notation $P$ hereafter: Just the piecewise
constant and increasing mappings $\boldsymbol{\varphi}$ are enough to describe
the entire instance and the reductions on it.

###  9 and 10 (Sections 4.4 and 4.5): The main reductions

Our main reduction aims to reduce the number of pieces of the high-value
bidder $H$’s mapping $\varphi_{H}$. (After the LABEL:alg:discretize reduction,
this mapping has finite many pieces. Especially, the one in the worst-case
instance has one single piece (Figure 2a), namely a constant mapping.) To this
end, we look at the first jump point of this mapping $\varphi_{H}$.
Furthermore, we distinguish two types of jumps, pseudo jumps versus real
jumps, and adopt two different reductions respectively.

For a 4.4 (LABEL:fig:intro:halve:input), the after-jump parts of all mappings
$\boldsymbol{\varphi}$ are universally higher than the before-jump parts, so
the entire instance naturally divides into the left-lower part versus the
right-upper part (LABEL:fig:intro:halve:left and LABEL:fig:intro:halve:right).
We prove that at least one part induces a worse-or-equal PoA than the given
instance.666Especially, for the right-upper part, we reapply the
LABEL:alg:translate reduction to make the bid space start from $0$. This is
another win-win reduction and will be called 9.

For a 4.5 (LABEL:fig:intro:AD:input), the after-jump parts (of some mappings)
still interlace with the before-jump parts. We would modify the first two
pieces of the high-value mapping $\varphi_{H}$ to reduce the number of pieces
by one. I.e., we either ascend the first piece to the value of the second
piece (LABEL:fig:intro:AD:ascend) or descend the second piece to the value of
the first piece (LABEL:fig:intro:AD:descend). We show that at least one
modification gives a worse-or-equal PoA than the given instance. This is again
a win-win reduction and will be called 10.

To conclude, whether a 4.4 or a 4.5, we obtain a new instance that (i) has a
worse-or-equal PoA and (ii) the high-value mapping $\varphi_{H}$ has one fewer
piece. Clearly, we can iterate the entire process until a constant mapping
$\varphi_{H}(b)\equiv v_{H}$, i.e., one single piece. Then, the
LABEL:alg:collapse reduction can replace all the other bidders
$\\{B_{k}\\}_{k\neq H}$ by one pseudo bidder $L$, hence a two-bidder pseudo
instance $H\otimes L$ that has the same shape as the worst case (Figure 2), as
desired.

We stress again that the above description is greatly simplified and thus just
roughly accurate – The high-level idea is delivered, but most technical
details are hidden.

### Solving the functional optimization (Section 5)

After the above reductions, we get a nice-looking instance: (i) one bidder $H$
with a fixed high value $\varphi_{H}(b)\equiv v_{H}$ and (ii) infinite
$n\to+\infty$ identical low-value bidders $\\{\sqrt[n]{L}\\}^{\otimes n}$, or
one pseudo bidder $L$ in our extended language. Towards the worst case, it
remains to decide the pseudo mapping $\varphi_{L}(b)$, or essentially, the
high-value bidder $H$’s bid distribution.

This is accomplished by standard tools from the calculus of variations. Via
the Euler-Lagrange equation [GS+00], we formulate the worst-case bid
distribution $H$ as the solution to an ordinary differential equation (ODE).
Luckily, this ODE admits a closed-form solution, and “coincidentally” the
tight bound $1-1/e^{2}$ is pretty nice-looking.

### Comparison with previous techniques

On the Price of Anarchy in auctions, the canonical approach is the smoothness
framework proposed by Roughgarden [Rou15] and developed by Syrgkanis and
Tardos [ST13]. The past decade has seen an abundance of its applications and
extensions (cf. the survey [RST17]).

However, the smoothness framework has an intrinsic restriction – It focuses on
the structure of an auction game BUT ignores the independence, i.e., both the
independence of value distributions $\boldsymbol{V}=\\{V_{i}\\}_{i\in[n]}$ and
the independence of strategies $\boldsymbol{s}=\\{s_{i}\\}_{i\in[n]}$. Thus,
although giving an arsenal of tools for proving lower bounds, this approach
seems hard to access tight bounds for some auctions. Especially for the first-
price auction, the smoothness-based bound of $1-1/e\approx 0.6321$ by
Syrgkanis and Tardos [ST13] is tight when correlated distributions are
allowed. Therefore, this bound cannot be improved without taking the
independence into account.

The work by Hoy, Taggart, and Wang [HTW18] is one of the very few follow-ups
that transcend the smoothness framework.777To the best of our knowledge,
[HTW18] is the only work for Bayesian single-item auctions that transcends the
smoothness framework. Other such works for multi-item auctions are thoroughly
discussed in [RST17, Section 8.3]. For the first-price auction, they show an
improved lower bound of $\approx 0.7430$, but still not tight. Technically,
the improvement stems from an extension of the smoothness framework that
leverages the independence.

In sum, towards tight bounds for the first-price auction and the beyond, the
primary consideration is: What is the consequence of the independence of
values $\boldsymbol{v}=(v_{i})_{i\in[n]}\sim\boldsymbol{V}$ and strategies
$\boldsymbol{s}$? Our answer is, the bids
$\boldsymbol{s}(\boldsymbol{v})=(s_{i}(v_{i}))_{i\in[n]}$ are also independent
and follow a product distribution $\boldsymbol{B}=\\{B_{i}\\}_{i\in[n]}$. This
is the starting point of our overall approach.

In the literature, ALL prior works (within/beyond the smoothness framework)
follow the proof paradigm: “searching over value distributions
$\boldsymbol{V}\in\mathbb{V}$ and equilibrium strategies
$\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V})$ plus deviation strategies
thereof $\boldsymbol{s}^{\prime}\neq\boldsymbol{s}$” [RST17, Section 8.3].
Instead, we present the FIRST different proof paradigm: “searching over
(valid) bid distributions
$\boldsymbol{B}=\boldsymbol{B}(\boldsymbol{V},\,\boldsymbol{s})\in\mathbb{B}_{\sf
valid}$ that are resulted from certain value-strategy tuples
$(\boldsymbol{V},\,\boldsymbol{s})\in\mathbb{V}\times\mathbb{BNE}$”.

In our main proof, we step by step narrow down the search space of the worst-
case instance, by showing stronger and stronger conditions it must satisfy,
and completely capture the worst-case instance eventually. En route, an
abundance of tools is developed, which may find applications in the future. It
is conceivable that our approach can be adapted to other auctions. So, we hope
that this would develop into a complement to the smoothness framework,
especially in the setting of independent distributions.

##  2 Structural Results

This section shows a bunch of structural results on First Price Auction and
Bayesian Nash Equilibrium. Some results or their analogs may already appear in
the literature [SZ90, Leb96, MR00a, MR00b, JSSZ02, MR03, HKMN11, CH13].
However, we still formalize and reprove them for completeness. Provided these
structural results, we can reformulate the Price of Anarchy problem in terms
of bid distributions rather than value distributions.

To sell a single indivisible item to one of $n\geq 1$ bidders, each bidder
$i\in[n]$ is asked to submit a non-negative bid $b_{i}\geq 0$. A generic
auction $\mathcal{A}=(\mathrm{x},\,\boldsymbol{\rho})$ is given by its
allocation rule $\mathrm{x}(\boldsymbol{b}):\mathbb{R}^{n}\mapsto[n]$ and
payment rule
$\boldsymbol{\rho}(\boldsymbol{b})=(\rho_{i}(\boldsymbol{b}))_{i\in[n]}:\mathbb{R}^{n}\to\mathbb{R}^{n}$,
both of which can be randomized. Concretely, the item is allocated to the
bidder $\mathrm{x}(\boldsymbol{b})\in[n]$, and $\rho_{i}(\boldsymbol{b})$’s
are the payments of bidders $i\in[n]$.

Rigorously, First Price Auction is not a single auction but a family of
auctions, each of which has a specific allocation rule that obeys the • ‣
2.1/• ‣ 2.1 principles.

######  Definition 2.1 (First Price Auctions).

An $n$-bidder single-item auction
$\mathcal{A}=(\mathrm{x},\,\boldsymbol{\rho})$ is called a First Price Auction
when its allocation rule $\mathrm{x}(\boldsymbol{b})$ and payment rule
$\boldsymbol{\rho}(\boldsymbol{b})=(\rho_{i}(\boldsymbol{b}))_{i\in[n]}$
satisfy that:

  * •

first price allocation: Let
$X(\boldsymbol{b}):=\mathop{\mathrm{argmax}}\big{\\{}b_{i}:i\in[n]\big{\\}}$
be the set of first-order bidders. When such bidders are not unique
$|X(\boldsymbol{b})|\geq 2$, allocate the item to one of them
$\mathrm{x}(\boldsymbol{b})\in X(\boldsymbol{b})$, through a (randomized) tie-
breaking rule given by the auction $\mathcal{A}$ itself on this bid profile
$\boldsymbol{b}$. When such a bidder is unique $|X(\boldsymbol{b})|=1$,
allocate the item to him/her $\mathrm{x}(\boldsymbol{b})\equiv
X(\boldsymbol{b})$.

  * •

first price payment: The allocated bidder $\mathrm{x}(\boldsymbol{b})$ pays
his/her own bid, while non-allocated bidders
$[n]\setminus\\{\mathrm{x}(\boldsymbol{b})\\}$ each pay nothing. Formally,
$\rho_{i}(\boldsymbol{b})=b_{i}\cdot\mathbbm{1}\big{(}i=\mathrm{x}(\boldsymbol{b})\big{)}$
for $i\in[n]$.

Without ambiguity, the allocation rule $\mathrm{x}(\boldsymbol{b})$ itself
will be called the considered First Price Auction, since it controls the
payment rule $\boldsymbol{\rho}(\boldsymbol{b})$. Denote by
$\mathbb{FPA}\ni\mathrm{x}$ the space of all First Price Auctions.

The only undetermined part of a First Price Auction is the tie-breaking rule,
which is subtle and plays an important role in our analysis. To clarify it,
let us rigorously define the interim allocation/ utility formulas (Definition
2.2) and Bayesian Nash Equilibrium (Definition 2.3).

######  Definition 2.2 (Interim allocations/utilities).

Given a First Price Auction $\mathrm{x}\in\mathbb{FPA}$, value distributions
$\boldsymbol{V}=\\{V_{i}\\}_{i\in[n]}$, and a strategy profile
$\boldsymbol{s}=\\{s_{i}\\}_{i\in[n]}$:

  * •

Each interim allocation formula $\mathrm{x}_{i}(b):=\operatorname{{\bf
Pr}}_{\mathrm{x},\,\boldsymbol{s}_{-i}(\boldsymbol{v}_{-i})}\big{[}i=\mathrm{x}\big{(}b,\,\boldsymbol{s}_{-i}(\boldsymbol{v}_{-i})\big{)}\big{]}$
for $b\geq 0$, over the randomness of the others’ bids
$\boldsymbol{s}_{-i}(\boldsymbol{v}_{-i})$ and the considered First Price
Auction $\mathrm{x}\in\mathbb{FPA}$ itself.

  * •

Each interim utility formula $u_{i}(v,\,b):=(v-b)\cdot\mathrm{x}_{i}(b)$ for
$v\in\mathrm{supp}(V_{i})$ and $b\geq 0$.

######  Definition 2.3 (Bayesian Nash Equilibria).

Following Definition 2.2, the strategy profile
$\boldsymbol{s}=\\{s_{i}\\}_{i\in[n]}$ reaches a Bayesian Nash Equilibrium for
this distribution-auction tuple, namely
$\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V},\,\mathrm{x})$, when: For each
bidder $i\in[n]$, any possible value $v\in\mathrm{supp}(V_{i})$, and any
deviation bid $b\geq 0$,

$\displaystyle\mathop{{\bf
E}\/}_{s_{i}}\big{[}\,u_{i}(v,\,s_{i}(v))\,\big{]}~{}\geq~{}u_{i}(v,\,b).$

Definition 2.3 means for any value $v\in\mathrm{supp}(V_{i})$, nearly all the
equilibrium bids $b\in\mathrm{supp}(s_{i}(v))$ EACH maximize the interim
utility formula $u_{i}(v,\,b)$, except a zero-measure set. By excluding these
zero-measure sets from the bid supports $\mathrm{supp}(s_{i}(v))$, for
$i\in[n]$, the modified strategy profile still satisfies the definition of
Bayesian Nash Equilibrium. Hereafter, without loss of generality, we assume
that EVERY equilibrium bid $b\in\mathrm{supp}(s_{i}(v))$ maximizes the formula
$u_{i}(v,\,b)$.

The following existence result can be concluded from [Leb96].

######  Theorem 2 (Bayesian Nash Equilibrium [Leb96]).

Given any value distribution $\boldsymbol{V}=\\{V_{i}\\}_{i\in[n]}$, there
exists at least one First Price Auction $\mathrm{x}\in\mathbb{FPA}$ that
admits an equilibrium
$\mathbb{BNE}(\boldsymbol{V},\,\mathrm{x})\neq\emptyset$.

###  2.1 The forward direction: Bayesian Nash Equilibria

This subsection presents a bunch of lemmas that characterize an equilibrium
$\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V},\,\mathrm{x})\neq\emptyset$. To
this end, let us introduce some helpful notations, which will be adopted
throughout this paper.

  * •

$\boldsymbol{B}=\\{B_{i}\\}_{i\in[n]}$ denotes the equilibrium bid
distributions
$\boldsymbol{s}(\boldsymbol{v})=(s_{i}(v_{i}))_{i\in[n]}\sim\boldsymbol{B}$.

  * •

$\mathcal{B}(b)=\prod_{i\in[n]}B_{i}(b)$ denotes the first-order bid
distribution $\max(\boldsymbol{s}(\boldsymbol{v}))\sim\mathcal{B}$.

  * •

$\mathcal{B}_{-i}(b)=\prod_{k\in[n]\setminus\\{i\\}}B_{k}(b)$ denotes the
competing bid distribution of each bidder $i\in[n]$.

  * •

$\gamma:=\inf(\mathrm{supp}(\mathcal{B}))$ and
$\lambda:=\sup(\mathrm{supp}(\mathcal{B}))$ denote the “infimum”/“supremum”
first-order bids, respectively. Without ambiguity, we call $v,\,b<\gamma$ the
low values/bids, $v,\,b=\gamma$ the boundary values/bids, and $v,\,b>\gamma$
the normal values/bids. As their names suggest: (i) low bids $b<\gamma$ each
gives a zero winning probability, so these bids are less important; (ii)
normal bids $b>\gamma$ are the most common ones and we will show that they
behave nicely; and (iii) boundary bids $b=\gamma$ are tricky and we will deal
with them separately.

  * •

$\mathcal{U}_{i}(v):=\max\big{\\{}u_{i}(v,\,b):b\geq 0\big{\\}}$ denotes the
optimal utility formula of each bidder $i\in[n]$. This is well defined on the
value support $v\in\mathrm{supp}(V_{i})$, because (Definition 2.3) every
equilibrium bid $s_{i}(v)$ does optimize the interim utility formula
$u_{i}(v,\,s_{i}(v))=\mathcal{U}_{i}(v)$.

Each bidder’s interim allocation $\mathrm{x}_{i}(b)$ relies on his/her
competing bid distribution $\mathcal{B}_{-i}(b)$, plus the tie-breaking rule
of the considered auction $\mathrm{x}\in\mathbb{FPA}$. When
$\mathcal{B}_{-i}(b)$ is a continuous distribution, they are identical
$\mathrm{x}_{i}(b)\equiv\mathcal{B}_{-i}(b)$, because the probability of being
ONE of the first-order bidders $\mathop{{\bf
Pr}\/}_{\boldsymbol{b}}[X(\boldsymbol{b})\ni i]$ is exactly the probability of
being the ONLY one $\mathop{{\bf
Pr}\/}_{\boldsymbol{b}}[X(\boldsymbol{b})=\\{i\\}]$. In general, we can at
least obtain (Lemma 2.4) the following properties for an interim allocation
$\mathrm{x}_{i}(b)$.

######  Lemma 2.4 (Interim allocations).

For each interim allocation formula $\mathrm{x}_{i}(b)$:

  1. 1.

$\mathrm{x}_{i}(b)$ is weakly increasing for $b\geq 0$.

  2. 2.

It is point-wise lower/upper bounded as
$\sup\big{\\{}\mathcal{B}_{-i}(t):t<b\big{\\}}\leq\mathrm{x}_{i}(b)\leq\mathcal{B}_{-i}(b)$
for $b\geq 0$.

  3. 3.

$\mathrm{x}_{i}(b)=0$ for any low bid $b<\gamma$, AND $\mathrm{x}_{i}(b)>0$
for any normal bid $b>\gamma$.

###### Proof.

Items 1 and 2 directly follows from the • ‣ 2.1 principle (Definition 2.1).
Especially for Item 2, suppose that (with a nonzero probability) bidder
$B_{i}$ ties with someone else $[n]\setminus\\{i\\}$ for this first-order bid
$s_{i}(v_{i})=\max(\boldsymbol{s}_{-i}(\boldsymbol{v}_{-i}))=b$, then the
auction always favors this bidder $B_{i}$ when
“$\mathrm{x}_{i}(b)=\mathcal{B}_{-i}(b)$”, or always disfavor him/her when
“$\mathrm{x}_{i}(b)=\sup\big{\\{}\mathcal{B}_{-i}(t):t<b\big{\\}}$”. Item 3
holds because $\gamma=\inf(\mathrm{supp}(\mathcal{B}))$ is the infimum first-
order bid $\max(\boldsymbol{s}(\boldsymbol{v}))\sim\mathcal{B}$. ∎

Lemma 2.5 shows that both of the value space $v\in\mathrm{supp}(V_{i})$ and
the bid space $b\geq 0$ of each bidder $i\in[n]$, are almost separated by the
infimum first-order bid $\gamma=\inf(\mathrm{supp}(\mathcal{B}))$.

######  Lemma 2.5 (Bidding dichotomy).

For each bidder $i\in[n]$:

  1. 1.

For a low/boundary value $v\in\mathrm{supp}_{\leq\gamma}(V_{i})$, the optimal
utility is zero $\mathcal{U}_{i}(v)=0$ and, almost surely, the equilibrium bid
is low/boundary $s_{i}(v)\leq\gamma$.

  2. 2.

For a normal value $v\in\mathrm{supp}_{>\gamma}(V_{i})$, the optimal utility
is nonzero $\mathcal{U}_{i}(v)>0$ and, almost surely, the equilibrium bid is
boundary/normal $\gamma\leq s_{i}(v)<v$.

###### Proof.

Recall Definition 2.2 for the interim utility formula
$u_{i}(v,\,b)=(v-b)\cdot\mathrm{x}_{i}(b)$.

Item 1. A low/boundary value $v\in\mathrm{supp}_{\leq\gamma}(V_{i})$ induces
EITHER a low (under)bid $b<v\leq\gamma$ and a zero interim allocation/utility
$\mathrm{x}_{i}(b)=u_{i}(v,\,b)=0$, OR a truthful/over bid $b\geq v$ and a
negative interim utility $u_{i}(v,\,b)\leq 0$. Especially, a normal bid
$b>\gamma\geq v$ induces a nonzero interim allocation $\mathrm{x}_{i}(b)>0$
and a strictly negative interim utility $u_{i}(v,\,b)<0$. Therefore, the
optimal utility is zero $\mathcal{U}_{i}(v)=0$ and the equilibrium bid must be
low/boundary $s_{i}(v)\leq\gamma$. Item 1 follows then.

Item 2. A normal value $v\in\mathrm{supp}_{>\gamma}(V_{i})$ is able to gain a
positive utility $u_{i}(v,\,b)>0$; for example, underbidding
$b^{*}=(\gamma+v)/2\in(\gamma,\,v)$ gives a nonzero allocation/utility
$\mathrm{x}_{i}(b^{*}),\,u_{i}(v,\,b^{*})>0$. So, the equilibrium bid
$s_{i}(v)$ neither can be truthful/over $b\geq v$ (hence a negative utility
$u_{i}(v,\,b)\leq 0$), nor can be low $b<\gamma$ (hence a zero
allocation/utility $\mathrm{x}_{i}(b)=u_{i}(v,\,b)=0$). That is, the optimal
utility is nonzero $\mathcal{U}_{i}(v)>0$ and the equilibrium (under)bid must
be boundary/normal $\gamma\leq s_{i}(v)<v$. Item 2 follows then. ∎

Lemma 2.6 shows, in the normal value regime $v\in\mathrm{supp}(V_{i})$, the
optimal utility formula $\mathcal{U}_{i}(v)$ and the equilibrium strategy
$s_{i}(v)$ are monotonic (cf. [CH13, Lemma 3.9] for a similar result).

######  Lemma 2.6 (Bidding monotonicity).

For any two normal values $v,\,w\in\mathrm{supp}_{>\gamma}(V_{i})$ that $v>w$
of a bidder $i\in[n]$:

  1. 1.

The two optimal utilities are strictly monotonic
$\mathcal{U}_{i}(v)>\mathcal{U}_{i}(w)>0$.

  2. 2.

The two random bids are weakly monotonic $s_{i}(v)\geq s_{i}(w)\geq\gamma$,
almost surely.

###### Proof.

Lemma 2.5 already shows that the utilities are nonzero
$\mathcal{U}_{i}(v),\,\mathcal{U}_{i}(w)>0$ and the equilibrium bids are
boundary/normal $s_{i}(v),\,s_{i}(w)\geq\gamma$. It remains to verify the
utility/bidding monotonicity.

Item 1. The utility monotonicity $\mathcal{U}_{i}(v)>\mathcal{U}_{i}(w)$. We
deduce that

$\displaystyle\mathcal{U}_{i}(v)~{}\geq~{}u_{i}(v,\,s_{i}(w))~{}=~{}\frac{v-s_{i}(w)}{w-s_{i}(w)}\cdot
u_{i}(w,\,s_{i}(w))~{}=~{}\frac{v-s_{i}(w)}{w-s_{i}(w)}\cdot\mathcal{U}_{i}(w)~{}>~{}\mathcal{U}_{i}(w),$

The first step: Under the value $v$, the optimal utility $\mathcal{U}_{i}(v)$
is at least the interim utility $u_{i}(v,\,s_{i}(w))$ resulted from bidding
$s_{i}(w)$, namely the equilibrium bid at the (lower) value $w$.
The second step: Apply the interim utility formula to $u_{i}(v,\,s_{i}(w))$
and $u_{i}(w,\,s_{i}(w))$.
The third step: The random bid $s_{i}(w)$ optimizes the interim utility
formula $u_{i}(w,\,s_{i}(w))=\mathcal{U}_{i}(w)$ at the value $w$.
The fourth step: (Lemma 2.5) $v>w>s_{i}(w)$ and $\mathcal{U}_{i}(w)>0$. Item 1
follows then.

Item 2. The bidding monotonicity $s_{i}(v)\geq s_{i}(w)$. This result also
appears in [CH13, Lemma 3.9]; we would recap their proof for completeness.
Assume to the opposite that $s_{i}(v)<s_{i}(w)$. Following the interim utility
formula (Definition 2.2),

$\displaystyle u_{i}(v,\,s_{i}(v))$
$\displaystyle~{}=~{}u_{i}(w,\,s_{i}(v))~{}+~{}(v-w)\cdot\mathrm{x}_{i}(s_{i}(v)),\phantom{\big{.}}$
$\displaystyle u_{i}(v,\,s_{i}(w))$
$\displaystyle~{}=~{}u_{i}(w,\,s_{i}(w))~{}+~{}(v-w)\cdot\mathrm{x}_{i}(s_{i}(w)).\phantom{\big{.}}$

We have (i) $u_{i}(v,\,s_{i}(v))\geq u_{i}(v,\,s_{i}(w))$, since the
equilibrium bid $s_{i}(v)$ optimizes the interim utility formula
$u_{i}(v,\,b)$ for this value $v$. Similarly, we have (ii)
$u_{i}(w,\,s_{i}(w))\geq u_{i}(w,\,s_{i}(v))$. Also, under the assumption
$s_{i}(v)<s_{i}(w)$, we know from Item 1 of Lemma 2.4 that (iii)
$\mathrm{x}_{i}(s_{i}(v))\leq\mathrm{x}_{i}(s_{i}(w))$. Given the above two
equations (note that $v>w$), each of 2.1, 2.1, and 2.1 must achieve the
equality. However, this means888Particularly, the equality of 2.1 gives
$(v-s_{i}(v))\cdot\mathrm{x}(s_{i}(v))=(v-s_{i}(w))\cdot\mathrm{x}(s_{i}(w))$;
notice that $s_{i}(v)<s_{i}(w)$. And the equality of 2.1 gives
$\mathrm{x}(s_{i}(v))=\mathrm{x}(s_{i}(w))$. For these reasons, we must have
$\mathrm{x}(s_{i}(v))=\mathrm{x}(s_{i}(w))=0$. all interim
allocations/utilities are zero
$\mathrm{x}_{i}(s_{i}(v))=\mathrm{x}_{i}(s_{i}(w))=u_{i}(v,\,s_{i}(v))=u_{i}(w,\,s_{i}(w))=0$,
which contradicts Item 1. Rejecting our assumption gives Item 2. ∎

######  Remark 3 (Quantiles).

Due to Lemma 2.6, the normal value space $v_{i}>\gamma$ and normal/boundary
bid space $s_{i}(v_{i})\geq\gamma$ each identify the other in terms of
quantiles. From this perspective, the stochastic process of the auction game
runs as follows: Draw a uniform random quantile $q_{i}\sim U[0,1]$, and then
realize the value/bid $V_{i}^{-1}(q_{i})$ and $B_{i}^{-1}(q_{i})$ accordingly.
The two stochastic processes are equivalent conditioned on the realized value
being normal $V_{i}^{-1}(q_{i})>\gamma$.

Lemma 2.7 shows that, on the whole interval
$b\in[\gamma=\inf(\mathrm{supp}(\mathcal{B})),\,\lambda=\sup(\mathrm{supp}(\mathcal{B}))]$,
all of the equilibrium/competing/first-order bid distributions $B_{i}(b)$,
$\mathcal{B}_{-i}(b)$, and $\mathcal{B}(b)$ are well structured. The earlier
works [MR00a, MR00b, MR03] derive similar results (under additional
assumptions).

######  Lemma 2.7 (Bid distributions).

Each of the following holds:

  1. 1.

The competing/first-order bid distributions $\mathcal{B}_{-i}(b)$ for
$i\in[n]$ and $\mathcal{B}(b)$ each have probability densities almost
everywhere on $b\in(\gamma,\,\lambda]$, therefore being strictly increasing
CDF’s on the CLOSED interval $b\in[\gamma,\,\lambda]$.

  2. 2.

The equilibrium/competing/first-order bid distributions $B_{i}(b)$ for
$i\in[n]$, $\mathcal{B}_{-i}(b)$ for $i\in[n]$ and $\mathcal{B}(b)$, each have
no probability mass on $b\in(\gamma,\,\lambda]$, excluding the boundary
$\gamma=\inf(\mathrm{supp}(\mathcal{B}))$, therefore being continuous CDF’s on
the CLOSED interval $b\in[\gamma,\,\lambda]$.

###### Proof.

We safely assume $n\geq 2$. (Otherwise, Lemma 2.7 is vacuously true since the
unique bidder always bids zero $[\gamma,\,\lambda]=\\{0\\}$ in any First Price
Auction.) The proof relies on Fact A.

######  Fact A.

Any two equilibrium bid distributions $B_{i}$ and $B_{k}$ for $i\neq k\in[n]$
cannot both have probability masses at a normal bid $b>\gamma$.

###### Proof.

Assume the opposite. Then both bidders $B_{i}$ and $B_{k}$ (and possibly
someone else) tie for this first-order bid
$s_{i}(v_{i})=s_{k}(v_{k})=\max(\boldsymbol{s}(\boldsymbol{v}))=b>\gamma$ with
a nonzero probability $>0$. Conditioned on this, with a nonzero probability
$>0$, at least one bidder between $B_{i}$ and $B_{k}$ cannot be allocated.
Hence, either $B_{i}$ or $B_{k}$ or both can gain a nonzero extra allocation
by raising his/her (equilibrium) bid $s_{i}(v_{i})=s_{k}(v_{k})=b$. More
formally, for some nonzero probabilities $\delta_{i},\,\delta_{k}>0$, we have
EITHER $\mathrm{x}_{i}(b^{*})\geq\mathrm{x}_{i}(b)+\delta_{i}$ for any
$b^{*}>b$, OR $\mathrm{x}_{k}(b^{*})\geq\mathrm{x}_{k}(b)+\delta_{k}$ for any
$b^{*}>b$, OR both.

Without loss of generality, let us consider the case that
$\mathrm{x}_{i}(b^{*})\geq\mathrm{x}_{i}(b)+\delta_{i}$ for any $b^{*}>b$.
However, this means some deviation bid, such as
$b^{*}=b+\frac{\delta_{i}/2}{\mathrm{x}_{i}(b)+\delta_{i}}\cdot(v_{i}-b)$, can
benefit. Namely, because this bidder $B_{i}$ has a normal equilibrium bid
$s_{i}(v_{i})=b>\gamma$, (Item 2 of Lemma 2.5) he/she must have a higher value
$v_{i}>s_{i}(v_{i})=b$. This implies that (by construction) $b<b^{*}<v_{i}$
and thus, that the deviated utility
$u_{i}(v_{i},\,b^{*})=(v_{i}-b^{*})\cdot\mathrm{x}_{i}(b^{*})$ is lower
bounded as

$\displaystyle u_{i}(v_{i},\,b^{*})$
$\displaystyle~{}\geq~{}(v_{i}-b^{*})\cdot\big{(}\mathrm{x}_{i}(b)+\delta_{i}\big{)}$
the “WLOG”
$\displaystyle~{}=~{}(v_{i}-b)\cdot\big{(}\mathrm{x}_{i}(b)+\delta_{i}/2\big{)}$
construction of $b^{*}$ $\displaystyle~{}>~{}(v_{i}-b)\cdot\mathrm{x}_{i}(b)$
$v_{i}>b$ and $\delta_{i}>0$
$\displaystyle~{}=~{}u_{i}(v_{i},\,b)~{}=~{}u_{i}(v_{i},\,s_{i}(v_{i})).$
$s_{i}(v_{i})=b$

To conclude, the deviation bid $b^{*}$ strictly surpasses the equilibrium bid
$s_{i}(v_{i})$, which contradicts (Definition 2.3) the optimality of
$s_{i}(v_{i})$. Rejecting our assumption gives Fact A.

Neighborhood Deviation Arguments. The concrete construction of the above
deviation bid $b^{*}$ is less important. Instead, the point is that we are
able to find two bids $b^{*}>b=s_{i}(v_{i})$ that can be arbitrarily close
$(b^{*}-b)\searrow 0$ BUT admit a nonzero interim allocation gap
$\mathrm{x}_{i}(b^{*})-\mathrm{x}_{i}(b)\geq\delta_{i}>0$. Suppose so, bidder
$i$ strictly benefits $u_{i}(v,\,b^{*})>u_{i}(v,\,b)$ from the deviation bid
$b^{*}$ when it is close enough to the equilibrium bid $b^{*}\searrow b$,
hence a contradiction to the optimality of $b=s_{i}(v_{i})$.

Also, suppose there are two bids $b^{*}<b=s_{i}(v_{i})$ that yield two
arbitrarily close nonzero interim allocations
$(\mathrm{x}_{i}(b^{*})-\mathrm{x}_{i}(b))\nearrow 0$ BUT themselves are
bounded away $b-b^{*}\geq\delta_{i}>0$, then bidder $i$ again benefits from
the deviation bid $b^{*}$, hence a contradiction to the optimality of
$b=s_{i}(v_{i})$.

We will apply such arguments in many places, WITHOUT specifying the deviation
bids $b^{*}$ as the explicit constructions are less informative. For clarity,
such arguments will be called the 2.1. ∎

Below let us prove Item 1 and Item 2. We reason about the first-order bid
distribution $\mathcal{B}(b)$ and the competing bid distributions
$\mathcal{B}_{-i}(b)$ separately.

Item 1: $\mathcal{B}(b)$. Assume the opposite to the $\mathcal{B}(b)$’s strong
monotonicity: The first-order bid distribution $\mathcal{B}(b)$ has no
probability density on an OPEN interval
$(\alpha,\,\beta)\subseteq[\gamma,\,\lambda]$.

Indeed, because $\gamma=\inf(\mathrm{supp}(\mathcal{B}))$ and
$\lambda=\sup(\mathrm{supp}(\mathcal{B}))$, we can find a maximal interval
$(\alpha,\,\beta)$ such that, the $\mathcal{B}(b)$ has probability densities
within both of the left/right neighborhoods $(\alpha-\delta,\,\alpha]$ and
$[\beta,\,\beta+\delta)$, for whatever $\delta>0$. This gives
$\mathcal{B}(\beta)\geq\mathcal{B}(\alpha)>0$. Let us do case analysis:

  * •

Case 1: $\mathcal{B}(\beta)>\mathcal{B}(\alpha)>0$. Then the $\mathcal{B}(b)$
must have ONE probability mass at the $\beta$.

(Fact A) Exactly one equilibrium bid distribution, $B_{k}(b)$ for a specific
$k\in[n]$, has a probability mass at the $\beta$; his/her competing bid
distribution $\mathcal{B}_{-k}(b)$ has no probability mass there, thus being
continuous at the $\beta$. This competing bid distribution
$\mathcal{B}_{-k}(b)$ has no probability density on the open interval
$(\alpha,\,\beta)\bigcap\mathrm{supp}(\mathcal{B}_{-k})=\emptyset$, à la the
first-order bid distribution $\mathcal{B}(b)$.

Hence, (Item 1 of Lemma 2.4) bidder $B_{k}(b)$ has a constant interim
allocation $\mathrm{x}_{k}(b)=\mathrm{x}_{k}(\beta)=\mathcal{B}_{-k}(\beta)>0$
on the left-open right-closed interval $b\in(\alpha,\,\beta]$. But this means,
conditioned on this bidder’s equilibrium bid being at the probability mass
$\big{\\{}s_{k}(v_{k})=\beta\big{\\}}$, any lower deviation bid
$b^{*}\in(\alpha,\,\beta)$ yields a better deviated utility
$u_{k}(v_{k},\,b^{*})>u_{k}(v_{k},\,s_{k}(v_{k}))$. This contradicts
(Definition 2.3) the optimality of this equilibrium bid $s_{k}(v_{k})=\beta$.

  * •

Case 2: $\mathcal{B}(\beta)=\mathcal{B}(\alpha)>0$. Then the $\mathcal{B}(b)$
must have NO probability mass at the $\beta$.

À la the $\mathcal{B}(b)$, at least one bidder $B_{k}(b)$ for some $k\in[n]$,
has probability densities within the right neighborhood
$[\beta,\,\beta+\delta)$, for whatever $\delta>0$. No matter how close
$b\searrow\beta$, we can find an equilibrium bid $b=s_{k}(v)$, for some
$v\in\mathrm{supp}(V_{k})$, that gives a positive utility $u_{k}(v,\,b)>0$.

À la Case 1, this bidder has a constant interim allocation
$\mathrm{x}_{k}(b^{*})=\mathrm{x}_{k}(\beta)=\mathcal{B}_{-k}(\beta)>0$ on the
left-open right-closed interval $b^{*}\in(\alpha,\,\beta]$; let us consider a
particular bid $b^{*}=\frac{1}{2}(\alpha+\beta)$. This deviation bid $b^{*}$
is bounded away from the above equilibrium bid
$b-b^{*}\geq\frac{1}{2}(\beta-\alpha)>0$ BUT, because there is no probability
mass at $\beta$, gives an arbitrarily close interim allocation
$\big{(}\mathrm{x}_{k}(b)-\mathrm{x}_{k}(b^{*})\big{)}\searrow 0$. Therefore,
we can apply the 2.1 to get a contradiction.

To conclude, we get a contradiction in the either case. Reject our assumption:
The first-order bid distribution $\mathcal{B}(b)$ is strictly increasing on
$b\in[\gamma,\,\lambda]$.

Item 1: $\mathcal{B}_{-i}(b)$. Assume the opposite to the
$\mathcal{B}_{-i}(b)$’s strong monotonicity: At least one competing bid
distribution $\mathcal{B}_{-i}(b)$ has no probability density on an OPEN
interval $(\alpha,\,\beta)\subseteq[\gamma,\,\lambda]$.

In contrast, the remaining bidder $B_{i}(b)$ has probability densities almost
everywhere on $(\alpha,\,\beta)$, since the first-order bid distribution
$\mathcal{B}(b)=B_{i}(b)\cdot\mathcal{B}_{-i}(b)$ is strongly increasing (as
shown above). Consider such an equilibrium bid
$s_{i}(v_{i})\in(\alpha,\,\beta)$. However, any lower deviation bid
$b^{*}\in\big{(}\alpha,\,s_{i}(v_{i})\big{)}$ results in the same nonzero
allocation $\mathrm{x}_{i}(b^{*})=\mathrm{x}_{i}(s_{i}(v_{i}))>0$ and thus a
better deviated utility
$u_{i}(v_{i},\,b^{*})=(v_{i}-b^{*})\cdot\mathrm{x}_{i}(b^{*})>\big{(}v_{i}-s_{i}(v_{i})\big{)}\cdot\mathrm{x}_{i}(b^{*})=u_{i}(v_{i},\,s_{i}(v_{i}))$.
This contradicts (Definition 2.3) the optimality of the equilibrium bid
$s_{i}(v_{i})\in(\alpha,\,\beta)$. Reject our assumption: Each competing bid
distribution $\mathcal{B}_{-i}(b)$ is strictly increasing on
$b\in[\gamma,\,\lambda]$. Item 1 follows then.

Item 2. We only need to verify continuity of the first-order bid distribution
$\mathcal{B}(b)=B_{i}(b)\cdot\mathcal{B}_{-i}(b)$, which implies continuity of
the equilibrium/competing bid distributions $\mathcal{B}_{i}(b)$ and
$\mathcal{B}_{-i}(b)$.

Assume the opposite: $\mathcal{B}(b)$ has a probability mass at some normal
bid $\beta\in(\gamma,\,\lambda]$. According to Fact A, exactly one bidder
$B_{i}(b)$, for a specific $i\in[n]$, has a probability mass at this $\beta$.
Further, following Item 1, his/her competing bid distribution
$\mathcal{B}_{-i}(b)$ has probability densities within the OPEN left
neighborhood $b\in(\beta-\delta,\,\beta)$, for whatever $\delta>0$; therefore
at least one OTHER bidder $k\in[n]\setminus\\{i\\}$ has probability densities
there.

This other bidder $B_{k}(b)$’s interim allocation formula $\mathrm{x}_{k}(b)$
is discontinuous at the $\beta\in(\gamma,\,\lambda]$, because of $B_{i}(b)$’s
probability mass at the $\beta$. Formally (Lemma 2.4), there exists a nonzero
interim allocation gap
$\xi^{*}:=\inf\big{\\{}\,\mathrm{x}_{k}(b^{*})-\mathrm{x}_{k}(b):b^{*}>\beta>b\,\big{\\}}>0$
around the $\beta\in(\gamma,\,\lambda]$. Hence, for some bids
$b\in(\beta-\delta,\,\beta)$ and $b^{*}>\beta$ that are arbitrary close
$(b^{*}-b)\searrow 0$, we can use the 2.1 to get a contradiction. Reject our
assumption gives Item 2.

This finishes the proof of Lemma 2.7. ∎

An important and direct implication of the continuity is that
$\mathrm{x}_{i}(b)=\mathcal{B}_{-i}(b)$ for any $b\in(\gamma,\lambda]$. This
is formalized as Corollary 2.8 and will be used in many places in the paper.

######  Corollary 2.8 (Interim allocations).

The interim allocation formula $\mathrm{x}_{i}(b)$ of each bidder $i\in[n]$ is
identical to his/her competing bid distribution
$\mathrm{x}_{i}(b)=\mathcal{B}_{-i}(b)$, for any normal bid
$b\in(\gamma,\lambda]$.

According to the Lebesgue differentiation theorem [Leb04], a monotonic
function $f:(\gamma,\,\lambda)\mapsto\mathbb{R}$ is differentiable almost
everywhere, except a set $\mathbb{D}_{f}\subseteq(0,\,\lambda)$ of a zero
measure.999Rigorously, the set $\mathbb{D}_{f}$ has a zero Lebesgue measure.
Yet since the bid distributions $B_{i}(b)$, $\mathcal{B}_{-i}(b)$, and
$\mathcal{B}(b)$ are continuous on $b\in(\gamma,\,\lambda)$, we need not to
distinguish the Lebesgue/probabilistic measures. We thus conclude Corollary
2.9 directly from Lemma 2.7.

######  Corollary 2.9 (Bid distributions).

Each of the equilibrium/competing/first-order bid distributions,
$\\{B_{i}\\}_{i\in[n]}$, $\\{\mathcal{B}_{-i}\\}_{i\in[n]}$, and $\mathcal{B}$
is differentiable almost everywhere on the OPEN interval
$b\in(\gamma,\,\lambda)$, except a set $\mathbb{D}\subseteq(\gamma,\,\lambda)$
on which this bid distribution, $B_{i}(b)$, $\mathcal{B}_{-i}(b)$, or
$\mathcal{B}(b)$, has a zero measure.

######  Remark 4 (Bid distributions).

The continuity/monotonicity/differentiability shown in Lemmas 2.7 and 2.9 are
the basics of our later discussions; all subsequent bid distributions will
satisfy them. So for brevity, we often omit a formal clarification. Also, we
often simply write the derivatives $B^{\prime}_{i}(b)$ etc by omitting
(Corollary 2.9) the zero-measure indifferentiable points
$\mathbb{D}\subseteq(\gamma,\,\lambda)$; we can use standard tools from real
analysis to deal with those points $\mathbb{D}\subseteq(\gamma,\,\lambda)$
separately.

###  2.2 The inverse direction: Bid-to-value mappings

In this subsection, we study the inverse mappings of strategies
$\boldsymbol{s}^{-1}=\\{s_{i}^{-1}\\}_{i\in[n]}$ and try to reconstruct the
value distributions $\boldsymbol{V}=\\{V_{i}\\}_{i\in[n]}$ from (equilibrium)
bid distributions.

######  Definition 2.10 (Inverses of strategies).

Consider bid distributions $\boldsymbol{B}=\\{B_{i}\\}_{i\in[n]}$ given by
value distributions $\boldsymbol{v}=(v_{i})_{i\in[n]}\sim\boldsymbol{V}$ and a
strategy profile $\boldsymbol{s}=\\{s_{i}\\}_{i\in[n]}$. Each random inverse
$s_{i}^{-1}(b)$ for $b\in\mathrm{supp}(B_{i})$ is defined as the conditional
distribution $\\{v_{i}\sim V_{i}\,\,\big{|}\,\big{.}\,s_{i}(v_{i})=b\\}$. So,
each random inverse $s_{i}^{-1}(b_{i})$ for $b_{i}\sim B_{i}$ is identically
distributed as the random value $v_{i}\sim V_{i}$.

Lemma 2.11 shows two basic properties of the random inverses
$\boldsymbol{s}^{-1}=\\{s_{i}^{-1}\\}_{i\in[n]}$.

######  Lemma 2.11 (Inverses of strategies).

For each inverse $s_{i}^{-1}$, the following hold (almost surely):

  1. 1.

dichotomy: $s_{i}^{-1}(b)\leq\gamma$ for any low bid
$b\in\mathrm{supp}_{<\gamma}(B_{i})$.
dichotomy: $s_{i}^{-1}(b)>b>\gamma$ for any normal bid
$b\in\mathrm{supp}_{>\gamma}(B_{i})$.

  2. 2.

monotonicity: $s_{i}^{-1}(b)\geq s_{i}^{-1}(t)$ for two boundary/normal bids
$b,\,t\in\mathrm{supp}_{\geq\gamma}(B_{i})$ that $b>t$.

###### Proof.

Under our definition of the $s_{i}^{-1}(b)$, Item 1 follows directly from
Lemma 2.5, while Item 2 follows from a combination of Lemma 2.5 and Lemma 2.6
(Item 2). ∎

Below, we characterize (Lemma 2.13) the inverses of equilibrium strategies
$s_{i}^{-1}(b)$ for normal bids $b\in(\gamma,\,\lambda]$, using (Definition
2.12) the concept of bid-to-value mappings $\varphi_{i}(b)$. We prove that the
inverse $s_{i}^{-1}(b)$ at a normal bid $b\in(\gamma,\,\lambda]$ is
essentially a deterministic value. (The inverses at the boundary bid
$s_{i}^{-1}(\gamma)$ are tricky and will be studied later.)

######  Definition 2.12 (Bid-to-value mappings).

Given equilibrium bid distributions $\boldsymbol{B}=\\{B_{i}\\}_{i\in[n]}$
(cf. Lemmas 2.7 and 2.9), define each bid-to-value mapping $\varphi_{i}(b)$
for $b\in(\gamma,\,\lambda)$ as follows:

$\varphi_{i}(b)~{}:=~{}b+\frac{\mathcal{B}_{-i}(b)}{\mathcal{B}^{\prime}_{-i}(b)}~{}=~{}b+\Big{(}\sum_{k\in[n]\setminus\\{i\\}}\frac{B^{\prime}_{k}(b)}{B_{k}(b)}\Big{)}^{-1}~{}=~{}b+\Big{(}\frac{\mathcal{B}^{\prime}(b)}{\mathcal{B}(b)}-\frac{B^{\prime}_{i}(b)}{B_{i}(b)}\Big{)}^{-1}$

It turns out that (Item 2 of Lemma 2.13) each $\varphi_{i}(b)$ is an
increasing function, so the domain can be extended to include the both
endpoints $\varphi_{i}(\gamma):=\lim_{b\searrow\gamma}\varphi_{i}(b)$ and
$\varphi_{i}(\lambda):=\lim_{b\nearrow\lambda}\varphi_{i}(b)$.

The above bid-to-value mapping is known in the literature ([HHT14] etc).
However, it is usually defined only on the support of $B_{i}$. We define it
and study its properties on the entire interval $[\gamma,\,\lambda]$, which is
very important to our argument.

######  Lemma 2.13 (Normal bids).

For each bid-to-value mapping $\varphi_{i}(b)$, the following hold:

  1. 1.

invertibility: $s_{i}^{-1}(b)=\varphi_{i}(b)$ almost surely, for any normal
bid $b\in\mathrm{supp}_{>\gamma}(B_{i})$.101010More rigorously, (Corollaries
2.9 and 4) we shall exclude a zero-measure set
$\mathbb{D}\subseteq(\gamma,\,\lambda]$, namely the indifferentiable points of
the $B_{i}(b)$’s

  2. 2.

monotonicity: $\varphi_{i}(b)$ is weakly increasing on the closed interval
$b\in[\gamma,\,\lambda]$.

  3. 3.

rationality: $\varphi_{i}(b)>b$ on the left-open right-closed interval
$b\in(\gamma,\,\lambda]$. Further, $\varphi_{i}(\gamma)\geq\gamma$.

###### Proof.

We safely assume $n\geq 2$. (Otherwise, Lemma 2.13 is vacuously true since the
unique bidder always bids zero $[\gamma,\,\lambda]=\\{0\\}$ in any First Price
Auction.)

Item 1. Consider a specific inverse/value $s_{i}^{-1}(b)=v$ resulted from a
normal bid $b\in\mathrm{supp}_{>\gamma}(B_{i})$. Regarding a normal bid
$b^{*}>\gamma$, we can rewrite (Lemma 2.4 (Item 2) and Corollary 2.8) the
interim utility formula
$u_{i}(v,\,b^{*})=(v-b^{*})\cdot\mathrm{x}_{-i}(b^{*})=(v-b^{*})\cdot\mathcal{B}_{-i}(b^{*})$
and deduce the partial derivative

$\tfrac{\partial u_{i}}{\partial
b^{*}}~{}=~{}-\mathcal{B}_{-i}(b^{*})+(v-b^{*})\cdot\mathcal{B}^{\prime}_{-i}(b^{*})~{}=~{}\big{(}v-\varphi_{i}(b^{*})\big{)}\cdot\mathcal{B}^{\prime}_{-i}(b^{*}).$

Hence, to make (Definition 2.3) the equilibrium bid
$b\in\mathrm{supp}_{>\gamma}(B_{i})$ optimize the formula $u_{i}(v,\,b^{*})$,
we must have $\varphi_{i}(b)=v=s_{i}^{-1}(b)$. Here we use the fact that
$B^{\prime}_{-i}(b^{*})>0$ since $B_{-i}$ is strictly increasing (Lemma 2.7).
Thus, Item 1 follows then.

Item 2. For brevity, we consider a twice differentiable111111In general,
following the Lebesgue differentiation theorem [Leb04], the $\mathcal{B}(b)$
is twice differentiable almost everywhere on $(\gamma,\,\lambda)$, except a
zero-measure set $\mathbb{D}_{\mathcal{B}}\subseteq(\gamma,\,\lambda)$ that
can be handled by standard tools from real analysis. first-order bid CDF
$\mathcal{B}(b)=B_{i}(b)\cdot\mathcal{B}_{-i}(b)$. Thus for $i\in[n]$, each
competing bid CDF $\mathcal{B}_{-i}(b)$ is also twice differentiable and each
bid-to-value mapping
$\varphi_{i}(b)=b+\mathcal{B}_{-i}(b)\big{/}\mathcal{B}^{\prime}_{-i}(b)$ is
continuous on $b\in(\gamma,\,\lambda)$.

Following a combination of Item 1 and Lemma 2.11 (Item 2), each mapping
$\varphi_{i}(b)$ is increasing on this equilibrium bid distribution $B_{i}$’s
normal bid support $\mathrm{supp}_{>\gamma}(B_{i})$, so the task is to extend
this monotonicity to the whole interval $b\in(\gamma,\,\lambda)$. The proof
relies on Facts A and B.

######  Fact A.

A mapping $\varphi(b)=b+B(b)\big{/}B^{\prime}(b)$ is increasing iff the
reciprocal function $1\big{/}B(b)$ is convex.

###### Proof.

Once again, we assume that the underlying CDF $B(b)$ is twice differentiable.
The reciprocal function $1\big{/}B(b)$ has the second derivative
$\frac{\mathrm{d}^{2}}{\mathrm{d}b^{2}}\big{(}\frac{1}{B}\big{)}=\frac{\mathrm{d}}{\mathrm{d}b}\big{(}-\frac{B^{\prime}}{B^{2}}\big{)}=-\frac{B^{\prime\prime}\cdot
B-2\cdot(B^{\prime})^{2}}{B^{2}}$. So we can rewrite the first derivative of
the mapping $\varphi^{\prime}(b)=1+\frac{(B^{\prime})^{2}-B\cdot
B^{\prime\prime}}{(B^{\prime})^{2}}=\frac{B^{2}}{(B^{\prime})^{2}}\cdot\frac{\mathrm{d}^{2}}{\mathrm{d}b^{2}}\big{(}\frac{1}{B}\big{)}$.
Precisely, the mapping is increasing $\varphi^{\prime}(b)\geq 0$ iff the
reciprocal function is convex
$\frac{\mathrm{d}^{2}}{\mathrm{d}b^{2}}(\frac{1}{B})\geq 0$. Fact A follows
then. ∎

######  Fact B.

The first-order mapping
$\varphi_{\mathcal{B}}(b):=b+\mathcal{B}(b)\big{/}\mathcal{B}^{\prime}(b)$ is
increasing on $b\in(\gamma,\,\lambda)$.

###### Proof.

Based on Fact A, it suffices to show that the first-order reciprocal function
$\mathcal{R}(b):=1\big{/}\mathcal{B}(b)$ is convex. For brevity, we denote the
equilibrium/competing reciprocal functions $R_{i}(b):=1\big{/}B_{i}(b)$ and
$\mathcal{R}_{-i}(b):=1\big{/}\mathcal{B}_{-i}(b)$ for $i\in[n]$. Also, we may
simply write $R_{i}=R_{i}(b)$ etc.

We first establish Fact B under the assumption that all bid distributions
$\boldsymbol{B}=\\{B_{i}\\}_{i\in[n]}$ are supported at this bid, namely
$b\in\mathrm{supp}_{>\gamma}(B_{i})$ for $i\in[n]$. By elementary algebra,
each competing reciprocal function
$\mathcal{R}_{-i}(b)=\prod_{k\in[n]\setminus\\{i\\}}R_{k}(b)$ has the second
derivative

$\displaystyle\mathcal{R}^{\prime\prime}_{-i}$
$\displaystyle~{}=~{}\sum_{k_{1}\neq k_{2}\neq
i}\Big{(}R^{\prime}_{k_{1}}R^{\prime}_{k_{2}}\prod_{k_{3}\notin\\{i,\,k_{1},\,k_{2}\\}}R_{k_{3}}\Big{)}+\sum_{k\neq
i}\Big{(}R^{\prime\prime}_{k}\prod_{k_{3}\notin\\{i,\,k\\}}R_{k_{3}}\Big{)}$
$\displaystyle~{}=~{}\mathcal{R}_{-i}\cdot\Big{(}\sum_{k_{1}\neq k_{2}\neq
i}\tfrac{R^{\prime}_{k_{1}}R^{\prime}_{k_{2}}}{R_{k_{1}}R_{k_{2}}}+\sum_{k\neq
i}\tfrac{R^{\prime\prime}_{k}}{R_{k}}\Big{)}.\qquad\mbox{factor out
$\mathcal{R}_{-i}=\prod_{k\neq i}R_{k}$}$

We thus deduce that

$\displaystyle\tfrac{1}{n-1}\sum_{i\in[n]}R_{i}\cdot\mathcal{R}^{\prime\prime}_{-i}$
$\displaystyle~{}=~{}\tfrac{\mathcal{R}}{n-1}\sum_{i\in[n]}\Big{(}\sum_{k_{1}\neq
k_{2}\neq
i}\tfrac{R^{\prime}_{k_{1}}R^{\prime}_{k_{2}}}{R_{k_{1}}R_{k_{2}}}+\sum_{k\neq
i}\tfrac{R^{\prime\prime}_{k}}{R_{k}}\Big{)}$
$R_{i}\cdot\mathcal{R}_{-i}=\mathcal{R}$
$\displaystyle~{}=~{}\tfrac{n-2}{n-1}\cdot\mathcal{R}\cdot\Big{(}\sum_{k_{1}\neq
k_{2}}\tfrac{R^{\prime}_{k_{1}}R^{\prime}_{k_{2}}}{R_{k_{1}}R_{k_{2}}}\Big{)}~{}+~{}\mathcal{R}\cdot\Big{(}\sum_{k\in[n]}\tfrac{R^{\prime\prime}_{k}}{R_{k}}\Big{)}.$
combine the like terms

Moreover, the first-order reciprocal function
$\mathcal{R}(b)=\prod_{k\in[n]}R_{k}(b)$ has the second derivative

$\displaystyle\mathcal{R}^{\prime\prime}$
$\displaystyle~{}=~{}\mathcal{R}\cdot\Big{(}\sum_{k_{1}\neq
k_{2}}\tfrac{R^{\prime}_{k_{1}}R^{\prime}_{k_{2}}}{R_{k_{1}}R_{k_{2}}}+\sum_{k\in[n]}\tfrac{R^{\prime\prime}_{k}}{R_{k}}\Big{)}$
à la the $\mathcal{R}^{\prime\prime}_{-i}$ formulas
$\displaystyle~{}=~{}\tfrac{\mathcal{R}}{n-1}\sum_{k_{1}\neq
k_{2}}\tfrac{R^{\prime}_{k_{1}}R^{\prime}_{k_{2}}}{R_{k_{1}}R_{k_{2}}}+\tfrac{1}{n-1}\sum_{k\in[n]}R_{k}\cdot\mathcal{R}^{\prime\prime}_{-k}~{}\geq~{}0.$
substitute $\sum_{i\in[n]}\mathcal{R}^{\prime\prime}_{-i}\cdot R_{i}$

The first summation: $R^{\prime}_{k_{1}},\,R^{\prime}_{k_{2}}\leq 0$ for
$k_{1}\neq k_{2}\in[n]$, so the product
$R^{\prime}_{k_{1}}R^{\prime}_{k_{2}}\geq 0$.
The second summation: $\mathcal{R}^{\prime\prime}_{-k}\geq 0$ for $k\in[n]$.
At the considered bid $b\in\mathrm{supp}_{>\gamma}(B_{i})$, each mapping is
increasing $\varphi^{\prime}_{i}(b)\geq 0$ (Item 1) and thus each reciprocal
is convex $\mathcal{R}^{\prime\prime}_{-i}(b)\geq 0$ (Fact A).

Hence, under the assumption that each bid CDF
$\boldsymbol{B}=\\{B_{i}\\}_{i\in[n]}$ is strictly increasing at this bid
$b\in\mathrm{supp}_{>\gamma}(B_{i})$, the first-order reciprocal
$\mathcal{R}(b)$ is convex here.

Removing the Assumption. If some bidders $i\in[n]$ are not supported here
$b\notin\mathrm{supp}_{>\gamma}(B_{i})$, we can modify the proof by treating
those $B_{i}(b)$’s constant and reasoning about the other bidders
$\big{\\{}i\in[n]:b\in\mathrm{supp}_{>\gamma}(B_{i})\big{\\}}$. The above
proof relies on that at least TWO bidders $k_{1}\neq k_{2}\in[n]$ are
supported at this bid
$\mathrm{supp}_{>\gamma}(B_{k_{1}}),\,\mathrm{supp}_{>\gamma}(B_{k_{1}})\ni
b$. This is true regardless of the assumption, because (Lemma 2.7) EACH
competing bid CDF $\mathcal{B}_{-i}$ for $i\in[n]$ is strictly increasing on
the whole interval $b\in[\gamma,\,\lambda]$. To conclude, the first-order
reciprocal $\mathcal{R}(b)$ is convex. Fact B follows then. ∎

Item 2 follows directly: On the normal bid support
$b\in\mathrm{supp}_{>\gamma}(B_{i})$, the mapping
$\varphi_{i}(b)=s_{i}^{-1}(b)$ must be increasing (Item 2 of Lemma 2.11).
Outside the support
$b\in(\gamma,\,\lambda)\setminus\mathrm{supp}_{>\gamma}(B_{i})$, we have
$\mathcal{B}_{-i}(b)\big{/}\mathcal{B}^{\prime}_{-i}(b)=\mathcal{B}(b)\big{/}\mathcal{B}^{\prime}(b)$,
so the mapping $\varphi_{i}(b)=\varphi_{\mathcal{B}}(b)$ is still increasing
(Fact B).

Item 3. Following Lemma 2.7, each competing bid distribution
$\mathcal{B}_{-i}(b)$ is a continuous and strictly increasing function on
$b\in[\gamma,\,\lambda]$. Hence, by definition
$\varphi_{i}(b)=b+\mathcal{B}_{-i}(b)\big{/}\mathcal{B}^{\prime}_{-i}(b)\geq
b$; the equality is possible only at the boundary bid $b=\gamma$. Item 3
follows then. This finishes the proof. ∎

As an implication of Lemma 2.13, the value distributions
$\boldsymbol{V}=\\{V_{i}\\}_{i\in[n]}$ can partially be reconstructed from the
equilibrium bid distributions $\boldsymbol{B}=\\{B_{i}\\}_{i\in[n]}$. (See
Remark 3.)

######  Corollary 2.14 (Reconstructions).

For each $i\in[n]$, the $v\geq\varphi_{i}(\gamma)$ part of the value
distribution $V_{i}(v)=\mathop{{\bf Pr}\/}_{v_{i}\sim V_{i}}\big{[}v_{i}\leq
v\big{]}$ can be reconstructed from the equilibrium bid distributions
$\boldsymbol{B}$ as follows.

$V_{i}(v)~{}=~{}\mathop{{\bf Pr}\/}_{b_{i}\sim
B_{i}}\big{[}(b_{i}\leq\gamma)\vee(\varphi_{i}(b_{i})\leq
v)\big{]},\qquad\qquad\forall v\geq\varphi_{i}(\gamma).$

In the statement of Corollary 2.14, a mapping $\varphi_{i}(b_{i})$ is
undefined when $b_{i}<\gamma$, but since the first condition
$(b_{i}\leq\gamma)$ already holds, we think of the disjunction
$(b_{i}\leq\gamma)\vee(\varphi_{i}(b_{i})\leq v)$ as being satisfied.

Figure 5: Demonstration for the reconstruction of a monopolist $h$’s value
distributions $V_{h}$ (Definitions 2.15 and 2.18). Notice that
$V_{i}(\gamma)\leq B_{i}(\gamma)\leq V_{i}(\varphi_{i}(\gamma))$. By Lemmas
2.5, 2.6 and 2.13:
(i) A normal value $v_{h}>\varphi_{h}(\gamma)$ induces a normal bid
$s_{h}(v_{h})>\gamma$.
(ii) The normal value $v_{h}=\varphi_{h}(\gamma)$ induces a normal bid
$s_{h}(v_{h})>\gamma$ or the boundary bid $s_{h}(v_{h})=\gamma$, both of which
are possible especially when there is a probability mass $\mathop{{\bf
Pr}\/}_{v_{h}\sim V_{h}}[v_{h}=\varphi_{h}(\gamma)]>0$.
(iii) A normal value $v_{h}\in(\gamma,\,\varphi_{h}(\gamma))$ induces the
boundary bid $s_{h}(v_{h})=\gamma$.
(iv) The boundary value $v_{h}=\gamma$ induces a low bid $s_{h}(v_{h})<\gamma$
or the boundary bid $s_{h}(v_{h})=\gamma$, both of which are possible
especially when there is a probability mass $\mathop{{\bf
Pr}\/}[v_{h}=\gamma]>0$.
(v) A low value $v_{h}<\gamma$ induces a bid $s_{h}(v_{h})$ that yields the
optimal zero utility $u_{h}(v_{h},\,s_{h}(v_{h}))=0$ but is otherwise
arbitrary; even an overbid $s_{h}(v_{h})>v_{h}$ is fine.

Corollary 2.14 enables us to reconstruct the $v\geq\varphi_{i}(\gamma)$ part
of each value distribution $V_{i}$. Then how about the $v<\varphi_{i}(\gamma)$
part? We shall consider two subparts separately. (i) The low value $v<\gamma$
subpart of a value distribution $V_{i}$ cannot be reconstructed from the bid
distributions $\boldsymbol{B}$. That is, an equilibrium strategy
$b_{i}=s_{i}(v)$ for a low value $v<\gamma$ is arbitrary as long as it yields
the optimal zero utility $u_{i}(v,\,b_{i})=0$. Luckily, these low value
$v<\gamma$ subparts (Lemmas 2.20 and 2.21) turn out to have no contribution to
neither of the auction/optimal Social Welfares, so we can ignore them. (ii)
The $\gamma\leq v<\varphi_{i}(\gamma)$ subpart of a value distribution $V_{i}$
has contributions to the auction/optimal Social Welfares but also cannot be
reconstructed. This subpart always induces to the boundary bid
$b_{i}=s_{i}(v)=\gamma$, following 2 (Lemmas 2.5 and 2.13).

As a remedy, we introduce the concept of monopolists (Definition 2.15); cf.
Figure 5 for a visual aid. Here we notice that $V_{i}(\gamma)\leq
B_{i}(\gamma)=\operatorname{{\bf Pr}}_{b_{i}\sim B_{i}}[b_{i}\leq\gamma]\leq
V_{i}(\varphi_{i}(\gamma))$. I.e., the first inequality holds since (Lemma
2.5) a normal bid $b_{i}>\gamma$ induces a higher normal value
$v_{i}=s_{i}^{-1}(b_{i})=\varphi_{i}(b_{i})>b_{i}>\gamma$. The second
inequality directly follows from Corollary 2.14.

######  Definition 2.15 (Monopolists).

A bidder $h\in[n]$ is called a monopolist when the probabilities of taking
normal bids/values are unequal $1-B_{h}(\gamma)<1-V_{h}(\gamma)$ or
equivalently, when the probability of taking the boundary bid yet a normal
value is nonzero $\operatorname{{\bf
Pr}}_{b_{h},\,s_{h}^{-1}}\big{[}(b_{h}=\gamma)\wedge(s_{h}^{-1}(b_{h})>\gamma)\big{]}>0$.

It is easier to understand this definition from the perspective of quantiles
(Remark 3): A bidder $h\in[n]$ is a monopolist when there are some quantiles
$q$ such that $V_{h}^{-1}(q)>\gamma$ but $B_{h}^{-1}(q)=\gamma$.

Lemma 2.6 presents the properties about the monopolists. (From the statement
of Lemma 2.16, we can infer that there is NO monopolist when the first-order
bid $\max(\boldsymbol{b})\sim\mathcal{B}$ has no probability mass at the
boundary bid $\mathcal{B}(\gamma)=0$.)

######  Lemma 2.16 (Monopolists).

There exists at most one monopolist $h$. If existential:

  * •

monopoly: The probability of a boundary first-order bid
$\big{\\{}\max(\boldsymbol{b})=\gamma\big{\\}}$ is nonzero
$\mathcal{B}(\gamma)>0$. Conditioned on the tiebreak
$\big{\\{}b_{h}=\max(\boldsymbol{b})=\gamma\big{\\}}$, the monopolist wins
$\mathrm{x}(\boldsymbol{b})=h$ almost surely.

  * •

boundedness: A boundary bid $b_{h}=\gamma$ induces a bounded random value
$s_{h}^{-1}(\gamma)\in[\gamma,\,\varphi_{h}(\gamma)]$.

###### Proof.

Suppose there is a monopolist $h\in[n]$. We first verify • ‣ 2.16 and • ‣
2.16, and then prove that there is no other monopolist.

For some normal value $v_{h}=s_{h}^{-1}(b_{h})>\gamma$, (Definitions 2.15 and
2.5) the boundary bid $b_{h}=\gamma$ yields the optimal utility
$u_{h}(v_{h},\,\gamma)=(v_{h}-\gamma)\cdot\mathrm{x}_{h}(\gamma)=\mathcal{U}_{h}(v_{h})>0$,
so the interim allocation is nonzero $\mathrm{x}_{h}(\gamma)>0$. The boundary
first-order bid $\big{\\{}\max(\boldsymbol{b})=\gamma\big{\\}}$ occurs with
probability
$\mathcal{B}(\gamma)=B_{h}(\gamma)\cdot\mathcal{B}_{-h}(\gamma)\geq\mathop{{\bf
Pr}\/}_{b_{h}}[b_{h}=\gamma]\cdot\mathrm{x}_{h}(\gamma)>0$. Assume for
contradiction that this monopolist $h\in[n]$ loses the tiebreak
$\big{\\{}b_{h}=\max(\boldsymbol{b})=\gamma\big{\\}}$ with a nonzero
probability $>0$. Based on the 2.1, some (infinitesimally) higher deviation
bid $b_{h}^{*}>b_{h}=\gamma$ gives a strictly better utility
$u_{h}(v_{h},\,b_{h}^{*})>u_{h}(v_{h},\,\gamma)>0$, which contradicts
(Definition 2.3) the optimality of this equilibrium bid $b_{h}=\gamma$. Reject
our assumption: This monopolist $h\in[n]$ always wins the tiebreak
$\big{\\{}b_{h}=\max(\boldsymbol{b})=\gamma\big{\\}}$ (• ‣ 2.16).

A boundary bid $b_{h}=\gamma$ induces a bounded random value $\gamma\leq
s_{h}^{-1}(\gamma)\leq\varphi_{h}(\gamma)$ (• ‣ 2.16). (i) This monopolist
$h\in[n]$ can never take a low value $s_{h}^{-1}(\gamma)<\gamma$. The tiebreak
$\big{\\{}b_{h}=\max(\boldsymbol{b})=\gamma\big{\\}}$ occurs with a nonzero
probability $>0$ and, suppose so, the monopolist wins
$\mathrm{x}(\boldsymbol{b})=h$ almost surely. Hence, a low value
$s_{h}^{-1}(\gamma)<\gamma$ together with a boundary bid $b_{h}=\gamma$ yields
a negative utility $<0$, which is impossible. (ii) The value is also upper
bounded $s_{h}^{-1}(\gamma)\leq\varphi_{h}(\gamma)$, provided 2 (Lemmas 2.5
and 2.13).

This monopolist $h\in[n]$ is the unique one. Otherwise, (Definition 2.15 and •
‣ 2.16) at least two monopolists $h\neq k\in[n]$ tie for the boundary first-
order bid $\big{\\{}b_{h}=b_{k}=\max(\boldsymbol{b})=\gamma\big{\\}}$ with a
nonzero probability $>0$ and, suppose so, BOTH win
$\mathrm{x}(\boldsymbol{b})=\\{h,\,k\\}$ almost surely. However, this is
impossible because we are auctioning ONE item. Lemma 2.16 follows then. ∎

Conceivably, we shall reconstruct the $\gamma\leq v<\varphi_{h}(\gamma)$
subpart just for the value distribution $V_{h}$ of the unique monopolist $h$
(if existential) – We will show this later in Lemma 2.18. To reconstruct the
$V_{h}$, we introduce (Definition 2.17) the concept of conditional value
distributions.

######  Definition 2.17 (Conditional value distributions).

Regarding the monopolist $h$’s the truncated random value
$\max(s_{h}^{-1}(b_{h}),\,\gamma)$ for $b_{h}\sim B_{h}$, define the
conditional value distribution $P(v)$ as follows.

$P(v)~{}:=~{}\mathop{{\bf Pr}\/}_{b_{h}\sim
B_{h},\,s_{h}^{-1}}\big{[}\,\max(s_{h}^{-1}(b_{h}),\,\gamma)\leq
v\,\,\big{|}\,\big{.}\,b_{h}\leq\gamma\,\big{]},\qquad\qquad\forall v\geq 0.$

In the case of no monopolist $h=\emptyset$, the
$P(v):=\mathbbm{1}(v\geq\gamma)$ always takes the boundary value $\gamma$.

######  Remark 5 (Conditional value distributions).

The random value $s_{h}^{-1}(b_{h})$ for $b_{h}\sim B_{h}$ exactly follows the
distribution $V_{h}$. With the help of Figure 5, we can see that the CDF
$P(v)$ is given by

$\displaystyle P(v)~{}=~{}\begin{cases}0&\forall v\in[0,\,\gamma)\\\
V_{h}(v)/B_{h}(\gamma)&\forall v\in[\gamma,\,\varphi_{h}(\gamma))\\\ 1&\forall
v\in[\varphi_{h}(\gamma),\,+\infty]\end{cases}.$

In general, the $P(v)$ can be any $[\gamma,\,\varphi_{h}(\gamma)]$-supported
distribution. Given this extra information, we can reconstruct the value
distributions $\boldsymbol{V}=\\{V_{i}\\}_{i\in[n]}$ (Lemma 2.18) except the
unimportant low value $v<\gamma$ parts.

######  Lemma 2.18 (Reconstructions).

For each $i\in[n]$, the $v\geq\gamma$ part of the value distribution
$V_{i}(v)=\mathop{{\bf Pr}\/}_{v_{i}\sim V_{i}}\big{[}v_{i}\leq v\big{]}$ can
be reconstructed from the equilibrium bid distributions $\boldsymbol{B}$ plus
the conditional value distribution $P$ as follows.

  * •

$V_{i}(v)=\mathop{{\bf Pr}\/}_{b_{i}\sim
B_{i}}\big{[}(b_{i}\leq\gamma)\vee(\varphi_{i}(b_{i})\leq v)\big{]}$ in the
case of a non-monopoly bidder $i\in[n]\setminus\\{h\\}$.

  * •

$V_{h}(v)=P(v)\cdot\mathop{{\bf Pr}\/}_{b_{h}\sim
B_{h}}\big{[}(b_{h}\leq\gamma)\vee(\varphi_{h}(b_{h})\leq v)\big{]}$ in the
case of the monopolist $h$.

(a)  The monopolist $h$

(b)  A non-monopoly bidder $i\in[n]\setminus\\{h\\}$

Figure 6: Demonstration for (Lemma 2.18) the reconstruction of the value
distributions $\boldsymbol{V}$.

###### Proof.

See Figure 6 for a visual aid. Regarding a non-monopoly bidder
$i\in[n]\setminus\\{h\\}$, (Lemmas 2.5 and 2.15; cf. Figure 6b) a normal bid
$>\gamma$ induces a normal value $>\gamma$ and vice versa. By 2, such a normal
value $v_{i}=\varphi_{i}(b_{i})$ for $b_{i}>\gamma$ is at least
$v_{i}\geq\varphi_{i}(\gamma)$. Hence, on the OPEN interval
$v\in(\gamma,\,\varphi_{i}(\gamma))$, the value distribution $V_{i}(v)$ has no
density and keeps a constant function $V_{i}(v)=B_{i}(\gamma)$. Given these,
the reconstruction in Corollary 2.14 can be generalized naively: For
$v\in[\gamma,\,\varphi_{i}(\gamma))$, we have
$V_{i}(v)=B_{i}(\gamma)=\mathop{{\bf Pr}\/}_{b_{i}\sim
B_{i}}\big{[}b_{i}\leq\gamma\big{]}=\mathop{{\bf Pr}\/}_{b_{i}\sim
B_{i}}\big{[}(b_{i}\leq\gamma)\vee(\varphi_{i}(b_{i})\leq v\big{]}$.

Further, we can check the claimed “monopolist” formula $V_{h}(v)$ for
$v\in[\gamma,\,\varphi_{i}(\gamma))$ (cf. Figure 6a): $P(v)\cdot\mathop{{\bf
Pr}\/}_{b_{h}\sim B_{h}}\big{[}(b_{h}\leq\gamma)\vee(\varphi_{h}(b_{h})\leq
v)\big{]}=P(v)\cdot\mathop{{\bf Pr}\/}_{b_{h}\sim
B_{h}}\big{[}b_{h}\leq\gamma\big{]}=P(v)\cdot B_{h}(\gamma)=V_{h}(v)$, where
the first step again leverages 2. This finishes the proof. ∎

Lemma 2.19 will be useful for formulating the expected auction/optimal Social
Welfares.

######  Lemma 2.19 (Social Welfares).

Conditioned on the boundary first-order bid
$\big{\\{}\max(\boldsymbol{b})=\gamma\big{\\}}$, each of the following exactly
follows the conditional value distribution $P$:

  * •

The conditional auction Social Welfare
$\big{\\{}s_{\mathrm{x}(\boldsymbol{b})}^{-1}(\gamma)\,\big{|}\,\big{.}\max(\boldsymbol{b})=\gamma\big{\\}}$.

  * •

The conditional optimal Social Welfare
$\big{\\{}\max(\boldsymbol{s}^{-1}(\boldsymbol{b}))\,\big{|}\,\big{.}\max(\boldsymbol{b})=\gamma\big{\\}}$.

###### Proof.

The random events $\big{\\{}\max(\boldsymbol{b})=\gamma\big{\\}}$ and
$\big{\\{}\max(\boldsymbol{b})\leq\gamma\big{\\}}$ are identical, regarding
the infimum first-order bid $\gamma=\inf(\mathrm{supp}(\mathcal{B}))$.
Conditioned on this, (i) a non-monopoly bidder $i\in[n]\setminus\\{h\\}$ has a
low/boundary bid $b_{i}\leq\gamma$ and (Lemmas 2.5 and 2.15) a low/boundary
value $s_{i}^{-1}(b_{i})\leq\gamma$; while (ii) the monopolist $h$ has EITHER
a low bid $b_{h}<\gamma$ and a low/boundary value
$s_{h}^{-1}(b_{h})\leq\gamma$, OR the boundary bid $b_{h}=\gamma$ and (Lemma
2.16) a boundary/normal value
$s_{h}^{-1}(b_{h})\in[\gamma,\,\varphi_{h}(\gamma)]$.

The allocated bidder $\mathrm{x}(\boldsymbol{b})\in[n]$ always take the
boundary bid $b_{\mathrm{x}(\boldsymbol{b})}=\gamma$ and, to make the utility
nonnegative, a boundary/normal value
$s_{\mathrm{x}(\boldsymbol{b})}^{-1}(b_{\mathrm{x}(\boldsymbol{b})})=s_{\mathrm{x}(\boldsymbol{b})}^{-1}(\gamma)\geq\gamma$;
the case of a normal value $>\gamma$ occurs only if the monopolist is
allocated $\mathrm{x}(\boldsymbol{b})=h$. Hence, the conditional optimal
Social Welfare is identically distributed as each of the following:

$\displaystyle\big{\\{}\max(\boldsymbol{s}^{-1}(\boldsymbol{b}))\,\big{|}\,\big{.}\max(\boldsymbol{b})=\gamma\big{\\}}$
$\displaystyle~{}\overset{\tt
d}{=}~{}\big{\\{}\max(\boldsymbol{s}^{-1}(\boldsymbol{b}))\,\big{|}\,\big{.}\max(\boldsymbol{b})\leq\gamma\big{\\}}$
$\displaystyle\gamma=\inf(\mathrm{supp}(\mathcal{B}))$
$\displaystyle~{}\overset{\tt
d}{=}~{}\big{\\{}\max(\boldsymbol{s}^{-1}(\boldsymbol{b}),\,\gamma)\,\big{|}\,\big{.}\max(\boldsymbol{b})\leq\gamma\big{\\}}$
$\displaystyle
s_{\mathrm{x}(\boldsymbol{b})}^{-1}(b_{\mathrm{x}(\boldsymbol{b})})\geq\gamma$
$\displaystyle~{}\overset{\tt
d}{=}~{}\big{\\{}\max(s_{h}^{-1}(b_{h}),\,\gamma)\,\big{|}\,\big{.}\max(\boldsymbol{b})\leq\gamma\big{\\}}$
$s_{i}^{-1}(b_{i})\geq\gamma$ for $i\neq h$ $\displaystyle~{}\overset{\tt
d}{=}~{}\big{\\{}\max(s_{h}^{-1}(b_{h}),\,\gamma)\,\big{|}\,\big{.}b_{h}\leq\gamma\big{\\}}.$
independence

That is, the conditional optimal Social Welfare follows (Definition 2.17) the
distribution $P$. Further, since the monopolist $h$ (as the only possible
bidder that has a normal value $>\gamma$) always wins the tiebreak
$\big{\\{}b_{h}=\max(\boldsymbol{b})=\gamma\big{\\}}$ (Lemma 2.16), the
conditional auction/optimal Social Welfares are identically distributed
$\big{\\{}s_{\mathrm{x}(\boldsymbol{b})}^{-1}(\gamma)\,\big{|}\,\big{.}\max(\boldsymbol{b})=\gamma\big{\\}}\overset{\tt
d}{=}\big{\\{}\max(\boldsymbol{s}^{-1}(\boldsymbol{b}))\,\big{|}\,\big{.}\max(\boldsymbol{b})=\gamma\big{\\}}$,
which again follow the distribution $P$. This finishes the proof. ∎

###  2.3 Reformulation for the Price of Anarchy problem

To address the Price of Anarchy problem, we shall formulate the expected
auction/optimal Social Welfares ${\sf
FPA}(\boldsymbol{V},\,\boldsymbol{s},\,\mathrm{x})$ and ${\sf
OPT}(\boldsymbol{V},\,\boldsymbol{s},\,\mathrm{x})$. Indeed, these can be
written in terms of the equilibrium bid distributions $\boldsymbol{B}$ plus
the conditional value distribution $P$ (Definition 2.17).

First, Lemma 2.20 formulates the expected auction Social Welfare ${\sf
FPA}(\boldsymbol{V},\,\boldsymbol{s},\,\mathrm{x})$.

######  Lemma 2.20 (Auction Social Welfare).

The expected auction Social Welfare ${\sf
FPA}(\boldsymbol{V},\,\boldsymbol{s},\,\mathrm{x})$ can be formulated based on
the conditional value distribution and the equilibrium bid distributions
$(P,\,\boldsymbol{B})$:

$\displaystyle{\sf
FPA}(\boldsymbol{V},\,\boldsymbol{s},\,\mathrm{x})~{}=~{}{\sf
FPA}(P,\,\boldsymbol{B})~{}=~{}\mathop{{\bf
E}\/}[P]\cdot\mathcal{B}(\gamma)+\sum_{i\in[n]}\bigg{(}\int_{\gamma}^{\lambda}\varphi_{i}(b)\cdot\frac{B^{\prime}_{i}(b)}{B_{i}(b)}\cdot\mathcal{B}(b)\cdot\mathrm{d}b\bigg{)}.$

where the first-order bid distribution
$\mathcal{B}(b)=\prod_{i\in[n]}B_{i}(b)$ and the bid-to-value mappings
$\varphi_{i}(b)$ can be computed from the bid distributions
$\boldsymbol{B}=\\{B_{i}\\}_{i\in[n]}$ (Definition 2.12).

###### Proof.

In any realization, the outcome auction Social Welfare is the allocated
bidder’s value $v_{\mathrm{x}(\boldsymbol{s}(\boldsymbol{v}))}$. Over the
randomness of the values $\boldsymbol{v}=(v_{i})_{i\in[n]}\sim\boldsymbol{V}$,
the equilibrium strategies $\boldsymbol{s}=\\{s_{i}\\}_{i\in[n]}$, and the
allocation rule $\mathrm{x}(\boldsymbol{s}(\boldsymbol{v}))$, the expected
auction Social Welfare ${\sf FPA}$ is given by

$\displaystyle{\sf FPA}~{}=~{}\mathop{{\bf
E}\/}_{\boldsymbol{v},\,\boldsymbol{s},\,\mathrm{x}}\big{[}\,v_{\mathrm{x}(\boldsymbol{s}(\boldsymbol{v}))}\,\big{]}$
$\displaystyle~{}=~{}\mathop{{\bf
E}\/}_{\boldsymbol{v},\,\boldsymbol{s},\,\mathrm{x}}\big{[}\,v_{\mathrm{x}(\boldsymbol{s}(\boldsymbol{v}))}\cdot\mathbbm{1}(\max(\boldsymbol{s}(\boldsymbol{v}))=\gamma)\,\big{]}$
(B) $\displaystyle\phantom{~{}=~{}}+\mathop{{\bf
E}\/}_{\boldsymbol{v},\,\boldsymbol{s},\,\mathrm{x}}\big{[}\,v_{\mathrm{x}(\boldsymbol{s}(\boldsymbol{v}))}\cdot\mathbbm{1}(\max(\boldsymbol{s}(\boldsymbol{v}))>\gamma)\,\big{]}.\hskip
13.37282pt$ (N)

Here we used the fact that the first-order bid
$\max(\boldsymbol{s}(\boldsymbol{v}))\sim\mathcal{B}$ is at least
$\gamma=\inf(\mathrm{supp}(\mathcal{B}))$.

For Term (B), we deduce that

Term (B) $\displaystyle~{}=~{}\mathop{{\bf
E}\/}_{\boldsymbol{v},\,\boldsymbol{s},\,\mathrm{x}}\big{[}\,v_{\mathrm{x}(\boldsymbol{s}(\boldsymbol{v}))}\cdot\mathbbm{1}(\max(\boldsymbol{s}(\boldsymbol{v}))=\gamma)\,\big{]}$
$\displaystyle~{}=~{}\mathop{{\bf
E}\/}_{\boldsymbol{v},\,\boldsymbol{s},\,\mathrm{x}}\big{[}\,v_{\mathrm{x}(\boldsymbol{s}(\boldsymbol{v}))}\,\,\big{|}\,\big{.}\,\max(\boldsymbol{s}(\boldsymbol{v}))=\gamma\,\big{]}\cdot\mathop{{\bf
Pr}\/}_{\boldsymbol{v},\,\boldsymbol{s}}\big{[}\,\max(\boldsymbol{s}(\boldsymbol{v}))=\gamma\,\big{]}$
$\displaystyle~{}=~{}\mathop{{\bf E}\/}[P]\cdot\mathcal{B}(\gamma).$

The last equality uses the fact that conditioned on the boundary first-order
bid $\big{\\{}\max(\boldsymbol{s}(\boldsymbol{v}))=\gamma\big{\\}}$, the
allocated bidder $\mathrm{x}(\boldsymbol{s}(\boldsymbol{v}))$’s value follows
the distribution $P$ (Lemma 2.19).

For Term (N), we deduce that

Term (N) $\displaystyle~{}=~{}\mathop{{\bf
E}\/}_{\boldsymbol{v},\,\boldsymbol{s},\,\mathrm{x}}\big{[}\,v_{\mathrm{x}(\boldsymbol{s}(\boldsymbol{v}))}\cdot\mathbbm{1}(\max(\boldsymbol{s}(\boldsymbol{v}))>\gamma)\,\big{]}\phantom{\bigg{.}}$
$\displaystyle~{}=~{}\mathop{{\bf
E}\/}_{\boldsymbol{b},\,\boldsymbol{s}^{-1},\,\mathrm{x}}\big{[}\,s_{\mathrm{x}(\boldsymbol{b})}^{-1}(b_{\mathrm{x}(\boldsymbol{b})})\cdot\mathbbm{1}(\max(\boldsymbol{b})>\gamma)\,\big{]}\phantom{\bigg{.}}$
(N1) $\displaystyle~{}=~{}\sum_{i\in[n]}\mathop{{\bf
E}\/}_{\boldsymbol{b},\,s_{i}^{-1},\,\mathrm{x}}\big{[}\,s_{i}^{-1}(b_{i})\cdot\mathbbm{1}(\mathrm{x}(\boldsymbol{b})=i)\cdot\mathbbm{1}(b_{i}>\gamma)\,\big{]}\phantom{\bigg{.}}\hskip
46.37813pt$ (N2) $\displaystyle~{}=~{}\sum_{i\in[n]}\mathop{{\bf
E}\/}_{b_{i}}\big{[}\,\varphi_{i}(b_{i})\cdot\mathrm{x}_{i}(b_{i})\cdot\mathbbm{1}(b_{i}>\gamma)\,\big{]}\phantom{\bigg{.}}$
(N3) $\displaystyle~{}=~{}\sum_{i\in[n]}\mathop{{\bf
E}\/}_{b_{i}}\big{[}\,\varphi_{i}(b_{i})\cdot\mathcal{B}_{-i}(b_{i})\cdot\mathbbm{1}(b_{i}>\gamma)\,\big{]}\phantom{\bigg{.}}$
(N4)
$\displaystyle~{}=~{}\sum_{i\in[n]}\bigg{(}\int_{\gamma}^{\lambda}\varphi_{i}(b)\cdot\mathcal{B}_{-i}(b)\cdot
B^{\prime}_{i}(b)\cdot\mathrm{d}b\bigg{)}$
$\displaystyle~{}=~{}\sum_{i\in[n]}\bigg{(}\int_{\gamma}^{\lambda}\varphi_{i}(b)\cdot\frac{B^{\prime}_{i}(b)}{B_{i}(b)}\cdot\mathcal{B}(b)\cdot\mathrm{d}b\bigg{)}.$
(N5)

(N1): Redenote $b_{i}=s_{i}(v_{i})\sim B_{i}$ for $i\in[n]$. Recall Definition
2.10 that each random inverse $s_{i}^{-1}(b_{i})$ for $b_{i}\sim B_{i}$ is
identically distributed as the random value $v_{i}\sim V_{i}$.
(N2): Divide the event $\big{\\{}\max(\boldsymbol{b})>\gamma\big{\\}}$ into
subevents
$\big{\\{}\mathrm{x}(\boldsymbol{b})=i~{}\text{and}~{}b_{i}=\max(\boldsymbol{b})>\gamma\big{\\}}$
for $i\in[n]$.
(N3): Lemma 2.13 (Item 1) that $s_{i}^{-1}(b)=\varphi_{i}(b)$ almost surely
for any normal bid $b\in\mathrm{supp}_{>\gamma}(B_{i})$, AND Definition 2.2
that $\mathrm{x}_{i}(b)=\mathop{{\bf
Pr}\/}_{\boldsymbol{b}_{-i},\,\mathrm{x}}\big{[}\mathrm{x}(\boldsymbol{b}_{-i},\,b)=i\big{]}=\mathop{{\bf
E}\/}_{\boldsymbol{b}_{-i},\,\mathrm{x}}\big{[}\mathbbm{1}(\mathrm{x}(\boldsymbol{b}_{-i},\,b)=i)\big{]}$.
(N4): Corollary 2.8 that $\mathrm{x}_{i}(b)=\mathcal{B}_{-i}(b)$ for any
normal bid $b>\gamma$.
(N5): The first-order bid distribution
$\mathcal{B}(b)=B_{i}(b)\cdot\mathcal{B}_{-i}(b)$.

Combining Terms (B) and (N) together finishes the proof of Lemma 2.20. ∎

Moreover, Lemma 2.21 formulates the expected optimal Social Welfare ${\sf
OPT}(\boldsymbol{V},\,\boldsymbol{s},\,\mathrm{x})$.

######  Lemma 2.21 (Optimal Social Welfare).

The expected optimal Social Welfare ${\sf
OPT}(\boldsymbol{V},\,\boldsymbol{s},\,\mathrm{x})$ can be formulated based on
the conditional value distribution and the equilibrium bid distributions
$(P,\,\boldsymbol{B})$:

$\displaystyle{\sf
OPT}(\boldsymbol{V},\,\boldsymbol{s},\,\mathrm{x})~{}=~{}{\sf
OPT}(P,\,\boldsymbol{B})~{}=~{}\gamma+\int_{\gamma}^{+\infty}\Big{(}1-P(v)\cdot\prod_{i\in[n]}\mathop{{\bf
Pr}\/}_{b_{i}}\big{[}b_{i}\leq\gamma\vee\varphi_{i}(b_{i})\leq
v\big{]}\Big{)}\cdot\mathrm{d}v.$

###### Proof.

This proof simply follows from Lemma 2.18, i.e., we essentially reconstruct
the value distributions $\boldsymbol{V}=\\{V_{i}\\}_{i\in[n]}$ from the tuple
$(P,\,\boldsymbol{B})$.

In any realization, the outcome optimal Social Welfare is the first-order
value $\max(\boldsymbol{v})$. Over the randomness of the values
$\boldsymbol{v}=(v_{i})_{i\in[n]}\sim\boldsymbol{V}$, the expected optimal
Social Welfare ${\sf OPT}$ is given by

$\displaystyle{\sf OPT}$ $\displaystyle~{}=~{}\mathop{{\bf
E}\/}_{\boldsymbol{v}}\big{[}\,\max(\boldsymbol{v})\,\big{]}~{}=~{}\mathop{{\bf
E}\/}_{\boldsymbol{v}}\big{[}\,\max(\boldsymbol{v},\,\gamma)\,\big{]}\phantom{\bigg{.}}$
(O1)
$\displaystyle~{}=~{}\int_{0}^{+\infty}\Big{(}1-\prod_{i\in[n]}V_{i}(v)\cdot\mathbbm{1}(v\geq\gamma)\Big{)}\cdot\mathrm{d}v$
(O2)
$\displaystyle~{}=~{}\int_{0}^{+\infty}\Big{(}1-\Big{(}1-P(v)\cdot\prod_{i\in[n]}\mathop{{\bf
Pr}\/}_{b_{i}}\big{[}b_{i}\leq\gamma\vee\varphi_{i}(b_{i})\leq
v\big{]}\cdot\mathbbm{1}(v\geq\gamma)\Big{)}\cdot\mathrm{d}v$ (O3)
$\displaystyle~{}=~{}\gamma+\int_{\gamma}^{+\infty}\Big{(}1-P(v)\cdot\prod_{i\in[n]}\mathop{{\bf
Pr}\/}_{b_{i}}\big{[}b_{i}\leq\gamma\vee\varphi_{i}(b_{i})\leq
v\big{]}\Big{)}\cdot\mathrm{d}v.$

(O1): The first-order value $\max(\boldsymbol{v})$ for
$\boldsymbol{v}\sim\boldsymbol{V}$ is always boundary/normal $\geq\gamma$.
(O2): The expectation of a nonnegative distribution $F$ is given by
$\operatorname{{\bf
E}}[F]=\int_{0}^{+\infty}\big{(}1-F(v)\big{)}\cdot\mathrm{d}v$.
(O3): Apply Lemma 2.18. It also holds in case that no monopolist exists since,
suppose so, we have $P(v)=1$ for $v\geq\gamma$. This finishes the proof of
Lemma 2.21. ∎

The above $(P,\,\boldsymbol{B})$-based Social Welfare formulas ${\sf
FPA}(P,\,\boldsymbol{B})$ and ${\sf OPT}(P,\,\boldsymbol{B})$, together with
the characterizations of $P$ and $\boldsymbol{B}$, are the foundation of the
whole paper. From all these discussions, we notice that the below-$\gamma$
parts of bid distributions $\boldsymbol{B}$ and value distributions
$\boldsymbol{V}$ are less important. To stress this observation, we have the
key definition of valid instances $(P,\,\boldsymbol{B})\in\mathbb{B}_{\sf
valid}$.

######  Definition 2.22 (Valid instances).

An instance $(P,\,\boldsymbol{B})$, where
$\boldsymbol{B}=\\{B_{i}\\}_{i\in[n]}$, is described by $n+1$ independent
distributions and is called valid $(P,\,\boldsymbol{B})\in\mathbb{B}_{\sf
valid}$ when the following hold.

  * •

There are $\gamma\in[0,\,+\infty)$ and $\lambda\in[\gamma,\,+\infty]$ such
that
$\gamma=\inf(\mathrm{supp}(B_{i}))\leq\sup(\mathrm{supp}(B_{i}))\leq\lambda$;
with at least one equality $\max(\mathrm{supp}(B_{i}))=\lambda$. It is
important that all these bid distributions
$\boldsymbol{B}=\\{B_{i}\\}_{i\in[n]}$ share the same infimum bid $\gamma$.

  * •

$B_{i}(b)$ for $i\in[n]$ each has no probability mass on
$b\in(\gamma,\,\lambda]$, excluding the boundary $\gamma$, thus each being
continuous on the CLOSED interval $b\in[\gamma,\,\lambda]$.

  * •

Let $\mathcal{B}(b)=\prod_{i\in[n]}B_{i}(b)$ and
$\mathcal{B}_{-i}(b)=\prod_{k\in[n]\setminus\\{i\\}}B_{k}(b)$ for $i\in[n]$.
These first-order/competing bid distributions $\mathcal{B}(b)$ and
$\mathcal{B}_{-i}(b)$ for $i\in[n]$ each have probability densities almost
everywhere on $b\in(\gamma,\,\lambda]$, thus each being strictly increasing on
the CLOSED interval $b\in[\gamma,\,\lambda]$.

  * •

The bid-to-value mappings
$\varphi_{i}(b):=b+\frac{\mathcal{B}_{-i}(b)}{\mathcal{B}^{\prime}_{-i}(b)}$
for $i\in[n]$ each are (weakly) increasing over the bid support
$b\in[\gamma,\,\lambda]$.

  * •

$P$ is a distribution supported on $[\gamma,\varphi_{h}(\gamma)]$ for some
(monopolist) $h\in[n]$. Without loss of generality, we reindex the bidders
$i\in[n]$ such that $h=1$.

The valid instances $(P,\,\boldsymbol{B})\in\mathbb{B}_{\sf valid}$ capture
nearly all Bayesian Nash Equilibria
$\big{\\{}\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V},\,\mathrm{x})\big{\\}}$.
Essentially, there is a bijection between these two spaces (without
considering some less important details about Bayesian Nash Equilibria),
especially in a sense of the Social Welfare invariant. This is formalized into
Theorem 6.

######  Theorem 6 (Valid instances).

(I) For any valid instance $(P,\,\boldsymbol{B})\in\mathbb{B}_{\sf valid}$,
there is some equilibrium
$\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V},\,\mathrm{x})\neq\emptyset$, for
some value distribution $\boldsymbol{V}=\\{V_{i}\\}_{i\in[n]}$, whose
conditional value distribution and bid distribution are exactly the
$(P,\,\boldsymbol{B})$. (II) For any value distribution
$\boldsymbol{V}=\\{V_{i}\\}_{i\in[n]}$ and any equilibrium
$\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V},\,\mathrm{x})\neq\emptyset$,
there is some valid instance $(P,\,\boldsymbol{B})\in\mathbb{B}_{\sf valid}$
that yields the same auction/optimal Social Welfares ${\sf
FPA}(P,\,\boldsymbol{B})={\sf
FPA}(\boldsymbol{V},\,\boldsymbol{s},\,\mathrm{x})$ and ${\sf
OPT}(P,\,\boldsymbol{B})={\sf
OPT}(\boldsymbol{V},\,\boldsymbol{s},\,\mathrm{x})$.

(a)  The monopolist $h=B_{1}$

(b)  A non-monopoly bidder $B_{i}$ for $i\in[2:n]$

Figure 7: Demonstration for valid instances
$(P,\,\boldsymbol{B})\in\mathbb{B}_{\sf valid}$ and Theorem 6.

###### Proof.

See Figure 7 for a visual aid. We prove Items (I) and (II) separately.

(I) Given a valid instance $(P,\,\boldsymbol{B})\in\mathbb{B}_{\sf valid}$, we
can construct the boundary/normal value $v\geq\gamma$ part of some value
distribution $\boldsymbol{V}=\\{V_{i}\\}_{i\in[n]}$, following Lemma 2.18. For
the low value $v<\gamma$ part, we simply let $V_{i}(v)\equiv 0$ on $v<\gamma$,
namely putting all the undecided probabilities to the boundary value $\gamma$.
Then the value distribution $\boldsymbol{V}=\\{V_{i}\\}_{i\in[n]}$ is well
defined.

Since we zero-out everything below $\gamma$, the equivalence in Remark 3 can
be extend to the entire quantile space $q\in[0,1]$. Hence, we can construct
the equilibrium by identifying the quantiles for value distributions and bid
distributions. Consider the quantile bid/value functions
$\\{B_{i}^{-1}\\}_{i\in[n]}$ and $\\{V_{i}^{-1}\\}_{i\in[n]}$. As Figure 7
shows, we construct the strategy profile
$\boldsymbol{s}=\\{s_{i}\\}_{i\in[n]}$ as follows: For $i\in[n]$ and
$v\in\mathrm{supp}(V_{i})$, let $q\sim U[0,\,1]$ be a uniform random quantile,
then

$\mathop{{\bf Pr}\/}_{s_{i}}\big{[}\,s_{i}(v)=b\,\big{]}~{}=~{}\mathop{{\bf
Pr}\/}_{q\,\sim\,U[0,\,1]}\big{[}\,B_{i}^{-1}(q)=b\,\,\big{|}\,\big{.}\,V_{i}^{-1}(q)=v\,\big{]},\qquad\qquad\forall
b\in[\gamma,\,\lambda].$

We conclude Item (I) with verifying the equilibrium conditions (Definition
2.3).

######  Fact A.

$u_{i}(v,\,s_{i}(v))\geq u_{i}(v,\,b^{*})$ almost surely, for each bidder
$i\in[n]$, any value $v\in\mathrm{supp}(V_{i})$, and any deviation bid
$b^{*}\geq 0$.

###### Proof.

First, the monopolist $B_{1}$ (Corollaries 2.8, 2.15 and 2.16) has the
allocation $\mathrm{x}_{1}(b)=\mathcal{B}_{-1}(b)$ for a boundary/normal bid
$b\geq\gamma$ and $\mathrm{x}_{1}(b)=0$ for a low $b\in[0,\,\gamma)$.
(i) A Normal Bid $s_{1}(v)\in(\gamma,\,\lambda]$. The underlying value
$v=\varphi_{1}(s_{1}(v))>s_{1}(v)>\gamma$, by construction and Lemmas 2.18 and
2.13. Accordingly, the current allocation/utility are positive
$u_{1}(v,\,s_{1}(v))=(v-s_{1}(v))\cdot\mathcal{B}_{-1}(s_{1}(v))>0$. Then a
low deviation bid $b^{*}<\gamma$ is suboptimal, because the deviated
allocation/utility are zero
$u_{1}(v,\,b^{*})=(v-b^{*})\cdot\mathrm{x}_{1}(b^{*})=0$. Moreover, a
boundary/normal deviation bid $b^{*}\geq\gamma$ is suboptimal – The current
bid $s_{1}(v)>\gamma$ maximizes the utility formula
$u_{1}(v,\,b^{*})=(v-b^{*})\cdot\mathcal{B}_{-1}(b^{*})$, because the partial
derivative $\frac{\partial u_{1}}{\partial
b^{*}}=\big{(}v-\varphi_{1}(b^{*})\big{)}\cdot\mathcal{B}^{\prime}_{-1}(b^{*})$,
the underlying value $v=\varphi_{1}(s_{1}(v))$, and the mapping
$\varphi_{1}(b^{*})$ is increasing (Item 2 of Lemma 2.13).
(ii) A Boundary Bid $s_{1}(v)=\gamma$. The underlying value
$v=s_{1}^{-1}(\gamma)$ exactly follows the conditional value distribution $P$
and ranges within $\mathrm{supp}(P)\subseteq[\gamma,\,\varphi_{1}(\gamma)]$,
by construction and Definitions 2.17 and 2.22. Reusing the above arguments
(i.e., the utility formula $u_{1}(v,\,b^{*})$ is decreasing for
$b^{*}\geq\gamma$), we can easily see that the current bid $s_{1}(v)=\gamma$
is optimal. In sum, the monopolist $B_{1}$ meets the equilibrium conditions.

Each non-monopoly bidder $i\in[2:n]$ (Corollaries 2.8, 2.15 and 2.16) has the
allocation $\mathrm{x}_{i}(b)=\mathcal{B}_{-i}(b)$ for a normal bid $b>\gamma$
and $\mathrm{x}_{i}(b)=0$ for a low/boundary bid $b\in[0,\,\gamma]$.
(i) A Normal Bid $s_{i}(v)\in(\gamma,\,\lambda]$. Reusing the above arguments
for the monopolist $B_{1}$, we can easily see that the current normal bid
$s_{i}(v)\in(\gamma,\,\lambda]$ is optimal.
(ii) A Boundary Bid $s_{i}(v)=\gamma$. The underlying value must be the
boundary value $v=s_{i}^{-1}(\gamma)\equiv\gamma$, by construction and
Definitions 2.17 and 2.22. Obviously, the current zero utility
$u_{i}(v,\,s_{i}(v))=0$ and the current boundary bid $s_{i}(v)=\gamma$ are
optimal. In sum, each non-monopoly bidder $i\in[2:n]$ meets the equilibrium
conditions. Fact A follows then. ∎

(II) Given an equilibrium
$\boldsymbol{s}\in\mathbb{BNE}(\boldsymbol{V},\,\mathrm{x})\neq\emptyset$, as
before, consider the bid distribution $\boldsymbol{B}^{(\boldsymbol{s})}$, the
conditional value distribution $P^{(\boldsymbol{s})}$, and the
infimum/supremum first-order bids
$\gamma=\inf(\mathrm{supp}(\mathcal{B}^{(\boldsymbol{s})}))$ and
$\lambda=\sup(\mathrm{supp}(\mathcal{B}^{(\boldsymbol{s})}))$. Following
Lemmas 2.7, 2.13, 2.16 and 2.17, this instance
$(P^{(\boldsymbol{s})},\,\boldsymbol{B}^{(\boldsymbol{s})})$ is almost valid,
except that the distribution
$\boldsymbol{B}^{(\boldsymbol{s})}=\\{B_{i}^{(\boldsymbol{s})}\\}_{i\in[n]}$
can be supported on low bids $b<\gamma$. (Recall that the distribution
$P^{(\boldsymbol{s})}$ is just supported on boundary/high values
$v\geq\gamma$.) By truncating the bid distribution $B_{i}(b)\equiv
B_{i}^{(\boldsymbol{s})}(b)\cdot\mathbbm{1}(b\geq\gamma)$ for $i\in[n]$ and
reusing the conditional value distribution $P\equiv P^{(\boldsymbol{s})}$, we
obtain a valid instance $(P,\,\boldsymbol{B})\in\mathbb{B}_{\sf valid}$.
Particularly, the truncation $B_{i}(b)\equiv
B_{i}^{(\boldsymbol{s})}(b)\cdot\mathbbm{1}(b\geq\gamma)$ does not modify the
auction/optimal Social Welfares (cf. Lemmas 2.20 and 2.21). This finishes the
proof of Item (II). ∎

We conclude this section with (Corollary 2.23) an equivalent definition for
Price of Anarchy in First Price Auctions, as an implication of Theorem 6.

######  Corollary 2.23 (Price of Anarchy).

Regarding First Price Auctions, the Price of Anarchy is given by

$\displaystyle{\sf PoA}~{}=~{}\inf\bigg{\\{}\,\frac{{\sf
FPA}(P,\,\boldsymbol{B})}{{\sf
OPT}(P,\,\boldsymbol{B})}\,\,\bigg{|}\,\bigg{.}\,(P,\,\boldsymbol{B})\in\mathbb{B}_{\sf
valid}~{}\text{\em and}~{}{\sf OPT}(P,\,\boldsymbol{B})<+\infty\,\bigg{\\}}.$

##  3 Preprocessing Valid Instances

This section presents several preparatory reductions towards the potential
worst-case instances. In Section 3.1, we introduce the concept of valid pseudo
instances, which generalizes valid instances and eases the presentation. In
Section 3.2, we discretize an instance up to any PoA-error $\varepsilon>0$,
simplifying the bid-to-value mappings $\boldsymbol{\varphi}$ to a (finite-
size) bid-to-value table $\boldsymbol{\Phi}$. In Section 3.3, we translate the
instances, making the infimum bids zero $\gamma=0$. In Section 3.4, we layer
the bid-to-value mappings $\boldsymbol{\varphi}$, making the table
$\boldsymbol{\Phi}$ decreasing bidder-by-bidder. In Section 3.5, we
derandomize the conditional value $P$ to either the floor value
$P^{\downarrow}\equiv 0$ or the ceiling value
$P^{\uparrow}\equiv\varphi_{1}(0)$.

To conclude (Section 3.6), we restrict the space of the worst cases to the
floor/ceiling pseudo instances, which can be represented just by the table
$\boldsymbol{\Phi}$. These materials serve as the basis for the more
complicated reductions later in Section 4.

###  3.1 The concept of valid pseudo instances

This subsection introduces the concept of valid pseudo instances
$(P,\,\boldsymbol{B}\otimes L)$, a natural extension of valid real instances
$(P,\,\boldsymbol{B})$ from Definition 2.22. Given a valid real instance
$(P,\,\boldsymbol{B})$, we can always (Lemma 3.5) construct a valid pseudo
instance $(P,\,\boldsymbol{B}\otimes L)$ that yields the same auction/optimal
Social Welfares. Thus towards a lower bound on the Price of Anarchy, we can
consider valid pseudo instances instead (Corollary 3.6).

Roughly speaking, a pseudo instance $(P,\,\boldsymbol{B}\otimes L)$ includes
one more pseudo bidder $L$ to a real instance $(P,\,\boldsymbol{B})$. To
clarify this difference, we often use the letter $i\in[n]$ and its variants
for real bidders, and the Greek letter $\sigma\in[n]\cup\\{L\\}$ and its
variants for real or pseudo bidders. Without ambiguity, we redenote by
$\mathbb{B}_{\sf valid}$ the space of valid pseudo instances. The formal
definition of valid pseudo instances is given below; cf. Definition 2.22 for
comparison.

######  Definition 3.1 (Valid pseudo instances).

A pseudo instance $(P,\,\boldsymbol{B}\otimes L)$ has two parts.

  * •

$P$ denotes a conditional value distribution (Definition 2.17), independent of
the $\boldsymbol{B}\otimes L$.

  * •

$\boldsymbol{B}\otimes L=\\{B_{\sigma}\\}_{\sigma\in[n]\cup\\{L\\}}$ denotes
bid distributions. Again, the infimum bid
$\max(\mathrm{supp}(B_{\sigma}))=\gamma\in[0,\,+\infty)$ and the supremum bid
$\max(\mathrm{supp}(B_{\sigma}))\leq\lambda\in[\gamma,\,+\infty]$; with at
least one equality $\max(\mathrm{supp}(B_{\sigma}))=\lambda$. The pseudo
bidder $L$ differs from real bidders $\boldsymbol{B}$ in that:

    * –

Each real bidder $B_{i}$ for $i\in[n]$ competes with OTHER bidders
$\boldsymbol{B}_{-i}\otimes L$.

    * –

The pseudo bidder $L$ competes with ALL bidders $\boldsymbol{B}\otimes L$,
including him/herself $L$.

In a uniform way (cf. Definition 2.12), each bidder $\sigma\in[n]\cup\\{L\\}$
has the bid-to-value mapping
$\varphi_{\sigma}(b):=b+\big{(}\sum_{k\in[n]\setminus\\{\sigma\\}}\frac{B^{\prime}_{k}(b)}{B_{k}(b)}+\frac{L^{\prime}(b)}{L(b)}\big{)}^{-1}=b+\big{(}\frac{\mathcal{B}^{\prime}(b)}{\mathcal{B}(b)}-\frac{B^{\prime}_{\sigma}(b)}{B_{\sigma}(b)}\cdot\mathbbm{1}(\sigma\neq
L)\big{)}^{-1}$ over $b\in[\gamma,\,\lambda]$, where the first-order bid
distribution $\mathcal{B}(b):=\prod_{\sigma\in[n]\cup\\{L\\}}B_{\sigma}(b)$.

This pseudo instance is valid $(P,\,\boldsymbol{B}\otimes L)\in\mathbb{B}_{\sf
valid}$ when it satisfies • ‣ 3.1 and • ‣ 3.1.

  * •

monotonicity: The bid-to-value mappings
$\boldsymbol{\varphi}=\\{\varphi_{\sigma}\\}_{\sigma\in[n]\cup\\{L\\}}$ are
increasing over the bid support $b\in[\gamma,\,\lambda]$.

  * •

boundedness: The monopolist $B_{1}$’s value $v_{1}=s_{1}^{-1}(b_{1})$,
conditioned on the infimum bid $\\{b_{1}=\gamma\\}$, exactly follows the
distribution $P$; this induces the restriction
$\mathrm{supp}(P)\subseteq[\gamma,\,\varphi_{1}(\gamma)]$. Moreover, each
other bidder $\sigma\in[2:n]\cup\\{L\\}$, conditioned on the infimum bid
$\\{b_{\sigma}=\gamma\\}$, is truthful $v_{i}=s_{i}^{-1}(b_{i})=\gamma$.

######  Remark 7 (Pseudo instances).

The concept of pseudo instances greatly eases the presentation and similar
ideas also appear in the previous works [AHN+19, JLTX20, JLQ+19, JJLZ21].

Essentially, a pseudo instance $\boldsymbol{B}\otimes L$ can be viewed as the
limit of a sequence of real instances. I.e., the pseudo bidder $L$ can be
viewed as, in the limit $k\to+\infty$, a collection of low-impact bidders
$L_{1}(b)=\dots=L_{k}(b):=(L(b))^{1/k}$. All these low-impact bidders have the
common competing bid distribution
$\mathfrak{B}(b)=\prod_{i\in[n]}B_{i}(b)\cdot(L(b))^{1-1/k}$, so the highest
bid among them leads to the highest value and we just need to keep track of
the collective information $\prod_{j\in[k]}L_{j}=L(b)$.

On the other hand, in the limit $k\to+\infty$, the common competing bid
distribution $\mathfrak{B}(b)$ pointwise converges to the first-order bid
distribution $\mathcal{B}(b)=\prod_{i\in[n]}B_{i}(b)\cdot L(b)$. This accounts
for the pseudo mapping
$\varphi_{L}(b)=b+\mathcal{B}(b)/\mathcal{B}^{\prime}(b)$.

Because valid pseudo instances $(P,\,\boldsymbol{B}\otimes L)$ differ from the
valid real instances ONLY in the definition of the pseudo mapping
$\varphi_{L}(b)$, most results in Section 2 still hold. Especially, Lemma 3.2
formulates their Social Welfares (which restates Lemmas 2.20 and 2.21
basically).

######  Lemma 3.2 (Social Welfares).

For a valid pseudo instance $(P,\,\boldsymbol{B}\otimes L)\in\mathbb{B}_{\sf
valid}$, the expected auction/ optimal Social Welfares ${\sf
FPA}(P,\,\boldsymbol{B}\otimes L)$ and ${\sf OPT}(P,\,\boldsymbol{B}\otimes
L)$ are given by

$\displaystyle{\sf FPA}(P,\,\boldsymbol{B}\otimes L)\;$
$\displaystyle~{}=~{}\mathop{{\bf
E}\/}[P]\cdot\mathcal{B}(\gamma)~{}+~{}\sum_{\sigma\in[n]\cup\\{L\\}}\Big{(}\int_{\gamma}^{\lambda}\varphi_{\sigma}(b)\cdot\frac{B^{\prime}_{\sigma}(b)}{B_{\sigma}(b)}\cdot\mathcal{B}(b)\cdot\mathrm{d}b\Big{)},$
$\displaystyle{\sf OPT}(P,\,\boldsymbol{B}\otimes L)$
$\displaystyle~{}=~{}\gamma~{}+~{}\int_{\gamma}^{+\infty}\Big{(}1-P(v)\cdot\mathcal{V}(v)\Big{)}\cdot\mathrm{d}v,$

where the first-order bid distribution
$\mathcal{B}(b):=\prod_{\sigma\in[n]\cup\\{L\\}}B_{\sigma}(b)$ and the quasi
first-order value distribution
$\mathcal{V}(v):=\prod_{\sigma\in[n]\cup\\{L\\}}\mathop{{\bf
Pr}\/}_{b_{\sigma}\sim
B_{\sigma}}\big{[}\,(b_{\sigma}\leq\gamma)\vee(\varphi_{\sigma}(b_{\sigma})\leq
v)\,\big{]}$ can be reconstructed from $\boldsymbol{B}\otimes L$.

Lemma 3.3 shows that given a pseudo instance $(P,\,\boldsymbol{B}\otimes L)$,
the pseudo bidder $L$ always has a dominated bid-to-value mapping
$\varphi_{L}(b)\leq\varphi_{i}(b)$, compared with other real bidders
$i\in[n]$.

######  Lemma 3.3 (Bid-to-value mappings).

For a valid pseudo instance $(P,\,\boldsymbol{B}\otimes L)\in\mathbb{B}_{\sf
valid}$, the bid-to-value mappings
$\boldsymbol{\varphi}=\\{\varphi_{\sigma}\\}_{\sigma\in[n]\cup\\{L\\}}$
satisfy the following:

  1. 1.

$\min(\boldsymbol{\varphi}(b^{\otimes n+1}))=\varphi_{L}(b)>b$ for
$b\in(\gamma,\,\lambda]$. Further, $\min(\boldsymbol{\varphi}(\gamma^{\otimes
n+1}))=\varphi_{L}(\gamma)\geq\gamma$.

  2. 2.

$\sum_{i\in[n]}\frac{\varphi_{L}(b)-b}{\varphi_{i}(b)-b}\geq n-1$ for
$b\in(\lambda,\,\gamma]$.

###### Proof.

Item 1 is an immediate consequence of (Definition 3.1) the bid-to-value
mappings
$\varphi_{\sigma}(b)=b+\big{(}\frac{\mathcal{B}^{\prime}(b)}{\mathcal{B}(b)}-\frac{B^{\prime}_{\sigma}(b)}{B_{\sigma}(b)}\cdot\mathbbm{1}(\sigma\neq
L)\big{)}^{-1}$ for $\sigma\in[n]\cup\\{L\\}$. Particularly, in the proof of
Lemma 2.13 (Fact B), we already show that the pseudo mapping
$\varphi_{L}(b)>b$ for $b\in(\gamma,\,\lambda]$ and
$\varphi_{L}(\gamma)\geq\gamma$. Moreover, we have
$\sum_{i\in[n]}\big{(}\varphi_{i}(b)-b\big{)}^{-1}=n\cdot\frac{\mathcal{B}^{\prime}(b)}{\mathcal{B}(b)}-\sum_{i\in[n]}\frac{B^{\prime}_{i}(b)}{B_{i}(b)}\geq(n-1)\cdot\frac{\mathcal{B}^{\prime}(b)}{\mathcal{B}(b)}+\frac{L^{\prime}(b)}{L(b)}=(n-1)\cdot\big{(}\varphi_{L}(b)-b\big{)}^{-1}$
Rearranging this equation gives Item 2. ∎

Lemma 3.4 shows that the bid distributions $\boldsymbol{B}\otimes
L=\\{B_{i}\\}_{i\in[n]}\otimes L$ can be reconstructed from the bid-to-value
mappings
$\boldsymbol{\varphi}=\\{\varphi_{\sigma}\\}_{\sigma\in[n]\cup\\{L\\}}$. This
lemma is important in that many subsequent reductions will construct new bid
distributions $\widetilde{\boldsymbol{B}}\otimes\widetilde{L}$ in terms of the
mappings $\widetilde{\boldsymbol{\varphi}}$. Therefore, the correctness of
such construction reduces to checking Items 1 and 2 of Lemma 3.3 and
monotonicity of the mappings $\widetilde{\boldsymbol{\varphi}}$.

######  Lemma 3.4 (Bid distributions).

For $(n+1)$ functions
$\boldsymbol{\varphi}=\\{\varphi_{\sigma}\\}_{\sigma\in[n]\cup\\{L\\}}$ that
are increasing on $b\in[\gamma,\,\lambda]$ and satisfy Items 1 and 2 of Lemma
3.3, the functions $\boldsymbol{B}\otimes L$ given below are well-defined
$[\gamma,\,\lambda]$-supported bid distributions and their bid-to-value
mappings are exactly
$\boldsymbol{\varphi}=\\{\varphi_{\sigma}\\}_{\sigma\in[n]\cup\\{L\\}}$.

$\displaystyle B_{i}(b)$
$\displaystyle~{}\equiv~{}\exp\Big{(}-\int_{b}^{\lambda}\Big{(}\big{(}\varphi_{L}(b)-b\big{)}^{-1}-\big{(}\varphi_{i}(b)-b\big{)}^{-1}\Big{)}\cdot\mathrm{d}b\Big{)}\cdot\mathbbm{1}(b\geq\gamma),\qquad\qquad\forall
i\in[n].$ $\displaystyle L(b)$
$\displaystyle~{}\equiv~{}\exp\Big{(}-\int_{b}^{\lambda}\Big{(}\sum_{i\in[n]}\big{(}\varphi_{i}(b)-b\big{)}^{-1}-(n-1)\cdot\big{(}\varphi_{L}(b)-b\big{)}^{-1}\Big{)}\cdot\mathrm{d}b\Big{)}\cdot\mathbbm{1}(b\geq\gamma).$

###### Proof.

The construction of $\boldsymbol{B}\otimes L$ intrinsically ensures that
$B_{\sigma}(b)=0$ below the infimum bid $b<\gamma$ and $B_{\sigma}(\lambda)=1$
at the supremum bid $\lambda$, for $\sigma\in[n]\cup\\{L\\}$. Moreover, Items
1 and 2 of Lemma 3.3 together make each $B_{\sigma}(b)$ an increasing function
on $b\in[\gamma,\,\lambda]$, hence a well-defined
$[\gamma,\,\lambda]$-supported bid distribution. It remains to verify
$\varphi_{\sigma}(b)=b+\big{(}\sum_{k\in[n]\setminus\\{\sigma\\}}\frac{B^{\prime}_{k}(b)}{B_{k}(b)}+\frac{L^{\prime}(b)}{L(b)}\big{)}^{-1}$
over the bid support $b\in[\gamma,\,\lambda]$, for $\sigma\in[n]\cup\\{L\\}$,
namely the functions
$\boldsymbol{\varphi}=\\{\varphi_{\sigma}\\}_{\sigma\in[n]\cup\\{L\\}}$ are
exactly (Definition 3.1) the bid-to-value mappings stemmed from the
$\boldsymbol{B}\otimes L$. These identities for $\sigma\in[n]\cup\\{L\\}$ can
be easily seen via elementary algebra; we omit the details for brevity. Lemma
3.4 follows then. ∎

Lemma 3.5 suggests that any valid real instance $(P,\,\boldsymbol{B})$ can be
reinterpreted as a valid pseudo instance $(P,\,\boldsymbol{B}\otimes
L_{\gamma})$, by employing a specific pseudo bidder $L_{\gamma}$. As a
consequence (Corollary 3.6): Towards a lower bound on the Price of Anarchy in
First Price Auctions, we can consider valid pseudo instances instead. (Cf.
Corollary 2.23 for comparison).

######  Lemma 3.5 (Pseudo instances).

For a valid instance $(P,\,\boldsymbol{B})\in\mathbb{B}_{\sf valid}$, the
following hold:

  1. 1.

The pseudo bidder $L_{\gamma}(b)\equiv\mathbbm{1}(b\geq\gamma)$ induces a
valid pseudo instance $(P,\,\boldsymbol{B}\otimes
L_{\gamma})\in\mathbb{B}_{\sf valid}$.

  2. 2.

${\sf OPT}(P,\,\boldsymbol{B}\otimes L_{\gamma})={\sf
OPT}(P,\,\boldsymbol{B})$ and ${\sf FPA}(P,\,\boldsymbol{B}\otimes
L_{\gamma})={\sf FPA}(P,\,\boldsymbol{B})$.

###### Proof.

As mentioned in Remark 7, to see the validity $(P,\,\boldsymbol{B}\otimes
L_{\gamma})\in\mathbb{B}_{\sf valid}$, we only need to verify • ‣ 3.1 of
mappings
$\boldsymbol{\varphi}=\\{\varphi_{\sigma}\\}_{\sigma\in[n]\cup\\{L\\}}$ and •
‣ 3.1 of the conditional value $P$.

Item 1. We have $L_{\gamma}(b)=1$ and
$L^{\prime}_{\gamma}(b)\big{/}L_{\gamma}(b)=0$ for $b\geq\gamma$. Thus, each
real bidder $i\in[n]$ keeps the same mapping $\varphi_{i}(b)$ after including
the pseudo bidder $L_{\gamma}$ (Definitions 2.12 and 3.1), preserving • ‣ 3.1.
Also, the pseudo mapping can be written as
$\varphi_{L_{\gamma}}(b)=b+\mathcal{B}(b)\big{/}\mathcal{B}^{\prime}(b)$ for
$b\in[\gamma,\,\lambda]$, based on the first-order bid distribution
$\mathcal{B}(b)=\prod_{i\in[n]}B_{i}(b)\cdot
L_{\gamma}(b)=\prod_{i\in[n]}B_{i}(b)$. In the proof of Lemma 2.13 (Fact B),
we already verify • ‣ 3.1 of this mapping. Moreover, the unmodified
conditional value $P$ must preserve • ‣ 3.1.

Item 2. This can be easily inferred from (Lemmas 2.20 and 2.21 versus Lemma
3.2) the Social Welfare formulas for valid real versus pseudo instances; thus
we omit details for brevity. Roughly speaking, the point is that the pseudo
bidder $L_{\gamma}(b)=1$ for $b\geq\gamma$ has no effect. ∎

Due to the above lemma, we know that the PoA of pseudo instances is a lower
bound of the real PoA. On the other hand, we know that a pseudo instance can
be viewed as a limit of real instances. As a result, any PoA ratio obtained by
a pseudo instance can arbitrarily approximated by real instances. Thus, we
have the following corollary.

######  Corollary 3.6 (Lower bound).

Regarding First Price Auctions, the Price of Anarchy is

$\displaystyle{\sf PoA}~{}=~{}\inf\bigg{\\{}\,\frac{{\sf
FPA}(P,\,\boldsymbol{B}\otimes L)}{{\sf OPT}(P,\,\boldsymbol{B}\otimes
L)}\,\,\bigg{|}\,\bigg{.}\,(P,\,\boldsymbol{B}\otimes L)\in\mathbb{B}_{\sf
valid}~{}\text{\em and}~{}{\sf OPT}(P,\,\boldsymbol{B}\otimes
L)<+\infty\,\bigg{\\}}.$

###  3.2 Discretize: Towards (approximate) discrete pseudo instances

In this subsection, we introduce the concept of discretized pseudo instances
$(P,\,\boldsymbol{B}\otimes L)$; see Definitions 3.7 and LABEL:fig:discretize
for its formal definition and a visual demonstration.

######  Definition 3.7 (Discretized pseudo instances).

A valid pseudo instance $(P,\,\boldsymbol{B}\otimes L)$ from Definition 3.1 is
further called discretized when it satisfies • ‣ 3.7 and • ‣ 3.7.

  * •

finiteness: The supremum bid/value are bounded away from infinite
$\lambda\leq\max(\boldsymbol{\varphi}(\boldsymbol{\lambda}))<+\infty$.

  * •

piecewise constancy: Given some bounded integer $0\leq m<+\infty$ and some
$(m+1)$-piece partition of the bid support
$\boldsymbol{\Lambda}:=[\gamma=\lambda_{0},\,\lambda_{1})\cup[\lambda_{1},\,\lambda_{2})\cup\dots\cup[\lambda_{m},\,\lambda_{m+1}=\lambda]$,
each bid-to-value mapping $\varphi_{\sigma}(b)$ for $\sigma\in[n]\cup\\{L\\}$
is a piecewise constant function under this partition.

Notice that the partition $\boldsymbol{\Lambda}$ relies on the bid
distributions $\boldsymbol{B}\otimes L$, irrelevant to the monopolist
$B_{1}$’s conditional value $P$.

######  Remark 8 (Discretized pseudo instances).

The value distributions $V_{\sigma}(v)$ for $\sigma\in[n]\cup\\{L\\}$
reconstructed from a discretized pseudo instance $(P,\,\boldsymbol{B}\otimes
L)$ are almost discrete, except the conditional value $P$ of the monopolist
$B_{1}$ (which ranges between
$\mathrm{supp}(P)\subseteq[\gamma,\,\varphi_{1}(\gamma)]$ but is otherwise
arbitrary). Namely, each index $j\in[0:m]$ piece of a bid-to-value mapping
$\varphi_{\sigma}(b)$ induces a probability mass
$\big{(}B_{\sigma}(\lambda_{j+1})-B_{\sigma}(\lambda_{j})\big{)}$ of the value
distribution $V_{\sigma}(v)$.

Lemma 3.8 shows that the PoA bound of a (generic) valid pseudo instance
$(P,\,\boldsymbol{B}\otimes L)$ can be approximated arbitrarily close by a
discretized pseudo instance
$(\widetilde{P},\,\widetilde{\boldsymbol{B}}\otimes\widetilde{L})$.

######  Intuition.

For the Price of Anarchy problem, we only consider (Corollary 3.6) the pseudo
instances that have bounded Social Welfares ${\sf
FPA}(P,\,\boldsymbol{B}\otimes L)\leq{\sf OPT}(P,\,\boldsymbol{B}\otimes
L)<+\infty$. In a sense of Lebesgue integrability, we can carefully
truncate121212We will use a special truncation scheme. The usual truncation
scheme often induces probability masses at the truncation threshold, but we
require that the bid CDF’s $\boldsymbol{B}\otimes L$ are continuous over the
bid support $b\in[\gamma,\,\lambda]$. the bid distributions
$\boldsymbol{B}\otimes L$ to meet the • ‣ 3.7 condition, by which the
auction/optimal Social Welfares change by negligible amounts.

Then, we replace the bid-to-value mappings
$\boldsymbol{\varphi}=\\{\varphi_{\sigma}\\}_{\sigma\in[n]\cup\\{L\\}}$ by
their interpolation functions
$\widetilde{\boldsymbol{\varphi}}=\\{\widetilde{\varphi}_{\sigma}\\}_{\sigma\in[n]\cup\\{L\\}}$
(• ‣ 3.7). The mappings $\boldsymbol{\varphi}$ decide the bid distributions
$\boldsymbol{B}\otimes L$ (Lemma 3.4) and the auction/optimal Social Welfares
(Lemma 3.2) in terms of integral formulas, which are insensitive to the
(local) changes of the interpolation functions