# Optimal Price Discrimination for Randomized Mechanisms

Shao-Heng Ko  Computer Science Department, Duke UniversityDurhamNCUSA
<EMAIL_ADDRESS>and  Kamesh Munagala  Computer Science Department, Duke
UniversityDurhamNCUSA<EMAIL_ADDRESS>
###### Abstract.

We study the power of price discrimination via an intermediary in bilateral
trade, when there is a revenue-maximizing seller selling an item to a buyer
with a private value drawn from a prior. Between the seller and the buyer,
there is an intermediary that can _segment_ the market by releasing
information about the true values to the seller. This is termed signaling, and
enables the seller to price discriminate. In this setting, Bergemann et al.
(Bergemann15) showed the existence of a signaling scheme that simultaneously
raises the optimal consumer surplus, guarantees the item always sells, and
ensures the seller’s revenue does not increase.

Our work extends the positive result of Bergemann et al. to settings where the
type space is larger, and where the optimal auction is randomized, possibly
over a menu that can be exponentially large. In particular, we consider two
settings motivated by budgets: The first is when there is a publicly known
budget constraint on the price the seller can charge (Chawla11) and the second
is the FedEx problem (Fiat16) where the buyer has a private deadline or
service level (equivalently, a private budget that is guaranteed to never
bind). For both settings, we present a novel signaling scheme and its analysis
via a continuous construction process that recreates the optimal consumer
surplus guarantee of Bergemann et al. and further subsumes their signaling
scheme as a special case. In effect, our results show settings where even
though the optimal auction is randomized over a possibly large menu, there is
a market segmentation such that for each segment, the optimal auction is a
simple posted price scheme where the item is always sold.

The settings we consider are special cases of the more general problem where
the buyer has a private budget constraint in addition to a private value. We
finally show that our positive results do not extend to this more general
setting, particularly when the budget can bind in the optimal auction, and
when the seller’s mechanism allows for all-pay auctions. Here, we show that
any efficient signaling scheme necessarily transfers almost all the surplus to
the seller instead of the buyer.

bilateral trade, auctions, signaling

††ccs: Theory of computation Algorithmic game theory††ccs: Mathematics of
computing Probabilistic algorithms

##  1\. Introduction

A canonical problem in mechanism design is that of bilateral trade – a single
seller selling an item to a buyer or equivalently, an infinite supply of
identical items to a stream of buyers. We assume the item has no value to the
seller. Typically, the buyers directly interact with the seller, who given
distributional knowledge of the buyer’s private valuation, runs an incentive
compatible mechanism in order to maximize its own revenue. This mechanism is
termed the optimal auction, which in this case is just a “take it or leave it”
(or monopoly) price offered to the buyer (Myerson81). Such a mechanism could
potentially lead to loss in social welfare, since the item is unsold if the
value of the buyer falls below the monopoly price.

Price Discrimination via an Intermediary. Now imagine a platform or exchange
that mediates the interaction between the buyers and the seller. This
intermediary observes the private value of each arriving buyer, and it uses
this information to segment the market of buyers by providing additional
information (or a signal) to the seller. The seller uses this signal (or
additional information) to price discriminate between different types of
buyers by running separate optimal auctions for each signal. Such
intermediaries are motivated by modern platforms such as ad exchanges
(doubleclick; msads; verizon; pubmatic), which help buyers (in this case,
advertisers) interact with sellers (in this case, publishers of content). The
ad exchange is usually run by a search engine or social media company that can
use its own data to accurately learn values of advertisers for various ad
slots, and selectively release this information to the publishers who then set
the prices based on this information.

Such an intermediary clearly benefits the seller’s revenue; after all, the
seller has more information that enables it to price discriminate. Counter-
intuitively, as shown by Bergemann, Brooks, and Morris (Bergemann15), it can
also lead to more utility for the buyers, and hence larger social welfare! In
fact, the main result of (Bergemann15) is remarkable – there is a signaling
scheme such that the item always sells (so that the social welfare is as large
as possible), while the seller’s revenue is the same as that without
signaling. Therefore, the entire extra social surplus due to signaling goes to
the buyer as its utility (or its consumer surplus). This is the best possible
outcome buyers can expect given that the seller controls the auction (or the
pricing scheme).

Though this result is striking, the underlying setting is the simplest
possible – there is one seller and one buyer (bilateral trade), so that the
optimal auction given distributional information about the buyer’s valuation
(either with or without signaling) is a posted price scheme that can be
computed in closed form. Given a prior distribution $\mathcal{G}$ on the
valuation of the buyer with a monopoly price $p$, the algorithms in
(Bergemann15) sequentially construct signals while maintaining the invariant
that at any step, the monopoly price of the residual distribution after
subtracting the signals constructed so far remains $p$. This strong invariant
seems critical to the guarantee on social optimality achieved in
(Bergemann15). This makes the positive results appear specific to this
setting. The question we ask in this paper is:

> Can the positive results in (Bergemann15) be extended to significantly more
> general settings where the optimal auction need not be so simple?

In this paper, we answer this question in the affirmative by extending the
positive results in (Bergemann15) to settings where the optimal auction can be
randomized, even with exponential menu complexity.111In randomized auctions
where the outcome for each buyer type is a (payment, allocation) pair, one can
equivalently view the collection of all such pairs as a menu, from which the
buyers can choose the best one for them. This encodes incentive compatibility.
The menu complexity refers to the size of this set.

Concretely, we study the setting where the type space of the buyer is
discrete, and includes not only their private value for the item, but also a
budget or deadline. Our positive results concern two settings. In the first
setting, there is a publicly known upper bound on the price any buyer can be
charged; this is termed the public budget setting in literature (Chawla11;
Laffont96). In the second setting, the buyer has a private deadline by which
time they need to receive the item; receiving it later than the deadline
yields the buyer no value. This can be equivalently viewed as a private
service level for the product. The private values and deadlines are assumed to
be drawn from an arbitrary two-dimensional discrete prior distribution. The
auction thus needs to be incentive compatible in the sense that the buyer
should not derive more utility by reporting a tighter deadline. This is termed
the FedEx problem in literature (Fiat16; Saxena18).

In both settings, the optimal auction can be randomized. In the public budget
case, the randomization is over two possible menu options (Chawla11), while
for the FedEx case, the randomization can be over a menu that can be
exponentially large in the number of deadlines (Fiat16; Devanur17; Saxena18).

###  1.1. Our Results

Our main contribution is a novel signaling scheme for price discrimination in
bilateral trade for the two settings of public budgets and the FedEx problem
mentioned above. We show that this scheme recreates the guarantee in
(Bergemann15) – it achieves full social welfare (that is, it always sells the
item), while ensuring the seller’s revenue is the same as without signaling,
thereby transferring all excess social surplus to the buyer. In particular,
this shows the following surprising corollary: For both these problems, even
though the optimal auction is randomized in general, there is a decomposition
of the prior distribution into a collection of signals such that for each
signal, the optimal auction is a simple posted price scheme where the item is
always sold.

The first technical highlight of our paper is a reinterpretation of the
signaling schemes for bilateral trade in (Bergemann15) as a continuous time
process. In this process, an infinitesimal quantity of a signal is
continuously removed from the prior distribution, and we maintain two
invariants at any time instant: (a) An optimal auction for the signal being
removed is efficient; and (b) the revenue for this signal is exactly equal to
the rate of decrease in revenue of the optimal auction on the current prior
distribution. We use the Envelope Theorem (Milgrom) to essentially show that
any algorithm that satisfies invariants (a) and (b) recreates the guarantee in
(Bergemann15), regardless of how complex the optimal auction for the setting
in consideration is. The advantage of this approach is that it enables us to
sidestep both the fine-grained characterization in (Bergemann15) of how the
prior changes when signals are removed from it, as well as proving their
invariant that the optimal auction is preserved as signals are removed from
the prior.

The continuous framework provides a unifying method to analyze signaling
schemes for both the public budget and the private deadline settings. However,
we still need a careful choice of how to run the continuous process so that
the two invariants hold. This is particularly challenging for the FedEx
problem, since the type space here is two-dimensional, representing the values
and deadlines. As we show later, a naive approach that applies the scheme in
(Bergemann15) separately to the marginal induced by each deadline raises too
little consumer surplus. We therefore need to develop an approach that
carefully hides both the value and deadline information, and our main
algorithmic contribution is the development of a novel signaling method in
such spaces (Section 4) that achieves precisely this. This forms our second
technical highlight.

Our signaling scheme and analysis require discrete (finite support) priors
over valuations. Following (RubinsteinW; cai2021duality), such priors are also
an arbitrary good approximation for continuous priors via discretization. Our
analysis requires a characterization of the optimal auctions in this setting,
which we present in Theorems 3.4 and 4.11. These are the discrete analogs of
results in (Chawla11; Fiat16) for continuous priors, and show that the optimal
auction is a distribution over posted prices that satisfy certain nice
properties. The characterizations we require are much coarser than those in
(Chawla11; Fiat16) and we present stand-alone alternate proofs of these
properties that are tailored to the discrete nature of the priors. In
particular, the proof for the deadline setting (Theorem 4.11) uses convexity
in the primal instead of duality, and this technique may be of independent
interest.

##### Impossibility for Private Budgets.

We finally ask how far we can push this positive result. Towards this end, we
consider the generalization of the above settings to the private budget
setting (Che00; Devanur17). Here, the buyer has a private budget, and the
values and budgets are assumed to be drawn from an arbitrary two-dimensional
discrete prior distribution. The buyer cannot over-report her budget, but an
incentive compatible auction needs to prevent under-reporting it. We assume
interim rationality to allow for all-pay auctions, or equivalently, views the
item as infinitely divisible; this is a standard assumption in economics
literature (Che00; Laffont96). Note that the FedEx problem is a special case
where the budgets are larger than all valuations.

For private budgets, there is no signaling scheme that satisfies both criteria
(a) and (b) above. This leads to a strong lower bound: Even with two values
and two budgets, any efficient signaling scheme (that always sells the item)
transfers all surplus to the seller, leading to vanishingly small consumer
surplus. Therefore, no efficient signaling scheme can reproduce the consumer
surplus guarantee in (Bergemann15) to any approximation. Furthermore, even if
we sacrifice efficiency, we cannot hope to achieve better than a constant
approximation to the consumer surplus guarantee.

###  1.2. Related Work

Our problem falls in the general framework of information design
(bergemann2019information) where an information mediator can deliberately
provide additional information to impact the behavior of agents in given
mechanisms; this is also sometimes termed signaling or persuasion
(dughmi2017algorithmic). The Bayesian Persuasion model (Kamenica11) is a
special case of information design with only one agent (often called the
receiver) receiving additional information that comes from a sender with more
knowledge of the state of nature. Given the signal, the receiver chooses the
actions to maximize her own utility based on her belief of the state of nature
(which may be influenced by the signal). Therefore, the sender designs the
signals so that the receiver, acting in her own interest, maximizes some
utility function the sender cares about. This problem is studied from various
theoretical perspectives (dughmi2016persuasion; dughmi2019algorithmic;
Babichenko21) as well as in different application domains (Bergemann15;
chakraborty2014persuasive; xu2015exploring; ParetoIS).

Starting with the seminal work of Bergemann et al. (Bergemann15), there has
been a line of work (dughmi2016persuasion; shen2018closed;
cummings2020algorithmic; cai2020third; ParetoIS) on Bayesian persuasion in the
bilateral trade model and its extensions. In this context, the sender is an
intermediary and the receiver is the seller, who given the signal, implements
an incentive-compatible auction to maximize expected revenue. The sender, on
the other hand, is interested in maximizing consumer surplus or social
welfare. In the versions we study with budgets or deadlines, the receiver’s
action space is the set of all randomized pricing rules, instead of just the
posted prices in the basic setting (Bergemann15). Our main contribution is to
show the existence of socially efficient signaling schemes that preserve
receiver utility (the revenue) and maximally increases sender utility
(consumer surplus) despite this additional complexity. We note that for other
non-trivial extensions of bilateral trade, for instance, the multi-buyer
auction setting in (Alijani20) and the multi-item auction setting in
(ParetoIS), it may in general not be possible to find socially optimal
signaling schemes that preserve seller revenue. This makes our positive
results all the more surprising.

As mentioned before, our work crucially requires a characterization of optimal
randomized auction in the respective settings. For public budgets, Laffont and
Roberts (Laffont96) show that the optimal auction is a posted price scheme
assuming regular distributions; for general priors, Chawla et al. (Chawla11)
show it is a lottery over two options. Che and Gale (Che00) consider private
budgets with a decreasing marginal revenue assumption, and show it is a
different price curve for each budget. Fiat et al. (Fiat16) and subsequently
Devanur and Weinberg (Devanur17) use duality to respectively generalize this
characterization to private deadlines and private budgets with arbitrary
priors; however, the characterization in the latter case is not closed form.
Since we use finite support priors, we present stand-alone proofs of the
required characterizations, and these may be of independent interest.

##### Organization.

In Section 2, we present preliminaries for optimal auction design and
signaling. In Section 3, we present the signaling scheme and analysis for the
public budget case. In Section 4, we present our main result – the new
signaling scheme for the FedEx problem, where the deadlines are private. In
Section 5, we present the impossibility result for the private budget setting
with interim rationality. All omitted proofs are in the Appendix.

##  2\. Preliminaries

###  2.1. Optimal Auctions with Budgets

We consider a single seller selling an item to a single buyer with private
valuation $v$ and private budget $b$ as a hard upper bound of payment. It is
known that optimal auctions with budgets require randomized allocations
(Chawla11; Che00; Devanur17): The buyer’s utility is $(x\cdot v-p)$ if she
pays a price of $p\leq b$ to get the item with probability $x\in[0,1]$, and is
$-\infty$ if $p>b$. Throughout the paper, we focus on interim IR auctions
where the buyer pays at most $b$ before learning whether or not she receives
the item. As mentioned before, this is the standard model for studying budget
constrained auctions in economics literature (Che00; Laffont96), and allows
for all-pay auctions. 222We note that the algorithms in Sections 3 and 4
construct signals whose optimal auctions are deterministic and satisfy ex-post
IR, meaning that the price charged is always at most the budget. However, our
lower bounds in Section 5 assume interim IR, and extending this to ex-post IR
is an open question. Alternatively, it models ex-post rationality assuming the
item is infinitely divisible, and $x\in[0,1]$ represents the fraction of the
item the buyer obtains at price $p$.

The joint distribution $(v,b)\sim\mathcal{G}$ is common knowledge and
supported on a discrete set
$\text{supp}(\mathcal{G})\coloneqq\\{v_{1},\ldots,v_{n}\\}\times\\{b_{1},\ldots,b_{k}\\}$,
where $0<v_{1}<\cdots<v_{n}$ and $0<b_{1}<\cdots<b_{k}$. For $j=1,2,\ldots,k$,
let $\mathcal{G}_{j}$ represent the marginal distribution of $v$ given
$b=b_{j}$, and define $f_{\mathcal{G}_{j}}$ as the probability mass function
of $\mathcal{G}_{j}$, i.e.,
$f_{\mathcal{G}_{j}}(v_{i})=\Pr_{v\sim\mathcal{G}_{j}}[v=v_{i}]=\Pr_{(v,b)\sim\mathcal{G}}[v=v_{i}\mid
b=b_{j}].$ Let
$\underline{F}_{\mathcal{G}_{j}}(v_{i})=\Pr_{v\sim\mathcal{G}_{j}}[v\leq
v_{i}]$ and
$\overline{F}_{\mathcal{G}_{j}}(v_{i})=\Pr_{v\sim\mathcal{G}_{j}}[v\geq
v_{i}]$. We assume the item holds no value to the seller; therefore, the
maximum social welfare is
$\textsf{SW}^{\ast}(\mathcal{G})=\operatorname*{\mathbbm{E}}_{(v,b)\sim\mathcal{G}}[v]$,
and is achieved by any auction that always makes the trade happen (or sells
the item).

##### Optimal Auctions.

It is known (Myerson81; Laffont96; Chawla11; Che00; Devanur17) that the
revenue maximizing auction for the seller can be described using lotteries or
randomized allocation rules. Specifically, each buyer type with valuation
$v_{i}$ and budget $b_{j}$ is associated to a payment $p_{ij}\geq 0$ and an
allocation probability $x_{ij}\in[0,1]$ to receive the item. Note that in the
interim-IR setting the buyer pays $p_{ij}$ upfront regardless of whether she
receives the item.

Following (Che00; Devanur17), we assume buyer with type $(v_{i},b_{j})$ cannot
report a budget larger than $b_{j}$.333Our positive results in Sections 3 and
4 either assume the budget is publicly known, or assume deadlines instead of
budgets, so this point is moot there. It is only relevant for the lower bounds
in Section 5. We can enforce this by a cash bond that requires the full
reported budget. We note that the setting where the IC constraints are only
enforced for smaller budgets is more challenging for designing optimal
auctions (Che00). By the revelation principle, it is sufficient to consider
lotteries that are incentive compatible, i.e., for all $i$ and $j$, a buyer of
type $(v_{i},b_{j})$ receives maximum possible utility from reporting her true
type $(v_{i},b_{j})$ and thereby receiving the item with allocation
probability $x_{ij}$ at price $p_{ij}$.

The revenue optimal auction can be computed by the following LP from
(Devanur17).

$\displaystyle\textsf{Budgets}(\mathcal{G})$
$\displaystyle\coloneqq\max_{\\{p_{ij}\\},\\{x_{ij}\\}}\quad\sum_{j=1}^{k}\left(\Pr[b=b_{j}]\cdot\sum_{i=1}^{n}\big{(}f_{\mathcal{G}_{j}}(v_{i})\cdot
p_{ij}\big{)}\right)$ (Same-budget IC) s.t. $\displaystyle v_{i}\cdot
x_{ij}-p_{ij}\geq v_{i}\cdot x_{i^{\prime}j}-p_{i^{\prime}j},$
$\displaystyle\quad\forall 1\leq i,i^{\prime}\leq n,$ $\displaystyle\,1\leq
j\leq k,$ (Inter-budget IC) $\displaystyle v_{i}\cdot x_{ij}-p_{ij}\geq
v_{i}\cdot x_{i(j-1)}-p_{i(j-1)},$ $\displaystyle\quad\forall 1\leq i\leq n,$
$\displaystyle\,2\leq j\leq k,$ (IR) $\displaystyle v_{i}\cdot
x_{ij}-p_{ij}\geq 0,$ $\displaystyle\quad\forall 1\leq i\leq n,$
$\displaystyle\,1\leq j\leq k,$ (Feasibility) $\displaystyle 0\leq x_{ij}\leq
1,$ $\displaystyle\quad\forall 1\leq i\leq n,$ $\displaystyle\,1\leq j\leq k,$
(Budgets) $\displaystyle p_{ij}\leq b_{j},$ $\displaystyle\quad\forall 1\leq
i\leq n,$ $\displaystyle\,1\leq j\leq k.$

By transitivity, the same-budget and inter-budget IC constraints imply all
necessary IC constraints so that the buyer with valuation $v_{i}$ and budget
$b_{j}$ does not misreport with some valuation $v_{i^{\prime}}\neq v_{i}$
and/or some budget $b_{j^{\prime}}<b_{j}$.

###### Definition 2.0.

For the revenue maximizing auction $(\\{p^{\ast}_{ij}\\},\\{x^{\ast}_{ij}\\})$
that is the optimal solution to Budgets$(\mathcal{G})$, denote

$\displaystyle\textsf{R}(\mathcal{G})$
$\displaystyle=\sum_{i,j}\big{(}\Pr[{\mathcal{G}}=(v_{i},b_{j})]\cdot
p^{\ast}_{ij}\big{)},$ $\displaystyle\textsf{SW}(\mathcal{G})$
$\displaystyle=\sum_{i,j}\big{(}\Pr[{\mathcal{G}}=(v_{i},b_{j})]\cdot
v_{i}\cdot x^{\ast}_{ij}\big{)},\ \ \mbox{and}$
$\displaystyle\textsf{CS}(\mathcal{G})$
$\displaystyle=\sum_{i,j}\big{(}\Pr[{\mathcal{G}}=(v_{i},b_{j})]\cdot(v_{i}\cdot
x^{\ast}_{ij}-p^{\ast}_{ij})\big{)}$

as the expected revenue (generated by the seller), the expected social
welfare, and the expected consumer surplus (generated for the buyer),
respectively. Then we have
$\textsf{CS}(\mathcal{G})+\textsf{R}(\mathcal{G})=\textsf{SW}(\mathcal{G})$.444If
there are multiple optimal auctions maximizing $\textsf{R}(\mathcal{G})$, we
break ties by defining $(\\{p^{\ast}_{ij}\\},\\{x^{\ast}_{ij}\\})$ to be the
auction that maximizes $\textsf{SW}(\mathcal{G})$ among the optimal solutions.
This auction must maximize $\textsf{CS}(\mathcal{G})$ as well.

We now specify two special cases of the budgeted problem for which we derive
positive results.

##### Optimal Auctions with Public Budget.

The first special case we consider is the public budget setting (Laffont96;
Chawla11) where $k=1$, the budget $b=b_{1}$ is public information, and the
only marginal distribution is $\mathcal{G}=\mathcal{G}_{1}$. This setting is
motivated by the seller having an upper bound on the price they can charge any
buyer, say due to regulation or other considerations.

In this case we omit the subscripts by referring to $f_{\mathcal{G}}(v_{i})$,
$\underline{F}_{\mathcal{G}}(v_{i})$, and $\overline{F}_{\mathcal{G}}(v_{i})$,
and use $p_{i}$ and $x_{i}$ as shorthand for the payment variables $p_{i1}$
and allocation variables $x_{i1}$, respectively. For this case, the optimal
auction is captured by the following special case of Budgets with $k=1$:

$\displaystyle\textsf{Public}(\mathcal{G})\coloneqq\max_{\\{p_{i}\\},\\{x_{i}\\}}\quad$
$\displaystyle\sum_{i=1}^{n}\big{(}f_{\mathcal{G}}(v_{i})\cdot p_{i}\big{)}$
(IC) s.t. $\displaystyle v_{i}\cdot x_{i}-p_{i}\geq v_{i}\cdot
x_{i^{\prime}}-p_{i^{\prime}},$ $\displaystyle\quad\forall 1\leq
i,i^{\prime}\leq n,$ (IR) $\displaystyle v_{i}\cdot x_{i}-p_{i}\geq 0,$
$\displaystyle\quad\forall 1\leq i\leq n,$ (Feasibility) $\displaystyle 0\leq
x_{i}\leq 1,$ $\displaystyle\quad\forall 1\leq i\leq n,$ (Budget)
$\displaystyle p_{i}\leq b,$ $\displaystyle\quad\forall 1\leq i\leq n.$

We devise price discrimination schemes for the public budget setting in
Section 3.

##### Optimal Auctions with Deadlines.

In this setting (Fiat16; Saxena18), we consider a single seller selling an
identical item with different levels of service quality to a single buyer. The
buyer now has private valuation $v$ (conditioned on getting the item with at
least her desired level of quality) and a private desired level of quality
$d$. One can think of $d$ as either a personal deadline for shipping options,
or as a level of service quality for a product. Keeping with previous work, we
will refer to $d$ as deadlines throughout.

The buyer’s utility is $(x\cdot v-p)$ if she pays a price of $p$ to get the
item with a probability of $x$ at some point before or right at her deadline.
She incurs utility $-p$ if she gets the item later than her deadline, since in
this case, she accrues no value from the item. As observed in (Fiat16), it is
sufficient to consider auctions that, for each buyer with deadline $d$, only
allocates the item right at the $d$-th deadline (if at all). This is because a
buyer does not get any additional utility if she receives the item at some
point earlier than her own deadline. Furthermore, the buyer weakly prefers
getting nothing over getting the item after her own deadline for some price.

The LP for this setting is a special case of the LP for the private budget
setting with large budgets, that is, when $v_{n}<b_{j}$ holds for all budget
types $j=1,\ldots,k$. As every budget is above the highest possible valuation,
by the IR constraint, the optimal auction never sets a price above $b_{j}$ for
any buyer with budget $b_{j}$, and thus the budget constraint $p_{ij}\leq
b_{j}$ in Budgets can be omitted.

For this case, we simplify the notations by denoting the joint distribution
$(v,d)\sim\mathcal{G}$ supported on
$\text{supp}(\mathcal{G})\coloneqq\\{v_{1},\ldots,v_{n}\\}\times\\{1,\ldots,k\\}$,
where $0<v_{1}<\cdots<v_{n}$. The deadlines can be represented as
$\\{1,\ldots,k\\}$ since their cardinal values do not matter. For
$j=1,2,\ldots,k$, $\mathcal{G}_{j}$ now represents the marginal distribution
of $v$ given $d=j$, and the corresponding probability mass function of
$\mathcal{G}_{j}$ is

$f_{\mathcal{G}_{j}}(v_{i})=\Pr\limits_{v\sim\mathcal{G}_{j}}[v=v_{i}]=\Pr\limits_{(v,d)\sim\mathcal{G}}[v=v_{i}\mid
d=j].$

Let $\underline{F}_{\mathcal{G}_{j}}(v_{i})=\Pr_{v\sim\mathcal{G}_{j}}[v\leq
v_{i}]$ and
$\overline{F}_{\mathcal{G}_{j}}(v_{i})=\Pr_{v\sim\mathcal{G}_{j}}[v\geq
v_{i}]$. We again assume the item holds no value to the seller; therefore, the
maximum social welfare is
${\textsf{SW}}^{\ast}(\mathcal{G})=\operatorname*{\mathbbm{E}}_{(v,d)\sim\mathcal{G}}[v]$,
and is achieved by any auction that always allocates the item to each buyer
right at her personal deadline.

The revenue maximizing randomized incentive compatible auction for the
deadlines setting is thus the following:

$\displaystyle\textsf{Deadlines}(\mathcal{G})\coloneqq\max_{\\{p_{ij}\\},\\{x_{ij}\\}}\quad\sum_{j=1}^{k}\left(\Pr_{(v,d)\sim\mathcal{G}}[d=j]\cdot\sum_{i=1}^{n}\big{(}f_{\mathcal{G}_{j}}(v_{i})\cdot
p_{ij}\big{)}\right)$ (Same-deadline IC) s.t. $\displaystyle v_{i}\cdot
x_{ij}-p_{ij}\geq v_{i}\cdot x_{i^{\prime}j}-p_{i^{\prime}j},$
$\displaystyle\quad\forall 1\leq i,i^{\prime}\leq n,\,1\leq j\leq k,$ (Inter-
deadline IC) $\displaystyle v_{i}\cdot x_{ij}-p_{ij}\geq v_{i}\cdot
x_{i(j-1)}-p_{i(j-1)},$ $\displaystyle\quad\forall 1\leq i\leq n,\,2\leq j\leq
k,$ (IR) $\displaystyle v_{i}\cdot x_{ij}-p_{ij}\geq 0,$
$\displaystyle\quad\forall 1\leq i\leq n,\,1\leq j\leq k,$ (Feasibility)
$\displaystyle 0\leq x_{ij}\leq 1,$ $\displaystyle\quad\forall 1\leq i\leq
n,\,1\leq j\leq k.$

Note that Deadlines is a special case of Budgets where the budget constraint
is omitted, and the IC constraints in Deadlines prevent misreporting a lower
deadline.

##### Remarks.

We first note that though our scheme require discrete priors over valuations,
these also serve as arbitrarily good approximations to continuous priors via
simple discretization (cai2021duality; RubinsteinW). Secondly, note that the
optimal auctions with interim IR coincides with that for ex-post IR for both
the public budget and the deadline setting; the former follows from Theorem
3.4 (or from (Chawla11)), while the latter follows because the prices are not
really constrained by any budget. Therefore, our positive results in Sections
3 and 4 extend as is to ex-post IR. Our negative results in Section 5 do
require interim IR.

###  2.2. Price Discrimination

We next introduce price discrimination via signaling by an information
intermediary for the general private budget setting; specializing it to
deadlines or public budgets is straightforward. The intermediary knows the
type $(v_{i},b_{j})$ of the buyer, and can propose a signaling scheme that
maps the buyer’s private information (i.e., a value-budget pair
$(v_{i},b_{j})$) to a distribution over signals that conveys additional
information to the seller. This makes the seller update her belief of the
buyer’s information via Bayes’ rule. The signaling scheme thus can be seen as
segmenting the market of buyers, each segment representing the conditional
distribution of buyer type given the signal. Therefore, we can overload
terminology and simply define a signal $\theta$ as the posterior distribution
of $(v,b)$ given the signal.

##### Signaling Scheme.

Formally, a signaling scheme $\Theta=\\{(\omega_{h},\theta_{h})\\}_{h\in[H]}$
is a collection of signals $\theta_{1},\ldots,\theta_{H}$ and probability
weights $\omega_{1},\ldots,\omega_{H}>0$, where $\sum_{h=1}^{H}\omega_{h}=1$.
Here $\theta_{h}$ represents the posterior distribution of the type given the
$h$-th signal. We also require $\Theta$ being Bayes plausible (Kamenica11),

(1) $\sum_{h=1}^{H}\omega_{h}\theta_{h}=\mathcal{G},$

i.e., the average signal is just the prior $\mathcal{G}$. The intermediary
commits to this signaling scheme before she observes the buyer type, and this
scheme is public knowledge to all parties.

We note that in general, collection of signals above could be a continuous
set, and the weights could represent a density over this set. This aspect will
not affect our algorithms, since the signaling schemes we construct in
Sections 3 and 4 will have finitely many signals. On the other hand, the lower
bound results in Section 5 hold even if the set of signals is uncountable.

Upon observing private information $(v,b)$, the intermediary sends the $h$-th
signal with probability
$\frac{\omega_{h}\cdot\Pr[\theta_{h}=(v,b)]}{\Pr[{\mathcal{G}}=(v,b)]}$, and
given this signal, if the seller uses Bayes rule to update the prior on the
buyer’s type, the posterior will be precisely $\theta_{h}$. The seller then
implements the revenue maximizing auction based on the updated prior
$\theta_{h}$.

##### Buyer Optimal Schemes.

Abusing the notation defined before, we let
$\textsf{R}(\Theta)=\sum_{h=1}^{H}\big{(}\omega_{h}\cdot\textsf{R}(\theta_{h})\big{)}$,
$\textsf{SW}(\Theta)=\sum_{h=1}^{H}\big{(}\omega_{h}\cdot\textsf{SW}(\theta_{h})\big{)}$,
and
$\textsf{CS}(\Theta)=\sum_{h=1}^{H}\big{(}\omega_{h}\cdot\textsf{CS}(\theta_{h})\big{)}$
denote the expected revenue, the expected social welfare, and the expected
consumer surplus, respectively, achieved by the signaling scheme $\Theta$,
where the expectation is now taken over all signals. As before, we have
$\textsf{CS}(\Theta)+\textsf{R}(\Theta)=\textsf{SW}(\Theta)$.

Furthermore, $\textsf{R}(\Theta)\geq\textsf{R}(\mathcal{G})$; otherwise, the
seller can ignore the signaling scheme $\Theta$ and implement the revenue
maximizing auction based on $\mathcal{G}$ instead. Hence, for any possible
signaling scheme $\Theta$, we have

$\textsf{CS}(\Theta)=\textsf{SW}(\Theta)-\textsf{R}(\Theta)\leq\textsf{SW}^{\ast}(\mathcal{G})-\textsf{R}(\mathcal{G})$

as an upper bound of the expected consumer surplus. Recall that
${\textsf{SW}}^{\ast}(\mathcal{G})$ is the maximum possible social welfare
assuming the item always sells. We define this bound on maximum achievable
consumer surplus as

$\textsf{CS}^{\ast}(\mathcal{G})\coloneqq\textsf{SW}^{\ast}(\mathcal{G})-\textsf{R}(\mathcal{G})=\operatorname*{\mathbbm{E}}\limits_{(v,b)\sim\mathcal{G}}[v]-\textsf{R}(\mathcal{G}).$

To achieve $\textsf{CS}(\Theta)=\textsf{CS}^{\ast}({\mathcal{G}})$, the
signaling scheme $\Theta$ thereby needs to satisfy (a) the item always sells,
and (b) the revenue $\textsf{R}(\Theta)$ generated by $\Theta$ is exactly
$\textsf{R}(\mathcal{G})$, i.e., the expected revenue without signaling. We
call a signaling scheme _buyer optimal_ if it achieves this upper bound.

###  2.3. Buyer Optimal Signaling without Budgets or Deadlines

We illustrate the concept of signaling via the following example.

###### Example 2.0.

Consider a simple two-point distribution where $v=1$ and $3$ each with
probability $\frac{1}{2}$. Then the maximum social welfare is
$\textsf{SW}^{\ast}(\mathcal{G})=\frac{1}{2}\cdot 1+\frac{1}{2}\cdot 3=2$. To
map to the notation above, we assume the budget is $b=3$, so that the type is
$(v,b)=(1,3)$ and $(3,3)$ with probability $1/2$ each; this budget is
irrelevant to the computations below. The revenue maximizing auction is a
single posted price $p=3$, which raises a revenue
$\textsf{R}(\mathcal{G})=3\cdot\frac{1}{2}=\frac{3}{2}$, whereas the consumer
gets no surplus (i.e., $\textsf{CS}(\mathcal{G})=0$).

Consider a signaling scheme $\Theta$ that segments $\mathcal{G}$ into two
signals $\theta_{1}$ and $\theta_{2}$ as follows:
$\Pr_{(v,b)\sim\theta_{1}}[(v,b)=(1,3)]=\frac{2}{3}$,
$\Pr_{(v,b)\sim\theta_{1}}[(v,b)=(3,3)]=\frac{1}{3}$, and
$\Pr_{(v,b)\sim\theta_{2}}[(v,b)=(3,3)]=1$. They are given weights
$\omega_{1}=\frac{3}{4}$ and $\omega_{2}=\frac{1}{4}$. If the intermediary
observes the buyer with type $(v,b)=(1,3)$, $S_{1}$ is released with
probability
$\omega_{1}\cdot\frac{\Pr[\theta_{1}=(1,3)]}{\Pr[{\mathcal{G}}=(1,3)]}=\frac{3}{4}\cdot\frac{2/3}{1/2}=1$;
on the other hand, if the buyer has type $(v,b)=(3,3)$, the intermediary
releases $S_{1}$ or $S_{2}$ with equal probability, since
$\omega_{1}\cdot\frac{\Pr[\theta_{1}=(3,3)]}{\Pr[{\mathcal{G}}=(3,3)]}=\frac{3}{4}\cdot\frac{1/3}{1/2}=\frac{1}{2}=\frac{1}{4}\cdot\frac{1}{1/2}=\omega_{2}\cdot\frac{\Pr[\theta_{2}=(3,3)]}{\Pr[{\mathcal{G}}=(3,3)]}$.

Again, since the budget is not relevant, the revenue maximizing auctions in
$\theta_{1}$ and $\theta_{2}$ are posted prices $p_{1}=1$ and $p_{2}=3$,
respectively. The expected revenue raised by the seller in this signaling
scheme is
$\textsf{R}(\Theta)=\omega_{1}\cdot\textsf{R}(\theta_{1})+\omega_{2}\cdot\textsf{R}(\theta_{2})=\frac{3}{4}\cdot
1+\frac{1}{4}\cdot 3=\frac{3}{2}=\textsf{R}(\mathcal{G})$. The consumer
surplus for the buyer is now
$\textsf{CS}(\Theta)=\omega_{1}\cdot\textsf{CS}(\theta_{1})+\omega_{2}\cdot\textsf{CS}(\theta_{2})=\frac{3}{4}\cdot\frac{1}{3}\cdot(3-1)+\frac{1}{4}\cdot
0=\frac{1}{2}$. Finally, since the item always sells, the expected social
welfare is exactly at $\textsf{SW}^{\ast}(\mathcal{G})=2$.

In this example, the optimal consumer surplus
$\textsf{CS}^{\ast}(\mathcal{G})$ is indeed achieved by the signaling scheme
$\Theta$. This is not a coincidence, but an example of the “optimal signaling
schemes” given by Bergemann et al. (Bergemann15). We restate their main result
for the case of no budgets or deadlines:

###### Theorem 2.3 (Bergemann et al. ’s signaling schemes (Bergemann15)).

Suppose $k=1$ and $b_{1}\geq v_{n}$. Then for any arbitrary prior
$\mathcal{G}$, there exists a signaling scheme $\Theta_{\mathcal{G}}$ that
guarantees:

  1. (1)

efficiency:
$\textsf{SW}(\Theta_{\mathcal{G}})=\textsf{SW}^{\ast}(\mathcal{G})$ (i.e., the
item always sells);

  2. (2)

minimum revenue: $\textsf{R}(\Theta_{\mathcal{G}})=\textsf{R}(\mathcal{G})$
(i.e., the seller’s revenue does not increase);

  3. (3)

maximum consumer surplus:
$\textsf{CS}(\Theta_{\mathcal{G}})=\textsf{CS}^{\ast}(\mathcal{G})=\textsf{SW}^{\ast}(\mathcal{G})-\textsf{R}(\mathcal{G})$
(i.e., the scheme maximizes the expected consumer surplus among all possible
signaling schemes.)

Note that the third property is implied from the first two. There are multiple
constructions of $\Theta_{\mathcal{G}}$ given in (Bergemann15), and one of
these is equivalent to our scheme for public budgets presented in Section 3.
These schemes proceed via the notion of _Equal Revenue Signals_. We now
introduce this notion since it is essential to our signaling scheme as well.

###### Definition 2.0 (Equal Revenue Signals).

A valuation distribution $\theta$ over its support set
$\text{supp}(\theta)=\\{v_{1},\ldots,v_{n}\\}$ is equal revenue if it
satisfies:

$\overline{F}_{\theta}(v_{1})\cdot v_{1}=\overline{F}_{\theta}(v_{2})\cdot
v_{2}=\cdots=\overline{F}_{\theta}(v_{n})\cdot v_{n}=\textsf{R}(\theta).$

In other words, assuming no budgets, every valuation with nonzero probability
mass in $\text{supp}(\theta)$ is an optimal monopoly price for $\theta$. This
distribution is unique and can be obtained as follows:

$\displaystyle f_{\theta}(v_{1})=1-\frac{v_{1}}{v_{2}};\quad
f_{\theta}(v_{i})=\big{(}1-\underline{F}_{\theta}(v_{i-1})\big{)}\cdot(1-\frac{v_{i}}{v_{i+1}}),\,\forall
2\leq i\leq n-1;\quad f_{\theta}(v_{n})=1-\underline{F}_{\theta}(v_{n-1}).$

##  3\. Warmup: Signaling Scheme for Public Budgets

In this section, we prove the analog of Theorem 2.3 when there is a public
budget. We show that there is a signaling scheme that is buyer optimal with a
public budget. We will show this via reinterpreting the algorithm in
(Bergemann15) as a continuous time process (Algorithm 1 below). The nice
aspect of this interpretation is that it leads to a different proof of
optimality (than (Bergemann15)) via invoking the Envelope Theorem (Milgrom) on
the revenue of the residual prior as a function of time. This continuous time
interpretation will form the building blocks for our main result for the
version with deadlines (the FedEx problem) in Section 4.

Interestingly, our signaling scheme for public budgets is the same as the no-
budget signaling scheme in (Bergemann15); this is easy to check and we omit
the proof. However, our analysis is entirely different and more generalizable
to the more complex deadline setting considered later.

###  3.1. Signaling Algorithm

Throughout this section, the buyer’s budget $b=b_{1}$ is public information,
and we use $\mathcal{G}$ to denote the prior over the buyer values
$\\{v_{1},v_{2},\ldots,v_{n}\\}$. We view the progress of the algorithm as
continuously decreasing this prior into a residual prior, and continuously
placing the remaining probability mass into the constructed signals.

We use the function $\vec{\mathbf{f}}(t)=\langle
f_{1}(t),\ldots,f_{n}(t)\rangle$ to represent the residual prior, where
$f_{i}(t)$ represents the remaining probability mass on type $v_{i}$ in the
residual prior distribution at time $t$. Strictly speaking,
$\vec{\mathbf{f}}(t)$ is not a distribution since the process we describe only
guarantees $\sum_{i=1}^{n}f_{i}(t)<1$ for $t>0$. To make this a valid
distribution, we place the remaining probability mass
$1-\sum_{i=1}^{n}f_{i}(t)$ at a dummy value $v_{0}=0$. We call the resulting
distribution $\mathcal{G}(t)$. In the subsequent discussion, the notation
$\vec{\mathbf{f}}(t)$ represents the probability mass of $\mathcal{G}(t)$ at
non-zero valuations, and we omit explicitly considering the dummy value
$v_{0}=0$ as part of the support of $\mathcal{G}(t)$. We define
$\text{supp}(\mathcal{G}(t))\coloneqq\\{v_{i}>0\mid f_{i}(t)>0\\}$ and
$v_{\min}(\mathcal{G}(t))\coloneqq\min\\{v_{i}>0\mid f_{i}(t)>0\\}$.

We start with the prior $\mathcal{G}(0)=\mathcal{G}$ and let
$f_{i}(0)=f_{\mathcal{G}}(v_{i})$, i.e., $\vec{\mathbf{f}}(0)$ is just the
probability vector associated with $\mathcal{G}$. Our algorithm continuously
takes away probability mass from $\vec{\mathbf{f}}(t)$ and transfers it to the
constructed signals, terminating when $\vec{\mathbf{f}}(t)$ becomes
$\mathbf{0}$; denote the latter time as $T$.

At any time $t$ such that $\vec{\mathbf{f}}(t)\neq\mathbf{0}$, we denote
$\vec{\mathbf{s}}(t)$ as the probability distribution associated with the
equal revenue distribution (see Definition 2.4) $\theta(t)$ over the set of
values in $\text{supp}(\mathcal{G}(t))$. Note that $\vec{\mathbf{s}}(t)$
depends on $\text{supp}(\mathcal{G}(t))$ but not the $f_{i}(t)$; therefore, it
is fixed as long as $\text{supp}(\mathcal{G}(t))$ does not change.555Note that
there exist other equal revenue distributions over different support sets; for
example, any distribution with a support size of one is equal revenue.
However, for the purpose of our algorithm, the equal revenue distribution must
use all remaining nonzero valuations with nonzero probability mass in the
residual prior. Our algorithm continuously reduces $\vec{\mathbf{f}}(t)$ at
rate $\vec{\mathbf{s}}(t)$ until $\vec{\mathbf{f}}$ becomes $\mathbf{0}$.
Formally:

(2) $\displaystyle\derivative{\vec{\mathbf{f}}}{t}(t)=-\vec{\mathbf{s}}(t).$

Since $\sum_{i=1}^{n}s_{i}(t)=1$, the rate of decrease of
$\sum_{i=1}^{n}f_{i}(t)$ is also $1$. Since $\sum_{i=1}^{n}f_{i}(0)=1$, this
means the process terminates at time $T=1$.

##### Signals constructed.

We say the type-$i$ valuation $v_{i}$ is exhausted at time $t$ if $f_{i}(t)=0$
but $f_{i}(t^{\prime})>0$ for all $t^{\prime}<t$. The algorithm therefore
terminates once all types are exhausted. Consider a maximal time interval
$t\in[t_{1},t_{2})$ in which $\text{supp}(\mathcal{G}(t))$ remains fixed;
denote the equal revenue signal in this interval by $\vec{\mathbf{s}}$.
Therefore, $\theta(t)=\vec{\mathbf{s}}$ for $t\in[t_{1},t_{2})$. Then we have:

(3)
$\vec{\mathbf{f}}(t_{1})-\vec{\mathbf{f}}(t_{2})=-\int_{t=t_{1}}^{t_{2}}-\vec{\mathbf{s}}(t)\differential{t}=(t_{2}-t_{1})\cdot\vec{\mathbf{s}}$

Therefore, the final scheme includes a signal $\vec{\mathbf{s}}$ with weight
$(t_{2}-t_{1})$. This holds for every such interval $[t_{1},t_{2})$. Since
$\vec{\mathbf{s}}(t)$ changes only if some element in $\vec{\mathbf{f}}(t)$
becomes zero, the number of signals constructed is at most $n$. The signaling
scheme is now formally described in Algorithm 1.

We have
$\sum_{h=1}^{H}\omega^{\ast}_{h}=\sum_{h=1}^{H}(t_{h}-t_{h-1})=t_{H}-t_{0}=1$.
Further, we have Bayes plausibility (as defined in Eq. (1) in Section 2):

###### Observation 3.1.

For any arbitrary $\mathcal{G}$, let
$\Theta^{\ast}_{\mathcal{G}}=\\{(\omega^{\ast}_{h},\theta^{\ast}_{h})\\}_{h\in[H]}$
be the set of signals output by Algorithm 1 taking $\mathcal{G}$ as input.
Then we have $H\leq|\text{supp}(\mathcal{G})|$, and
$\sum_{h=1}^{H}\omega^{\ast}_{h}\theta^{\ast}_{h}=\mathcal{G}$.

###### Proof.

By summing up Eq. (3) for all pairs $[t_{h-1},t_{h})$ for
$h\in\\{1,\ldots,H\\}$ we have

$\displaystyle\vec{\mathbf{f}}(0)=\vec{\mathbf{f}}(0)-\vec{\mathbf{f}}(1)=\vec{\mathbf{f}}(t_{0})-\vec{\mathbf{f}}(t_{H})=\sum\limits_{h=1}^{H}\big{(}\vec{\mathbf{f}}(t_{h-1})-\vec{\mathbf{f}}(t_{h})\big{)}$
$\displaystyle=\sum\limits_{h=1}^{H}\big{(}(t_{h}-t_{h-1})\cdot\vec{\mathbf{s}}(t_{h-1})\big{)}$
$\displaystyle=\sum\limits_{h=1}^{H}\big{(}\omega^{\ast}_{h}\cdot\vec{\mathbf{s}}(t_{h-1})\big{)}.$

Therefore the claim follows by observing $\vec{\mathbf{f}}(0)$ is the
probability vector associated with $\mathcal{G}$ and each
$\vec{\mathbf{s}}(t_{h-1})$ is the probability vector associated with
$\theta^{\ast}_{h}$. ∎

Algorithm 1 Continuous Algorithm for Public Budget Setting

1:$\mathcal{G}$

2:$\Theta=\Theta^{\ast}_{\mathcal{G}}$

3:$t_{0}\leftarrow 0$; $\mathcal{G}(t_{0})\leftarrow\mathcal{G}$;
$\vec{\mathbf{f}}(t_{0})\leftarrow\langle
f_{\mathcal{G}}(v_{1}),\ldots,f_{\mathcal{G}}(v_{n})\rangle$;

4:for $h\in\\{1,\ldots,H\\}$ do

5: $t\leftarrow t_{h-1}$

6: $\theta(t_{h-1})\leftarrow$ Equal revenue distribution on
$\text{supp}(\mathcal{G}(t_{h-1}))$

7: Run Equation (2) using $\vec{\mathbf{s}}(t)$ as density of
$\theta(t_{h-1})$ till some type’s support in $\vec{\mathbf{f}}(t)$ is
exhausted at time $t=t_{h}$

8: $\mathcal{G}(t_{h})\leftarrow$ distribution induced by
$\vec{\mathbf{f}}(t_{h})$

9: $\omega^{\ast}_{h}\leftarrow t_{h}-t_{h-1}$;
$\theta^{\ast}_{h}\leftarrow\theta(t_{h-1})$;
$\Theta\leftarrow\Theta\cup\\{(\omega^{\ast}_{h},\theta^{\ast}_{h})\\}$

10:return $\Theta$

###  3.2. Optimal Auction For Signals

We start with the easy step. We characterize the revenue-optimal auctions in
the signals created by Algorithm 1 in Lemma 3.2 (proved in Appendix A). As an
easy consequence, $\Theta^{\ast}_{\mathcal{G}}$ always sells the item, and
therefore guarantees efficiency. This is the first necessary condition for
buyer optimality.

Let $\theta_{h}\in\Theta^{\ast}_{\mathcal{G}}$ denote a signal created by
Algorithm 1 for the prior $\mathcal{G}$, and let $v_{\min}(\theta_{h})$ denote
the minimum $v_{i}>0$ such that $\Pr_{v\sim\theta_{h}}[v=v_{i}]>0$.

###### Lemma 3.2.

The optimal auction for $\theta_{h}$ has the following structure:

  * •

If $b\leq v_{\min}(\theta_{h})$, there is an optimal auction that posts a
price of $b$, and raises a revenue of $b$.

  * •

If $b>v_{\min}(\theta_{h})$, there is an optimal auction that posts price
$v_{\min}(\theta_{h})$ and raises a revenue $v_{\min}(\theta_{h})$. Further,
for every $v\in\text{supp}(\theta_{h})$, we have
$v\cdot\overline{F}_{\theta_{h}}(v)=v_{\min}(\theta_{h})$.

###### Proof.

First consider the case when $b\leq v_{\min}(\theta_{h})$. In the program
$\textsf{Public}(\theta_{h})$ (defined in Section 2.1), we have the budget
constraints $p_{i}\leq b$ for all $i$. This means the optimal revenue is
$\sum_{i=1}^{n}\big{(}p_{i}f_{\theta_{h}}(v_{i})\big{)}\leq
b\cdot\sum_{i=1}^{n}f_{\theta_{h}}(v_{i})=b$. However, posting a price of $b$
is also a feasible auction, and raises exactly revenue $b$ since $b\leq
v_{\min}(\theta_{h})$. Therefore, it is an optimal auction for
$\textsf{Public}(\theta_{h})$.

Next consider the case when $b>v_{\min}(\theta_{h})$. Suppose we remove the
constraints $p_{i}\leq b$ from $\textsf{Public}(\theta_{h})$. This cannot
decrease the optimal revenue. The optimal auction without the budget
constraint posts the monopoly price (Myerson81). Since $\theta_{h}$ is equal
revenue, this price is $v_{\min}(\theta_{h})$. However, this price is also
feasible for the budget constraint $b$ since $b>v_{\min}(\theta_{h})$, which
means it must be the optimal auction even with the budget constraint. The
second part of the claim directly follows from the fact that $\theta_{h}$ is
equal revenue. ∎

By the characterizations of the optimal auctions in the above two cases, we
have the following claim that states the item always sells in
$\Theta^{\ast}_{\mathcal{G}}$.

###### Lemma 3.3 (Efficiency of $\Theta^{\ast}_{\mathcal{G}}$).

For each signal $\theta_{h}\in\Theta^{\ast}_{\mathcal{G}}$, there exists a
revenue optimal auction that always allocates the item. As a consequence,
$\textsf{SW}(\Theta^{\ast}_{\mathcal{G}})=\textsf{SW}^{\ast}(\mathcal{G})$.

###  3.3. Characterization of Optimal Auction for $\mathcal{G}(t)$

We analyze the revenue of the signals by showing that the rate of decrease in
revenue of the optimal auction for $\mathcal{G}(t)$ is equal to the revenue of
the signal $\theta(t)$. (See Theorem 3.6.) This when integrated over time
shows that the optimal revenue of the signals is exactly equal to the optimal
revenue for prior $\mathcal{G}$, hence showing buyer optimality.

##### Continuous Constraints.

For the purpose of analysis, we make the constraints in
$\textsf{Public}(\mathcal{G}(t))$ hold not just for
$\text{supp}(\mathcal{G}(t))$, but for all continuous values $v\geq 0$, where
the prior possibly has zero probability mass.666It follows from (RubinsteinW;
cai2021duality) that this formulation is equivalent to
$\textsf{Public}(\mathcal{G}(t))$, though we will not need this equivalence.
Among other things, this formulation allows us to argue that the revenue
changes continuously as the prior changes while constructing our signals.

Formally, fix some time $t$, and let $\mathcal{A}=\mathcal{G}(t)$ so that
$\text{supp}(\mathcal{A})\subseteq\text{supp}(\mathcal{G})$. Recall that the
decision variables in $\textsf{Public}(\mathcal{A})$ are $p_{i}$ (the payment)
and $x_{i}$ (the allocation probability) for all buyer types with valuation
$v_{i}$. We augment the variables by extending the domain to $[0,v_{n}]$; for
all $v\in[0,v_{n}]$, we let $p(v)$ and $x(v)$ denote the expected payment and
allocation probability at $v\in[0,v_{n}]$. This yields the following LP, where
the IC and IR constraints are extended to this domain.

$\displaystyle\textsf{PublicContinuous}(\mathcal{A})$
$\displaystyle\coloneqq\max_{p(\cdot),x(\cdot)}\quad\sum_{i=1}^{n}\big{(}f_{\mathcal{A}}(v_{i})\cdot
p(v_{i})\big{)}$ (Cont. IC) s.t. $\displaystyle v\cdot x(v)-p(v)\geq v\cdot
x(v^{\prime})-p(v^{\prime}),$ $\displaystyle\quad\forall
v,v^{\prime}\in[0,v_{n}],$ (Cont. IR) $\displaystyle v\cdot x(v)-p(v)\geq 0,$
$\displaystyle\quad\forall v\in[0,v_{n}],$ (Feasibility) $\displaystyle 0\leq
x(v)\leq 1,$ $\displaystyle\quad\forall v\in[0,v_{n}],$ (Budget)
$\displaystyle p(v)\leq b,$ $\displaystyle\quad\forall v\in[0,v_{n}].$

From Definition 2.1, $\textsf{R}(\mathcal{A})$ is the optimal revenue
achievable by $\textsf{Public}(\mathcal{A})$. Denote by
$\tilde{\textsf{R}}(\mathcal{A})$ the optimal revenue achievable by
$\textsf{PublicContinuous}(\mathcal{A})$. Clearly,
$\textsf{R}(\mathcal{A})\geq\tilde{\textsf{R}}(\mathcal{A})$.

We now present the main characterization result for the optimal solution to
this LP. This can be viewed as a discrete analog of the characterization for
continuous priors in (Chawla11). We present a stand-alone proof for our
discrete setting in Appendix A via convexity of the utility curve.

###### Theorem 3.4.

For any prior $\mathcal{A}=\mathcal{G}(t)$ with $b>v_{\min}(\mathcal{A})$,
there exists a set of valuations
$\\{w^{\prime}_{1},w^{\prime}_{2},\ldots,w^{\prime}_{m^{\prime}}\\}\subseteq\text{supp}(\mathcal{A})$
and weights $\delta_{1},\delta_{2},\ldots,\delta_{m^{\prime}}\in(0,1]$ such
that $\sum_{j=1}^{m^{\prime}}\delta_{j}=1$, and the optimal revenue of
$\textsf{PublicContinuous}(\mathcal{A})$ is
$\tilde{\textsf{R}}(\mathcal{A})=\sum_{j=1}^{m^{\prime}}\big{(}\delta_{j}\cdot
w^{\prime}_{j}\cdot\overline{F}_{\mathcal{A}}(w^{\prime}_{j})\big{)}$.

###  3.4. Revenue Preservation in Algorithm 1

We are now ready to prove the second necessary criterion for buyer optimality:
$\textsf{R}(\Theta^{\ast}_{\mathcal{G}})=\textsf{R}(\mathcal{G})$, i.e.,
Algorithm 1 minimizes the expected seller revenue through signaling. As
mentioned above, the key step (Theorem 3.6) is to argue that the rate of
decrease of revenue of $\textsf{PublicContinuous}(\mathcal{G}(t))$ exactly
equals the optimal revenue of the signal $\theta(t)$. This when combined with
Lemma 3.3 gives buyer optimality. As a side effect, this will also show the
optimal objectives of $\textsf{Public}(\mathcal{G})$ and
$\textsf{PublicContinuous}(\mathcal{G})$ are identical.

##### Convexity of Revenue in $\textsf{PublicContinuous}(\mathcal{G}(t))$.

The next lemmas bound the continuous flow of revenue being transferred into
the signals. At any time $t$, let $\tilde{\textsf{R}}(t)$ denote the optimal
revenue of $\textsf{PublicContinuous}(\mathcal{G}(t))$.

Our first step is fairly generic, and shows that $\tilde{\textsf{R}}(t)$ is
convex777This is slightly misleading: As we show later, the function
$\tilde{\textsf{R}}(t)$ is actually linear as long as
$\text{supp}(\mathcal{G}(t))$ does not change. The overall function over
$t\in[0,1]$ turns out to be piece-wise linear and concave. in any time
interval $(t_{h-1},t_{h})$ where $\text{supp}(\mathcal{G}(t))$ (and hence
$\theta(t)$) does not change for $t\in(t_{h-1},t_{h})$. Let this signal be
$\theta$ and its corresponding probability vector to be
$\vec{\mathbf{s}}=\\{s_{i}\\}$ over $t\in(t_{h-1},t_{h})$.

Consider the decrease in revenue of any feasible solution
$\mathcal{M}\coloneqq(p(\cdot),x(\cdot))$ of
PublicContinuous$(\mathcal{G}(t))$. The revenue of the solution $\mathcal{M}$
in PublicContinuous$(\mathcal{G}(t))$ is given by
$\tilde{\textsf{R}}_{\mathcal{M}}(t)\coloneqq\sum\limits_{i=1}^{n}\big{(}f_{i}(t)\cdot{p}(v_{i})\big{)}.$
Fixing this $\mathcal{M}$, for each $t\in(t_{h-1},t_{h})$, we have:

(4)
$\displaystyle\derivative{\tilde{\textsf{R}}_{\mathcal{M}}(t)}{t}=\derivative{t}\left(\sum_{i=1}^{n}\big{(}f_{i}(t)\cdot{p}(v_{i})\big{)}\right)=-\sum_{v_{i}\in\text{supp}(\mathcal{G}(t))}s_{i}\cdot{p}(v_{i}),$

where the last equality uses Eq. (2) and the fact that $s_{i}=0$ for any
$v_{i}\notin\text{supp}(\mathcal{G}(t))$. Therefore, for each $\mathcal{M}$,
its revenue $\tilde{\textsf{R}}_{\mathcal{M}}(t)$ decreases linearly with
time. Further, since the constraints of PublicContinuous$(\mathcal{G}(t))$ do
not change with time, $\mathcal{M}$ remains feasible at all points in time
$t\in[0,1]$ (the duration of the algorithm), and its revenue
$\tilde{\textsf{R}}_{\mathcal{M}}(t)$ is continuous at all $t\in[0,1]$ since
each $f_{i}(t)$ changes continuously. Since
$\tilde{\textsf{R}}(t)=\max_{\mathcal{M}}\tilde{\textsf{R}}_{\mathcal{M}}(t)$,
we have:

###### Lemma 3.5.

In Algorithm 1, for any interval $(t_{h-1},t_{h})$ where
$\text{supp}(\mathcal{G}(t))$ does not change, the function
$\tilde{\textsf{R}}(t)$ is convex. Further, the function
$\tilde{\textsf{R}}(t)$ is continuous for all $t\in[0,1]$, that is, the entire
duration of the algorithm.

##### Revenue of Signals.

We are now ready to prove our main theorem quantifying the rate of decrease of
$\tilde{\textsf{R}}(t)$, and thus bounding the revenue of the signals.

###### Theorem 3.6.

In any interval $(t_{h-1},t_{h})$ where $\text{supp}(\mathcal{G}(t))$ does not
change, the function $\tilde{\textsf{R}}(t)$ is linear, and
$\derivative{\tilde{\textsf{R}}(t)}{t}=-\textsf{R}(\theta(t))$, where
$\textsf{R}(\theta(t))$ is the optimal revenue of Public$(\theta(t))$.
Furthermore, at the end of Algorithm 1, it holds that
$\textsf{R}(\Theta^{\ast}_{\mathcal{G}})=\textsf{R}(\mathcal{G})$.

###### Proof.

Fix some $t\in(t_{h-1},t_{h})$, and assume $\text{supp}(\mathcal{G}(t))$ does
not change in $(t_{h-1},t_{h})$ and thus $\theta(t)=\theta$. Note that
$\text{supp}(\mathcal{G}(t))=\text{supp}(\theta)$. First consider the case
where $v_{\min}(\theta)\geq b$. By Lemma 3.2, every revenue maximizing auction
for $\theta$ must have $p_{i}=b$ for all $v_{i}\in\text{supp}(\theta)$, and
thus $\textsf{R}(\theta)=b$; the same proof implies every revenue maximizing
auction $\mathcal{M}^{\prime}$ for PublicContinuous$(\mathcal{G}(t))$ must
have $p^{\prime}_{i}=b$ for all $v_{i}\in\text{supp}(\mathcal{G}(t))$.
Therefore, we have

$\displaystyle\derivative{\tilde{\textsf{R}}(t)}{t}=\sum\limits_{v_{i}\in\text{supp}(\mathcal{G}(t))}\big{(}\derivative{f_{i}(t)}{t}\cdot
b\big{)}=b\cdot\sum\limits_{v_{i}\in\text{supp}(\theta)}-s_{i}=-b=-\textsf{R}(\theta)=-\textsf{R}(\theta(t)).$

Next consider the case when $v_{\min}(\theta)<b$ and let $\text{supp}(\theta)\
=\\{w_{1},\ldots,w_{m}\\}$. Since $\theta$ is an equal revenue distribution,
by Lemma 3.2, we have

(5) $\displaystyle
w_{1}\cdot\overline{F}_{\theta}(w_{1})=\cdots=w_{m}\cdot\overline{F}_{\theta}(w_{m})=w_{1}=v_{\min}(\theta)=\textsf{R}(\theta).$

Let $\mathcal{M}^{\ast}$ be an optimal solution to
PublicContinuous$(\mathcal{G}(t))$. Note that $\mathcal{M}^{\ast}$ is not
necessarily unique, and further, can change as $t$ changes. Since
$\text{supp}(\theta)=\text{supp}(\mathcal{G}(t))$, by Theorem 3.4, the revenue
$\tilde{\textsf{R}}(t)$ achieved by $\mathcal{M}^{\ast}$ in
PublicContinuous$(\mathcal{G}(t))$ is the revenue of a distribution of posted
prices
$\\{w^{\prime}_{1},\ldots,w^{\prime}_{m^{\prime}}\\}\subseteq\text{supp}(\theta)$
with weights $\delta_{1},\ldots,\delta_{m^{\prime}}\in(0,1]$, where
$\sum_{j=1}^{m^{\prime}}\delta_{j}=1$.

At any time $t^{\prime}\in(t_{h-1},t_{h})$, the function
$\tilde{\textsf{R}}_{\mathcal{M}^{\ast}}(t^{\prime})$ – the revenue of
$\mathcal{M}^{\ast}$ over $\mathcal{G}(t^{\prime})$ – is linearly decreasing.
We now calculate the rate of decrease at time $t^{\prime}$. By Theorem 3.4,

$\displaystyle\derivative{\tilde{\textsf{R}}_{\mathcal{M}^{\ast}}(t^{\prime})}{t^{\prime}}$
$\displaystyle=\derivative{t^{\prime}}\left(\sum\limits_{j=1}^{m^{\prime}}\big{(}\delta_{j}\cdot
w^{\prime}_{j}\cdot\sum_{i:v_{i}\geq
w^{\prime}_{j}}f_{i}(t^{\prime})\big{)}\right)$ (by definition that
$\derivative{\vec{\mathbf{f}}}{t^{\prime}}=-\vec{\mathbf{s}})$
$\displaystyle=\sum\limits_{j=1}^{m^{\prime}}\left(-\delta_{j}\big{(}w^{\prime}_{j}\cdot\overline{F}_{\theta}(w^{\prime}_{j})\big{)}\right)$
$\displaystyle=-\sum\limits_{j=1}^{m^{\prime}}\big{(}\delta_{j}\cdot\textsf{R}({\theta})\big{)}=-\textsf{R}({\theta}),$

where the second last equality is by Eq. (5), and the last because
$\sum_{j=1}^{m^{\prime}}\delta_{j}=1$.

By Lemma 3.5, $\tilde{\textsf{R}}(t^{\prime})$ is a maximum of linear revenue
functions of bounded range, one for each feasible auction. Now applying the
Envelope Theorem (Theorem 2 in (Milgrom)), we have that
$\tilde{\textsf{R}}(t^{\prime})$ is differentiable, and further,
$\derivative{\tilde{\textsf{R}}(t)}{t}=-\textsf{R}(\theta)=-\textsf{R}(\theta(t))$.
Indeed, $\tilde{\textsf{R}}(t^{\prime})$ must be a linear function for
$t^{\prime}\in(t_{h-1},t_{h})$.

Note that $\theta(t)$ and thus $-\textsf{R}(\theta(t))$ changes only when some
valuation in the residual prior $\mathcal{G}(t)$ is exhausted. This happens
finitely many times throughout the process. Hence
$\derivative{\tilde{\textsf{R}}(t)}{t}=-\textsf{R}(\theta(t))$ is a piecewise
constant function with finitely many discontinuities, and is thus Riemann
integrable. Recall $\tilde{\textsf{R}}(0)=\tilde{\textsf{R}}(\mathcal{G})$ and
$\tilde{\textsf{R}}(1)=0$. Also recall every signal $\theta_{h}$ in Algorithm
1 is associated with weight $\omega_{h}=t_{h}-t_{h-1}$. Therefore we have

$\displaystyle\tilde{\textsf{R}}(\mathcal{G})$
$\displaystyle=\tilde{\textsf{R}}(0)-\tilde{\textsf{R}}(1)=\int_{t=0}^{1}\big{(}-\derivative{\tilde{\textsf{R}}(t)}{t}\big{)}\differential{t}=\int_{t=0}^{1}\textsf{R}(\theta(t))\differential{t}$
(6)
$\displaystyle=\sum\limits_{h=1}^{H}\int_{t=t_{h-1}}^{t_{h}}\textsf{R}(\theta(t))\differential{t}=\sum\limits_{h=1}^{H}\big{(}\omega_{h}\cdot\textsf{R}(\theta_{h})\big{)}=\textsf{R}(\Theta^{\ast}_{\mathcal{G}}).$

We then observe that it is always feasible for the seller to ignore the
signals: Consider any arbitrary optimal auction
$\hat{\mathcal{M}}=(\\{\hat{p}_{i}\\},\\{\hat{x}_{i}\\})$ for
Public$(\mathcal{G})$. If the seller implements $\hat{\mathcal{M}}$ as the
auction for each signal $\theta_{h}$ created by Algorithm 1, by Bayes
plausibility, the resulting revenue is given by

$\displaystyle\sum\limits_{h=1}^{H}\Big{(}\omega_{h}\cdot\sum\limits_{i=1}^{n}\big{(}f_{\theta_{h}}(v_{i})\cdot\hat{p}_{i}\big{)}\Big{)}$
$\displaystyle=\sum\limits_{i=1}^{n}\Big{(}\sum\limits_{h=1}^{H}\big{(}\omega_{h}\cdot
f_{\theta_{h}}(v_{i})\cdot\hat{p}_{i}\big{)}\Big{)}=\sum\limits_{i=1}^{n}\big{(}f_{\mathcal{G}}(v_{i})\cdot\hat{p}_{i}\big{)}=\textsf{R}(\mathcal{G}).$

Since the above is the total revenue raised by some auction
$\hat{\mathcal{M}}$ over all signals $\\{\theta_{h}\\}$, the total revenue
$\textsf{R}(\Theta^{\ast}_{\mathcal{G}})$ raised by implementing the optimal
auction for each signal $\theta_{h}$ is at least as much. Therefore, we have
$\textsf{R}(\mathcal{G})\leq\textsf{R}(\Theta^{\ast}_{\mathcal{G}})$.
Combining this with Eq. (6), and observing that
PublicContinuous$(\mathcal{G})$ relaxes Public$(\mathcal{G})$, we have:

$\displaystyle\textsf{R}(\mathcal{G})$
$\displaystyle\geq\tilde{\textsf{R}}(\mathcal{G})=\textsf{R}(\Theta^{\ast}_{\mathcal{G}})\geq\textsf{R}(\mathcal{G}).$

Hence, all inequalities must be equalities, which proves the theorem. ∎

In Theorem 3.6 above, we have proved that the process in Algorithm 1 preserves
the seller’s expected revenue. By Lemma 3.3, $\Theta^{\ast}_{\mathcal{G}}$
also achieves efficiency, and thus maximizes social welfare. Hence
$\Theta^{\ast}_{\mathcal{G}}$ must maximize the consumer surplus. This implies
that the analog of Theorem 2.3 on buyer optimality holds for the public budget
case:

###### Theorem 3.7 (Buyer optimality for public budgets).

Suppose $k=1$ in Budgets$(\mathcal{G})$ for some prior $\mathcal{G}$. Then
there exists a signaling scheme $\Theta^{\ast}_{\mathcal{G}}$ (given by
Algorithm 1) that guarantees:
(1)
$\textsf{SW}(\Theta^{\ast}_{\mathcal{G}})=\textsf{SW}^{\ast}(\mathcal{G})$;
(2) $\textsf{R}(\Theta^{\ast}_{\mathcal{G}})=\textsf{R}(\mathcal{G})$; and (3)
$\textsf{CS}(\Theta^{\ast}_{\mathcal{G}})=\textsf{CS}^{\ast}(\mathcal{G})=\textsf{SW}^{\ast}(\mathcal{G})-\textsf{R}(\mathcal{G})$.

##### Discussion.

The nice aspect of our proof approach is twofold. First, we can derive the
following corollary showing the existence of a common revenue-optimal auction
throughout the process.

###### Corollary 3.0.

Any optimal auction $\mathcal{M}^{\ast}(t^{\prime})$ for
PublicContinuous$(\mathcal{G}(t^{\prime}))$ at time $t^{\prime}$ in Algorithm
1 stays revenue optimal throughout the course of the algorithm (i.e., for all
$t>t^{\prime}$).

###### Proof.

Recall that we have $\tilde{\textsf{R}}(\mathcal{G})=\textsf{R}(\mathcal{G})$,
where the former is the optimal objective of PublicContinuous$(\mathcal{G})$
and the latter is the optimal objective of Public$(\mathcal{G})$.

Suppose $\mathcal{M}^{\ast}(t^{\prime})$ is optimal in
PublicContinuous$(\mathcal{G}(t^{\prime}))$ at $t=t^{\prime}$ corresponding to
some equal revenue signal $\theta(t^{\prime})$. Then by the above,
$\mathcal{M}^{\ast}(t^{\prime})$ is also optimal in
Public$(\mathcal{G}(t^{\prime}))$. Also by Theorem 3.6 we have
$\derivative{\tilde{\textsf{R}}(t^{\prime})}{t}=\derivative{\tilde{\textsf{R}}_{\mathcal{M}^{\ast}(t^{\prime})}(t)}{t}=-\textsf{R}(\theta(t^{\prime}))$
(recall $\tilde{\textsf{R}}_{\mathcal{M}^{\ast}(t^{\prime})}(t)$ denotes the
objective achieved by $\mathcal{M}^{\ast}(t^{\prime})$ in
PublicContinuous$(\mathcal{G}(t))$). The above means
$\mathcal{M}^{\ast}(t^{\prime})$ remains optimal (both w.r.t.
PublicContinuous$(\mathcal{G}(t))$ and Public$(\mathcal{G}(t))$) till the next
time $\theta(t)$ changes (say at $t=t^{\prime\prime}$). Since the revenue of
any auction is continuous in $t$, this implies
$\mathcal{M}^{\ast}(t^{\prime})$ is still optimal at $t=t^{\prime\prime}$.
Take $\mathcal{M}^{\ast}(t^{\prime\prime})=\mathcal{M}^{\ast}(t^{\prime})$.
Repeating this argument shows $\mathcal{M}^{\ast}(t^{\prime})$ remains optimal
for all $t>t^{\prime}$. ∎

Secondly, our approach is extensible to more complex settings in the following
sense: Theorem 3.4 yields a characterization of the revenue optimal auction in
the specific case of public budgets. We use this to prove the first claim in
Theorem 3.6, that the rate of decrease of revenue of the optimal auction is
equal to the revenue of the signal constructed. The rest of the proof is
generic in that it invokes the Envelope Theorem on $\tilde{\textsf{R}}(t)$.
Our proof for the FedEx case simply reuses the generic portion, along with a
specialized characterization of the optimal auction there.

##  4\. Main Result: Signaling Scheme with Private Deadlines

We now focus on the case with private valuation-deadline pairs
$(v,d)\sim\mathcal{G}$, where $\mathcal{G}_{j}$ denotes the marginal
distribution of $v$ given $d=j$. This is the so-called FedEx problem (Fiat16).
The non-trivial aspect now is the construction of the signals themselves. We
first generalize the notion of equal revenue signals in Section 4.1, and
outline the corresponding signaling algorithm (Algorithm 2). We then proceed
to show that Algorithm 2 is buyer optimal, using the same plan of attack in
Section 3.

We begin with some notation. For an arbitrary prior $\mathcal{A}$ with
$\text{supp}(\mathcal{A})\subseteq\text{supp}(\mathcal{G})=\\{v_{1},\ldots,v_{n}\\}\times\\{1,\ldots,k\\}$,
we denote by $\mathcal{A}_{j}$ the conditional distribution of $\mathcal{A}$
given $d=j$. Further, let
$f_{\mathcal{A}_{j}}(v_{i})\coloneqq\Pr_{(v,d)\sim\mathcal{A}}[v=v_{i}\mid
d=j]$, and
$\underline{F}_{\mathcal{A}_{j}}(v_{i})\coloneqq\Pr_{(v,d)\sim\mathcal{A}}[v\leq
v_{i}\mid d=j]$. Further, define
$\text{values}(\mathcal{A})\coloneqq\\{v_{i}>0\mid\sum_{j=1}^{k}f_{\mathcal{A}_{j}}(v_{i})>0\\}$
as the set of values with non-zero support in $\mathcal{A}$, and similarly,
$\text{values}(\mathcal{A}_{j})\coloneqq\\{v_{i}>0\mid
f_{\mathcal{A}_{j}}(v_{i})>0\\}$. Finally, let
$v_{\min}(\mathcal{A})\coloneqq\min\\{v_{i}>0\mid\sum_{j=1}^{k}f_{\mathcal{A}_{j}}(v_{i})>0\\}$,
and $v_{\min}(\mathcal{A}_{j})\coloneqq\min\\{v_{i}>0\mid
f_{\mathcal{A}_{j}}(v_{i})>0\\}$.

###  4.1. Generalized Equal Revenue Signals

One natural approach to designing a signaling scheme is to apply the algorithm
in (Bergemann15) to the marginal $\mathcal{G}_{j}$ induced by each deadline
separately. However, consider the following example:

###### Example 4.0.

Let the initial prior $\mathcal{G}$ be supported on
$(v,d)=\\{(2,1),(3,1),(1,2),(2,2),(3,4),(4,3)\\}$ with uniform probability, as
shown in Table 1. Accordingly, the maximum social welfare
$\textsf{SW}^{\ast}_{\mathcal{G}}$ is given by
$\frac{2+3+1+2+4+3}{6}=\frac{5}{2}$. The revenue maximizing auction posts a
fixed price of $2$ to all types. This auction raises an expected revenue of
$\textsf{R}^{\ast}_{\mathcal{G}}=2\cdot\frac{5}{6}=\frac{5}{3}$ and thus an
expected consumer surplus of $\frac{5}{2}-\frac{5}{3}=\frac{5}{6}$.

On this example, suppose we run the algorithm in (Bergemann15) separately for
each deadline. Then, this results in a price of $2$ when $d=1$, a price of $1$
when $d=2$, and prices of $4$ and $3$ respectively when $d=3$ and $d=4$. It is
easy to check that this raises consumer surplus $\frac{1}{3}$, which is much
smaller than the optimal surplus of $\frac{5}{6}$.

$\Pr[\mathcal{G}=(v,d)]$ | $v=1$ | $v=2$ | $v=3$ | $v=4$
---|---|---|---|---
$d=1$ | $0$ | $1/6$ | $1/6$ | $0$
$d=2$ | $1/6$ | $1/6$ | $0$ | $0$
$d=3$ | $0$ | $0$ | $0$ | $1/6$
$d=4$ | $0$ | $0$ | $1/6$ | $0$
Table 1.  Probability values $\Pr_{(v,d)\sim\mathcal{G}}[(v,d)=(\cdot,\cdot)]$
in the running example.

The main reason that the scheme that separately develops signals for each
deadline does not raise optimal consumer surplus is because it reveals the
deadline of the buyer, which provides the seller with too much information. We
therefore need a different and novel signaling scheme that can “blur” the
deadline information in addition to the value information. Our key idea is to
define signals that continuously pull mass from all marginals
$\mathcal{G}_{j}$ at once, albeit in an equal revenue fashion.

###### Definition 4.0 (Lower Envelope).

Given prior $\mathcal{A}$ with
$\text{supp}(\mathcal{A})\subseteq\text{supp}(\mathcal{G})$, for all
$j\in[1,k]$, let

$\hat{i}_{j}\coloneqq\max\\{i:\underline{F}_{\mathcal{A}_{j^{\prime}}}(v_{i})=0\quad\forall
j^{\prime}\in[j,k]\\}$

denote the largest $i$ such that no buyer with valuation at most $v_{i}$ and
deadline at least $j$ exists in $\mathcal{A}$. Note that $\hat{i}_{j}=0$ if
$f_{\mathcal{A}_{j^{\prime}}}(v_{1})>0$ for some $j^{\prime}\in[j,k]$. Let
$\hat{i}_{k+1}=n$. The lower envelope of $\mathcal{A}$ is defined as

$\textsf{LE}(\mathcal{A})\coloneqq\\{(v_{i},j)\mid\big{(}f_{\mathcal{A}_{j}}(v_{i})>0\big{)}\land\big{(}\hat{i}_{j}<i\leq\hat{i}_{j+1}\big{)}\\}.$

We say a value-deadline pair $(v_{i},j)$ is _on the lower envelope of
$\mathcal{A}$_ if $(v_{i},j)\in\textsf{LE}(\mathcal{A})$. Two pairs
$(v_{a},r),(v_{b},r^{\prime})\in\textsf{LE}(\mathcal{A})$ where $a<b$ and
$r^{\prime}\geq r$ are _consecutive points on $\textsf{LE}(\mathcal{A})$_ if
there is no $i\in(a,b)$ and some $j$ such that $(v_{i},j)$ is on the lower
envelope of $\mathcal{A}$.

An immediate observation is that for any $\mathcal{A}$, its lower envelope
$\textsf{LE}(\mathcal{A})$ does not contain two different valuation-deadline
pairs with the same valuation:

###### Observation 4.3.

For any prior $\mathcal{A}$, if
$(v_{i},j),(v_{i},j^{\prime})\in\textsf{LE}(\mathcal{A})$ for some $i$, then
$j=j^{\prime}$.

###### Definition 4.0 (Equal revenue Lower Envelope
$\theta^{ELE}_{\mathcal{A}}$).

For an arbitrary prior $\mathcal{A}$ with
$\text{supp}(\mathcal{A})\subseteq\text{supp}(\mathcal{G})$, let
$\textsf{LE}(\mathcal{A})$ be supported on
$\\{(v^{\prime}_{1},j^{\prime}_{1}),(v^{\prime}_{2},j^{\prime}_{2}),\ldots,(v^{\prime}_{m},j^{\prime}_{m})\\}$,
where
$0<v_{\min}(\mathcal{A})=v^{\prime}_{1}<v^{\prime}_{2}<\cdots<v^{\prime}_{m}\leq
v_{n}$.888Note that all $v^{\prime}_{i}$’s are unique by Observation 4.3. We
define the _Equal Revenue Lower Envelope_ signal $\theta^{ELE}_{\mathcal{A}}$
for $\mathcal{A}$ to be the equal revenue distribution over
$\\{(v^{\prime}_{i},j^{\prime}_{i})\\}$, i.e.,

$\Pr_{(v,d)\sim\theta^{ELE}_{\mathcal{A}}}[v\geq v^{\prime}_{1}]\cdot
v^{\prime}_{1}=\Pr_{(v,d)\sim\theta^{ELE}_{\mathcal{A}}}[v\geq
v^{\prime}_{2}]\cdot
v^{\prime}_{2}=\cdots=\Pr_{(v,d)\sim\theta^{ELE}_{\mathcal{A}}}[v\geq
v^{\prime}_{m}]\cdot v^{\prime}_{m}=v^{\prime}_{1}=v_{\min}(\mathcal{A}).$

In other words, when disregarding the deadlines (and thus treating
$\theta^{ELE}_{\mathcal{A}}$ as a distribution of $v$), every valuation with
nonzero probability mass in its support is an optimal monopoly price.
Analogous to Definition 2.4, this distribution is unique given
$\textsf{LE}(\mathcal{A})$.

###### Example 4.0.

Let $\mathcal{A}=\mathcal{G}$ be the input prior $\mathcal{G}$ in Example 4.1.
Then the lower envelope LE$(\mathcal{G})$ is given by
$\\{(1,2),(2,2),(3,4)\\}$, and the corresponding equal revenue lower envelope
signal $\theta^{ELE}_{\mathcal{G}}$ has $\Pr[(1,2)]=1/2$, $\Pr[(2,2)]=1/6$,
and $\Pr[(3,4)]=1/3$. We have

$\Pr_{(v,d)\sim\theta^{ELE}_{\mathcal{G}}}[v\geq 1]\cdot
1=\Pr_{(v,d)\sim\theta^{ELE}_{\mathcal{G}}}[v\geq 2]\cdot
2=\Pr_{(v,d)\sim\theta^{ELE}_{\mathcal{G}}}[v\geq 3]\cdot 3=1.$

We have the following observation:

###### Observation 4.6.

For an arbitrary prior $\mathcal{A}$ with
$\text{supp}(\mathcal{A})\subseteq\text{supp}(\mathcal{G})$, for any $i,j$
such that $(v_{i},j)\in\text{supp}(\theta^{ELE}_{\mathcal{A}})$, it holds that
$\underline{F}_{(\theta^{ELE}_{\mathcal{A}})_{j^{\prime}}}(v_{i})=0$ for all
$j<j^{\prime}\leq k$.

##### Signaling Algorithm.

For any time $t\in[0,1]$, we now let $\mathbf{F}(t)=[f_{ij}(t)]$ be an
$n\times k$ matrix function representing the residual prior, where $f_{ij}(t)$
represents the remaining probability mass on type $(v_{i},j)$ at time $t$.
Similar to the public budget case, let $\mathcal{G}(t)$ denote the probability
distribution obtained by placing the remaining probability mass
$1-\sum_{j=1}^{k}\sum_{i=1}^{n}f_{ij}(t)$ at $(v,d)=(0,0)$. We omit
considering $(0,0)$ as part of the support of $\mathcal{G}(t)$. Therefore we
define $\text{supp}(\mathcal{G}(t))\coloneqq\\{(v_{i},j)\mid
v_{i}>0,\,f_{ij}(t)>0\\}$. For each deadline $d=j$, we denote the marginal
distribution of $\mathcal{G}(t)$ as $\mathcal{G}_{j}(t)$. We therefore have:
$\text{values}(\mathcal{G}(t))\coloneqq\\{v_{i}>0\mid\sum_{j}f_{ij}(t)>0\\}$,
$\text{values}(\mathcal{G}_{j}(t))\coloneqq\\{v_{i}>0\mid f_{ij}(t)>0\\}$, and
$v_{\min}(\mathcal{G}_{j}(t))\coloneqq\min\\{v_{i}>0\mid f_{ij}(t)>0\\}$.

We now start with the prior distribution $\mathcal{G}(0)=\mathcal{G}$ and let
$f_{ij}(0)=\Pr[\mathcal{G}=(v_{i},j)]$ for every $i,j$. Our algorithm
continuously takes away probability mass from $\mathbf{F}(t)$ and transfers it
to the constructed signals, terminating when $\mathbf{F}(t)$ becomes
$\mathbf{0}$ at time $t=T$. At any time $t\in[0,T)$, denote
$\theta(t)=\theta^{ELE}_{\mathcal{G}(t)}$ over $\textsf{LE}(\mathcal{G}(t))$
(Definition 4.4),
$s_{ij}(t)=\Pr_{(v,d)\sim\theta^{ELE}_{\mathcal{G}(t)}}[(v,d)=(v_{i},j)]$, and
$\mathbf{S}(t)\coloneqq[s_{ij}(t)]$. As $\mathbf{S}(t)$ depends on
$\text{values}(\mathcal{G}(t))$ but not $\\{f_{ij}(t)\\}$, it is fixed as long
as $\text{values}(\mathcal{G}(t))$ does not change. Our algorithm continuously
reduces $\mathbf{F}(t)$ at rate $\mathbf{S}(t)$ until $\mathbf{F}(t)$ becomes
$\mathbf{0}$:

(7) $\displaystyle\derivative{\mathbf{F}}{t}=-\mathbf{S}(t).$

Since $\sum_{i,j}s_{ij}(t)=1$, the rate of decrease of $\sum_{i,j}f_{ij}(t)$
is $1$. Since $\sum_{i,j}f_{ij}(0)=1$, we have $T=1$.

##### Signals constructed.

We say the type $(v_{i},j)$ is exhausted at time $t$ if $f_{ij}(t)=0$ but
$f_{ij}(t^{\prime})>0$ for all $t^{\prime}<t$. Therefore,
$\text{values}(\mathcal{G}(t))$ changes only when some type is exhausted. For
each maximal time interval $t\in[t_{1},t_{2})$ in which
$\text{values}(\mathcal{G}(t))$ remains fixed, the final scheme includes a
corresponding signal $\theta$ with weight $(t_{2}-t_{1})$ so that
$\theta(t)=\theta$ for $t\in[t_{1},t_{2})$. Since $\theta(t)$ changes only if
some element in $\mathbf{F}(t)$ becomes zero, the number of signals
constructed is finite.

The overall signaling scheme is described in Algorithm 2.

Algorithm 2 Continuous Algorithm for Deadlines Setting

1:$\mathcal{G}$

2:$\Theta=\Theta^{\ast}_{\mathcal{G}}$

3:$t_{0}\leftarrow 0$; $\mathcal{G}(t_{0})\leftarrow\mathcal{G}$;
$\mathbf{F}(0)\leftarrow[\Pr_{(v,d)\sim\mathcal{G}}[(v,d)=(v_{i},j)]]$;

4:for $h\in\\{1,\ldots,H\\}$ do

5: $t\leftarrow t_{h-1}$

6: $\theta(t_{h-1})\leftarrow$ Equal revenue distribution on
$\text{supp}(\mathcal{G}(t_{h-1}))$

7: Run Equation (7) using $\mathbf{S}(t)$ as density of $\theta(t_{h-1})$ till
some type’s support in $\mathbf{F}(t)$ is exhausted at time $t=t_{h}$

8: $\mathcal{G}(t_{h})\leftarrow$ distribution induced by $\mathbf{F}(t_{h})$

9: $\omega^{\ast}_{h}\leftarrow t_{h}-t_{h-1}$;
$\theta^{\ast}_{h}\leftarrow\theta(t_{h-1})$;
$\Theta\leftarrow\Theta\cup\\{(\omega^{\ast}_{h},\theta^{\ast}_{h})\\}$

10:return $\Theta$

###### Example 4.0.

Table 2 presents the execution of Algorithm 2 on the instance in Example 4.1.
Consider the resulting signals $\\{S_{1},\ldots,\theta_{6}\\}$. As all signals
are of the lower-envelope fashion, the signaling scheme suggests
$v_{\min}(\theta_{i})$ as the posted price for $\theta_{i}$, which is
$\\{1,2,2,2,2,2\\}$, respectively. Accordingly, the expected revenue raised by
the seller under this signaling scheme is given by
$\sum_{i}v_{\min}(\theta_{i})\cdot\omega_{i}=1\cdot\frac{24}{72}+2\cdot\frac{6+12+12+15+3}{72}=\frac{1}{3}+\frac{4}{3}=\frac{5}{3}=\textsf{R}^{\ast}_{\mathcal{G}}$.
The item always sells, and the maximum expected consumer surplus
$\textsf{SW}^{\ast}_{\mathcal{G}}-\textsf{R}^{\ast}_{\mathcal{G}}=\frac{5}{2}-\frac{5}{3}=\frac{5}{6}$
is achieved. Therefore, Algorithm 2 is buyer optimal for $\mathcal{G}$.

$\Pr[\mathcal{G}]$ | $v=1$ | $v=2$ | $v=3$ | $v=4$
---|---|---|---|---
$d=1$ | - | $12/72$ | $12/72$ | -
$d=2$ | $12/72$ | $12/72$ | - | -
$d=3$ | - | - | - | $12/72$
$d=4$ | - | - | $12/72$ | -
(a) The initial prior $\mathcal{G}(0)=\mathcal{G}$ at $t_{0}=0$.

$\Pr[\theta]$ | $v=1$ | $v=2$ | $v=3$ | $v=4$
---|---|---|---|---
$d=1$ | - | - | - | -
$d=2$ | $12/72$ | $4/72$ | - | -
$d=3$ | - | - | - | -
$d=4$ | - | - | $8/72$ | -
(b) Signal $\theta_{1}=\theta(0)$ multiplied by $\omega_{1}=\frac{24}{72}$.

$\Pr[\mathcal{G}]$ | $v=1$ | $v=2$ | $v=3$ | $v=4$
---|---|---|---|---
$d=1$ | - | $12/72$ | $12/72$ | -
$d=2$ | - | $8/72$ | - | -
$d=3$ | - | - | - | $12/72$
$d=4$ | - | - | $4/72$ | -
(c) The residual prior $\mathcal{G}(\frac{24}{72})$ at $t_{1}=\frac{24}{72}$.

$\Pr[\theta]$ | $v=1$ | $v=2$ | $v=3$ | $v=4$
---|---|---|---|---
$d=1$ | - | - | - | -
$d=2$ | - | $2/72$ | - | -
$d=3$ | - | - | - | -
$d=4$ | - | - | $4/72$ | -
(d) Signal $\theta_{2}=\theta(\frac{24}{72})$ multiplied by
$\omega_{2}=\frac{6}{72}$.

$\Pr[\mathcal{G}]$ | $v=1$ | $v=2$ | $v=3$ | $v=4$
---|---|---|---|---
$d=1$ | - | $12/72$ | $12/72$ | -
$d=2$ | - | $6/72$ | - | -
$d=3$ | - | - | - | $12/72$
$d=4$ | - | - | - | -
(e) The residual prior $\mathcal{G}(\frac{30}{72})$ at $t_{2}=\frac{30}{72}$.

$\Pr[\theta]$ | $v=1$ | $v=2$ | $v=3$ | $v=4$
---|---|---|---|---
$d=1$ | - | - | - | -
$d=2$ | - | $6/72$ | - | -
$d=3$ | - | - | - | $6/72$
$d=4$ | - | - | - | -
(f) Signal $\theta_{3}=\theta(\frac{30}{72})$ multiplied by
$\omega_{3}=\frac{12}{72}$.

$\Pr[\mathcal{G}]$ | $v=1$ | $v=2$ | $v=3$ | $v=4$
---|---|---|---|---
$d=1$ | - | $12/72$ | $12/72$ | -
$d=2$ | - | - | - | -
$d=3$ | - | - | - | $6/72$
$d=4$ | - | - | - | -
(g) The residual prior $\mathcal{G}(\frac{42}{72})$ at $t_{3}=\frac{42}{72}$.

$\Pr[\theta]$ | $v=1$ | $v=2$ | $v=3$ | $v=4$
---|---|---|---|---
$d=1$ | - | $4/72$ | $2/72$ | -
$d=2$ | - | - | - | -
$d=3$ | - | - | - | $6/72$
$d=4$ | - | - | - | -
(h) Signal $\theta_{4}=\theta(\frac{42}{72})$ multiplied by
$\omega_{4}=\frac{12}{72}$.

$\Pr[\mathcal{G}]$ | $v=1$ | $v=2$ | $v=3$ | $v=4$
---|---|---|---|---
$d=1$ | - | $8/72$ | $10/72$ | -
$d\geq 2$ | - | - | - | -
(i) The residual prior $\mathcal{G}(\frac{54}{72})$ at $t_{4}=\frac{54}{72}$.

$\Pr[\theta]$ | $v=1$ | $v=2$ | $v=3$ | $v=4$
---|---|---|---|---
$d=1$ | - | $5/72$ | $10/72$ | -
$d\geq 2$ | - | - | - | -
(j) Signal $\theta_{5}=\theta(\frac{54}{72})$ multiplied by
$\omega_{5}=\frac{15}{72}$.

$\Pr[\mathcal{G}]$ | $v=1$ | $v=2$ | $v=3$ | $v=4$
---|---|---|---|---
$d=1$ | - | $3/72$ | - | -
$d\geq 2$ | - | - | - | -
(k) The residual prior $\mathcal{G}(\frac{69}{72})$ at $t_{5}=\frac{69}{72}$.

$\Pr[\theta]$ | $v=1$ | $v=2$ | $v=3$ | $v=4$
---|---|---|---|---
$d=1$ | - | $3/72$ | - | -
$d\geq 2$ | - | - | - | -
(l) Signal $\theta_{6}=\theta(\frac{69}{72})$ multiplied by
$\omega_{6}=\frac{3}{72}$.

Table 2.  Timeline of the algorithm applied on Example 4.1. Values of
probabilistic masses in the constructed signals are multiplied by the
corresponding weights of the signals. All values are divided by $72$ for
simplicity.

Similar to Algorithm 1, the signals created by Algorithm 2 are Bayes
plausible:

###### Observation 4.8.

For any arbitrary $\mathcal{G}$, let
$\Theta^{\ast}_{\mathcal{G}}=\\{(\omega^{\ast}_{h},\theta^{\ast}_{h})\\}_{h\in[H]}$
be the set of signals output by Algorithm 2 taking $\mathcal{G}$ as input.
Then we have $\sum_{h=1}^{H}\omega^{\ast}_{h}\theta^{\ast}_{h}=\mathcal{G}$.

###  4.2. Optimal Auction for Signals

In the following, we show the counterparts of Lemmas 3.2 and 3.3 in the
deadlines context, and that Algorithm 2 guarantees efficiency. Let
$\theta_{h}\in\Theta^{\ast}_{\mathcal{G}}$ denote a signal created by
Algorithm 2 for the prior $\mathcal{G}$. This theorem is proved in Appendix B.

###### Lemma 4.9.

There is an optimal auction for $\theta_{h}$ that posts a price of
$v_{\min}(\theta_{h})$. Further, for every
$v_{i}\in\text{values}(\theta_{h})$, we have
$v_{i}\cdot\Pr_{(v,d)\sim\theta_{h}}[v\geq v_{i}]=v_{\min}(\theta_{h})$.

###### Proof.

By Observation 4.3 and Definition 4.4, we have that for any $i$, if
$(v_{i},j),(v_{i},j^{\prime})\in\text{supp}(\theta_{h})$, then $j=j^{\prime}$;
furthermore, if
$(v_{i^{\prime}},j),(v_{i^{\prime\prime}},j)\in\text{supp}(\theta_{h})$ for
some $i^{\prime}\leq i^{\prime\prime}$, then for any
$i\in[i^{\prime},i^{\prime\prime}]$,
$(v_{i},j^{\prime})\in\text{supp}(\theta_{h})$ implies $j^{\prime}=j$.
Therefore, we can denote
$\text{values}(\theta_{h})=\\{w_{1},w_{2},\ldots,w_{m}\\}$ and
$\text{supp}(\theta_{h})=\\{(w_{1},d_{1}),(w_{2},d_{2}),\ldots,(w_{m},d_{m})\\}$,
where $w_{1}<w_{2}<\cdots<w_{m}$ and $d_{1}\leq d_{2}\leq\cdots\leq d_{m}$.
Any incentive compatible auction for $\theta_{h}$ can thus be represented by
$\\{(p_{i},x_{i})\\}$, where $p_{i}$ and $x_{i}$ are the expected payment and
allocation probability, respectively, for the type $(w_{i},d_{i})$. For
simplicity, let $f_{i}=\Pr_{(v,d)\sim\theta_{h}}[v=w_{i}]$, and thus
$\sum_{i=1}^{m}f_{i}=1$; also let
$\overline{F}_{i}=\Pr_{(v,d)\sim\theta_{h}}[v\geq w_{i}]$. We have

(8) $\displaystyle\overline{F}_{1}\cdot w_{1}=\overline{F}_{2}\cdot
w_{2}=\cdots=\overline{F}_{m}\cdot w_{m}=w_{1}=v_{\min}(\theta_{h}),$

and thus for every $i=1,\ldots,(m-1)$ we have

$\displaystyle\overline{F}_{i}\cdot w_{i}-\overline{F}_{i+1}\cdot w_{i+1}$
$\displaystyle=(\overline{F}_{i+1}+f_{i})\cdot w_{i}-\overline{F}_{i+1}\cdot
w_{i+1}$ (9) $\displaystyle=f_{i}\cdot
w_{i}-\overline{F}_{i+1}\cdot(w_{i+1}-w_{i})=0.$

Consider any feasible auction $\\{(p_{i},x_{i})\\}$ for $\theta_{h}$. By
individual rationality for the type $(w_{1},d_{1})$, we have $w_{1}\cdot
x_{1}-p_{1}\geq 0$, or $p_{1}\leq w_{1}\cdot x_{1}$. Next, for all
$i=2,\ldots,m$, to prevent the type $(w_{i},d_{i})$ to misreport
$(w_{i-1},d_{i-1}\leq d_{i})$, we have $w_{i}\cdot x_{i}-p_{i}\geq w_{i}\cdot
x_{i-1}-p_{i-1}$, or equivalently, $p_{i}\leq
p_{i-1}+w_{i}\cdot(x_{i}-x_{i-1})$. Letting $x_{0}=0$, for all $i\in[1,m]$ we
can write

$\displaystyle f_{i}\cdot p_{i}$ $\displaystyle\leq
f_{i}\cdot\big{(}p_{i-1}+w_{i}\cdot(x_{i}-x_{i-1})\big{)}$ $\displaystyle\leq
f_{i}\cdot\Big{(}\big{(}p_{i-2}+w_{i-1}\cdot(x_{i-1}-x_{i-2})\big{)}+w_{i}\cdot(x_{i}-x_{i-1})\Big{)}$
$\displaystyle\leq\cdots\leq
f_{i}\cdot\sum_{i^{\prime}=1}^{i}\big{(}w_{i}\cdot(x_{i}-x_{i-1})\big{)}.$

Summing up the above inequality for all $i\in[1,m]$, we have

$\displaystyle\sum_{i=1}^{m}(f_{i}\cdot p_{i})$
$\displaystyle\leq\sum_{i=1}^{m}\Big{(}f_{i}\cdot\sum_{i^{\prime}=1}^{i}\big{(}w_{i}\cdot(x_{i}-x_{i-1})\big{)}\Big{)}$
$\displaystyle=\sum_{i=1}^{m-1}\Big{(}x_{i}\cdot\big{(}f_{i}\cdot
w_{i}-\sum_{i^{\prime}=i+1}^{m}f_{i^{\prime}}\cdot(w_{i}-w_{i-1})\big{)}\Big{)}+x_{m}\cdot
f_{m}\cdot w_{m}$
$\displaystyle=\sum_{i=1}^{m-1}\Big{(}x_{i}\cdot\big{(}f_{i}\cdot
w_{i}-\overline{F}_{i+1}\cdot(w_{i}-w_{i-1})\big{)}\Big{)}+x_{m}\cdot
f_{m}\cdot w_{m}$ (by Eq. (9)) $\displaystyle=x_{m}\cdot f_{m}\cdot w_{m}$
($x_{m}\leq 1$) $\displaystyle\leq f_{m}\cdot w_{m}.$

Notice that the left-hand side of the above inequality,
$\sum_{i=1}^{m}(f_{i}\cdot p_{i})$, is exactly the revenue raised by
$\\{(p_{i},x_{i})\\}$ in $\theta_{h}$. Furthermore, by Eq. (8) we also have
$f_{m}\cdot w_{m}=\overline{F}_{m}\cdot w_{m}=w_{1}=v_{\min}(\theta_{h})$.
This shows the maximum revenue is upper bounded by $w_{1}$. But
$w_{1}=v_{\min}(\theta_{h})$ is exactly the revenue raised by the feasible
auction that posts a fixed price of $w_{1}=v_{\min}(\theta_{h})$. Therefore,
this auction is optimal, and the maximum revenue is
$w_{1}=v_{\min}(\theta_{h})$. The second statement in the lemma follows
directly from Eq. (8). ∎

The characterization of the optimal auction above implies the item always
sells in $\Theta^{\ast}_{\mathcal{G}}$:

###### Lemma 4.10 (Efficiency of $\Theta^{\ast}_{\mathcal{G}}$).

For each signal $\theta_{h}\in\Theta^{\ast}_{\mathcal{G}}$, there exists a
revenue optimal auction that always sells the item. As a consequence,
$\textsf{SW}(\Theta^{\ast}_{\mathcal{G}})=\textsf{SW}^{\ast}(\mathcal{G})$.

###  4.3. Characterization of Optimal Auction for $\mathcal{G}(t)$

In the following, we analyze the revenue of the signals using the same
technique in Section 3.3: We make the constraints in
Deadlines$(\mathcal{G}(t))$ hold not just for values in
$\text{values}(\mathcal{G}(t))$ but for all continuous values $v>0$. Fix some
time $t$, and let $\mathcal{A}=\mathcal{G}(t)$ so that
$\text{supp}(\mathcal{A})\subseteq\text{supp}(\mathcal{G})$. We describe the
linear program with extended domain and IC/IR constraints:

$\displaystyle\textsf{DeadlinesContinuous}(\mathcal{A})$
$\displaystyle\coloneqq\max_{\\{p_{j}(\cdot)\\},\\{x_{j}(\cdot)\\}}\quad\sum_{j=1}^{k}\left(\Pr_{(v,d)\sim\mathcal{A}}[d=j]\cdot\sum_{i=1}^{n}\big{(}f_{\mathcal{A}_{j}}(v_{i})\cdot
p_{j}(v_{i})\big{)}\right)$ s.t. $\displaystyle v\cdot x_{j}(v)-p_{j}(v)\geq
v\cdot x_{j}(v^{\prime})-p_{j}(v^{\prime}),$ $\displaystyle\quad\forall
v,v^{\prime}\in[0,v_{n}],\,1\leq j\leq k,$ $\displaystyle v\cdot
x_{j}(v)-p_{j}(v)\geq v\cdot x_{j-1}(v)-p_{j-1}(v),$
$\displaystyle\quad\forall v\in[0,v_{n}],\,2\leq j\leq k,$ $\displaystyle
v\cdot x_{j}(v)-p_{j}(v)\geq 0,$ $\displaystyle\quad\forall
v\in[0,v_{n}],\,1\leq j\leq k,$ $\displaystyle 0\leq x_{j}(v)\leq 1,$
$\displaystyle\quad\forall v\in[0,v_{n}],\,1\leq j\leq k.$

We denote $\textsf{R}(\mathcal{A})$ the optimal revenue achievable by
Deadlines$(\mathcal{A})$ and $\tilde{\textsf{R}}(\mathcal{A})$ the optimal
revenue achievable by DeadlinesContinuous$(\mathcal{A})$. Clearly,
$\textsf{R}(\mathcal{A})\geq\tilde{\textsf{R}}(\mathcal{A})$.999It follows
from (RubinsteinW; cai2021duality) that these two revenues are equal; however,
we will not need this fact in our proof.

We now present a characterization result for the optimal auction that is a
discrete analog of the characterization for continuous priors in (Fiat16;
Devanur17). We present a stand-alone and elementary proof for the discrete
setting in Appendix B. We note that unlike (Fiat16; Devanur17), our proof uses
convexity of the utility curve in the primal solution instead of invoking
duality, and may be of independent interest. This theorem is proved in
Appendix B.

###### Theorem 4.11.

For any prior $\mathcal{A}=\mathcal{G}(t)$ such that
$\text{values}(\mathcal{A})=\\{w_{1},w_{2},\ldots,w_{m}\\}$, where
$w_{1}<w_{2}<\cdots<w_{m}$, there exists weights
$\delta^{j}_{1},\delta^{j}_{2},\ldots,\delta^{j}_{m}\in[0,1]$ for all
$j\in[1,k]$ such that the optimal revenue of
$\textsf{DeadlinesContinuous}(\mathcal{A})$ is

$\tilde{\textsf{R}}(\mathcal{A})=\sum_{j=1}^{k}\left(\Pr_{(v,d)\sim\mathcal{A}}[d=j]\cdot\sum_{i^{\prime}=1}^{m}\big{(}\delta^{j}_{i^{\prime}}\cdot\overline{F}_{\mathcal{A}_{j}}(w_{i^{\prime}})\cdot
w_{i^{\prime}}\big{)}\right).$

Furthermore, we have the following properties about the lower envelope
$\textsf{LE}(\mathcal{A})$:

  * •

If $(w_{a},r)\in\textsf{LE}(\mathcal{A})$, then
$\delta^{j}_{a}=\delta^{r}_{a}$ for all $j\geq r$.

  * •

If $(w_{a},r)$ and $(w_{b},r^{\prime})$ are consecutive points on
$\textsf{LE}(\mathcal{A})$ where $a<b$ and $r^{\prime}\geq r$, then
$\delta^{j}_{i}=0$ for all $i\in(a,b)$ and $j\geq r$.

  * •

$\sum_{i=1}^{m}\big{(}\mathbbm{1}^{\textsf{LE}(\mathcal{A})}_{i}\cdot\delta^{k}_{i}\big{)}=1$,
where $\mathbbm{1}^{\textsf{LE}(\mathcal{A})}_{i}$ equals $1$ if
$(w_{i},j)\in\textsf{LE}(\mathcal{A})$ for some $j$, and $0$ otherwise.

We illustrate this characterization in Figure 1.

$d=1$$d=2$$d=3$$d=4$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{6}$$w_{7}$$x_{4}(\cdot)$$v$$w_{1}$$w_{2}$$w_{4}$$w_{6}$$1$$0$
Figure 1. Illustration of Theorem 4.11. Crosses represent $(w_{i},j)$ pairs in
$\text{supp}(\mathcal{A})$. Red large crosses represent $(w_{i},j)$ pairs on
the lower envelope $\textsf{LE}(\mathcal{A})=\text{supp}(\theta)$. Blue solid
arrows pointing to the $(w_{i},j)$ pairs in a slightly tilted angle represent
breakpoints in the allocation curve $x_{j}(\cdot)$ (i.e., $\delta^{j}_{i}>0$).
For each $(w_{a},r)\in\textsf{LE}(\mathcal{A})$, the dashed arrows pointing
directly downwards illustrate the weight $\delta^{r}_{a}$ is preserved up to
the latest deadline type, i.e., $\delta^{j}_{a}=\delta^{r}_{a}$ for all $j\geq
r$. The lower portion shows the allocation curve $x_{4}(\cdot)$ for the latest
deadline type $d=4$ with breakpoints at $v\in\\{w_{1},w_{2},w_{4},w_{6}\\}$.
Note that $x_{04}=0$ and $x_{64}=1$, and we have
$\delta^{4}_{1}+\delta^{4}_{2}+\delta^{4}_{4}+\delta^{4}_{6}=1$, where
$\delta^{4}_{i}=x_{i4}-x_{(i-1)4}$ is the jump length of $x_{4}(\cdot)$ at
$v=w_{i}$. Since $(w_{2},2)$ and $(w_{4},3)$ are consecutive points on
$\textsf{LE}(\mathcal{A})$, we have $\delta^{j}_{3}=0$ for all $j\geq 2$, and
thus $x_{4}(v)$ does not increase at $v=w_{3}$.

###  4.4. Revenue Preservation in Algorithm 2

We now prove that Algorithm 2 preserves the expected seller revenue, following
the same roadmap as in Section 3.4: We argue that the rate of decrease of
revenue of DeadlinesContinuous$(\mathcal{G}(t))$ equals the optimal revenue of
the signal $\theta(t)$.

##### Convexity of Revenue in $\textsf{DeadlinesContinuous}(\mathcal{G}(t))$.

At any time $t$, let $\tilde{\textsf{R}}(t)$ denote the optimal revenue of
$\textsf{DeadlinesContinuous}(\mathcal{G}(t))$; since
DeadlinesContinuous$(\mathcal{G}(0))$ = DeadlinesContinuous$(\mathcal{G})$ has
more constraints than Deadlines$(\mathcal{G})$, we have
$\tilde{\textsf{R}}(0)\leq\textsf{R}(\mathcal{G})$. Also,
$\tilde{\textsf{R}}(1)=0$.

Similar to Section 3.4, we consider any time interval $(t_{h-1},t_{h})$ in
which $\text{supp}(\mathcal{G}(t))$, and hence $\theta(t)$, does not change
for $t\in(t_{h-1},t_{h})$, and let the signal be $\theta$ and its
corresponding probability matrix to be $\mathbf{S}=[s_{ij}]$ over
$t\in(t_{h-1},t_{h})$. Then for any feasible solution
$\mathcal{M}\coloneqq(\\{p_{j}(\cdot)\\},\\{x_{j}(\cdot)\\})$, its revenue in
$\textsf{DeadlinesContinuous}(\mathcal{G}(t))$ is given by
$\tilde{\textsf{R}}_{\mathcal{M}}(t)\coloneqq\sum_{j=1}^{k}\sum_{i=1}^{n}f_{ij}(t)\cdot
p_{j}(v_{i}).$ Fixing this $\mathcal{M}$, for each $t\in(t_{h-1},t_{h})$ we
have

(10)
$\displaystyle\derivative{\tilde{\textsf{R}}_{\mathcal{M}}(t)}{t}=\derivative{t}\left(\sum\limits_{j=1}^{k}\sum\limits_{i=1}^{n}f_{ij}(t)\cdot
p_{j}(v_{i})\right)=-\sum\limits_{j=1}^{k}\sum_{v_{i}\in\text{values}(\mathcal{G}_{j}(t))}s_{ij}\cdot
p_{j}(v_{i}),$

where the last equality uses Eq. (7) and the fact that $s_{ij}=0$ for any
$v_{i}\notin\text{values}(\mathcal{G}_{j}(t))$ for all $j\in[1,k]$. Therefore,
for each $\mathcal{M}$, its revenue $\tilde{\textsf{R}}_{\mathcal{M}}(t)$
decreases linearly with time. Further, since the constraints of
DeadlinesContinuous$(\mathcal{G}(t))$ do not change with time, $\mathcal{M}$
remains feasible at all points in time $t\in[0,1]$ (the duration of the
algorithm), and its revenue $\tilde{\textsf{R}}_{\mathcal{M}}(t)$ is
continuous at all $t\in[0,1]$ since each $f_{ij}(t)$ changes continuously.
Since
$\tilde{\textsf{R}}(t)=\max_{\mathcal{M}}\tilde{\textsf{R}}_{\mathcal{M}}(t)$,
we have:

###### Lemma 4.12.

For any interval $(t_{h-1},t_{h})$ where $\text{supp}(\mathcal{G}(t))$ does
not change, the function $\tilde{\textsf{R}}(t)$ is convex. Further, the
function $\tilde{\textsf{R}}(t)$ is continuous for all $t\in[0,1]$, the entire
duration of the algorithm.

##### Revenue of Signals.

We now quantify the rate of decrease of $\tilde{\textsf{R}}(t)$ in the
deadlines setting.

###### Theorem 4.13.

In any interval $(t_{h-1},t_{h})$ where $\text{supp}(\mathcal{G}(t))$ does not
change, the function $\tilde{\textsf{R}}(t)$ is linear, and
$\derivative{\tilde{\textsf{R}}(t)}{t}=-\textsf{R}(\theta(t))$, where
$\textsf{R}(\theta(t))$ is the optimal revenue of Deadlines$(\theta(t))$.
Furthermore, at the end of Algorithm 2, it holds that
$\textsf{R}(\Theta^{\ast}_{\mathcal{G}})=\textsf{R}(\mathcal{G})$.

###### Proof.

Fix some $t\in(t_{h-1},t_{h})$, and assume $\text{supp}(\mathcal{G}(t))$ does
not change in $(t_{h-1},t_{h})$ and thus $\theta(t)=\theta$. Let
$\text{values}(\mathcal{G}(t))=\\{w_{1},w_{2},\ldots,w_{m}\\}$, where
$w_{1}<w_{2}<\cdots<w_{m}$. Recall that $\theta$ is an equal revenue lower
envelope distribution supported on $\textsf{LE}(\mathcal{G}(t))$ (see
Definition 4.4), and thus
$\text{values}(\theta)\subseteq\text{values}(\mathcal{G}(t))$. By Lemma 4.9,
for all $w_{i}\in\text{values}(\theta)$ we have:

(11) $\displaystyle\Pr_{(v,d)\sim\theta}[v\geq w_{i}]\cdot
w_{i}=v_{\min}(\theta)=\textsf{R}(\theta).$

Let $\mathcal{M}^{\ast}$ be the (not necessarily unique) revenue maximizing
solution to DeadlinesContinuous$(\mathcal{G}(t))$. At any time
$t^{\prime}\in(t_{h-1},t_{h})$, the function
$\tilde{\textsf{R}}_{\mathcal{M}^{\ast}}(t^{\prime})$ – the revenue of
$\mathcal{M}^{\ast}$ over $\mathcal{G}(t^{\prime})$ – is linearly decreasing.
We now calculate the rate of decrease at time $t^{\prime}$. By Theorem 4.11,
for each deadline $d=j$, the revenue $\tilde{\textsf{R}}(t)$ achieved by
$\mathcal{M}^{\ast}$ in DeadlinesContinuous$(\mathcal{G}(t))$ is a weighted
combination of the revenue for posted prices $\\{w_{1},\ldots,w_{m}\\}$ with
weights $\delta^{j}_{1},\ldots,\delta^{j}_{m}\in[0,1]$, where
$\sum_{i=1}^{m}\big{(}\mathbbm{1}^{\textsf{LE}(\mathcal{G}(t))}_{i}\cdot\delta^{k}_{i}\big{)}=1$.
Therefore,

$\displaystyle\derivative{\tilde{\textsf{R}}_{\mathcal{M}^{\ast}}(t^{\prime})}{t^{\prime}}$
$\displaystyle=\derivative{t^{\prime}}\left(\sum\limits_{j=1}^{k}\Big{(}\Pr_{(v,d)\sim\mathcal{G}(t^{\prime})}[d=j]\cdot\sum\limits_{i^{\prime}=1}^{m}\big{(}\delta^{j}_{i^{\prime}}\cdot
w_{i^{\prime}}\cdot\overline{F}_{\mathcal{G}_{j}(t^{\prime})}(w_{i^{\prime}})\big{)}\Big{)}\right)$
(using $\derivative{\mathbf{F}}{t^{\prime}}=-\mathbf{S})$
$\displaystyle=\derivative{t^{\prime}}\left(\sum\limits_{j=1}^{k}\sum\limits_{i^{\prime}=1}^{m}\big{(}\delta^{j}_{i^{\prime}}\cdot
w_{i^{\prime}}\cdot\sum_{i:v_{i}\geq
w_{i^{\prime}}}f_{ij}(t^{\prime})\big{)}\right)=\sum\limits_{j=1}^{k}\sum\limits_{i^{\prime}=1}^{m}\left(-\delta^{j}_{i^{\prime}}\cdot
w_{i^{\prime}}\cdot\sum_{i:v_{i}\geq w_{i^{\prime}}}s_{ij}(t^{\prime})\right)$
($\star$)
$\displaystyle=-\sum\limits_{i^{\prime}=1}^{m}\left(w_{i^{\prime}}\cdot\sum\limits_{j=1}^{k}\Big{(}\delta^{j}_{i^{\prime}}\cdot\sum_{i:v_{i}\geq
w_{i^{\prime}}}s_{ij}(t^{\prime})\Big{)}\right).$

Consider some $w_{i^{\prime}}\notin\text{values}(\theta)$. Suppose there exist
some $a<i^{\prime}<b$ and $r\leq r^{\prime}$ such that
$(w_{a},r),(w_{b},r^{\prime})\in\textsf{LE}(\mathcal{G}(t))=\text{supp}(\theta)$
are consecutive points in $\textsf{LE}(\mathcal{G}(t))$. By Theorem 4.11, this
implies $\delta^{j}_{i^{\prime}}=0$ for all $j\geq r$. Also, for all
$v_{i}\geq w_{i^{\prime}}$ we have $s_{ij}(t^{\prime})=0$ for all $j<r$.
Otherwise, there is no $v_{i}>w_{i^{\prime}}$ such that
$v_{i}\in\text{supp}(\theta)$; in this case we have $s_{ij}(t^{\prime})=0$ for
all $v_{i}\geq w_{i^{\prime}}$ and all $j\in[1,k]$. In both cases, the
summation $\sum_{j=1}^{k}\Big{(}\delta^{j}_{i^{\prime}}\cdot\sum_{i:v_{i}\geq
w_{i^{\prime}}}s_{ij}(t^{\prime})\Big{)}$ evaluates to 0.

On the other hand, for each $w_{i^{\prime}}\in\text{values}(\theta)$, there is
a unique $r$ such that
$(w_{i^{\prime}},r)\in\textsf{LE}(\mathcal{G}(t))=\text{supp}(\theta)$, which
(by Theorem 4.11) implies $\delta^{j}_{i^{\prime}}=\delta^{k}_{i^{\prime}}$
for all $j\in[r,k]$. Since for all $v_{i}\geq w_{i^{\prime}}$ it still holds
that $s_{ij}(t^{\prime})=0$ for all $j<r$, we have

$\sum_{j=1}^{k}\Big{(}\delta^{j}_{i^{\prime}}\cdot\sum_{i:v_{i}\geq
w_{i^{\prime}}}s_{ij}(t^{\prime})\Big{)}=\sum_{j=r}^{k}\Big{(}\delta^{j}_{i^{\prime}}\cdot\sum_{i:v_{i}\geq
w_{i^{\prime}}}s_{ij}(t^{\prime})\Big{)}=\delta^{k}_{i^{\prime}}\cdot\sum_{i:v_{i}\geq
w_{i^{\prime}}}\sum_{j=r}^{k}s_{ij}(t^{\prime})=\delta^{k}_{i^{\prime}}\cdot\Pr_{(v,d)\sim\theta}[v\geq
w_{i^{\prime}}].$

Combining the above with Eq. (11), the expression ($\star$) evaluates to

$\displaystyle\,-\sum\limits_{i:\,w_{i}\in\text{values}(\theta)}\left(\delta^{k}_{i}\cdot
w_{i}\cdot\Pr_{(v,d)\sim\theta}[v\geq w_{i}]\right)=\
-\sum\limits_{i:\,w_{i}\in\text{values}(\theta)}\big{(}\delta^{k}_{i}\cdot\textsf{R}_{\theta}\big{)}=\
-\textsf{R}({\theta}),$

where the last equality is by
$\sum_{i:\,w_{i}\in\text{values}(\theta)}\delta^{k}_{i}=\sum_{i=1}^{m}\big{(}\mathbbm{1}^{\textsf{LE}(\mathcal{G}(t^{\prime}))}_{i}\cdot\delta^{k}_{i}\big{)}=1$.

Using Lemma 4.12 and again applying the Envelope Theorem (Milgrom), the above
implies $\tilde{\textsf{R}}(t)$ is linear and hence differentiable in the
interval $t\in(t_{h-1},t_{h})$, and
$\derivative{\tilde{\textsf{R}}(t)}{t}=-\textsf{R}(\theta)=-\textsf{R}(\theta(t))$.

Note that $\theta(t)$ and thus $-\textsf{R}(\theta(t))$ changes only when some
$(v,d)$-type in the residual prior $\mathcal{G}(t)$ is exhausted; this happens
finitely many times throughout the process. Hence
$\derivative{\tilde{\textsf{R}}(t)}{t}=-\textsf{R}(\theta(t))$ is a piecewise
constant function with finitely many discontinuities, and is thus Riemann
integrable. Similar to that in the proof of Theorem 3.6, we have
$\tilde{\textsf{R}}(0)=\tilde{\textsf{R}}(\mathcal{G})$,
$\tilde{\textsf{R}}(1)=0$, and every signal $\theta_{h}$ in Algorithm 2 is
associated with weight $\omega_{h}=t_{h}-t_{h-1}$. Therefore Eq. (6) holds
exactly as is.

We observe that it is still feasible for the seller to ignore the signals by
implementing some revenue optimal auction for
$\textsf{Deadlines}(\mathcal{G})$ as the auction for each signal $\theta_{h}$
and achieve $\textsf{R}(\mathcal{G})$ as the total revenue. Thus, the theorem
follows analogously to the public budget case. ∎

Theorem 4.13 above shows that the process in Algorithm 2 preserves the
seller’s expected revenue. By Lemma 4.10, $\Theta^{\ast}_{\mathcal{G}}$ also
achieves efficiency, and thus maximizes social welfare. Hence
$\Theta^{\ast}_{\mathcal{G}}$ must maximize the expected consumer surplus, and
the analog of Theorem 3.7 on buyer optimality holds for the deadlines case as
well:

###### Theorem 4.14 (Buyer optimality for deadlines).

In the private deadlines setting, there exists a signaling scheme
$\Theta^{\ast}_{\mathcal{G}}$ for prior $\mathcal{G}$ that guarantees: (1)
$\textsf{SW}(\Theta^{\ast}_{\mathcal{G}})=\textsf{SW}^{\ast}(\mathcal{G})$;
(2) $\textsf{R}(\Theta^{\ast}_{\mathcal{G}})=\textsf{R}(\mathcal{G})$; and (3)
$\textsf{CS}(\Theta^{\ast}_{\mathcal{G}})=\textsf{CS}^{\ast}(\mathcal{G})=\textsf{SW}^{\ast}(\mathcal{G})-\textsf{R}(\mathcal{G})$.

##  5\. Impossibility of Optimal Signaling for Private Budgets

We now consider the setting with private budgets. Recall the program
Budgets$(\mathcal{G})$ from Section 2, where the type space has valuation and
budget, with the IR constraint being interim. We show that there are instances
with just two budget types in which achieving full social welfare via
signaling requires sacrificing almost all consumer surplus.

###### Theorem 5.1.

For $n=k=2$, for any given constant $\varepsilon>0$, there exists a prior
$\mathcal{G}$ in which any signaling scheme $\Theta$ that achieves efficiency
(i.e., item always sells) has
$\textsf{CS}(\Theta)\leq\varepsilon\cdot\textsf{CS}^{\ast}(\mathcal{G})$,
where
$\textsf{CS}^{\ast}(\mathcal{G})=\textsf{SW}^{\ast}(\mathcal{G})-\textsf{R}(\mathcal{G})$
is the maximum achievable consumer surplus with respect to prior
$\mathcal{G}$.

Furthermore, a similar proof shows a lower bound of $2$ on approximating the
consumer surplus even when it is no longer required that the signaling scheme
retains full social welfare.

###### Theorem 5.2.

For $n=k=2$, for any given constant $\varepsilon>0$, there exists a prior
$\mathcal{G}$ in which any signaling scheme $\Theta$ has
$\textsf{CS}(\Theta)\leq(\frac{1}{2}+\varepsilon)\cdot\textsf{CS}^{\ast}(\mathcal{G})$.

###  5.1. Proof of Theorems 5.1 and 5.2

Both Theorems 5.1 and 5.2 use the following family of instances.

###### Definition 5.0.

For any $M>1$ and $\delta<\frac{1}{M}$, let the prior $\mathcal{G}_{M,\delta}$
be supported on $\\{(v_{1},b_{1}),(v_{2},b_{2})\\}$, where
$v_{1}=1,\,b_{1}=1-\delta$, and $v_{2}=b_{2}=M$. Let
$f_{1}=\Pr_{(v,b)\sim{\mathcal{G}_{M,\delta}}}[(v,b)=(v_{1},b_{1})]=1-\delta$,
and
$f_{2}=\Pr_{(v,b)\sim{\mathcal{G}_{M,\delta}}}[(v,b)=(v_{2},b_{2})]=\delta$.
The social welfare of $\mathcal{G}_{M,\delta}$ is thus given by

(12) $\textsf{SW}^{\ast}({\mathcal{G}_{M,\delta}})=f_{1}\cdot v_{1}+f_{2}\cdot
v_{2}=(1-\delta)+\delta M.$

We now characterize the revenue optimal auction for each
$\mathcal{G}_{M,\delta}$. Let $(p_{1},x_{1})$ and $(p_{2},x_{2})$ denote the
(price, allocation probability) pairs for the two types $(v_{1},b_{1})$ and
$(v_{2},b_{2})$, respectively.

###### Lemma 5.4.

The revenue optimal auction for $\mathcal{G}_{M,\delta}$ (denoted by
${\mathcal{M}^{\ast}_{M,\delta}}$) has $(p_{1},x_{1})=(1-\delta,1-\delta)$ and
$(p_{2},x_{2})=(\delta M+(1-\delta),1)$, and raises a revenue of
$\textsf{R}({\mathcal{G}_{M,\delta}})=1-\delta+\delta^{2}M$. Furthermore, the
maximum achievable consumer surplus for $\mathcal{G}_{M,\delta}$ is
$\textsf{CS}^{\ast}({\mathcal{G}_{M,\delta}})=\delta(1-\delta)M.$

###### Proof.

The revenue optimal auction for ${\mathcal{G}_{M,\delta}}$ is captured by the
following LP:

$\displaystyle\max_{p_{1},x_{1},p_{2},x_{2}}\quad$ $\displaystyle f_{1}\cdot
p_{1}+f_{2}\cdot p_{2}$ (IC) s.t. $\displaystyle v_{2}\cdot x_{2}-p_{2}\geq
v_{2}\cdot x_{1}-p_{1},$ (IR) $\displaystyle v_{i}\cdot x_{i}-p_{i}\geq 0,$
$\displaystyle\,i\in\\{1,2\\},$ (Feasibility) $\displaystyle x_{i}\in[0,1],$
$\displaystyle\,i\in\\{1,2\\},$ (Budgets) $\displaystyle p_{i}\leq b_{i},$
$\displaystyle\,i\in\\{1,2\\}.$

To characterize the optimal auction, we first observe that $x_{2}$ must be
$1$. To see this, notice that given fixed values of $x_{1}$ and $p_{1}$, if
$x_{2}<1$, then $p_{2}<M$ by individual rationality, and it is always
favorable to simultaneously increase $x_{2}$ by $\varepsilon$ and $p_{2}$ by
$v_{2}\cdot\varepsilon$ for some small $\varepsilon>0$. Therefore let
$x_{2}=1$. Also notice that the IR and budget constraints for $i=2$ are
implied by other constraints and thus are redundant. Thus we can simplify the
LP as

$\displaystyle\max_{p_{1},x_{1},p_{2}}\quad$ $\displaystyle f_{1}\cdot
p_{1}+f_{2}\cdot p_{2}$ (IC) s.t. $\displaystyle M-p_{2}\geq M\cdot
x_{1}-p_{1},$ (IR for $i=1$) $\displaystyle x_{1}-p_{1}\geq 0,$ (Feasibility)
$\displaystyle x_{1},x_{2}\in[0,1],$ (Budget for $i=1$) $\displaystyle
p_{1}\leq 1-\delta.$

Next, observe that given any fixed $p_{1}$, the optimal solution will set

(13) $x_{1}=p_{1},\quad p_{2}=M\cdot(1-p_{1})+p_{1},$

as this does not violate any constraint and maximizes the objective. The
objective is then given by $(1-\delta)\cdot p_{1}+\delta\cdot p_{2}=\delta
M+(1-\delta M)\cdot p_{1}$. Since $\delta<\frac{1}{M}$, $1-\delta M>0$, and
thus the objective is maximized when $p_{1}$ is maximized at $1-\delta$.
Therefore, $\mathcal{M}^{\ast}_{M,\delta}$ has
$(p_{1},x_{1})=(1-\delta,1-\delta)$ and $(p_{2},x_{2})=(\delta
M+(1-\delta),1)$, and achieves a revenue of
$\textsf{R}({\mathcal{G}_{M,\delta}})=\delta M+(1-\delta
M)\cdot(1-\delta)=1-\delta+\delta^{2}M$. By Eq. (12), we have
$\textsf{CS}^{\ast}({\mathcal{G}_{M,\delta}})=\textsf{SW}^{\ast}({\mathcal{G}_{M,\delta}})-\textsf{R}({\mathcal{G}_{M,\delta}})=\delta(1-\delta)M$.
∎

##### Characterizing the revenue optimal auction for signals.

Next, we characterize the optimal auctions for any possible signal
$\theta\in\Theta$, and for each category of $\theta$, determine whether there
exists some optimal auction that is efficient, i.e., sells the item
deterministically. Consider some signal $\theta$. Let
$g_{1}=\Pr_{(v,b)\sim\theta}[(v,b)=(1,1-\delta)]$, and
$g_{2}=1-g_{1}=\Pr_{(v,b)\sim\theta}[(v,b)=(M,M)]$ be the corresponding
probabilities of the types $(1,1-\delta)$ and $(M,M)$ in $\theta$,
respectively. We have three cases:

  1. (1)

$g_{1}=1$ and $g_{2}=0$. Then $\theta$ contains only the type
$(v,b)=(1,1-\delta)$. This is then a signal with a public budget, and by Lemma
3.2, there is an optimal auction that posts a price of $1-\delta$ and raises a
revenue of $1-\delta$ and is efficient. The consumer surplus achieved by this
auction in $\theta$ is $1-(1-\delta)=\delta$.101010Note that there exist other
optimal auctions for this case that do not allocate the item
deterministically, but any such auction raises a strictly smaller consumer
surplus and thus is not suggested by the signaling scheme.

  2. (2)

$g_{1}=0$ and $g_{2}=1$. Similar to the above, $\theta$ contains only the type
$(v,b)=(M,M)$, and the optimal auction posts a price of $M$ and raises a
revenue of $M$, and is efficient. Since the price is equal to the valuation,
the consumer surplus is zero.

  3. (3)

$g_{1},g_{2}\neq 0$, i.e., both types are included in $\theta$. Observe that
the proof of Lemma 5.4 does not use the values of $f_{1}$ and $f_{2}$ up to
Eq. (13), and thus Eq. (13) holds for the optimal auction for $\theta$ as
well. Hence in any optimal auction for $\theta$ we have $x_{1}=p_{1}<1$, i.e.,
the auction is not efficient. Fix $p_{1}$, the objective for this case is then
given by $g_{1}\cdot p_{1}+g_{2}\cdot
p_{2}=g_{2}M+\big{(}g_{1}-(M-1)g_{2}\big{)}p_{1}$. Therefore, we have three
cases:

    1. (a)

If $g_{1}\geq(M-1)\cdot g_{2}$, the above objective is maximized111111If
$g_{1}=\frac{M-1}{M}$, then the objective is $g_{2}M$ for any
$p_{1}\in[0,1-\delta]$. Hence any auction in this family is optimal. For any
$p_{1}$, the corresponding consumer surplus in this case is
$g_{2}\cdot(M-p_{2})=g_{2}\cdot\big{(}M-(M\cdot(1-p_{1})+p_{1})\big{)}=p_{1}(M-1)g_{2}$.
Hence for any $M>1$ it is maximized by the auction with $p_{1}=(1-\delta)$,
i.e., ${\mathcal{M}^{\ast}_{M,\delta}}$, and the signaling scheme suggests
${\mathcal{M}^{\ast}_{M,\delta}}$ over all other optimal auctions. when
$p_{1}$ is maximized at $p_{1}=1-\delta$, i.e., the auction is exactly
${\mathcal{M}^{\ast}_{M,\delta}}$. The consumer surplus in this case is given
by

(14) $g_{2}\cdot\big{(}M-(\delta M+(1-\delta))\big{)}=(1-\delta)(M-1)g_{2}.$

    2. (b)

If $g_{1}<(M-1)\cdot g_{2}$, and the optimal auction for $\theta$ sets
$p_{1}=x_{1}=0$, and accordingly $p_{2}=M$. The consumer surplus in this case
is $0$.

We are now ready to prove Theorems 5.1 and 5.2 based on the above
characterizations.

##### Proof of Theorem 5.1.

In case 3 in the above characterization, we see that no signals in which
$g_{1},g_{2}\neq 0$ can retain efficiency. Hence any signaling scheme that
achieves efficiency does not include any signal of this type, and thus must
completely separate the two types in all signals created. Accordingly, the
lower type $(v_{1},b_{1})=(1,1-\delta)$ always pays a price of $1-\delta$, and
the higher type $(v_{2},b_{2})=(M,M)$ always pays a price of $M$. Thus the
total consumer surplus is given by

$f_{1}\cdot\big{(}v_{1}-(1-\delta)\big{)}+f_{2}\cdot(v_{2}-M)=(1-\delta)\delta=\frac{\textsf{CS}^{\ast}({\mathcal{G}_{M,\delta}})}{M},$

and the theorem follows by taking any instance $\mathcal{G}_{M,\delta}$ with
$M=\frac{1}{\varepsilon}$ and $\delta<\varepsilon$ for any given
$\varepsilon>0$.

##### Proof of Theorem 5.2.

Consider any signaling scheme $\Theta$. Based on the previous
characterizations, we can categorize all possible signals $\theta\in\Theta$ by
the consumer surplus-maximizing auction among all revenue-maximizing auctions
for $\theta$. We first observe that any signal $\theta\in\Theta$ that contain
both types $(v_{1},b_{1})$ and $(v_{2},b_{2})$ but do not admit
${\mathcal{M}^{\ast}_{M,\delta}}$ as an optimal auction (case 3b) raises zero
consumer surplus. Since the case 10 signal that contains only type
$(v_{1},b_{1})$ raises positive consumer surplus, it is always better (in
terms of total consumer surplus) to further separate this signal $\theta$ into
one that contains only type $(v_{1},b_{1})$ and another signal that only
contains type $(v_{2},b_{2})$. Hence, any signaling scheme that maximizes
consumer surplus does not include any case 3b signal. Therefore:

  * •

(Case 10) let $g_{11}$ be the total weight of all signals that contains only
type $(v_{1},b_{1})$.

  * •

(Case 2) let $g_{22}$ be the total weight of all signals that contains only
type $(v_{2},b_{2})$.

  * •

(Case 3a) let $g_{31}$ and $g_{32}$ be the total probability masses of types
$(v_{1},b_{1})$ and $(v_{2},b_{2})$ put into signals that contain both types
and admit ${\mathcal{M}^{\ast}_{M,\delta}}$ as an optimal auction. Then we
have $g_{31}\geq(M-1)\cdot g_{32}$.

Let $M=2$. The problem of optimizing consumer surplus is captured by the
following LP:

$\displaystyle\max\quad$ $\displaystyle\delta\cdot g_{11}+(1-\delta)\cdot
g_{32}$ s.t. $\displaystyle g_{11}+g_{31}=1-\delta,$ $\displaystyle
g_{22}+g_{32}=\delta,$ $\displaystyle g_{31}\geq g_{32},$ $\displaystyle
g_{11},g_{22},g_{31},g_{32}\geq 0.$

Since $M=2$, we have $\delta<\frac{1}{M}=\frac{1}{2}$, and thus
$(1-\delta)>\delta$. For any value $g_{32}\in[0,\delta]$, it is feasible and
optimal to set $g_{31}=g_{32}\leq\delta<(1-\delta)$ and $g_{11}=1-\delta-
g_{32}$. This achieves an objective of

$\delta\cdot(1-\delta-g_{32})+(1-\delta)\cdot
g_{32}=\delta(1-\delta)+(1-2\delta)\cdot g_{32}.$

Since $1-2\delta>0$, the above is maximized at $g_{32}=\delta$ for an
objective of $\delta(2-3\delta)$. Recall that for $M=2$ the benchmark consumer
surplus is $\textsf{CS}^{\ast}({\mathcal{G}_{M,\delta}})=2\delta(1-\delta)$.
Take $\delta=\frac{1}{2}-\frac{\varepsilon}{2}$. Then for all $\Theta$ and
$\varepsilon>0$ we have

$\displaystyle\textsf{CS}(\Theta)\leq\delta(2-3\delta)$
$\displaystyle=\frac{\delta(1+3\varepsilon)}{2}<\frac{\delta(1+3\varepsilon+2\varepsilon^{2})}{2}=(\frac{1}{2}+\varepsilon)\delta(2-2\delta)=(\frac{1}{2}+\varepsilon)\textsf{CS}^{\ast}({\mathcal{G}_{M,\delta}}),$

which proves the theorem.

##  6\. Conclusion

Observe that our positive results hold for two budgeted settings where the
optimal auctions with interim and ex-post IR constraints coincide, while our
negative result holds for the most general budgeted setting where imposing ex-
post IR constraints does reduce optimal revenue. In effect, our work points to
a separation between auctions with ex-post IR constraints, where optimal
signaling is possible (public budget or deadlines), and interim IR
constraints, where it is not possible (private budget setting). The main open
question is whether this separation can be formalized. We conjecture that
there is indeed an optimal signaling scheme for the general private budget
setting, when the mechanism is required to be ex-post IR instead of interim
IR. The key stumbling block is the development of a characterization analogous
to Theorem 4.11 for this setting, and we leave this as an interesting open
question.

Several other open questions arise from our work. For instance, for private
budgets with interim IR, is there an inefficient signaling scheme that
extracts a constant factor of the optimal consumer surplus, thereby providing
a positive counterpart to Theorem 5.2? Finally, can our results be generalized
to larger type spaces, for instance, spaces with three dimensions such as
value, deadline, and amount required?

##  Appendix A Proof of Theorem 3.4

See 3.4 Recall that $\mathcal{A}=\mathcal{G}(t)$ is the residual prior with
support being a subset of $\\{v_{1},v_{2},\ldots v_{n}\\}$. By Myerson’s
characterization [Myerson81], every feasible solution $(p(\cdot),x(\cdot))$ to
$\textsf{PublicContinuous}(\mathcal{A})$ must satisfy

(15) $\displaystyle p(v)=v\cdot x(v)-\int_{w=0}^{v}x(w)\differential{w}$

for all $v\in[0,v_{n}]$; furthermore, $p(\cdot)$ and $x(\cdot)$ must be
monotone non-decreasing. Define
$\textsf{Area}_{x}(v)=\int_{w=0}^{v}x(w)\differential{w}$. Then
$\textsf{Area}_{x}(v)$ is convex in $[0,v_{n}]$, and
$\textsf{PublicContinuous}(\mathcal{A})$ can be simplified to

$\displaystyle\text{B3}(\mathcal{A})\coloneqq\max_{x(\cdot)}\quad$
$\displaystyle\sum_{j=1}^{n}\Big{(}f_{\mathcal{A}}(v_{j})\cdot\big{(}v_{j}\cdot
x(v_{j})-\textsf{Area}_{x}(v_{j})\big{)}\Big{)}$ (Budget) s.t. $\displaystyle
v_{n}\cdot x(v_{n})-\textsf{Area}_{x}(v_{n})\leq b,$ $\displaystyle x(0)\geq
0,\,x(v_{n})\leq 1,\,x(v)\text{ is monotone non-decreasing in }[0,v_{n}].$

Let $\text{supp}(\mathcal{A})=\\{w_{1},w_{2},\ldots,w_{m}\\}$, where
$0<w_{1}<\cdots<w_{m}\leq v_{n}$, and let $w_{0}=0$ and $w_{m+1}=v_{n}$, which
can possibly be equal to $w_{m}$. We next simplify B3$(\mathcal{A})$ one step
further, based on the observation that there always exists an optimal solution
to B3$(\mathcal{A})$ in which $x(v)$ is a constant over each interval
$[w_{i},w_{i+1})$ and thus $\textsf{Area}_{x}(v)$ is piecewise linear.

###### Lemma A.1.

Given an optimal solution $x^{\ast}(\cdot)$ to B3$(\mathcal{A})$, there exists
another optimal solution $\hat{x}(\cdot)$ in which
$\hat{x}(w_{m+1})=\hat{x}(v_{n})=x^{\ast}(v_{n})$, and
$\hat{x}(v)=\frac{\int_{w=w_{i}}^{w_{i+1}}x^{\ast}(w)\differential{w}}{w_{i+1}-w_{i}}$
for all $v\in[w_{i},w_{i+1})$, and $w_{i}<v_{n}$.

###### Proof.

Let $x^{\ast}(\cdot)$ be an optimal solution to B3$(\mathcal{A})$, and
$\hat{x}(\cdot)$ as stated above. This implies

$\displaystyle\textsf{Area}_{\hat{x}}(w_{i})=\sum\limits_{i^{\prime}=0}^{i-1}\left((w_{i^{\prime}+1}-w_{i^{\prime}})\cdot\frac{\int_{w=w_{i^{\prime}}}^{w_{i^{\prime}+1}}x^{\ast}(w)\differential{w}}{w_{i^{\prime}+1}-w_{i^{\prime}}}\right)=\sum\limits_{i^{\prime}=0}^{i-1}\int\limits_{w=w_{i^{\prime}}}^{w_{i^{\prime}+1}}x^{\ast}(w)\differential{w}=\textsf{Area}_{x^{\ast}}(w_{i})$

for all $i\in\\{0,1,\ldots,m+1\\}$. Note that $v_{n}=w_{m+1}$ and
$\hat{x}(v_{n})=x^{\ast}(v_{n})$. This means the budget constraint is exactly
preserved by $\hat{x}(\cdot)$. It is easy to see $\hat{x}(\cdot)$ remains
bounded in $[0,1]$ and is non-decreasing; hence it is feasible.

By monotonicity of $x^{\ast}(\cdot)$, we also have $\hat{x}(w_{i})\geq
x^{\ast}(w_{i})$ for all $i\in\\{0,1,\ldots,m+1\\}$. Hence, for all
$j\in[1,n]$, either $v_{j}\notin\text{supp}(\mathcal{A})$ (so
$f_{\mathcal{A}}(v_{j})=0$), or $v_{j}=w_{i}$ for some $i$, for which we have

$\displaystyle\hat{p}(v_{j})=\hat{p}(w_{i})=w_{i}\cdot\hat{x}(w_{i})-\textsf{Area}_{\hat{x}}(w_{i})\geq
w_{i}\cdot
x^{\ast}(w_{i})-\textsf{Area}_{x^{\ast}}(w_{i})=p^{\ast}(w_{i})=p^{\ast}(v_{j}),$

where $\hat{p}(v)$ and $p^{\ast}(v)$ are the prices associated with value $v$
given by Eq. (15) when the allocation function is $\hat{x}(\cdot)$ and
$x^{\ast}(\cdot)$, respectively. Summing this up for all
$v_{j}\in\text{supp}(\mathcal{A})$ implies $\hat{x}(\cdot)$ achieves (in
B3$(\mathcal{A})$) an objective value of at least that given by
$x^{\ast}(\cdot)$. Hence $\hat{x}(\cdot)$ is also optimal for
B3$(\mathcal{A})$. ∎

By Lemma A.1, we only need to consider solutions of the form $\hat{x}(\cdot)$.
Specifically, we now have the extra constraint that $x(v)=x(w_{i})$ for all
$v\in[w_{i},w_{i+1})$ (again using $w_{0}=0$ and $w_{m+1}=v_{n}$). Therefore,
for all $i\in[1,m]$ we now have

$\displaystyle\textsf{Area}_{x}(w_{i})=\sum\limits_{i^{\prime}=0}^{i-1}\big{(}(w_{i^{\prime}+1}-w_{i^{\prime}})\cdot
x(w_{i^{\prime}})\big{)}.$

Thus, the decision variables are now $\\{x_{i}\coloneqq x(w_{i})\\}$ for
$i\in[0,m]$, and $\text{B3}(\mathcal{A})$ is equivalent to

$\displaystyle\text{B4}(\mathcal{A})\coloneqq\max_{\\{x_{i}\\}}\quad$
$\displaystyle\sum_{i=1}^{m}\Big{(}f_{\mathcal{A}}(w_{i})\cdot\big{(}w_{i}\cdot
x_{i}-\textsf{Area}_{x}(w_{i})\big{)}\Big{)}$ (16) s.t. $\displaystyle
w_{m}\cdot x_{m}-\textsf{Area}_{x}(w_{m})\leq b,$ $\displaystyle 0\leq
x_{0}\leq x_{1}\leq\cdots\leq x_{m}\leq 1.$

Next, we show that assuming $w_{1}<b$, there always exists an optimal solution
to B4$(\mathcal{A})$ in which (i) the buyer with the highest valuation $w_{m}$
of nonzero probability mass in $\mathcal{A}$ gets the item deterministically,
and (ii) the buyer with the dummy valuation $w_{0}$ is never allocated the
item.

###### Lemma A.2.

If $w_{1}<b$, there exists an optimal solution $\\{\hat{x}_{i}\\}$ to
B4$(\mathcal{A})$ such that $\hat{x}_{m}=1$ and $\hat{x}_{0}=0$.

###### Proof.

Consider any optimal solution $\\{x^{\ast}_{i}\\}$ to B4$(\mathcal{A})$ with
$x^{\ast}_{m}<1$. Let $\varepsilon=1-x^{\ast}_{m}$. Consider another solution
$\\{\tilde{x}_{i}\\}$ such that $\tilde{x}_{i}=x^{\ast}_{i}+\varepsilon$ for
all $i\in[0,m]$. This implies (for all $i\in[0,m]$)

$\displaystyle\textsf{Area}_{\tilde{x}}(w_{i})=\textsf{Area}_{x^{\ast}}(w_{i})+\varepsilon\cdot
w_{i}$

and thus

$\displaystyle w_{i}\cdot\tilde{x}_{i}-\textsf{Area}_{\tilde{x}}(w_{i})$
$\displaystyle=w_{i}\cdot\big{(}x^{\ast}_{i}+\varepsilon\big{)}-\big{(}\textsf{Area}_{x^{\ast}}(w_{i})+\varepsilon\cdot
w_{i}\big{)}=w_{i}\cdot x^{\ast}_{i}-\textsf{Area}_{x^{\ast}}(w_{i}).$

Therefore, both the budget constraint (Eq. (16)) and the objective value are
exactly preserved. Since $\\{\tilde{x}_{i}\\}\in[0,1]$ and is monotone non-
decreasing, it is feasible and also optimal in B4$(\mathcal{A})$.

Note that $\tilde{x}_{0}>0$ and thus $\textsf{Area}_{\tilde{x}}(w_{1})>0$,
i.e., the point $(w_{1},0)$ lies strictly below
$\textsf{Area}_{\tilde{x}}(\cdot)$. Next, pick the smallest $y$ such that

(17) $\displaystyle\textsf{Area}_{\tilde{x}}(w_{i})=(w_{i}-w_{1})\cdot y$

is satisfied for some $i\in[1,m]$, or equivalently, the straight line
$\ell_{y}(\cdot)$ passing $(w_{1},0)$ with slope $y$ is tangent to the curve
$\textsf{Area}_{\tilde{x}}(\cdot)$ at some $v=v^{\prime}$ (see Figure 2). Note
that the slope of $\textsf{Area}_{\tilde{x}}(\cdot)$ between
$v\in(w_{i},w_{i+1})$ is $\tilde{x}_{i}$. By convexity of
$\textsf{Area}_{\tilde{x}}(\cdot)$, we have $y\geq\tilde{x}_{1}$ (otherwise
$\ell_{y}(\cdot)$ stays strictly below $\textsf{Area}_{\tilde{x}}(\cdot)$ for
all $v\geq w_{1}$). Since $\textsf{Area}_{\tilde{x}}(\cdot)$ is piecewise
linear in each $v\in[w_{i},w_{i+1}]$, $v^{\prime}$ must lie in
$\\{w_{1},\ldots,w_{m}\\}$.

$v$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$\textsf{Area}_{\tilde{x}}(v)$$\ell_{y}(\cdot)$
Figure 2. $\ell_{y}(\cdot)$ is tangent to $\textsf{Area}_{\tilde{x}}(\cdot)$
at $v^{\prime}=w_{3}$.

Let $y^{\prime}=\min\\{y,1\\}$, and consider another solution
$\\{\hat{x}_{i}\\}$ such that $\hat{x}_{0}=0$, and
$\hat{x}_{i}=\max\\{y^{\prime},\tilde{x}_{i}\\}\geq\tilde{x}_{i}$ for all
$1\leq i\leq m$. Then $\hat{x}_{i}\in[0,1]$ and is monotone non-decreasing,
and we have

(18) $\displaystyle\textsf{Area}_{\hat{x}}(v)\leq\begin{cases}(v-w_{1})\cdot
y=\ell_{y}(v),&v\in[w_{1},v^{\prime}],\\\
\textsf{Area}_{\tilde{x}}(v),&v\in[v^{\prime},w_{m}],\end{cases}$

where the equality holds if $y^{\prime}=y$. This implies
$\textsf{Area}_{\hat{x}}(v)\leq\textsf{Area}_{\tilde{x}}(v)$ for all
$v\in[0,w_{m}]$, and thus

(19) $\displaystyle w_{i}\cdot\hat{x}_{i}-\textsf{Area}_{\hat{x}}(w_{i})\geq
w_{i}\cdot\tilde{x}_{i}-\textsf{Area}_{\hat{x}}(w_{i})\geq
w_{i}\cdot\tilde{x}_{i}-\textsf{Area}_{\tilde{x}}(w_{i})$

holds for all $i=1,2,\ldots,m$.

Recall that $\tilde{x}_{m}=1$. Suppose $y\leq 1$ and thus $y^{\prime}=y$. Then
$\hat{x}_{m}=\tilde{m}=1$, and by Eq. (18) we have
$\textsf{Area}_{\hat{x}}(w_{m})=\textsf{Area}_{\tilde{x}}(w_{m})$. Hence all
equalities in Eq. (19) must hold for $i=m$. Otherwise, $y>1$, and
$\hat{x}_{i}=1$ for all $i\in[1,m]$. Then we have
$w_{m}\cdot\hat{x}_{m}-\textsf{Area}_{\hat{x}}(w_{m})=w_{m}-(w_{m}-w_{1})=w_{1}<b$.
This implies $\\{\hat{x}_{i}\\}$ satisfies the budget constraint in both
cases.

Finally, observe that by Eq. (19), each term in the objective of
B4$(\mathcal{A})$ is weakly higher when the allocation variables are
$\\{\hat{x}_{i}\\}$ then when they are $\\{\tilde{x}_{i}\\}$. Hence
$\\{\hat{x}_{i}\\}$ is optimal to B4$(\mathcal{A})$. ∎

Finally, putting the previous lemmas together, we show that the optimal
objective of B4$(\mathcal{A})$ equals the revenue achieved by a distribution
over posted-price schemes when $w_{1}<b$.

##### Completing proof of Theorem 3.4.

Assume $w_{1}<b$. Then by Lemma A.2, there is an optimal solution
$\\{\hat{x}_{i}\\}$ to B4$(\mathcal{A})$ such that $\hat{x}_{0}=0$ and
$\hat{x}_{m}=1$. Let $\hat{x}(w)=\hat{x}_{i}$ for all $w\in[w_{i},w_{i+1})$.
Let
$\\{w^{\prime}_{1},w^{\prime}_{2},\ldots,w^{\prime}_{m^{\prime}}\\}\coloneqq\\{w_{i}\mid\hat{x}_{i}>\hat{x}_{i-1}\\}$
be the set of vertices of $\textsf{Area}_{\hat{x}}(\cdot)$ (equivalently,
valuations whose corresponding allocation probability is strictly higher than
the previous type of buyer). Let $w^{\prime}_{0}=0$. Then for
$j\in\\{1,\ldots,m^{\prime}\\}$ denote allocation function $x_{j}(\cdot)$ such
that

$x_{j}(w_{i})=\begin{cases}1,\quad&w_{i}\geq w^{\prime}_{j};\\\
0,\quad&w_{i}<w^{\prime}_{j}.\end{cases}$

This corresponds to posting a price of $w^{\prime}_{j}$ and selling to only
the buyers with valuation $w_{i}\geq w^{\prime}_{j}$ with probability $1$.
Therefore, the revenue generated by $\\{x_{j}(w_{i})\\}$ is

(20) $\displaystyle\sum_{i=1}^{m}\big{(}f_{\mathcal{A}}(w_{i})\cdot
p_{j}(w_{i})\big{)}=\overline{F}_{\mathcal{A}}(w^{\prime}_{j})\cdot
w^{\prime}_{j},$

where $p_{j}(w_{i})\coloneqq w_{i}\cdot
x_{j}(w_{i})-\int_{w=0}^{w_{i}}x_{j}(w)\differential{w}$ is the price
associated with buyer with valuation $w_{i}$.

Let $\delta_{j}=\hat{x}(w^{\prime}_{j})-\hat{x}(w^{\prime}_{j-1})$. Then for
all $i=1,2,\ldots,m$ we can write

$\hat{x}(w_{i})=\sum\limits_{j=1}^{m^{\prime}}\big{(}\delta_{j}\cdot
x_{j}(w_{i})\big{)},\quad\hat{p}(w_{i})=\sum\limits_{j=1}^{m^{\prime}}\big{(}\delta_{j}\cdot
p_{j}(w_{i})\big{)},$

where $\hat{p}(w_{i})\coloneqq
w_{i}\cdot\hat{x}(w_{i})-\int_{w=0}^{w_{i}}\hat{x}(w)\differential{w}$.
Therefore, the optimal objective for B4$(\mathcal{A})$ is

$\displaystyle\sum\limits_{i=1}^{m}\big{(}f_{\mathcal{A}}(w_{i})\cdot\hat{p}(w_{i})\big{)}\Big{)}$
$\displaystyle=\sum\limits_{i=1}^{m}\Big{(}f_{\mathcal{A}}(w_{i})\cdot\sum\limits_{j=1}^{m^{\prime}}\big{(}\delta_{j}\cdot
p_{j}(w_{i})\big{)}\Big{)}$
$\displaystyle=\sum\limits_{j=1}^{m^{\prime}}\Big{(}\delta_{j}\cdot\sum\limits_{i=1}^{m}\big{(}f_{\mathcal{A}}(w_{i})\cdot
p_{j}(w_{i})\big{)}\Big{)}=\sum\limits_{j=1}^{m^{\prime}}\big{(}\delta_{j}\cdot\overline{F}_{\mathcal{A}}(w^{\prime}_{j})\cdot
w^{\prime}_{j}\big{)},$

where the last equality follows from Eq. (20). Finally, notice that since
$\hat{x}(w^{\prime}_{m^{\prime}})=\hat{x}(w_{m})=1$, we have
$\sum_{j=1}^{m^{\prime}}\delta_{j}=\hat{x}(w_{m})-\hat{x}(w^{\prime}_{0})=1$.
This proves the theorem. ∎

##  Appendix B Proof of Theorem 4.11

See 4.11

####  B.0.1. Simplification of $\textsf{DeadlinesContinuous}(\mathcal{A})$
into discrete set of decision variables

Recall $\mathcal{A}=\mathcal{G}(t)$ is the residual prior with support
$\text{supp}(\mathcal{A})\subseteq\text{supp}(\mathcal{G})=\\{v_{1},v_{2},\ldots,v_{n}\\}\times\\{1,2,\ldots,k\\}$.
By Myerson’s characterization [Myerson81], every feasible solution
$\big{(}\\{p_{j}(\cdot)\\},\\{x_{j}(\cdot)\\}\big{)}$ for
$\textsf{DeadlinesContinuous}(\mathcal{A})$ must satisfy

(21) $\displaystyle p_{j}(v)\coloneqq v\cdot
x_{j}(v)-\int_{w=0}^{v}x_{j}(w)\differential{w}$

for all $v\in[0,v_{n}]$ and $j\in[1,k]$, and all $\\{x_{j}(\cdot)\\}$ are
monotone non-decreasing. Therefore, for each $j\in[1,k]$, the area below the
allocation curve $x_{j}(\cdot)$, denoted
$\textsf{Area}_{x}(v,j)\coloneqq\int_{w=0}^{v}x_{j}(w)\differential{w}$, is
convex in $[0,v_{n}]$. Therefore, $\textsf{DeadlinesContinuous}(\mathcal{A})$
can be simplified to

$\displaystyle\text{D3}(\mathcal{A})\coloneqq\max_{\\{x_{j}(\cdot)\\}}\quad$
$\displaystyle\sum_{j=1}^{k}\left(\Pr_{(v,d)\sim\mathcal{A}}[d=j]\cdot\sum_{i=1}^{n}\Big{(}f_{\mathcal{A}_{j}}(v_{i})\cdot\big{(}v_{i}\cdot
x_{j}(v_{i})-\textsf{Area}_{x}(v_{i},j)\big{)}\Big{)}\right)$ (Inter-deadline
IC) s.t.
$\displaystyle\textsf{Area}_{x}(v,j)\geq\textsf{Area}_{x}(v,j-1),\quad\forall
v\in[0,v_{n}],\,2\leq j\leq k,$ $\displaystyle x_{j}(0)\geq
0,\,x_{j}(v_{n})\leq 1,\,x_{j}(v)\text{ is monotone non-decreasing in
}[0,v_{n}]\text{ for all }j.$

Let $\text{values}(\mathcal{A})=\\{w_{1},w_{2},\ldots,w_{m}\\}$, where
$0<w_{1}<\cdots<w_{m}\leq v_{n}$, and let $w_{0}=0$ and $w_{m+1}=v_{n}$, which
can possibly be equal to $w_{m}$. Analogous to Lemma A.1, we next simplify
D3$(\mathcal{A})$ such that for all $j$, $x_{j}(v)$ is piecewise constant, and
$\textsf{Area}_{x}(v,j)$ is piecewise linear, in each interval
$v\in[w_{i},w_{i+1})$.

###### Lemma B.1.

Given an optimal solution $\\{x^{\ast}_{j}(\cdot)\\}$ to D3$(\mathcal{A})$,
there exists another optimal solution $\\{\hat{x}_{j}(\cdot)\\}$ in which for
all $j=1,\ldots,k$ we have
$\hat{x}_{j}(w_{m+1})=\hat{x}_{j}(v_{n})=x^{\ast}_{j}(v_{n})$, and
$\hat{x}_{j}(v)=\frac{\int_{w=w_{i}}^{w_{i+1}}x^{\ast}_{j}(w)\differential{w}}{w_{i+1}-w_{i}}$
for all $v\in[w_{i},w_{i+1})$, and $w_{i}<v_{n}$.

###### Proof.

Let $\\{x^{\ast}_{j}(\cdot)\\}$ be an optimal solution to D3$(\mathcal{A})$,
and let $\\{\hat{x}_{j}(\cdot)\\}$ as stated above. By the same arguments in
the proof of Lemma A.1, this implies

(22)
$\displaystyle\textsf{Area}_{\hat{x}}(w_{i},j)=\textsf{Area}_{x^{\ast}}(w_{i},j)$

holds for all $i\in[0,m+1]$ and $j\in[1,k]$. By Eq. (22) and the inter-
deadline IC constraints in D3$(\mathcal{A})$, we have
$\textsf{Area}_{\hat{x}}(w_{i},j)=\textsf{Area}_{x^{\ast}}(w_{i},j)\geq\textsf{Area}_{x^{\ast}}(w_{i},j-1)=\textsf{Area}_{\hat{x}}(w_{i},j-1)$
for all $i\in[0,m+1]$ and $j\in[2,k]$. Since both
$\textsf{Area}_{\hat{x}}(v,j)$ and $\textsf{Area}_{\hat{x}}(v,j-1)$ are
continuous and piecewise linear in each $v\in[w_{i},w_{i+1})$, this implies
$\textsf{Area}_{\hat{x}}(v,j)$ must be weakly above
$\textsf{Area}_{x^{\ast}}(v,j-1)$ at all $v\in[w_{0},w_{m+1}]=[0,v_{n}]$,
i.e., $\\{\hat{x}_{j}(\cdot)\\}$ satisfies all inter-deadline IC constraints.
Similar to the case in the proof of Lemma A.1, it can be verified that each
$\\{\hat{x}_{j}(\cdot)\\}$ is monotone non-decreasing and in $[0,1]$. Hence
$\\{\hat{x}_{j}(\cdot)\\}$ is feasible in D3$(\mathcal{A})$.

For all $j$, by the monotonicity of $x^{\ast}_{j}(\cdot)$ and the construction
of $\hat{x}_{j}(\cdot)$, we have $\hat{x}_{j}(w_{i})\geq x^{\ast}_{j}(w_{i})$
for all $i\in[0,m]$. Hence, for all $i^{\prime}\in[1,n]$, either
$v_{i^{\prime}}\notin\text{values}(\mathcal{A})$ (so
$f_{\mathcal{A}_{j}}(v_{i^{\prime}})=0$), or $v_{i^{\prime}}=w_{i}$ for some
$i^{\prime}$. Analogous to Eq. (19), for all such
$v_{i^{\prime}}\in\text{values}(\mathcal{A})$, the price
$\hat{p}_{j}(v_{i^{\prime}})$ (given by the allocation variables
$\\{\hat{x}_{j}(\cdot)\\}$) is at least the old price
$p^{\ast}_{j}(v_{i^{\prime}})$ (given by $\\{x^{\ast}_{j}(\cdot)\\}$). Since
this holds for all $j$, $\\{\hat{x}_{j}(\cdot)\\}$ gives in D3$(\mathcal{A})$
an objective at least that given by $\\{x^{\ast}_{j}(\cdot)\\}$, and thus is
optimal. ∎

By Lemma B.1, we only need to consider solutions in the form of
$\\{\hat{x}_{j}(\cdot)\\}$, i.e., for all $j\in[1,k]$ we require that
$x_{j}(v)=x_{j}(w_{i})$ for all $v\in[w_{i},w_{i+1})$ (again using $w_{0}=0$
and $w_{m+1}=v_{n}$). Therefore, the decision variables are now
$\\{x_{ij}\coloneqq x_{j}(w_{i})\\}$ for $i\in[0,m]$ and $j\in[1,k]$.

Throughout the rest of the proof, given the set of decision variables
$\\{x_{ij}\\}$, for all $i_{1}\leq i_{2}\in[0,m]$ and $j\in[1,k]$, we denote
the area below the curve $x_{j}(v)$ from $v=w_{i_{1}}$ to $v=w_{i_{2}}$ as

$\textsf{Area}_{x}(w_{i_{1}},w_{i_{2}},j)\coloneqq\sum_{i^{\prime}=i_{1}}^{i_{2}-1}\big{(}(w_{i^{\prime}+1}-w_{i^{\prime}})\cdot
x_{i^{\prime}j}\big{)}.$

For convenience we also let
$\textsf{Area}_{x}(w_{i},j)\coloneqq\textsf{Area}_{x}(w_{0},w_{i},j)$.
Therefore, D3$(\mathcal{A})$ is equivalent to

$\displaystyle\text{D4}(\mathcal{A})\coloneqq\max_{x_{ij}}\quad$
$\displaystyle\sum_{j=1}^{k}\left(\Pr_{(v,d)\sim\mathcal{A}}[d=j]\cdot\sum_{i=1}^{m}\Big{(}f_{\mathcal{A}_{j}}(w_{i})\cdot\big{(}w_{i}\cdot
x_{ij}-\textsf{Area}_{x}(w_{i},j)\big{)}\Big{)}\right)$ s.t.
$\displaystyle\textsf{Area}_{x}(w_{i},j)\geq\textsf{Area}_{x}(w_{i},j-1),\quad$
$\displaystyle i\in[1,m],\,j\in[2,k];$ $\displaystyle 0\leq x_{0j}\leq
x_{1j}\leq\cdots\leq x_{mj}\leq 1,\quad$ $\displaystyle j\in[1,k].$

####  B.0.2. Aligning the Allocation Curves

In the following, we aim to further characterize the optimal solution to
D4$(\mathcal{A})$. We will show the following theorem that shows the
allocation curves are aligned below the lower envelope:

###### Theorem B.2.

There exists a set of optimal allocation variables $\\{\hat{x}_{ij}\\}$ to
D4$(\mathcal{A})$ in which for all $(i,j)$ such that