[name=Theorem, sibling=theorem]rThm [name=Lemma, sibling=theorem]rLem
[name=Observation, sibling=theorem]rObs [name=Corollary, sibling=theorem]rCor
[name=Proposition, sibling=theorem]rPro ebblue czred vgpurple xtcyan

# Online Mechanism Design with Predictions††thanks: All four authors were
supported by NSF grant CCF-2210502. Eric Balkanski was also supported by NSF
grant IIS-2147361.

Eric Balkanski<EMAIL_ADDRESS>Columbia University, IEOR  Vasilis
Gkatzelis<EMAIL_ADDRESS>Drexel University, Computer Science  Xizhi Tan
<EMAIL_ADDRESS>Drexel University, Computer Science  Cherlin Zhu
<EMAIL_ADDRESS>Columbia University, IEOR

###### Abstract

Aiming to overcome some of the limitations of worst-case analysis, the
recently proposed framework of “algorithms with predictions” allows algorithms
to be augmented with a (possibly erroneous) machine-learned prediction that
they can use as a guide. In this framework, the goal is to obtain improved
guarantees when the prediction is correct, which is called _consistency_ ,
while simultaneously guaranteeing some worst-case bounds even when the
prediction is arbitrarily wrong, which is called _robustness_. The vast
majority of the work on this framework has focused on a refined analysis of
online algorithms augmented with predictions regarding the future input. A
subsequent line of work has also successfully adapted this framework to
mechanism design, where the prediction is regarding the private information of
strategic agents. In this paper, we initiate the study of online mechanism
design with predictions, which combines the challenges of online algorithms
with predictions and mechanism design with predictions.

We consider the well-studied problem of designing a revenue-maximizing auction
to sell a single item to strategic bidders who arrive and depart over time,
each with an unknown, private, value for the item. We study the learning-
augmented version of this problem where the auction designer is given a
prediction regarding the maximum value over all agents. Our main result is a
strategyproof mechanism whose revenue guarantees are $\alpha$-consistent with
respect to the highest value and $(1-\alpha^{2})/4$-robust with respect to the
second-highest value, for $\alpha\in[0,1]$. We show that this tradeoff is
optimal within a broad and natural family of auctions, meaning that any
$\alpha$-consistent mechanism in that family has robustness at most
$(1-\alpha^{2})/4$. Finally, we extend our mechanism to also obtain expected
revenue that is proportional to the prediction quality.

##  1 Introduction

One of the well-established shortcomings of worst-case analysis is that it
often leads to overly pessimistic conclusions. On the other hand, any non-
trivial performance guarantee that can be established through worst-case
analysis is very robust, since it holds no matter what the input may be. In an
attempt to overcome the limitations of worst-case analysis without
compromising its robustness, the recently proposed framework of “algorithms
with predictions” allows algorithms to be augmented with a machine-learned
prediction that they can use as a guide [28]. Crucially, this prediction may
be highly inaccurate, so depending too heavily on it can lead to very poor
performance in the worst case. Therefore, the goal in this framework is to use
such a prediction so that a strong performance can be guaranteed whenever the
prediction is accurate (known as the _consistency_ guarantee), while
simultaneously maintaining non-trivial worst-case guarantees even if the
prediction is inaccurate (known as the _robustness_ guarantee).

During the last five years since this framework was introduced, a surge of
work has utilized it toward a refined analysis of algorithms, data structures,
and mechanisms (see [25] for a frequently updated list of papers in this
rapidly growing literature). The vast majority of this work has focused on the
design and analysis of online algorithms, i.e., algorithms that need to
process their input piece-by-piece and make irrevocable decisions without
knowing the whole input. Learning-augmented online algorithms are enhanced
with a prediction regarding the future input, which they can potentially use
to make more informed decisions, while carefully managing the risk of being
misguided by it. An even more recent line of work has successfully adapted
this framework for the design and analysis of mechanisms interacting with
strategic bidders [1, 34]. One of the canonical problems in mechanism design
is the design of auctions for selling goods to a group of strategic bidders,
aiming to maximize the revenue. The main obstacle in achieving this goal is
the fact that the amount that each bidder is willing to pay is private
information that the designer needs to carefully elicit. Learning-augmented
mechanisms are therefore enhanced with predictions regarding the value of this
private information, which can potentially overcome these obstacles.

In this work, we initiate the study of online mechanism design with
predictions, bringing together the two lines of work on online algorithms with
predictions and mechanism design with predictions. Specifically, we consider
the problem of selling goods to strategic bidders that arrive and depart over
time. This problem combines the challenges of both lines of work since the
designer needs to carefully elicit the unknown, private, value of each bidder,
while also not knowing (and being unable to elicit) the values of the bidders
who have not yet arrived. In fact, designing an auction for such dynamic
settings can be more demanding because, apart from the combined information
limitations that the designer faces, the bidders may not only strategically
misreport their value for the good(s) beings sold, but they may also
strategically misrepresent their arrival and departure times.

The study of online mechanism design (without predictions) has previously
received a lot of attention, given the many important applications that
involve dynamic settings with bidders that arrive and depart over time [32].
For example the sale of airplane and theater seats or the sale of cars usually
takes place over a period of time, during which interested buyers join the
market and depart from it. As this happens, the seller may gradually adjust
the prices of the goods being sold aiming to maximize the revenue. These
adjustments can be a function of the demand that the seller observes over
time, but it is quite natural to assume that the designer may also have access
to some prediction regarding this demand, e.g., using historical data. Our
goal in this paper is to design online auctions enhanced with such a
prediction and to evaluate the extent to which they can yield strong
performance guarantees in terms of consistency and robustness.

###  1.1 Our results

Our main goal is to evaluate the potential impact of the learning-augmented
model on the performance of auctions in dynamic environments. To achieve this
goal, we revisit the well-studied model of online mechanism design, where the
bidders arrive and depart over time [32, 20]. This model poses several
realistic and non-trivial obstacles for the auction designer: 1) the bidders
can lie about their value for the good(s) being sold (the standard obstacle in
mechanism design), 2) during the execution of the auction, the auctioneer has
no information regarding bidders who have not yet arrived (the standard
obstacle in online problems), and 3) the bidders can also lie regarding their
arrival and departure times (an obstacle that is specific to the online
mechanism design setting).

Within this model, we focus on the problem of selling a single item aiming to
maximize revenue. Each bidder $i$ has a value $v_{i}$ for the item being sold
and this value is the largest amount she would be willing to pay for it. In
the absence of any predictions, the best revenue that one can guarantee, even
in an offline setting, is equal to the second-highest value over all
bidders.111This can be achieved by the classic Vickrey (second-price) auction.
Using this as a benchmark, prior work proposed an online single-item auction
that guarantees revenue at least $1/4$ of the second-highest value [20].
Aiming to refine this result and achieve stronger guarantees, we adopt the
learning-augmented framework and consider the design of online auctions that
are enhanced with a (possibly very inaccurate) prediction regarding the
highest value over all bidders. The goal is to guarantee more revenue whenever
the prediction is accurate (the consistency guarantee), while also achieving
some non-trivial revenue guarantee even if the prediction is highly inaccurate
(the robustness guarantee, which is equivalent to the worst-case guarantee
studied in prior work).

Targeting a more ambitious benchmark, we use the highest value over all
bidders (the first-best revenue) as a benchmark for our consistency guarantee,
while maintaining the second-highest value (the second-best revenue) as the
benchmark for robustness (as in prior work).

#### The Three-Phase learning-augmented online auction.

Our first main result is the Three-Phase auction: a learning-augmented online
auction parameterized by some value $\alpha\in[0,1]$, which takes place in
three phases. During the first phase, the auction observes the values of the
first $\lceil\frac{1-\alpha}{2}n\rceil$ departing bidders in order to “learn”
an estimate regarding what an appropriate price may be. In the second phase,
the auction “tests the prediction” by giving each active bidder the
opportunity to clinch the item if their value is at least as high as the
prediction. After $\lfloor\alpha n\rfloor$ more bidders have departed, if the
item remains unsold the auction enters the third and last phase. During this
phase, any active bidder is given the opportunity to clinch the item at a
price equal to the maximum value observed during the first two phases. This
learning-augmented online auction achieves the following trade-off between
consistency and robustness.

######  Theorem.

The Three-Phase learning-augmented online auction is deterministic,
strategyproof, and for any $\alpha\in[0,1]$ such that $\alpha
n\in\mathbb{N}\text{ and }\frac{1-\alpha}{2}n\in\mathbb{N}$ its revenue
guarantees $\alpha$-consistency with respect to the first-best revenue
benchmark and $(1-\alpha^{2})/4$-robustness with respect to the second-best
revenue benchmark.

Note that, although we focus on revenue maximization throughout this paper, as
a corollary of our analysis, we also obtain a social welfare guarantee that is
also $\alpha$-consistent and $(1-\alpha^{2})/4$-robust, where consistency and
robustness are both with respect to the highest value.

Figure 1: The robustness-consistency trade-off achieved by the Three-Phase
auction and the trade-off achieved by convex combinations of the auction that
optimizes consistency by completely trusting the predictions and the auction
that optimizes robustness by ignoring the predictions.

If we let $\alpha=0$ our auction retrieves the robustness guarantee of $1/4$
that was achieved in prior work, but provides no consistency guarantees. On
the other extreme, if we let $\alpha=1$ then we get a perfect consistency of
$1$ (since our auction reduces to a posted price auction that offers a price
equal to the prediction to every bidder, if the prediction is correct it
extracts the first-best revenue) but without any robustness guarantees. Figure
1 exhibits the convex combination of these two extreme solutions, as well as
the improved tradeoff achieved by the Three-Phase auction.

#### A tight impossibility result.

Our other main result is an impossibility result proving the optimality of our
Three-Phase auction within a broad and natural family of learning-augmented
online auctions called PAF auctions (Prediction or Any-so-Far auctions).
Having no information regarding the bidders’ values beyond the observed values
of previous bidders and the prediction, online auctions are limited in terms
of what is a “reasonable” price for them to offer. The PAF class contains all
auctions such that the prices offered are equal to any value of previous
bidders or the prediction (see Definition 10). Although one could technically
define auctions outside this class (e.g., auctions that just post an arbitrary
price outside this set), PAF captures the Three-Phase auction, existing
auctions from previous work [20, 14].

######  Theorem.

For any $\alpha\in[0,1]$, there is no PAF auction that is $\alpha$-consistent
with respect to the first-best revenue benchmark and
$(1-\alpha^{2})/4+\omega(\frac{1}{n})$-robust with respect to the second-best
revenue benchmark.

Note that optimality results for secretary and online auction problems are
often obtained through LP duality arguments [15, 14, 2]. The LP formulations
for these problems rely on strong history-independence properties. In our
problem, these history-independence properties do not hold because, for
example, the probability of a bidder accepting a price equal to the prediction
crucially depends on how many bidders have previously rejected an offered
price equal to the prediction. Such dependencies make it challenging to give
an LP formulation of our problem. Instead, we use an interchange argument to
show that, for any $\alpha\in[0,1]$ there exists an $\alpha$-consistent PMF
auction that achieves an optimal robustness and satisfies a three-phase
structure identical to our auction. We then optimize for the optimal time
thresholds for auctions that satisfy this three-phase structure.

###  1.2 Related work

#### Online mechanism design.

Due to the many applications with strategic agents who arrive in an online
fashion, online mechanism design is an important subfield of mechanism design
(see Chapter 16 by Parkes [32] of the Algorithmic Game Theory textbook [31]
for an overview). The problem of online auctions with bidders who arrive
dynamically and might misreport their arrival and departure times was
introduced by Hajiaghayi et al. [20]. For revenue maximization, their main
results are a $1/4$-competitive strategyproof mechanism and a $2/3$
impossibility result in the single item setting, and a constant factor
competitive strategyproof mechanism for the $k$-item setting. Since then,
different variations of the problem have been considered. Buchbinder et al.
[14] examine agents with private arrival times and values, along with an
unrestricted strategy space, and propose a strategyproof auction that achieves
a competitive ratio of $3/16$ in terms of revenue. Krysta and Telelis [24]
improve the $k$-item competitive ratio of [20] to $1/26e$ for the special case
where the active times of bidders do not overlap. Additional related models
for online mechanism design include unlimited supply, digital goods [9, 11,
10, 23]; two-sided auctions with both buyers and sellers online [13, 12]; and
interdependent value environments [16].

#### Online algorithms with predictions.

The line of work on algorithms with predictions, also called learning-
augmented algorithms, is an exciting emerging literature (see [29] for a
survey of early contributions and [25] for an updated list of papers in this
field). Numerous classic online algorithm design problems have been revisited,
including online paging [26], scheduling [33], optimization problems involving
covering [7] and knapsack constraints [21], as well as Nash social welfare
maximization [8], the secretary problem [2, 17, 18], and a range of graph-
related challenges [3]. Among these previous works, the most closely related
to our setting is by Antoniadis et al. [2], who consider the value-maximizing
secretary problem augmented with a prediction regarding the maximum value of
the agents. In fact, their proposed learning-augmented algorithm follows a
three-phase structure which is similar to the one used in our auction.
However, our setting and our proposed solution, differ in several significant
ways. The most significant one is the fact that just focusing on the online
aspect of the problem, we need to deal with the important additional obstacle
that the agents are strategic and can misreport their value, as well as their
arrival and departure time. Furthermore, our goal is to maximize revenue
whereas the goal in the secretary problem is to choose the agent with maximum
value. Finally, our setting does not assume that each agent departs before the
arrival of the next one, like the secretary setting does; this makes the
problem of designing strategyproof mechanisms significantly more delicate. To
achieve strategyproofness, our auction must very carefully determine the time
at which the item is allocated, the bidder who receives the item, and the
item’s price in order to handle bidders who might be active during multiple
phases, which is the main technical (and novel) challenge in our setting.

#### Mechanism design with predictions.

Mechanism design with predictions regarding the private information of bidders
is an even more recent line of work that was initiated by [1] and [34]. It
includes strategic facility location [1, 34, 22], price of anarchy of cost-
sharing protocols [19], strategic scheduling [34, 6], auctions [27, 34], and
bicriteria (social welfare and revenue) mechanism design [4]. We refer to [5]
for a reading list of this line of work.

##  2 Preliminaries

We consider the problem of designing an auction to sell a single item to a set
$N=\\{1,2,\dots,n\\}$ of $n$ bidders who arrive and depart over time. Each
bidder $i$ arrives at some time $a_{i}$, departs at some time $d_{i}\geq
a_{i}$, and has value $v_{i}$ for the item being sold. We refer to the
interval $[a_{i},d_{i}]$ as the _active time_ for bidder $i$. For simplicity,
we assume that the bidders are indexed based on their order of departure
(i.e., bidder $i$ is the $i$-th bidder to depart). We also let $\pi$ be an
arbitrary total order over the set of bidders, which we use for tie-breaking,
and let $i\succ j$ denote the fact that $i$ is ranked before bidder $j$
according to $\pi$. Our objective is to maximize the revenue from the sale.

The main obstacle is that all the relevant information of each bidder $i$,
i.e., their “type” $\theta_{i}=(a_{i},d_{i},v_{i})$, is private information
that is unknown to the auction designer, so the auction needs to elicit it
from each bidder. However, the bidders can misreport their types and the
auction needs to be designed to ensure that they cannot benefit by doing so.
Specifically, apart from misreporting her value $v_{i}$ for the item (which is
the standard type of manipulation considered in mechanism design), a bidder
can also misreport her arrival and departure times: adopting the original
model introduced by Hajiaghayi et al. [20], we assume that each bidder $i$ can
delay the announcement of her arrival (essentially reporting a delayed arrival
time $\hat{a}_{i}>a_{i}$), and she can report a false departure time
$\hat{d}_{i}$ (either earlier or later than her true departure time, $d_{i}$).
Upon arrival, each bidder $i$ declares a type $\hat{\theta}_{i}$ (potentially
different than $\theta_{i}$) and the auction needs to determine who the winner
is (i.e., which bidder will be allocated the item), at what time $t$ the item
should be allocated to the winner, as well as the amount $p$ that the winner
should pay.

Apart from the information limitations that the auction faces due to the
private nature of the bidders’ types, the auction also needs to be implemented
in an _online_ fashion. This means that if it decides to allocate the item at
some time $t$, then this decision is irrevocable, and both this allocation
decision and the payment amount requested from the winner can depend only on
information regarding bidders with arrival time $a_{i}\leq t$. In other words,
the allocation and payment cannot in any way depend on the types of bidders
that have not yet arrived.

If the auction allocates the item to some bidder $i^{*}$ at some time $t$ for
a price of $p$, then this bidder’s utility is equal to $v_{i^{*}}-p$, as long
as $t\in[a_{i^{*}},d_{i^{*}}]$, i.e., as long as $i^{*}$ is active at time
$t$. Otherwise, if $i^{*}$ is allocated the item outside her (real) active
time, then she receives no value from it, and her utility is $-p$. All other
bidders receive no item and contribute no payment, so their utility is $0$. A
auction is _strategyproof_ if for every bidder $i$, truthfully reporting her
type is a dominant strategy. This means that no matter what types
$\hat{\Theta}_{-i}=(\hat{\theta}_{1},\dots,\hat{\theta}_{i-1},\hat{\theta}_{i+1},\dots,\hat{\theta}_{n})$
the other bidders report, the utility of bidder $i$ is maximized if she
reports her true type, $\theta_{i}$. To emphasize the added difficulty for
achieving strategyproofness in online auctions, relative to static ones, prior
work often distinguishes between _value-strategyproofness_ , which ensures
that bidders will not want to misreport their value, and _time-
strategyproofness_ , which is the additional requirement to ensure that
bidders cannot benefit by misrepresenting their arrival or departure times
either.

To evaluate the performance of online auctions with respect to the revenue
they extract, prior work focused on a model where a set
$I=\\{[a_{1},d_{1}],[a_{2},d_{2}],...,[a_{n},d_{n}]\\}$ of $n$ arrival-
departure intervals and a set $V$ of $n$ values are generated adversarially,
and the values of $V$ are then matched to arrival-departure intervals from $I$
uniformly at random. Note that, if the intervals are all non-overlapping, this
reduces to the classic _random ordering_ model, where the values of the
bidders are determined adversarially and the order of their arrival is random.
Therefore, our setting generalizes the classic setting of the “secretary
problem”. We let $\mu(V,I)$ denote the random matching of values to intervals
and $\operatorname{\mathbb{E}}_{\Theta\sim\mu(V,I)}(\texttt{Rev}(M(\Theta)))$
denote the _expected_ revenue of an auction $M$ with respect to this random
matching. Also, let $v_{(1)}$ and $v_{(2)}$ denote the highest and second-
highest values in $V$, which are important benchmarks since the former is the
highest feasible revenue (no bidder would pay more than that) and the latter
is the “offline Vickrey” benchmark (this corressponds to the amount of revenue
that is actually achievable via the classic Vickrey auction in offline
settings).

In this work we adopt the learning-augmented framework and study online
auctions that are also equipped with a (potentially very inaccurate)
prediction $\tilde{v}_{(1)}$ regarding the highest value, $v_{(1)}$, in $V$.
We denote the expected revenue of a auction, $M$, as
$\operatorname{\mathbb{E}}_{\Theta\sim\mu(V,I)}(\texttt{Rev}(M(\Theta,\tilde{v}_{(1)})))$
and we evaluate the performance of $M$ using its _consistency_ and
_robustness_. Consistency refers to the competitive ratio of the expected
revenue achieved by the algorithm when the prediction it is provided with is
accurate, i.e., whenever $\tilde{v}_{(1)}=v_{(1)}$. The benchmark we use for
consistency is the highest value in $V$, often referred to as the _first-best_
revenue. Formally:

$\text{consistency}(M)=\min_{V,I}\frac{\operatorname{\mathbb{E}}_{\Theta\sim\mu(V,I)}\left(\texttt{Rev}\left(M\left(\Theta,v_{(1)}\right)\right)\right)}{v_{(1)}}.$

Robustness refers to the competitive ratio of the expected revenue given an
adversarially chosen, inaccurate, prediction. The benchmark we use for
robustness is the best revenue achievable via any (offline) strategyproof
auction, i.e., the second highest value $v_{(2)}$, often referred to as the
_second-best_ revenue. Formally:

$\text{robustness}(M)=\min_{V,I,\tilde{v}_{(1)}}\frac{\operatorname{\mathbb{E}}_{\Theta\sim\mu(V,I)}\left(\texttt{Rev}\left(M\left(\Theta,\tilde{v}_{(1)}\right)\right)\right)}{v_{(2)}}.$

##  3 The Three-Phase Auction

We propose the Three-Phase auction, which is parameterized by a value
$\alpha\in[0,1]$, with greater values corresponding to higher confidence in
the accuracy of the prediction. Our main result in this section shows that for
any choice of $\alpha$ this auction achieves $\alpha$-consistency and
$(1-\alpha^{2})/4$-robustness, while simultaneously guaranteeing both value-
strategyproofness and time-strategyproofness.

The Three-Phase auction considers the bidders based on the order of their
departure (i.e., the order of their indices) and comprises three separate
phases.

  1. 1.

During the first phase, the auction observes the values of the first
$\lceil\frac{1-\alpha}{2}n\rceil$ bidders to depart (without allocating the
item to any of them), aiming to “learn” an estimate regarding what a
reasonable price for the item may be. If, during this first phase, the auction
observes a value that exceeds the predicted maximum, $\tilde{v}_{(1)}$
(implying that the prediction is inaccurate), then, after the first phase is
complete, the auction essentially skips the second phase and moves directly
onto the third phase. If, on the other hand, the first phase does not prove
the prediction to be inaccurate, then the auction proceeds to the second
phase.

  2. 2.

During the second phase, the auction “tests” the prediction. Specifically,
during this phase (which terminates after $\lfloor\alpha n\rfloor$ more
bidders have departed) it asks all active bidders whether they would be
willing to pay a price equal to the prediction. If any active bidder is
willing to pay this price, then they secure the item and they are guaranteed
to pay a price no more than that. The exact payment of bidders who secure the
item during the second phase, however, may need to be lower than that to
guarantee strategyproofnes; we discuss this important subtlety later on.
Finally, if none of the $\lfloor\alpha n\rfloor$ bidders is willing to pay a
price equal to the prediction during the second phase, then the auction enters
its third phase.

  3. 3.

During the third phase, the auction offers a take-it-or-leave-it price equal
to the highest value observed over all the bidders that have previously
departed, and any active bidder can claim the item at that price.

Before going into more detail regarding each of the phases, we note that the
auction has a simple description for the special case where no two bidders
have overlap with respect to their active intervals (i.e., there is just one
active bidder at a time). In this case, the auction is a posted price
mechanism that posts price $\infty$ to the first
$\lceil\frac{1-\alpha}{2}n\rceil$ bidders, then posts price
$\max\\{v_{\max},\tilde{v}_{(1)}\\}$ to the next $\lfloor\alpha n\rfloor$
bidders and, finally, if the item remains unsold, it posts price $v_{\max}$ to
the remaining bidders, where $v_{\max}$ is the maximum value of bidders who
have previously departed. We note that the allocation rule induced by these
posted prices is a generalization of the threshold-based algorithm for the
classic secretary problem.

The main challenge, and the main technical portion of our auction, is to
handle the cases where there is an overlap between bidders. The time at which
the item is allocated, the bidder who receives the item, and the item’s price
must all be carefully designed to handle bidders who might be active during
multiple phases (in particular the second and third phases) and are competing
against other bidders. Irrespective of the stage of the auction where the
winner $i^{*}$ is determined, the item is allocated to $i^{*}$ at the time of
her (reported) departure, $d_{i^{*}}$, to guarantee time-strategyproofness. If
the winner is determined during the third phase, then her final price is the
take-it-or-leave-it price that they accepted during this phase. If, on the
other hand, the winner is determined during the second phase, the final price
needs to be carefully determined in order to guarantee the strategyproofness
of the auction. Specifically, if the winner remains active after the
transition into the third phase and no other bidder would have claimed the
item during the second phase, then the Three-Phase auction may need to reduce
the winner’s payment to be equal to the take-it-or-leave-it price that would
have been offered during the third phase if we were to remove $i^{*}$ and
simulate the outcome of the auction without them.

For clarity, we formally present the allocation and the payment rule of the
auction separately:

  * •

Process 1 is the execution of the allocation rule, i.e., it determines who
should receive the item. This process maintains a value $v_{\max}$,
corresponding to the maximum value observed among the bidders that have
departed so far, and a threshold value $\tau$. If any active bidder has value
at least $\tau$, then they can secure the item (tie-breaking using $\pi$ if
there are multiple such active bidders). The threshold $\tau$ is $\infty$
during the first phase, then $\max\\{v_{\max},\tilde{v}_{(1)}\\}$ during the
second phase, and finally $v_{\max}$ during the third phase. This process
returns the winner $i^{*}$, if any, and the threshold $\tau$ at which $i^{*}$
secured the item. Furthermore, to make the formal definition of the payment
rule easier, we also let this process return a Boolean variable, “active-
winner,” which is true only if $i^{*}$ secured the item right after the
transition between two phases. Specifically, this Boolean variable is set to
true if the item was secured after a departure of an agent rather than an
arrival of one, which implies that the departure caused the transition from
one phase to another, leading to a drop in the threshold value, $\tau$, and
the winner was already active.

  * •

Process 2 is the execution of the payment rule, i.e., it determines how much
the winner, if any, should pay for the item. The price is initially set to be
equal to the threshold $\tau$ at which the item was secured and the final
price will be no more than that. However, under some circumstances, the price
is reduced to guarantee strategyproofness. Specifically, if the winner secured
the item during the second phase and remains active during the third phase,
they may receive a lower price. In this case, the price is determined by
simulating the allocation process without the winning bidder, $i^{*}$. If the
new winner $i^{\prime}$, in the absence of $i^{*}$, either i) is not active
during the transition into the third phase or ii) loses to $i^{*}$ in tie-
breaking, then the price $p$ is lowered to the threshold $\tau^{\prime}$ at
which $i^{\prime}$ would have secured the item. Intuitively, if neither of
these two conditions hold and we did not offer $i^{*}$ the reduced price, then
$i^{*}$ could report a value of $\tau^{\prime}$ instead of her true value and
secure the item at that lower price right after the transition into the third
phase.

Input : types $\Theta$ of the $n$ bidders, consistency parameter
$\alpha\in[0,1]$, prediction $\tilde{v}_{(1)}\geq 0$

$A\leftarrow\emptyset$

// the set of active bidders

$L\leftarrow\emptyset$

// the set of bidders who have departed

$v_{\max}\leftarrow 0$

// the maximum value observed so far

1 $\tau\leftarrow\infty$

2 $i^{*}\leftarrow 0$

3 active-winner $\leftarrow$ false

4 while $L\neq N$ do

5 if some bidder $i$ arrives (tie-break using $\pi$) then

6 $A\leftarrow A\cup\\{i\\}$

7 if $v_{i}\geq\tau$ then

8 $i^{*}\leftarrow i$ and then break from while-loop

9

10 else if some bidder $i$ departs (tie-break using $\pi$) then

11 $A\leftarrow A\setminus\\{i\\}$ and $L\leftarrow L\cup\\{i\\}$

12 $v_{\max}\leftarrow\max\\{v_{\max},v_{i}\\}$

// threshold update if we just entered the second phase

13 if $|L|=\lceil\frac{1-\alpha}{2}n\rceil$ then

14 $\tau\leftarrow\max\\{v_{\max},\tilde{v}_{(1)}\\}$

15

// threshold update if we just entered the third phase

16 else if $|L|=\lfloor\frac{1+\alpha}{2}n\rfloor$ then

17 $\tau\leftarrow v_{\max}$

18

// check for potential winner among active bidders

19 if there exists $i\in A$ such that $v_{i}\geq\tau$ then

20 active-winner $\leftarrow$ true

21 $i^{*}\leftarrow i$ (tie-break using $\pi$ if needed in choosing $i$) and
then break from while-loop

22

23

24

return $i^{*}$, $\tau$, active-winner

Process 1 Alloc: the allocation rule of the Three-Phase auction

Input : the output of the allocation rule: $i^{*}$, $\tau$, active-winner

$p\leftarrow\tau$

// initialize the price to $\tau$, the threshold at which $i^{*}$ claimed the
item

// If the winner is determined in second phase and remains active in third
phase

1 if $\tau=\tilde{v}_{(1)}$ and $i^{*}>\lfloor\frac{1+\alpha}{2}n\rfloor$ then

$i^{\prime},\tau^{\prime},\text{active-
winner}^{\prime}\leftarrow\textsc{Alloc}(n-1,\Theta_{-i^{*}},\alpha,\tilde{v}_{(1)})$

// simulate allocation without $i^{*}$

// If $i^{\prime}$ is inactive when entering third phase or loses in tie-
breaking to $i^{*}$

2 if $\text{active-winner}^{\prime}=$ false or $i^{*}\succ i^{\prime}$ then

$p\leftarrow\tau^{\prime}$

// update the price to $\tau^{\prime}\leq\tau$

3

4

5

return $p$

Process 2 the payment rule of the Three-Phase auction

######  Observation 1.

The Three-Phase auction can be implemented in an online fashion.

###### Proof.

It is easy to verify that the allocation rule is online implementable, since
the auction maintains a threshold $\tau$ at any point and decides the winner
when some active bidder’s value is above the threshold; this requires no
future information. We now argue that the payment rule is online implementable
as well. Crucially, note that the winner is allocated the item at the time of
their departure, so all we need to argue is that the price that they need to
pay can be determined at that point. To verify this fact, note that if $i^{*}$
is not active during the transition from the second phase to the third phase,
then her price is just $\tau$. If, on the other hand, $i^{*}$ is active during
that transition, then the auction can also check the value of any other bidder
that is also active up to that transition to determine
$i^{\prime},\tau^{\prime}$ and active-winner′, without needing to simulate any
portion of the allocation rule beyond the departure of $i^{*}$. ∎

Our main result in this section shows that the Three-Phase not only guarantees
value- and time-strategyproofness, but it also achieve a non-trivial tradeoff
between robustness and consistency.

######  Theorem 2.

Three-Phase is a value-strategyproof and time-strategyproof online auction
that, given any parameter $\alpha\in W_{n}$, simultaneously guarantees
$\alpha$-consistency and $\frac{1-\alpha^{2}}{4}$-robustness.

In Section 3.1, we prove the consistency and robustness guarantees achieved by
our auction. In Section 3.2, we show that it is strategyproof. Finally, in
Section 3.3, we give an extension of our auction that achieves revenue
guarantees as a function of the prediction quality. For presentation purposes
we use $i_{1}$ to denote $\frac{1-\alpha}{2}n$ and $i_{2}$ to denote
$\frac{1+\alpha}{2}n$ in the following analysis.

###  3.1 Revenue Guarantees

In this section we analyze the performance of our auction in terms of
consistency and robustness. We focus on the values of $\alpha$ in the set
$W_{n}=\\{\alpha\in[0,1]:\alpha n\in\mathbb{N}\text{ and
}\frac{1-\alpha}{2}n\in\mathbb{N}\\}$ which make $\alpha n$ and
$\frac{1-\alpha}{2}n$ (the number of bidder departures in the first two
phases) are integral.

######  Lemma 3.

For any $\alpha\in W_{n}$, Three-Phase is $\alpha$-consistent.

###### Proof.

Assume that the prediction is correct, i.e., $\tilde{v}_{(1)}=v_{(1)}$. First,
observe that $\tilde{v}_{(1)}\geq v_{i}$ for all $i\in[n]$, so
$\tau=\tilde{v}_{(1)}=v_{(1)}$ during Phase 2, and no one would be above the
threshold besides the highest value bidder. Additionally, note that no bidder
is allocated the item in the first phase. Then the auction would be able to
extract revenue $v_{(1)}$ if the highest value bidder is allocated the item
during Phase 2 and pays the price $v_{(1)}$. Let $i^{*}$ be the bidder with
the highest value; it is sufficient to guarantee the aforementioned outcome if
the departure time is between the $i_{1}$-th departure and the $i_{2}$-th
departure, i.e., $i^{*}\in[i_{1}+1,i_{2}]$, which, based on our random-
ordering assumption, occurs with a probability of
$\frac{i_{2}-i_{1}}{n}=\alpha$. ∎

######  Lemma 4.

For any $\alpha\in W_{n}$, Three-Phase is $\frac{(1-\alpha^{2})}{4}$-robust.

###### Proof.

Recall that robustness is measured relative to $v_{(2)}$. We now consider the
cases where we under-predict and over-predict separately.

Case one: $\tilde{v}_{(1)}>v_{(1)}$. Since $\tau=\tilde{v}_{(1)}>v_{i}$ for
any bidder $i$, we have that bidders can only be above the threshold in phase
3. In this case, by the payment rule, it is sufficient to extract $v_{(2)}$ if
$\tau=v_{(2)}$, which requires the second highest bidder to be amongst the
first $i_{2}$ bidders to depart and bidders with the highest value are amongst
the last $n-i_{2}$ to depart. Then with probability
$\frac{i_{2}}{n}\frac{n-i_{2}}{n-1}=\frac{1-\alpha^{2}}{4}+O(\frac{1}{n})$,
revenue $v_{(2)}$ is extracted.

Case two: $\tilde{v}_{(1)}\leq v_{(1)}$. Observe that in the under-predicted
case, the prices in phases 2 and 3 are guaranteed to fall in the range
$[v_{(2)},v_{(1)}]$ if the second highest bidder is amongst the first $i_{1}$
bidders to depart. Bidders with the highest value may be allocated the item if
they are present at any point in phases 2 and 3, meaning they are amongst the
last $n-i_{1}$ to depart. Then with probability
$\frac{i_{1}}{n}\frac{n-i_{1}}{n-1}=\frac{1-\alpha^{2}}{4}+O(\frac{1}{n})$,
revenue $v_{(2)}$ is extracted. ∎

###  3.2 Strategyproofness

In this section we show our auction is both value-strategyproof and time-
strategyproof. All the missing proofs are deferred to Appendix A. We first
show that the bidders with the first $i_{1}$ departure times have no incentive
to misreport.

######  Lemma 5.

Consider some bidder $i$ and any $\hat{\Theta}_{-i}$. If bidder $i$’s true
departure time is in the first $i_{1}$, then bidder $i$ has no incentive to
misreport her type $\theta_{i}$.

###### Proof.

First note that if such bidder $i$ reports her type truthfully, she won’t
receive the item since $\tau=\infty$ before the departure of the $i_{1}$-th
bidder. Let $\hat{d}$ be the reported departure time of the $i_{1}+1$-th
bidder based on the departure schedule. The only way for bidder $i$ to
possibly obtain the item is to report a later departure time, denoted as
$\hat{d}_{i}$, such that $\hat{d}_{i}>\hat{d}\geq d_{i}$. However, the auction
allocates at her reported departure time $\hat{d}_{i}$, which falls outside
her active time. Based on our assumption, she receives no value from the item.
Such bidder therefore has no incentive to change her type to obtain the item.
∎

We now make the following observation: if there exists a value in the first
$i_{1}$ bidders that is weakly more than the prediction, then the price the
winner pays is fixed. [] Let $v^{\leq i_{1}}_{\max}$ be the maximum value of
the first $i_{1}$ departed bidders. If in Line 1, $\tau=v^{\leq
i_{1}}_{\max}$, then the price winners pays is $p=v^{\leq i_{1}}_{\max}$.

We refer to the above scenario as the _single-threshold case_ since $\tau$ is
effectively only updated once (from $\infty$ to $v^{\leq i_{1}}_{\max}$),
analogously, we refer to the other scenario as the _two-threshold case_. We
note that only the first $i_{1}$ bidders can define $v^{\leq i_{1}}_{\max}$
therefore they (together with the prediction) decide which case the rest of
the bidders are in. We first show that the rest of the bidders have no
incentive to lie in the single-threshold case. The next two lemmas focus on
bidders with true value below and above the threshold, respectively. []
Consider some bidder $i$, and any $\hat{\Theta}_{-i}$ that results in the
single-threshold case and let $\tau$ be the thresholds defined in Line 1. If
bidder $i$ has a value $v_{i}\leq\tau$, she has no incentive to misreport her
type $\theta_{i}$. [] Consider some bidder $i$, and any $\hat{\Theta}_{-i}$
that results in the single-threshold case and let $\tau$ be the thresholds
defined in Line 1. If bidder $i$ has a value $v_{i}>\tau$, she has no
incentive to misreport her type $\theta_{i}$. We now discuss the more involved
case, the two-threshold case. For the ease of presentation, we will denote the
threshold defined in Line 1 as $\tau_{1}$ and the threshold defined in Line 1
as $\tau_{2}$. Note that $\tau_{2}<\tau_{1}$ ($\tau_{2}=\tau_{1}$ is
equivalent to the single-threshold case). We first show that winners in this
case can’t manipulate the price via misreporting.

######  Lemma 6.

Consider some bidder $i$, and any $\hat{\Theta}_{-i}$ that results in the two-
threshold case. If $i$ is the winner with her true type $\theta_{i}$, then
bidder $i$ has no incentive to misreport her type $\theta_{i}$.

###### Proof.

Consider the two possible prices the bidder is paying, $\tau_{1}$ and
$\tau_{2}$. If bidder $i$ wins and pays $\tau_{2}$ (the cheaper one), she has
no incentive to deviate as it is the best outcome. Consider the cases where
bidder $i$ wins with price $\tau_{1}$. By the payment rule, she either left
before the $\tau$ update (she is ranked before $i_{2}$ with respect to
departure time) or there must exist a bidder $i^{\prime}$ that wins in Line 2
of the payment rule. Consider the three possible cases below:

Case one: $i\leq i_{2}$. In this case the bidder $i$ departs before the
threshold drops to $\tau_{2}$. To possibly get the lower price, she has to
report a departure time $\hat{d}_{i}>\hat{d}_{i_{2}}\geq d_{i}$. However, the
auction allocates at her reported departure time $\hat{d}_{i}$ which falls
outside her active time. Based on our assumption, she receives no utility from
the item.

Case two: $\tau^{\prime}=\tau_{1}$. This means that some other bidder
$i^{\prime}$ is above the threshold $\tau_{1}$ before it drops. In this case,
the winner can’t reduce the price since the existence of such a bidder is
independent of her report.

Case three: $\text{active-winner}=\text{true}$ and $i^{\prime}\succ i$. This
case happens when $i^{\prime}$ becomes available right after the threshold
drops to $\tau_{2}$. Since both the tie-breaking rule and the existence of
bidder $i^{\prime}$ are independent of bidder $i$’s report, bidder $i$ can’t
get a better price via misreporting. ∎

We now demonstrate that the losing bidders cannot benefit from misreporting as
well. The next lemma shows that bidders with values below $\tau_{2}$ have no
incentive to lie. The proof is almost identical to the proof of Lemma 5.

[] Consider some bidder $i$, and any $\hat{\Theta}_{-i}$ that results in the
two-threshold case and let $\tau_{1}$ and $\tau_{2}$ be the thresholds defined
in Line 1 and Line 1 respectively. If bidder $i$ has a value
$v_{i}\leq\tau_{2}$, she has no incentive to misreport her type $\theta_{i}$.

The next lemma shows that the losing bidder with values above $\tau_{1}$ has
no incentive to lie. The proof is almost identical to the proof of Lemma 5
regrading the losing bidders. [] Consider some bidder $i$, and any
$\hat{\Theta}_{-i}$ that results in the two-threshold case and let $\tau_{1}$
and $\tau_{2}$ be the thresholds defined in Line 1 and Line 1 respectively. If
bidder $i$ has a value $v_{i}\geq\tau_{1}$ and she is not the winner, she has
no incentive to misreport her type $\theta_{i}$. The next lemma shows that
bidders with value in between the two threshold have no incentive to lie.

######  Lemma 7.

Consider some bidder $i$, and any $\hat{\Theta}_{-i}$ that results in the two-
threshold case and let $\tau_{1}$ and $\tau_{2}$ be the thresholds defined in
Line 1 and Line 1 respectively. If bidder $i$ has a value
$\tau_{1}>v_{i}>\tau_{2}$ and she is not the winner, she has no incentive to
misreport her type $\theta_{i}$.

###### Proof.

Consider a bidder $i$ with a value such that $\tau_{1}>v_{i}>\tau_{2}$ who is
not the winner. The only outcome that is strictly better for her is winning
the item with a price of $\tau_{2}$. For the rest of the proof we show that
such outcome is not obtainable by such bidders through misreporting. Since $i$
is not the winner, there must be another bidder $i^{*}$ who either has a value
above the threshold before $i$ or $i^{*}$ is above the threshold at the same
time as $i$ but $i^{*}\succ i$. Since $i$’s value is less than $\tau_{1}$, she
can only be above the threshold after the departure of the $i_{2}$-th bidder
if she reports her true type.

Case one: If bidder $i^{*}$ is above the threshold before bidder $i$, two
scenarios are possible. First, bidder $i^{*}$ is above the threshold before
the arrival time of bidder $i$, in which case there is no way bidder $i$ can
misreport and win the item, as we assume bidders cannot report an arrival time
earlier than their actual arrival time. If bidder $i^{*}$’s value is not above
the threshold before bidder $i$’s arrival time but is earlier than when
$v_{i}$ is above the threshold, it must be that bidder $i$’s arrival time is
before the threshold drops to $\tau_{2}$, and bidder $i^{*}$ is above the
threshold $\tau_{1}$. In this case, bidder $i$ indeed can report a value
$\hat{v}_{i}\geq\tau_{1}$ to win the item. However, due to the presence of
bidder $i^{*}$, the price she needs to pay is $p=\tau_{1}$ by Line 2 of the
payment subroutine, implying that bidder $i$ would reduce her utility by
misreporting in this way.

Case two: If bidder $i$ loses to bidder $i^{*}$ in the tie-breaking, this can
only occur when the threshold drops to $\tau_{2}$222In all of the cases, we
consider the bidders with respect to some ordering even if they arrive at the
same time.. The only way for bidder $i$ to win the item is if she has an
arrival time before the threshold drop and reports a value
$\hat{v}_{i}\geq\tau_{1}$ to avoid the tie-breaking. However, due to the
presence of bidder $i^{*}$, we would get $\text{active-winner}=\text{true}$
and $i^{\prime}\succ i$, making $p=\tau=\tau_{1}$. Even if bidder $i$ obtains
the item, her utility is non-positive. ∎

We are now ready to show the main Lemma of the subsection

######  Lemma 8.

Three-Phase is both value-strategyproof and time-strategyproof.

###### Proof.

Combining Lemma 5 and 5 we get that in the single-threshold case, no bidder
$i$ has incentive to misreport her type $\theta_{i}$. Combining Lemma 6, 6, 6
and 7, we get that in the two-threshold case, no bidder $i$ has incentive to
misreport her type $\theta_{i}$. ∎

###  3.3 The Error-Tolerant Auction

We now show that our auction can be easily extended to achieve an improved
revenue guarantee not only when the prediction is perfectly accurate, but even
when it is approximately accurate. Given a prediction $\tilde{v}_{(1)}$
regarding the maximum bidder value $v_{(1)}$, we use
$q(\tilde{v}_{(1)},v_{(1)})$, or just $q$, to capture the prediction quality,
defined as the relative under- or over-prediction:

$q=\min\left\\{\frac{\tilde{v}_{(1)}}{v_{(1)}},\frac{v_{(1)}}{\tilde{v}_{(1)}}\right\\}.$

Note that $q\in[0,1]$ and that higher values of $q$ correspond to better
predictions.

We start by describing the Error-Tolerant auction, which is an extension of
the Three-Phase auction. This auction takes as input an additional parameter
$\gamma\in[0,1]$ called the error-tolerance parameter and whose value is
chosen by the auction designer. The only change from Three-Phase to Error-
Tolerant is that Line 1 is changed from
$\tau=\max\\{v_{\max},\tilde{v}_{(1)}\\}$ to
$\tau=\max\\{v_{\max},\gamma\cdot\tilde{v}_{(1)}\\}$. The main result for the
Error-Tolerant auction is that when the prediction quality $q$ is at least the
error-tolerance $\gamma$, then the auction achieves a revenue guarantee of
$\max\\{\alpha\gamma q\cdot v_{(1)},\frac{1-\alpha^{2}}{4}v_{(2)}\\}$. Thus,
in that case, a competitive ratio of $\alpha\gamma q$ is guaranteed against
the first-best revenue benchmark $v_{(1)}$, even if the prediction is not
exactly correct. In addition, a competitive ratio of $\frac{1-\alpha^{2}}{4}$
against the second-best revenue benchmark $v_{(2)}$ is always maintained. We
defer the proof to Appendix B. [] Error-Tolerant is a value-strategyproof and
time-strategyproof online auction that, given any parameter $\alpha\in W_{n}$,
$\gamma\in[0,1]$, and the actual quality $q$ of the prediction, achieves
expected revenue at least

$\operatorname{\mathbb{E}}(Rev(M,\Theta,\tilde{v}_{(1)}))\geq\begin{cases}\max\left\\{\alpha\gamma
q\cdot v_{(1)},\frac{1-\alpha^{2}}{4}v_{(2)}\right\\}&\text{if
$q\geq\gamma$,}\\\ \frac{1-\alpha^{2}}{4}v_{(2)}&\text{if
$q<\gamma$.}\end{cases}$

##  4 A Tight Impossibility Result

In this section, we show that the tradeoff achieved by our auction is optimal
for a natural family of auctions. To define this family of auctions, we first
need to define the family of instances $\mathcal{I}_{\text{no}}$, called the
no-overlap instances. A no-overlap instance is such that at each time step
$i\in[n]$, there is a single active bidder $i$ such that $a_{i}=d_{i}=i$ (the
values can be arbitrary). For the remainder of this section, we implicitly
assume that we are only considering no-overlap instances and show that the
tight impossibility result holds on this restricted family of instances. We
refer to bidder $i$ as the bidder who arrives and departs at time $i\in[n].$
The analysis of the impossibility result considers two nested families of
auctions. The first is called the family of Prediction or Maximum-so-Far (PMF)
auctions.

######  Definition 9.

Consider the following three allocation rules: $x_{1}^{i}$ never allocates the
item to bidder $i$, $x_{2}^{i}$ allocates to $i$ if
$v_{i}\geq\max(\tilde{v}_{(1)},v_{\max}^{<i})$, and $x_{3}^{i}$ allocates to
$i$ if $v_{i}\geq v_{\max}^{<i}$. An auction $M$ is in the family of
Prediction or Maximum-so-Far (PMF) auctions $\mathcal{M}_{m}$ if, for every
bidder $i\in[n]$, there is an allocation rule
$x^{i}\in\\{x_{1}^{i},x_{2}^{i},x_{3}^{i}\\}$ such that, for all no-overlap
instances $\mathcal{I}_{\text{no}}$, if the item is not allocated to a bidder
$j<i$ then $M$ allocates to $i$ according to $x^{i}$.

It is easy to verify that our auction, as well as online auctions in previous
work that are without predictions [20, 14], are PMF auctions. Our
impossibility result holds for a family of auctions that generalizes PMF
auctions. In a Prediction or Any-so-Far (PAF) auction $M\in\mathcal{M}_{a}$,
the allocation rules can depend on the $j^{th}$ highest value seen so far
$v^{<i}_{(j)}$, for any $j\in[i-1]$.

######  Definition 10.

Consider the following allocation rules for bidder $i$:

  * •

$x_{1}^{i}$ never allocates the item to bidder $i$,

  * •

for all $j\in[i-1]$, $x_{2,j}^{i}$ allocates to $i$ if
$v_{i}\geq\max(\tilde{v}_{(1)},v^{<i}_{(j)})$, and

  * •

for all $j\in[i-1]$, $x_{3,j}^{i}$ allocates to $i$ if $v_{i}\geq
v^{<i}_{(j)}$.

Let
$A^{i}=\\{x_{1}^{i}\\}\cup\\{x_{2,j}^{i}\\}_{j\in[i-1]}\cup\\{x_{3,j}^{i}\\}_{j\in[i-1]}$.
An auction $M$ is in the family of Prediction or Any-so-Far (PAF) auctions
$\mathcal{M}_{a}$ if, for every bidder $i\in[n]$, there is an allocation rule
$x^{i}\in A^{i}$ such that, if the item is not allocated to a bidder $j<i$,
$M$ allocates to $i$ according to $x^{i}$ for all no-overlap instances
$\mathcal{I}_{\text{no}}$.

Observe that $\mathcal{M}_{m}\subset\mathcal{M}_{a}\subset\mathcal{M}$.

The main result in this section is the following.

######  Theorem 11.

For any $\alpha\in[0,1]$, there is no auction $M$ in the PAF family of
auctions $\mathcal{M}_{a}$ that is $\alpha$-consistent and
$(\frac{1-\alpha^{2}}{4}+\omega(\frac{1}{n}))$-robust.

We conjecture that the above result also holds for all strategyproof auctions.
Note that, even without predictions, there is still a gap between the best-
known $\frac{1}{4}$-competitive auction and the $\frac{2}{3}$ impossibility
result of [20]. Thus, showing that Theorem 11 holds for all strategyproof
auctions would also close the gap for the setting without predictions.

#### Overview of the proof.

By Myerson’s Lemma [30], we have that for any PAF auction $M$ and bidder $i$,
there is a price
$p_{i}\in\\{\infty,\\{\max(\tilde{v}_{(1)},v_{(j)}^{<i})\\}_{j\in[i-1]},\\{v_{\max}^{<i}\\}_{j\in[i-1]}\\}$
such that, if the item is not allocated to a bidder $j<i$, $M$ posts price
$p_{i}$ to bidder $i$ for all no-overlap instances $\mathcal{I}_{\text{no}}$.
We say that an $\alpha$-consistent auction $M$ is robustness-optimal among
$\mathcal{M}$ if $M\in\mathcal{M}$ and there is no $\alpha$-consistent auction
$M^{\prime}\in\mathcal{M}$ that achieves strictly better robustness than $M$.

  1. 1.

We first show that, for any PAF auction $M\in\mathcal{M}_{a}$, there exists a
PMF auction that achieves consistency and robustness that are no worse than
those achieve by $M$ (Section 4.1). Thus, impossibility results for PMF
auctions extend to PAF auctions.

  2. 2.

We then show that, for any $\alpha\in[0,1]$, there exist $i_{1},i_{2}\in[n]$
and an $\alpha$-consistent, robustness-optimal auction among auctions in
$\mathcal{M}_{m}$ that posts price $\infty$ at each time $i\in[1,i_{1}]$, then
price $\max(\tilde{v}_{(1)},v^{\leq i_{1}}_{(1)})$ at each time
$i\in[i_{1}+1,i_{2}]$, and finally price $v^{\leq i_{2}}_{(1)}$ at each time
$i\in[i_{2}+1,n]$ (Section 4.2). This is the main part of the proof.

  3. 3.

Finally we show that, for the auction structure described in the second step,
the optimal thresholds for maximizing robustness are
$i_{1}=\frac{1-\alpha}{2}n$ and $i_{2}=\frac{\alpha+1}{2}n$, achieving
robustness at most $\frac{1-\alpha^{2}}{4}+\omega(\frac{1}{n})$ (Section 4.3).

###  4.1 The reduction from PAF to PMF auctions

We start by giving a simple formula for the consistency and robustness of
auctions in $\mathcal{M}_{a}$ over the family of instances
$\mathcal{I}_{\text{no}}$. Observe that for instances in
$\mathcal{I}_{\text{no}}$, the random matching of values to intervals is
equivalent to drawing a random permutation that maps the values $V$ to indices
$[1,\ldots,n]$. Let $\Sigma$ be the set of all permutations over the $n$
bidders. Given a permutation $\sigma\in\Sigma$, we define $\sigma(i)$ as the
rank of the ith arriving bidder. In particular, $\sigma(i)=1$ if bidder $i$ is
the bidder with the highest value. If multiple bidders have equal value, we
break ties arbitrarily and consistently. Then we have that $\sigma^{-1}(j)$
denotes the position of the $j$th highest ranked bidder. For
$M\in\mathcal{M}_{a}$, we let $C^{M}:=\\{\sigma:\text{$M$ posts price
$\tilde{v}_{(1)}$ to $\sigma^{-1}(1)$ under order $\sigma$}\\}$ and
$R^{M}:=\\{\sigma:\text{$M$ posts price $v_{(2)}$ to $\sigma^{-1}(1)$ under
order $\sigma$}\\}$.

######  Lemma 12.

Consider an auction $M\in\mathcal{M}_{a}$. Over the family of no-overlap
instances $\mathcal{I}_{\text{no}}$, its consistency is $|C^{M}|/(n!)$ and its
robustness is $|R^{M}|/(n!)$.

###### Proof.

Observe that for each $\sigma\in C^{M}$, the auction achieves revenue
$v_{(1)}$ when the prediction is correct. In addition, for each $\sigma\in
R^{M}$, the auction achieves revenue $v_{(2)}$, even when the prediction is
incorrect. Then consistency and robustness are lower bounded by the
probability of drawing $\sigma\in C^{M}$ and $\sigma\in R^{M}$ respectively
from $\Sigma$, which are precisely $|C^{M}|/|\Sigma|=|C^{M}|/(n!)$ and
$|R^{M}|/|\Sigma|=|R^{M}|/(n!)$.

To show that consistency is at most $|C^{M}|/(n!)$, it suffices to find a
single instance where equality holds. Consider the instance where the values
are $v_{(1)}=1,v_{(2)}=\cdots=v_{(n)}=0$ and prediction $\tilde{v}_{(1)}=1$
(we will denote this $I_{1}$). Observe from our definition of PAF auctions,
the only (noninfinite) prices that can be posted to bidder $i$ are in the set
$\\{v_{1},v_{2},\ldots,v_{i-1},\tilde{v}_{(1)}\\}$. For this instance, only
two of these may be nonzero, $\tilde{v}_{(1)}$ or $v_{j}=1$ if the highest
bidder arrives at step $j<i$ bidder. In the first case, the only bidder who
can accept this price is the highest bidder, and revenue of $v_{(1)}$ is
extracted. In the second case, we know the highest bidder has already
departed, so bidder $i$ must have value $v_{i}=0$ and no revenue can be
gained. Thus the only way revenue is gained in this instance is by posting
$\tilde{v}_{(1)}$ to the highest bidder at step $\sigma^{-1}(1)$, and the
revenue is precisely $v_{(1)}$, so consistency is exactly $|C^{M}|/(n!)$.

Similarly, for robustness consider the instance where the values are
$v_{(1)}=1,v_{(2)}=\varepsilon,v_{(3)}=\cdots=v_{(n)}=0$ for some
$\varepsilon<1$ and the prediction is $\tilde{v}_{(1)}=v_{(1)}+1$ (we will
denote this $I_{2}$). No revenue is gained by posting $\tilde{v}_{(1)}$ since
no bidder would accept that price. The only other positive prices that can be
posted to bidder $i$ are $v_{j}=1$ if the highest bidder arrives at step $j<i$
or $v_{j}=\varepsilon$ if the second highest bidder arrives at step $j<i$. The
first case is the same as above. As for $v_{j}=\varepsilon$, the only bidder
who can accept this price is the highest bidder, and revenue of $v_{(2)}$ is
gained. Thus the only way revenue is gained in this instance is by posting
price $v_{(2)}$ to the highest bidder at step $\sigma^{-1}(1)$, and the
revenue is precisely $v_{(2)}$, so robustness is $|R^{M}|/(n!)$. ∎

######  Lemma 13.

For every $M\in\mathcal{M}_{a}$, there exists some
$M^{\prime}\in\mathcal{M}_{m}$ such that
$\text{consistency}(M^{\prime})\geq\text{consistency}(M)\text{ and
robustness}(M^{\prime})\geq\text{robustness}(M).$

###### Proof.

We will construct $M^{\prime}$ from $M$ as follows. We determine the
allocation rule $M^{\prime}$ uses for bidder $i$:

$x^{\prime i}=\begin{cases}x_{1}^{i}&x^{i}\in\\{x_{1}^{i}\\}\\\
x_{2}^{i}&x^{i}\in\\{x_{2,j}^{i}\\}_{j\in[i-1]}\\\
x_{3}^{i}&x^{i}\in\\{x_{3,j}^{i}\\}_{j\in[i-1]}\end{cases}$

Note that $x_{2}^{i}$ and $x_{3}^{i}$ allocate the item to bidder i if $v_{i}$
is at least $\max(\tilde{v}_{(1)},v_{(1)}^{<i})$ and $v_{(1)}^{<i}$
respectively.

Next, we show that $\text{consistency}(M^{\prime})\geq\text{consistency}(M)$.
First, we have that $\text{consistency}(M^{\prime})=|C^{M^{\prime}}|/(n!)$ by
Lemma 12, so it is sufficient to show that $|C^{M^{\prime}}|\geq|C^{M}|$.
Consider any $\sigma\in C^{M}$ with $\sigma^{-1}(1)=i$. Observe that if $M$
does not allocate the item prior to step $i$, neither does $M^{\prime}$
because at any $j<i$, $M^{\prime}$ posts to $j$ a price at least as high as
the price $M$ posts to $j$. Since price $\tilde{v}_{(1)}$ is posted by $M$ to
$i$, we know that $x^{i}\in\\{x_{2,j}^{i}\\}_{j\in[i-1]}$, and subsequently
$x^{\prime i}=x_{2}^{i}$, so $M^{\prime}$ also posts price $\tilde{v}_{(1)}$
to $i$. Thus $\sigma\in C^{M^{\prime}}$, and therefore
$|C^{M^{\prime}}|\geq|C^{M}|$.

Similarly, we show that
$\text{robustness}(M^{\prime})\geq\text{robustness}(M)$ by proving that
$|R^{M^{\prime}}|\geq|R^{M}|$. Consider any $\sigma\in R^{M}$ with
$\sigma^{-1}(1)=i$. By the same argument as above, if $M$ does not allocate
the item prior to step $i$ neither does $M^{\prime}$. Since $M$ posts price
$v_{(2)}$ to $i$, there are two cases for $x^{i}$. Case 1 is
$x^{i}=x_{2,1}^{i}$ if $\tilde{v}_{(1)}\leq v_{(2)}$. Note that we know $j=1$
because $v_{(1)}$ must be seen at time i. Then $x^{\prime i}=x_{2}^{i}$ and
also posts $v_{(2)}$ to bidder $i$. Case 2 is $x^{i}=x_{3,1}^{i}$, and $j=1$
by the same reasoning. Then $x^{\prime i}=x_{3}^{i}$ and again posts $v_{(2)}$
to bidder $i$. Thus $\sigma\in R^{M^{\prime}}$ and
$|R^{M^{\prime}}|\geq|R^{M}|$. ∎

By Lemma 13, impossibility results for $\mathcal{M}_{m}$ extend to
$\mathcal{M}_{a}$.

###  4.2 The main lemma for the impossibility result

The main lemma for the impossibility result shows that there exists an
$\alpha$-consistent auction that is robustness-optimal among auctions in
$\mathcal{M}_{a}$ and has, on no-overlap instances, a three-phase structure
(as our auction).

######  Lemma 14.

There exists an $\alpha$-consistent auction that is robustness-optimal among
auctions in $\mathcal{M}_{a}$ and satisfies the following structure: it posts
price $\infty$ at each time $i\in[1,i_{1}]$, then price
$\max(\tilde{v}_{(1)},v_{\max}^{<i})$ at each time $i\in[i_{1}+1,i_{2}]$, and
finally price $v_{\max}^{<i}$ at each time $i\in[i_{2}+1,n]$.

The remainder of Section 4.2 is devoted to the proof of Lemma 14.

#### Overview of the proof of Lemma 14.

The proof follows an interchange argument that shows that if an auction
$M\in\mathcal{M}_{m}$ does not post prices in the order specified by Lemma 14,
then there are two positions $i$ and $i+1$ that violate this order and the
prices posted at these time steps can be swapped without decreasing $|C^{M}|$
and $|R^{M}|$, and therefore without decreasing consistency and robustness.
There are three potential violations of the ordering specified by Lemma 14. In
Lemma 16, we consider the case where $v_{\max}^{<i}$ is posted to bidder $i$
and $\max(\tilde{v}_{(1)},v_{\max}^{<i+1})$ to bidder $i+1$, in Lemma 17 the
case where $v_{\max}^{<i}$ is posted to bidder $i$ and $\infty$ to bidder
$i+1$, and in Lemma 18 the case where $\max(\tilde{v}_{(1)},v_{\max}^{<i})$ to
bidder $i$ and $\infty$ to bidder $i+1$.

We now define the interchange function $f_{i}:\Sigma\to\Sigma$. For fixed
index $i$ and any permutation $\sigma$, let

$f_{i}(\sigma)(j)=\begin{cases}\sigma(i+1)&j=i\\\ \sigma(i)&j=i+1\\\
\sigma(j)&\text{else},\end{cases}$

which is a bijective function that swaps the values of the ith and (i+1)th
bidders. We first state a trivial fact regarding the revenue achieved from the
first $i-1$ bidders for two auctions that are identical up to step $i$. This
fact will be repeatedly used in the proof of the next lemmas.

######  Lemma 15.

Consider two auctions $M,M^{\prime}\in\mathcal{M}_{m}$ that are identical for
steps up to $i$. Then $M$ under order $\sigma$ and $M^{\prime}$ under order
$f_{i}(\sigma)$ gain the same revenue before step $i$.

###### Proof.

Observe that $f_{i}(\sigma)$ does not affect the values that appear before
$i$. Then $M^{\prime}$ sees the same ranks before $i$ under $f_{i}(\sigma)$ as
$M$ does under $\sigma$, and since they follow the same rules the revenue
gained at each step before $i$ is the same. ∎

The first potential violation of the ordering specified by Lemma 14 is when
$v_{\max}^{<i}$ is posted to bidder $i$ and
$\max(\tilde{v}_{(1)},v_{\max}^{<i+1})$ to bidder $i+1$.

######  Lemma 16.

Consider an auction $M\in\mathcal{M}_{m}$ that posts price $v_{\max}^{<i}$ at
some step $i$ and $\max(\tilde{v}_{(1)},v_{\max}^{<i+1})$ at step $i+1$. Let
$M^{\prime}$ be the same auction as $M$ except that it posts price
$\max(\tilde{v}_{(1)},v_{\max}^{<i})$ at step $i$ and $v_{\max}^{<i+1}$ at
step $i+1$. Then, $|C^{M^{\prime}}|\geq|C^{M}|$ and
$|R^{M^{\prime}}|\geq|R^{M}|$.

###### Proof.

First we show that if $\sigma\in C^{M}$, then $f_{i}(\sigma)\in
C^{M^{\prime}}$, meaning $f_{i}(C^{M})\subseteq C^{M^{\prime}}$. Since $f_{i}$
is a bijective function, consequently $|C^{M^{\prime}}|\geq|C^{M}|$. Assume
that $\tilde{v}_{(1)}=v_{(1)}$. Consider any $\sigma\in C^{M}$, then
$\tilde{v}_{(1)}$ is posted to the highest ranked bidder who arrives at step
$\sigma^{-1}(1)$. Observe that to prove $f_{i}(\sigma)\in C^{M^{\prime}}$, it
is sufficient to show that price $\tilde{v}_{(1)}$ is posted to bidder
$f_{i}(\sigma)^{-1}(1)$, or that revenue $\tilde{v}_{(1)}$ is extracted by
$M^{\prime}$ under ordering $f_{i}(\sigma)$. There are three cases.

First, if $\sigma^{-1}(1)<i$, observe that there is no difference between $M$
and $M^{\prime}$ before step $i$. Then it follows from Lemma 15 that since $M$
extracts revenue $\tilde{v}_{(1)}$ at step $\sigma^{-1}(1)<i$, $M^{\prime}$
extracts the same revenue under $f_{i}(\sigma)$ before step $i$.

The second case is if $\sigma^{-1}(1)\in\\{i,i+1\\}$. Recall that $\sigma\in
C^{M}$ implies that price $\tilde{v}_{(1)}$ is posted to bidder
$\sigma^{-1}(1)$. Then since $M$ posts $v_{\max}^{<i}<\tilde{v}_{(1)}$ to
bidder $i$, $\sigma^{-1}(1)=i+1$ is the only possibility, and indeed $M$ posts
$\max(\tilde{v}_{(1)},v_{\max}^{<i+1})=\tilde{v}_{(1)}$ to $i+1$. Now we must
show that $M^{\prime}$ posts price $\tilde{v}_{(1)}$ to
$f_{i}(\sigma)^{-1}(1)$. By our definition of the interchange function,
$f_{i}(\sigma)(i)=\sigma(i+1)=1$, so $f_{i}(\sigma)^{-1}(1)=i$. Note that if
$M$ reaches step $i$, then $M^{\prime}$ does as well. Then since $M^{\prime}$
posts price $\max(\tilde{v}_{(1)},v_{\max}^{<i})=\tilde{v}_{(1)}$ at step $i$,
then $f_{i}(\sigma)\in C^{M^{\prime}}$.

The third and last case is if $\sigma^{-1}(1)>i+1$. Observe that it is
sufficient to show that under $M^{\prime}$, bidders $i$ and $i+1$ do not
receive the item because at steps after $i+1$, the auctions see the same order
of bidders and make the same posts. Clearly if under $M$ bidder $i+1$ does not
accept its posted-price $\tilde{v}_{(1)}$, ie $v_{i+1}<\tilde{v}_{(1)}$, then
under $M^{\prime}$, bidder $i$ with value
$v_{(f_{i}(\sigma)(i))}=v_{(\sigma(i+1))}=v_{i+1}$ will not accept its posted
price $\tilde{v}_{(1)}$. Now we consider bidder $i+1$ under $M^{\prime}$. If
we let $\overline{v}_{\max}^{<\ell}$ be the value of the highest ranked bidder
seen before step $\ell$ given ordering $f_{i}(\sigma)$, we can see that
$\overline{v}_{\max}^{<i+1}\geq\overline{v}_{\max}^{<i}=v_{\max}^{<i}$. Then
if bidder $i$ does not accept the price $v_{\max}^{<i}$ posted under $M$, ie
$v_{i}<v_{\max}^{<i}$, then
$v_{(f_{i}(\sigma)(i+1))}=v_{(\sigma(i))}=v_{i}<v_{\max}^{<i}\leq\overline{v}_{\max}^{<i+1}$
and under $M^{\prime}$ bidder $i+1$ also does not accept its posted price
$\overline{v}_{\max}^{<i+1}$.

Next, to show the second part of lemma, we show that $f_{i}(R^{M})\subseteq
R^{M^{\prime}}$. If $\sigma\in R^{M}$ is true, then $v_{\max}^{<i}=v_{(2)}$ is
posted to the bidder at step $\sigma^{-1}(1)$. Similar to the consistency
proof, to prove $f_{i}(\sigma)\in R^{M^{\prime}}$, it is sufficient to show
that price $v_{(2)}$ is posted to bidder $f_{i}(\sigma)^{-1}(1)$, or that
revenue $v_{(2)}$ is extracted by $M^{\prime}$ under ordering $f_{i}(\sigma)$
(for any value of $\tilde{v}_{(1)}$). Cases 1 and 3 are exactly the same as
for consistency. Then consider $\sigma^{-1}(1)\in\\{i,i+1\\}$.

If $\tilde{v}_{(1)}>v_{(1)}$, then under $M$ price
$\max(\tilde{v}_{(1)},v_{\max}^{<i+1})>v_{(1)}$ is posted to and rejected by
bidder $i+1$, so $\sigma^{-1}(1)=i$ is the only possibility. Indeed, price
$v_{\max}^{<i}=v_{(2)}$ may be posted to $i$ if the second highest bidder
arrives before $i$. After the interchange, bidder $i$ is offered price
$\tilde{v}_{(1)}>v_{(1)}$ under $M^{\prime}$ and they reject it. Observe that
if $\sigma^{-1}(1)=i$, then $f_{i}(\sigma)^{-1}(1)=i+1$. Then under
$M^{\prime}$, bidder $i+1$ sees price
$\overline{v}_{\max}^{<i+1}=v_{\max}^{<i}=v_{(2)}$.

Now if $\tilde{v}_{(1)}<v_{(2)}$, then there are two scenarios. First,
consider $\sigma^{-1}(1)=i$, then since $M$ posts $v_{\max}^{<i}$ at $i$ we
know that $v_{\max}^{<i}=v_{(2)}$. Observe that since the highest two bidders
arrive by step $i$, then $v_{i+1}<v_{(2)}$. Under $f_{i}(\sigma)$, bidder $i$
has value $v_{(f_{i}(\sigma)(i))}=v_{(\sigma(i+1))}=v_{i+1}$. Then when
$M^{\prime}$ posts to bidder $i$ price
$\max(\tilde{v}_{(1)},\overline{v}_{\max}^{<i})=v_{\max}^{<i}=v_{(2)}$, it is
rejected. $M^{\prime}$ then posts price $\overline{v}_{\max}^{<i+1}$, which is
exactly $v_{(2)}$ because bidder $i$ has value below $v_{(2)}$, to the bidder
with rank $f_{i}(\sigma)(i+1)=\sigma(i)=1$. If instead $\sigma^{-1}(1)=i+1$,
then it is impossible for bidder $i$ to have the second highest value or else
they would accept their price $v_{\max}^{<i}<v_{(2)}$. Then for
$\max(\tilde{v}_{(1)},v_{\max}^{<i})=v_{(2)}$ to hold, the second highest
bidder must arrive before $i$ and $v_{\max}^{<i}=v_{(2)}$. Thus under
$M^{\prime}$, price $\overline{v}_{\max}^{<i}=v_{\max}^{<i}$ is posted at step
$i$ to the bidder with rank $f_{i}(\sigma)(i)=\sigma(i+1)=1$.

Observe that if $v_{(2)}\leq\tilde{v}_{(1)}\leq v_{(1)}$, given that
$v_{\max}^{<i}=v_{(2)}$, selling by posting
$\max(\tilde{v}_{(1)},v_{\max}^{<i})$ and $v_{\max}^{<i}$ both result in at
least $v_{(2)}$ revenue, so swapping these two prices does not lower
robustness. ∎

The second potential violation of the ordering specified by Lemma 14 is when
$v_{\max}^{<i}$ is posted to bidder $i$ and $\infty$ to bidder $i+1$.

######  Lemma 17.

Consider an auction $M\in\mathcal{M}_{m}$ that posts price $v_{\max}^{<i}$ at
some step $i$ and $\infty$ at step $i+1$. Let $M^{\prime}$ be the same auction
at $M$ except that it posts price $\infty$ at step $i$ and $v_{\max}^{<i+1}$
at step $i+1$. Then, $|C^{M^{\prime}}|\geq|C^{M}|$ and
$|R^{M^{\prime}}|\geq|R^{M}|$.

###### Proof.

We first show that $|C^{M^{\prime}}|\geq|C^{M}|$ by proving that
$f_{i}(C^{M})\subseteq C^{M^{\prime}}$. Let $\tilde{v}_{(1)}=v_{(1)}$.
Consider any $\sigma\in C^{M}$, so $\tilde{v}_{(1)}$ is posted to bidder
$\sigma^{-1}(1)$. There are again three cases. The first case,
$\sigma^{-1}(1)<i$, is as in Lemma 16. The second case is
$\sigma^{-1}(1)\in\\{i,i+1\\}$. Observe that it is impossible to post
$\tilde{v}_{(1)}$ to bidder $\sigma^{-1}(1)$ by posting $\infty$ or
$v_{\max}^{<i}$. This is because $v_{\max}^{<i}\leq v_{(2)}$. The third and
last case is $\sigma^{-1}(1)>i+1$. It is sufficient to show that $M^{\prime}$
does not sell the item at time $i$ or $i+1$. Clearly the former is true
because $\infty$ is posted to $i$. Since $M$ fails to sell the item at step
$i$ by posting price $v_{\max}^{<i}$, we know that $v_{i}<v_{\max}^{<i}$. Then
under $M^{\prime}$, the price
$\overline{v}_{\max}^{<i+1}\geq\overline{v}_{\max}^{<i}=v_{\max}^{<i}$ is
posted to bidder with value $v_{(f_{i}(\sigma)(i+1))}=v_{(\sigma(i))}=v_{i}$,
so the item is not sold to bidder $i+1$ under $M^{\prime}$.

For the second part of the lemma, we show $f_{i}(\sigma)\in R^{M^{\prime}}$
for any $\sigma\in R^{M}$. If $\sigma\in R^{M}$ is true, then
$v_{\max}^{<i}=v_{(2)}$ is posted to the bidder at step $\sigma^{-1}(1)$.
Similar to the consistency proof, to prove $f_{i}(\sigma)\in R^{M^{\prime}}$,
it is sufficient to show that price $v_{(2)}$ is posted to bidder
$f_{i}(\sigma)^{-1}(1)$, or that revenue $v_{(2)}$ is extracted by
$M^{\prime}$ under ordering $f_{i}(\sigma)$ (for any value of
$\tilde{v}_{(1)}$). Once again, cases one and three are the same. Now consider
$\sigma^{-1}(1)\in\\{i,i+1\\}$. Since bidder $i+1$ never accepts $\infty$,
this means that $\sigma^{-1}(1)=i$. $M$ posts price $v_{\max}^{<i}$ to bidder
$i$, so $v_{\max}^{<i}=v_{(2)}$. Observe that
$f_{i}(\sigma)(i+1)=\sigma(i)=1$. First $M^{\prime}$ posts $\infty$ at step
$i$, and then $\overline{v}_{\max}^{<i+1}$, which equals $v_{(2)}$ since the
highest bidder cannot be at step $i$ under $f_{i}(\sigma)$. Then $v_{(2)}$ is
posted to bidder $i+1=f_{i}(\sigma)^{-1}(1)$. ∎

The third and last potential violation of the ordering specified by Lemma 14
is when $\max(\tilde{v}_{(1)},v_{\max}^{<i})$ to bidder $i$ and $\infty$ to
bidder $i+1$.

######  Lemma 18.

Consider an auction $M\in\mathcal{M}_{m}$ that posts price
$\max(\tilde{v}_{(1)},v_{\max}^{<i})$ at some step $i$ and $\infty$ at step
$i+1$. Let $M^{\prime}$ be the same auction at $M$ except that it posts price
$\infty$ at step $i$ and $\max(\tilde{v}_{(1)},v_{\max}^{<i+1})$ at step
$i+1$. Then, $|C^{M^{\prime}}|\geq|C^{M}|$ and $|R^{M^{\prime}}|\geq|R^{M}|$.

###### Proof.

We again first show that $|C^{M^{\prime}}|\geq|C^{M}|$ by proving that
$f_{i}(C^{M})\subseteq C^{M^{\prime}}$. Let $\tilde{v}_{(1)}=v_{(1)}$.
Consider any $\sigma\in C^{M}$, so $\tilde{v}_{(1)}$ is posted to bidder
$\sigma^{-1}(1)$. The first case, $\sigma^{-1}(1)<i$, is as in Lemma 16. The
second case is $\sigma^{-1}(1)\in\\{i,i+1\\}$. Since auction $M$ posts
$\infty$ to $i+1$, $\sigma^{-1}(1)=i$ is the only possibility, and indeed
$\max(\tilde{v}_{(1)},v_{\max}^{<i})=\tilde{v}_{(1)}$ is posted at $i$. First
observe that if $M$ reaches step $i$, then $M^{\prime}$ does as well.
$M^{\prime}$ subsequently posts $\infty$ to bidder $i$, effectively skipping
them. We know that $f_{i}(\sigma)(i+1)=\sigma(i)=1$. Then when under
$f_{i}(\sigma)$ auction $M^{\prime}$ posts
$\max(\tilde{v}_{(1)},v_{\max}^{<i+1})=\tilde{v}_{(1)}$ at step $i+1$, it is
to the highest bidder. The third and last case is $\sigma^{-1}(1)>i+1$. Use
the same argument as in Lemma 17 except instead of $v_{\max}^{<i}$ being
rejected by bidder $i$ under $M$ and $i+1$ under $M^{\prime}$, here
$\max(\tilde{v}_{(1)},v_{\max}^{<i})\geq v_{\max}^{<i}$ is being rejected by
bidder $i$ under $M$ and $i+1$ under $M^{\prime}$.

For the second part of the lemma, we show that $f_{i}(\sigma)\in
R^{M^{\prime}}$ for $\sigma\in R^{M}$. If $\sigma\in R^{M}$ is true, then
$v_{\max}^{<i}=v_{(2)}$ is posted to the bidder at step $\sigma^{-1}(1)$.
Similar to the consistency proof, to prove $f_{i}(\sigma)\in R^{M^{\prime}}$,
it is sufficient to show that price $v_{(2)}$ is posted to bidder
$f_{i}(\sigma)^{-1}(1)$, or that revenue $v_{(2)}$ is extracted by
$M^{\prime}$ under ordering $f_{i}(\sigma)$ (for any value of
$\tilde{v}_{(1)}$). Observe that the proofs for cases 1 and 3 are the same as
above. Case two is impossible if $\tilde{v}_{(1)}>v_{(1)}$ because no bidder
accepts prices $\infty$ or $\max(\tilde{v}_{(1)},v_{\max}^{<i})>v_{(1)}$. Then
if $\tilde{v}_{(1)}<v_{(1)}$, we have $\sigma^{-1}(1)=i$, as auction $M$ posts
$\infty$ to bidder $i+1$. In order for value at least $v_{(2)}$ (but below
$v_{(1)}$) to be posted at step $i$ by $M$, we need
$\max(\tilde{v}_{(1)},v_{\max}^{<i})\geq v_{(2)}$, so it is sufficient for the
second highest bidder to arrive before $i$ and therefore
$v_{\max}^{<i}=v_{(2)}$. Observe that $f_{i}(\sigma)(i+1)=\sigma(i)=1$. Under
$M^{\prime}$, $\infty$ is posted to bidder $i$, and then
$\max(\tilde{v}_{(1)},\overline{v}_{\max}^{<i+1})$ is posted to bidder $i+1$.
We know that
$\overline{v}_{\max}^{<i+1}=\overline{v}_{\max}^{<i}=v_{\max}^{<i}$ by the
same reasoning as in Lemma 17. Then $M^{\prime}$ posts
$\max(\tilde{v}_{(1)},v_{\max}^{<i+1})\in[v_{(1)},v_{(2)}]$ to bidder $i+1$
with the highest value. ∎

We are now ready to prove Lemma 14.

Proof of Lemma 14. Consider an $\alpha$-consistent robustness-optimal auction
$M\in\mathcal{M}_{m}$. If it does not satisfy the structure specified by Lemma
14, then there exist time steps $i$ and $i+1$ such that $M$ either posts
prices $v_{\max}^{<i}$ and $\max(\tilde{v}_{(1)},v_{\max}^{<i+1})$, or prices
$\infty$ and $v_{\max}^{<i+1}$, or prices $\infty$ and
$\max(\tilde{v}_{(1)},v_{\max}^{<i+1})$ to $i$ and $i+1$. Lemma 16, Lemma 17,
and Lemma 18 show that for each of these cases, the two prices can be swapped
without decreasing $|R^{M}|$ and $|C^{M}|$. By repeating this swapping
process, we obtain an auction $M^{\prime}$ such that
$|C^{M^{\prime}}|\geq|C^{M}|$ and $|R^{M^{\prime}}|\geq|R^{M}|$.

Thus, by Lemma 12, $M^{\prime}$ is also an $\alpha$-consistent robustness-
optimal auction among $\mathcal{M}_{m}$ with the structure presented in Lemma
14. By Lemma 13, $M^{\prime}$ is also robustness-optimal among
$\mathcal{M}_{a}$. ∎

###  4.3 The optimal thresholds

For auctions in $\mathcal{M}_{a}$ constructed as in Lemma 14, the time
thresholds $i_{1}$ and $i_{2}$ set to $\frac{1-\alpha}{2}n$ and
$\frac{1+\alpha}{2}n$ achieve $\alpha$-consistency and
$\frac{1-\alpha^{2}}{4}+O(\frac{1}{n})$-robustness. We show that for
$\alpha\in[0,1]$, no other thresholds lead to a better robustness, which then
shows the impossibility result for PAF auctions. We note that our auction also
use these same thresholds.

Proof of Theorem 11. Let us first introduce some notation. Let $R_{i}(M)$ be
the event that step $i$ is reached under auction $M$ and let
$P_{i}^{\tilde{v}_{(1)}}(M)$ be the event that $\tilde{v}_{(1)}$ is posted at
step $i$ under auction $M$. For a fixed $\alpha\in[0,1]$, consider an
$\alpha$-consistent auction $M\in\mathcal{M}_{a}$ that is optimal with respect
to robustness and is structured as in Lemma 14 with time thresholds $i_{1}$
and $i_{2}$. Observe that if $\tilde{v}_{(1)}=v_{(1)}$, then the consistency
achieved by $M$ is

$\displaystyle\sum_{i=1}^{n}\mathbb{P}(\sigma(i)=1)\cdot\mathbb{P}(R_{i}(M)|\sigma(i)=1)\cdot\mathbb{P}(P_{i}^{\tilde{v}_{(1)}}(M)|R_{i}(M),\sigma(i)=1)$
$\displaystyle=\frac{1}{n}\sum_{i=i_{1}+1}^{i_{2}}\mathbb{P}(R_{i}(M)|\sigma(i)=1)$
$\displaystyle=\frac{i_{2}-i_{1}}{n}.$

where the first equality is because $\tilde{v}_{(1)}$ is posted only at steps
$i\in[i_{1}+1,i_{2}]$ and the highest ranking bidder is equally likely to be
at any step. The second equality holds because $M$ posting $\infty$ up to step
$i_{1}$ and bidders within $[i_{1}+1,i-1]$ failing to accept price $v_{(1)}$.
Thus, $M$ achieves $\alpha$-consistency if $i_{2}\geq i_{1}+\alpha n$ .

In our auction, we use $i_{1}=\frac{1-\alpha}{2}n$ and
$i_{2}=\frac{1+\alpha}{2}n$, and we show no other pair
$i_{1}^{\prime},i_{2}^{\prime}$ can improve robustness. Recall from Lemma 12
that the robustness of $M$ is precisely $|R^{M}|/(n!)$. We consider two cases.
The first is if $i_{1}^{\prime}\leq i_{1}$. Observe that if
$\tilde{v}_{(1)}<v_{(2)}$, and letting $\sigma$ being a uniformly random
permutation in $\Sigma$, then we have that

$\displaystyle\frac{|R^{M}|}{n!}=\mathbb{P}_{\sigma}(\sigma\in R^{M})$
$\displaystyle=\mathbb{P}_{\sigma}(M\text{ posts price }v_{(2)}\text{ to
}\sigma^{-1}(1))$ $\displaystyle=\mathbb{P}_{\sigma}(\sigma^{-1}(2)\leq
i_{1}^{\prime})\cdot\mathbb{P}_{\sigma}(\sigma^{-1}(1)>i_{1}^{\prime}|\sigma^{-1}(2)\leq
i_{1}^{\prime})$
$\displaystyle=\frac{i_{1}^{\prime}}{n}\frac{n-i_{1}^{\prime}}{n-1}$

where the first equality is by definition of $\sigma$ and the second by
definition of $R^{M}$. The third equality is since we need
$\sigma^{-1}(1)>i_{1}^{\prime}$ to not post $\infty$ to $\sigma^{-1}(1)$,
$\sigma^{-1}(2)\leq\sigma^{-1}(1)$ so that
$\max(\tilde{v}_{(1)},v_{\max}^{<\sigma^{-1}(1)})=v_{\max}^{<\sigma^{-1}(1)}=v_{(2)}$
is posted to $\sigma^{-1}(1)$, and
$\sigma^{-1}(2)\not\in[i_{1}^{\prime},\sigma^{-1}(1)]$ to not sell to
$\sigma^{-1}(2)$ and reach $\sigma^{-1}(1)$. Differentiating
$\frac{i_{1}^{\prime}}{n}\frac{n-i_{1}^{\prime}}{n-1}$ with respect to
$i_{1}^{\prime}$, we get $\frac{n-2i_{1}^{\prime}}{n(n-1)}$, which is positive
for $i_{1}^{\prime}\leq\frac{n}{2}$. Then since
$i_{1}^{\prime}\leq\frac{1-\alpha}{2}n\leq\frac{n}{2}$, we get that the
robustness of $M$ is
$\frac{i_{1}^{\prime}}{n}\frac{n-i_{1}^{\prime}}{n-1}\leq\frac{i_{1}}{n}\frac{n-i_{1}}{n-1}=\frac{n}{n-1}\frac{1-\alpha^{2}}{4}$.

The second case is if $i_{1}^{\prime}>i_{1}$. Since $i_{2}=i_{1}+\alpha n$,
then $i_{2}^{\prime}\geq i_{1}^{\prime}+\alpha n\geq i_{2}$. Observe that if
$\tilde{v}_{(1)}>v_{(1)}$, and letting $\sigma$ being a uniformly random
permutation in $\Sigma$, then we have that

$\displaystyle\frac{|R^{M}|}{n!}$ $\displaystyle=\mathbb{P}_{\sigma}(M\text{
posts price }v_{(2)}\text{ to }\sigma^{-1}(1))$
$\displaystyle=\mathbb{P}_{\sigma}(\sigma^{-1}(2)\leq
i_{2}^{\prime})\cdot\mathbb{P}_{\sigma}(\sigma^{-1}(1)>i_{2}^{\prime}|\sigma^{-1}(2)\leq
i_{1}^{\prime})$
$\displaystyle=\frac{i_{2}^{\prime}}{n}\frac{n-i_{2}^{\prime}}{n-1}$

where the second equality is since we need $\sigma^{-1}(1)>i_{2}^{\prime}$ to
not post $\infty$ or $\tilde{v}_{(1)}$ to $\sigma^{-1}(1)$,
$\sigma^{-1}(2)\leq\sigma^{-1}(1)$ so that
$v_{\max}^{<\sigma^{-1}(1)}=v_{(2)}$ is posted to $\sigma^{-1}(1)$, and
$\sigma^{-1}(2)\not\in[i_{2}^{\prime},\sigma^{-1}(1)]$ to not sell to
$\sigma^{-1}(2)$ and reach $\sigma^{-1}(1)$. Differentiating
$\frac{i_{2}^{\prime}}{n}\frac{n-i_{2}^{\prime}}{n-1}$ with respect to
$i_{2}^{\prime}$, we get $\frac{n-2i_{2}^{\prime}}{n(n-1)}$, which is negative
for $i_{2}^{\prime}\geq\frac{n}{2}$. Since
$i_{2}^{\prime}\geq\frac{1+\alpha}{2}n\geq\frac{n}{2}$, we obtained that the
robustness achieved by $M$ is
$\frac{i_{2}^{\prime}}{n}\frac{n-i_{2}^{\prime}}{n-1}\leq\frac{i_{2}}{n}\frac{n-i_{2}}{n-1}=\frac{n}{n-1}\frac{1-\alpha^{2}}{4}$.

Thus, an $\alpha$-consistent auction $M\in\mathcal{M}_{a}$ that is optimal
with respect to robustness and is structured as in Lemma 14 achieves a
robustness that is at most
$\frac{n}{n-1}\frac{1-\alpha^{2}}{4}=\frac{1-\alpha^{2}}{4}+O(\frac{1}{n})$.
By Lemma 14, we conclude that this robustness bound holds for any PAF auction.
∎

## References

  * Agrawal et al. [2022] P. Agrawal, E. Balkanski, V. Gkatzelis, T. Ou, and X. Tan.  Learning-augmented mechanism design: Leveraging predictions for facility location.  In _EC ’22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022_ , pages 497–528. ACM, 2022\.
  * Antoniadis et al. [2023] A. Antoniadis, T. Gouleakis, P. Kleer, and P. Kolev.  Secretary and online matching problems with machine learned advice.  _Discret. Optim._ , 48(Part 2):100778, 2023.
  * Azar et al. [2022] Y. Azar, D. Panigrahi, and N. Touitou.  Online graph algorithms with predictions.  _Proceedings of the Thirty-Third Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2022.
  * Balcan et al. [2023] M. Balcan, S. Prasad, and T. Sandholm.  Bicriteria multidimensional mechanism design with side information.  _CoRR_ , abs/2302.14234, 2023.  doi: 10.48550/arXiv.2302.14234.  URL https://doi.org/10.48550/arXiv.2302.14234.
  * Balkanksi et al. [2023] E. Balkanksi, V. Gkatzelis, and X. Tan.  Mechanism design with predictions: An annotated reading list.  _SIGecom Exchanges_ , 21(1):54–57, 2023.
  * Balkanski et al. [2023] E. Balkanski, V. Gkatzelis, and X. Tan.  Strategyproof scheduling with predictions.  In Y. T. Kalai, editor, _14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA_ , volume 251 of _LIPIcs_ , pages 11:1–11:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.  doi: 10.4230/LIPIcs.ITCS.2023.11.  URL https://doi.org/10.4230/LIPIcs.ITCS.2023.11.
  * Bamas et al. [2020] É. Bamas, A. Maggiori, and O. Svensson.  The primal-dual method for learning augmented algorithms.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Banerjee et al. [2022] S. Banerjee, V. Gkatzelis, A. Gorokh, and B. Jin.  Online nash social welfare maximization with predictions.  In _Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022_. SIAM, 2022.
  * Bar-Yossef et al. [2002] Z. Bar-Yossef, K. Hildrum, and F. Wu.  Incentive-compatible online auctions for digital goods.  In D. Eppstein, editor, _Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA_ , pages 964–970. ACM/SIAM, 2002.  URL http://dl.acm.org/citation.cfm?id=545381.545506.
  * Blum and Hartline [2005] A. Blum and J. D. Hartline.  Near-optimal online auctions.  In _Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005_ , pages 1156–1163. SIAM, 2005.  URL http://dl.acm.org/citation.cfm?id=1070432.1070597.
  * Blum et al. [2003] A. Blum, V. Kumar, A. Rudra, and F. Wu.  Online learning in online auctions.  In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA_ , pages 202–204. ACM/SIAM, 2003.  URL http://dl.acm.org/citation.cfm?id=644108.644143.
  * Blum et al. [2006] A. Blum, T. Sandholm, and M. Zinkevich.  Online algorithms for market clearing.  _J. ACM_ , 53(5):845–879, 2006.  doi: 10.1145/1183907.1183913.  URL https://doi.org/10.1145/1183907.1183913.
  * Bredin and Parkes [2012] J. Bredin and D. C. Parkes.  Models for truthful online double auctions.  _CoRR_ , abs/1207.1360, 2012.  URL http://arxiv.org/abs/1207.1360.
  * Buchbinder et al. [2010] N. Buchbinder, K. Jain, and M. Singh.  Incentives in online auctions via linear programming.  In _International Workshop on Internet and Network Economics_ , pages 106–117. Springer, 2010.
  * Buchbinder et al. [2014] N. Buchbinder, K. Jain, and M. Singh.  Secretary problems via linear programming.  _Mathematics of Operations Research_ , 39(1):190–206, 2014.  URL http://www.jstor.org/stable/24540892.
  * Constantin et al. [2007] F. Constantin, T. Ito, and D. C. Parkes.  Online auctions for bidders with interdependent values.  In E. H. Durfee, M. Yokoo, M. N. Huhns, and O. Shehory, editors, _6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2007), Honolulu, Hawaii, USA, May 14-18, 2007_ , page 110. IFAAMAS, 2007.  doi: 10.1145/1329125.1329260.  URL https://doi.org/10.1145/1329125.1329260.
  * Dütting et al. [2021] P. Dütting, S. Lattanzi, R. P. Leme, and S. Vassilvitskii.  Secretaries with advice.  In P. Biró, S. Chawla, and F. Echenique, editors, _EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021_ , pages 409–429. ACM, 2021.
  * Fujii and Yoshida [2023] K. Fujii and Y. Yoshida.  The secretary problem with predictions.  _CoRR_ , abs/2306.08340, 2023.
  * Gkatzelis et al. [2022] V. Gkatzelis, K. Kollias, A. Sgouritsa, and X. Tan.  Improved price of anarchy via predictions.  In _Proceedings of the 23rd ACM Conference on Economics and Computation_ , pages 529–557, 2022.
  * Hajiaghayi et al. [2004] M. T. Hajiaghayi, R. Kleinberg, and D. C. Parkes.  Adaptive limited-supply online auctions.  In _Proceedings of the 5th ACM Conference on Electronic Commerce_ , pages 71–80, 2004.
  * Im et al. [2021] S. Im, R. Kumar, M. M. Qaem, and M. Purohit.  Online knapsack with frequency predictions.  In _Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual_ , pages 2733–2743, 2021.
  * Istrate and Bonchis [2022] G. Istrate and C. Bonchis.  Mechanism design with predictions for obnoxious facility location.  _CoRR_ , abs/2212.09521, 2022.
  * Koutsoupias and Pierrakos [2013] E. Koutsoupias and G. Pierrakos.  On the competitive ratio of online sampling auctions.  _ACM Transactions on Economics and Computation (TEAC)_ , 1(2):1–10, 2013.
  * Krysta and Telelis [2012] P. Krysta and O. Telelis.  Limited supply online auctions for revenue maximization.  In _International Workshop on Internet and Network Economics_ , pages 519–525. Springer, 2012.
  * [25] A. Lindermayr and N. Megow.  Alps.  URL https://algorithms-with-predictions.github.io/.
  * Lykouris and Vassilvtiskii [2018] T. Lykouris and S. Vassilvtiskii.  Competitive caching with machine learned advice.  In _International Conference on Machine Learning_ , pages 3296–3305. PMLR, 2018.
  * Medina and Vassilvitskii [2017] A. M. Medina and S. Vassilvitskii.  Revenue optimization with approximate bid predictions.  In I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 1858–1866, 2017.  URL https://proceedings.neurips.cc/paper/2017/hash/884d79963bd8bc0ae9b13a1aa71add73-Abstract.html.
  * Mitzenmacher and Vassilvitskii [2021] M. Mitzenmacher and S. Vassilvitskii.  Algorithms with predictions.  In T. Roughgarden, editor, _Beyond the Worst-Case Analysis of Algorithms_ , page 646–662. Cambridge University Press, 2021.  doi: 10.1017/9781108637435.037.
  * Mitzenmacher and Vassilvitskii [2022] M. Mitzenmacher and S. Vassilvitskii.  Algorithms with predictions.  _Commun. ACM_ , 65(7):33–35, 2022.
  * Myerson [1981] R. B. Myerson.  Optimal auction design.  _Mathematics of operations research_ , 6(1):58–73, 1981.
  * Nisan et al. [2007] N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani.  _Algorithmic Game Theory_.  Cambridge University Press, New York, NY, USA, 2007.
  * Parkes [2007] D. C. Parkes.  Online mechanisms.  In N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, editors, _Algorithmic Game Theory_ , page 411–440. Cambridge University Press, 2007\.  doi: 10.1017/CBO9780511800481.018.
  * Purohit et al. [2018] M. Purohit, Z. Svitkina, and R. Kumar.  Improving online algorithms via ML predictions.  In _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada_ , pages 9684–9693, 2018.
  * Xu and Lu [2022] C. Xu and P. Lu.  Mechanism design with predictions.  In L. D. Raedt, editor, _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022_ , pages 571–577. ijcai.org, 2022.

##  Appendix A Missing proofs from Section 3.2

See 5

###### Proof.

If $\tau=v^{\leq i_{1}}_{\max}$ in Line 1, it means that $v^{\leq
i_{1}}_{\max}\geq\tilde{v}_{(1)}$. First note that $\tau$ will never equal to
$\tilde{v}_{(1)}$, implying $p=\tau$. Consider the case where the winner is
above the threshold before the $i_{2}$-th bidder departs, then the allocation
is terminated before the possible update of $\tau$, making $p=\tau=v^{\leq
i_{1}}_{\max}$. Consider the case where the winner, denoted as $i^{*}$ is
above the threshold after the departure of the $i_{2}$-th bidder, then
$v^{\leq i_{2}}_{\max}=v^{\leq i_{1}}_{\max}$, since there are no bidder with
value higher than $\tau=v^{\leq i_{1}}_{\max}$ before bidder $i^{*}$, in this
case the payment is also $v^{\leq i_{1}}_{\max}$. ∎

See 5

###### Proof.

First, note that if such a bidder, denoted as $i$, reports her type
truthfully, she won’t receive the item. The only way she can possibly win the
item is by reporting a value $\hat{v}_{i}\geq\tau$. However, since, as
observed in Observation 5, in the case of a single threshold, the price
$p=\tau>v_{i}$, bidder $i$ would incur non-positive utility if she were to
obtain the item. ∎

See 5

###### Proof.

By Lemma 5, we already have that the bidders with the first $i_{1}$ departures
has no incentive to misreport. Note that the threshold $\tau$, and therefore
the payment $p$, is independent of the rest of the bidders’ reports. First if
bidder $i$, with her true type, wins the auction, then she has no incentive to
misreport since the price is independent of her report. We now consider some
bidder $i$ with $v_{i}\geq\tau$ but bidder $i$ is not the winner. This can
only result from one of the following two scenarios: 1. Some other bidder $j$
is above the threshold before bidder $i$ is above the threshold. 2. bidder $i$
and some bidder $j$ are above the threshold at the same time, but bidder $i$
loses in tie-breaking. We will now address these two cases separately.

Case one: Since in the single-threshold case $\tau$ is not updated after Line
1, it means that bidder $j$ is above the threshold before the arrival time of
bidder $i$. For bidder $i$ to claim the item, she would need to report an
earlier arrival time $\hat{a}_{i}<a_{i}$ to be above the threshold weakly
earlier than bidder $j$. However, this is not a feasible outcome since we
assume bidders cannot report $\hat{a}_{i}<a_{i}$.

Case two: First, note that by the definition of our auction and the fact that
$v_{i}\geq\tau$, the only possible tie-breaking happens at Line 1 after $\tau$
changes from $\infty$ to $v^{\leq i_{1}}_{\max}$. Since the tie-breaking rules
are independent of bidders’ reports, there is no way for bidder $i$ to change
the results of the tie-breaking. Additionally, since the threshold is $\infty$
before this point, there is also no way for bidder $i$ to misreport her type
to win the item. ∎

See 6

###### Proof.

First, note that if such a bidder, denoted as $i$, reports her type
truthfully, she won’t receive the item. The only way she can possibly win the
item is by reporting a value $\hat{v}_{i}\geq\tau_{2}$. However, since the
price $p\geq\tau_{2}>v_{i}$, bidder $i$ would incur negative utility if she
were to obtain the item. ∎

See 6

###### Proof.

Consider some bidder $i$ with $v_{i}\geq\tau_{1}$ but bidder $i$ is not the
winner. First note that if $i\leq i_{1}$ by Lemma 5 she has no incentive to
misreport. Consider any $i\geq i_{1}$ but $i$ is not the winner. Then it can
only result from one of the following two scenarios: 1. Some other bidder $j$
is above the threshold before bidder $i$ is above the threshold. 2. bidder $i$
and some bidder $j$ are above the threshold at the same time, but bidder $i$
loses in tie-breaking. We will now address these two cases separately.

Case one: Since $v_{i}\geq\tau_{1}$, it means that bidder $j$ is above the
threshold before the arrival time of bidder $i$. For bidder $i$ to claim the
item, she would need to report an earlier arrival time $\hat{a}_{i}<a_{i}$ to
be above the threshold weakly earlier than bidder $j$. However, this is not a
feasible outcome since we assume bidders cannot report $\hat{a}_{i}<a_{i}$.

Case two: First, note that by the definition of our auction and the fact that
$v\geq\tau_{1}$, the only possible tie-breaking happens at Line 1 after $\tau$
changes from $\infty$ to $v^{\leq i_{1}}_{\max}$. Since the tie-breaking rules
are independent of bidders’ reports, there is no way for bidder $i$ to change
the results of the tie-breaking. Additionally, since the threshold is $\infty$
before this point, there is also no way for bidder $i$ to misreport her
arrival as earlier to win the item. ∎

##  Appendix B Missing Proofs from Section 3.3

See 3.3

###### Proof.

We first prove that the worst case expected revenue is always bounded by
$\frac{1-\alpha^{2}}{4}v_{(2)}$. The argument is identical to the proof of
Lemma 4, but changing the case conditions from $\tilde{v}_{(1)}>v_{(1)}$ and
$\tilde{v}_{(1)}\leq v_{(1)}$ to $\gamma\tilde{v}_{(1)}>v_{(1)}$ and
$\gamma\tilde{v}_{(1)}\leq v_{(1)}$, respectively.

We now prove the $\alpha\gamma qv_{(1)}$ bound when the prediction is
relatively accurate, i.e., $q\geq\gamma$. First by the definition of $q$ we
have $q\tilde{v}_{(1)}\leq v_{(1)}\leq\frac{\tilde{v}_{(1)}}{q}$. Suppose
$q\geq\gamma$, then $\gamma\tilde{v}_{(1)}\leq q\tilde{v}_{(1)}\leq v_{(1)}$.
Consider the same instance we consider in Lemma 3, where the highest value
agent $i^{*}\in[i_{1}+1,i_{2}]$, i.e., agent $i^{*}$ in the second phase.
First note that she will get the item and pay $\tau$, since
$v_{(1)}\geq\gamma\tilde{v}_{(1)}$ and $v_{(1)}\geq v_{\max}$. In addition,
the threshold
$\tau=\max(\gamma\tilde{v}_{(1)},v_{\max})\geq\gamma\tilde{v}_{(1)}$. In this
case the revenue achieved is at least

$\tau\geq\gamma\tilde{v}_{(1)}\geq\gamma qv_{(1)}.$

Since such instance happens with probability $\frac{i_{2}-i_{1}}{n}=\alpha$.
We therefore have that the expected revenue is at least $\alpha\gamma
qv_{(1)}$ when $q\geq\gamma$.

Lastly, we note that the strategyproof argument for auction Error-Tolerant is
identical to that for auction Three-Phase. ∎