11institutetext: Faculty of Computer Science, Technion – Israel Institute of
Technology, 11email<EMAIL_ADDRESS>
# Auctions with Interdependence and SOS: Improved Approximation

Ameer Amer  Inbal Talgam-Cohen

###### Abstract

Interdependent values make basic auction design tasks – in particular
maximizing welfare truthfully in single-item auctions – quite challenging.
Eden et al. recently established that if bidders’ valuation functions are
submodular over their signals (a.k.a. SOS), a truthful 4-approximation to the
optimal welfare exists. We show existence of a mechanism that is truthful and
achieves a tight 2-approximation to the optimal welfare when signals are
binary. Our mechanism is randomized and assigns bidders only $0$ or
$\frac{1}{2}$ probabilities of winning the item. Our results utilize
properties of submodular set functions, and extend to matroid settings.

###### Keywords:

Mechanism design Welfare maximization Submodularity.

##  1 Introduction

One of the greatest contributions of Robert Wilson and Paul Milgrom, the 2020
Nobel Laureates in economics, is their formulation of a framework for auction
design with _interdependent_ values [14]. Up to their work, the standard
assumption underlying auction design theory was that each bidder fully knows
her value for the item being auctioned, because this value depends only on her
own private information. This assumption is, however, far from reality in very
important settings – for example, when the auction is for drilling rights, the
information one bidder has about whether or not there is oil to be found is
extremely relevant to how another bidder evaluates the rights being auctioned.
Works like [18] and [12] lay the foundation for rigorous mathematical research
of such settings, yet many key questions still remain unanswered.

For concreteness, consider an auction with a single item for sale (our main
setting of interest). In the interdependent values model, every bidder
$i\in[n]$ has a privately-known signal $s_{i}$, and her value $v_{i}$ is a
(publicly-known) function of all the signals, i.e.,
$v_{i}=v_{i}(s_{1},s_{2},...,s_{n})$. Thus, in this model, not only the
auctioneer is in the dark regarding a bidder’s willingness to pay for the item
being auctioned; so is the bidder herself (who knows $s_{i}$ and
$v_{i}(\cdot)$ but not $s_{-i}$)!

This stark difference from the standard, independent private values (IPV)
model creates a big gap in our ability to perform seemingly-simple auction
design tasks. Arguably the most fundamental such task is _truthful welfare
maximization_. For IPV, the truthful welfare-maximizing Vickrey auction [17]
is a pillar of mechanism design (e.g., it has many practical applications and
is usually the first auction taught in a mechanism design course). But with
interdependence, welfare and truthfulness are no longer perfectly compatible:
Consider two bidders reporting their signals $s_{1},s_{2}$ to the auction,
which allocates the item to the highest-value bidder according to these
reports; if the valuation functions $v_{1},v_{2}$ are such that bidder 1 wins
when $s_{1}=0$ but loses when $s_{1}=1$, this natural generalization of
Vickrey to interdependence is non-monotone and thus non-truthful. This is the
case, for example, if $v_{1}=1+s_{1}$ and $v_{2}=H\cdot s_{1}$ for $H>2$ (see
[5, Example 1.2]).

The classic economics literature addressed this challenge by introducing a
somewhat stringent condition on the valuation functions called “single-
crossing”, which ensures truthfulness of the natural generalization of Vickrey
(in particular, single-crossing is violated by $v_{1}=1+s_{1},v_{2}=H\cdot
s_{1}$). Recently, a breakthrough result of Eden et al. [5] took a different
approach: For simplicity consider _binary_ signals – e.g., “oil” or “no oil”
in an auction for drilling rights. Formally, $s_{i}\in\\{0,1\\}$ (we focus on
the binary case throughout the paper). The valuations are now simply _set
functions_ over the signals, objects for which a rich mathematical theory
exists. Eden et al. applied a _submodularity_ assumption to these set
functions (in particular, submodularity holds for $v_{1}=1+s_{1}$ and
$v_{2}=H\cdot s_{1}$). Under such submodularity over the signals (_SOS_), they
shifted focus from maximizing welfare to _approximating_ the optimal welfare.
While they showed that no truthful mechanism can achieve a better
approximation factor than 2 (guaranteeing more than half the optimal welfare),
they constructed a truthful randomized mechanism that achieves a
4-approximation (guaranteeing at least a quarter of the optimal welfare). The
gap between $2$ and $4$ was left as an open problem.

####  1.0.1 Our Results and Organization.

In this work we resolve the above open problem of [5] for binary signals. More
precisely, we show that in the binary signal case there exists a truthful
randomized mechanism that achieves a 2-approximation to the optimal welfare
(for a formal statement see Theorem 3.1). Our result holds for any number $n$
of bidders, and is constructive – that is, we give an algorithm that gets the
$n$ valuation functions as input, and returns the mechanism as output.111The
algorithm runs in time polynomial in its input size, which consists of set
functions over $n$ elements and so is exponential in $n$.

The fact that our mechanism is randomized is unsurprising given another result
of Eden et al. [5], who show that a deterministic mechanism cannot achieve a
constant approximation to the optimal welfare even with SOS. This result is in
fact proved with the above example of $v_{1}=1+s_{1},v_{2}=H\cdot s_{1}$ and
$s_{i}\in\\{0,1\\}$. An interesting corollary of our construction is that a
$2$-approximation is achievable by a mechanism that is only “slightly”
randomized – the only allocation probabilities it uses are $0$ and
$\frac{1}{2}$.

Our algorithm is arguably quite simple and streamlined – for every signal
profile it searches for a feasible pair of bidders whose aggregate value
exceeds that of the highest bidder, and randomly allocates the item among
these two (this explains the factor of 2 in the approximation guarantee). Only
if no such pair exists, the item is randomly either allocated to the highest
bidder or left unallocated. To maintain monotonicity, the algorithm
_propagates_ allocation probabilities to neighboring signal profiles. Despite
its relative simplicity, the algorithm requires careful analysis, which in
particular relies on new properties of collections of submodular functions
(Section 4.2). The main technical challenge is in showing that the
2-approximation guarantee holds despite the propagations.

Example. To illustrate our method, consider again the above example of
$v_{1}=1+s_{1}$ and $v_{2}=H\cdot s_{1}$ where $s_{i}\in\\{0,1\\}$. Our
algorithm returns a randomized allocation rule that gives the item to bidder
$1$ with probability $\frac{1}{2}$ if $s_{1}=0$, and randomly allocates it to
one of the two bidders if $s_{1}=1$.222Our algorithm has two iterations: At
$s_{1}=0$, an appropriate pair is not found and so the highest bidder (bidder
$1$) wins the item with probability $\frac{1}{2}$, which is propagated forward
to this bidder at $s_{1}=1$. At $s_{1}=1$, an appropriate pair is again not
found and so the highest bidder (bidder $2$) wins the item with probability
$\frac{1}{2}$. This allocation rule is monotone (unlike the natural
generalization of Vickrey), and leads to a truthful mechanism with a
2-approximation guarantee.

Extensions. In Appendix 0.C we extend our main result to beyond single-item
settings, namely to general single-parameter settings in which the set of
winning bidders must satisfy a _matroid_ constraint [15]. As in [5], we can
also extend our positive results from welfare to _revenue_ maximization using
a reduction of [4].

Organization. After presenting the preliminaries in Section 2, we state our
main theorem and give an overview of our algorithm in Section 3. The analysis
appears in Section 4 and Appendix 0.B. Section 5 summarizes with future
directions. Appendix 0.A includes the algorithm and running time, Appendix 0.C
the extension to matroids and Appendix 0.D our results for non-binary signals.

####  1.0.2 Additional Related Work.

Interdependent values have been extensively studied in the economic literature
(see, e.g., [3, 8, 11, 1]). In computer science, most works to date focus on
the objective of maximizing revenue [2, 16, 10, 4]. The work of [4] considers
welfare maximization with a relaxed _$c$ -single-crossing_ assumption, where
parameter $c\geq 1$ measures how close the valuations are to satisfying
classic single-crossing. This work achieves a $c$-approximation for settings
with binary signals. Their mechanisms also use propagations but otherwise are
quite different than ours. The work of [7] also focuses on welfare but does
not assume single-crossing; instead it partitions the bidders into $\ell$
“expertise groups” based on how their signal can impact the values for the
good, and using clock auctions achieves approximation results parameterized by
$\ell$ (and by the number of possible signals). The main paper our work is
inspired by is [5]. It introduces the _Random Sampling Vickrey auction_ ,
which by excluding roughly half of the bidders achieves a $4$-approximation to
the optimal welfare for single-parameter, downward-closed SOS environments.
The authors also show positive results for combinatorial SOS environments
under various natural constraints. Finally, [6] also study welfare
maximization in single- and multi-parameter environments but by simple, non-
truthful parallel auctions.

##  2 Setting

Signals. As our main setting of interest we consider single-item auctions with
$n$ bidders. Every bidder $i$ has a binary _signal_ $s_{i}\in\\{0,1\\}$, which
encompasses the bidder’s private bit of information about the item. It is
convenient to identify a signal profile $s=(s_{1},s_{2},...,s_{n})$ with its
corresponding set $S=\\{i\mid s_{i}=1\\}$ (by treating $s_{i}$ as an indicator
of whether $i\in S$).

Values. The bidders have _interdependent values_ for the item being auctioned:
Every bidder $i$’s value $v_{i}$ is a non-negative function of all bidders’
signals, i.e., $v_{i}=v_{i}(s_{1},s_{2},...,s_{n})\geq 0$. We adopt the
standard assumption that the valuation function $v_{i}$ is weakly increasing
in each coordinate and strongly increasing in $s_{i}$. Using the set notation
we also write $v_{i}=v_{i}(S)$.333This notation is not to be confused with the
value for a _set of items_ $S$; in our model there is a _single_ item, and a
bidder’s interdependent value for it is determined by the _set of signals_ ,
i.e., which subset of signals is “on”. This makes $v_{i}(\cdot)$ a monotone
_set function_ over subsets of $[n]$.

Who knows what. A setting is summarized by the valuation functions
$v_{1},\dots,v_{n}$, which are publicly known (as is the signal domain
$\\{0,1\\}$). The instantiation of the signals is private knowledge, that is,
signal $s_{i}$ is known only to bidder $i$.

####  2.0.1 SOS Valuations.

The term _SOS valuations_ was coined by Eden et al. [5] to describe
interdependent valuation functions that are _submodular over the signals_ (see
also [2, 4, 13]).444As mentioned above, submodularity over signals is not to
be confused with submodularity over items in combinatorial auctions. With
binary signals, valuations are SOS if $v_{i}(\cdot)$ is a submodular set
function for every $i\in[n]$.

######  Definition 1 (Submodular set function)

A set function $v_{i}:2^{[n]}\rightarrow\mathbb{R}$ is submodular if for every
$S,T\subseteq[n]$ such that $S\subseteq T$ and $i\in[n]\setminus T$ it holds
that $v_{i}(S\cup\\{i\\})-v_{i}(S)\geq v_{i}(T\cup\\{i\\})-v_{i}(T)$.

A weaker definition that will also be useful for us is subadditivity. Every
submodular set function is subadditive, but not vice versa.

######  Definition 2 (Subadditive set function)

A set function $v_{i}:2^{[n]}\rightarrow\mathbb{R}$ is subadditive if for
every $S,T\subseteq[n]$ is holds that $f(S)+f(T)\geq f(S\cup T)$.

Given a set function $v_{i}$ and a subset $S\subseteq[n]$, we use
$v_{i}(\cdot\mid S)$ to denote the following set function: $v_{i}(T\mid
S)=v_{i}(T\cup S)-v_{i}(S)$ for every $T\subseteq[n]$. It is known that
submodularity of $v_{i}$ implies subadditivity of $v_{i}(\cdot\mid S)$:

######  Proposition 1 (e.g., Lemma 1 of [9])

If $v_{i}$ is submodular then $v_{i}(\cdot\mid S)$ is subadditive for every
subset $S\subseteq[n]$.

We refer to an ordering $S_{1},S_{2},\dots,S_{2^{n}}$ of all subsets of the
ground set of elements $[n]$ as _inclusion-compatible_ if for every pair
$S_{k},S_{\ell}$ such that $S_{k}\subset S_{\ell}$, it holds that $k<\ell$
(the included set is before the including one in the ordering).

Notation. Consider a set function $v_{i}$ and two elements $j,k\in[n]$. For
brevity we often write $v_{i}(j)$ for $v_{i}(\\{j\\})$, and $v_{i}(jk)$ for
$v_{i}(\\{j,k\\})$.

###  2.1 Auctions with Interdependence

Randomized mechanisms. Due to strong impossibility results for deterministic
mechanisms [5], we focus on randomized mechanisms as follows: A randomized
mechanism $M=(x,p)$ for interdependent values is a pair of allocation rule $x$
and payment rule $p$. The mechanism solicits signal reports from the bidders,
and maps a reported signal profile $s$ to non-negative allocations
$x=(x_{1},...,x_{n})$ and expected payments $p=(p_{1},...,p_{n})$, such that
the item is _feasibly_ allocated to bidder $i$ with probability $x_{i}$
(feasibility means $\sum_{i=1}^{n}{x_{i}(s)}\leq 1$).

Truthfulness. With interdependence, it is well-established that the
appropriate notion of truthfulness is _ex post IC_ (incentive compatibility)
and _IR_ (individual rationality). Mechanism $M$ is ex post IC-IR if the
following holds for every bidder $i$, true signal profile $s$ and reported
signal $s^{\prime}_{i}$: Consider bidder $i$’s expected utility when the
others truthfully report $s_{-i}$:

$x_{i}(s_{-i},s^{\prime}_{i})v_{i}(s)-p_{i}(s_{-i},s^{\prime}_{i});$

then this expected utility is non-negative and maximized by truthfully
reporting $s^{\prime}_{i}=s_{i}$.555Note the difference from _dominant-
strategy_ IC, in which this guarantee should hold no matter how other bidders
report.

Similarly to independent private values, the literature on interdependent
values provides a characterization of ex post IC-IR mechanisms – as the class
of mechanisms with a _monotone_ allocation rule $x$. Allocation rule $x$
satisfies monotonicity if for every signal profile $s$, bidder $i$ and
$\delta\geq 0$, increasing $i$’s signal report by $\delta$ while holding other
signals fixed increases $i$’s allocation probability:

$x_{i}(s_{-i},s_{i})\leq x_{i}(s_{-i},s_{i}+\delta).$

The characterization also gives a payment formula which, coupled with the
monotone allocation rule, results in an ex post IC-IR mechanism. In more
detail, the expected payment of bidder $i$ is achieved by finding her critical
signal report and plugging it into her valuation function while holding
others’ signals fixed (see [16] for a comprehensive derivation of the
payments).

Welfare maximization. Our objective in this work is to design ex post IC-IR
mechanisms for interdependent values that maximize social welfare. For a given
setting and true signal profile $s$, the optimal welfare
$\operatorname{OPT}(s)$ is achieved by giving the item to the bidder with the
highest value, i.e., $\operatorname{OPT}(s)=\max_{i}\\{v_{i}(s)\\}$. Given a
randomized ex post IC-IR mechanism $M=(x,p)$ for this setting,
$\operatorname{ALG}(s)$ is its welfare in expectation over the internal
randomness, i.e., $\operatorname{ALG}(s)=\sum_{i=1}^{n}{x_{i}(s)v_{i}(s)}.$ We
say mechanism $M$ achieves a $c$-approximation to the optimal welfare for a
given setting if for every signal profile $s$,
$\operatorname{ALG}(s)\geq\frac{1}{c}\operatorname{OPT}(s)$ (note that the
required approximation guarantee here is “universal”, i.e., should hold
individually for every $s$). Since Eden et al. [5] devise a setting for which
no randomized ex post IC-IR mechanism can achieve better than a
$2$-approximation, we aim to design mechanisms that achieve a
$c$-approximation to the optimal welfare where $c\geq 2$ (the closer to $2$
the better).

##  3 Main Result and Construction Overview

Our main result is the following:

###### Theorem 3.1

For every single-item auction setting with $n$ bidders, binary signals and
interdependent SOS valuations, there exists an ex post IC-IR mechanism that
achieves a $2$-approximation to the optimal welfare.

Our proof of Theorem 3.1 is constructive – we design an algorithm (Algorithm
1) that gets as input the valuation functions $v_{1},\dots,v_{n}$, and outputs
an allocation rule $x$. Note that the main goal of the algorithm is to
establish existence. Rule $x$ is guaranteed to be both feasible and monotone.
Thus, coupled with the appropriate expected payments $p$ (based on critical
signal reports), it constitutes an ex post IC-IR mechanism $M=(x,p)$. The main
technical challenge is in showing that mechanism $M$ has the following welfare
guarantee: for every signal profile $s$,
$\operatorname{ALG}(s)\geq\frac{1}{2}\operatorname{OPT}(s)$. We prove this
approximation ratio and establish $x$’s other properties like monotonicity in
Section 4. The algorithm itself appears in Appendix 0.A; we now give an
overview of its construction.

###  3.1 Construction Overview

In this section we give an overview of Algorithm 1. The algorithm maintains an
“allocation table” with rows corresponding to the $n$ bidders, and columns
corresponding to subsets $S\subseteq[n]$. At termination, column $S$ will
represent the allocation rule $x(S)$, with entry $(i,S)$ encoding $x_{i}(S)$.
For clarity of presentation the encoding is via colors: At initiation, all
entries of the table are colored white to indicate they have not yet been
processed. During its run, the algorithm colors each entry $(i,S)$ of the
table either red or black. Once a cell has been colored red or black, its
color remains invariant until termination. The colors represent allocation
probabilities as follows:

  * •

red = bidder $i$ gets the item with probability $\frac{1}{2}$ at signal
profile $S$;

  * •

black = $i$ does not get the item at $S$ (i.e., gets the item with probability
$0$).

As an interesting consequence, the allocation rule achieving the
2-approximation guarantee of Theorem 3.1 uses only two allocation
probabilities, namely $\frac{1}{2}$ and $0$. Note that for feasibility, no
more than two entries in a single column should be colored red, and the
remaining entries should be colored black.

We now explain roughly how the colors are determined by the algorithm.
Consider an inclusion-compatible ordering of all subsets of $[n]$. The
algorithm iterates over the ordered subsets, with $S$ representing the current
subset. We say bidder $i$ _can be colored red at iteration $S$_ if at the
beginning of the iteration, $(i,S)$ is colored either white or red. We define
a notion of _favored bidder(s) at iteration $S$_ – these are the ones the
algorithm “favors” as winners of the item given signal profile $S$, and so
will color them red at $S$. First, if there is a pair of bidders $i\neq j$ for
which the following conditions all hold, we say they are favored at iteration
$S$ with Priority 1:

  1. 1.

Bidder $i$ and $j$’s signals both belong to $S$ (i.e., $s_{i}=s_{j}=1$);

  2. 2.

Bidders $i$ and $j$ can both be colored red at iteration $S$;

  3. 3.

No other bidder $k\neq i,j$ is colored red at the beginning of iteration $S$;

  4. 4.

The sum of values $v_{i}(S)+v_{j}(S)$ is at least $\operatorname{OPT}(S)$
(recall that $\operatorname{OPT}(S)$ is the highest value of any bidder for
the item given signal profile $S$).

If such a pair does not exist, but there exists a bidder $i$ who satisfies the
following alternative conditions, we say $i$ is favored at iteration $S$ with
Priority 2:

  1. 1.

Bidder $i$ can be colored red at iteration $S$;

  2. 2.

The value $v_{i}(S)$ equals $\operatorname{OPT}(S)$.

Our main technical result in the analysis of the algorithm is to show that,
unless at the beginning of iteration $S$ two bidders are already colored red,
then one of the two cases above must hold. That is, in every iteration $S$
with no two reds, there is always either a favored pair with Priority 1, or a
single favored bidder with Priority 2. Assuming this holds, the algorithm
proceeds as follows. At iteration $S$ it checks whether two bidders are
already red, and if so continues to the next iteration. Otherwise, it colors
the favored bidder(s) red by priority, and all other bidders black. The
algorithm then performs _propagation_ to other subsets $S^{\prime}$ in order
to maintain monotonicity of the allocation rule (the term propagation was
introduced in our context by [5]):

  * •

If bidder $i\notin S$ is colored red at subset $S$, then red is propagated
_forward_ to bidder $i$ at subset $S^{\prime}=S\cup\\{i\\}$.

  * •

If bidder $i\in S$ is colored black at subset $S$, then black is propagated
_backward_ to bidder $i$ at subset $S^{\prime}=S\setminus\\{i\\}$.

This completes the overview of our construction.

##  4 Proof of Theorem 3.1

We begin with a simple but useful observation:

###### Observation 1

Consider a subset $S\subseteq[n]$ and $i\notin S$. If during iteration $S$
bidder $i$ is colored red then $v_{i}(S)=\operatorname{OPT}(S)$.

###### Proof

The algorithm colors a bidder with a low signal red only if this bidder has
Priority 2, and in this case her value must be highest among all bidders.

We now prove our main theorem, up to three lemmas which we prove in Sections
4.1-4.3, respectively. Section 4.2 also develops a necessary tool for the
proof in Section 4.3.

######  Proof (Theorem 3.1)

We show that Algorithm 1 returns an allocation rule that is feasible,
monotone, and achieves a $2$-approximation to the optimal welfare. For such an
allocation rule there exist payments that result in an ex post IC-IR mechanism
(see Section 2.1), establishing the theorem.

Let $x$ be the allocation rule returned by Algorithm 1. We first show $x$ is
_feasible_. That is, for every subset $S\subseteq[b]$, the algorithm colors
$(i,S)$ either red or black for every bidder $i$, and at most two bidders are
colored red in column $S$. To show this we invoke Lemma 1 below, by which
Algorithm 1 never reaches one of its error lines. Given that there are no
errors, observe that the algorithm goes over all subsets, and for every subset
$S\subseteq[n]$ either (i) skips to the next subset (if two bidders are
already red), or (ii) finds a Priority 1 pair or Priority 2 bidder and colors
them red. Indeed, by Lemma 4, if (i) does not occur then (ii) is necessarily
successful. Once a Priority 1 pair or Priority 2 bidder is found, the rest of
the column is colored black. Furthermore, once any two bidders in a column are
colored red, the rest of the column is colored black. This establishes
feasibility.

We now show $x$ is _monotone_. Since the only allocation probabilities $x$
assigns are $\frac{1}{2}$ and $0$ (and one of these is always assigned), it is
sufficient to show that for every $S\subseteq[n]$ and $i\notin S$, if
$x(i,S)=\frac{1}{2}$ then $x(i,S\cup\\{i\\})=\frac{1}{2}$. This holds since
every time the algorithm calls ColorRed to color $(i,S)$, it propagates the
color red forward to $(i,S\cup\\{i\\})$ as well.

It remains to show that $x$ achieves a $2$-approximation to the optimal
welfare. By definition of Priority 1 and Priority 2, if such bidders are
colored red then a $2$-approximation is achieved for the corresponding signal
profiles. It remains to consider signal subsets $S$ for which at the beginning
of iteration $S$, two cells $i,j$ in the column are already colored red. These
reds propagated forward from $v_{i}(S\setminus\\{i\\})$ and
$v_{j}(S\setminus\\{j\\})$. Let $v_{k}(S)$ be the highest value at $S$. By
Observation 1, $v_{i}(S\setminus\\{i\\})$ and $v_{j}(S\setminus\\{j\\})$ are
highest at $S\setminus\\{i\\}$ and $S\setminus\\{j\\}$, respectively:

$\displaystyle v_{i}(S\setminus\\{i\\})$ $\displaystyle\geq
v_{k}(S\setminus\\{i\\});$ $\displaystyle v_{j}(S\setminus\\{j\\})$
$\displaystyle\geq v_{k}(S\setminus\\{j\\}).$

Applying Lemma 2 to the above inequalities, it cannot simultaneously hold that
$v_{k}(S)>v_{i}(S)+v_{j}(S)$. So $v_{i}(S)+v_{j}(S)\geq v_{k}(S)$, and the
approximation guarantee holds, completing the proof. ∎

###  4.1 No errors

In this section we show that the algorithm runs without producing an error.

######  Lemma 1 (No errors)

Algorithm 1 never reaches error lines 35, 41 or 55.

###### Proof

We first establish that ColorRed is only called on white or red cells (so line
35 is never reached). In Algorithm 1’s main procedure Allocate, sub-procedure
ColorRed is called on cells that correspond to bidder $b$ of Priority 1 or
Priority 2 (see lines 16-17 and 25), i.e., it is called only after verifying
$b$ is not colored black (lines 13 and 23). Sub-procedure ColorRed also calls
itself (line 50), after being called on $S$ from Allocate; in this case the
color red is being propagated forward from $S$ to $S\cup\\{b\\}$. Assume for
contradiction $(b,S\cup\\{b\\})$ is already colored black. This means
ColorBlack was called on $(b,S\cup\\{b\\})$. But then due to backward
propagation, $(b,S)$ would already be black too, in contradiction to ColorRed
being called on it from Allocate.

We now show ColorBlack is only called on white or black cells (so line 55 is
never reached). Sub-procedure ColorBlack is called from Allocate (line 27)
inside a condition verifying the current color is white. ColorBlack is also
called from ColorRed at (line 46); in this case the current subset $S$ already
has two red bidders, on which ColorBlack is _not_ called, and there can never
be more than two reds due to the condition at line 41 of ColorRed. Finally,
ColorBlack also calls itself (line 62), after being called on $S$ from
Allocate or from ColorRed; in this case the color black is being propagated
backward from $S\cup\\{b\\}$ to $S$. Assume for contradiction $(b,S)$ is
already colored red. This means ColorRed was called on $(b,S)$. But then due
to forward propagation, $(b,S\cup\\{b\\})$ would already be red too, in
contradiction to ColorBlack being called on it from Allocate or from ColorRed.

It remains to show that Algorithm 1 never reaches error line 41, i.e., never
attempts to color more than two bidders red for a given subset $S$. Note that
such an attempt will not be made from Allocate due to the conditions at lines
8 and 14. Assume for contradiction it happens because of forward propagation
from $S$ to $S\cup\\{b\\}$. Then there are two bidders $b_{1}\neq b_{2}$
distinct from $b$ who are already colored red for signal profile
$S\cup\\{b\\}$ at the beginning of iteration $S$. This means that all other
bidders including $b$ are colored black for signal profile $S\cup\\{b\\}$ at
the beginning of iteration $S$ (see lines 44-48, in which after every time a
bidder is colored red the algorithm checks if there are now two red bidders
and if so colors all other bidders black). But then $(b,S\cup\\{b\\})$ is
black when Algorithm 1 attempts to color it red during forward propagation,
contradiction. ∎

###  4.2 Properties of SOS Valuations

In this section we state and prove two lemmas for SOS valuations. The first is
used in the proof of Theorem 3.1, and the second is the workhorse driving the
proof in Section 4.3 that either Priority 1 or Priority 2 always hold. Very
roughly, the first lemma (Lemma 2) states that if bidders $i,j$ have higher
values than bidder $k$ when their own signals are low, then bidder $k$’s value
cannot exceed their sum when their signals are high. The second lemma (Lemma
3) is more complex, and to give intuition for what it states we provide a
visualization in Figures 1-5 (we use a similar visualization to sketch our
main proof in Section 4.3). The proof is by induction and is deferred to
Appendix 0.B.1.

###### Lemma 2

Consider a subset $S^{\prime}\subseteq[n]$ and three bidders $i,j,k$ (not
necessarily distinct) with SOS valuations over binary signals; let
$S^{*}=S^{\prime}\cup\\{i,j\\}$. If the following three inequalities hold
simultaneously then they all hold with equality:

  * •

$v_{i}(S^{*}\setminus\\{i\\})\geq v_{k}(S^{*}\setminus\\{i\\})$;

  * •

$v_{j}(S^{*}\setminus\\{j\\})\geq v_{k}(S^{*}\setminus\\{j\\})$;

  * •

$v_{k}(S^{*})\geq v_{i}(S^{*})+v_{j}(S^{*})$.

###### Proof

Define $u_{i}(\cdot)=v_{i}(\cdot\mid S^{\prime})$ for every $i\in[n]$. Using
this notation, to prove the lemma we need to show that if the following three
inequalities hold simultaneously, they must all hold with equality:

  * •

$u_{i}(j)+v_{i}(S^{\prime})\geq u_{k}(j)+v_{k}(S^{\prime})$;

  * •

$u_{j}(i)+v_{j}(S^{\prime})\geq u_{k}(i)+v_{k}(S^{\prime})$;

  * •

$u_{k}(ij)+v_{k}(S^{\prime})\geq
u_{i}(ij)+v_{i}(S^{\prime})+u_{j}(ij)+v_{j}(S^{\prime})$.

Assume the inequalities hold. Summing them and simplifying we get

$\displaystyle u_{i}(j)+u_{j}(i)+u_{k}(ij)\geq
u_{k}(j)+u_{k}(i)+v_{k}(S^{\prime})+u_{i}(ij)+u_{j}(ij).$ (1)

We now use the fact that $u_{k}(\cdot)$ is subadditive (Proposition 1), so
$u_{k}(ij)\leq u_{k}(j)+u_{k}(i)$. Thus by Inequality (1),

$u_{i}(j)+u_{j}(i)\geq v_{k}(S^{\prime})+u_{i}(ij)+u_{j}(ij).$

By monotonicity of set functions $u_{i}$ and $u_{j}$, $u_{i}(j)\leq u_{i}(ij)$
and $u_{j}(i)\leq u_{j}(ij)$. We conclude that $v_{k}(S^{\prime})\leq 0$,
which can hold only with equality. But this equality would be violated if one
of the three inequalities was strict, completing the proof.∎

###### Lemma 3

Consider a subset $S^{\prime}\subseteq[n]$ and $3+\ell_{1}+\ell_{2}+\ell_{3}$
bidders $E=\\{i,j,k$,
$t_{1},\dots,t_{\ell_{1}}$,$t_{1}^{\prime},\dots,t_{\ell_{2}}^{\prime}$,$t^{\prime\prime}_{1},\dots,t^{\prime\prime}_{\ell_{3}}\\}$
(not necessarily distinct) with SOS valuations over binary signals. Let
$t_{\ell_{1}+1}=k$,
$t_{\ell_{2}+1}^{\prime}=k,t^{\prime\prime}_{\ell_{3}+1}=i$, and
$S^{*}=S^{\prime}\cup E$. If the following $3+\ell_{1}+\ell_{2}+\ell_{3}$
inequalities hold simultaneously then they all hold with equality:

  * •

$v_{i}(S^{*}\setminus\\{i\\})\geq
v_{t_{1}}(S^{*}\setminus\\{i\\})+v_{j}(S^{*}\setminus\\{i\\})$;

  * •

$\forall h\in[\ell_{1}]:v_{t_{h}}(S^{*}\setminus\\{i,t_{1},...,t_{h}\\})\geq
v_{t_{h+1}}(S^{*}\setminus\\{i,t_{1},...,t_{h}\\})+v_{j}(S^{*}\setminus\\{i,t_{1},...,t_{h}\\})$;

  * •

$v_{j}(S^{*}\setminus\\{j\\})\geq
v_{t_{1}^{\prime}}(S^{*}\setminus\\{j\\})+v_{i}(S^{*}\setminus\\{j\\})$;

  * •

$\forall
h\in[\ell_{2}]:v_{t_{h}^{\prime}}(S^{*}\setminus\\{j,t_{1}^{\prime},...,t_{h}^{\prime}\\})\geq
v_{t_{h+1}^{\prime}}(S^{*}\setminus\\{j,t_{1}^{\prime},...,t_{h}^{\prime}\\})+v_{i}(S^{*}\setminus\\{j,t_{1}^{\prime},...,t_{h}^{\prime}\\})$;

  * •

$v_{k}(S^{*}\setminus\\{k\\})\geq
v_{t_{1}^{\prime\prime}}(S^{*}\setminus\\{k\\})+v_{j}(S^{*}\setminus\\{k\\})$;

  * •

$\forall
h\in[\ell_{3}]:v_{t_{h}^{\prime\prime}}(S^{*}\setminus\\{k,t_{1}^{\prime\prime},...,t_{h}^{\prime\prime}\\})\geq
v_{t_{h+1}^{\prime\prime}}(S^{*}\setminus\\{k,t_{1}^{\prime\prime},...,t_{h}^{\prime\prime}\\})+v_{j}(S^{*}\setminus\\{k,t_{1}^{\prime\prime},...,t_{h}^{\prime\prime}\\})$.

### Visualization of Lemma 3.

Consider the case $\ell_{1}=\ell_{2}=\ell_{3}=0$. The first inequality of
Lemma 3 in this case, using that $t_{1}=t_{\ell_{1}+1}$ (which equals $k$ by
definition), is:

$v_{i}(S^{*}\setminus\\{i\\})\geq
v_{k}(S^{*}\setminus\\{i\\})+v_{j}(S^{*}\setminus\\{i\\}).$ (2)

We introduce a visualization of Inequality (2) as the $2\times n$ “block”
shown in Fig. 1. The columns of the block correspond to the bidders. The first
row of the block represents which bidders participate in the inequality (in
this case $i,j,k$), with the bidder on the greater (left) side of the
inequality depicted in striped red (in this case $i$); the second row
represents the signal set in the inequality (in this case
$S^{*}\setminus{i}$), with the signals not in the set depicted in white (in
this case $i$).

Figure 1: Visualization of Inequality (2).

Figure 2: Visualization of the inequalities of Lemma 3 for
$\ell_{1}=\ell_{2}=\ell_{3}=0$.

We can use the above visualization to depict all inequalities of Lemma 3. For
the case that $\ell_{1}=\ell_{2}=\ell_{3}=0$, these are shown in Fig. 2.
Consider now the case $\ell_{1}=\ell_{2}=\ell_{3}=1$, with the following
inequalities (among others):

$\displaystyle v_{i}(S^{*}\setminus\\{i\\})$ $\displaystyle\geq$
$\displaystyle v_{j}(S^{*}\setminus\\{i\\})+v_{t_{1}}(S^{*}\setminus\\{i\\});$
$\displaystyle v_{t_{1}}(S^{*}\setminus\\{i,t_{1}\\})$ $\displaystyle\geq$
$\displaystyle
v_{j}(S^{*}\setminus\\{i,t_{1}\\})+v_{k}(S^{*}\setminus\\{i,t_{1}\\}).$

In this case we have a fourth bidder $t_{1}$ who “bridges” between $i,j,k$.
Instead of an inequality requiring that $v_{i}\geq v_{j}+v_{k}$ directly, here
it is required that $v_{i}\geq v_{j}+v_{t_{1}}$, and in turn $v_{t_{1}}\geq
v_{j}+v_{k}$ but with a different set of signals. The full system of
inequalities for this case (with $6$ inequalities) appears in Fig. 3.

Figure 3: Visualization of the inequalities of Lemma 3 for
$\ell_{1}=\ell_{2}=\ell_{3}=1$.

More generally, Lemma 3 holds for any number of “bridge” bidders. The general
case is shown in Fig. 5 in Appendix 0.B.1.

###  4.3 When Are Priorities 1 or 2 Guaranteed

In this section we prove the following lemma (some details of the proof are
deferred to Appendix 0.B.1):

###### Lemma 4

Assume Algorithm 1 runs on $n$ bidders with SOS valuations over binary
signals. Then for every $S\subseteq[n]$, if at the beginning of iteration $S$
there are less than two red bidders, either Priority 1 or Priority 2 must
hold.

We begin with two observations that will be useful in the proof of Lemma 4.

###### Observation 2

If at the beginning of iteration $S$ no bidder is colored red, and during the
iteration bidder $i$ whose signal is low ($i\notin S$) is colored red, then
for every pair $j,k\in S$, $v_{i}(S)\geq v_{j}(S)+v_{k}(S)$.

###### Proof

Assume for contradiction that $v_{j}(S)+v_{k}(S)>v_{i}(S)$, then since $j,k$
both have high signals and can be colored red at iteration $S$, they have
Priority 1 and should be colored in place of bidder $i$, contradiction. ∎

###### Observation 3

If at the beginning of iteration $S$ only bidder $t$ whose signal is high
($t\in S$) is colored red, and during the iteration bidder $i$ whose signal is
low ($i\notin S$) is colored red, then for every $j\in S$, $v_{i}(S)\geq
v_{j}(S)+v_{t}(S)$.

###### Proof

Assume for contradiction that $v_{j}(S)+v_{t}(S)>v_{i}(S)$, then since $j,t$
both have high signals and can be colored red at iteration $S$ ($t$ is already
red and $j$ can be colored red since there are no other reds besides $t$),
they have Priority 1 and should be colored in place of bidder $i$,
contradiction. ∎

We can now prove our main lemma; missing details appear in Appendix 0.B.1.

######  Proof (Lemma 4, sketch)

Fix an iteration $S$ with $<2$ red bidders at its beginning. By _highest
bidder_ we mean the bidder whose value at $S$ equals $\operatorname{OPT}(S)$.
We split the analysis into cases; the most challenging cases technically are
when the highest bidder is colored black in column $S$, and there are either
no red cells or a single red cell in this column at the beginning of the
iteration. Here we focus on the first among these cases and remark at the end
how to treat the second, showing in both why a Priority 1 pair exists in
column $S$. The remaining cases are addressed in Appendix 0.B.1.

##### Case 1: No red cells.

Assume that at the beginning of iteration $S$, the highest bidder is colored
black and there are no red cells in column $S$. Denote the highest bidder by
$k$ and observe that its color must have propagated backward from
$(k,S\cup\\{k\\})$; let $S^{*}=S\cup\\{k\\}$. In column $S^{*}$ there must
therefore be two red bidders, whom we refer to as $i$ and $j$, due to which
$k$ is colored black in this column. Red must have propagated forward to
column $S^{*}$ from $S^{*}\setminus\\{i\\}$ and $S^{*}\setminus\\{j\\}$. Fig.
4 shows the allocation status of the relevant bidders at the beginning of
iteration $S$ for subsets
$S,S^{*},S^{*}\setminus\\{i\\},S^{*}\setminus\\{j\\}$ – we use the same
visualization as in Section 4.2, but with colors in the first row representing
those set by the algorithm and arrows representing propagations.

Figure 4: Colorings at $S,S^{*}$, $S^{*}\setminus\\{i\\}$ and
$S^{*}\setminus\\{j\\}$ given that $(k,S)$ is black.

Towards establishing existence of a Priority 1 pair in column $S$, consider
first the case in which the following two conditions hold:

  1. 1.

At the beginning of iteration $S^{*}\setminus\\{i\\}$, no cells in that column
are red;

  2. 2.

At the beginning of iteration $S^{*}\setminus\\{j\\}$, no cells in that column
are red.

By Observation 2,

$\displaystyle v_{i}(S^{*}\setminus\\{i\\})$ $\displaystyle\geq$
$\displaystyle v_{j}(S^{*}\setminus\\{i\\})+v_{k}(S^{*}\setminus\\{i\\});$ (3)
$\displaystyle v_{j}(S^{*}\setminus\\{j\\})$ $\displaystyle\geq$
$\displaystyle v_{i}(S^{*}\setminus\\{j\\})+v_{k}(S^{*}\setminus\\{j\\}).$ (4)

If both (3) and (4) hold, by Lemma 3 with $\ell_{1}=\ell_{2}=\ell_{3}=0$ it
cannot simultaneously hold that $v_{k}(S)>v_{i}(S)+v_{j}(S)$ (see Fig. 2 and
related text). Thus $v_{i}(S)+v_{j}(S)\geq v_{k}(S)$, and pair $i,j$ has
Priority 1.

Now consider the case in which one of the two conditions does not hold,
w.l.o.g. Condition (1). That is, at the beginning of iteration
$S^{*}\setminus\\{i\\}$, a bidder $t_{1}$ is colored red. (There is only one
such bidder since we know bidder $i$ cannot be red at the beginning of that
iteration – no forward propagation as $i\notin S^{*}\setminus\\{i\\}$ – and
that $i$ is colored red during the iteration.) By Observation 3,

$v_{i}(S^{*}\setminus\\{i\\})\geq
v_{j}(S^{*}\setminus\\{i\\})+v_{t_{1}}(S^{*}\setminus\\{i\\}).$ (5)

Since $(t_{1},S^{*}\setminus\\{i\\})$ is red at the beginning of iteration
$S^{*}\setminus\\{i\\}$, the color red necessarily propagated forward from
$S^{*}\setminus\\{i,t_{1}\\}$. If Condition (1) now holds for
$S^{*}\setminus\\{i,t_{1}\\}$ then by Observation 2,

$v_{t_{1}}(S^{*}\setminus\\{i,t_{1}\\})\geq
v_{j}(S^{*}\setminus\\{i,t_{1}\\})+v_{k}(S^{*}\setminus\\{i,t_{1}\\})$ (6)

If Inequalities (4)-(6) hold simultaneously, then by Lemma 3 with
$\ell_{1}=1,\ell_{2}=\ell_{3}=0$ we can again conclude that
$v_{i}(S)+v_{j}(S)\geq v_{k}(S)$, and pair $i,j$ has Priority 1. Notice that
$t_{1}$ is the “bridge” bidder we discussed in Section 4.2. For visualization
we note that Inequality (4) is the one depicted in Fig. 2 (middle) while
Inequalities (5)-(6) are shown in Fig. 3 (left); these are the inequalities
that correspond to $\ell_{1}=1$ and $\ell_{2}=0$.

If Condition (1) does not hold for subset $S^{*}\setminus\\{i,t_{1}\\}$, then
there is an additional “bridge” bidder $t_{2}$ that is colored red at
$S^{*}\setminus\\{i,t_{1}\\}$, and we can possibly apply Lemma 3 with
$\ell_{1}=2$. If not, we continue in this way until either Condition (1) holds
or only $j,k$ remain in the subset. In either case, denote the final number of
“bridge” bidders by $\ell_{1}$. In the latter case, either Observation 2 or
Observation 3 hold, and so

$v_{t_{\ell_{1}}}(\\{j,k\\})\geq v_{j}(\\{j,k\\})+v_{k}(\\{j,k\\}).$

By applying Lemma 3 with $\ell_{1}>0$ (and $\ell_{2}=\ell_{3}=0$) we conclude
that pair $i,j$ has Priority 1.

Observe that the same analysis holds if both Condition (1) and Condition (2)
are relaxed. In this case Lemma 3 applies with $\ell_{1}>0,\ell_{2}>0$ (and
$\ell_{3}=0$).

##### Case 2: Single red cell.

Finally, we address the case in which there exists a red bidder
$t_{1}^{\prime\prime}$ in column $S$ at the beginning of iteration $S$. We can
write $S$ as $S^{*}\setminus\\{k\\}$; the color red of $t_{1}^{\prime\prime}$
necessarily propagated forward from
$S^{*}\setminus\\{k,t_{1}^{\prime\prime}\\}$. Assume the following third
condition holds:

  1. 3.

At the beginning of iteration $S^{*}\setminus\\{k,t_{1}^{\prime\prime}\\}$, no
cells in that column are red.

By Observation 2,

$v_{t_{1}^{\prime\prime}}(S^{*}\setminus\\{k,t_{1}^{\prime\prime}\\})\geq
v_{j}(S^{*}\setminus\\{k,t_{1}^{\prime\prime}\\})+v_{i}(S^{*}\setminus\\{k,t_{1}^{\prime\prime}\\}).$
(7)

If Inequality (7) holds (alongside previous inequalities) then Lemma 3 applies
with $\ell_{1}>0,\ell_{2}>0,\ell_{3}=1$. If Condition (3) does not hold for
subset $S^{*}\setminus\\{k,t_{1}^{\prime\prime}\\}$, we continue as above,
denoting the final number of “bridge” bidders by $\ell_{3}$. By applying Lemma
3 with $\ell_{1}>0,\ell_{2}>0$ and $\ell_{3}>0$, we conclude that pair
$i,t_{1}^{\prime\prime}$ has Priority 1. ∎

##  5 Summary and Future Directions

Tension between optimization and truthfulness is an important theme of
algorithmic game theory. With interdependent values, this tension appears even
without computational considerations. Since with interdependence there is an
inherent clash between welfare maximization and truthfulness, the
approximation toolbox comes in handy. We apply it to arguably the simplest
possible setting (single-item auctions with binary signals), and get a tight
understanding of the tradeoff (i.e., what fraction of the optimal welfare can
be guaranteed by a truthful mechanism). Our results extend beyond single
items.

Two promising future directions are: (i) generalizing our results beyond
binary signals, and (ii) designing an “on the fly” tractable version of the
2-approximation truthful mechanism (i.e., a version that gets signal reports
and returns an allocation only for the reported signal profile). For the
former direction, non-binary signals pose additional challenges since two
priorities are no longer sufficient in the algorithm, and additionally the
propagation is more complex. In Appendix 0.D we present progress towards
resolving these challenges (in particular, Lemma 5 extends Lemma 3 to
functions over general integer signals).

## References

  * [1] Ausubel, L.: A Generalized Vickrey Auction. Econometric Society World Congress 2000 Contributed Papers 1257, Econometric Society (2000)
  * [2] Chawla, S., Fu, H., Karlin, A.R.: Approximate revenue maximization in interdependent value settings. In: Proceedings of the 15th ACM Conference on Economics and Computation EC. pp. 277–294 (2014)
  * [3] Dasgupta, P., Maskin, E.: Efficient auctions. The Quarterly Journal of Economics 115(2), 341–388 (2000)
  * [4] Eden, A., Feldman, M., Fiat, A., Goldner, K.: Interdependent values without single-crossing. In: Proceedings of the 19th ACM Conference on Economics and Computation EC. p. 369 (2018)
  * [5] Eden, A., Feldman, M., Fiat, A., Goldner, K., Karlin, A.R.: Combinatorial auctions with interdependent valuations: SOS to the rescue. In: Proceedings of the 20th ACM Conference on Economics and Computation EC. pp. 19–20 (2019)
  * [6] Eden, A., Feldman, M., Talgam-Cohen, I., Zviran, O.: Poa of simple auctions with interdependent values. In: The 35th AAAI Conference on Artificial Intelligence (2021)
  * [7] Gkatzelis, V., Patel, R., Pountourakis, E., Schoepflin, D.: Prior-free clock auctions for bidders with interdependent values. 14th International Symposium on Algorithmic Game Theory (2021)
  * [8] Jehiel, P., Moldovanu, B.: Efficient design with interdependent valuations. Econometrica 69(5), 1237–1259 (2001)
  * [9] Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55(2), 270–296 (2006)
  * [10] Li, Y.: Approximation in mechanism design with interdependent values. Games and Economic Behavior 103(C), 225–253 (2017)
  * [11] Maskin, E.: Auctions and privatization. In: Siebert, H. (ed.) Privatization, pp. 115–136. J.C.B. Mohr Publisher (1992)
  * [12] Milgrom, P.R., Weber, R.J.: A theory of auctions and competitive bidding. Econometrica 50(5), 1089–1122 (1982)
  * [13] Niazadeh, R., Roughgarden, T., Wang, J.R.: Optimal algorithms for continuous non-monotone submodular and dr-submodular maximization. J. Mach. Learn. Res. 21, 125:1–125:31 (2020)
  * [14] Nobel Committee for the Prize in Economic Sciences: Scientific background: Improvements to auction theory and inventions of new auction formats. The Royal Swedish Academy of Sciences Press Release (2020)
  * [15] Oxley, J.G.: Matroid Theory (Oxford Graduate Texts in Mathematics). Oxford University Press, Inc., USA (2006)
  * [16] Roughgarden, T., Talgam-Cohen, I.: Optimal and robust mechanism design with interdependent values. ACM Trans. Economics and Comput. 4(3), 18:1–18:34 (2016)
  * [17] Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance 16(1), 8–37 (1961)
  * [18] Wilson, R.: A bidding model of perfect competition. The Review of Economic Studies 44(3), 511–518 (1977)

##  Appendix 0.A Main Algorithm

In this section we give the pseudocode of our main algorithm (Algorithm 1),
which proves Theorem 3.1 by returning a truthful, $2$-approximate welfare
maximizing mechanism for any given setting $v_{1},\dots,v_{n}$. The
algorithm’s main procedure is Allocate, and it contains two sub-procedures
ColorRed and ColorBlack. For completeness, in Appendix 0.A.1 we analyze the
algorithm’s running time as a function of $n$.

1:Input: Set of bidders $E=\\{1,\dots,n\\}$ and their valuation functions
$V=(v_{1},\dots,v_{n})$, where $value(b,S)$ for $b\in E$ and $S\subseteq[n]$
returns $v_{b}(S)$.

2:Output: Allocation rule $x$, where allocation$(b,S)$ returns $x_{b}(S)$
represented by the following colors – red represents $x_{b}(S)=\frac{1}{2}$
and black represents $x_{b}(S)=0$.

3:Initialization: For every $b,S$, initialize allocation$(b,S)$=white. Let
$S_{1},S_{2},\dots,S_{2^{n}}$ be an inclusion-compatible ordering of all
subsets of $[n]$.

4:

5:function Allocate($E,V$)

6: for $S\in(S_{1},S_{2},\dots,S_{2^{n}})$ do

7: cnt_reds $\leftarrow\left|\\{b\in E\text{ s.t.
allocation}(b,S)=\text{red}\\}\right|$

8: if cnt_reds $=2$ then

9: continue;$\triangleright$ go to next subset

10: end if

11: max_v $\leftarrow$ max{$value(b,S)$ : $b\in E$} $\triangleright$ max_v
$=\operatorname{OPT}(S)$

12: if $\exists b_{1},b_{2}$ s.t. $b_{1}\neq b_{2}$ and
$\\{b_{1},b_{2}\\}\subseteq S$ then

13: if allocation($b_{1}$, S) $\neq$ black and allocation($b_{2}$, S) $\neq$
black then

14: if $\nexists b_{3}\notin\\{b_{1},b_{2}\\}$ s.t. allocation($b_{3}$,
S)$=$red then

15: if $value(b_{1},S)+value(b_{2},S)\geq$ max_v then

16: ColorRed($b_{1}$, $S$) $\triangleright$ Priority 1

17: ColorRed($b_{2}$, $S$) $\triangleright$ Priority 1

18: continue;

19: end if

20: end if

21: end if

22: end if

23: if $\exists b_{1}$ s.t. allocation($b_{1}$, $S$) $\neq$ black then

24: if $value(b_{1},S)=$ max_v then

25: ColorRed($b_{1}$, $S$) $\triangleright$ Priority 2

26: for $b_{2}$ s.t. allocation$(b_{2},S)=$ white do

27: ColorBlack($b_{2}$, $S$)

28: end for

29: end if

30: end if

31: end for

32:end function

Algorithm 1 Mechanism Construction

33:function ColorRed($b$, $S$)

34: if allocation($b$, $S$) $=$ black then

35: Error(“Cannot color a black cell red”)

36: end if

37: if allocation($b$, $S$) $=$ red then

38: return

39: end if

40: if $\exists b_{1},b_{2}$ s.t. $b_{1},b_{2}\neq b$ and $b_{1}\neq b_{2}$,
and allocation($b_{1}$, $S$) $=$ allocation($b_{2}$, $S$) $=$ red then

41: Error(“Cannot color more than two cells red”)

42: end if

43: allocation($b$, $S$) $\leftarrow$ red

44: if $\exists b_{1}\neq b$ s.t. allocation($b_{1}$, $S$) $=$ red then
$\triangleright$ Two cells $b,b_{1}$ are red

45: for $b^{\prime}\neq b,b_{1}$ do

46: ColorBlack($b^{\prime}$, $S$) $\triangleright$ Color the others black

47: end for

48: end if

49: if $b\notin S$ then

50: ColorRed($b$, $S\cup\\{b\\}$) $\triangleright$ Propagate forward

51: end if

52:end function$\triangleright$
———————————————————————————————————–

53:function ColorBlack($b$, $S$)

54: if allocation($b$, $S$) $=$ red then

55: Error(“Cannot color a red cell black”)

56: end if

57: if allocation($b$, $S$) $=$ black then

58: return

59: end if

60: allocation($b$, $S$) $\leftarrow$ black

61: if $b\in S$ then

62: ColorBlack($b$, $S\setminus\\{b\\}$) $\triangleright$ Propagate backward

63: end if

64:end function

###  0.A.1 Computational Complexity

The loop in line 36 iterates over all subsets of bidders, that is, over
$2^{n}$ sets. For each set:

  1. 1.

We count the red bidders in line $7$ which takes $O(n)$;

  2. 2.

We find the maximum value in line $11$ which takes $O(n)$;

  3. 3.

In lines $12$-$15$ we search for two bidders that satisfy Priority 1, for
which we iterate over all bidders once more to check there is no other red
bidder. This takes $O(n^{3})$;

  4. 4.

When two bidders are found, we call ColorRed twice. In ColorRed we check if
two are already red, which takes $O(n)$, and if so we color all the others
black with ColorBlack (which takes O(1)). Thus, ColorRed in total takes
$O(n)$;

  5. 5.

In lines $23$-$26$ we iterate over all bidders and search for a bidder with
Priority 2. If found we call ColorRed, which takes $O(n)$;

In total, the algorithm’s runtime complexity is $O(n^{3}\cdot 2^{n})$.

##  Appendix 0.B Missing Proofs from Section 4

###  0.B.1 Proof of Lemma 3

Figure 5: Visualization of the inequalities of Lemma 3 for the general case.

In this section we prove that if the inequalities of Lemma 3 (as depicted in
Fig. 5) hold simultaneously, then they must all hold with equality.

###### Proof

The proof is by induction. For the base cases define
$u_{i^{\prime}}(x)=v_{i^{\prime}}(x\mid S^{\prime})$ for every
${i^{\prime}}\in[n]$. Note that we provide the analysis of Base Cases 2-4 to
build intuition (Base Case 1 is sufficient to complete the proof).

#### Base cases.

##### Base Case 1: $\ell_{1}=\ell_{2}=\ell_{3}=0$.

For any three bidders $i,j,k$, consider the following three inequalities:

  * •

$u_{i}(jk)+v_{i}(S^{\prime})\geq
u_{j}(jk)+v_{j}(S^{\prime})+u_{k}(jk)+v_{k}(S^{\prime})$;

  * •

$u_{j}(ik)+v_{j}(S^{\prime})\geq
u_{i}(ik)+v_{i}(S^{\prime})+u_{k}(ik)+v_{k}(S^{\prime})$;

  * •

$u_{k}(ij)+v_{k}(S^{\prime})\geq
u_{i}(ij)+v_{i}(S^{\prime})+u_{j}(ij)+v_{j}(S^{\prime})$.

We sum the inequalities and replace
$v_{i}(S^{\prime})+v_{j}(S^{\prime})+v_{k}(S^{\prime})$ by $A$ to get:

$u_{i}(jk)+u_{j}(ik)+u_{k}(ij)+A\geq
u_{j}(jk)+u_{k}(jk)+u_{i}(ik)+u_{k}(ik)+u_{i}(ij)+u_{j}(ij)+2A.$

Since all factors are non-negative, $A\leq 2A$ and so:

$u_{i}(jk)+u_{j}(ik)+u_{k}(ij)\geq
u_{j}(jk)+u_{k}(jk)+u_{i}(ik)+u_{k}(ik)+u_{i}(ij)+u_{j}(ij).$

By subadditivity we know that:

  * •

$u_{i}(j)+u_{i}(k)\geq u_{i}(jk)$;

  * •

$u_{j}(i)+u_{j}(k)\geq u_{j}(ik)$;

  * •

$u_{k}(i)+u_{k}(j)\geq u_{k}(ij)$.

Thus, we get:

$\underbrace{u_{i}(j)}_{\text{1}}+\underbrace{u_{i}(k)}_{\text{2}}+\underbrace{u_{j}(i)}_{\text{3}}+\underbrace{u_{j}(k)}_{\text{4}}+\underbrace{u_{k}(i)}_{\text{5}}+\underbrace{u_{k}(j)}_{\text{6}}\geq$
$\underbrace{u_{j}(jk)}_{\text{4}}+\underbrace{u_{k}(jk)}_{\text{6}}+\underbrace{u_{i}(ik)}_{\text{2}}+\underbrace{u_{k}(ik)}_{\text{5}}+\underbrace{u_{i}(ij)}_{\text{1}}+\underbrace{u_{j}(ij)}_{\text{3}}$

Notice that for each pair of summands with the same number, the left-hand side
is at most the right-hand side by monotonicity. This completes the analysis of
Base Case 1.

##### Base Case 2: $\ell_{1}=1,\ell_{2}=\ell_{3}=0$.

For any four bidders $i,j,k,t$, consider the following four inequalities:

  * •

$u_{i}(jkt)+v_{i}(S^{\prime})\geq
u_{j}(jkt)+v_{j}(S^{\prime})+u_{t}(jkt)+v_{t}(S^{\prime})$;

  * •

$u_{t}(jk)+v_{t}(S^{\prime})\geq
u_{j}(jk)+v_{j}(S^{\prime})+u_{k}(jk)+v_{k}(S^{\prime})$;

  * •

$u_{j}(ikt)+v_{j}(S^{\prime})\geq
u_{i}(ikt)+v_{i}(S^{\prime})+u_{k}(ikt)+v_{k}(S^{\prime})$;

  * •

$u_{k}(ijt)+v_{k}(S^{\prime})\geq
u_{i}(ijt)+v_{i}(S^{\prime})+u_{j}(ijt)+v_{j}(S^{\prime})$.

We sum the inequalities and use that
$v_{i}(S^{\prime})+v_{t}(S^{\prime})+v_{j}(S^{\prime})+v_{k}(S^{\prime})\leq
3v_{j}(S^{\prime})+v_{t}(S^{\prime})+2v_{k}(S^{\prime})+2v_{i}(S^{\prime})$ to
get:

$\displaystyle u_{i}(jkt)+u_{t}(jk)+u_{j}(ikt)+u_{k}(ijt)\geq$ $\displaystyle
u_{j}(jkt)+u_{t}(jkt)+u_{j}(jk)+u_{k}(jk)+u_{i}(ikt)+u_{k}(ikt)+u_{i}(ijt)+u_{j}(ijt).$

By subadditivity we know that:

  * •

$u_{i}(j)+u_{i}(kt)\geq u_{i}(jkt)$;

  * •

$u_{j}(i)+u_{j}(k)+u_{j}(t)\geq u_{j}(ikt)$;

  * •

$u_{k}(it)+u_{k}(j)\geq u_{k}(ijt)$.

Thus, we get:

$\underbrace{u_{i}(j)}_{\text{1}}+\underbrace{u_{i}(kt)}_{\text{2}}+\underbrace{u_{t}(jk)}_{\text{3}}+\underbrace{u_{j}(i)}_{\text{4}}+\underbrace{u_{j}(k)}_{\text{5}}+\underbrace{u_{j}(t)}_{\text{6}}+\underbrace{u_{k}(it)}_{\text{7}}+\underbrace{u_{k}(j)}_{\text{8}}\geq$
$\underbrace{u_{j}(jkt)}_{\text{6}}+\underbrace{u_{t}(jkt)}_{\text{3}}+\underbrace{u_{j}(jk)}_{\text{5}}+\underbrace{u_{k}(jk)}_{\text{8}}+\underbrace{u_{i}(ikt)}_{\text{2}}+\underbrace{u_{k}(ikt)}_{\text{7}}+\underbrace{u_{i}(ijt)}_{\text{1}}+\underbrace{u_{j}(ijt)}_{\text{4}}$

As above, for each pair of summands with the same number, the left-hand side
is at most the right-hand side by monotonicity. This completes the analysis of
Base Case 2.

##### Base Case 3: $\ell_{2}=1,\ell_{1}=\ell_{3}=0$.

The analysis of this case is symmetric to that of
$\ell_{1}=1,\ell_{2}=\ell_{3}=0$.

##### Base Case 4: $\ell_{1}=\ell_{2}=0,\ell_{3}=1$.

For any four bidders $i,j,k,t^{\prime\prime}_{1}$, consider the following four
inequalities:

  1. 1.

$u_{i}(jkt^{\prime\prime}_{1})+v_{i}(S^{\prime})\geq
u_{j}(jkt^{\prime\prime}_{1})+v_{j}(S^{\prime})+u_{k}(jkt^{\prime\prime}_{1})+v_{k}(S^{\prime})$;

  2. 2.

$u_{j}(ikt^{\prime\prime}_{1})+v_{j}(S^{\prime})\geq
u_{i}(ikt^{\prime\prime}_{1})+v_{i}(S^{\prime})+u_{k}(ikt^{\prime\prime}_{1})+v_{k}(S^{\prime})$;

  3. 3.

$u_{t^{\prime\prime}_{1}}(ij)+v_{t^{\prime\prime}_{1}}(S^{\prime})\geq
u_{j}(ij)+v_{j}(S^{\prime})+u_{i}(ij)+v_{i}(S^{\prime})$;

  4. 4.

$u_{k}(ijt^{\prime\prime}_{1})+v_{k}(S^{\prime})\geq
u_{t^{\prime\prime}_{1}}(ijt^{\prime\prime}_{1})+v_{t^{\prime\prime}_{1}}(S^{\prime})+u_{j}(ijt^{\prime\prime}_{1})+v_{j}(S^{\prime})$.

We sum the inequalities and use that
$v_{i}(S^{\prime})+v_{j}(S^{\prime})+v_{t^{\prime\prime}_{1}}(S^{\prime})+v_{k}(S^{\prime})\leq
2v_{i}(S^{\prime})+3v_{j}(S^{\prime})+v_{t^{\prime\prime}_{1}}(S^{\prime})+2v_{k}(S^{\prime})$
to get:

$\displaystyle
u_{i}(jkt^{\prime\prime}_{1})+u_{j}(ikt^{\prime\prime}_{1})+u_{t^{\prime\prime}_{1}}(ij)+u_{k}(ijt^{\prime\prime}_{1})\geq$
$\displaystyle
u_{j}(jkt^{\prime\prime}_{1})+u_{k}(jkt^{\prime\prime}_{1})+u_{i}(ikt^{\prime\prime}_{1})+u_{k}(ikt^{\prime\prime}_{1})+u_{j}(ij)+u_{i}(ij)+u_{t^{\prime\prime}_{1}}(ijt^{\prime\prime}_{1})+u_{j}(ijt^{\prime\prime}_{1}).$

By subadditivity we know that:

  * •

$u_{i}(j)+u_{i}(k{t^{\prime\prime}_{1}})\geq u_{i}(jk{t^{\prime\prime}_{1}})$;

  * •

$u_{j}(i)+u_{j}(k)+u_{j}({t^{\prime\prime}_{1}})\geq
u_{j}(ik{t^{\prime\prime}_{1}})$;

  * •

$u_{k}(i{t^{\prime\prime}_{1}})+u_{k}(j)\geq u_{k}(ij{t^{\prime\prime}_{1}})$.

Thus, we get:

$\underbrace{u_{i}(j)}_{\text{1}}+\underbrace{u_{i}(k{t^{\prime\prime}_{1}})}_{\text{2}}+\underbrace{u_{t^{\prime\prime}_{1}}(ij)}_{\text{3}}+\underbrace{u_{j}(i)}_{\text{4}}+\underbrace{u_{j}(k)}_{\text{5}}+\underbrace{u_{j}(t^{\prime\prime}_{1})}_{\text{6}}+\underbrace{u_{k}(i{t^{\prime\prime}_{1}})}_{\text{7}}+\underbrace{u_{k}(j)}_{\text{8}}\geq$
$\underbrace{u_{j}(ij{t^{\prime\prime}_{1}})}_{\text{6}}+\underbrace{u_{t^{\prime\prime}_{1}}(ijt^{\prime\prime}_{1})}_{\text{3}}+\underbrace{u_{j}(jkt^{\prime\prime}_{1})}_{\text{5}}+\underbrace{u_{k}(jkt^{\prime\prime}_{1})}_{\text{8}}+\underbrace{u_{i}(ikt^{\prime\prime}_{1})}_{\text{2}}+\underbrace{u_{k}(ikt^{\prime\prime}_{1})}_{\text{7}}+\underbrace{u_{i}(ij)}_{\text{1}}+\underbrace{u_{j}(ij)}_{\text{4}}.$

As above, for each pair of summands with the same number, the left-hand side
is at most the right-hand side by monotonicity. This completes the analysis of
Base Case 4.

#### Induction step.

Assuming the lemma holds for $\ell_{1}-1,\ell_{2},\ell_{3}$, we prove it for
$\ell_{1},\ell_{2},\ell_{3}$. The proof is symmetric for increasing $\ell_{2}$
or $\ell_{3}$.

Define $S=S^{\prime}\cup\\{t_{\ell_{1}}\\}$ and
$u_{i^{\prime}}^{*}(x)=v_{i^{\prime}}(x\mid S)$ for every
${i^{\prime}}\in[n]$. Using this notation we can rewrite the inequalities of
the lemma as follows:

  * •

$u_{i}^{*}(jkt_{1}t_{2}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{i}(S)\geq\\\
u_{j}^{*}(jkt_{1}t_{2}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{j}(S)+\\\
u_{t_{1}}^{*}(jkt_{1}t_{2}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{t_{1}}(S)$;

  * •

$\forall
h\in[\ell_{1}]:u_{t_{h}}^{*}(jkt_{h+1}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{t_{h}}(S)\geq\\\
u_{j}^{*}(jkt_{h+1}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{j}(S)+\\\
u_{t_{h+1}}^{*}(jkt_{h+1}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{t_{h+1}}(S)$;

  * •

$u_{j}^{*}(ikt_{1}t_{2}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{j}(S)\geq\\\
u_{i}^{*}(ikt_{1}t_{2}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{i}(S)+\\\
u_{t_{1}^{\prime}}^{*}(jkt_{1}t_{2}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{t_{1}^{\prime}}(S)$;

  * •

$\forall
h\in[\ell_{2}]:u_{t_{h}^{\prime}}^{*}(ikt_{1}...t_{\ell_{1}-1}t_{h+1}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{t_{h}^{\prime}}(S)\geq\\\
u_{i}^{*}(ikt_{1}...t_{\ell_{1}-1}t_{h+1}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{i}(S)+\\\
u_{t_{h+1}^{\prime}}^{*}(jkt_{1}...t_{\ell_{1}-1}t_{h+1}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{t_{h+1}^{\prime}}(S)$;

  * •

$u_{k}^{*}(ijt_{1}t_{2}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{k}(S)\geq\\\
u_{i}^{*}(ijt_{1}t_{2}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{i}(S)+\\\
u_{j}^{*}(ijt_{1}t_{2}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{j}(S)$;

  * •

$\forall
h\in[\ell_{3}]:u_{t^{\prime\prime}_{h}}^{*}(ijt_{1}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{h+1},...,t^{\prime\prime}_{\ell_{3}})+v_{t^{\prime\prime}_{h}}(S)\geq\\\
u_{j}^{*}(ijt_{1}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{h+1},...,t^{\prime\prime}_{\ell_{3}})+v_{j}(S)+\\\
u_{t^{\prime\prime}_{h+1}}^{*}(ijt_{1}...t_{\ell_{1}-1}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{h+1},...,t^{\prime\prime}_{\ell_{3}})+v_{t_{h+1}}(S)$.

The last two inequalities in the second bullet are:

$\displaystyle
u_{t_{\ell_{1}-1}}^{*}(jkt_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime})+v_{t_{\ell_{1}-1}}(S)\geq$
$\displaystyle
u_{j}^{*}(jkt_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime})+v_{j}(S)+u_{t_{\ell_{1}}}^{*}(jkt_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime})+v_{t_{\ell_{1}}}(S);$
(8) $\displaystyle
u_{t_{\ell_{1}}}^{*}(jkt_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime})+v_{t_{\ell_{1}}}(S)\geq$
$\displaystyle
u_{j}^{*}(jkt_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime})+v_{j}(S)+u_{k}^{*}(jkt_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime})+v_{k}(S).$
(9)

Combining Inequalities (8)-(9) we get that:

$\displaystyle
u_{t_{\ell_{1}-1}}^{*}(jkt_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime})+v_{t_{\ell_{1}-1}}(S)\geq$
$\displaystyle
u_{j}^{*}(jkt_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime})+v_{j}(S)+u_{j}^{*}(jkt_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime})+v_{j}(S)+u_{k}^{*}(jkt_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime})+v_{k}(S)\geq$
$\displaystyle
u_{j}^{*}(jkt_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime})+v_{j}(S)+u_{k}^{*}(jkt_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime})+v_{k}(S).$
(10)

Consider replacing the last two inequalities in the second bullet with the
combined Inequality (10). We know from the induction assumption for
$\ell_{1}-1,\ell_{2},\ell_{3}$ that these $\ell_{1}+\ell_{2}+\ell_{3}+2$
inequalities must hold with equality. Thus, the same holds for the
$\ell_{1}+\ell_{2}+\ell_{3}+3$ original inequalities. ∎

###  0.B.2  Proof of Lemma 4: Supplementary

######  Proof (Lemma 4, missing details)

Fix a subset $S\subseteq[n]$ such that there are $<2$ red bidders at the
beginning of iteration $S$. We show by case analysis that one of the two
priorities holds.

Denote the highest bidder (whose value at $S$ equals $\operatorname{OPT}(S)$)
by $k$. If at the beginning of iteration $S$ bidder $k$ is not colored black,
then $k$ has Priority 2 (note there is also possibly an additional pair with
Priority 1), and this is sufficient to complete the proof. The main technical
challenge is if at the beginning of iteration $S$, bidder $k$ _is_ colored
black. Observe this can only happen due to back propagation from
$(k,S\cup\\{k\\})$.

Let $S^{*}=S\cup\\{k\\}$. Since $S\subset S^{*}$ we know that at the beginning
of iteration $S$, Algorithm 1 did not yet reach iteration $S^{*}$. Thus, for
back propagation to occur, two reds must have propagated forward to $S^{*}$;
denote the corresponding red bidders by $i,j$. The forward propagation must
have been from $(i,S^{*}\setminus\\{i\\})$ and $(j,S^{*}\setminus\\{j\\})$,
resulting in coloring $(k,S^{*})$ black (and back-propagating the color black
to $(k,S)$). We now split the analysis into two cases, by the number of cells
colored red at the beginning of iteration $S$ (which is $<2$ by assumption).
We use $i,j,k$ as defined above in the case analysis:

##### Case 1: No red cells.

As detailed in Section 4.3, Observations 2-3 imply that for
$\ell_{1},\ell_{2}\geq 0$ there exist
$t_{1},t_{2},...,t_{l_{1}},t_{1}^{\prime},t_{2}^{\prime},...,t_{l_{2}}^{\prime}$
for which the following inequalities simultaneously hold:

  * •

$v_{i}(S^{*}\setminus\\{i\\})\geq
v_{t_{1}}(S^{*}\setminus\\{i\\})+v_{j}(S^{*}\setminus\\{i\\})$;

  * •

$\forall h\in[\ell_{1}]:v_{t_{h}}(S^{*}\setminus\\{i,t_{1},...,t_{h}\\})\geq
v_{t_{h+1}}(S^{*}\setminus\\{i,t_{1},...,t_{h}\\})+v_{j}(S^{*}\setminus\\{i,t_{1},...,t_{h}\\})$;

  * •

$v_{j}(S^{*}\setminus\\{j\\})\geq
v_{t_{1}^{\prime}}(S^{*}\setminus\\{j\\})+v_{i}(S^{*}\setminus\\{j\\})$;

  * •

$\forall
h\in[\ell_{2}]:v_{t_{h}^{\prime}}(S^{*}\setminus\\{j,t_{1}^{\prime},...,t_{h}^{\prime}\\})\geq
v_{t_{h+1}^{\prime}}(S^{*}\setminus\\{j,t_{1}^{\prime},...,t_{h}^{\prime}\\})+v_{i}(S^{*}\setminus\\{j,t_{1}^{\prime},...,t_{h}^{\prime}\\})$;

By Lemma 3 with $\ell_{3}=0$, if $v_{k}(S^{*}\setminus\\{k\\})\geq
v_{i}(S^{*}\setminus\\{k\\})+v_{j}(S^{*}\setminus\\{k\\})$ then the
inequalities all hold with equality. In particular,
$v_{k}(S)=v_{k}(S^{*}\setminus\\{k\\})=v_{i}(S^{*}\setminus\\{k\\})+v_{j}(S^{*}\setminus\\{k\\})=v_{i}(S)+v_{j}(S)$.
In other words, by Lemma 3 either $v_{k}(S)=v_{i}(S)+v_{j}(S)$, or else
$v_{k}(S)<v_{i}(S)+v_{j}(S)$ to begin with. We conclude that
$v_{i}(S)+v_{j}(S)\geq v_{k}(S)$. Therefore, both $i$ and $j$ are contained in
the set $S$, their aggregate value is at least that of $k$, and there are no
bidders already colored red at $S$. Thus the pair $i,j$ has Priority 1.

##### Case 2: Single red cell.

Denote the bidder colored red at $S$ by $t^{\prime\prime}_{1}$. As explained
in Section 4.3, Observations 2-3 imply that for $\ell_{3}\geq 0$ there exist
$t^{\prime\prime}_{2},...,t^{\prime\prime}_{\ell_{3}+1}$ where
$t^{\prime\prime}_{\ell_{3}+1}=i$ such that:

$\forall
h\in[\ell_{3}]:v_{t^{\prime\prime}_{h}}(S\setminus\\{t^{\prime\prime}_{1},..,t^{\prime\prime}_{h}\\})\geq
v_{t^{\prime\prime}_{h+1}}(S\setminus\\{t^{\prime\prime}_{1},..,t^{\prime\prime}_{h}\\})+v_{j}(S\setminus\\{t^{\prime\prime}_{1},..,t^{\prime\prime}_{h}\\}).$

These inequalities hold simultaneously with the inequalities for
$\ell_{1},\ell_{2}$ above. By Lemma 3, if $v_{k}(S^{*}\setminus\\{k\\})\geq
v_{t^{\prime\prime}_{1}}(S^{*}\setminus\\{k\\})+v_{j}(S^{*}\setminus\\{k\\})$
then the inequalities all hold with equality. As above we conclude that
$v_{t^{\prime\prime}_{1}}(S)+v_{j}(S)\geq v_{k}(S)$, and that the pair
$t^{\prime\prime}_{1},j$ has Priority 1. ∎

##  Appendix 0.C Matroid Auction Settings

In this appendix we establish, by reduction to the single item case, the
existence of a truthful mechanism for matroid settings that achieves a
$2$-approximation to the optimal welfare. This existence result follows
directly from Proposition 2 below.

A _matroid auction setting_ is defined by a matroid $([n],\mathcal{I})$, where
$\mathcal{I}$ contains all _independent sets_ of bidders, i.e., subsets of
bidders who can simultaneously _win_ in the auction. We also refer to sets in
$\mathcal{I}$ as _feasible_. For example, if there are $k$ units of the item
to allocate in the auction, $\mathcal{I}$ can be all possible subsets of $k$
bidders. The rest of the setting is as before, i.e., every bidder $i$ has a
signal $s_{i}$ and a valuation $v_{i}(s_{1},\dots,s_{n})$ for winning. It is
well known that in matroid settings _with given values_ , welfare maximization
is achieved by greedily adding bidders to the winner set $W$ while keeping $W$
feasible. We refer to this algorithm as Greedy.

1:function MatroidMechanism($(E,\mathcal{I}),k,S=\\{s_{i}\mid
s_{i}=1\\},V=(v_{1},\dots,v_{n})$)

2: $W=\emptyset$$\triangleright$ Current winning bidders

3: for $j\in[k]$ do$\triangleright$ Run $k$ times where $k$ is the matroid
rank

4: $x=$ Allocate($E$,$V$)

5: $b=$ randomly choose a bidder such that every bidder $b^{\prime}\in E$ is
chosen with probability $x(b^{\prime},S)$

6: $W=W\cup\\{b\\}$ $\triangleright$ Add $b$ to the winning set

7: $E=$ all bidders $b^{\prime}$ such that
$W\cup\\{b^{\prime}\\}\in\mathcal{I}$ $\triangleright$ Remove bidders who can
no longer feasibly win

8: end for

9:end function

Algorithm 2 Matroid Settings

###### Proposition 2

If for single item auctions there exists a monotone feasible allocation rule
that achieves a 2-approximation to the optimal welfare, then there exists such
an allocation rule for matroid auction settings as well.

###### Proof

Consider the matroid auction setting and fix a signal profile $S$. Let $k$ be
the rank of the matroid. Algorithm 9 gives our reduction. For the analysis we
use the following notation:

  * •

$\operatorname{GRD}_{i}$: The welfare contribution (i.e., the valuation given
$S$) of the $i$th bidder chosen by Greedy. Using this notation,
$\operatorname{OPT}=\sum_{i=1}^{k}\operatorname{GRD}_{i}$.

  * •

$\operatorname{ALG}_{i}$: The expected welfare contribution of the $i$th
bidder chosen by Algorithm 9 (where the expectation is over the randomness of
Allocate). Using this notation and linearity of expectation,
$\operatorname{ALG}=\sum_{i=1}^{k}\operatorname{ALG}_{i}$.

  * •

$\operatorname{GRD}_{i}^{*}$: After choosing $i-1$ winners by Algorithm 9,
$\operatorname{GRD}_{i}^{*}$ is the welfare contribution of the $i$th bidder
chosen by Greedy.

To show that $\operatorname{ALG}\geq\frac{1}{2}\operatorname{OPT}$, it is
sufficient to show that for every $i\in[k]$,
$\operatorname{ALG}_{i}\geq\frac{1}{2}\operatorname{GRD}_{i}^{*}\geq\frac{1}{2}\operatorname{GRD}_{i}$:

  1. 1.

$\operatorname{ALG}_{i}\geq\frac{1}{2}\operatorname{GRD}_{i}^{*}$: Let $v^{*}$
be the highest value among the remaining bidders after $i-1$ iterations of
Algorithm 9. Observe that $\operatorname{GRD}_{i}^{*}=v^{*}$. Since Alloc
guarantees a 2-approximation,
$\operatorname{ALG}_{i}\geq\frac{1}{2}v^{*}=\frac{1}{2}\operatorname{GRD}_{i}^{*}$.

  2. 2.

$\operatorname{GRD}_{i}^{*}\geq\operatorname{GRD}_{i}$: Let $W_{i-1}$ be the
winning set of bidders after $i-1$ iterations of Algorithm 9, and let
$W^{*}_{i}$ be the winning set of bidders after $i$ iterations of Greedy.
Observe that $\operatorname{GRD}_{i}$ is the lowest among the values of
bidders in $W^{*}_{i}$. By the exchange property of matroids, there is a
bidder in $W^{*}_{i}$ that can be feasibly added to $W_{i-1}$, and
$\operatorname{GRD}_{i}^{*}$ will be the highest value of such a bidder. The
inequality follows.

It remains to show that the algorithm maintains monotonicity. Denote:

  * •

$W_{i}$: Indicator – bidder $i$ wins at one of the iterations.

  * •

$W_{i}^{t}$: Indicator – bidder $i$ wins at iteration $t$.

We need to show that $\mathop{\mathbb{E}}{[W_{i}\mid
s_{i}=1]}\geq\mathop{\mathbb{E}}{[W_{i}\mid s_{i}=0]}$. Note that:

$\displaystyle\mathop{\mathbb{E}}{[W_{i}\mid s_{i}=1]}=$
$\displaystyle\mathop{\mathbb{E}}[\sum_{t=1}^{k}{W_{i}^{t}}\mid s_{i}=1]$ (11)
$\displaystyle=$
$\displaystyle\sum_{t=1}^{k}{\mathop{\mathbb{E}}{[W_{i}^{t}\mid s_{i}=1}]}$
(12) $\displaystyle\geq$
$\displaystyle\sum_{t=1}^{k}{\mathop{\mathbb{E}}{[W_{i}^{t}\mid s_{i}=0}]}$
(13) $\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}{[\sum_{t=1}^{k}{{W_{i}^{t}}\mid s_{i}=0]}]}$
(14) $\displaystyle=$ $\displaystyle\mathop{\mathbb{E}}{[W_{i}\mid s_{i}=0]},$
(15)

where Equations (11) and (15) are due to the fact that the bidder can only win
at one of the $k$ iterations, equations (12) and (14) are due to the linearity
of expectation and inequality (13) is due to the fact that Allocate at each
iteration is monotone; i.e. by Theorem 3.1. This completes the proof. ∎

##  Appendix 0.D Beyond Binary Signals

An interesting open question is whether our result extends beyond binary
signals. This appendix gives two indications that the answer may be positive.

###  0.D.1 Simulations

We ran a computer simulation that constructs random values, which satisfy SOS
for a setting with 3 bidders and 3 signals each. The values are randomized
under the SOS and monotonicity (of values) constraints. We achieve that by
constructing the values iteratively by the natural signals order to hold under
the constraints. To illustrate this, consider the valuation
$v_{1}(s=(1,1,0))$.

  1. 1.

We start by constructing the valuation $v_{1}(0,0,0)$ by simply choosing a
random number;

  2. 2.

We construct the valuations $v_{1}(1,0,0)$ and $v_{1}(0,1,0)$ to random
numbers in the range $[v_{1}(0,0,0),\infty]$ to satisfy the constraint of
monotonicity of the valuations; i.e. $v_{1}(0,1,0)\geq v_{1}(0,0,0)$;

  3. 3.

We finally construct the valuation $v_{1}(1,1,0)$ to a random number in the
range
$[\max\\{v_{1}(1,0,0),v_{1}(0,1,0)\\},v_{1}(1,0,0)+v_{1}(0,1,0)-v_{1}(0,0,0)]$;

The upper bound of the range in (3) is used to satisfy the SOS constraint. By
SOS we know that:

$v_{1}(1,1,0)-v_{1}(1,0,0)\leq v_{1}(0,1,0)-v_{1}(0,0,0)$

Reordering the inequality gives the upper bound:

$v_{1}(1,1,0)\leq v_{1}(1,0,0)+v_{1}(0,1,0)-v_{1}(0,0,0)$

We continue to construct all the values iteratively in the same way.

We ran an extended algorithm for over $2,000,000$ different random valuations.
For each run of the algorithm, we checked if the social welfare approximation
of 2 was achieved. All the runs successfully passed the approximation test.
The code for the simulations is publicly available.666See
https://colab.research.google.com/drive/1vkhOt3aMG5DgivaHZt5URNhPJ7q0W4J1.

The algorithm that we ran is very similar to the one shown in this paper for
binary signals but with one change. The priorities are defined differently.
Given that the range of possible signals is $[k]$; we ordered the priorities
from $k$ to $1$. For each signals profile $s$, we iterate over the signal
range from $k$ to $1$ and for the iteration of signal’s value $m$ we check for
priorities $1$ and $2$ as follows; Priority 1 at iteration $m$ consists of two
bidders $i$ and $j$ s.t.:

  1. 1.

Bidder $i$ and $j$’s signals are at least $m$;

  2. 2.

Bidders $i$ and $j$ can both be colored red at iteration $s$;

  3. 3.

No other bidder $k\neq i,j$ is colored red at the beginning of iteration $s$;

  4. 4.

The sum of values $v_{i}(s)+v_{j}(s)$ is at least $\operatorname{OPT}(s)$
(recall that $\operatorname{OPT}(s)$ is the highest value of any bidder for
the item given signal profile $s$).

Priority 2 at iteration $m$ consists of one bidder $i$ s.t.:

  1. 1.

Bidder $i$’s signal is at least $m-1$;

  2. 2.

Bidder $i$ can be colored red at iteration $s$;

  3. 3.

The value $v_{i}(s)$ equals $\operatorname{OPT}(s)$.

In this extended algorithm we get $2k$ priorities, $2$ for each possible value
of a signal. We incorporate the sense of high and low signals by ordering the
priorities decreasingly by the signal range.

###  0.D.2 Extending Lemma 3

We show that our main technical lemma, Lemma 3, extends beyond binary signals.

###### Lemma 5

Consider a signals profile $s^{\prime}=(s_{1}^{\prime},...,s_{n}^{\prime})$
and $3+\ell_{1}+\ell_{2}+\ell_{3}$ bidders
$E=\\{i,j,k$,
$t_{1},\dots,t_{\ell_{1}}$,$t_{1}^{\prime},\dots,t_{\ell_{2}}^{\prime}$,$t^{\prime\prime}_{1},\dots,t^{\prime\prime}_{\ell_{3}}\\}$
(not necessarily distinct) with SOS valuations, and $n$ values
$d_{1},d_{2},...,d_{n}$. Define $s_{h}=s_{h}^{\prime}+d_{h}$ for each bidder
$h\in[n]$ and $s=(s_{1},...,s_{n})$. If the following
$3+\ell_{1}+\ell_{2}+\ell_{3}$ inequalities hold simultaneously then they hold
with equality:

  * •

$v_{i}(s_{i}^{\prime},s_{-i})\geq
v_{j}(s_{i}^{\prime},s_{-i})+v_{t_{1}}(s_{i}^{\prime},s_{-i})$

  * •

$\forall 0<h\leq\ell_{1}$:
$v_{t_{h}}(s_{i}^{\prime},s_{t_{1}}^{\prime},...,s_{t_{h}}^{\prime},s_{-\\{i,t_{1},...,t_{h}\\}})\geq\\\
v_{j}(s_{i}^{\prime},s_{t_{1}}^{\prime},...,s_{t_{h}}^{\prime},s_{-\\{i,t_{1},...,t_{h}\\}})+v_{t_{h+1}}(s_{i}^{\prime},s_{t_{1}}^{\prime},...,s_{t_{h}}^{\prime},s_{-\\{i,t_{1},...,t_{h}\\}})$

  * •

$v_{j}(s_{j}^{\prime},s_{-j})\geq
v_{i}(s_{j}^{\prime},s_{-j})+u_{t_{1}^{\prime}}(s_{j}^{\prime},s_{-j})$

  * •

$\forall 0<h\leq\ell_{2}$:
$v_{t_{h}^{\prime}}(s_{j}^{\prime},s_{t_{1}^{\prime}}^{\prime},...,s_{t_{h}^{\prime}}^{\prime},s_{-\\{j,t_{1}^{\prime},...,t_{h}^{\prime}\\}})\geq\\\
v_{i}(s_{j}^{\prime},s_{t_{1}^{\prime}}^{\prime},...,s_{t_{h}^{\prime}}^{\prime},s_{-\\{j,t_{1}^{\prime},...,t_{h}^{\prime}\\}})+v_{t_{h+1}^{\prime}}(s_{j}^{\prime},s_{t_{1}^{\prime}}^{\prime},...,s_{t_{h}^{\prime}}^{\prime},s_{-\\{j,t_{1}^{\prime},...,t_{h}^{\prime}\\}})$

  * •

$\forall 0<h\leq\ell_{3}$:
$v_{t^{\prime\prime}_{h}}(s_{k}^{\prime},s_{t^{\prime\prime}_{1}}^{\prime},...,s_{t^{\prime\prime}_{h}}^{\prime},s_{-\\{k,t^{\prime\prime}_{1},...,t^{\prime\prime}_{h}\\}})\geq\\\
v_{j}(s_{k}^{\prime},s_{t^{\prime\prime}_{1}}^{\prime},...,s_{t^{\prime\prime}_{h}}^{\prime},s_{-\\{k,t^{\prime\prime}_{1},...,t^{\prime\prime}_{h}\\}})+v_{t^{\prime\prime}_{h+1}}(s_{k}^{\prime},s_{t^{\prime\prime}_{1}}^{\prime},...,s_{t^{\prime\prime}_{h}}^{\prime},s_{-\\{k,t^{\prime\prime}_{1},...,t^{\prime\prime}_{h}\\}})$

  * •

$v_{k}(s_{k}^{\prime},s_{-k})\geq
v_{t^{\prime\prime}_{1}}(s_{k}^{\prime},s_{-k})+v_{j}(s_{k}^{\prime},s_{-k})$

###### Proof

For each profile of signals $\widetilde{s}$ define the corresponding set of
signals
$\widetilde{S}=\\{h\mid\widetilde{s}_{h}=s_{h}=s_{h}^{\prime}+d_{h}\\}$.
$v(\widetilde{S})$ is a submodular set function, and thus, defining
$u_{i}(x)=v_{i}(x\mid S^{\prime})$, we can rewrite the inequalities as the
following:

  * •

$u_{i}(jkt_{1}t_{2}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{i}(S^{\prime})\geq\\\
u_{j}(jkt_{1}t_{2}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{j}(S^{\prime})+\\\
u_{t_{1}}(jkt_{1}t_{2}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{t_{1}}(S^{\prime})$

  * •

$\forall 0<h\leq\ell_{1}$:
$u_{t_{h}}(jkt_{h+1}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{t_{h}}(S^{\prime})\geq\\\
u_{j}(jkt_{h+1}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{j}(S^{\prime})+\\\
u_{t_{h+1}}(jkt_{h+1}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{t_{h+1}}(S^{\prime})$

  * •

$u_{j}(ikt_{1}t_{2}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{j}(S^{\prime})\geq\\\
u_{i}(ikt_{1}t_{2}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{i}(S^{\prime})+\\\
+u_{t_{1}^{\prime}}(ikt_{1}t_{2}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{t_{1}^{\prime}}(S^{\prime})$

  * •

$\forall 0<h\leq\ell_{2}$:
$u_{t_{h}^{\prime}}(ikt_{1}...t_{\ell_{1}}t_{h+1}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{t_{h}^{\prime}}(S^{\prime})\geq\\\
u_{i}(ikt_{1}...t_{\ell_{1}}t_{h+1}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{i}(S^{\prime})+\\\
u_{t_{h+1}^{\prime}}(ikt_{1}...t_{\ell_{1}}t_{h+1}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{t_{h+1}^{\prime}}(S^{\prime})$

  * •

$\forall 0<h\leq\ell_{3}$:
$u_{t^{\prime\prime}_{h}}(ijt_{1}t_{2}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{h+1},...,t^{\prime\prime}_{\ell_{3}})+v_{t^{\prime\prime}_{h}}(S^{\prime})\geq\\\
u_{j}(ijt_{1}t_{2}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{h+1},...,t^{\prime\prime}_{\ell_{3}})+v_{j}(S^{\prime})+\\\
u_{t^{\prime\prime}_{h+1}}(ijt_{1}t_{2}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{h+1},...,t^{\prime\prime}_{\ell_{3}})+v_{t^{\prime\prime}_{h+1}}(S^{\prime})$

  * •

$u_{k}(ijt_{1}t_{2}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{k}(S^{\prime})\geq\\\
u_{t^{\prime\prime}_{1}}(ijt_{1}t_{2}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{t^{\prime\prime}_{1}}(S^{\prime})+\\\
+u_{j}(ijt_{1}t_{2}...t_{\ell_{1}}t_{1}^{\prime}t_{2}^{\prime}...t_{\ell_{2}}^{\prime}t^{\prime\prime}_{1},...,t^{\prime\prime}_{\ell_{3}})+v_{j}(S^{\prime})$

By Lemma 3 we know that if these inequalities hold together, they hold with
equality. ∎