# Discrete Single-Parameter Optimal Auction Design111Supported through the DFG
CRC/TRR 154, subproject B07.

Yiannis Giannakopoulos University of Glasgow. Email:
<EMAIL_ADDRESS>Johannes Hahn University of Technology,
Nuremberg. Email<EMAIL_ADDRESS>
(June 11, 2024)

###### Abstract

We study the classic single-item auction setting of Myerson, but under the
assumption that the buyers’ values for the item are distributed over _finite_
supports. Using strong LP duality and polyhedral theory, we rederive various
key results regarding the revenue-maximizing auction, including the
characterization through virtual welfare maximization and the optimality of
deterministic mechanisms, as well as a novel, generic equivalence between
dominant-strategy and Bayesian incentive compatibility.

Inspired by this, we abstract our approach to handle more general auction
settings, where the feasibility space can be given by arbitrary convex
constraints, and the objective is a convex combination of revenue and social
welfare. We characterize the optimal auctions of such systems as generalized
virtual welfare maximizers, by making use of their KKT conditions, and we
present an analogue of Myerson’s payment formula for general discrete single-
parameter auction settings. Additionally, we prove that total unimodularity of
the feasibility space is a sufficient condition to guarantee the optimality of
auctions with integral allocation rules.

Finally, we demonstrate this KKT approach by applying it to a setting where
bidders are interested in buying feasible flows on trees with capacity
constraints, and provide a combinatorial description of the (randomized, in
general) optimal auction.

##  1 Introduction

The design of optimal auctions [Kri09, Mil04] that maximize the seller’s
revenue is a cornerstone of the field of mechanism design (see, e.g., [JR11,
Ch. 9] and [HK07]), established into prominence by the highly-influential work
of [Mye81], and traced back to the seminal work of [Vic61].

In its most classical form [Mye81], which is the basis for the setting we are
studying in our paper as well, there is a single item to sell and the problem
is modelled as a Bayesian game. The seller has only incomplete information
about the bidders’ true valuations of the item, in the form of independent
(but not necessarily identical) probability distributions; these distributions
are assumed to be public knowledge across all participants in the auction. The
players/bidders submit bids to the auctioneer/seller and the seller decides
(a) who gets the item, and with what probability (since lotteries are
allowed), and (b) how much the winning bidders are charged for this
transaction.

In this game formulation, the strategies of the players are the different bids
they can submit, and it could well be the case that bidders misreport their
true valuations, if this can result in maximizing their own personal utility.
Therefore, a desirable feature of mechanism design in such settings is the
implementation of auctions which provably guarantee that truth-telling is an
_equilibrium_ of the game; such auctions are called _truthful_ (or _incentive
compatible (IC)_). Perhaps surprisingly, the celebrated Revelation Principle
of [Mye81] ensures that restricting our attention within the class of such
well-behaved selling mechanism is without loss for our purposes.

The seminal work of [Mye81] provides a complete and mathematically satisfying
characterization of revenue-maximizing truthful auctions in the aforementioned
single-item setting, under the assumption that valuation/bidding spaces are
_continuous_. It explicitly constructs an optimal auction that (a) is
deterministic, i.e. the item is allocated to a single bidder (with full
probability), or not sold at all, (b) satisfies truthfulness in a very strong
sense, namely under dominant-strategy equilibrium, and not just in-expectation
(see Section 2.2 for more details), and (c) has a very elegant description,
enabled via the well-known _virtual valuation_ “trick” (see (1)); this casts
the problem into the domain of welfare-maximization, simplifying it
significantly by stripping away the game-theoretic incentives components, and
transforming it to a “purely algorithmic” optimization problem — resembling
the familiar, to any computer scientist, notion of a reduction (a
formalization of this connection, even for more general environments, can be
found in the work of [CDW12, CDW13]).

Still, the assumption of continuity may be considered as too strong for many
practical, and theoretical, purposes. Any conceivable instantiation of an
auction on a computing system will require some kind of discretization; not
only as a trivial, unavoidable consequence of the fundamentally discrete
nature of computation (i.e., “bits”), but also for practical reasons: bids are
usually expected to be submitted as increments of some common denomination
(e.g., “cents”). And any implementation of optimal auction design as an
optimization problem, would need to be determined by finitely many parameters
and variables, to be passed, e.g., to some solver. Furthermore, although many
of the key properties and results for the continuous setting can be derived as
a limiting case of a sequence of discrete ones, in general the opposite is not
true: most of the techniques used in traditional auction theory rely on real
analysis and continuous probability, thus breaking down when called to be
applied to discrete spaces.

The above reasons highlight the importance of deriving a clear and robust
theory of optimal auction design, under the assumption of _finite_ value
spaces. In other words, a discrete analogue of Myerson’s [Mye81] theory.
During the last couple of decades, various papers within the field of
algorithmic game theory have dealt with this task; see Section 1.1 for a more
detailed overview. Our goal in this paper is to first rederive existing key
results, in a unified way, with an emphasis on clarity, simplicity, and
rigorousness; and, do this via purely discrete optimization tools (namely, LP
duality and polyhedral combinatorics), “agnostically”, rather than trying to
mimic and discretize Myerson’s [Mye81] approach for the continuous setting.
Secondly, this comprehensiveness and transparency allows us to lift our
approach up to handle quite general single-parameter mechanism design
environments, by concisely formulating our problem as an elegant KKT system.

###  1.1 Related Work

To the best of our knowledge, the first to explicitly study optimal auction
design at a discrete setting were [BP07] and [Elk07]; the latter offers a more
complete treatment, providing a natural discretization of Myerson’s [Mye81]
techniques, including “ironing” of non-regular distributions (see Section
3.4). A limitation of [Elk07] is that it establishes that the discrete
analogue of Myerson’s auction is optimal within the more restrictive class of
dominant-strategy incentive compatible (DSIC) mechanisms, instead of using the
standard, weaker notion of Bayesian incentive compatibility (BIC).

In a discussion paper, [MV04] study discrete auction environments with
identical bidders under BIC, providing a simpler, equivalent characterization
of truthfulness, through a set of local constraints. We will make critical use
of this characterization, appropriately adapted to our general, non-symmetric
setting of our paper (see Section 2.3). The treatment of [MV04] puts emphasis
on linear programming (LP) formulations, and derive an interesting, flow-based
description of optimality for general, multi-dimensional mechanism design
settings; the monograph of [Voh11] provides a comprehensive treatment of this
approach.

All aforementioned approaches work, essentially, by adapting the keys steps of
Myerson’s derivations, from the continuous to the discrete setting. [CDW19]
provide a totally different, and very powerful, approach based on Lagrangian
duality. Conceptually, their paper is clearly the closest to ours. [CDW19]
followed a line of work, where duality proved very useful in designing optimal
multiple-item auctions in the continuous case (see, e.g., [DDT17, GK18]).
Although the duality framework of [CDW19] is fundamentally discrete, it was
also designed for multi-dimensional revenue-maximization, a notoriously
difficult and complex problem. Therefore, its instantiation for a single-
parameter Myersonian setting (see [CDW19, Sec. 4]) results, arguably, in a
rather involved presentation. One of the goals of our paper is exactly to
demystify duality for single-item domains, by making use of classical LP
duality, particularly tailored for our problem, instead of the more obscure
Lagrangian flows interpretation in [CDW19], resulting in greater transparency
and a wider spectrum of questions that we can attack (see Section 3).

###  1.2 Our Results

We begin our presentation by introducing our _single-parameter_ auction design
setting, and fixing some overarching notation, in Section 2. Our model
formulation is deliberately general, allowing for arbitrary feasibility
domains $\mathcal{A}$ for the auction’s allocation; we will specialize this to
the standard distributional simplex when studying the classical Myersonian
single-item setting in Section 3, however we want to be able to capture the
abstract convex environments we study later in Section 4. Importantly, in
Section 2.2 we discuss in detail the two different notions of truthfulness
used for our problem, and in Section 2.3 we provide a local characterization
of truthfulness, essentially proved in [MV04], which we will extensively use
in our optimization formulation throughout our paper.

Section 3 includes our rederivation of the key components of Myerson’s [Mye81]
theory for single-item revenue-maximization, but for finite-support
distributions, as well as some novel results. They all arise, in a unified
way, through a chain of traditional LP duality, presented in Section 3.1 (see
Figure 1 for a concise pictorial view). The resulting revenue-maximizing
auction, together with some key results characterizing optimality, are given
in the “master” Theorem 1: in a nutshell, the optimal auction first transforms
the submitted bids to _virtual_ bids and then _irons_ them, finally allocating
the item to the highest non-negative (virtual, ironed) bidder. Similar to the
classical results of [Mye81] for continuous domains, this auction turns out to
be deterministic and truthful in the strongest DSIC sense, “for free”,
although we are optimizing within the much wider space of lotteries under BIC.
To the best of our knowledge, Point 2 where we formalize the equivalence of
DSIC and BIC, under revenue-maximization, as a more fundamental and general
consequence of the polyhedral structure of our feasibility space, rather than
just a feature of the particular optimal auction solution format, is novel.
The remaining subsections 3.2, 3.3, and 3.4, are dedicated to elaborating and
formally proving the various components of Theorem 1. A point worth noting is
that our virtual value (13) and ironing (19) transformations are not “guessed”
and then proven to impose optimality, as is the case with prior work in the
area, but rather arise organically as a necessity of our strong LP duality
technique.

Inspired by the transparency of our duality framework in Section 3, we try to
generalize our approach to a more general single-parameter mechanism design
setting, where the feasibility space $\mathcal{A}$ is given by arbitrary
convex constraints, and the optimization objective is a convex combination of
revenue and social welfare; see Section 4.1. Our results are summarized in
master Theorem 2, which is essentially the analogue of Theorem 1. Given the
generality of our model in this section, we have to depart from our basic LP
duality tools of Section 3, and make use of the more general KKT conditions
framework, including duality and complementary slackness; our KKT formulation
is discussed in Section 4.2. The abstraction of our model allows for a very
concise description of the optimal auction’s allocation and payment rules (see
Section 4.3). Similarly to the single-item setting of Section 3, we can again
show that optimizing under the more restrictive notion of DSIC truthfulness is
without loss for our optimization objective. Furthermore, we investigate under
what structural conditions of our underlying feasibility space we can
“generically” guarantee that there exists an optimal auction that does not
need to allocate fractionally/randomly, i.e. it is integral; it turns out,
that _total unimodularity_ is such a sufficient condition (see Section 4.4 for
more details and definitions).

It is important to point out here that, in principle, one could derive the
main results of Section 3 for the single-item case by making use of the more
general KKT setting of Section 4. In other words, Theorem 1 can be viewed as a
special case of Theorem 2. Nevertheless, we deliberately choose in our paper
to first, independently develop the special, single-item theory of Section 3,
not as much as a warm-up for the conceptually more demanding and abstract
presentation of Section 4, but also for essential technical reasons: many
components of our proofs from Section 3 are needed in order to keep the
technical difficulty of Section 4 manageable, i.e., our paper is built in a
modular way so that we do not unnecessarily repeat technical parts from the
single-item to the general case, but at the same time those parts are key
components for the way our proofs are presented for the general case in
Section 4. Additionally, if one was to actually rederive our results and
presentation for the single-item case as a special-case instantiation of the
more general framework in Section 4, this would result in a very hard to
penetrate presentation, obscuring from the key insights and clarity provided
by the traditional LP tools used in Section 3.

Finally, in Section 5 we demonstrate the transparency and strength of our
framework, by applying it to a capacitated tree setting, inspired by real-life
gas network structures [Sch+17], where each bidder wants to send flow between
a fixed origin-destination pair. In addition to the KKT formulation of the
problem, we “unravel” its optimal solution (as dictated by Point 3 of Theorem
2) to derive a purely combinatorial, algorithmic description of the allocation
and payment rules (see Section 5.1), that reveals an interesting economics
interpretation of _edge pricing_.

##  2 Preliminaries

###  2.1 Model and Notation

We use $\mathbb{R}$, $\mathbb{R}_{+}$, and $\mathbb{N}$, for the set of reals,
non-negative reals, and non-negative integers, respectively. For any positive
integer $k$ we denote $[k]\coloneqq\\{1,2,\dots,k\\}$.

#### Single-parameter settings

In a (Bayesian) single-parameter auction design setting there are $n\geq 1$
bidders, and each bidder $i\in[n]$ has a value $v_{i}\in\mathbb{R}_{+}$ for
being allocated a single “unit” of some “service”. Each value $v_{i}$ is drawn
independently from a distribution (with cdf) $F_{i}$ with support
$V_{i}\subseteq\mathbb{R}_{+}$, called the _prior_ of bidder $i$. We will use
$f_{i}$ to denote the probability mass function (pmf) of $F_{i}$. These
distributions are public knowledge, however the realization $v_{i}$ is private
information of bidder $i$ only. In this paper we only study _discrete_ auction
settings, where the prior supports $V_{i}$ are _finite_. For notational
convenience we denote the corresponding product distribution of the _value
profiles_
$\bm{v}=(v_{1},v_{2},\dots,v_{n})\in\bm{V}\coloneqq\times_{i=1}^{n}V_{i}$ by
$\bm{F}\coloneqq\times_{i=1}^{n}F_{i}$, and we also use
$\bm{V}_{-i}\coloneqq\times_{j\in[n]\setminus{i}}V_{j}$ and
$\bm{F}_{-i}\coloneqq\times_{j\in[n]\setminus{i}}F_{j}$.

There is also a set of feasible outcomes
$\mathcal{A}\subseteq\mathbb{R}_{+}^{n}$, each outcome
$\bm{a}=(a_{1},a_{2},\dots,a_{n})\in\mathcal{A}$ corresponding to bidder $i$
being allocated a “quantity” $a_{i}$. Throughout this paper we assume that
$\mathcal{A}$ is _convex_. A canonical example is the classical single-item
auction setting (which we study in Section 3), where $a_{i}$ can be
interpreted as the probability of a lottery assigning the item to bidder $i$,
in which case the feasibility set $\mathcal{A}$ is the $n$-dimensional simplex
$\mathcal{S}_{n}\coloneqq\left\\{\bm{a}\in\mathbb{R}^{n}_{+}\;\left|\;\sum_{i=1}^{n}a_{i}\leq
1\right.\right\\}$.

#### Auctions

An auction $M=(\bm{a},\bm{p})$ consists of an allocation rule
$\bm{a}:\bm{V}\longrightarrow\mathcal{A}$ and a payment rule
$\bm{p}:\bm{V}\longrightarrow\mathbb{R}^{n}$ that, given as input a vector of
bids $\bm{b}\in\bm{V}$, dictates that each bidder $i$ should get allocated
quantity $a_{i}(\bm{b})$ and submit a payment of $p_{i}(\bm{b})$ to the
auctioneer.

Given such an auction $M$, the (ex-post) utility of a bidder $i$, when their
true value is $v_{i}\in V_{i}$ and bidders submit bids $\bm{b}\in\bm{V}$, is

$u_{i}^{M}(\bm{b};v_{i})=u_{i}(\bm{b};v_{i})\coloneqq a_{i}(\bm{b})\cdot
v_{i}-p_{i}(\bm{b}).$ (1)

Using the distributional priors $F_{i}$ to capture the uncertainty about other
bidders’ behaviour, we can also define the _interim_ utility of a bidder, when
having true value $v_{i}\in V_{i}$ and bidding $b_{i}\in V_{i}$ as

$U_{i}(b_{i};v_{i})\coloneqq\operatorname*{\mathbb{E}}_{\bm{b}_{-i}\sim\bm{F}_{-i}}\nolimits\left[u_{i}(b_{i},\bm{b}_{-i};v_{i})\right]=A_{i}(b_{i})\cdot
v_{i}-P_{i}(b_{i}),$

where

$A_{i}(b_{i})\coloneqq\operatorname*{\mathbb{E}}_{\bm{b}_{-i}\sim\bm{F}_{-i}}\nolimits\left[a_{i}(b,\bm{b}_{-i})\right]\qquad\text{and}\qquad
P_{i}(b_{i})\coloneqq\operatorname*{\mathbb{E}}_{\bm{b}_{-i}\sim\bm{F}_{-i}}\nolimits\left[p_{i}(b,\bm{b}_{-i})\right]$

are the interim versions of the allocation and payment rules of the mechanism,
respectively.

An auction whose allocations lie in the $n$-simplex, i.e.
$\bm{a}(\bm{v})\in\mathcal{S}_{n}$ for all $\bm{v}\in\bm{V}$, will be called a
_lottery_ , since its fractional allocations $a_{i}\in[0,1]$ can be
equivalently interpreted as the probability of assigning $1$ unit of service
to bidder $i$, given the linearity of the utilities (1). In particular,
lotteries with only integral $0$-$1$ allocations, i.e.
$\bm{a}\in\mathcal{S}_{n}\cap\\{0,1\\}^{n}$ will be called _deterministic
auctions_. More generally, any auction with allocation rule
$\bm{a}\in\mathbb{N}^{n}$ will be called _integral_.

###  2.2 Incentive Compatibility

From the perspective of each bidder $i$, the goal is to bid so that they can
maximize their own utility. In particular, this means that bidders can lie and
misreport $b_{i}\neq v_{i}$. Therefore, one of the goals of mechanism design
is to construct auctions that avoid this pitfall, and which _provably_
guarantee that truthful participation is to each bidder’s best interest. From
a game-theoretic perspective this can be formalized by demanding that truthful
bidding $b_{i}=v_{i}$ is an equilibrium of the induced Bayesian game.

This gives rise to the following constraints, known as _dominant-strategy
incentive compatibility (DSIC)_ : for any bidder $i$, any true value $v_{i}\in
V_{i}$, and any bidding profile $\bm{b}\in\bm{V}$, it holds that

$u_{i}(v_{i},\bm{b}_{-i};v_{i})\geq u_{i}(b_{i},\bm{b}_{-i};v_{i}),$ (DSIC)

and its more relaxed version of _Bayesian incentive compatibility (BIC)_ ,
involving the interim utilities:

$U_{i}(v_{i};v_{i})\geq U_{i}(b_{i};v_{i}),$ (BIC)

for any bidder $i$, true value $v_{i}\in V_{i}$ and bid $b_{i}\in V_{i}$.

#### Individual rationality

Another desired property of our mechanisms is that no bidder should harm
themselves by truthfully participating in our auction, known as _individual
rationality (IR)_. Similarly to the truthfulness conditions (DSIC) and (BIC),
this can be formalized both in an ex-post and interim way:
$u_{i}(v_{i},\bm{b}_{-i})\geq 0$ and $U_{i}(v_{i};v_{i})\geq 0$, respectively,
for all bidders $i$, true values $v_{i}\in V_{i}$ and other bidders’ bid
profile $\bm{b}_{-i}\in\bm{V}_{-i}$, respectively.

One elegant way to merge the (IR) constraints into truthfulness, is to extend
the bidding space of bidder $i$ in (DSIC) and (BIC) from $V_{i}$ to
$\bar{V}_{i}\coloneqq V_{i}\cup\\{\varnothing\\}$ and define

$a_{i}(\varnothing,\bm{b}_{-i})=p_{i}(\varnothing,\bm{b}_{-i})=0$ (2)

for all bidders $i$ and other bidders’ bids $\bm{b}_{-i}\in\bm{V}_{-i}$. Then,
bidding $\varnothing$ can be interpreted as an option to “abstain” from the
auction for a utility of
$u_{i}(\varnothing,\bm{b}_{-i};v_{i})=U_{i}(\varnothing;v_{i})=0$. From now on
we will assume that our truthfulness conditions (DSIC) and (BIC) are indeed
extended in that way to $\bar{V_{i}}$, thus including the (IR) constraints. An
auction will be called DSIC (resp. BIC) if it satisfies those (extended)
(DSIC) (resp. (BIC)) constraints. Observe that, since $\eqref{eq:DSIC-
def}\subseteq\eqref{eq:BIC-def}$, any DSIC auction is also BIC.

#### Optimal auctions

The main focus of our paper is the design of _optimal auctions_ , for discrete
value domains. That is, maximize the seller’s _revenue_ within the space of
all feasible _truthful_ auctions. Formally, if for a given auction
$M=(\bm{a},\bm{p})$ we denote its expected revenue, with respect to the value
priors $\bm{F}$, by

$\mathsf{Rev}(M)\coloneqq\operatorname*{\mathbb{E}}_{\bm{v}\sim\bm{F}}\nolimits\left[\sum_{i=1}^{n}p_{i}(\bm{v})\right],$
(3)

then our optimization problem can be stated as
$\sup_{M:\mathcal{A}\land\eqref{eq:DSIC-def}}\mathsf{Rev}(M)$, or
$\sup_{M:\mathcal{A}\land\eqref{eq:BIC-def}}\mathsf{Rev}(M)$, depending on
whether we choose the notion dominant-strategy, or Bayesian truthfulness. An
optimal solution to the former problem will be called _optimal DSIC_ auction,
and to the latter, _optimal BIC_ auction. Following the standard convention in
the field (see, e.g., [Kri09] and [Mye81]), the term _optimal auction_ that
does not explicitly specify the underlying truthfulness notion, will refer to
the optimal BIC auction. Notice that, since $\eqref{eq:DSIC-
def}\subseteq\eqref{eq:BIC-def}$, for an optimal DSIC auction $M$ and an
optimal BIC auction $M^{\prime}$ it must be that
$\mathsf{Rev}(M)\leq\mathsf{Rev}(M^{\prime})$.

Nevertheless, as we demonstrate in Section 4, our general duality approach
provides for greater flexibility with respect to the optimization objective.
For example, this will allow us to instantiate our framework for a convex
combination or revenue and another important objective in auction theory, that
of _social welfare_ :

$\mathsf{SW}(M)\coloneqq\operatorname*{\mathbb{E}}_{\bm{v}\sim\bm{F}}\nolimits\left[\sum_{i=1}^{n}a_{i}(\bm{v})v_{i}\right].$
(4)

###  2.3 Locality of Truthfulness

It turns out our truthfulness constraints can be simplified, and expressed
through a set of constraints that are “local” in nature, in the sense that
they only involve deviations between adjacent values. To formalize this,
recall that our value spaces $V_{i}$ are finite, so we can define the notion
of _predecessor_ and _successor_ values for a given bidder $i$ and a value
$v_{i}\in V_{i}$:

$v_{i}^{+}\coloneqq\min\left\\{v\in
V_{i}\;\left|\;v>v_{i}\right.\right\\}\quad\text{and}\quad
v_{i}^{-}\coloneqq\max\left\\{v\in V_{i}\;\left|\;v<v_{i}\right.\right\\},$

if the above sets are non-empty, otherwise we define
$v_{i}^{+}\coloneqq\varnothing$ for $v_{i}=\max V_{i}$ and
$v_{i}^{-}\coloneqq\varnothing$ for $v_{i}=\min V_{i}$.

Now we can state the local characterization of truthfulness, first for (DSIC),
but a totally analogous lemma holds for (BIC) as well – see Appendix A. This
result can be essentially derived by the work of [MV04, Theorems 1 and 2]; for
reasons of clarity and compatibility with our model and notation, we also
present a proof in Appendix A.

######  Lemma 1 ([MV04]).

For any discrete, single-dimensional auction $(\bm{a},\bm{p})$, the (DSIC)
condition is _equivalent_ to the following set of constraints:

$\displaystyle u_{i}(\bm{v};v_{i})$ $\displaystyle\geq
u_{i}(v_{i}^{-},\bm{v}_{-i};v_{i})$ (5) $\displaystyle u_{i}(\bm{v};v_{i})$
$\displaystyle\geq u_{i}(v_{i}^{+},\bm{v}_{-i};v_{i}),$ (6)

for all bidders $i\in[n]$ and any value profile $\bm{v}\in\bm{V}$.
Furthermore, conditions (5) and (6) imply

$a_{i}(\bm{v})\geq a_{i}(v_{i}^{-},\bm{v}_{-i}),$ (7)

for all $i\in[n]$ and $\bm{v}\in\bm{V}$.

Conditions (5) and (6) are called _downwards_ and _upwards_ DSIC constraints,
respectively, and (7) are called _monotonicity_ constraints.

##  3 The Discrete Myerson Auction: an LP Duality Approach

In this section we begin our study of optimal single-parameter auctions, by
considering the canonical single-item setting of [Mye81], but under discrete
values. That is, the feasibility set for our allocations is the simplex
$\mathcal{S}_{n}$ (see Section 2.1), giving rise to the following _feasibility
constraints_ :

$\sum_{i=1}^{n}a_{i}(\bm{v})\leq 1,\qquad\text{for all}\;\;\bm{v}\in\bm{V}.$
(8)

Our results of this section are summarized in the following main theorem:

######  Theorem 1 (Optimal Discrete Single-Item Auction).

For any discrete, single-item auction setting, the following hold for revenue
maximization: 1. There always exists an optimal auction which is
deterministic. 2. _Any_ optimal DSIC auction is an optimal BIC auction. 3. The
following deterministic DSIC auction is optimal (even within the class of
randomized BIC auctions): • Allocate (fully) the item to the bidder with the
highest non-negative ironed virtual value (19), breaking ties
arbitrarily.222In order to maintain determinism, this can be any fixed
deterministic tie-breaking rule; e.g., allocating the bidder with the smallest
index $i$. Fractionally splitting the item among bidders that tie would still
ensure revenue optimality (and DSIC), but the mechanism would be randomized. •
Collect from the winning bidder a payment equal to their critical bid (14).

Point 3 of Theorem 1 is essentially a discrete analogue of Myerson’s optimal
auction for the continuous case. As we mentioned in our introduction (see
Sections 1.1 and 1.2), this result can be already derived by readily combining
prior work on discrete auctions (see, e.g., [CDW12, Elk07]); our contribution
here is not the result itself, but the proof technique, which makes use of
classical LP duality theory. This allows us to make use of powerful and
transparent results from polyhedral combinatorics, to structurally
characterize optimal auctions. In particular, we establish the optimality of
DISC mechanisms, in a very general sense (see Point 2), which to the best of
our knowledge was not known before. This is also enabled by our discrete
optimization view of the problem, through the use of polyhedral properties
(see Section 3.3). Finally, observe that Point 1 can be derived directly as a
corollary of Point 3; nevertheless, we choose to state it independently, in
order to reflect the logical progression of our derivation in this paper,
which actually allows us to establish Point 1 more generally, as a result of
the polyhedral structure of our problem (see Section 3.2), _before_ we
determine the actual optimal solution in Point 3.

We start our presentation by considering the revenue-maximization problem
under the more restricted DSIC truthfulness notion. We do this for reasons of
clarity of exposition, and then in Section 3.3 we carefully discuss how our
formulations adapt for the more relaxed (BIC) constraints, and the relation
between the two notions with respect to optimality, completing the picture for
Theorem 1.

###  3.1 A Chain of Dual Linear Programs

In this section we develop the skeleton of our approach for proving Theorem 1.
It consists of a sequence of LPs, as summarized in Figure 1. We start by
formulating the single-item, revenue-maximization problem as an LP in (LP1).
Next, we dualize it in (DP1), and then restrict the program to derive (DP2)
that can only have a worse (i.e., higher) optimal objective. Then, we dualize
again, deriving a maximization program in (LP2). Finally, we prove (see Lemma
3) that our original maximization program (LP1) is a relaxation of (LP2), thus
establishing a collapse of the entire duality chain, and the equivalence of
all involved LPs. This closure of the chain is exactly from where virtual
values (13), virtual welfare maximization (LP2), optimality of determinism
(see Lemma 4), and the optimal payment rule (LP2) naturally emerge.

ptLP1DP1DP2LP2$\geq$=$\leq$= Figure 1: An overview of the linear programs used
in our derivation throughout Section 3 and the relations between their optimal
values.

Before we formally present and start working within the LPs, we need to fix
some notation.

#### LP notation

Since our value sets are finite, for each player $i$ we can enumerate their
support as $V_{i}=\\{v_{i,1},v_{i,2},\dots,v_{i,K_{i}}\\}$, for some positive
integer $K_{i}$. For notational convenience we denote
$\bm{K}\coloneqq[K_{1}]\times[K_{2}]\times\dots\times[K_{n}]$ and
$\bm{K}_{-i}\coloneqq[K_{1}]\times\dots\times[K_{i-1}]\times[K_{i-1}]\times\dots\times[K_{n}]$.
To keep our LP formulations below as clean as possible, we will feel free to
abuse notation and use the support indices $k\in[K_{i}]$ instead of the actual
values $v_{i,k}\in V_{i}$, as arguments for the allocations $a_{i}$, payments
$p_{i}$, and prior cdf’s $F_{i}$ and pmf’s $f_{i}$. That is, e.g., we will
denote $a_{i}(k,\bm{k}_{-i})$, $p_{i}(k,\bm{k}_{-i})$, $f_{i}(k)$, and
$F_{i}(k)$, instead of $a_{i}(v_{i},\bm{v}_{-i})$, $p_{i}(v_{i},\bm{v}_{-i})$,
$f_{i}(v_{i})$, and $F_{i}(v_{i})$, respectively, when the valuation profile
$\bm{v}$ is such that $v_{i}=v_{i,k_{i}}$ for $i\in[n]$. As all values are
independently drawn from distributions $F_{i}$, the probability of a bid
profile $\bm{v}\in\bm{V}$ being realized is given by the pmf of their product
distribution $\bm{F}$, denoted by
$f(\bm{k})=f(\bm{v})=\prod_{i\in[n]}f_{i}(v_{i,k})$. Analogously, we denote
$f(\bm{k}_{-i})=f(\bm{v}_{-i})=\prod_{j\in[n]\setminus\\{i\\}}f_{j}(v_{j,k_{j}})$.
Finally, given that we make heavy use of duality, we choose to label each
constraint of our LPs with the name of its corresponding dual variable, using
blue colour (see, e.g., (LP1)).

For our starting (LP1), we want to formulate an LP maximizing expected revenue
(3), under the single-item allocation constraints (8) of our current section,
and DSIC truthfulness, through its equivalent formulation via Lemma 1. Since
we want to optimize over the space of all feasible auctions, the real-valued
variables of our LP are the allocation and payment rules of the auction, over
all possible bidding profiles, namely
$\\{a_{i}(\bm{v}),p_{i}(\bm{v})\\}_{\bm{v}\in\bm{V}}$. Putting everything
together, we derive the following LP:

max
$\displaystyle\quad\sum_{\bm{v}\in\bm{V}}\sum_{i=1}^{n}p_{i}(\bm{v})f(\bm{v})$
(LP1) s.t. $\displaystyle v_{i,k}a_{i}(k,\bm{k}_{-i})-p_{i}(k,\bm{k}_{-i})\geq
v_{i,k}a_{i}(k-1,\bm{k}_{-i})-p_{i}(k-1,\bm{k}_{-i}),$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\lambda_{i}(k,k-1,\bm{k}_{-i})]}$
$\displaystyle\quad\text{for}\;i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i},$
$\displaystyle v_{i,k}a_{i}(k,\bm{k}_{-i})-p_{i}(k,\bm{k}_{-i})\geq
v_{i,k}a_{i}(k+1,\bm{k}_{-i})-p_{i}(k+1,\bm{k}_{-i}),$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\lambda_{i}(k,k+1,\bm{k}_{-i})]}$
$\displaystyle\quad\text{for}\;i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i},$
$\displaystyle a_{i}(k,\bm{k}_{-i})\geq a_{i}(k-1,\bm{k}_{-i}),$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\tau_{i}(k,k-1,\bm{k}_{-i})]}$
$\displaystyle\quad\text{for}\;i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i},$
$\displaystyle\sum_{i=1}^{n}a_{i}(\bm{v})\leq 1,$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\psi(\bm{v})]}$
$\displaystyle\quad\text{for}\;\bm{v}\in\bm{V}.$

Notice how our LP can readily incorporate the no-participation IR constraints
(2), by defining the fixing the under-/overflowing corner cases as constants

$a_{i}(0,\bm{k}_{-i})=p_{i}(0,\bm{k}_{-i})=a_{i}(K_{i}+1,\bm{k}_{-i})=p_{i}(K_{i}+1,\bm{k}_{-i})=0$
(9)

for all bidders $i$, on any bidding profile $\bm{k}_{-i}$ of the other
bidders.

According to this we formulate the dual LP (DP1). Similar to the borderline
cases (9) in the primal LP some restrictions on the dual variables are
necessary to obtain a correct dual problem formulation. There we have

$\lambda_{i}(K,K+1,\bm{k}_{-i})=\lambda_{i}(K+1,K,\bm{k}_{-i})=\lambda_{i}(0,1,\bm{k}_{-i})=\tau_{i}(K+1,K,\bm{k}_{-i})=0$
(10)

for all bidders $i$, on any bidding profile $\bm{k}_{-i}$ of the other
bidders, for constraints that do not exist in (LP1). To ensure dual
feasibility, all dual variables corresponding to inequality constraints in the
primal have to be non-negative, thus all $\lambda,\psi,\tau\geq 0$. It is
worth pointing out that $\lambda_{i}(1,0,\bm{k}_{-i})$ and
$\tau_{i}(1,0,\bm{k}_{-i})$ are explicitly not fixed to zero as the
corresponding constraints, the local downward DSIC constraint that ensures IR,
$v_{i,1}a_{i}(1,\bm{k}_{-i})-p_{i}(1,\bm{k}_{-i})\geq 0$, as well as the
monotonicity constraint that ensures non-negativity of the allocation
variables, $a_{i}(1,\bm{k}_{-i})\geq 0$, are crucial for the problem. By that
we write the dual LP as

$\displaystyle\min\quad$ $\displaystyle\sum_{\bm{v}\in\bm{V}}\psi(\bm{v})$
(DP1) s.t. $\displaystyle\psi(k,\bm{k}_{-i})\geq
v_{i,k}\lambda_{i}(k,k-1,\bm{k}_{-i})+v_{i,k}\lambda_{i}(k,k+1,\bm{k}_{-i})$
$\displaystyle\qquad-
v_{i,k+1}\lambda_{i}(k+1,k,\bm{k}_{-i})-v_{i,k-1}\lambda_{i}(k-1,k,\bm{k}_{-i})$
$\displaystyle\qquad+\tau_{i}(k,k-1,\bm{k}_{-i})-\tau_{i}(k+1,k,\bm{k}_{-i}),$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[a_{i}(k,\bm{k}_{-i})]}$
$\displaystyle\quad\text{for
\;}i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i},$
$\displaystyle\lambda_{i}(k,k-1,\bm{k}_{-i})+\lambda_{i}(k,k+1,\bm{k}_{-i})$
$\displaystyle\qquad-\lambda_{i}(k+1,k,\bm{k}_{-i})-\lambda_{i}(k-1,k,\bm{k}_{-i})=f(\bm{v}),$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[p_{i}(k,\bm{k}_{-i})]}$
$\displaystyle\quad\text{for
\;}i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i}.$

As $p$ are free variables in the primal problem, the corresponding dual
constraints are equations, while as $a$ are required to be non-negative, the
corresponding dual constraints are inequalities. In the same spirit as
denoting the local DSIC constraints, that consider a deviation to the lower
value, as _downwards constraint_ (5), we call the corresponding dual variables
$\lambda_{i}(k,k-1,\bm{k}_{-i})$ where the index in the first argument is
greater than in the second _downward $\lambda$ variables_. The dual variables
$\lambda_{i}(k,k+1,\bm{k}_{-i})$ corresponding to the upwards DSIC constraints
(6) are the _upward $\lambda$ variables_. Putting together the dual borderline
variables (10) and the set of equations in (DP1) we can state the following
lemma, whose proof can be found in Appendix B.

######  Lemma 2.

In any feasible solution of (DP1) all downward $\lambda$ variables are
strictly positive, i.e.,

$\lambda_{i}(k,k-1,\bm{k}_{-i})>0,$

for all $i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i}.$

This motivates us to reformulate the dual program in a certain way. Recall,
that any dual solution has to satisfy the set of equations

$\lambda_{i}(k,k-1,\bm{k}_{-i})+\lambda_{i}(k,k+1,\bm{k}_{-i})=f(\bm{v})+\lambda_{i}(k+1,k,\bm{k}_{-i})+\lambda_{i}(k-1,k,\bm{k}_{-i}).$
(11)

Using this we reformulate the dual inequality constraints

$\displaystyle\psi(\bm{v})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:dual_equations}}}{{\geq}}v_{i,k}f(\bm{v})-(v_{i,k+1}-v_{i,k})\lambda_{i}(k+1,k,\bm{k}_{-i})+(v_{i,k}-v_{i,k-1})\lambda_{i}(k-1,k,\bm{k}_{-i})$
$\displaystyle\qquad+\tau_{i}(k,k-1,\bm{k}_{-i})-\tau_{i}(k+1,k,\bm{k}_{-i})$

Note, that by the use of (11), i.e. exclusively equations, this is only a
reformulation and does not affect the set of feasible dual solutions of (DP1).
Now we unconventionally fix specific values of the $\lambda$ variables. As the
dual’s objective aims to minimize the sum of the $\psi$ variables, according
to the reformulated inequality constraints it seems convenient to choose all
upward $\lambda$ as small and all downward $\lambda$ as large as possible. To
do so we set $\lambda_{i}(k,k+1,\bm{k}_{-i})=0$, for all $k\in[K_{i}],i\in[n]$
and $\bm{k}_{-i}\in\bm{K}_{-i}$. Fixing variables, essentially adding equality
constraints, can only increase the optimal value of (DP1) in terms of
minimization. As a next critical step we introduce _free_ variables $\rho$ and
substitute the expression

$\rho_{i}(k,\bm{k}_{-i})\coloneqq\lambda_{i}(k,k-1,\bm{k}_{-i})-\lambda_{i}(k+1,k,\bm{k}_{-i})$

for all bidders $i$ with value index $k\in[K_{i}]$, and any bidding profile
$\bm{k}_{-i}$ of the other bidders. These variables are all bound to fixed
values and by dropping the $\lambda$ variables from the problem formulation we
do not lose any information about feasible dual solutions as by
${\lambda_{i}(K+1,K,\bm{k}_{-i})=0}$ we keep track of all fixed values. The
reformulated dual LP then is

$\displaystyle\min\quad$ $\displaystyle\sum_{\bm{v}\in\bm{V}}\psi(\bm{v})$
(DP2) s.t. $\displaystyle\psi(k,\bm{k}_{-i})\geq
v_{i,k}\rho_{i}(k,\bm{k}_{-i})-(v_{i,k+1}-v_{i,k})\sum_{l=k+1}^{K_{i}}\rho_{i}(l,\bm{k}_{-i})$
$\displaystyle\qquad+\tau_{i}(k,k-1,\bm{k}_{-i})-\tau_{i}(k+1,k,\bm{k}_{-i}),$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[a_{i}(k,\bm{k}_{-i})]}$
$\displaystyle\quad\text{for
\;}i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i},$
$\displaystyle\rho_{i}(k,\bm{k}_{-i})=f(\bm{v}),$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[p_{i}(k,\bm{k}_{-i})]}$
$\displaystyle\quad\text{for
\;}i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i}.$

The inequality constraints now can also be written with all explicit values of
$\rho$ inserted. By that we obtain for a fixed bidder $i$ and bids
$\bm{v}_{-i}$

$\psi(k,\bm{k}_{-i})\geq
f(\bm{v})\left[v_{i,k}-(v_{i,k+1}-v_{i,k})\frac{1-F_{i}(k)}{f_{i}(k)}+\frac{\tau_{i}(k,k-1,\bm{k}_{-i})}{f(\bm{v})}-\frac{\tau_{i}(k+1,k,\bm{k}_{-i})}{f(\bm{v})}\right].$
(12)

This gives rise to the well known definition of a sequence of values for
player $i$ which is independent of all other bidders’ values $\bm{v}_{-i}$.

######  Definition 1 (Virtual Values).

The _virtual values_ of bidder $i\in[n]$ are defined as

$\varphi_{i}(k)=\varphi_{i}(v_{i,k})\coloneqq
v_{i,k}-(v_{i,k+1}-v_{i,k})\frac{1-F_{i}(v_{i,k})}{f_{i}(v_{i,k})}\qquad\text{for}\;\;k\in[K_{i}].$
(13)

We return to the primal setting of allocation and payment variables by now
taking _the dual of the dual_. To get the full transparency of the gained
insights within the reformulation to (DP2) we do two things at the same time:
We insert the true values of all $\rho$ in the inequalities and obtain the
virtual values as the coefficients of the allocation variables in the new
primal objective. At the same time we stick with $\rho$ as free variables in
the dual inequalities and obtain the payment formula in (LP2) as the
coefficients of $\rho$ in the dual become the coefficients of the allocation
variables in the primal payment formula. Note, that equivalently we could
still maximize the expected payments in the new primal LP without using the
explicit values for $\rho$.

$\displaystyle\max\quad$
$\displaystyle\sum_{\bm{v}\in\bm{V}}\sum_{i=1}^{n}a_{i}(\bm{v})\varphi_{i}(k)f(\bm{v})$
(LP2) s.t. $\displaystyle
p_{i}(k,\bm{k}_{-i})=v_{i,k}a_{i}(k,\bm{k}_{-i})-\sum_{l=1}^{k-1}(v_{i,l+1}-v_{i,l})a_{i}(l,\bm{k}_{-i}),$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\rho_{i}(k,\bm{k}_{-i})]}$
$\displaystyle\quad\text{for}\;i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i},$
$\displaystyle a_{i}(k,\bm{k}_{-i})\geq a_{i}(k-1,\bm{k}_{-i}),$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\tau_{i}(k,k-1,\bm{k}_{-i})]}$
$\displaystyle\quad\text{for}\;i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i},$
$\displaystyle\sum_{i=1}^{n}a_{i}(\bm{v})\leq 1,$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\psi(\bm{v})]}$
$\displaystyle\quad\text{for}\;\bm{v}\in\bm{V}.$

As our interest lies in optimal auctions, we _close the chain_ of LPs using
Lemma 2 and strong LP duality to verify that the sets of optimal solutions of
(LP1) and of (LP2) are equivalent.

######  Lemma 3.

Any optimal solution of (LP2) represents an optimal DSIC auction, i.e. an
optimal solution of (LP1) and vice versa.

###### Proof.

We first show that any solution of (LP2) is also feasible for (LP1). This
closes the chain in terms of objective values. Secondly, we use complementary
slackness to prove that any optimal solution of (LP1) has to be feasible for
(LP2). By that both linear programs have the exact same set of optimal
solutions.

Let $(\bm{a},\bm{p})$ be an optimal solution of (LP2). We insert the payment
rule into the local DSIC constraints of (LP1) to verify that they are
satisfied. For that fix player $i$, player $i$’s value $v_{i,k}$, and all
other players’ values $\bm{v}_{-i}$ and consider the downward constraint

$\displaystyle v_{i,k}a_{i}(k,\bm{k}_{-i})-p_{i}(k,\bm{k}_{-i})$
$\displaystyle\geq v_{i,k}a_{i}(k-1,\bm{k}_{-i})-p_{i}(k-1,\bm{k}_{-i})$
$\displaystyle\sum_{l=1}^{k-1}(v_{i,l+1}-v_{i,l})a_{i}(l,\bm{k}_{-i})$
$\displaystyle\geq
v_{i,k}a_{i}(k-1,\bm{k}_{-i})-v_{i,k-1}a_{i}(k-1,\bm{k}_{-i})+\sum_{l=1}^{k-2}(v_{i,l+1}-v_{i,l})a_{i}(l,\bm{k}_{-i})$
$\displaystyle(v_{i,k}-v_{i,k-1})a_{i}(k-1,\bm{k}_{-i})$
$\displaystyle\geq(v_{i,k}-v_{i,k-1})a_{i}(k-1,\bm{k}_{-i}).$

The equality in the last line is no coincidence, and we have a closer look at
it in the last part of the proof.

For the upward constraint we have

$\displaystyle v_{i,k}a_{i}(k,\bm{k}_{-i})-p_{i}(k,\bm{k}_{-i})$
$\displaystyle\geq v_{i,k}a_{i}(k+1,\bm{k}_{-i})-p_{i}(k+1,\bm{k}_{-i})$
$\displaystyle\sum_{l=1}^{k-1}(v_{i,l+1}-v_{i,l})a_{i}(l,\bm{k}_{-i})$
$\displaystyle\geq
v_{i,k}a_{i}(k+1,\bm{k}_{-i})-v_{i,k+1}a_{i}(k+1,\bm{k}_{-i})+\sum_{l=1}^{k}(v_{i,l+1}-v_{i,l})a_{i}(l,\bm{k}_{-i})$
$\displaystyle(v_{i,k+1}-v_{i,k})a_{i}(k+1,\bm{k}_{-i})$
$\displaystyle\geq(v_{i,k+1}-v_{i,k})a_{i}(k,\bm{k}_{-i})$

which always holds by monotonicity.

Finally, for the other direction let $(\bm{a},\bm{p})$ be an optimal solution
of (LP1). Any optimal solution of this linear program by strong duality has to
satisfy complementary slackness: If any dual variable is strictly positive,
the corresponding primal constraint has to bind. By Lemma 2 we know that all
feasible, thus, all optimal downward $\lambda$ variables, are positive. This
implies that in any optimal solution of (LP1) all local downward constraints
have to bind. The payment rule of (LP2) is only the result of the successive
application of the binding constraints. The upward constraints are then also
satisfied as this follows directly from the first part of the proof. ∎

The immediate result is that the problem of finding an optimal DSIC auction
reduces to finding an optimal solution of (LP2), i.e. a feasible, virtual
welfare maximizing, monotone allocation rule $\bm{a}$. The optimal payments
are computed afterwards as a linear function of the allocations according to
the payment rule

$p_{i}(k,\bm{k}_{-i})=v_{i,k}a_{i}(k,\bm{k}_{-i})-\sum_{l=1}^{k-1}(v_{i,l+1}-v_{i,l})a_{i}(l,\bm{k}_{-i}).$
(14)

If for player $i$ and fixed $\bm{v}_{-i}$ the allocation variables
$a_{i}(k,\bm{k}_{-i})\in\\{0,1\\}$ for $k\in[K_{i}]$, the payment rule (14)
simplifies: If player $i$ wins, the payment $p_{i}(k,\bm{k}_{-i})$ is the
_critical bid_ , i.e. the minimum value such that player $i$ still wins, and
zero if player $i$ does not win. Therefore, we want to examine the potential
of the allocation variables being binary in an optimal solution in the
following.

###  3.2 Deterministic vs Randomized Auctions

In this section we essentially establish the foundation for Point 1 of Theorem
1. We are using the property of _totally unimodularity_ [HK10] of the
constraint matrix of (LP2). This is enough to show that the optimal
allocations of (LP1) and (LP2) are the convex hull of optimal binary
solutions.

######  Lemma 4 (Optimality of determinism).

The vertices of the polyhedron of feasible allocations for (LP2) are integral,
hence, binary.

###### Proof.

This proof is based on the matrix property of total unimodularity (TU). More
specific, we will make use of the following well-known properties (see, e.g.,
[Sch03, Ch. 13]): for any matrix $A\in\\{-1,0,1\\}^{M\times N}$, (i) $A$ is TU
if and only if $(A\,\bm{1})$ is TU, where $\bm{1}$ is an $M\times M$ unit
matrix, and (ii) $A$ is TU if and only if $A^{\top}$ is TU, where $A^{\top}$
denotes the transpose of matrix $A$. Furthermore, (iii) the adjacency matrix
of a directed graph is TU.

To argue this coherently we have to put some effort in understanding the
structure of the linear constraints that can be expressed as matrix vector
inequalities. The set of feasible allocations for (LP2) are all non-negative
$\bm{a}$ satisfying

$\displaystyle a_{i}(k,\bm{k}_{-i})\geq a_{i}(k-1,\bm{k}_{-i})$
$\displaystyle\text{for}\;i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i},$ (15)
$\displaystyle\sum_{i=1}^{n}a_{i}(\bm{v})\leq 1$
$\displaystyle\text{for}\;\bm{v}\in\bm{V},$ (16)

Therefore, we consider the allocation the polyhedron
$\\{\bm{a}\,|\,a_{i}(k,\bm{k}_{-i})\geq
a_{i}(k-1,\bm{k}_{-i})\,,i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i},\,\text{and},\,\sum_{i=1}^{n}a_{i}(\bm{v})\leq
1\,,\bm{v}\in\bm{V}\\}$ as $\\{\bm{a}\,|\,A\bm{a}\leq b\\}$. We see the
allocations $\bm{a}$ as a vector of dimension $\mathcal{N}\coloneqq
n\cdot|\bm{V}|=n\cdot|V_{1}|\cdots|V_{n}|=n\cdot K_{1}\cdots K_{n}$. We order
them such that the first $|\bm{V}|$ entries are all allocations of player $1$
varying over the bid profiles $\bm{v}$, then the second player and so on. The
order of the $\bm{v}$ is consistent over all players. By that we can write the
constraint matrix $A$ and the right-hand side $b$ as

$A=\left(\begin{array}[]{ccc|c|ccc}M_{1}(\bm{v}_{-1})&&0&\\\
&\ddots&&\bm{0}&&\bm{0}\\\ 0&&M_{1}(\bm{v}^{\prime}_{-1})&\\\
\hline\cr&\bm{0}&&\ddots&&\bm{0}\\\ \hline\cr&&&&M_{n}(\bm{v}_{-n})&&0\\\
&\bm{0}&&\bm{0}&&\ddots&\\\ &&&&0&&M_{n}(\bm{v}^{\prime}_{-n})\\\
\hline\cr-1&&0&\\\ &\ddots&&\bm{0}&&\bm{0}\\\ 0&&-1&\\\
\hline\cr&\bm{0}&&\ddots&&\bm{0}\\\ \hline\cr&&&&-1&&0\\\
&\bm{0}&&\bm{0}&&\ddots&\\\ &&&&0&&-1\\\ \hline\cr 1&&0&&1&&0\\\
&\ddots&&\cdots&&\ddots\\\ 0&&1&&0&&1\end{array}\right),\quad
b=\begin{pmatrix}0\\\ \vdots\\\ \\\ \vdots\\\ \\\ \vdots\\\ \vspace{.05cm}0\\\
0\\\ \vdots\\\ \\\ \vdots\\\ \\\ \vdots\\\ \vspace{.05cm}0\\\ 1\\\ \vdots\\\
1\end{pmatrix}$ (17)

Here, $M_{i}(\bm{v}_{-i})$ is a $|V_{i}|\times|V_{i}|$ matrix that contains
the coefficients of the monotonicity constraints (15) of player $i$ fixing all
other players’ values to $\bm{v}_{-i}$. We do not keep explicit track of the
order within the monotonicity block matrices but note that each block is the
transposed adjacency matrix of a directed graph. By that the monotonicity part
is TU. The monotonicity constraints $a_{i}(1,\bm{k}_{-i})\geq
a_{i}(0,\bm{k}_{-i})=0$ are not considered in the monotonicity but shifted to
general non-negativity constraints in the following part of $A$.

The next part, containing the $-1$ entries, is an
$\mathcal{N}\times\mathcal{N}$ negative unity matrix to ensure the non-
negativity of all allocation variables. The side by side unity matrices in the
last row of blocks represent the feasibility constraints (16) and are also
clearly TU.

It remains to show that any sub-matrix of $A$ consisting of a mixture of the
different parts of monotonicity, non-negativity and the side by side unit
matrices is TU. This follows directly by the dimension of the non-negativity
part. There is no sub-matrix that contains rows from the monotonicity as well
as from the side by side unity matrix part. Knowing that $A$ is totally
unimodular and $b$ having only integer entries, the proof is concluded. ∎

Thus, determinism of optimal DSIC auctions is without loss. Also, since the
set of optimal solutions is convex, any fractional optimal solution is only a
convex combination of multiple integer solutions and for given
$\bm{v}\in\bm{V}$ represents a probability distribution.

###  3.3 Dominant-strategy vs Bayesian Truthfulness

The optimal auction problem typically is considered in a setting where
truthfulness constraints are a relaxed version of (DSIC) and a bidder’s
truthfulness only has to hold in expectation over all other bidders’
distributions, i.e., in the (BIC) sense (see Section 2.2). In this section we
essentially perform the same steps as in Section 3.1 where we considered DSIC
truthfulness, but unlike before under the constraints that an auction has to
be BIC. Now, by the expectations in the Bayesian setting we have a drastically
reduced number of constraints. Due to the feasibility constraints (8) that do
not change between the two settings, we still consider the same number of
primal variables. Maintaining the amount of dual constraints ultimately yields
the same payment formula as in (LP2) for any optimal BIC auction.

The LP to find the optimal auction under Bayesian truthfulness is (BLP1).
Lemma 1 allows us to restrict ourselves to local truthfulness without loss as
well. Also note, that we fix the same borderline variables to the same values
as in the DSIC setting, see (9).

$\displaystyle\max\quad$
$\displaystyle\sum_{\bm{v}\in\bm{V}}\sum_{i=1}^{n}p_{i}(\bm{v})f(\bm{v})$
(BLP1) s.t.
$\displaystyle\sum_{\bm{v}_{-i}}\bigl{[}v_{i,k}a_{i}(k,\bm{k}_{-i})-p_{i}(k,\bm{k}_{-i})-v_{i,k}a_{i}(k-1,\bm{k}_{-i})+p_{i}(k-1,\bm{k}_{-i})\bigr{]}f_{-i}(\bm{v}_{-i})\geq
0,$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\lambda_{i}(k,k-1)]}$
$\displaystyle\quad\text{for}\;i\in[n],k\in[K_{i}],$
$\displaystyle\sum_{\bm{v}_{-i}}\bigl{[}v_{i,k}a_{i}(k,\bm{k}_{-i})-p_{i}(k,\bm{k}_{-i})-v_{i,k}a_{i}(k+1,\bm{k}_{-i})+p_{i}(k+1,\bm{k}_{-i})\bigr{]}f_{-i}(\bm{v}_{-i})\geq
0,$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\lambda_{i}(k,k+1)]}$
$\displaystyle\quad\text{for}\;i\in[n],k\in[K_{i}],$
$\displaystyle\sum_{\bm{v}_{-i}}\bigl{[}a_{i}(k,\bm{k}_{-i})-a_{i}(k-1,\bm{k}_{-i})\bigr{]}f_{-i}(\bm{v}_{-i})\geq
0,$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\tau_{i}(k,k-1)]}$
$\displaystyle\quad\text{for}\;i\in[n],k\in[K_{i}],$
$\displaystyle\sum_{i=1}^{n}a_{i}(\bm{v})\leq 1,$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\psi(\bm{v})]}$
$\displaystyle\quad\text{for}\;\bm{v}\in\bm{V}.$

The dual LP (BDP1) now has a reduced number of variables but the same number
of constraints as (DP1).

$\displaystyle\min\quad$ $\displaystyle\sum_{\bm{v}\in\bm{V}}\psi(\bm{v})$
(BDP1) s.t. $\displaystyle\psi(\bm{v})\geq
f(\bm{v}_{-i})\bigl{[}v_{i,k}\lambda_{i}(k,k-1)+v_{i,k}\lambda_{i}(k,k+1)$
$\displaystyle\qquad-v_{i,k+1}\lambda_{i}(k+1,k)-v_{i,k-1}\lambda_{i}(k-1,k)$
$\displaystyle\qquad+\tau_{i}(k,k-1)-\tau_{i}(k+1,k)\bigr{]},$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[a_{i}(k,\bm{k}_{-i})]}$
$\displaystyle\quad\text{for}\;i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i},$
$\displaystyle\lambda_{i}(k,k-1)+\lambda_{i}(k,k+1)$
$\displaystyle\qquad-\lambda_{i}(k+1,k)-\lambda_{i}(k-1,k)=f_{i}(v_{i,k}),$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[p_{i}(k,\bm{k}_{-i})]}$
$\displaystyle\quad\text{for}\;i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i}.$

By the same argument as in the DSIC setting, Lemma 2 applies as well and all
feasible downward $\lambda$ are strictly positive. Again we fix all upward
$\lambda$ to zero and after the similar substitution by the free variable
$\rho$, we obtain the same results for the dual constraints, namely,

$\displaystyle\psi(\bm{v})\geq
f(\bm{v}_{-i})\Bigg{[}v_{i,k}\rho_{i}(k,\bm{k}_{-i})-(v_{i,k+1}-v_{i,k})\sum_{l=k+1}^{K_{i}}\rho_{i}(l,\bm{k}_{-i})+\tau_{i}(k,k-1)-\tau_{i}(k+1,k)\Bigg{]},$
$\displaystyle\rho_{i}(k,\bm{k}_{-i})\coloneqq\lambda_{i}(k,k-1)-\lambda_{i}(k+1,k)=f_{i}(k).$

Inserting the fixed values of $\rho$ yields

$\psi(\bm{v})\geq
f(\bm{v})\Bigg{[}\varphi_{i}(k)+\frac{\tau_{i}(k,k-1)}{f_{i}(k)}-\frac{\tau_{i}(k+1,k)}{f_{i}(k)}\Bigg{]}.$
(18)

Perhaps surprisingly, although we consider BIC truthfulness, this yields the
exact same virtual values as in the DSIC setting, but due to the fewer
monotonicity constraints there is also a reduced number of $\tau$ variables in
the dual. We dualize once more to return to the primal setting again and
essentially obtain a discrete version of Myerson’s famous Lemma [Mye81, Lem.
3] in LP form:

$\displaystyle\max\quad$
$\displaystyle\sum_{\bm{v}\in\bm{V}}\sum_{i=1}^{n}a_{i}(\bm{v})\varphi_{i}(k)f(\bm{v})$
(BLP2) s.t. $\displaystyle
p_{i}(k,\bm{k}_{-i})=v_{i,k}a_{i}(k,\bm{k}_{-i})-\sum_{l=1}^{k-1}(v_{i,l+1}-v_{i,l})a_{i}(l,\bm{k}_{-i}),$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\rho_{i}(k,\bm{k}_{-i})]}$
$\displaystyle\;\text{for}\;i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i},$
$\displaystyle\sum_{\bm{v}_{-i}}\bigl{[}a_{i}(k,\bm{k}_{-i})-a_{i}(k-1,\bm{k}_{-i})\bigr{]}f_{-i}(\bm{v}_{-i})\geq
0,$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\tau_{i}(k,k-1)]}$
$\displaystyle\;\text{for}\;i\in[n],k\in[K_{i}],\bm{k}_{-i}\in\bm{K}_{-i},$
$\displaystyle\sum_{i=1}^{n}a_{i}(\bm{v})\leq 1,$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\psi(\bm{v})]}$
$\displaystyle\;\text{for}\;\bm{v}\in\bm{V}.$

Clearly, any feasible solution of (BLP2) is feasible for (BLP1) and as fixing
the upward $\lambda$ variables in the dual to zero can only increase the
optimal objective value, optimality transfers from (BLP2) to (BLP1) as well.
Furthermore, as BIC truthfulness is a relaxation of DSIC, any feasible
solution of (LP2) is feasible for (BLP2). Whether optimality transfers as well
is not obvious but can be verified if the pair of optimal primal and dual
solutions of (LP2) and (DP2) is feasible for (BLP2) and (BDP1). Therefore, we
will now focus on the dual problems and the $\tau$ variables, to which we have
paid little attention so far.

###  3.4 Ironing

In this section we examine the connection between the primal and dual via
strong duality and what insights this can give us about optimal solutions,
i.e., optimal auctions. The parallels between the dominant and the Bayesian
setting are striking. The primal LPs (LP2) and (BLP2) only differ in the
monotonicity constraints. Analogously in the dual programs the corresponding
$\tau$ variables differ accordingly.

#### Thought experiment

For a brief moment we fix all $\tau$ variables to be zero such that both
settings have the same dual inequalities. Then the optimal dual solution would
clearly be to point-wise set

$\psi(\bm{v})=f(\bm{v})\max_{i\in[n]}\varphi_{i}^{+}(k),$

where $\varphi_{i}^{+}(k)\coloneqq\max\\{0,\varphi_{i}(k)\\}$ is the non-
negative part of $\varphi_{i}(k)$. In words, given a bid profile $\bm{v}$,
$\psi$ would be set equal to the highest non-negative virtual value among all
players multiplied with the probability that this bid profile is realized. As
all players share the same $f(\bm{v})$ the winning bidder is has to have the
highest non-negative virtual value. More precise, we draw the connection to
the primal. By complementary slackness we would have the following
implications for any optimal solution:

  * •

$a_{i}(k,\bm{k}_{-i})>0\Longrightarrow\psi(\bm{v})=f(\bm{v})\varphi_{i}(k)$,
i.e. if a player has positive probability to win, then the dual inequality has
to be met with equality, and

  * •

$\psi(\bm{v})>0\Longrightarrow\sum_{i=1}^{n}a_{i}(\bm{v})=1$, if at least one
player has a positive virtual value, the item is allocated with full
probability, potentially distributed over multiple players.

Now we consider a specific bid profile $\bm{v}$ and a player’s monotonicity
constraint for the variables $a_{i}(k,\bm{k}_{-i})$ and
$a_{i}(k+1,\bm{k}_{-i})$. Assume that $a_{i}(k,\bm{k}_{-i})>0$, then the same
has to hold for $a_{i}(k+1,\bm{k}_{-i})$. By complementary slackness for
$a_{i}(k,\bm{k}_{-i})>0$ player $i$ has to be the player with the highest non-
negative virtual value in $\bm{v}$, potentially among others. Now keep all
other players fixed but increase the value of player $i$ to the next value.
Although, $a_{i}(k+1,\bm{k}_{-i})>0$ implies that player $i$ still has to have
the highest non-negative virtual value, if $\varphi_{i}(k)>\varphi_{i}(k+1)$
this can no longer be ensured in general. Thus, decreasing virtual values can
cause a contradiction and the $\tau$ variables cannot be set to zero in
general.

To resolve this problem we find values for $\tau$ that absorb any decrease of
the virtual values, i.e., _iron out_ such intervals. If $\varphi$ and $\tau$
combined are non-decreasing, we show in Lemma 8 that the optimal auction can
easily be found via complementary slackness. Note, that the discussion of this
problem is independent of DSIC or BIC truthfulness. Its solution, i.e. the
assigned values to $\tau$ may differ in the two cases, but we show in Lemma 6
that the ironed virtual values are equivalent. For now, we use the notion of
BIC and translate this to the DSIC setting later on. In the following we show
the existence of these dual variables that ensure monotonicity as a solution
of a system of linear equations. Furthermore, we show that this choice is
unique and, therefore, the ironing is equivalent for the DSIC and the BIC
setting. Unsurprisingly we obtain the same values as in the ironing algorithm
of [CDW19].

######  Lemma 5 (Ironing).

Let $\varphi_{i}(k)$ for $k\in[K_{i}]$ be a player $i$’s virtual values. Then
there exist _unique_ values $\tau\in\mathbb{R}_{+}^{K_{i}}$ such that

$\tilde{\varphi}_{i}(k)\coloneqq\varphi_{i}(k)+\frac{\tau_{i}(k,k-1)}{f_{i}(k)}-\frac{\tau_{i}(k+1,k)}{f_{i}(k)}$
(19)

is non-decreasing. We call this monotone sequence _ironed virtual values_.

###### Proof.

In abuse of notation for the rest of the proof we fix player $i$ and drop the
index. This is because the ironing of (19) is independent of all other
players.

To check whether the sequence $\varphi(k)$ is monotone, we construct a
piecewise linear function whose derivative assumes the values $\varphi(k)$.
Let $S_{0}\coloneqq 0$ and $S_{k}\coloneqq\sum_{j=1}^{k}\varphi(j)f(j)$ for
$k\in[K]$, as well as $F_{0}\coloneqq 0$ and $F_{k}\coloneqq
F(k)=\sum_{j=1}^{k}f(j)$ for $k\in[K]$. We then simply connect all
$(F_{k},S_{k})$ to construct the piecewise linear function
$S(x):[0,1]\longrightarrow\mathbb{R}$, and obtain
$\varphi(k)=\frac{S_{k}-S_{k-1}}{F_{k}-F_{k-1}}$, i.e. the slope of $S(x)$ for
$x\in(F_{k-1},F_{k})$. If this function is convex, $\varphi(k)$ is non-
decreasing and nothing needs to be done, i.e. all $\tau(k,k-1)$ can be set to
zero. Otherwise, we construct the convex hull $H$ of this function. If the
convex hull connects two points $(F_{l-1},S_{l-1})$ and $(F_{r},S_{r})$ with
$l<r$ and $H(x)<S(x)$ for all $x\in(F_{l-1},F_{r})$, the interval
$[F_{l},F_{r}]$ has to be ironed. For that we need to choose the $\tau$
variables such that $\tilde{\varphi}(k)$ is constant for $k\in[l,r]$ and leave
all other virtual values unchanged. This means that for all $k\in[l,r]$ it has
to hold

$\varphi(k)+\frac{\tau(k,k-1)}{f(k)}-\frac{\tau(k+1,k)}{f(k)}=c$

for some constant $c\in\mathbb{R}$. This constant as well as the values of
$\tau$ can be computed via the system of linear equations

$\begin{pmatrix}1&\frac{1}{f({l})}&0&\cdots&0\\\
\vdots&-\frac{1}{f({l+1})}&\frac{1}{f({l+1})}&\ddots&\vdots\\\
\vdots&0&\ddots&\ddots&0\\\
\vdots&\vdots&\ddots&-\frac{1}{f({r-1})}&\frac{1}{f({r-1})}\\\
1&0&\cdots&0&-\frac{1}{f({r})}\end{pmatrix}\begin{pmatrix}c\\\
\tau({l+1},l)\\\ \vdots\\\
\tau({r},{r-1})\end{pmatrix}=\begin{pmatrix}\varphi({l})\\\ \vdots\\\
\vdots\\\ \vdots\\\ \varphi({r})\end{pmatrix}.$

Note, that as we have to leave all other virtual values unchanged, we cannot
choose $\tau(l,l-1)$ or $\tau(r+1,r)$ non-zero. Furthermore, if a variable
$\tau(k,k-1)$ for some $k\in[l+1,r]$ would assume the value zero, this
variable separates two adjacent intervals $[l,k-1]$ and $[k,r]$, and these
have to be ironed individually. Thus, all $\tau$ variables can be assumed to
be positive. The first observation is that the square matrix has absolute
determinant value $\frac{\sum_{j=l}^{r}f(j)}{\prod_{j=l}^{r}f(j)}$. Therefore,
the solution of the system is always unique. Hence, there is only one option
on how to choose the $\tau$ variables in order to obtain constant
$\tilde{\varphi}(k)$ for $k\in[l,r]$. We can also compute the value of $c$ by
Cramer’s rule and obtain
$c=\frac{\sum_{j=l}^{r}\varphi(j)f(j)}{\sum_{j=l}^{r}f(j)}$, the average
virtual value. This is the same as $c=\frac{S_{r}-S_{l-1}}{F_{r}-F_{l-1}}$,
i.e. the slope of the convex hull within the ironed interval. The average
virtual value clearly yields the same expected virtual welfare objective
function that could have been realized without the ironing, thus, the ironing
does not affect optimality.

Lastly, we have to ensure that the unique values of $\tau$ over an ironed
interval are indeed positive. This follows directly by strong duality as this
gives us the existence of a dual solution with non-negative $\tau$, the system
of linear equations then additionally yields their uniqueness. ∎

As the virtual values are identical under DSIC and BIC truthfulness their
convex hulls are the same as well. Hence, we can show that by the uniqueness
of $\tau$ in Lemma 5 the ironing has to be equivalent in both settings.

######  Lemma 6.

The ironed virtual values under DSIC truthfulness are equivalent to the BIC
ironed virtual values. Furthermore, as the choice of $\tau$ is unique in both
cases, there is a one to one identification between the DSIC and BIC $\tau$
variables.

###### Proof.

We start with the crucial observation that, as the virtual values are the same
in both settings, the $\tau$ variables in the DSIC ironing have to construct
the exact same convex hull. Therefore, for player $i$ equality must hold for
all $k\in[K_{i}]$

$\varphi_{i}(k)+\frac{\tau_{i}(k,k-1)}{f_{i}(k)}-\frac{\tau_{i}(k+1,k)}{f_{i}(k)}=\varphi_{i}(k)+\frac{\tau_{i}(k,k-1,\bm{k}_{-i})}{f(\bm{v})}-\frac{\tau_{i}(k+1,k,\bm{k}_{-i})}{f(\bm{v})}.$

Lemma 5 gives us the uniqueness of the $\tau$ variables for the BIC ironing.
To obtain the equality of the ironed values we have to define uniquely

$\tau_{i}(k+1,k,\bm{k}_{-i})\coloneqq
f(\bm{k}_{-i})\tau_{i}(k,k-1)\quad\text{or}\quad\tau_{i}(k,k-1)\coloneqq\frac{\tau_{i}(k+1,k,\bm{k}_{-i})}{f(\bm{k}_{-i})}.$
(20)

Note, that the latter is still valid since all
$\frac{\tau_{i}(k+1,k,\bm{k}_{-i})}{f(\bm{k}_{-i})}$ have to be the same
regardless of $\bm{v}_{-i}.$ The uniqueness follows by the non-negativity of
the $\tau$ variables. ∎

Lemma 6 establishes an equivalence involving the $\tau$ variables in the
ironing procedure. These are the only variables that differ between the DSIC
and BIC truthfulness settings. This allows us to connect the two perspectives
proving Point 2 ofTheorem 1.

######  Lemma 7 (DSIC Optimality).

Let $(\bm{a},\bm{p})$ be an optimal DSIC auction, i.e. an optimal solution of
(LP2). Then $(\bm{a},\bm{p})$ is an optimal BIC auction, i.e. optimal for
(BLP2).

###### Proof.

Let $(\bm{a},\bm{p})$ be an optimal solution of (LP2). Then there exists a
corresponding dual solution $(\lambda,\psi,\tau)$ with values for $\tau$ such
that the ironed virtual values in the dual are non-decreasing and $\lambda$ is
fixed by setting all upward variables equal to zero. As the BIC truthfulness
constraints are a relaxation of DSIC truthfulness, $(\bm{a},\bm{p})$ clearly
is a BIC auction (see Section 2.2), i.e., feasible for (BLP2).

If we find dual variables that are feasible for (BDP1) and satisfy
complementary slackness we prove that $(\bm{a},\bm{p})$ is also an optimal BIC
auction. This can be done straightforward: The dual variables $\psi$ are
chosen to be the same, the $\tau$ variables according to (20) and the
$\lambda$ variables are uniquely determined by setting all upward $\lambda$
equal to zero as well. Since all dual constraints reduce to being exactly the
same, the complementary slackness immediately holds. ∎

Without loss of generality by Lemma 4 we can assume, that in an optimal DSIC
auction $\bm{a}$ is binary since any extreme point of the set of feasible
solutions for (LP2) is integer in the allocation components. By that, any
fractional optimal solution is only a convex combination of such extreme
points. The same transfers to the BIC setting: If there are multiple integer
solution optimal DSIC auctions, each of them is also an optimal BIC auction
and so is any convex combination.

######  Lemma 8 (Optimality of Determinism).

The set of optimal BIC auctions always contains a deterministic auction, and
it can be computed by solving the linear program (LP2).

Beyond formally ensuring the existence of a deterministic optimal solution, we
want to derive the explicit auction when we are given a bid profile
$\bm{v}\in\bm{V}$. By the complementary slackness condition

$a_{i}(k,\bm{k}_{-i})>0\quad\Longrightarrow\quad\psi(\bm{v})=f(\bm{v})\tilde{\varphi}_{i}(k)=f(\bm{v})\max_{i\in[n]}\tilde{\varphi}_{i}(k),$

and the existence of an integral solution, we essentially have shown Point 3
of Theorem 1, i.e., receiving a bid profile $\bm{v}\in\bm{V}$ the item is
allocated to the highest non-negative ironed virtual bidder. The corresponding
payments are computed via (14) which by determinism reduces to the critical
bid, i.e., the threshold value of such that the player still wins.

######  Remark 1.

Although, we can describe the optimal single-item auction clear and explicit
via complementary slackness, an interesting insight is worth to be mentioned:
By the ironing, i.e. the monotone $\tilde{\varphi}$, in combination with a
deterministic tie-breaking rule we get the monotonicity of the primal program
_for free_. This is because a player with non-decreasing ironed virtual values
can only be allocated more when increasing the own value while all other
players stay the same, as long as ties are broken consistently. We can then
state the optimal single-item auction problem as finding an allocation from

$\displaystyle\max\quad$
$\displaystyle\sum_{\bm{v}\in\bm{V}}\sum_{i=1}^{n}a_{i}(\bm{v})\tilde{\varphi}_{i}(k)f(\bm{v})$
s.t. $\displaystyle\sum_{i=1}^{n}a_{i}(\bm{v})\leq 1,$
$\displaystyle\;\text{for}\;\bm{v}\in\bm{V}.$

and only have to ensure the deterministic tie-breaking rule and that the
payments are computed via the formula (14).

##  4 General Single-Parameter Auction Design: a KKT Approach

In general, single-parameter auctions go far beyond the single-item case. In
this section we generalize our formulation from the previous section and
present a framework for a wider range of feasibility spaces. In fact, the
specialization on the single-item setting emerges solely from the feasibility
constraints (8). In a more general single-parameter setting we want to relax
feasibility while still holding on to truthfulness, i.e., that the players
have no incentive to misreport their true values. We maintain the linearity of
the truthfulness constraints that arises from the definition of a player’s
utility (1), which is natural for the single-parameter auction design. Our
framework which unites the techniques from the single-item setting, i.e., the
duality approach connected by complementary slackness, is a KKT system
formulation [KT51].

Again we summarize our results of this section in a main theorem:

######  Theorem 2 (Optimal Single-Parameter Auction).

For any discrete convex single-parameter auction setting, under the objective
of maximizing a convex combination of revenue and social welfare (see GM1),
the following hold: 1. If our setting is TU, then there exists an optimal
auction which is integral.333Recall the definition of an integral auction from
Section 2.1, page 2.1. The definition of a totally unimodular (single-
parameter) auction setting can be found in Definition 2. 2. _Any_ optimal DSIC
auction is an optimal BIC auction. 3. The following DSIC auction is optimal
(even within the class of BIC auctions): • Choose pointwise an allocation that
maximizes the generalized ironed virtual welfare (GM2), breaking ties
arbitrarily. • Collect from the allocated bidders a payment equal to their
critical bids (21).

The framework we will present in Section 4.2 allows us to assume that any
feasible solution of the KKT system is also an optimal solution. Within this
rather abstract formulation we are free to leave the ambiguity whether to
interpret the truthfulness constraint as DSIC or BIC. This not only reveals
the strong similarity of the two interpretations, but also allows us great
clearness when investigating their connection for Point 2. Motivated by this
in Section 4.4 we establish a setting where we can guarantee that the optimal
auction is integral and randomization or fractional allocation is not
necessary. Even in the very general case of Section 4, Point 3 gives a
description of the optimal auction. We not only are able to maintain the
transition to welfare maximization (see Section 4.3), but also derive the
identical payment rule as in the single-item setting. Although, complementary
slackness cannot guarantee such a clear optimal auction as in Theorem 1 in
Section 5 we present an application to show that even in a general case with
combinatorial feasibility constraints the auction can be described nicely.

###  4.1 Notation

For the general model formulation we want to use a notation that provides
simplicity while at the same time allows to model very general settings.
Still, we frequently draw the connection to the single-item LP formulation
such that the reader can always recall this as a special case. In the
following we will use a unified notation: In both settings of truthfulness,
DSIC and BIC, each allocation and payment variable represents an outcome per
given bid profile $\bm{v}\in\bm{V}$ and per player $i\in[n].$ We write the
allocations $\bm{a}$ and payments $\bm{p}$ as vectors of dimension
$\mathcal{N}\coloneqq n|\bm{V}|=n\cdot K_{1}\cdots K_{n}$. One entry is a
single variable, e.g., $a_{i}(k,\bm{k}_{-i})$. We further define $\bm{f}$ as a
vector of the same dimension. Each entry is the probability that a specific
bid profile $\bm{v}$ is realized, i.e., $f(\bm{v})$ corresponding to the
respective allocation or payment variables $a_{i}(k,\bm{k}_{-i})$ or
$p_{i}(k,\bm{k}_{-i})$ for all players $i\in[n]$. To remain accurate with the
dimensions of the objects that represent social and virtual welfare, we also
define $\bm{\nu}$ as the quadratic $\mathcal{N}\times\mathcal{N}$ matrix with
all values and similarly $\bm{\varphi}$ with all virtual values corresponding
to player $i$’s value of the respective allocation on the diagonal and zero
elsewhere.

#### Objective function

With this notation we write the generalized objective, a linear combination of
expected revenue and expected social welfare, as

$\alpha\;\mathsf{Rev}(M)+\beta\;\mathsf{SW}(M)=\alpha\bm{f}^{\top}\bm{p}+\beta\bm{f}^{\top}\bm{\nu}\bm{a},$

with
$\bm{f},\bm{a}\in\mathbb{R}_{+}^{\mathcal{N}},\bm{p}\in\mathbb{R}^{\mathcal{N}},\bm{\nu}\in\mathbb{R}_{+}^{\mathcal{N}\times\mathcal{N}}$
and $\alpha,\beta\in\mathbb{R}_{+}$.

#### Truthfulness

Independent of a more general feasibility space the locality of the linear
truthfulness constraints as in (LP1) and (BLP1) maintains. They can be
expressed by matrix vector notation: Matrix $A$ contains the coefficients of
the allocation variables $\bm{a}$ and $B$ the coefficients of the payment
variables $\bm{p}$ of the upward and downward truthfulness constraints. Matrix
$M$ contains the coefficients required to model the monotonicity constraints.
Whether we consider DSIC or BIC truthfulness then depends on the coefficients
and dimensions of the matrices $A,B$ and $M$, and we do not restrict ourselves
to only one of the settings. When directly comparing the two cases we will use
$\bar{M}$ later on to describe the monotonicity constraints in expectation.
However, we differentiate between the downward and upward constraints using,
${}^{\downharpoonleft}\negthinspace A$ and ${}^{\upharpoonleft}\negthinspace
A$. The split constraints are then

${}^{\downharpoonleft}\negthinspace A\bm{a}+{}^{\downharpoonleft}\negthinspace
B\bm{p}\leq 0,\quad{}^{\upharpoonleft}\negthinspace
A\bm{a}+{}^{\upharpoonleft}\negthinspace B\bm{p}\leq 0\quad\text{and}\quad
M\bm{a}\leq 0.$

#### Feasibility space

Besides the truthfulness conditions the allocations’ feasibility space
$\mathcal{A}$ is represented by a finite set of convex and continuously
differentiable constraints. We assume that for each bid profile
$\bm{v}\in\bm{V}$, there are $m\in\mathbb{N}$ constraints. Each constraint
$g_{j}(\bm{a}):\bm{V}\longrightarrow\mathbb{R}_{+}$ involves _only_ allocation
variables corresponding to this very bid profile. That is,
$g_{j}(\bm{a})=g_{j}(a_{1}(\bm{v}),a_{2}(\bm{v}),\dots,a_{n}(\bm{v}))$ for
$j\in[m]$ and some $\bm{v}\in\bm{V}$. To maintain ex-post feasibility the
constraints are copied for each bid profile varying over the $\bm{v}\in\bm{V}$
such that the total number of constraints then is $\mathcal{M}:=m|\bm{V}|$.
E.g., in the single-item case $\mathcal{M}=|\bm{V}|$ and each $g_{j}(\bm{a})$
represents _the one_ feasibility constraint per fixed bid profile, see (8).

Hence, an allocation $\bm{a}$ is feasible, i.e. $\bm{a}\in\mathcal{A}$, if and
only if $g_{j}(\bm{a})\leq 0$ for all $j\in[\mathcal{M}].$ In our framework we
use the notion $G$ which can be seen as a vector of the $g_{j}$ functions,

$G(\bm{a})=\begin{pmatrix}g_{1}(\bm{a})\\\ g_{2}(\bm{a})\\\ \vdots\\\
g_{\mathcal{M}}(\bm{a})\end{pmatrix},\quad(G(\bm{a}))^{\top}\psi=0\;\Longleftrightarrow\;g_{1}(\bm{a})\psi_{1}=0,\dots,g_{\mathcal{M}}(\bm{a})\psi_{\mathcal{M}}=0.$

$\nabla G(\bm{a})$ is the corresponding Jacobian matrix of $G(\bm{a})$ where
column $i$ contains all functions’ derivatives with respect to the allocation
variable of player $i$ for a given bid profile $\bm{v}$. E.g. in the single-
item case we can write the linear feasibility constraints in matrix vector
notation $G\bm{a}\leq 1$ and $\nabla G(\bm{a})=G^{\top}$. Note, that we can
always hide the non-negativity of the allocations within these constraints.

###  4.2 The General KKT Formulation

Putting the generalized objective function, truthfulness, and the feasibility
constraints together we derive the following General Model (GM1):

$\displaystyle\max\quad$
$\displaystyle\alpha\bm{f}^{\top}\bm{p}+\beta\bm{f}^{\top}\bm{\nu}\bm{a}$
(GM1) s.t. $\displaystyle{}^{\downharpoonleft}\negthinspace
A\bm{a}+{}^{\downharpoonleft}\negthinspace B\bm{p}\leq 0,$
$\displaystyle{}^{\upharpoonleft}\negthinspace
A\bm{a}+{}^{\upharpoonleft}\negthinspace B\bm{p}\leq 0,$ $\displaystyle
M\bm{a}\leq 0,$ $\displaystyle G(\bm{a})\leq 0.$

According to this optimization problem the KKT system covering Primal
feasibility, the Dual constraints, Dual feasibility and the Complementary
slackness conditions then is

$\displaystyle{}^{\downharpoonleft}\negthinspace
A\bm{a}+{}^{\downharpoonleft}\negthinspace B\bm{p}$ $\displaystyle\leq 0,$
(Primal feasibility) $\displaystyle{}^{\upharpoonleft}\negthinspace
A\bm{a}+{}^{\upharpoonleft}\negthinspace B\bm{p}$ $\displaystyle\leq 0,$
$\displaystyle M\bm{a}$ $\displaystyle\leq 0,$ $\displaystyle G(\bm{a})$
$\displaystyle\leq 0,$
$\displaystyle\begin{pmatrix}{}^{\downharpoonleft}\negthinspace A^{\top}\\\
{}^{\downharpoonleft}\negthinspace
B^{\top}\end{pmatrix}{}^{\downharpoonleft}\negthinspace\lambda+\begin{pmatrix}{}^{\upharpoonleft}\negthinspace
A^{\top}\\\ {}^{\upharpoonleft}\negthinspace
B^{\top}\end{pmatrix}{}^{\upharpoonleft}\negthinspace\lambda+\begin{pmatrix}M^{\top}\\\
0\end{pmatrix}\tau+\begin{pmatrix}(\nabla G(\bm{a}))^{\top}\\\
0\end{pmatrix}\psi$ $\displaystyle=\begin{pmatrix}\beta\bm{\nu}\bm{f}\\\
\alpha\bm{f}\end{pmatrix},$ (Dual constraints)
$\displaystyle\lambda,\tau,\psi$ $\displaystyle\geq 0,$ (Dual feasibility)
$\displaystyle({}^{\downharpoonleft}\negthinspace
A\bm{a}+{}^{\downharpoonleft}\negthinspace
B\bm{p})^{\top}{}^{\downharpoonleft}\negthinspace\lambda$ $\displaystyle=0,$
(Complementary slackness) $\displaystyle({}^{\upharpoonleft}\negthinspace
A\bm{a}+{}^{\upharpoonleft}\negthinspace
B\bm{p})^{\top}{}^{\upharpoonleft}\negthinspace\lambda$ $\displaystyle=0,$
$\displaystyle(M\bm{a})^{\top}\tau$ $\displaystyle=0,$
$\displaystyle(G(\bm{a}))^{\top}\psi$ $\displaystyle=0.$

Due to the convexity of all components of (GM1) any feasible solution of the
KKT system is also optimal and vice versa. Observe, that in the KKT system we
have equations for the Dual constraints only instead of inequalities as in the
LP formulation. This is due to the fact that we consider $\bm{a}$ and $\bm{p}$
as free variables but ensure the non-negativity of the allocations within the
feasibility constraints $G$. The corresponding dual variables can always
ensure equality then. However, if we set such a dual variable positive by
complementary slackness this leads to the primal, i.e. the allocation
variable, to be zero. E.g. in the single-item case not having the highest
ironed virtual value of even a negative one always implies zero probability of
allocation. We now use this system to derive similar results as in Section
3.1.

######  Lemma 9.

If $\alpha>0$, the payments of the optimal auction are completely determined
by the allocation variables and the payment rule then is exactly the same as
in the single-item setting (14).

###### Proof.

If $\alpha>0$, the dual constraints corresponding to the payment variables are

${{}^{\downharpoonleft}\negthinspace
B^{\top}}{}^{\downharpoonleft}\negthinspace\lambda+{{}^{\upharpoonleft}\negthinspace
B^{\top}}{}^{\upharpoonleft}\negthinspace\lambda=\alpha\bm{f}.$

These are exactly the equations considered in (DP1) and (BDP1). By Lemma 2 we
know that all ${}^{\downharpoonleft}\negthinspace\lambda$ are strictly
positive. Applying the complementary slackness condition

${({}^{\downharpoonleft}\negthinspace
A\bm{a}+{}^{\downharpoonleft}\negthinspace
B\bm{p})}^{\top}{}^{\downharpoonleft}\negthinspace\lambda=0$

we see that in any feasible KKT solution, i.e., any optimal solution, all
downward incentive compatible conditions have to bind. This gives us the
unique single-item payment rule (14), which we also write in matrix vector
notation as

$\bm{p}=C\bm{a}.$

∎

As the payment rule in the single-item setting is a linear combination of
allocation variables, we use matrix $C$ such that the payments defined by

$\bm{p}=C\bm{a}$ (21)

are the same as (14). The fixed the payments arise regardless of DSIC or BIC
truthfulness. Combining the monotonicity constraints with the payment rule
(21), we know by Lemma 3 for DSIC truthfulness that the local truthfulness
constraints are redundant now. This clearly transfers to BIC as well, thus,
the local upward and downward constraints can be dropped completely from the
system, as long as we hold on the (21) and add a dual variable according to
the payments. We follow the notation from the single-item case and call this
free variable $\rho$. The induced the dual constraints are then

$\begin{pmatrix}C^{\top}\\\ \bm{1}\end{pmatrix}\rho+\begin{pmatrix}M^{\top}\\\
0\end{pmatrix}\tau+\begin{pmatrix}(\nabla G(\bm{a}))^{\top}\\\
0\end{pmatrix}\psi=\begin{pmatrix}\beta\bm{\nu}\bm{f}\\\
\alpha\bm{f}\end{pmatrix}.$

As $\rho$ is a free variable corresponding to equality constraints, it does
not appear in the complementary slackness conditions. Therefore, we can use
its fixed values $\rho=\alpha\bm{f}$ and insert them explicitly. Having the
identical payment rule (21) to the single-item case we know that
$C^{\top}\bm{f}=\bm{\varphi}\bm{f}$ (compare(DP2) and (12)), and since all
elements are linear this transfers when we multiply the equation with the
scalar $\alpha$. Note that the virtual values again are equivalent for DISC
and BIC truthfulness. This closes the analogue to our chain of dual programs
in Section 3.1.

Now we can write an equivalent KKT system for the general setting even before
essentially having to differentiate between DSIC and BIC truthfulness.

$\displaystyle\bm{p}$ $\displaystyle=C\bm{a},$ (General KKT) $\displaystyle
M\bm{a}$ $\displaystyle\leq 0,$ $\displaystyle G(\bm{a})$ $\displaystyle\leq
0,$ $\displaystyle(\nabla G(\bm{a}))^{\top}\psi$
$\displaystyle=\alpha\bm{\varphi}\bm{f}+\beta\bm{\nu}\bm{f}-M^{\top}\tau,$
$\displaystyle\tau,\psi$ $\displaystyle\geq 0,$
$\displaystyle(M\bm{a})^{\top}\tau$ $\displaystyle=0,$
$\displaystyle(G(\bm{a}))^{\top}\psi$ $\displaystyle=0.$

###  4.3 Generalized Virtual Welfare Maximization

The right-hand side of the dual constraints in the General KKT system is a
modification of the virtual values we know from revenue maximization in
Section 3. E.g. $\alpha=1$ and $\beta=0$ is pure expected revenue
maximization. However, we can combine these two objects in a nice way and
obtain what we call _generalized virtual values_. We quickly reshape

$\alpha\bm{\varphi}\bm{f}+\beta\bm{\nu}\bm{f}=(\alpha\bm{\varphi}+\beta\bm{\nu})\bm{f}$

and obtain for player $i$ with value $v_{i,k}$ the generalized virtual value

$\alpha\,\varphi_{i}(v_{i,k})+\beta\,v_{i,k}=(\alpha+\beta)\,v_{i,k}-\alpha\,(v_{i,k+1}-v_{i,k})\frac{1-F_{i}(v_{i,k})}{f_{i}(v_{i,k})}.$
(22)

Now for larger $\beta>0$ and a small value for $\alpha$ the generalized
virtual values are more likely to be non-decreasing, still, we have to
consider potential non-monotonicities in the general case as well.

Even though by complementary slackness we can not directly derive such a clear
auction as in Theorem 1 we are still interested in the role of complementary
slackness in the general case and whether it requires an analogue of ironing.
To investigate this, we carry out the same thought experiment as in Section
3.4 (Page 3.4): Fix a value profile $\bm{v}\in\bm{V}$ as well as a player $i$
and assume that the player has positive probability of winning, i.e.
$a_{i}(k,\bm{k}_{-i})>0$, thus, the corresponding dual constraint has to bind.
If we increase the player’s value and keep all other players’ values fixed we
run into the same problem as in the single-item case: All other players’
generalized virtual values remain the same. If player $i$’s generalized
virtual values are decreasing, in general, this might lead to a strict
inequality which possibly can only be fixed by increasing the dual variable
corresponding to the non-negativity. Due to complementary slackness this would
lead to $a_{i}(k+1,\bm{k}_{-i})=0$, contradicting the primal monotonicity
constraints. Therefore, we also need an analogue of ironing, i.e., a choice of
values for $\tau$ such that for player $i$ the generalized virtual values (22)
are non-decreasing in $k\in[K_{i}]$. The procedure including the uniqueness
remains the same as in Lemma 5, as we again flatten out certain intervals to
be constant by construction of a convex hull which is not specified for
virtual values only.

The result of inserting these unique values for $\tau$ is what we call the
_ironed generalized virtual values_

$(\alpha\tilde{\bm{\varphi}}+\beta\tilde{\bm{\nu}})\bm{f}:=\alpha\bm{\varphi}\bm{f}+\beta\bm{\nu}\bm{f}-M^{\top}\tau.$

This is, that the sequences

$\displaystyle\alpha\,\varphi_{i}(v_{i,k})+\beta\,v_{i,k}+\frac{\tau_{i}(k,k-1,\bm{k}_{-i})}{f(\bm{v})}-\frac{\tau_{i}(k+1,k,\bm{k}_{-i})}{f(\bm{v})}$
(Generalized DSIC ironing)
$\displaystyle\alpha\,\varphi_{i}(v_{i,k})+\beta\,v_{i,k}+\frac{\tau_{i}(k,k-1)}{f_{i}(k)}-\frac{\tau_{i}(k+1,k)}{f_{i}(k)}$
(Generalized BIC ironing)

not only are non-decreasing in both settings, but also assume the exact same
values for each $v_{i,k}$. This is due to the fact that the generalized
virtual values again are identical in both settings and the $\tau$ variables
are unique, see Lemma 5.

The only difference between the DSIC and the BIC formulation of the General
KKT system lies in the monotonicity constraints $M\bm{a}\leq 0$ and the
corresponding dual variables $\tau$. To distinguish between the settings we
use $\bar{M}$ and $\bar{\tau}$ for the BIC case. As we again add the identical
values in (Generalized DSIC ironing) and (Generalized BIC ironing) we can
unite the generalization of Lemma 6 and Lemma 7.

######  Lemma 10 (DSIC Optimality).

Any feasible, hence optimal, solution of the General KKT system under DSIC
truthfulness is feasible, hence optimal, for the BIC setting.

###### Proof.

Recall that any primal DSIC solution is feasible for the primal BIC
constraints. The dual variables $\psi$ are chosen to be the same in both
cases. Lastly, since the ironing is unique in both settings there is a one-to-
one correspondence and we can write by the (Generalized DSIC ironing) and
(Generalized BIC ironing)

$\frac{\tau_{i}(k,k-1,\bm{k}_{-i})}{f(\bm{v})}-\frac{\tau_{i}(k+1,k,\bm{k}_{-i})}{f(\bm{v})}=\frac{\tau_{i}(k,k-1)}{f_{i}(k)}-\frac{\tau_{i}(k+1,k)}{f_{i}(k)}$

which is equivalent, using the matrix vector notation, to
$M^{\top}\tau=\bar{M}^{\top}\bar{\tau}$. The complementary slackness transfers
as well by
$0=(M\bm{a})^{\top}\tau=\bm{a}^{\top}M^{\top}\tau=\bm{a}^{\top}\bar{M}^{\top}\bar{\tau}=(\bar{M}\bm{a})^{\top}\bar{\tau}.$
∎

Putting everything together we obtain an equivalent problem formulation for
(GM1). This is, finding a generalized optimal single-parameter auction reduced
to solving the optimization problem

$\displaystyle\max\quad$
$\displaystyle\bm{f}^{\top}(\alpha\tilde{\bm{\varphi}}+\beta\tilde{\bm{\nu}})\bm{a}$
(GM2) s.t. $\displaystyle\bm{p}=C\bm{a},$ $\displaystyle G(\bm{a})\leq 0,$

and additionally fixing a deterministic tie-breaking rule. By this rule and
the flattening procedure we ultimately get monotonicity _for free_. As the
generalized ironed virtual values are non-decreasing, increasing a player’s
value while all other players stay the same ensures monotonicity of the
allocations as long as ties are broken consistently. Therefore, when solving
for an optimal _generalized ironed virtual welfare maximizing_ allocation we
can restrict ourselves to pointwise finding such a maximizer under the
feasibility constraints then. The payments are computed afterwards as a
function of the allocations by the same rule as in the single-item case (14).

###  4.4 Integral Auctions

The generalized single-parameter auction optimization problem formulation
(GM2) provides great transparency on how to find an optimal auction in the
general setting, that is, to focus on the allocations and compute the payments
afterwards. The only relevant constraints for the allocations are
$G(\bm{a})\leq 0$. In this section we want to make use of the geometrical
property that also ensures determinism of the optimal single-item auction: As
the objective points into a certain direction, integral extreme points ensure
that an optimal solution has to be assumed in one of these. To use this in the
general case we have to assume that $G(\bm{a})\leq 0$ is linear and we can
write the constraints in matrix vector notation as $G\bm{a}\leq b$. By that,
we define an auction setting with sufficient conditions for obtaining an
integral auction.

######  Definition 2 (TU auction setting).

A (single-parameter) auction setting will be called _totally unimodular (TU)_
, if the allocation feasibility constraints are given by a TU matrix. More
precisely, if there exists a TU matrix $G$ and an integral vector $b$ such
that

$\mathcal{A}=\\{\,\bm{a}\;|\;G\bm{a}\leq b\\}.$

As we know by Lemma 10 that optimality transfers from the formulation under
DSIC to BIC, the TU auction setting within the DSIC formulation ensures the
existence of an integral solution under BIC truthfulness as well. Hence, we
can state the general counterpart of Lemma 4 for the general case, that is
Point 1 of Theorem 2.

######  Lemma 11 (Integral optimality).

If our (single-parameter) auction setting is TU, then there exists an optimal
BIC auction which is integral.

###### Proof.

We start with the notation of the constraint matrix: Let $G$ be an
$\mathcal{M}\times\mathcal{N}$ matrix and $M$ the constraint matrix of the
DSIC monotonicity constraints to ensure the deterministic tie-breaking rule.
The set of feasible allocations for the General KKT system is then given by
the polyhedron

$\\{\,\bm{a}\;|\;G\bm{a}\leq b,\,M\bm{a}\leq 0\\}.$

The monotonicity constraints are the same for the general case and the proof
follows directly from the matrix structure used in Lemma 4: As $G\bm{a}\leq b$
has to contain the non-negativity of $\bm{a}$ we separate the constraints to
as $\bm{a}\geq 0$ and the remaining constraints to $G^{\prime}\bm{a}\leq
b^{\prime}$. Therefore we can write the constraints in the general case as

$\begin{pmatrix}M\\\ -\bm{1}\\\
G^{\prime}\end{pmatrix}\bm{a}\leq\begin{pmatrix}0\\\ 0\\\
b^{\prime}\end{pmatrix}.$

By the dimension of the unity matrix, TU of $M$ and $G^{\prime}$ themselves
are sufficient. $M$ is TU as it has the structure of the transposed of a
adjacency matrix, and $G^{\prime}$ is TU if and only if $G$ is TU. ∎

This implies that several single-parameter auction settings have integral
solutions also in the BIC setting. Examples are, of course, the single-item
auction, but also the $k$-unit auction, the digital good auction, and in
general combinatorial auctions where all constraints can be described via a
totally unimodular matrix $G$.

We will dive deeper in such a combinatorial auction in the application
presented in Section 5.

##  5 Application: Buying Flows on a Tree

We consider a problem of $n$ requests to transport specific amounts of a good
through a capacitated network modelled by a directed graph. This problem is
motivated by the transport of gas where the pressure along a path is
decreasing. By this decrease of pressure the assumption to have a directed
graph without circuits seems reasonable. In fact, a close real-world
approximation of the Greek gas network [Sch+17] underlying this topology.

The network is therefore considered as the graph $G=(V,E,c)$ with nodes $V$,
directed edges $E$ and edge capacities $c_{e}\in\mathbb{R}_{+}$ with $c_{e}>0$
attached to each edge $e\in E$. Now there are $n$ bidders, each one having a
request to send demand $d_{i}$ of a good from a specific source to a sink node
$s_{i},t_{i}\in V$. Each bidder has a private value $v_{i}\sim F_{i}$ for
sending this amount over the path $s_{i}\leadsto t_{i}$ though the network. We
want to model this problem and find an optimal mechanism for this setting.

#### Objective function

We allow a convex combination of revenue and social welfare in the objective,
i.e. for $\alpha\in(0,1)$ we maximize

$\operatorname*{\mathbb{E}}_{\bm{v}\sim\bm{F}}\nolimits\left[\alpha\sum_{i}p_{i}(\bm{v})+(1-\alpha)\sum_{i}v_{i}x_{i}(\bm{v})\right].$

#### Feasibility space

The feasibility constraints of the network can be modelled via the linear
constraints $Ga\leq b$: Per edge $e\in E$ and per bid profile
$\bm{v}\in\bm{V}$ we have the capacity constraints

$\sum_{i:\,e\in(s_{i}\leadsto t_{i})}d_{i}a_{i}(\bm{v})\leq
c_{e}\quad\Longleftrightarrow\quad\sum_{i:\,e\in(s_{i}\leadsto
t_{i})}\frac{d_{i}}{c_{e}}a_{i}(\bm{v})\leq 1.$ (23)

The corresponding non-negative dual variable for the edge capacity constraint
for $e\in E$ is denoted by $\eta_{e}(\bm{v})$ and we will interpret them as
_edge costs_. For reasons of simplicity we stick with the normalized capacity
constraints, i.e. the right hand formulation of (23), and state this again as
matrix vector constraints by $E\bm{a}\leq 1$. Furthermore, we allow an
allocation of at most one, i.e., $a_{i}(\bm{v})\leq 1$ and denote the
corresponding non-negative dual variable by $\psi_{i}(\bm{v}).$ Quickly
observe, that the single-item setting can be modelled by a single edge with
capacity one and each player having a demand of one to send over this edge.

Applying our general framework we can simplify the right-hand side of the dual
constraints of the KKT system to

$(1-\alpha)\bm{\nu}\bm{f}+\alpha\bm{\varphi}\bm{f}=\left[(1-\alpha)\bm{\nu}+\alpha\bm{\varphi}\right]\bm{f}=\bm{\varphi}^{\alpha}\bm{f},$

where $\bm{\varphi}^{\alpha}$ denotes the diagonal matrix containting the
_$\alpha$ -virtual values_:

$\varphi^{\alpha}(v_{i,k})\coloneqq
v_{i,k}-\alpha\cdot(v_{i,k+1}-v_{i,k})\frac{1-F_{i}(v_{i,k})}{f_{i}(v_{i,k})}.$

For the remainder of this section we assume that the ironing has already been
carried out, hence, the solution for the flow auction can be found by
computing an optimal solution of

$\displaystyle\max\quad$
$\displaystyle\bm{f}^{\top}\bm{\tilde{\varphi}}^{\alpha}\bm{a}$ s.t.
$\displaystyle\bm{p}=C\bm{a},$ $\displaystyle\bm{a}\leq 1,$ $\displaystyle
E\bm{a}\leq 1,$

including a consistent tie-breaking rule to ensure monotonicity. To actually
find the optimal auction we investigate the complementary slackness condition
of the dual constraints associated with the allocation variables. The dual
constraint for variable $a_{i}(k,\bm{k}_{-i})$ with the already ironed (unique
values for $\tau$ inserted) is

$\psi_{i}(k,\bm{k}_{-i})+\sum_{e\in(s_{i}\leadsto
t_{i})}\frac{d_{i}}{c_{e}}\eta_{e}(k,\bm{k}_{-i})\geq
f(\bm{v})\tilde{\varphi}_{i}^{\alpha}(k).$ (24)

The direct implications of complementary slackness for optimal primal and dual
values are:

  * •

$\tilde{\varphi}_{i}^{\alpha}(k)<0\Longrightarrow a_{i}(k,\bm{k}_{-i})=0$,
i.e., a player with negative ironed $\alpha$-virtual value never wins,

  * •

$\eta_{e}(\bm{v})>0\Longrightarrow\sum_{i:e\in(s_{i}\leadsto
t_{i})}d_{i}a_{i}(\bm{v})=c_{e}$, i.e., if an optimal solution requires costs
on edge $e$, its capacity is fully utilized.

  * •

$\psi_{i}(k,\bm{k}_{-i})>0\Longrightarrow a_{i}(k,\bm{k}_{-i})=1$, i.e., there
exists a condition that leads to full allocation.

If feasible, it would clearly be revenue maximizing to let all players with
non-negative ironed $\alpha$-virtual values win. We are therefore interested
in resolving conflicts in competition between bidders on an edge that would
exceed capacity when fully awarding all players. For this analysis we need to
define and quantify the term of competition.

######  Definition 3 (Competitive edge).

An edge $e\in E$ will be called _competitive_ with respect to a given subset
of players $\mathcal{I}\subseteq[n]$ if

$\sum_{i\in\mathcal{I},\,e\in(s_{i}\leadsto t_{i})}\frac{d_{i}}{c_{e}}>1.$
(25)

The quantity on the left-hand side of (25) is called the _competition_ of $e$
(with respect to $\mathcal{I}$).

We now present an algorithm solving for the optimal allocation for which we
compute the payments afterwards. When fixing the received bid profile $\bm{v}$
in the first step we will abuse the notation by dropping the values and
indices as they are consistent afterwards.

###  5.1 A Combinatorial Algorithm

In this section we present an algorithm that makes use of the KKT system by
using all its components, i.e. primal feasibility, the dual constraints, dual
feasibility, and complementary slackness condition and show how they interact
with each other when we are interested in finding an optimal auction. To do
this, we consider the ironed virtual values as the players’ _budgets_ and
calculate _buy-in_ costs for the edges.

  1. 1.

Fix a $\bm{v}$ and set all corresponding $\psi_{i}=\eta_{e}=0$ as well as a
budget $b_{i}\coloneqq f(\bm{v})\tilde{\varphi}_{i}^{\alpha}(k)$ for each
player. Let $\mathcal{I}\subseteq[n]$ the set of all players with non-negative
budget, i.e., non-negative ironed $\alpha$-virtual value (and already set for
all other players $a_{i}(\bm{v})=0$ as they cannot afford the buy-in of zero).
Furthermore, define the empty ordered set of players
$\mathcal{J}\coloneqq\\{\emptyset\\}$.

  2. 2.

Repeat the following until there is no competitive edge left:

    1. (a)

Find the edge $e$ with highest competition w.r.t. $\mathcal{I}$

    2. (b)

Define the buy-in for the edge as

$\min_{i\in\mathcal{I},e\in(s_{i}\leadsto t_{i})}b_{i}\frac{c_{e}}{d_{i}}$

and add this value to $\eta_{e}$.

    3. (c)

Charge every $i\in\mathcal{I}$ with $e\in(s_{i}\leadsto t_{i})$ the buy-in
$\eta_{e}$ from their budget. Delete all players with $b_{i}=0$ from
$\mathcal{I}$ and add them to the start of $\mathcal{J}$ by a deterministic
rule, e.g., in lexicographical order.

  3. 3.

Set all $\psi_{i}\coloneqq\max\\{b_{i},0\\}$ and allocate in the following
way:

    1. (a)

We _fully_ allocate all players $i$ with $\psi_{i}>0$, that is, we set
$a_{i}(\bm{v})=1$. These players have endured all competition, and even have
some of their budget left.

    2. (b)

Players in $\mathcal{J}$ _fractionally_ fill up the leftover capacities of the
edge where they spent their _last_ budget, one-by-one, according to the order
of $\mathcal{J}$. More formally,

      1. i.

choose $i$, the first player of the ordered set $\mathcal{J}$, and $e$, the
edge where $i$ spent the last budget and was added to $\mathcal{J}$,
furthermore define $\delta_{e}$ to be the remaining capacity on edge $e$ after
the prior full allocations,

      2. ii.

we set $a_{i}(\bm{v})=\frac{\delta_{e}}{c_{e}}$, remove $i$ from
$\mathcal{J}$, and go back to the previous step.

    3. (c)

All other players cannot afford the required edge prices and lose, i.e.,
$a_{i}(\bm{v})=0$.

  4. 4.

The payments are computed afterwards via the known payment rule (14).

######  Theorem 3.

The allocations and payments computed in the combinatorial algorithm are
optimal for the flow auction problem.

###### Proof.

We prove optimality as the computed solution of the algorithm is feasible for
the respective KKT system. To do so we have to verify that each component of
the General KKT system is satisfied. Note, that by the observations of Section
4.3 using the ironed $\alpha$-virtual values and a deterministic tie-breaking
rule, we get the monotonicity for free and do not have to consider these
constraints nor the corresponding complementary slackness condition.

  * •

Primal feasibility:
The allocations computed in Step 3 are clearly non-negative and at most one.
This step also ensures the feasible flows, i.e. $E\bm{a}\leq 1$: As the
algorithm eliminates players from $\mathcal{I}$ until no edge is competitive
any more, i.e. until

$\sum_{i\in\mathcal{I},\,e\in(s_{i}\leadsto t_{i})}\frac{d_{i}}{c_{e}}\leq 1$

holds for all edges, the full allocation never exceeds capacity. Filling up
the remaining capacities fractionally leads to exploitation but never to an
overflow.

  * •

Dual constraints:
The dual constraint corresponding to $a_{i}(k,\bm{k}_{-i})$ essentially has
the form of (24). In the KKT formulation there is an additional non-negative
dual variable $\kappa_{i}(\bm{v})$ corresponding to the non-negativity of the
allocation variable. Furthermore, the constraint then is an equation, namely

$\psi_{i}(\bm{v})+\sum_{e\in(s_{i}\leadsto
t_{i})}\frac{d_{i}}{c_{e}}\eta_{e}(\bm{v})-\kappa_{i}(\bm{v})=f(\bm{v})\tilde{\varphi}_{i}^{\alpha}(k).$

If a player’s buy-in costs are too high, i.e., $\sum_{e\in(s_{i}\leadsto
t_{i})}\frac{d_{i}}{c_{e}}\eta_{e}(\bm{v})>f(\bm{v})\tilde{\varphi}_{i}^{\alpha}(k)$
we can choose $\kappa_{i}(\bm{v})>0$ such that equality is ensured. The other
way round, if there is budget left, we set $\psi_{i}(\bm{v})>0$ such that
equality is ensured as well.

  * •

Dual feasibility:
In Step 1 $\psi_{i}(\bm{v})$ and $\eta_{e}(\bm{v})$ are initialized as zero.
The edge prices $\eta_{e}(\bm{v})$ can only increase in Step 2 and in Step 3
we set $\psi_{i}(\bm{v})$ to the remaining budget or zero. Hence, the dual
variables are clearly non-negative.

  * •

Complementary slackness:

    * –

$\psi_{i}(\bm{v})>0\Longrightarrow a_{i}(\bm{v})=1$ and
$a_{i}(\bm{v})<1\Longrightarrow\psi_{i}(\bm{v})=0$
$\psi_{i}(\bm{v})$ is only positive, if player $i$ had some budget left in the
end and is fully allocated. On the other hand, if player $i$ is not fully
allocated, i.e. $a_{i}(\bm{v})<1$, $\psi_{i}(\bm{v})>0$ would be a
contradiction to Step 3.

    * –

$a_{i}(\bm{v})>0\Longrightarrow\kappa_{i}(\bm{v})=0$ and
$\kappa_{i}(\bm{v})>0\Longrightarrow a_{i}(\bm{v})=0$
A player with positive allocation $a_{i}(\bm{v})>0$, either is fully allocated
and has positive $\psi_{i}(\bm{v})$ equal to the remaining budget or is
fractionally allocated and has exactly zero budget left in the end, i.e. in
both cases

$\psi_{i}(\bm{v})+\sum_{e\in(s_{i}\leadsto
t_{i})}\frac{d_{i}}{c_{e}}\eta_{e}(\bm{v})=f(\bm{v})\tilde{\varphi}_{i}^{\alpha}(k)$

and we can set $\kappa_{i}(\bm{v})=0$ then. If $\kappa_{i}(\bm{v})>0$ is
necessary to ensure equality in the corresponding dual constraint the player
cannot afford the buy-in for the required edges and gets no positive
allocation.

    * –

$\eta_{e}(\bm{v})>0\Longrightarrow\sum_{i,\,e\in(s_{i}\leadsto
t_{i})}\frac{d_{i}}{c_{e}}a_{i}(\bm{v})=1$ and $\sum_{i,\,e\in(s_{i}\leadsto
t_{i})}\frac{d_{i}}{c_{e}}a_{i}(\bm{v})<1\Longrightarrow\eta_{e}(\bm{v})=0$
$\eta_{e}$ only increases in Step 2 if $e$ is a competitive edge. By the
fractional allocation in Step 3 a player that would exceed the capacity when
being fully allocated fills up the remaining capacity. Thus, a positive
$\eta_{e}$ always corresponds to an edge with exploited capacity. An edge with
leftover capacity was never the edge with highest competition in Step 2, thus,
$\eta_{e}=0$ never increased from the initialization in Step 1. Otherwise, a
player would have been eliminated from competition at one point and the
remaining capacity would have been used by this player.

∎

## References

  * [BP07] Dirk Bergemann and Martin Pesendorfer  “Information Structures in Optimal Auctions”  In _Journal of Economic Theory_ 137.1, 2007, pp. 580–609  DOI: 10.1016/j.jet.2007.02.001
  * [CDW12] Yang Cai, Constantinos Daskalakis and S. Weinberg  “Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization”  In _Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS)_ , 2012, pp. 130–139  DOI: 10.1109/FOCS.2012.88
  * [CDW13] Yang Cai, Constantinos Daskalakis and S. Weinberg  “Understanding incentives: Mechanism design becomes algorithm design”  In _Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS)_ , 2013, pp. 618–627  DOI: 10.1109/FOCS.2013.72
  * [CDW19] Yang Cai, Nikhil R. Devanur and S. Weinberg  “A Duality-Based Unified Approach to Bayesian Mechanism Design”  In _SIAM Journal on Computing_ 50.3, 2019  DOI: 10.1137/16M1100113
  * [DDT17] Constantinos Daskalakis, Alan Deckelbaum and Christos Tzamos  “Strong Duality for a Multiple-Good Monopolist”  In _Econometrica_ 85.3, 2017, pp. 735–767  DOI: 10.3982/ECTA12618
  * [Elk07] Edith Elkind  “Designing and Learning Optimal Finite Support Auctions”  In _Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2007, pp. 736–745  URL: https://dl.acm.org/doi/10.5555/1283383.1283462
  * [GK18] Yiannis Giannakopoulos and Elias Koutsoupias  “Duality and Optimality of Auctions for Uniform Distributions”  In _SIAM Journal on Computing_ 47.1, 2018, pp. 121–165  DOI: 10.1137/16M1072218
  * [HK07] Jason D. Hartline and Anna R. Karlin  “Profit Maximization in Mechanism Design”  In _Algorithmic Game Theory_ Cambridge University Press, 2007, pp. 331–362  DOI: https://doi.org/10.1017/CBO9780511800481.015
  * [HK10] Alan J. Hoffman and Joseph B. Kruskal  “Integral Boundary Points of Convex Polyhedra”  In _50 Years of Integer Programming 1958–2008: From the Early Years to the State-of-the-Art_ Springer, 2010, pp. 49–76  DOI: 10.1007/978-3-540-68279-0_3
  * [JR11] Geoffrey A. Jehle and Philip J. Reny  “Advanced Microeconomic Theory”  Prentice Hall, 2011
  * [Kri09] Vijay Krishna  “Auction Theory”  Academic Press, 2009
  * [KT51] H.. Kuhn and A.. Tucker  “Nonlinear Programming”  In _Proceedings of the 2nd Berkeley Symposium on Mathematical Statistics and Probability_ University of California Press, 1951
  * [Mil04] Paul Milgrom  “Putting Auction Theory to Work”  Cambridge University Press, 2004  DOI: 10.1017/CBO9780511813825.009
  * [MV04] Alexey Malakhov and Rakesh V. Vohra  “Single and Multi-Dimensional Optimal Auctions: a Network Approach”  Evanston, IL: Northwestern University, Kellogg School of Management, Center for Mathematical Studies in EconomicsManagement Science, 2004  URL: https://hdl.handle.net/10419/31166
  * [Mye81] Roger B. Myerson  “Optimal Auction Design”  In _Mathematics of Operations Research_ 6.1, 1981, pp. 58–73  DOI: 10.1287/moor.6.1.58
  * [Sch+17] Martin Schmidt et al.  “GasLib—A Library of Gas Network Instances”  In _Data_ 2.4, 2017  DOI: 10.3390/data2040040
  * [Sch03] Alexander Schrijver  “Combinatorial optimization: polyhedra and efficiency”  Springer, 2003
  * [Vic61] William Vickrey  “Counterspeculation, Auctions and Competitive Sealed Tenders”  In _Journal of Finance_ 16.1, 1961, pp. 8–37  DOI: 10.1111/j.1540-6261.1961.tb02789.x
  * [Voh11] Rakesh V. Vohra  “Mechanism Design: a Linear Programming Approach”  Cambridge University Press, 2011  DOI: 10.1017/CBO9780511835216

## Appendix

##  Appendix A Local DSIC/BIC Characterization (Lemma 1)

In this appendix we first give a formal proof of the alternative local
characterization of DSIC truthfulness presented in Lemma 1, and then argue how
it can readily be adapted to BIC truthfulness as well.

###### Proof of Lemma 1.

For the proof of Lemma 1 we first show the equivalence of the (DSIC)
conditions and the local DSIC constraints (5) and (6). To do so, we first show
that the local DSIC constraints imply monotonicity. Then the constraint that
truthful bidding yields higher utility than deviating to the next but one
value is implied by two local constraints. This can be done to the higher as
well as to the lower values. In abuse of notation we mainly drop the index of
player $i$ and assume that any allocation of payment variable has as a second
input argument the other players’ fixed values $\bm{v}_{-i}$.

####  $\Longrightarrow$)

Observe that the local DSIC constraints (5) and (6) are trivially implied by
the (DSIC) conditions as they represent only are a reduced subset.

####  $\Longleftarrow$)

Now assume that $(\bm{a},\bm{p})$ satisfies the local DSIC constraints (5) and
(6). We fix a player $i$, value $v\in V_{i}$ and some other players’ values
$\bm{v}_{-i}$. Adding up the two local constraints

$\displaystyle v^{+}a(v^{+})-p(v^{+})$ $\displaystyle\geq
v^{+}a(v)-p(v),\;\text{and}$ $\displaystyle va(v)-p(v)$ $\displaystyle\geq
va(v^{+})-p(v^{+})$

we obtain

$\displaystyle v^{+}a(v^{+})+va(v)$ $\displaystyle\geq v^{+}a(v)+va(v^{+})$
(26) $\displaystyle(v^{+}-v)a(v^{+})$ $\displaystyle\geq(v^{+}-v)a(v).$ (27)

Therefore, the local DSIC constraints (5) and (6) imply (7) monotonicity.

According to the downward deviation we consider the two local inequalities

$\displaystyle v^{+}a(v^{+})-p(v^{+})$ $\displaystyle\geq
v^{+}a(v)-p(v),\quad\text{and}$ $\displaystyle va(v)-p(v)$ $\displaystyle\geq
va(v^{-})-p(v^{-}).$

Again we add them up and obtain by using monotonicity in the last inequality

$\displaystyle v^{+}a(v^{+})-p(v^{+})+va(v)-p(v)$ $\displaystyle\geq
v^{+}a(v)-p(v)+va(v^{-})-p(v^{-})$ $\displaystyle
v^{+}a(v^{+})-p(v^{+})+va(v)$ $\displaystyle\geq v^{+}a(v)+va(v^{-})-p(v^{-})$
$\displaystyle v^{+}a(v^{+})-p(v^{+})$ $\displaystyle\geq
v^{+}a(v)+va(v^{-})-p(v^{-})-va(v)+v^{+}a(v^{-})-v^{+}a(v^{-})$ $\displaystyle
v^{+}a(v^{+})-p(v^{+})$ $\displaystyle\geq
v^{+}(a(v)-a(v^{-}))-v(a(v)-a(v^{-}))+v^{+}a(v^{-})-p(v^{-})$ $\displaystyle
v^{+}a(v^{+})-p(v^{+})$ $\displaystyle\geq
v^{+}a(v^{-})-p(v^{-})+(v^{+}-v)(a(v)-a(v^{-}))$ $\displaystyle
v^{+}a(v^{+})-p(v^{+})$ $\displaystyle\geq v^{+}a(v^{-})-p(v^{-}).$

Thus, the two local downward inequalities imply the constraint of the
deviation to the next but one value. The analogue of the upward deviation
follows directly when switching $v^{+}$ and $v^{-}$. This clearly can be
extended to see that the deviation to any other value, hence all (DSIC)
constraints are implied by the local DSIC constraints. ∎

Now we could rewrite the proof replacing each allocation and payment variable
with the interim versions

$A_{i}(v)\coloneqq\operatorname*{\mathbb{E}}_{\bm{v}_{-i}\sim\bm{F}_{-i}}\nolimits\left[a_{i}(v,\bm{v}_{-i})\right]\qquad\text{and}\qquad
P_{i}(v)\coloneqq\operatorname*{\mathbb{E}}_{\bm{v}_{-i}\sim\bm{F}_{-i}}\nolimits\left[p_{i}(v,\bm{v}_{-i})\right]$

and rederive the same result for the (BIC) conditions, only in expectation
with respect to the other players’ values.

##  Appendix B Proof of Lemma 2

To prove this, we fix a player $i$ as well as the other players’ bids
$\bm{v}_{-i}$, and proceed inductively over $k\in[K_{i}]$ considering the
equality constraints corresponding to the payment variables. We know by the
dual borderline cases (10) that
$\lambda_{i}(K,K+1,\bm{k}_{-i})=\lambda_{i}(K+1,K,\bm{k}_{-i})=0$.

We start the induction for $k=K_{i}$ and obtain

$\displaystyle\lambda_{i}(K_{i},K_{i}-1,\bm{k}_{-i})+\lambda_{i}(K_{i},K_{i}+1,\bm{k}_{-i})-\lambda_{i}(K_{i}+1,K,\bm{k}_{-i})-\lambda_{i}(K_{i}-1,K,\bm{k}_{-i})=f(K_{i},\bm{k}_{-i})$
$\displaystyle\lambda_{i}(K_{i},K_{i}-1,\bm{k}_{-i})-\lambda_{i}(K_{i}-1,K,\bm{k}_{-i})=f(K_{i},\bm{k}_{-i}).$

As all probabilities are strictly positive, the difference of the $\lambda$
variables is positive as well. By the non-negativity the same has to hold for
the downward variable $\lambda_{i}(K_{i},K_{i}-1,\bm{k}_{-i}).$

Now assume that for some $k\in[K_{i}]$ we have the positive difference
$\lambda_{i}(k,k-1,\bm{k}_{-i})-\lambda_{i}(k-1,k,\bm{k}_{-i})>0$ and consider
the equality constraint for $k-1$,

$\displaystyle\lambda_{i}(k-1,k-2,\bm{k}_{-i})+\lambda_{i}(k-1,k,\bm{k}_{-i})-\lambda_{i}(k,k-1,\bm{k}_{-i})-\lambda_{i}(k-2,k-1,\bm{k}_{-i})=f(k-1,\bm{k}_{-i})$
$\displaystyle\lambda_{i}(k-1,k-2,\bm{k}_{-i})-\lambda_{i}(k-2,k-1,\bm{k}_{-i})=f(k-1,\bm{k}_{-i})+\lambda_{i}(k,k-1,\bm{k}_{-i})-\lambda_{i}(k-1,k,\bm{k}_{-i}).$

Thus, the difference
$\lambda_{i}(k-1,k-2,\bm{k}_{-i})-\lambda_{i}(k-2,k-1,\bm{k}_{-i})>0$ is
strictly positive as well and by that the downward
$\lambda_{i}(k-1,k-2,\bm{k}_{-i})>0.$ This follows for all downward
$\lambda_{i}$ as long as the right-hand side is positive, i.e., until
$\lambda_{i}(1,0,\bm{k}_{-i})$.