# Multi-Channel Auction Design in the Autobidding World

Gagan Aggarwal, Andres Perlroth11footnotemark: 1 and Junyao Zhao Google,
<EMAIL_ADDRESS>University<EMAIL_ADDRESS>
Over the past few years, more and more Internet advertisers have started using
automated bidding for optimizing their advertising campaigns. Such advertisers
have an optimization goal (e.g. to maximize conversions), and some constraints
(e.g. a budget or an upper bound on average cost per conversion), and the
automated bidding system optimizes their auction bids on their behalf. Often,
these advertisers participate on multiple advertising channels and try to
optimize across these channels. A central question that remains unexplored is
how automated bidding affects optimal auction design in the multi-channel
setting.

In this paper, we study the problem of setting auction reserve prices in the
multi-channel setting. In particular, we shed light on the revenue
implications of whether each channel optimizes its reserve price locally, or
whether the channels optimize them globally to maximize total revenue.
Motivated by practice, we consider two models: one in which the channels have
full freedom to set reserve prices, and another in which the channels have to
respect floor prices set by the publisher. We show that in the first model,
welfare and revenue loss from local optimization is bounded by a function of
the advertisers’ inputs, but is independent of the number of channels and
bidders. In stark contrast, we show that the revenue from local optimization
could be arbitrarily smaller than those from global optimization in the second
model.

##  1 Introduction

Advertisers are increasingly using automated bidding in order to set bids for
ad auctions in online advertising. Automated bidding simplifies the bidding
process for advertisers – it allows an advertiser to specify a high-level goal
and one or more constraints, and optimizes their auction bids on their behalf
[17, 25, 23, 9]. A common goal is to maximize conversions or conversion value.
Some common constraints include Budgets and TargetCPA (i.e. an upper bound on
average cost per conversion). This trend has led to interesting new questions
on auction design in the presence of automated bidders [5, 14, 8, 7].

One central question that remains unexplored is how automated bidding affects
optimal auction design in the multi-channel setting. It is common for
advertisers to show ads on multiple channels and optimize across channels. For
example, an advertiser can optimize across Google Ads inventory (YouTube,
Display, Search, Discover, Gmail, and Maps) with Performance Ads [3], or can
optimize across Facebook, Instagram and Messenger with Automated Ad Placement
[4], or an app developer can advertise across Google’s properties including
Search, Google Play and YouTube with App campaigns [2]. With traditional
quasi-linear bidders, the problem of auction design on each channel is
independent of other channels’ designs. However, when advertisers use
automated bidders and optimize across channels, the auction design of one
channel creates externalities for the other channels through the constraints
of automated bidders.

Motivated by this, we introduce the problem of auction design in the multi-
channel setting with automated bidding across channels. In particular, we
study the problem of setting reserve prices across channels. We consider two
behavior models: Local and Global. In the Local model, each channel optimizes
its reserve price to maximize its own revenue, while in the Global model, the
channels optimize their reserve prices globally in order to maximize the total
revenue across channels. The main question is: what is the revenue loss from
optimizing locally, rather than globally?

We consider this question in two settings: one in which each channel has full
control over its reserve prices, and one in which the channels have to respect
an externally-imposed lower bound on the reserve prices. The first setting
which we call Without Publisher Reserves is very common in practice and arises
when the impressions are owned by the selling channel, or when the publisher
leaves the pricing decisions to the selling channel. The second setting which
we call With Publisher Reserves arises when the impressions are owned by a
third-party publisher that sets a floor price for its impressions – this could
come from an outside option for selling the impression. This is common in
Display advertising where the selling channel is often different from the
publisher who owns the impressions.

Model: Our model consists of $k$ channels, each selling a set of impressions.
Each channel can set a uniform reserve price. The uniform reserve price is in
the cost-per-unit-value space111See Section 7 for a discussion of uniform
reserve prices in the cost-per-impression space (see Section 3.1 for details).
This is motivated by the observation that, in practice, values are commonly
known by the channels; values are usually click-through-rate or conversion-
rate of an ad, as in [5], and the channels have good estimates for those.
Besides the reserve prices set by channels, in the With Publisher Reserves
setting, each impression could have a price floor set by the publisher who
owns the impression. Each impression is sold in a Second-Price-Auction with a
floor price that depends on the reserve price set by the selling channel and
the price constraint set by the publisher. Bidders want to maximize their
conversions (or some other form of value) subject to one of two types of
constraints: (1) Budget, an upper bound on spend and (2) TargetCPA, an upper
bound on the average cost per conversion. The model also allows standard
quasi-linear bidders with no constraints. The game consists of two main
stages: First, each channel simultaneously announces its reserve price; then,
bidders bid optimally for the different impressions.

###  1.1 Our results

The paper’s main focus is to compare the revenue222See Section 7 for a brief
discussion of welfare at equilibrium when channels optimize locally, i.e. each
sets its reserve price(s) to maximize its own revenue, to the revenue where
channels act globally and set their reserve prices to maximize the sum of the
total revenue. We define the Price of Anarchy (PoA) as the worst-case ratio
between the total revenue when the channels optimize locally compared to the
case where the channels optimize globally. Our main goal is to bound the Price
of Anarchy in the two settings: Without Publisher Reserves, and With Publisher
Reserves.

### Setting without Publisher Reserves

In order to bound the Price of Anarchy, we first bound the local and global
revenue in terms of the optimal Liquid Welfare (see Section 3 for the
definition). These revenue bounds are interesting in their own right and the
proof methodology gives (non-polytime) algorithms for determining good reserve
prices.

We first consider the worst-case revenue in the local model where each channel
is optimizing for its own revenue, compared to the optimal Liquid Welfare. We
show in Theorem 2 that the worst-case revenue is at least
$\Omega(\frac{1}{\log\eta})$ fraction of the optimal Liquid Welfare, where
$\eta$ depends on the bidders’ inputs333$\eta$ is the maximum of the ratio of
the highest to lowest TargetCPA among TargetCPA bidders and a ratio defined
(in Definition 5) for Budgeted bidders. and quantifies the heterogeneity of
the pool of bidders. This lower bound on revenue trivially carries over to the
setting where the channels are optimizing globally and to the single-channel
setting. Next, we show that this bound is tight up to constant factors
(Proposition 3). In particular, we give an example in the single-channel
setting where the optimal revenue with a uniform reserve price is
$O(\frac{1}{\log\eta})$ of the optimal Liquid Welfare. This upper bound also
applies to the global and local models in the multi-channel setting. In other
words, the upper bound and lower bounds on the gap between Liquid Welfare and
revenue in each of these settings is $\Theta(\log\eta)$. That naturally makes
one wonder: Is optimizing locally as good for revenue as optimizing globally?
If we look into the gap bounds, we find that they arise from trying to capture
values of different scales with a uniform reserve price. And one might
conjecture that since the source of the gap applies to both the global and
local model, that even if there is a revenue gap between the two models, it
should depend on different factors. Surprisingly, we show that the gap between
optimizing locally and globally is exactly the same $\log\eta$ factor (Theorem
4). Note that in all the above settings, the revenue guarantee is independent
of the number of channels and bidders and depends only on the heterogeneity of
the bidders.

### Setting with Publisher Reserves

In stark contrast to the setting without publisher reserves, we show that the
PoA in this setting can be arbitrarily small even with one tCPA bidder
(Theorem 6). The gap example depends heavily on the asymmetry between the
different channels. Motivated by this, we consider the restricted setting
where each channel sells a random sample of the impressions (see Section 6 for
the exact details). For this case, with one tCPA bidder in the game, we show
that under some mild constraint on the channels’ strategies, the PoA = $1/k$,
where $k$ is the number of channels. When the channels optimize globally, the
equilibrium is efficient and all channels set low reserve prices. On the other
hand, for the equilibrium in the local optimization model, the larger channels
(in terms of the volume of impressions they own) set low reserve prices while
small channels are extractive and set high reserve prices.

### Hardness of Equilibrium Computation

To complement our Price of Anarchy results, we also study the computational
complexity of computing the equilibrium of the game. We show an impossibility
result – that it is PPAD-hard to compute the subgame equilibrium of the
bidders (Theorem 1). To prove this result, we use gadget reduction from the
problem of finding approximate Nash equilibrium for $0$-$1$ bimatrix game, and
we need to handle many difficulties unique to our subgame, which we explain
with more details in Section 4 and Appendix B.

### Key implications of our results

Our results have several implications for setting reserve prices in the multi-
channel setting:

  * •

The revenue gap between local and global optimization depends heavily on
whether there are publisher-imposed reserve prices.

  * •

Without publisher reserves, the worst-case gap between the revenue in the
local model and the global model is $\Theta(\log\eta)$, where $\eta$ captures
the heterogeneity of the bidders’ inputs and is independent of the number of
channels and bidders. Thus it is better to optimize globally when possible.

  * •

Without publisher reserves, it is possible to obtain a revenue of
$\Theta(\frac{1}{\log\eta})$ fraction of the optimal Liquid Welfare by setting
uniform reserve prices. This observation is not surprising in the single-
channel setting and for global optimization in the multi-channel setting, but
it is remarkable that it holds even with local optimization, where the
selfishness of a channel could have made it difficult for other channels to
make revenue. We also note that the approximation can be improved by setting
reserve prices at a more granular level, rather than a uniform reserve price.
In that case, the approximation ratio will depend on the heterogeneity of
bidders per slice.

  * •

With publisher reserves, the gap between the revenue in the local and global
model can be arbitrarily large. This can happen even when only one of the
channels has external pricing constraint.

### Organization of the paper

We present a formal model of the problem in Section 3. Then, in Section 4, we
show that it is PPAD-hard to compute the equilibrium of the sub-game. In
Section 5, we study the setting without publisher reserves and present a tight
bound on the Price of Anarchy, as well as on the gap between the revenue and
optimal Liquid Welfare in the local and global models. In Section 6, we study
the setting with publisher reserves and show the Price of Anarchy is 0. We
also study a restricted version of this setting, and show a Price of Anarchy
of $1/k$ for that version. Finally, in Section 7, we discuss extensions for
welfare and for setting reserve prices in the cost-per-impression space.

##  2 Related Work

Autobidding. There has been a lot of recent interest in exploring questions
related to automated bidding, including bidding algorithms and their
equilibria [5], and auction design in the presence of automated bidding [14,
8, 7]. Aggarwal et al. [5] initiate the study of autobidding and find optimal
bidding strategies for a general class of autobidding constraints. They also
prove the existence of an equilibrium and prove a lower bound on liquid
welfare at equilibrium compared to the optimal liquid welfare. Deng et al.
[14] show how boosts can be used to improve welfare guarantees when bidders
can have both TargetCPA and Budget constraints, potentially at the cost of
revenue. Balseiro et al. [8] characterize the revenue-optimal single-stage
auctions with either value-maximizers or utility-maximizers with TargetCPA
constraints, when either the values and/or the targets are private. Similar to
our paper, Balseiro et al. [7] also study reserve prices in the presence of
autobidders, and show that with TargetCPA and Quasi-linear bidders, revenue
and welfare can be increased by using (bidder-specific) reserve prices. They
do not study budget-constrained bidders. All of the above papers are in the
single channel setting.

Auction design with multiple channels. Most of this stream of literature have
focused on models where multiple channels (auctioneers) compete to take
captive profit-maximizers buyers [10, 16, 20]. The competition across channels
leads to lower reserve prices, obtaining lower revenues and more efficient
outcomes [24]. Our model differs from them in that our bidders are not captive
but are instead are optimizing under their autobidding constraints.
Interestingly, we show that in some cases the competition among channels leads
to higher reserve prices, and at the same time, improves welfare (see Theorem
7.).

##  3 Model

Our baseline model considers a set of bidders (advertisers) $J$ interested in
purchasing a set of impressions $I$ that are sold by $K$ different channels.
The impressions that channel $k$ sells, $i\in I_{k}$, are sold using a second-
price auction with a floor price. This floor price depends on the reserve
price $r_{k}$ chosen by the channel and by the minimum price $p_{i}$ set by
the publisher that owns the impression444The publisher might have an outside
option to sell some of the impressions and sets a reserve price to account for
that. These reserve prices are prechosen by the publishers and hence are fixed
constants known to both channels and bidders..

###  3.1 Bidders

Motivated by the most common bidding formats that are used in practice, we
assume that each bidder can be one of the following types: a tCPA bidder, a
Budgeted bidder, or a Quasi-linear (QL) bidder. We denote by
$J_{\tiny{\mbox{tCPA}}}$, $J_{\tiny{\mbox{Budgeted}}}$ and
$J_{\tiny{\mbox{QL}}}$ the set of bidders that are tCPA, Budgeted and QL
bidders, respectively.

Each Bidder $j$ has a value (e.g. conversion rate) $v_{j,i}$ for impression
$i$ and submits a bid $b_{j,i}$ for the impression. A bidder’s cost for buying
impression $i\in I_{k}$ is

$\displaystyle c_{j,i}({\bm{b}}_{i},{\bm{r}})=\max\\{\max_{\ell\neq j\textrm{
s.t.
}b_{\ell,i}\geq\max\\{r_{k}v_{\ell,i},\,p_{i}v_{\ell,i}\\}}\\{b_{\ell,i}\\},\,r_{k}v_{j,i},\,p_{i}v_{j,i}\\},$
(1)

where ${\bm{b}}_{i}=(b_{j,i})_{j\in J}$ (note we use the notation
$c_{j,i}({\bm{b}}_{i},{\bm{r}})$ for simplicity, even though
$c_{j,i}({\bm{b}}_{i},{\bm{r}})$ does not depend on $b_{j,i}$) and
${\bm{r}}=(r_{k})_{k\in K}$ (because $p_{i}$’s are fixed constants prechosen
by the publishers, for simplicity we do not include them as variables). That
is, a bidder’s cost for an impression is the maximum among (i) the bids of the
bidders who bid above their own reserve prices, (ii) reserve price set by the
channel which owns the impression, and (iii) reserve price set by the
publisher. Also, note that the reserve prices $r_{k}$ and $p_{i}$ are
multiplied by $v_{j,i}$ to get the final floor price of impression $i$ for
bidder $j$. In other words, the reserve prices are in the cost-per-unit-value
space. We will refer to the final reserve price of impression $i$ for bidder
$j$ by $r_{j,i}:=\max\\{r_{k}v_{j,i},\,p_{i}v_{j,i}\\}$. Now we explain the
bidder types.

QL bidder: This is a traditional profit-maximizing bidder with no constraint.
The dominant strategy for such a Bidder $j$ is to bid her value $v_{j,i}$ for
impression $i$, regardless of how everyone else bids for that impression.

tCPA bidder: Such Bidder $j$ maximizes the number of conversions (i.e., the
total value of the impressions which the bidder gets) subject to the
constraint that the average cost per conversion is no greater than their tCPA
$T_{j}\geq 0$. Namely, bidder $j$ solves the following maximization problem:

$\displaystyle\max_{\forall i\in I,\,b_{j,i}\geq 0,\,x_{j,i}\in[0,1]}\quad$
$\displaystyle\sum_{i\in I\textrm{ s.t. }b_{j,i}\geq
c_{j,i}({\bm{b}}_{i},{\bm{r}})}v_{j,i}x_{j,i}$ s.t. $\displaystyle\sum_{i\in
I}c_{j,i}({\bm{b}}_{i},{\bm{r}})x_{j,i}\leq T_{j}\cdot\sum_{i\in
I}v_{j,i}x_{j,i}\quad\forall j\in J$ $\displaystyle x_{j,i}=1\mbox{ if
}b_{j,i}>c_{j,i}({\bm{b}}_{i},{\bm{r}})\quad\forall j\in J,i\in I.$ (2)

Budgeted bidder: Such Bidder $j$ maximizes the number of conversions subject
to a budget constraint $B_{j}$. Namely, Bidder $j$ solves the following
maximization problem:

$\displaystyle\max_{\forall i\in I,\,b_{j,i}\geq 0,\,x_{j,i}\in[0,1]}\quad$
$\displaystyle\sum_{i\in I\textrm{ s.t. }b_{j,i}\geq
c_{j,i}({\bm{b}}_{i},{\bm{r}})}v_{j,i}x_{j,i}$ s.t. $\displaystyle\sum_{i\in
I}c_{j,i}({\bm{b}}_{i},{\bm{r}})x_{j,i}\leq B_{j}\quad\forall j\in J$
$\displaystyle x_{j,i}=1\mbox{ if
}b_{j,i}>c_{j,i}({\bm{b}}_{i},{\bm{r}})\quad\forall j\in J,i\in I.$ (3)

Notice that both tCPA bidder and Budgeted bidder are allowed to decide the
fraction of an impression they get in case they are tied for that impression
(we say that bidder $j$ is tied for an impression $i$ if
$b_{j,i}=c_{j,i}({\bm{b}}_{i},{\bm{r}})$). This is in line with the standard
approach in the literature (e.g., budget pacing equilibrium [13]) that
endogenizes the tie-breaking rule as part of the equilibrium concept which we
will define shortly. Moreover, in the following proposition, we show that
given other bidders’ bids, it is optimal for a tCPA bidder (or a Budgeted
bidder) $j$ to bid uniformly555Qualitatively, this is same as the well-known
result of Aggarwal et al. [5]. They prove this by introducing small
perturbations to bidders’ values. Instead, we take the approach that
endogenizes the tie-breaking rule as part of the equilibrium concept, which is
the standard approach in the literature for proving existence and
computational complexity of equilibrium., i.e., the bids are characterized by
a single bidding parameter $\alpha_{j}\geq 0$ as follows: $\forall i\in
I,\,b_{j,i}=\alpha_{j}v_{j,i}$.

######  Proposition 1.

For a tCPA bidder (or a Budgeted bidder resp.) $j$, the optimal bids for
Problem (2) (or (3) resp.) have the following form: there exists
$\alpha_{j}\geq 0$ such that $\forall i\in I,\,b_{j,i}=\alpha_{j}v_{j,i}$.

The proof of Proposition 1 is provided in appendix.

###  3.2 Bidders’ Subgame

Bidders observe the reserve prices ${\bm{r}}=(r_{k})_{k\in K}$ posted by the
channels and decide their bids ${\bm{b}}_{i}({\bm{r}})$ for each impression
$i$, and if a Bidder $j$ is tied for impression $i$, they can also decide the
fraction $x_{j,i}({\bm{r}})$ of impression $i$ they get. In the previous
subsection, we have shown that for any bidder of any type, the best response
given other bidders’ bids is bidding uniformly, and hence, we assume that each
bidder $j$ uses uniform bidding with a bidding parameter
$\alpha_{j}({\bm{r}})$.

Moreover, we assume that in the bidders’ subgame, bidders use the undominated
uniform bidding strategies. Specifically, for a QL bidder, bidding less than
their value is dominated by bidding their value, and for a tCPA bidder $j$,
using a bidding parameter less than $T_{j}$ is dominated by using a bidding
parameter $\alpha_{j}({\bm{r}})=T_{j}$. To see the latter, notice that a tCPA
bidder $j$ using a bidding parameter strictly less than $T_{j}$ cannot be
tCPA-constrained since their cost for any impression they are winning cannot
be more than their bid $b_{j,i}=\alpha_{j}({\bm{r}})v_{j,i}<T_{j}v_{j,i}$.
Thus, their tCPA constraint, i.e., the first constraint in Problem (2), is not
tight, and hence, by increasing their bidding parameter to $T_{j}$, the bidder
can only increase the total value without violating its tCPA constraint. In
summary, we make the following assumption:

######  Assumption 1 (Uniform Undominated Bidding).

Each bidder $j\in J$ uses uniform bidding, i.e., $\forall i\in
I,\,b_{j,i}({\bm{r}})=\alpha_{j}({\bm{r}})v_{j,i}$ for some bidding parameter
$\alpha_{j}({\bm{r}})\geq 0$. Moreover, each QL bidder $j$ uses a bidding
parameter $\alpha_{j}({\bm{r}})=1$, and each tCPA bidder $j$ uses a bidding
parameter $\alpha_{j}({\bm{r}})\geq T_{j}$.

The equilibrium solution we adopt for the bidders’ subgame is a version of
subgame perfection that takes into account endogenous tie-breaking rules,
which is in line with the literature, e.g., the pacing equilibrium for
Budgeted bidders [13] and the autobidding equilibrium for tCPA bidders [19].

######  Definition 1 (Subgame Bidding Equilibrium).

Consider the bidders’ subgame given reserve prices ${\bm{r}}$ posted by the
channels. An equilibrium for the subgame consists of bidders’ bidding
parameters $\bm{\alpha}({\bm{r}})=(\alpha_{j}({\bm{r}}))_{j\in J}$ and
probabilities of allocations of the impressions
${\bm{x}}({\bm{r}})=(x_{j,i}({\bm{r}}))_{j\in J,i\in I}$ such that

  1. (1)

Only a bidder whose bid is no less than the cost gets the impression: for
$i\in I_{k}$, $x_{j,i}({\bm{r}})>0$ holds only if $b_{j,i}({\bm{r}})\geq
c_{j,i}({\bm{b}}_{i}({\bm{r}}),{\bm{r}})$.

  2. (2)

Full allocation of any item with a bid above the reserve price: for $i\in
I_{k}$, $\sum_{j\in J}x_{j,i}({\bm{r}})=1$ must hold if there exists some
$\ell\in J$ such that $b_{\ell,i}({\bm{r}})>r_{\ell,i}$.

  3. (3)

Constraints are satisfied: for each $j\in J_{\tiny{\mbox{Budgeted}}}$,
$\sum_{i\in I}c_{j,i}({\bm{b}}_{i}(r),{\bm{r}})\cdot x_{j,i}({\bm{r}})\leq
B_{j}$, and for each $j\in J_{\tiny{\mbox{tCPA}}}$, ${\sum_{i\in
I}c_{j,i}({\bm{b}}_{i}({\bm{r}}),{\bm{r}})x_{j,i}({\bm{r}})}\leq
T_{j}\cdot{\sum_{i\in I}v_{j,i}x_{j,i}({\bm{r}})}$.

  4. (4)

For every Budgeted or tCPA bidder $j$, even if they can decide the fraction
$x_{j,i}({\bm{r}})$ of an impression $i$ they get in case they are tied for
impression $i$, increasing their bidding parameter would not increase their
value without violating their budget/tCPA constraint.

The existence of subgame bidding equilibrium is a straightforward consequence
by adapting the existence proofs of the pacing equilibrium for Budgeted
bidders [13] and the autobidding equilibrium for tCPA bidders [19].

######  Proposition 2.

In the bidders’ subgame, the subgame bidding equilibrium always exists.

###  3.3 Channels

We focus on two models that depend on the objective functions the channels may
have: the Local channels model and the Global channels model.

Local Channels Model: In this case, each channel sets its reserve price
$r_{k}$ to maximize its own revenue given the other channels’ reserve prices
${\bm{r}}_{-k}$. Thus, channel $k$ solves

$\max_{r_{k}}\sum_{j\in J}\sum_{i\in
I_{k}}c_{j,i}({\bm{b}}_{i}(r_{k},{\bm{r}}_{-k}),r_{k},{\bm{r}}_{-k})x_{j,i}(r_{k},{\bm{r}}_{-k}).$

Global Channels Model: In this case, the channels determine the reserve prices
${\bm{r}}$ to maximize the sum of the revenue across all channels. Thus, they
set reserve prices solving

$\max_{{\bm{r}}}\sum_{k\in K}\sum_{j\in J}\sum_{i\in
I_{k}}c_{j,i}({\bm{b}}_{i}({\bm{r}}),{\bm{r}})x_{j,i}({\bm{r}}).$

###  3.4 The Full Game

We summarize the full game for the channels and the bidders as the following
two-stage game:

  * (S0)

Each Channel $k\in K$ chooses a uniform reserve price (in the cost-per-unit-
value space) $r_{k}$ with finite precision666Note that assuming the reserve
prices have finite precision is very natural for practice. for their
impressions $I_{k}$.

  * (S1)

Each Bidder $j\in J$ observes the reserve prices ${\bm{r}}$ posted by the
channels (and the reserve prices $(p_{i})_{i\in I}$ prechosen by the
publishers), and then they choose a bidding parameter $\alpha_{j}({\bm{r}})$
and submit their bids according to $\alpha_{j}({\bm{r}})$ (see Assumption 1).
If Bidder $j$ is tied for impression $i$, they can also decide the fraction
$x_{j,i}({\bm{r}})$ of impression $i$ they get.

By Proposition 2, given any fixed ${\bm{r}}$ in the support of the channels’
mixed strategies, stage (S1) has a subgame equilibrium between the bidders. We
assume that stage (S1) always results into one such equilibrium
deterministically, i.e., henceforth, we assume that
$(({\bm{b}}_{i}({\bm{r}}))_{i\in I},{\bm{x}}({\bm{r}}))$ in stage (S1) is
always a fixed subgame equilibrium given ${\bm{r}}$ (as defined in Definition
1).

Channels are allowed to use mixed strategies in stage (S0), i.e., sampling
their reserve price $r_{k}$ from a distribution $\mathcal{R}_{k}$. Notice that
the game for the channels is a finite game between finite players, and hence,
there always exists a mixed-strategy equilibrium by the celebrated Nash’s
theorem [21].

Additionally, we assume the game is complete-information. That is,
$(v_{j,i},B_{j},T_{j},p_{i})_{j\in J,i\in I}$ are known to the channels and
the bidders.

###  3.5 Important Concepts

We now present the main concepts which we will use to compare the outcomes of
the local channels model to the global channels model.

######  Definition 2 (Liquid Welfare).

The liquid welfare of a fractional allocation ${\bm{x}}=(x_{j,i})_{j\in J,i\in
I}$ is

${Wel}({\bm{x}})=\sum_{j\in
J_{\tiny{\mbox{Budgeted}}}}\min\left\\{{\mbox{B}}_{j},\sum_{i\in
I}v_{j,i}x_{j,i}\right\\}+\sum_{j\in J_{\tiny{\mbox{tCPA}}}}\sum_{i\in
I}T_{j}v_{j,i}x_{j,i}+\sum_{j\in J_{\tiny{\mbox{QL}}}}\sum_{i\in
I}v_{j,i}x_{j,i},$

and the optimal liquid welfare is $Wel^{*}:=\max_{{\bm{x}}\textrm{ that
satisfies bidders' constraints}}Wel({\bm{x}})$.

This concept of liquid welfare has been previously studied in e.g., Aggarwal
et al. [5] and Azar et al. [6], and it was first introduced by Dobzinski and
Paes Leme [15]. It is well-known that optimal liquid welfare is an upper bound
on the sum of the revenues of all channels. More precisely, optimal liquid
welfare $Wel^{*}$ is greater or equal than the sum of the channels’ revenues,
which we denote by $Rev({\bm{r}}):=\sum_{k\in K}\sum_{j\in J}\sum_{i\in
I_{k}}c_{j,i}({\bm{b}}_{i}({\bm{r}}),{\bm{r}})x_{j,i}({\bm{r}})$, regardless
of the reserve prices they choose:

######  Fact 1.

For any ${\bm{r}}\in\mathbb{R}_{\geq 0}^{K}$, $Rev({\bm{r}})\leq Wel^{*}$.

Thus, we use the optimal liquid welfare as the benchmark to measure
performance of the revenue in the local and global models. We let LocalEQ
denote the set that contains every mixed-strategy equilibrium
$\mathcal{R}:=(\mathcal{R}_{k})_{k\in K}$ for the channels in the local
channel model, and we define the revenue guarantees in the local and global
models as follows:

######  Definition 3 (Revenue Guarantee).

The revenue guarantees for the local and global models are defined as

$\displaystyle RevG(Local)$
$\displaystyle=\frac{\inf_{\mathcal{R}\in\mbox{LocalEQ}}\mathbb{E}_{{\bm{r}}\sim\mathcal{R}}[\mbox{Rev}({\bm{r}})]}{Wel^{*}},$
$\displaystyle RevG(Global)$
$\displaystyle=\frac{\sup_{{\bm{r}}\in\mathbb{R}_{\geq 0}^{K}}\mbox{
Rev}({\bm{r}})}{Wel^{*}}.$

Note that any reserve prices ${\bm{r}}$ in the support of any
$\mathcal{R}\in\mbox{LocalEQ}$ in the local model is also feasible in the
global model, thereby giving us the following fact.

######  Fact 2.

$RevG(Local)\leq RevG(Global)\leq 1$

Furthermore, to compare the outcomes of the two models, we use the standard
notion of the Price of Anarchy [18].

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

The Price of Anarchy (PoA) of the local model compared to the global model is

$\mbox{PoA}\;=\;\frac{\inf_{\mathcal{R}\in\mbox{LocalEQ}}\mathbb{E}_{{\bm{r}}\sim\mathcal{R}}[\mbox{Rev}({\bm{r}})]}{\sup_{{\bm{r}}\in\mathbb{R}_{\geq
0}^{K}}\mbox{ Rev}({\bm{r}})}.$

##  4 Hardness of equilibrium computation

In this section, we study the computational complexity of computing
equilibrium of our game. Our main result in this section is that we show that
even just finding the subgame equilibrium (Definition 1) for the bidders’
subgame is already computationally hard:

######  Theorem 1.

Finding the subgame equilibrium (Definition 1) is PPAD-hard.

We prove this by reduction from the problem of finding an approximate Nash
equilibrium for the 0-1 bimatrix game, which was shown to be PPAD-hard in
[12]. The basic idea of the proof is similar to that of the hardness result
for finding a pacing equilibrium for budget-constrained quasi-linear bidders
[11]. However, we have to handle many difficulties that are unique to tCPA
bidders. Most notably, in contrast to budget-constrained quasi-linear bidders,
whose bidding parameters are at most $1$, tCPA bidders do not have a natural
upper bound for their bids, and their bidding parameters can be arbitrarily
high when their tCPA constraints are not tight. We construct new gadgets that
force tCPA bidders’ bidding parameters to stay bounded but still leave a
controlled amount of ”slack” for them, so that they can bid on impressions
that are more expensive than their tCPA but not win all of them. We provide
the full reduction in the appendix.

Despite the computational hardness, we are able to prove tight revenue
guarantees that channels can achieve in the equilibrium, which we will present
in the subsequent sections.

##  5 Revenue and Price of Anarchy with no Publisher Reserves

In this section, we focus on the setting where impressions do not have
publisher-chosen reserve prices, i.e. $p_{i}=0$ for every $i\in I$. We study
the revenue guarantees that the channels can achieve in the local model where
each channel chooses their reserve price out of their own self-interest vs.
the global model where the channels cooperatively choose the reserve prices to
maximize their total revenue.

Our main results in this section are the following:

  * •

We establish a revenue guarantee (defined in Definition 3) in the local model
(Theorem 2).

  * •

Moreover, we prove that our revenue guarantee in the local model is _tight
even for the global model_ (Proposition 3).

  * •

Furthermore, as a corollary of the revenue guarantee in the local model, we
immediately get a lower bound for the price of anarchy (Theorem 3). We give a
matching upper bound for the price of anarchy (Theorem 4) and thus establish a
_tight separation between the local and global models_.

###  5.1 Revenue Guarantees

We begin by proving the main technical result of this section, which
establishes a revenue guarantee for the local model. It is PPAD-hard to
actually compute the equilibrium, as shown in Theorem 1. Nevertheless, we will
show that each channel can set a certain reserve price in order to guarantee
itself a decent amount of revenue, irrespective of the reserve prices set by
other channels.

To do this, we will show that each channel can set a reserve price which
ensures that its revenue is at least a certain fraction of the total budget of
unconstrained Budgeted bidders (Lemma 1 and Corollary 1). Then, we will show
that each channel can set a reserve price which ensures that its revenue is at
least a certain fraction of its contribution to the optimal liquid welfare
(Definition 2) from tCPA and QL bidders (Lemma 2 and Corollary 2). Finally, we
will put these together to get the final revenue guarantee (Theorem 2).

The main difficulty in this proof comes from Budgeted bidders who are
unconstrained, i.e. not spending their budget, at the equilibrium of the local
model. The contribution to optimal Liquid Welfare from tCPA and QL bidders can
be easily attributed to different channels (see the definition of
$W_{\tiny{\mbox{tCPA}}}^{*}(k)$ and $W_{\tiny{\mbox{QL}}}^{*}(k)$ in Lemma 2)
and there is a natural way for a channel to obtain a good fraction of its
contribution as revenue (see Lemma 2). However, there is no obvious
attribution for the contribution of Budgeted bidders to different channels,
and no obvious lower bound on the bid of Budgeted bidders. In order to get a
handle on unconstrained Budgeted bidders, we define the notion of Budget-
fraction.

######  Definition 5 (Budget-fraction $\beta_{j}$ and $\beta_{max}$,
$\beta_{min}$).

For a Budgeted bidder $j$, define their budget-fraction as
$\beta_{j}=\frac{B_{j}}{\sum_{i\in I}v_{j,i}}$, i.e., the ratio of their
budget to the sum of their values of all impressions. Also, define
$\beta_{max}=\max_{j\in J_{\tiny{\mbox{Budgeted}}}}\beta_{j}$ and
$\beta_{min}=\min_{j\in J_{\tiny{\mbox{Budgeted}}}}\beta_{j}$.

Intuitively, the budget-fraction for a Budgeted bidder plays a role similar to
the tCPA of a tCPA bidder. With this, we are ready to prove some key technical
claims that will help establish a lower bound on the bids of unconstrained
Budgeted bidders, which in turn will help us find a good reserve price for
these bidders.

### Key Claims

######  Claim 1.

In a subgame equilibrium (Definition 1), if a Budgeted bidder $j$ is
unconstrained, i.e. not spending all its budget, then they must be winning all
impressions $i$ with $v_{j,i}>0$ and cannot be tied with another unconstrained
Budgeted bidder on those impressions.

###### Proof.

Suppose for contradiction that a Budgeted bidder $j$ is unconstrained but does
not fully win certain impression $i$ (i.e., $x_{j,i}({\bm{r}})<1$) such that
$v_{j,i}>0$. Notice that Bidder $j$ can increase the bidding parameter
$\alpha_{j}$ without increasing the total spend until Bidder $j$ is tied for
(but does not fully win) some impression $i^{\prime}$ with
$v_{j,i^{\prime}}>0$. Such tie must occur, because otherwise, as Bidder $j$
increases $\alpha_{j}$, at some point Bidder $j$ will be tied for the
impression $i$. However, this contradicts item (4) of Definition 1, because
Bidder $j$ can strictly increase the utility by increasing
$x_{j,i^{\prime}}({\bm{r}})$ by a sufficiently small amount such that their
budget constraint is not violated. ∎

The next claim follows directly from Claim 1.

######  Claim 2.

In a subgame equilibrium, for any impression $i\in I$, there can be at most
one unconstrained Budgeted bidder $j$ with $v_{j,i}>0$.

Next we prove the following claim, which will be helpful in bounding revenue
against the optimal Liquid Welfare from unconstrained Budgeted bidders.

######  Claim 3.

If the final reserve price of an impression $i$ for a Budgeted bidder $j$
satisfies that $r_{j,i}<\beta_{j}v_{j,i}$, then impression $i$ will be sold
for a cost at least $r_{j,i}$ in the subgame equilibrium.

###### Proof.

We first show that unless impression $i$ is fully sold to bidder $j$ (in which
case the statement holds trivially because the cost of impression $i$ is at
least its reserve price $r_{j,i}$), Bidder $j$ will bid
$b_{j,i}\geq\beta_{j}v_{j,i}$ for impression $i$.

Suppose $b_{j,i}<\beta_{j}v_{j,i}$ for contradiction. Recall that $\alpha_{j}$
denotes the bidding parameter of Bidder $j$. Since $b_{j,i}=\alpha_{j}v_{j,i}$
is assumed to be less than $\beta_{j}v_{j,i}$, we get $\alpha_{j}<\beta_{j}$.
Moreover, because the total amount spent by Bidder $j$ is at most the sum of
their bids, we have that

$\mbox{Total amount spent by bidder }j\leq\sum_{i\in I}b_{j,i}=\sum_{i\in
I}\alpha_{j}v_{j,i}<\sum_{i\in I}\beta_{j}v_{j,i}=B_{j}.$

Thus, Bidder $j$ is unconstrained. By Claim 1, this bidder must be winning all
its impressions.

Now we have shown that $b_{j,i}\geq\beta_{j}v_{j,i}$, which is by our
assumption strictly greater than $r_{j,i}$. Thus, it follows from item (2) of
Definition 1 that impression $i$ will be fully sold in the subgame equilibrium
(for a cost that is at least $b_{j,i}>r_{j,i}$ because of item (1) of
Definition 1). ∎

The following claim, analogous to the claim above, will be used to bound
revenue against the optimal Liquid Welfare from tCPA and QL bidders.

######  Claim 4.

If the final reserve price (i.e., in the cost space) of impression $i$ for a
tCPA bidder $j$ (recall this is denoted by $r_{j,i}$ in the model section)
satisfies that $r_{j,i}<T_{j}v_{j,i}$, then impression $i$ will be sold for a
cost of at least $r_{j,i}$ in the subgame equilibrium. Similarly, if the final
reserve price of impression $i$ for a QL bidder $j$ satisfies that
$r_{j,i}<v_{j,i}$, then impression $i$ will be sold for a cost of at least
$r_{j,i}$ in the subgame equilibrium.

###### Proof.

By Assumption 1, a tCPA bidder $j$ bids $b_{j,i}({\bm{r}})\geq
T_{j}v_{j,i}>r_{j,i}$ on impression $i$. Thus, by item (2) of Definition 1,
impression $i$ will be fully sold in the subgame equilibrium (for a cost that
is at least $r_{j,i}$ because of item (1) of Definition 1). An analogous
argument holds for the case of QL bidder. ∎

Next, we first lower bound each channel’s revenue against the optimal Liquid
Welfare contribution from Budgeted bidders (Lemma 1 and Corollary 1), and then
we lower bound each channel’s revenue against the welfare contribution from
tCPA and QL bidders (Lemma 2 and Corollary 2). Finally, we will put these
together to get a lower bound on the revenue guarantee (Theorem 2).

### Welfare from Budgeted Bidders

######  Lemma 1.

Let $E$ be any subgame equilibrium given any reserve prices. Define the
following:

  * •

Let $J^{E}_{C}$ be the subset of Budgeted bidders who are constrained, i.e.
are spending their entire budget in the equilibrium $E$.

  * •

Let $J^{E}_{U}$ be the subset of Budgeted bidders who are unconstrained, i.e.
are spending strictly less than their budget in the equilibrium $E$.

  * •

For Channel $k$ and Budgeted bidder $j$, let $\rho(k,j)=\frac{\sum_{i\in
I_{k}}v_{j,i}}{\sum_{i\in I}v_{j,i}}$ be the ratio of the total value of
impressions in $I_{k}$ for Bidder $j$ to the total value of all impressions in
$I$ for Bidder $j$.

Then, for any $\varepsilon>0$,

  1. 1.

in the equilibrium $E$, the total revenue of all the channels from a Bidder
$j\in J^{E}_{C}$ is no less than their budget $B_{j}$,

  2. 2.

and moreover, if Channel $k$ could set bidder-specific reserve prices
$r_{k}(j)=(1-\varepsilon)\beta_{j}$ for each Budgeted bidder $j$ (recall
$\beta_{j}$ is the budget-fraction in Definition 5), then regardless of other
channels’ reserve prices, in the resulting subgame equilibrium (this is not
necessarily $E$), Channel $k$ can obtain a revenue of at least

$\sum_{j\in J^{E}_{U}}(1-\varepsilon)\rho(k,j)B_{j},$

  3. 3.

and furthermore, Channel $k$ can set a uniform reserve price $r_{k}$ which is
independent of $E$ such that regardless of other channels’ reserve prices, in
the resulting subgame equilibrium (not necessarily $E$), Channel $k$ will
obtain a revenue of at least

$\frac{\sum_{j\in
J^{E}_{U}}(1-\varepsilon)\rho(k,j)B_{j}}{2\max\big{\\{}1,\big{\lceil}\log\frac{\beta_{max}}{\beta_{min}}\big{\rceil}\big{\\}}}.$

###### Proof.

  1. 1.

Since bidders $j\in J^{E}_{C}$ are spending their entire budget in $E$ (by
definition of $J^{E}_{C}$), the total revenue of all channels from them is
equal to their budget.

  2. 2.

Consider any equilibrium $E_{r}$ resulting from Channel $k$’s bidder-specific
reserve prices given in the statement and arbitrary reserve prices of other
channels (note $E_{r}$ is unrelated to $E$). Consider any impression $i\in
I_{k}$. Since Channel $k$ has set a bidder-specific reserve price of
$(1-\varepsilon)\beta_{j}$ for each Budgeted bidder $j$, the reserve price of
impression $i$ for Budgeted bidder $j$ is
$r_{j,i}=(1-\varepsilon)\beta_{j}v_{j,i}<\beta_{j}v_{j,i}$. Then, by Claim 3,
each impression $i$ is sold for a price of at least
$r_{j,i}=(1-\varepsilon)\beta_{j}v_{j,i}$ in the equilibrium $E_{r}$ for any
$j\in J_{\tiny{\mbox{Budgeted}}}$. That is,

$\textrm{the revenue of Channel $k$ in the equilibrium $E_{r}$}\geq\sum_{i\in
I_{k}}\max_{j\in J_{\tiny{\mbox{Budgeted}}}}(1-\varepsilon)\beta_{j}v_{j,i}.$
(4)

Now let $I_{k}(j)\subseteq I_{k}$ denote the set of the impressions $i\in
I_{k}$ such that $v_{j,i}>0$. By Claim 2, if $j$ and $j^{\prime}$ are two
bidders unconstrained in the equilibrium $E$, then $I_{k}(j)$ and
$I_{k}(j^{\prime})$ are disjoint.

Hence, we have that

$\displaystyle\sum_{i\in I_{k}}\max_{j\in
J_{\tiny{\mbox{Budgeted}}}}(1-\varepsilon)\beta_{j}v_{j,i}$
$\displaystyle\geq\sum_{j\in J^{E}_{U}}\sum_{i\in
I_{k}(j)}(1-\varepsilon)\beta_{j}v_{j,i}$ (5) $\displaystyle=\sum_{j\in
J^{E}_{U}}(1-\varepsilon)\beta_{j}\sum_{i\in I_{k}(j)}v_{j,i}$ (6)
$\displaystyle=\sum_{j\in
J^{E}_{U}}(1-\varepsilon)\beta_{j}\rho(k,j)\sum_{i\in I}v_{j,i}$ (7)
$\displaystyle=\sum_{j\in J^{E}_{U}}(1-\varepsilon)\rho(k,j)B_{j},$ (8)

which finishes the proof by Inequality (4).

  3. 3.

The high-level idea for setting a good uniform reserve price is to bucketize
the reserve prices and pick the one with the highest revenue potential.
Specifically, we divide Budgeted bidders into the following buckets:

$J^{s}_{\tiny{\mbox{Budgeted}}}=\\{j:j\in J_{\tiny{\mbox{Budgeted}}}\mbox{ and
}2^{s}\beta_{min}\leq\beta_{j}\leq 2^{s+1}\beta_{min}\\}$

for
$s\in\\{0\\}\cup\left[\lceil\log\frac{\beta_{max}}{\beta_{min}}\rceil-1\right]$
(recall $\beta_{max},\beta_{min}$ are the largest and smallest budget-
fractions respectively defined in Definition 5). We observe that if Channel
$k$ sets its uniform reserve price to $(1-\varepsilon)2^{s}\beta_{min}$, then
for bidders $j\in J^{s}_{\tiny{\mbox{Budgeted}}}$, it holds that
$r_{j,i}=(1-\varepsilon)2^{s}\beta_{min}v_{j,i}<\beta_{j}v_{j,i}$ for all
impressions $i\in I_{k}$. Thus, by Claim 3, each impression $i\in I_{k}$ will
get sold for a price of at least $\max_{j\in
J^{s}_{\tiny{\mbox{Budgeted}}}}r_{j,i}=\max_{j\in
J^{s}_{\tiny{\mbox{Budgeted}}}}(1-\varepsilon)2^{s}\beta_{min}v_{j,i}\geq\max_{j\in
J^{s}_{\tiny{\mbox{Budgeted}}}}\frac{1-\varepsilon}{2}\beta_{j}v_{j,i}$ (the
inequality is by bucketization) in the subgame equilibrium $E_{r}$ that
results from Channel $k$ setting a uniform reserve price of
$(1-\varepsilon)2^{s}\beta_{min}$ and arbitrary reserve prices set by other
channels. Thus, the revenue of Channel $k$ from setting a uniform reserve
price to $(1-\varepsilon)2^{s}\beta_{min}$

$\displaystyle\mbox{Rev}_{k}((1-\varepsilon)2^{s}\beta_{min})$
$\displaystyle\geq\sum_{i\in I_{k}}\max_{j\in
J^{s}_{\tiny{\mbox{Budgeted}}}}\frac{1-\varepsilon}{2}\beta_{j}v_{j,i}.$ (9)

Now let $I_{k}(j)\subseteq I_{k}$ denote the set of impressions $i\in I_{k}$
such that $v_{j,i}>0$. Then, by Claim 2, $I_{k}(j)$ and $I_{k}(j^{\prime})$
are disjoint for two unconstrained Budgeted bidders $j\neq j^{\prime}$ in the
equilibrium $E$. Hence, we have that

$\displaystyle\sum_{s}\sum_{i\in I_{k}}\max_{j\in
J^{s}_{\tiny{\mbox{Budgeted}}}}\frac{1-\varepsilon}{2}\beta_{j}v_{j,i}$
$\displaystyle\geq\sum_{s}\sum_{j\in J^{E}_{U}\cap
J^{s}_{\tiny{\mbox{Budgeted}}}}\sum_{i\in
I_{k}(j)}\frac{1-\varepsilon}{2}\beta_{j}v_{j,i}$ $\displaystyle=\sum_{j\in
J^{E}_{U}}\sum_{i\in I_{k}(j)}\frac{1-\varepsilon}{2}\beta_{j}v_{j,i}$
$\displaystyle\geq\frac{1-\varepsilon}{2}\sum_{j\in J^{E}_{U}}\rho(k,j)B_{j},$
(10)

where the last inequality follows from the same derivation as in Inequalities
(5-8).

Finally, let
$s^{*}=\operatorname*{arg\,max}_{s\in\\{0\\}\cup\left[\lceil\log\frac{\beta_{max}}{\beta_{min}}\rceil-1\right]}\sum_{i\in
I_{k}}\max_{j\in
J^{s}_{\tiny{\mbox{Budgeted}}}}\frac{1-\varepsilon}{2}\beta_{j}v_{j,i}$. Then,
we have that the revenue of Channel $k$ by setting a uniform reserve price
$r_{k}^{*}=2^{s^{*}}\beta_{min}$ (notice $r_{k}^{*}$ is indeed independent of
$E$) is

$\displaystyle\mbox{Rev}_{k}((1-\varepsilon)2^{s^{*}}\beta_{min})$
$\displaystyle\geq\sum_{i\in I_{k}}\max_{j\in
J^{s}_{\tiny{\mbox{Budgeted}}}}\frac{1-\varepsilon}{2}\beta_{j}v_{j,i}$ (By
Inequality (9)) $\displaystyle\geq\frac{\sum_{s}\sum_{i\in I_{k}}\max_{j\in
J^{s}_{\tiny{\mbox{Budgeted}}}}\frac{1-\varepsilon}{2}\beta_{j}v_{j,i}}{\max\big{\\{}1,\big{\lceil}\log\frac{\beta_{max}}{\beta_{min}}\big{\rceil}\big{\\}}}$
(By definition of $s^{*}$)
$\displaystyle\geq\frac{\frac{1-\varepsilon}{2}\sum_{j\in
J^{E}_{U}}\rho(k,j)B_{j}}{\max\big{\\{}1,\big{\lceil}\log\frac{\beta_{max}}{\beta_{min}}\big{\rceil}\big{\\}}}$
$\displaystyle\text{(By Inequality~{}\eqref{eq:revk_sum_over_buckets})}.$

∎

Item (3) in Lemma 1 implies the following corollary:

######  Corollary 1.

Define $\rho(k,j)$ as in Lemma 1. Let $\mathcal{R}=(\mathcal{R}_{k})_{k\in K}$
be any mixed-strategy equilibrium of the channels’ game (i.e., S0), and let
$E({\bm{r}})$ be the subgame equilibrium given any reserve prices ${\bm{r}}$
in the support of the channels’ mixed strategies. Then, the expected revenue
of Channel $k$ in the mixed-strategy equilibrium $\mathcal{R}$ is at least

$\mathbf{E}_{{\bm{r}}\sim\mathcal{R}}\left[\frac{\sum_{j\in
J^{E({\bm{r}})}_{U}}(1-\varepsilon)\rho(k,j){\mbox{B}}_{j}}{2\max\big{\\{}1,\big{\lceil}\log\frac{\beta_{max}}{\beta_{min}}\big{\rceil}\big{\\}}}\right].$

### Welfare from tCPA and QL Bidders

######  Lemma 2.

Let ${\bm{x}}^{*}$ be a welfare maximizing allocation (i.e., ${\bm{x}}^{*}$ is
s.t. $Wel^{*}=Wel({\bm{x}}^{*})$ in Definition 2) and

  * •

let $W_{\tiny{\mbox{tCPA}}}^{*}(k)$ be the liquid welfare generated by the
impressions in $I_{k}$ allocated to tCPA bidders in $x^{*}$, i.e.,

$W_{\tiny{\mbox{tCPA}}}^{*}(k):=\sum_{j\in J_{\tiny{\mbox{tCPA}}}}\sum_{i\in
I_{k}}T_{j}v_{j,i}x^{*}_{j,i},$

  * •

and let $W_{\tiny{\mbox{QL}}}^{*}(k)$ be the liquid welfare generated by the
impressions in $I_{k}$ allocated to quasi-linear bidders in $x^{*}$, i.e.,

$W_{\tiny{\mbox{QL}}}^{*}(k):=\sum_{j\in J_{\tiny{\mbox{QL}}}}\sum_{i\in
I_{k}}v_{j,i}x^{*}_{j,i}.$

Then, for any $\varepsilon>0$,

  1. 1.

if Channel $k$ could set the bidder-specific reserve prices (also in the cost-
per-unit-value space) $r_{k}(j)$ for each tCPA or QL bidder $j$ as follows:

$r_{k}(j)=\begin{cases}(1-\varepsilon)T_{j}&\text{if $j$ is a ${\mbox{tCPA}}$
bidder}\\\ 1-\varepsilon&\text{if $j$ is a ${\mbox{QL}}$ bidder},\end{cases}$

then Channel $k$ obtains a revenue at least
$(1-\varepsilon)(W_{\tiny{\mbox{tCPA}}}^{*}(k)+W_{\tiny{\mbox{QL}}}^{*}(k))$
regardless of what other channels do,

  2. 2.

and moreover, we let $T_{max}=\max_{j\in J_{\tiny{\mbox{tCPA}}}}T_{j}$ and let
$T_{min}=\min_{j\in J_{\tiny{\mbox{tCPA}}}}T_{j}$, and then Channel $k$ can
set a uniform reserve price $r_{k}$ s.t. Channel $k$ obtains a revenue at
least

$\frac{(1-\varepsilon)(W_{\tiny{\mbox{tCPA}}}^{*}(k)+W_{\tiny{\mbox{QL}}}^{*}(k))}{2+2\max\big{\\{}1,\big{\lceil}\log\frac{T_{max}}{T_{min}}\big{\rceil}\big{\\}}}$

regardless of what other channels do.

###### Proof.

  1. 1.

Fix Channel $k$’s bidder-specific reserve prices as in the assumption and
consider any subgame equilibrium. For any impression $i\in I_{k}$, let Bidder
$j=\operatorname*{arg\,max}_{\ell\in J_{\tiny{\mbox{tCPA}}}\textrm{ s.t.
}x^{*}_{\ell,i}>0}T_{\ell}v_{\ell,i}$, and let Bidder
$q=\operatorname*{arg\,max}_{\ell\in J_{\tiny{\mbox{QL}}}\textrm{ s.t.
}x^{*}_{\ell,i}>0}v_{\ell,i}$. Since
$r_{j,i}=r_{k}(j)v_{j,i}=(1-\varepsilon)T_{j}v_{j,i}<T_{j}v_{j,i}$, it follows
from Claim 4 that impression $i$ will be sold for a cost of at least
$r_{j,i}=(1-\varepsilon)T_{j}v_{j,i}$. Similarly, since
$r_{q,i}=r_{k}(q)v_{q,i}=(1-\varepsilon)v_{q,i}<v_{q,i}$, it follows from
Claim 4 that impression $i$ will be sold for a cost of at least
$r_{q,i}=(1-\varepsilon)v_{q,i}$. Moreover, note that the contribution of
impression $i$ to $W_{\tiny{\mbox{tCPA}}}^{*}(k)+W_{\tiny{\mbox{QL}}}^{*}(k)$
is at most $\max\\{v_{q,i},T_{j}v_{j,i}\\}$, and we have shown impression $i$
will be sold for at least $(1-\varepsilon)$-fraction of this amount, it
follows that channel $k$’s revenue is at least
$(1-\varepsilon)(W_{\tiny{\mbox{tCPA}}}^{*}(k)+W_{\tiny{\mbox{QL}}}^{*}(k))$.

  2. 2.

The high-level idea for setting a good uniform reserve price is again to
bucketize the bidder-specific reserve prices used above and set the uniform
reserve price $r_{k}$ to the lower end of the bucket that has the highest
revenue potential. Specifically, we divide all the tCPA bidders into the
following buckets:

$J^{s}_{\tiny{\mbox{tCPA}}}=\\{j:j\in J_{\tiny{\mbox{tCPA}}},2^{s}T_{min}\leq
T_{j}\leq 2^{s+1}T_{min}\\}$

for $s\in\\{0\\}\cup\left[\lceil\log\frac{T_{max}}{T_{min}}\rceil-1\right]$.

As before, for any impression $i\in I_{k}$, let bidder
$j=\operatorname*{arg\,max}_{\ell\in J_{\tiny{\mbox{tCPA}}}\textrm{ s.t.
}x^{*}_{\ell,i}>0}T_{\ell}v_{\ell,i}$ and bidder
$q=\operatorname*{arg\,max}_{\ell\in J_{\tiny{\mbox{QL}}}\textrm{ s.t.
}x^{*}_{\ell,i}>0}v_{\ell,i}$, and notice that the contribution of impression
$i$ to $W_{\tiny{\mbox{tCPA}}}^{*}(k)+W_{\tiny{\mbox{QL}}}^{*}(k)$ is at most
$\max\\{v_{q,i},T_{j}v_{j,i}\\}$.

If $T_{j}v_{j,i}>v_{q,i}$, let $s$ be such that $j\in
J^{s}_{\tiny{\mbox{tCPA}}}$. Suppose Channel $k$ sets a reserve price of
$r_{k}=(1-\varepsilon)2^{s}T_{min}$ which is strictly less than $T_{j}$
because of the bucketization. Then, by Claim 4, impression $i$ will be sold at
a cost at least
$(1-\varepsilon)2^{s}T_{min}v_{j,i}\geq\frac{1-\varepsilon}{2}T_{j}v_{j,i}$ in
the subgame equilibrium, where the inequality is because of the bucketization.

If $v_{q,i}\geq T_{j}v_{j,i}$, suppose Channel $k$ sets a reserve price
$r_{k}=1-\varepsilon$. Then, by Claim 4, impression $i$ will be sold at a cost
at least $v_{q,i}$ in the subgame equilibrium.

Now we put these two cases together. Let $Rev_{k}(r_{k})$ be the revenue of
Channel $k$ at the subgame equilibrium if Channel $k$ sets a uniform reserve
price $r_{k}$ (regardless of the reserve prices of other channels). Then,
summing over all the buckets $s$, we have

$\sum_{r_{k}\in\\{1-\varepsilon,\,T_{min}\\}\cup\left\\{2^{s}T_{min}\mid\,s\in\left[\lceil\log\frac{T_{max}}{T_{min}}\rceil-1\right]\right\\}}Rev_{k}(r_{k})\geq\frac{1-\varepsilon}{2}(W_{\tiny{\mbox{tCPA}}}^{*}(k)+W_{\tiny{\mbox{QL}}}^{*}(k)),$

because as we have shown in the above case analysis, all the buckets together
cover at least $\frac{1-\varepsilon}{2}$-fraction of the liquid welfare of
each impression’s contribution to
$W_{\tiny{\mbox{tCPA}}}^{*}(k)+W_{\tiny{\mbox{QL}}}^{*}(k)$.

Let
$r^{*}_{k}=\operatorname*{arg\,max}_{r_{k}\in\\{1-\varepsilon,\,T_{min}\\}\cup\left\\{2^{s}T_{min}\mid\,s\in\left[\lceil\log\frac{T_{max}}{T_{min}}\rceil-1\right]\right\\}}Rev_{k}(r_{k})$.
Then, by setting a reserve price of $r^{*}_{k}$, Channel $k$ can get a revenue
of at least

$\frac{(1-\varepsilon)(W_{\tiny{\mbox{tCPA}}}^{*}(k)+W_{\tiny{\mbox{QL}}}^{*}(k))}{2+2\max\big{\\{}1,\big{\lceil}\log\frac{T_{max}}{T_{min}}\big{\rceil}\big{\\}}}.$

∎

If Channel $k$ can always get certain amount of revenue by setting a
particular uniform reserve price $r_{k}$ regardless of what other channels do,
then Channel $k$’s revenue at any mixed-strategy equilibrium of the channels’
game (i.e., stage (S0) of the full game) is at least the same amount (because
otherwise Channel $k$ will deviate to the uniform reserve price $r_{k}$).
Thus, item (2) in Lemma 2 implies the following corollary:

######  Corollary 2.

Let $W_{\tiny{\mbox{tCPA}}}^{*}(k)$ and $W_{\tiny{\mbox{QL}}}^{*}(k)$ be
defined as in Lemma 2 above. Then, for any $\varepsilon>0$, at any mixed-
strategy equilibrium of the channels’ game (S0), the expected revenue of
channel $k$ is at least

$\frac{(1-\varepsilon)(W_{\tiny{\mbox{tCPA}}}^{*}(k)+W_{\tiny{\mbox{QL}}}^{*}(k))}{2+2\max\big{\\{}1,\big{\lceil}\log\frac{T_{max}}{T_{min}}\big{\rceil}\big{\\}}}.$

### The Final Revenue Guarantee

######  Theorem 2.

For any $\varepsilon>0$,

$RevG(Local)\geq\frac{1-\varepsilon}{3+2\max\big{\\{}1,\big{\lceil}\log\frac{T_{max}}{T_{min}}\big{\rceil}\big{\\}}+2\max\big{\\{}1,\big{\lceil}\log\frac{\beta_{max}}{\beta_{min}}\big{\rceil}\big{\\}}}.$

###### Proof.

Let $\mathcal{R}=(\mathcal{R}_{k})_{k\in K}$ be any mixed-strategy equilibrium
of the channels’ game, and let $E({\bm{r}})$ denote the subgame equilibrium
given any reserve prices ${\bm{r}}$ in the support of the channels’ mixed
strategies. Let ${\bm{x}}^{*}$ be the liquid welfare maximizing allocation
(i.e., ${\bm{x}}^{*}$ is s.t. $Wel^{*}=Wel({\bm{x}}^{*})$).

By Corollary 2, the expected revenue of Channel $k$ in the equilibrium
$\mathcal{R}$, denoted by $\mbox{Rev}_{k}[\mathcal{R}]$, is

$\mbox{Rev}_{k}[\mathcal{R}]\geq\frac{(1-\varepsilon)(W_{\tiny{\mbox{tCPA}}}^{*}(k)+W_{\tiny{\mbox{QL}}}^{*}(k))}{2+2\max\big{\\{}1,\big{\lceil}\log\frac{T_{max}}{T_{min}}\big{\rceil}\big{\\}}},$

where $W_{\tiny{\mbox{tCPA}}}^{*}(k)$ and $W_{\tiny{\mbox{QL}}}^{*}(k)$ are
defined as in Lemma 2.

Thus, the expected total revenue of all channels, denoted by
$\mbox{Rev}[\mathcal{R}]$, is

$\mbox{Rev}[\mathcal{R}]\geq\frac{(1-\varepsilon)(W_{\tiny{\mbox{tCPA}}}^{*}+W_{\tiny{\mbox{QL}}}^{*})}{2+2\max\big{\\{}1,\big{\lceil}\log\frac{T_{max}}{T_{min}}\big{\rceil}\big{\\}}},$
(11)

where $W_{\tiny{\mbox{tCPA}}}^{*}:=\sum_{k\in K}W_{\tiny{\mbox{tCPA}}}^{*}(k)$
and $W_{\tiny{\mbox{QL}}}^{*}:=\sum_{k\in K}W_{\tiny{\mbox{QL}}}^{*}(k)$
denote the total contributions of tCPA and QL bidders to the liquid welfare of
$x^{*}$ respectively.

Let $\rho(k,j)$ be as defined in Lemma 1. Then, by Corollary 1,

$\mbox{Rev}_{k}[\mathcal{R}]\geq\mathbf{E}_{{\bm{r}}\sim\mathcal{R}}\left[\frac{\sum_{j\in
J^{E({\bm{r}})}_{U}}(1-\varepsilon)\rho(k,j)B_{j}}{2\max\big{\\{}1,\big{\lceil}\log\frac{\beta_{max}}{\beta_{min}}\big{\rceil}\big{\\}}}\right].$

Summing over all channels, we get

$\mbox{Rev}[\mathcal{R}]\geq\sum_{k}\mathbf{E}_{{\bm{r}}\sim\mathcal{R}}\left[\frac{\sum_{j\in
J^{E({\bm{r}})}_{U}}(1-\varepsilon)\rho(k,j)B_{j}}{2\max\big{\\{}1,\big{\lceil}\log\frac{\beta_{max}}{\beta_{min}}\big{\rceil}\big{\\}}}\right]=\mathbf{E}_{{\bm{r}}\sim\mathcal{R}}\left[\frac{\sum_{j\in
J^{E({\bm{r}})}_{U}}(1-\varepsilon)B_{j}}{2\max\big{\\{}1,\big{\lceil}\log\frac{\beta_{max}}{\beta_{min}}\big{\rceil}\big{\\}}}\right].$
(12)

Also, by item (1) of Lemma 1, we have that

$\mbox{Rev}[\mathcal{R}]\geq\mathbf{E}_{{\bm{r}}\sim\mathcal{R}}\left[\sum_{j\in
J^{E({\bm{r}})}_{C}}B_{j}\right].$ (13)

Notice that

$Wel^{*}\leq W_{\tiny{\mbox{tCPA}}}^{*}+W_{\tiny{\mbox{QL}}}^{*}+\sum_{j\in
J_{\tiny{\mbox{Budgeted}}}}B_{j},$

and then the theorem follows from Inequalities (11), (12) and (13). ∎

Combining Theorem 2 with Fact 2, we get the following corollary:

######  Corollary 3.

For any $\varepsilon>0$,

$RevG(Global)\geq\frac{1-\varepsilon}{3+2\max\big{\\{}1,\big{\lceil}\log\frac{T_{max}}{T_{min}}\big{\rceil}\big{\\}}+2\max\big{\\{}1,\big{\lceil}\log\frac{\beta_{max}}{\beta_{min}}\big{\rceil}\big{\\}}}.$

Finally, we show that the above revenue guarantees in the local and global
models are both tight up to a constant factor by constructing an example using
the well-known ”equal-revenue” trick.

######  Proposition 3.

For the single-channel setting, there is an instance where
$RevG(Global)=RevG(Local)=O(1/(\log(T_{max}/T_{min})+\log(\beta_{max}/\beta_{min})))$.

###### Proof.

Since there is only one channel, $RevG(Global)=RevG(Local)$.

Consider $2^{\ell}$ tCPA bidders with tCPAs $1/2^{\ell}$ for
$\ell=0,\ldots,w_{1}-1$, each interested in a unique impression with a value
of $1$ (i.e. their value for every other impression is 0, and everyone else’s
value for their impression is 0). Similarly, there are $2^{\ell}$ Budgeted
bidders with budgets $1/2^{\ell}$ for $\ell=0,\ldots,w_{2}-1$, each interested
in a unique impression with a value of $1$ (i.e. their value for every other
impression is 0, and everyone else’s value for their impression is 0). Optimal
liquid welfare is $w_{1}+w_{2}$ obtained by giving everyone their unique
impression. The best uniform reserve price cannot get a revenue more than $4$.
This shows that $RevG(Global)\leq
4/(w_{1}+w_{2})=4/(2+\log\frac{T_{max}}{T_{min}}+\log\frac{\beta_{max}}{\beta_{min}})$.
∎

###  5.2 Price of Anarchy

In this subsection, we study how much total revenue the channels lose in the
local model where they set their uniform reserve prices out of their own self-
interest compared to the global model where they choose the reserve prices
cooperatively. Specifically, we consider the standard notion – price of
anarchy $PoA$ (Definition 4). First, we observe that the revenue guarantee
from Theorem 2 immediately implies a lower bound for the $PoA$:

######  Theorem 3.

For any $\varepsilon>0$,

$PoA\geq\frac{1-\varepsilon}{3+2\max\big{\\{}1,\big{\lceil}\log\frac{T_{max}}{T_{min}}\big{\rceil}\big{\\}}+2\max\big{\\{}1,\big{\lceil}\log\frac{\beta_{max}}{\beta_{min}}\big{\rceil}\big{\\}}}.$

###### Proof.

By definition of $PoA$ (Definition 4), $PoA=\frac{RevG(Local)}{RevG(Global)}$.
By Fact 2, $RevG(Global)\leq 1$. It follows that $PoA\geq RevG(Local)$, and
then the proof finishes by applying Theorem 2. ∎

Next, we show that the $PoA$ lower bound in Theorem 3 is tight (up to a
constant factor).

######  Theorem 4.

There is an instance with two channels such that
$PoA=O(1/(\log(T_{max}/T_{min})+\log(\beta_{max}/\beta_{min})))$.

##### The high-level idea:

We first construct an “equal-revenue” instance (which consists of many tCPA
bidders $J_{1}$ with geometrically decreasing tCPAs, each interested in a
unique impression owned by Channel $k_{1}$) as in the proof of Proposition 3.
For this “equal-revenue” instance, Channel $k_{1}$ cannot simultaneously get
good revenues from all the bidders in $J_{1}$ by setting a uniform reserve
price.

Now the key idea is to introduce another Channel $k_{2}$ and another tCPA
bidder $j_{2}\notin J_{1}$, such that Channel $k_{2}$ only owns one
impression, for which only bidder $j_{2}$ has strictly positive value.
Moreover, Bidder $j_{2}$ has a value for each impression $i$ in channel
$k_{1}$, and Bidder $j_{2}$’s value for impression $i$ is carefully chosen to
be proportional to the tCPA of the bidder in $J_{1}$ who is interested in
impression $i$. Thus, if Bidder $j_{2}$ makes a uniform bid (in the cost-per-
unit-value space), it results into non-uniform bids (in the cost space) for
the impressions in Channel $k_{1}$, which are proportional to the tCPAs of
bidders in $J_{1}$. We can think of these non-uniform bids as non-uniform
bidder-specific reserve prices for bidders in $J_{1}$, which are proportional
to their tCPAs. Thus, we are able to extract the full revenue from all the
bidders in $J_{1}$ (similar to item (1) of Lemma 2).

Finally, we just need to argue the above idea can only be successfully applied
in the global model but not in the local model. This is because in the local
model, Channel $k_{2}$ sets a high reserve price for its sole impression in
order to profit more from bidder $j_{2}$, and as a result, Bidder $j_{2}$ does
not have enough “slack” to make a sufficiently high uniform bid to incur
sufficiently high bidder-specific reserve prices for bidders in $J_{1}$.

The construction of the instance with Budgeted bidders uses essentially the
same idea as above. The full proof is provided in Appendix C.

As a corollary of Theorem 3 and Theorem 4, we have the following tight price
of anarchy:

######  Theorem 5 (Price of Anarchy).

$PoA=\Theta(1/(\log(T_{max}/T_{min})+\log(\beta_{max}/\beta_{min})))$.

##  6 Price of Anarchy with Publisher Reserves

This section studies the general version of the model where a publisher,
owning impression $i$, sets a minimum price $p_{i}$ for the impression to be
sold.777Recall that the price $p_{i}$ is also in the cost-per-unit-value
space. The main finding we obtain is that Theorem 5 dramatically depends on
not having publisher prices. We show that with publisher prices and general
channels, $PoA=0$ in the worst case (Theorem 6).

We then restrict our attention to an important subclass of instances where
channels are scaled copy of each other. That is, channels share a set of a
homogeneous set of impressions and differ on the revenue share each owns. In
this context, we show that $PoA$ has non-trivial lower bound only if there is
one bidder in the auction. In this case, $PoA=1/|K|$, and hence, depends on
the number of channels in the game in contrast to our results in Section 5.

### General Channels

We now present the main result of the section for the general case when
channels can have arbitrary asymmetries for the impressions they own with
arbitrary publisher reserve prices.

######  Theorem 6.

If publishers can set arbitrary minimum prices on their impressions, then
there is an instance for which $PoA=0$.

###### Proof.

Consider the following instance with two channels and one bidder who is a tCPA
bidder with a target constraint $T=1$. Channel 1 has only one impression to
sell. This impression does not have any publisher pricing constraint
($p_{i}=0$). Channel 2 has $q$ impressions to sell, each of these impressions
has the same publisher pricing constraint $p_{i}=1+1/q$. The bidder’s
valuation for all impressions is the same, i.e., $v_{i}=1$ for all $i\in I$.

We assert that in the global model, it is optimal to set reserve prices equal
to zero for both channels. Indeed, with no reserve prices, the bidder can
purchase all impressions since she gets a value of $1+q$ for a total cost of
$q\cdot(1+1/q)=1+q$. This is the optimal solution for the global model as the
total revenue is exactly the optimal liquid welfare.

On the other hand, in the local model, it is a strictly dominant strategy for
Channel 1 to set a uniform reserve $r_{1}=1$: if $r_{1}>1$, Channel 1 gets
zero revenue. If $r_{1}\leq 1$, the bidder purchases its impression, which
leads to a revenue of $r_{1}$. Thus, Channel 1 strictly prefers to set a
reserve price of $r_{1}=1$. Because of $r_{1}=1$, the bidder cannot afford to
buy any impression of Channel 2 since the cost of each impression is at least
$1+1/q$. Thus, in this equilibrium, the bidder submits a uniform bid of $1$,
gets only the impressions sold by Channel 1, and the global revenue is $1$.

Therefore from this instance we have that $RevG(Local)/RevG(Global)\leq
1/(1+q)$. We conclude the proof by taking $q\to\infty$. ∎

The intuition behind the previous result comes from instances where some of
the channels have high publisher prices relative to the bidder’s tCPA targets
while some other channels do not have publisher prices. In these instances, in
the global model, channels benefit by keeping low reserve prices in the cheap
channels (without publisher reserves) as they provide subsidy to the tCPA
bidders to buy impressions from the expensive channels. However, when the
cheap channels are myopic, they would like to raise their reserve prices to
increase their local revenue. This local behavior negatively impacts the
revenue of the expensive channels, which in turn, is negative for all
channels.

Given that the reason for the previous negative $PoA$ result is the asymmetry
of the publisher prices on the different channels, in what follows we restrict
our $PoA$ analysis for a special subclass where channels are scaled versions
of each other.

### Scaled Channels

The scaled channels model consists of weights
$\bm{\gamma}=(\gamma_{1},\ldots,\gamma_{k})\in\Delta([0,1]^{K})$
888$\Delta([0,1]^{K}$ is the unit simplex in $\mathbb{R}^{K}$ so that Channel
$k$ owns a fraction $\gamma_{k}$ of each impression $i\in I$.999For simplicity
of the exposition we assume that impressions are divisible. A similar model
with non-divisible impressions would assume that each impression $i$ is
duplicated so that Channel $k$ owns a fraction $\gamma_{k}$ of those
duplicates.

The first result shows that, surprisingly, so long as there are more than one
bidder participating in the auctions, then $PoA=0$ in the worst case.

######  Theorem 7.

For the scaled channels models if there are two or more bidders participating
in the auctions, then there is an instance for which $PoA=0$.

The instance we construct (deferred to Appendix D) consists of two channels
and two tCPA bidders. The idea of the instance is that the main source of
revenue for the channels comes from Bidder 1 buying the expensive impressions,
those with high publisher reserve price. Bidder 1 needs enough slack to be
able to purchase those expensive impressions. Thus, Bidder 1 needs to buy
enough cheap impressions. However, the cheap impressions may have a high price
if Bidder 2 sets a high bid. Bidder 2 can only set a high bid if, instead, it
has enough slack from (other) cheap impressions. The crux of the argument is
that, in the global model, by setting a sufficiently high reserve price, the
channels can avoid Bidder 2 to have enough slack. This, in turn, allows Bidder
$1$ to have slack to buy the expensive impressions. On the contrary, for the
local models, there is an equilibrium where both channels set a low reserve.
This prevents Bidder 1 to buy expensive impressions because Bidder 2 is
setting a high bid and removing Bidder 1’s slack.

As a corollary of this instance, we show that in the autobidding framework
setting a high reserve price like in the global model not only increases
revenue but also increases the welfare. This contrasts with the classic
profit-maximizing framework where there is a negative correlation between high
reserve prices and welfare.

We finish this section by showing that for the case of only one bidder
participating across all channels the $PoA$ is always strictly positive (for
pure-strategy equilibria).

######  Theorem 8.

If there is only a single bidder, then for pure-strategy equilibria we have
that $PoA=\frac{1}{|K|}$, where $|K|$ is the number of channels in the game.

We defer the proof to Appendix D. We note that in contrast to the results of
Section 5 where the $PoA$ is independent of the number of channels, in the
setting with publisher reserves, the $PoA$ directly depends of the number of
channels.

##  7 Further Discussion

In this paper, we have established tight bounds on _revenue_ guarantees and
Price of Anarchy when the reserve prices are set in the _cost-per-unit-value_
space. Two natural follow-up questions are:

>   * •
>
> Can we obtain similar bounds for _welfare_ of the bidders?
>
>   * •
>
> What are the revenue guarantees if the channels set reserve prices in the
> _cost-per-impression_ space?
>
>

We briefly discuss how to extend some of our results to answer these
questions. We defer the details to the full paper.

### Bounds for Welfare

Most of our revenue and Price of Anarchy results carry over to welfare. In
particular for the setting without publisher reserves, we can get bounds
similar to the the revenue bounds in Theorem 2 and Proposition 3 and the Price
of Anarchy bound in Theorem 5 for welfare (see Appendix E for a proof sketch).
Many of the results in the setting without publisher reserves also carry over
to welfare. We defer the details to the full paper.

We also observe an interesting phenomena – in contrast to the quasi-linear
setting, using a higher reserve price can sometimes increase the welfare (see
the discussion after Theorem 7).

### Uniform cost-per-impression reserve prices

We can obtain a revenue guarantee analogous to Theorem 2 when channels set
uniform cost-per-impression reserve prices (i.e., value-independent and the
same for all bidders and impressions). We can do this by adapting the
bucketization arguments in Section 5 to bucketize $T_{j}v_{j,i}$ instead of
$T_{j}$ for tCPA bidders, bucketize $v_{j,i}$ for Quasi-linear bidders, and
bucketize $\beta_{j}v_{j,i}$ instead of $\beta_{j}$ for Budgeted bidders.

## References

  * [1]
  * About App campaigns [[n. d.]] About App campaigns [n. d.].  About App campaigns.  https://support.google.com/google-ads/answer/6247380?hl=en.  Accessed: 2022-02-08.
  * About Performance Max campaigns [[n. d.]] About Performance Max campaigns [n. d.].  About Performance Max campaigns.  https://support.google.com/google-ads/answer/10724817?hl=en.  Accessed: 2022-02-08.
  * About the Delivery System: Placements [[n. d.]] About the Delivery System: Placements [n. d.].  About the Delivery System: Placements.  https://www.facebook.com/business/help/965529646866485?id=802745156580214.  Accessed: 2022-02-08.
  * Aggarwal et al. [2019] Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. 2019.  Autobidding with Constraints. In _Web and Internet Economics - 15th International Conference, WINE 2019, New York, NY, USA, December 10-12, 2019, Proceedings_ _(Lecture Notes in Computer Science, Vol. 11920)_ , Ioannis Caragiannis, Vahab S. Mirrokni, and Evdokia Nikolova (Eds.). Springer, 17–30.  https://doi.org/10.1007/978-3-030-35389-6_2
  * Azar et al. [2017] Yossi Azar, Michal Feldman, Nick Gravin, and Alan Roytman. 2017.  Liquid price of anarchy. In _International Symposium on Algorithmic Game Theory_. Springer, 3–15.
  * Balseiro et al. [2021a] Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. 2021a.  Robust Auction Design in the Auto-bidding World.  _Advances in Neural Information Processing Systems_ 34 (2021).
  * Balseiro et al. [2021b] Santiago R. Balseiro, Yuan Deng, Jieming Mao, Vahab S. Mirrokni, and Song Zuo. 2021b.  _The Landscape of Auto-Bidding Auctions: Value versus Utility Maximization_.  Association for Computing Machinery, New York, NY, USA, 132–133.  https://doi.org/10.1145/3465456.3467607
  * Bidding on Twitter Ads [[n. d.]] Bidding on Twitter Ads [n. d.].  Bidding on Twitter Ads.  https://business.twitter.com/en/help/troubleshooting/bidding-and-auctions-faqs.html.  Accessed: 2022-02-08.
  * Burguet and Sákovics [1999] Roberto Burguet and József Sákovics. 1999.  Imperfect Competition in Auction Designs.  _International Economic Review_ 40 (1999), 231–247.
  * Chen et al. [2021] Xi Chen, Christian Kroer, and Rachitesh Kumar. 2021.  The Complexity of Pacing for Second-Price Auctions. In _Proceedings of the 22nd ACM Conference on Economics and Computation_ _(EC ’21)_. Association for Computing Machinery, 318\.
  * Chen et al. [2007] Xi Chen, Shang-Hua Teng, and Paul Valiant. 2007.  The approximation complexity of win-lose games. In _SODA_ , Vol. 7. Citeseer, 159–168.
  * Conitzer et al. [2021] Vincent Conitzer, Christian Kroer, Eric Sodomka, and Nicolas E Stier-Moses. 2021.  Multiplicative pacing equilibria in auction markets.  _Operations Research_ (2021).
  * Deng et al. [2021] Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. 2021\.  _Towards Efficient Auctions in an Auto-Bidding World_.  Association for Computing Machinery, New York, NY, USA, 3965–3973.  https://doi.org/10.1145/3442381.3450052
  * Dobzinski and Paes Leme [2014] Shahar Dobzinski and Renato Paes Leme. 2014.  Efficiency guarantees in auctions with budgets. In _International Colloquium on Automata, Languages, and Programming_. Springer, 392–404.
  * Ellison et al. [2004] Glenn Ellison, Drew Fudenberg, and Markus Möbius. 2004\.  Competing Auctions.  _Journal of the European Economic Association_ 2, 1 (03 2004), 30–66.  https://doi.org/10.1162/154247604323015472 arXiv:https://academic.oup.com/jeea/article-pdf/2/1/30/10312861/jeea0030.pdf
  * Google Ads Help Center: About automated bidding [[n. d.]] Google Ads Help Center: About automated bidding [n. d.].  Google Ads Help Center: About automated bidding.  https://support.google.com/google-ads/answer/2979071?hl=en.  Accessed: 2020-02-08.
  * Koutsoupias and Papadimitriou [1999] Elias Koutsoupias and Christos Papadimitriou. 1999.  Worst-Case Equilibria. In _Proceedings of the 16th Annual Conference on Theoretical Aspects of Computer Science_ (Trier, Germany) _(STACS’99)_. Springer-Verlag, Berlin, Heidelberg, 404–413.
  * Li and Tang [2022] Juncheng Li and Pingzhong Tang. 2022.  Auto-bidding Equilibrium in ROI-Constrained Online Advertising Markets.  _arXiv preprint arXiv:2210.06107_ (2022).
  * McAfee [1993] R. Preston McAfee. 1993\.  Mechanism Design by Competing Sellers.  _Econometrica_ 61, 6 (1993), 1281–1312.  http://www.jstor.org/stable/2951643
  * NAs [1951] JF NAs. 1951.  Non-cooperative games.  _Annals of mathematics_ 54, 2 (1951), 286–295.
  * Rankin [1968] RA Rankin. 1968\.  Real and Complex Analysis. By W. Rudin. Pp. 412. 84s. 1966.(McGraw-Hill, New York.).  _The Mathematical Gazette_ 52, 382 (1968), 412–412.
  * Tiktok Business Help Center: About App Event Optimization [[n. d.]] Tiktok Business Help Center: About App Event Optimization [n. d.].  Tiktok Business Help Center: About App Event Optimization.  https://ads.tiktok.com/help/article?aid=179845248081724490.  Accessed: 2022-02-08.
  * Virág [2010] Gábor Virág. 2010\.  Competing auctions: Finite markets and convergence.  _Theoretical Economics_ 5, 2 (2010), 241–274.  https://doi.org/10.3982/TE538 arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.3982/TE538
  * Your Guide to Meta Bid Strategies [[n. d.]] Your Guide to Meta Bid Strategies [n. d.].  Your Guide to Meta Bid Strategies.  https://www.facebook.com/business/m/one-sheeters/facebook-bid-strategy-guide.  Accessed: 2022-02-08.

##  Appendix A Bidding Uniformly is Optimal

###### Proof of Proposition 1.

We prove the proposition using a greedy-exchange argument. We will maintain
the invariant $\forall i\in I,\,b_{j,i}=\alpha_{j}v_{j,i}$. Initially, we let
$\alpha_{j}=0$ and $\forall i\in I,\,x_{j,i}=0$, and then we update them using
a greedy procedure: Until the first constraint in Problem (2) (or (3) resp.)
is tight for solution $(b_{j,i})_{i\in I},(x_{j,i})_{i\in I}$ or $\forall i\in
I\textrm{ s.t. }v_{j,i}>0,x_{j,i}=1$ (i.e., bidder $j$ has already won every
impression for which they have strictly positive value), do the following

  1. 1.

if bidder $j$ is tied for an impression $i$ and $x_{j,i}<1$ (when there are
multiple such impressions, choose an arbitrary one), increase $x_{j,i}$ until
$x_{j,i}=1$ or the stop condition is met,

  2. 2.

and if there is no such impression, increase $\alpha_{j}$ until bidder $j$ is
tied for a new impression $i$ and go to Step 1.

Notice that whenever the above procedure increases $x_{j,i_{1}}$ for an
impression $i_{1}$ in Step 1, two things must hold: (i) for any impression
$i_{2}\in I$ such that
$\frac{c_{j,i_{2}}({\bm{b}}_{i_{2}},{\bm{r}})}{v_{j,i_{2}}}<\alpha_{j}$, we
have $x_{j,i_{2}}=1$ (because for any such $i_{2}$, in the the above
procedure, bidder $j$ would have been tied for $i_{2}$ before $i_{1}$, and the
above procedure would have already increased $x_{j,i_{2}}$ to $1$), and (ii)
$\frac{c_{j,i_{1}}({\bm{b}}_{i_{1}},{\bm{r}})}{v_{j,i_{1}}}=\alpha_{j}$
(because the procedure only increases $x_{j,i_{1}}$ when bidder $j$ is tied
for impression $i_{1}$). Therefore, at any moment when the above procedure is
increasing $x_{j,i}$ for some impression $i$, impression $i$ must be the
current “best bang for the buck”, i.e., among all the impressions $\ell\in I$
such that $x_{j,\ell}<1$, impression $i$ has the smallest cost-per-unit-value
$\frac{c_{j,i}({\bm{b}}_{i},{\bm{r}})}{v_{j,i}}$ for bidder $j$.

Now we let $(b^{*}_{j,i})_{i\in I},(x^{*}_{j,i})_{i\in I}$ be the solution to
Problem (2) (or (3) resp.) that the above greedy procedure converges to and
let $(b^{\prime}_{j,i})_{i\in I},(x^{\prime}_{j,i})_{i\in I}$ be any feasible
solution to Problem (2) (or (3) resp.), and we want to show that
$(b^{*}_{j,i})_{i\in I},(x^{*}_{j,i})_{i\in I}$ is not worse than
$(b^{\prime}_{j,i})_{i\in I},(x^{\prime}_{j,i})_{i\in I}$.

To this end, we rank all the impressions in $I$ according to their cost-per-
unit-value $\frac{c_{j,i}({\bm{b}}_{i},{\bm{r}})}{v_{j,i}}$ for bidder $j$ in
the increasing order $\pi$, i.e., $\pi$ is a permutation over $I$ such that
$\frac{c_{j,\pi(i_{1})}({\bm{b}}_{\pi(i_{1})},{\bm{r}})}{v_{j,\pi(i_{1})}}\leq\frac{c_{j,\pi(i_{2})}({\bm{b}}_{\pi(i_{2})},{\bm{r}})}{v_{j,\pi(i_{2})}}$
for any $i_{1}<i_{2}$. Let $i_{0}$ be the smallest number such that
$x^{\prime}_{j,\pi(i_{0})}\neq x^{*}_{j,\pi(i_{0})}$. It must hold that
$x^{*}_{j,\pi(i_{0})}>x^{\prime}_{j,\pi(i_{0})}$. To see this, notice that if
$x^{*}_{j,\pi(i_{0})}<1$, because the greedy procedure prioritize increasing
$x^{*}_{j,\pi(i_{0})}$ over any other $x^{*}_{j,\pi(i)}$ for $i>i_{0}$ until
the first constraint in Problem (2) (or (3) resp.) is tight, and
$x^{\prime}_{j,\pi(i)}=x^{*}_{j,\pi(i)}$ for all $i<i_{0}$ by definition of
$i_{0}$, we must have $x^{*}_{j,\pi(i_{0})}\geq x^{\prime}_{j,\pi(i_{0})}$
(otherwise $(x^{\prime}_{j,i})_{i\in I}$ should violate the first constraint).
If $x^{*}_{j,\pi(i_{0})}=1$, then $x^{*}_{j,\pi(i_{0})}\geq
x^{\prime}_{j,\pi(i_{0})}$ holds trivially. Since in both cases we have
$x^{*}_{j,\pi(i_{0})}\geq x^{\prime}_{j,\pi(i_{0})}$, and we assumed that
$x^{\prime}_{j,\pi(i_{0})}\neq x^{*}_{j,\pi(i_{0})}$, it follows that
$x^{*}_{j,\pi(i_{0})}>x^{\prime}_{j,\pi(i_{0})}$.

Let $i^{\prime}>i_{0}$ be such that $x^{\prime}_{j,\pi(i^{\prime})}>0$. There
must exist such $i^{\prime}$ WLOG, because otherwise it is obvious that
$(b^{*}_{j,i})_{i\in I},(x^{*}_{j,i})_{i\in I}$ is the better solution. Now
consider the overall cost-per-unit-value $T^{\prime}=\frac{\sum_{i\in
I}c_{j,i}({\bm{b}}_{i},{\bm{r}})x^{\prime}_{j,i}}{\sum_{i\in
I}v_{j,i}x^{\prime}_{j,i}}$ and the total cost $B^{\prime}=\sum_{i\in
I}c_{j,i}({\bm{b}}_{i},{\bm{r}})x^{\prime}_{j,i}$. Because
$\frac{c_{j,\pi(i_{0})}({\bm{b}}_{\pi(i_{0})},{\bm{r}})}{v_{j,\pi(i_{0})}}\leq\frac{c_{j,\pi(i^{\prime})}({\bm{b}}_{\pi(i^{\prime})},{\bm{r}})}{v_{j,\pi(i^{\prime})}}$,
if we decrease $x^{\prime}_{j,i^{\prime}}$ by
$\frac{\delta}{v_{j,\pi(i^{\prime})}}$ and increase $x^{\prime}_{j,i_{0}}$ by
$\frac{\delta}{v_{j,\pi(i_{0})}}$ for
$\delta=\min\\{v_{j,\pi(i_{0})}(x^{*}_{j,i_{0}}-x^{\prime}_{j,i_{0}}),\,v_{j,\pi(i^{\prime})}x^{\prime}_{j,i^{\prime}}\\}$,
then neither $T^{\prime}$ nor $B^{\prime}$ can increase, and the total value
$\sum_{i\in I}v_{j,i}x^{\prime}_{j,i}$ does not change. (Note that such change
for $x^{\prime}_{j,i^{\prime}}$ and $x^{\prime}_{j,i_{0}}$ is feasible after
changing the bids $b^{\prime}_{j,i^{\prime}}$ and $b^{\prime}_{j,i_{0}}$
appropriately.)

Furthermore, we can repeat the above argument whenever there exists $i_{0}\in
I$ such that $x^{\prime}_{j,\pi(i_{0})}\neq x^{*}_{j,\pi(i_{0})}$ to make
$x^{\prime}_{j,\pi(i_{0})}=x^{*}_{j,\pi(i_{0})}$, which shows that
$(x^{*}_{j,i})_{i\in I}$ achieves better (or equal) total value than
$(x^{\prime}_{j,i})_{i\in I}$. ∎

##  Appendix B Proof of Hardness of Finding Subgame Equilibrium

In this section, we prove that it is PPAD-hard to find the subgame equilibrium
(Definition 1) even when the subgame only consists of tCPA bidders and does
not have reserve prices. Since we only consider tCPA bidders and no reserve
prices in this section, we first simplify the notion of the subgame
equilibrium by restricting to tCPA bidders in the following subsection.

###  B.1 Subgame Equilibrium for tCPA Bidders

Without reserve prices, the subgame equilibrium for tCPA bidders can be
simplified as the following _uniform-bidding equilibrium_ , which is
essentially same as the autobidding equilibrium in [19], and hence, we also
refer to the subgame for tCPA bidders as _uniform-bidding game_ in this
section.

######  Definition 6 (Uniform-Bidding Equilibrium for tCPA Bidders).

In the subgame with $m$ items (impressions) $I$ and $n$ tCPA bidders with
tCPAs $T_{1},\dots,T_{n}$, let $\alpha=(\alpha_{1},\dots,\alpha_{n})$ be the
vector of the bidders’ bidding parameters, where $\alpha_{j}\geq T_{j}$, and
let $x=(x_{1,1},\dots,x_{n,m})$ be the vector of the allocations of the items,
where $x_{j,i}\in[0,1]$ is the fraction of item $i$ being allocated to bidder
$j$, and thus $\sum_{j\in[n]}x_{ji}\leq 1$, and let $p_{i}$ be the second
highest bid for item $i$, and thus bidder $j$ pays $p_{i}x_{j,i}$ for item
$i$. We say $(\alpha,x)$ is a uniform-bidding equilibrium if

  1. (1)

Only the bidder with highest bid gets the item: $x_{j,i}>0$ only if
$\alpha_{j}v_{j,i}\geq\alpha_{\ell}v_{\ell,i}$ for all $\ell\in[n]$.

  2. (2)

Full allocation of any item with a positive bid: $\sum_{j\in[n]}x_{j,i}=1$ if
$\alpha_{\ell}v_{\ell,i}>0$ for some $\ell\in[n]$.

  3. (3)

tCPAs are satisfied: for each $j\in[n]$,
$\frac{\sum_{i\in[m]}p_{i}x_{j,i}}{\sum_{i\in[m]}v_{j,i}x_{j,i}}\leq T_{j}$.

  4. (4)

Every bidder’s bidding parameter is such that even if they can decide the
fraction of an item they get in case of a tie, increasing their bidding
parameter would not increase their total value without violating their tCPA
constraint.

###  B.2 Hardness of Finding the Uniform-Bidding Equilibrium

We reduce computing an (approximate) mixed-strategy Nash equilibrium of a 0-1
(win-lose) bimatrix game to computing a uniform-bidding equilibrium of the
uniform-bidding game for tCPA bidders. The basic idea of the reduction is
similar to that of the hardness result for finding uniform-bidding equilibrium
for budget-constrained quasi-linear bidders [11]. However, we do have to
handle many difficulties that are unique to the tCPA constraints. Most
notably, in contrast to budget-constrained quasi-linear bidders, whose bidding
parameter is at most $1$, tCPA bidders do not have a natural upper bound for
their bids, and their bidding parameters can be arbitrarily high when their
tCPA constraints are not binding.

We start by defining the 0-1 bimatrix game and the approximate Nash
equilibrium of this game.

######  Definition 7 (0-1 bimatrix game $\mathcal{G}(A,B)$).

In a 0-1 bimatrix game, there are two players, and they both have $n$
strategies to choose from. Player 1’s cost matrix is $A\in\\{0,1\\}^{n\times
n}$, i.e., player 1’s cost is $A_{ij}$ if player 1 plays the $i$-th strategy,
and player 2 plays the $j$-th strategy. Similarly, player 2’s cost matrix is
$B\in\\{0,1\\}^{n\times n}$, i.e., player 2’s cost is $B_{ij}$ if player 1
plays the $i$-th strategy, and player 2 plays the $j$-th strategy..

######  Definition 8 ($\varepsilon$-approximate Nash equilibrium).

In a 0-1 bimatrix game $\mathcal{G}(A,B)$, suppose that player 1 plays mixed
strategy $x\in[0,1]^{n}$ s.t. $1^{T}x=1$, and player 2 plays mixed strategy
$y\in[0,1]^{n}$ s.t. $1^{T}y=1$. Then, we say $(x,y)$ is an
$\varepsilon$-approximate Nash equilibrium if it holds for all $z\in[0,1]^{n}$
s.t. $1^{T}z=1$ that

$\displaystyle x^{T}Ay$ $\displaystyle\leq z^{T}Ay+\varepsilon,$
$\displaystyle x^{T}By$ $\displaystyle\leq x^{T}Az+\varepsilon.$

Finding an approximate Nash equilibrium for 0-1 bimatrix game was shown to be
PPAD-hard [12].

######  Lemma 3 (Chen et al. [12, Theorem 6.1]).

For any constant $c>0$, finding $1/n^{c}$-approximate Nash equilibrium for 0-1
bimatrix game is PPAD-hard.

Now, given a 0-1 bimatrix game $\mathcal{G}(A,B)$ with arbitrary cost matrices
$A$ and $B$, we construct a uniform-bidding game $\mathcal{I}(A,B)$ for tCPA
bidders as follows.

####  B.2.1 Construction of Hard Instance $\mathcal{I}(A,B)$

Bidders:

For each player $p\in\\{1,2\\}$ and each strategy $s\in[n]$, we introduce two
tCPA bidders $\mathcal{C}(p,s)$ and $\mathcal{D}(p,s)$. In addition, we have
two more tCPA bidders $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$.

Items:

For each $p\in\\{1,2\\}$ and each $s\in[n]$, we construct an _expensive item_
$H(p,s)$, a _cheap item_ $L(p,s)$, a set of _normalized items_
$\\{N(p,s)_{i}\mid i\in[n]\\}$, and a set of _expenditure items_
$\\{E(p,s)_{i}\mid i\in[n]\\}$ for bidder $\mathcal{C}(p,s)$, and moreover, we
construct a cheap item $D(p,s)$ for bidder $\mathcal{D}(p,s)$. Furthermore, we
have a special item $T$ for bidders $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$
and a cheap item $T_{2}$ for bidder $\mathcal{T}_{2}$.

Valuations:

We first give an informal description of the valuations, and then we provide
the formal definition. Let $\delta_{1}=1/n^{2}$ and $\delta_{2}=1/n^{4}$.

Bidder $\mathcal{C}(1,s)$ has high values (i.e., $n^{3}$) for the items
$H(1,s)$ and $L(1,s)$, medium values (i.e., $3$) for their own normalized
items $\\{N(1,s)_{i}\mid i\in[n]\textrm{ and }i\neq s\\}$, low values (i.e.,
$1$) for their own expenditure items $\\{E(1,s)_{i}\mid i\in[n]\\}$,
normalized item $N(1,s)_{s}$, and bidder $\mathcal{C}(1,t)$’s $s$-th
normalized item $N(1,t)_{s}$, and negligible values (i.e., $\delta_{1}B_{st}$)
for bidder $\mathcal{C}(2,t)$’s $s$-th expenditure item $E(2,t)_{s}$. Bidder
$\mathcal{C}(2,s)$’s valuation is analogous.

On the other hand, bidder $\mathcal{D}(1,s)$ has the same value (i.e., $1$) as
bidder $\mathcal{C}(1,s)$ for bidder $\mathcal{C}(1,s)$’s $s$-th normalized
item $N(1,s)_{s}$ and value $1$ for their own item $D(p,s)$.

Bidder $\mathcal{T}_{1}$ has the same value (i.e., $n^{3}$) as bidder
$\mathcal{C}(1,s)$ for bidder $\mathcal{C}(1,s)$’s expensive item $H(1,s)$ and
value $1$ for the item $T$. Bidder $\mathcal{T}_{2}$ has the same value (i.e.,
$1$) for the item $T$ as bidder $\mathcal{T}_{1}$ and value $1$ for their own
item $T_{2}$.

Formally, we use the notation $v(\textrm{bidder},\textrm{item})$ to denote a
bidder’s value of an item. For all $p\in\\{1,2\\}$, all distinct $s,t\in[n]$
and all $i\in[n]$, we let

$\displaystyle v(\mathcal{C}(p,s),N(p,s)_{s})=1$
$\displaystyle,\,\,v(\mathcal{C}(p,s),N(p,s)_{t})=3$ $\displaystyle
v(\mathcal{C}(p,s),N(p,t)_{s})=1$
$\displaystyle,\,\,v(\mathcal{C}(p,s),E(p,s)_{i})=1,$ $\displaystyle
v(\mathcal{C}(1,s),E(2,i)_{s})=\delta_{1}B_{si}$
$\displaystyle,\,\,v(\mathcal{C}(2,t),E(1,i)_{t})=\delta_{1}A_{it},$
$\displaystyle v(\mathcal{C}(p,s),H(p,s))=n^{3}$
$\displaystyle,\,\,v(\mathcal{C}(p,s),L(p,s))=n^{3},$ $\displaystyle
v(\mathcal{D}(p,s),D(p,s))=1$
$\displaystyle,\,\,v(\mathcal{D}(p,s),N(p,s)_{s})=1.$

Moreover, we let $v(\mathcal{T}_{1},H(p,s))=n^{3}$ for all $p\in\\{1,2\\}$ and
$s\in[n]$, and
$v(\mathcal{T}_{1},T)=v(\mathcal{T}_{2},T)=v(\mathcal{T}_{2},T_{2})=1$. For
any other $(\textrm{bidder},\textrm{item})$ pair that did not appear above,
$v(\textrm{bidder},\textrm{item})=0$.

tCPAs:

Bidder $\mathcal{T}_{1}$’s tCPA is $1$, and bidder $\mathcal{T}_{2}$’s tCPA is
$\delta_{2}$. For all $p\in\\{1,2\\}$ and $s\in[n]$, bidder
$\mathcal{D}(p,s)$’s tCPA is $\delta_{2}$, and

$\displaystyle\textrm{bidder $\mathcal{C}(1,s)$'s
${\mbox{tCPA}}$}=\frac{n^{3}+n+\delta_{1}\sum_{t\in[n]}A_{st}+3/2}{2n^{3}+4n-2},$
$\displaystyle\textrm{bidder $\mathcal{C}(2,s)$'s
${\mbox{tCPA}}$}=\frac{n^{3}+n+\delta_{1}\sum_{t\in[n]}B_{ts}+3/2}{2n^{3}+4n-2}.$

####  B.2.2 Proof of Hardness

######  Theorem 9.

It is PPAD-hard to find a uniform-bidding equilibrium in uniform-bidding game
for tCPA bidders.

We prove Theorem 9 by showing that if we find a uniform-bidding equilibrium
for our hard instance $\mathcal{I}(A,B)$, then we also find a
$O(1/n)$-approximate Nash equilibrium for the 0-1 bimatrix game
$\mathcal{G}(A,B)$ (the theorem follows by Lemma 3). We split the proof of the
theorem into a series of lemmata.

######  Lemma 4.

In any uniform-bidding equilibrium of $\mathcal{I}(A,B)$, for all
$p\in\\{1,2\\}$ and $s\in[n]$, bidder $\mathcal{C}(p,s)$’s bidding parameter
is at least $1$.

###### Proof.

Suppose for contradiction bidder $\mathcal{C}(p,s)$’s bidding parameter is
strictly less than $1$. Then, bidder $\mathcal{C}(p,s)$ does not get any
fraction of the item $H(p,s)$, because bidder $\mathcal{T}_{1}$ has the same
value for the item $H(p,s)$ as bidder $\mathcal{C}(p,s)$, and bidder
$\mathcal{T}_{1}$’s bidding parameter is at least bidder $\mathcal{T}_{1}$’s
tCPA, which is $1$. Now let us upper bound the CPA (_cost-per-acquisition_ ,
i.e., bidder’s total payment divided by bidder’s total value) of bidder
$\mathcal{C}(p,s)$.

First, the total value that bidder $\mathcal{C}(p,s)$ gets is at least the
value of the item $L(p,s)$, which is $n^{3}$, because no one other than
$\mathcal{C}(p,s)$ has positive value for $L(p,s)$, and hence
$\mathcal{C}(p,s)$ always wins $L(p,s)$ for free.

Moreover, the total payment that bidder $\mathcal{C}(p,s)$ makes is at most
$\mathcal{C}(p,s)$’s bidding parameter times $\mathcal{C}(p,s)$’s total value
of the items except $H(p,s)$ and $L(p,s)$, because $\mathcal{C}(p,s)$ does not
get any fraction of $H(p,s)$ and gets $L(p,s)$ for free. It is straightforward
to verify that by construction of $\mathcal{I}(A,B)$, $\mathcal{C}(p,s)$’s
total value of the items except $H(p,s)$ and $L(p,s)$ is less than $5n$. Since
we assume for contradiction that $\mathcal{C}(p,s)$’s bidding parameter is
less than $1$, the total payment $\mathcal{C}(p,s)$ makes is less than $5n$.

Thus, bidder’s $\mathcal{C}(p,s)$’s CPA is less than $5n/n^{3}$, which is much
less than $\mathcal{C}(p,s)$’s tCPA. Next, we show that this contradicts the
fourth property in Definition 6. Specifically, we can first assume WLOG that
bidder $\mathcal{C}(p,s)$ does not tie for any item, because otherwise
$\mathcal{C}(p,s)$ can increase the bidding parameter by an arbitrarily small
amount such that $\mathcal{C}(p,s)$ gets the full item which
$\mathcal{C}(p,s)$ ties for, and $5n$ would still be an upper bound of
$\mathcal{C}(p,s)$’s total payment (by the same argument as before), which
contradicts the fourth property in Definition 6. Then, we notice there exist
items for which bidder $\mathcal{C}(p,s)$ has positive value such as $H(p,s)$.
Therefore, if $\mathcal{C}(p,s)$ raises the bidding parameter until the first
time $\mathcal{C}(p,s)$ ties for a new item for which $\mathcal{C}(p,s)$ has
positive value, then because $\mathcal{C}(p,s)$ already gets positive value
with a CPA that is much less than $\mathcal{C}(p,s)$’s tCPA,
$\mathcal{C}(p,s)$ can afford at least a fraction of that new item (which
contradicts the fourth property in Definition 6). ∎

######  Lemma 5.

In any uniform-bidding equilibrium of $\mathcal{I}(A,B)$, bidder
$\mathcal{T}_{2}$’s bidding parameter is equal to bidder $\mathcal{T}_{1}$’s
bidding parameter, and bidder $\mathcal{D}(p,s)$’s bidding parameter is equal
to bidder $\mathcal{C}(p,s)$’s bidding parameter for all $p\in\\{1,2\\}$ and
$s\in[n]$.

###### Proof.

First, we show that in a uniform-bidding equilibrium, bidder
$\mathcal{T}_{2}$’s bidding parameter is equal to bidder $\mathcal{T}_{1}$’s
bidding parameter. Notice that no one other than bidder $\mathcal{T}_{2}$ has
positive value for the item $T_{2}$, and thus, $\mathcal{T}_{2}$ gets $T_{2}$
with value $1$ for free, which gives $\mathcal{T}_{2}$ the flexibility to
afford certain fraction of the item $T$ regardless of its price, because
bidder $\mathcal{T}_{2}$’s tCPA is positive. Since bidder $\mathcal{T}_{2}$
has the same value (i.e., $1$) for the item $T$ as bidder $\mathcal{T}_{1}$
and can always afford a fraction of $T$, it follows by the fourth property in
Definition 6 that in a uniform-bidding equilibrium, $\mathcal{T}_{2}$’s
bidding parameter should be no less than $\mathcal{T}_{1}$’s bidding
parameter. On the other hand, if $\mathcal{T}_{2}$’s bidding parameter is
strictly greater than $\mathcal{T}_{1}$’s bidding parameter, which is at least
$1$, then $\mathcal{T}_{2}$ will win the full item $T$ for a price that is at
least $1$, and it follows that $\mathcal{T}_{2}$’s CPA is at least $1/2$,
which is much higher than $\mathcal{T}_{2}$’s tCPA (i.e., $\delta_{2}$). Thus,
$\mathcal{T}_{2}$’s bidding parameter is no greater than (and hence equal to)
$\mathcal{T}_{1}$’s bidding parameter.

The proof of the equivalence between bidder $\mathcal{D}(p,s)$’s bidding
parameter and bidder $\mathcal{C}(p,s)$’s is similar. Specifically,
$\mathcal{D}(p,s)$ also has a free item $D(p,s)$ with value $1$, and
$\mathcal{D}(p,s)$ also has a positive but tiny tCPA (i.e., $\delta_{2}$), and
thus, $\mathcal{D}(p,s)$ can afford certain fraction of the item $N(p,s)_{s}$.
Notice that $\mathcal{D}(p,s)$ and $\mathcal{C}(p,s)$ have the same value
(i.e., $1$) for the item $N(p,s)_{s}$, and $\mathcal{C}(p,s)$’s bidding
parameter is no less than $\mathcal{C}(p,s)$’s tCPA ($\approx 1/2$). The rest
of the proof is same as the proof above for bidder $\mathcal{T}_{2}$ and
bidder $\mathcal{T}_{1}$. ∎

######  Lemma 6.

In any uniform-bidding equilibrium of $\mathcal{I}(A,B)$, bidder
$\mathcal{T}_{1}$’s bidding parameter is $1$.

###### Proof.

$\mathcal{T}_{1}$’s bidding parameter is at least $1$, because
$\mathcal{T}_{1}$’s tCPA is $1$. It suffices to prove that $\mathcal{T}_{1}$’s
bidding parameter is at most $1$.

Now suppose for contradiction, bidder $\mathcal{T}_{1}$’s bidding parameter is
strictly greater than $1$. In the proof of Lemma 5, we have shown that bidder
$\mathcal{T}_{2}$’s bidding parameter is equal to $\mathcal{T}_{1}$’s bidding
parameter and that $\mathcal{T}_{2}$ can not afford the full item $T$.
Therefore, $\mathcal{T}_{1}$ must get a fraction of $T$ by the second property
of Definition 6, and the payment per value $\mathcal{T}_{1}$ makes for $T$ is
exactly $\mathcal{T}_{1}$’s bidding parameter, which is strictly greater than
$1$ by our assumption for contradiction. Moreover, for all $p\in\\{1,2\\}$ and
$s\in[n]$, (i) by Lemma 4, bidder $\mathcal{C}(p,s)$’s bidding parameter is at
least $1$, and (ii) bidder $\mathcal{T}_{1}$ has the same value for the item
$H(p,s)$ as bidder $\mathcal{C}(p,s)$ by construction of $\mathcal{I}(A,B)$.
Hence, if bidder $\mathcal{T}_{1}$ wins any fraction of the item $H(p,s)$ for
any $p\in\\{1,2\\}$ and $s\in[n]$, the payment per value $\mathcal{T}_{1}$
makes for $H(p,s)$ is at least $1$. Therefore, overall, bidder
$\mathcal{T}_{1}$’s CPA is strictly greater than $1$ and thus violates
$\mathcal{T}_{1}$’s tCPA, which is a contradiction. ∎

######  Lemma 7.

In any uniform-bidding equilibrium, for all $p\in\\{1,2\\}$ and $s\in[n]$,
bidder $\mathcal{C}(p,s)$ wins at least $1-2\delta_{2}$ fraction of the item
$N(p,s)_{s}$.

###### Proof.

Bidder $\mathcal{C}(p,s)$ and bidder $\mathcal{D}(p,s)$ tie for the item
$N(p,s)_{s}$, because they have the same value $1$ for this item and the same
bidding parameter by Lemma 5. Thus, the payment per value for the item
$N(p,s)_{s}$ is equal to $\mathcal{C}(p,s)$’s bidding parameter which is $\geq
1$. Since the only other item bidder $\mathcal{D}(p,s)$ gets is $D(p,s)$
(value $1$ and zero cost), and $\mathcal{D}(p,s)$ has tCPA $\delta_{2}$, it
follows by straightforward calculation that $\mathcal{D}(p,s)$ can afford no
more than $2\delta_{2}$ fraction of the item $N(p,s)_{s}$. By the second
property in Definition 6, $\mathcal{C}(p,s)$ wins at least $1-2\delta_{2}$
fraction of $N(p,s)_{s}$. ∎

######  Lemma 8.

In any uniform-bidding equilibrium of $\mathcal{I}(A,B)$, for all
$p\in\\{1,2\\}$ and $s\in[n]$, bidder $\mathcal{C}(p,s)$’s bidding parameter
is strictly less than $3$.

###### Proof.

We prove the lemma for bidder $\mathcal{C}(1,s)$ (the case of bidder
$\mathcal{C}(2,s)$ is analogous). Suppose for contradiction bidder
$\mathcal{C}(1,s)$’s bidding parameter is at least $3$, we show that
$\mathcal{C}(1,s)$’s tCPA must be violated. To this end, we count the total
value $\mathcal{C}(1,s)$ gets and the total payment $\mathcal{C}(1,s)$ makes.

First, bidder $\mathcal{C}(1,s)$ is the only bidder who has postive value for
the item $L(1,s)$. Thus, bidder $\mathcal{C}(1,s)$ gets value $n^{3}$ from the
item $L(1,s)$ with zero payment.

Notice that bidder $\mathcal{T}_{1}$ and bidder $\mathcal{C}(1,s)$ have the
same value $n^{3}$ for the item $H(1,s)$, and by Lemma 6, bidder
$\mathcal{T}_{1}$’s bidding parameter is $1$ which is strictly less than
bidder $\mathcal{C}(1,s)$’s bidding parameter ($\geq 3$), and hence, bidder
$\mathcal{C}(1,s)$ wins the full item $H(1,s)$ with payment $n^{3}$ and gets
value $n^{3}$.

Bidder $\mathcal{C}(1,s)$ and bidder $\mathcal{D}(1,s)$ have the same value
$1$ for the item $N(1,s)_{s}$. Lemma 5 shows that bidder $\mathcal{D}(1,s)$’s
bidding parameter is equal to bidder $\mathcal{C}(1,s)$’s bidding parameter
($\geq 3$). Therefore, the price per value of the item $N(1,s)_{s}$ is at
least $3$. By Lemma 7, $\mathcal{C}(1,s)$ gets at least $1-2\delta_{2}$
fraction of the item $N(1,s)_{s}$ and hence pays at least $3(1-2\delta_{2})$
for that fraction of $N(1,s)_{s}$. That is, $\mathcal{C}(1,s)$ gets at most
value $1$ from $N(1,s)_{s}$ (because $\mathcal{C}(1,s)$’s value for the full
item $N(1,s)_{s}$ is $1$) and pays at least $3(1-2\delta_{2})$.

The other items for which bidder $\mathcal{C}(1,s)$ has positive value are
$\\{E(1,s)_{t}\mid t\in[n]\\}$, $\\{N(1,s)_{t}\mid t\in[n]\textrm{ and }t\neq
s\\}$, $\\{E(2,t)_{s}\mid t\in[n]\\}$ and $\\{N(1,t)_{s}\mid t\in[n]\textrm{
and }t\neq s\\}$.

Because bidder $\mathcal{C}(2,t)$ has value $\delta_{1}A_{st}$ for the item
$E(1,s)_{t}$, and by Lemma 4 $\mathcal{C}(2,t)$’s bidding parameter is at
least $1$, if bidder $\mathcal{C}(1,s)$ wins the full item $E(1,s)_{t}$, the
payment $\mathcal{C}(1,s)$ makes is at least $\delta_{1}A_{st}$. For $t\neq s$
and $t\in[n]$, because bidder $\mathcal{C}(1,t)$ has value $1$ for the item
$N(1,s)_{t}$, and $\mathcal{C}(1,t)$’s bidding parameter is at least $1$ by
Lemma 4, if bidder $\mathcal{C}(1,s)$ wins the full item $N(1,s)_{t}$, the
payment $\mathcal{C}(1,s)$ makes is at least $1$. We can assume WLOG that
$\mathcal{C}(1,s)$ gets the full value of $E(1,s)_{t}$ (i.e., $1$) with
payment $\delta_{1}A_{st}$ for each $t\in[n]$ and gets the full value of
$N(1,s)_{t}$ (i.e., $3$) with payment $1$ for each $t\neq s$, because these
are the best payments per value $\mathcal{C}(1,s)$ can hope for these items,
and these payments per value are much lower than $\mathcal{C}(1,s)$’s tCPA
($\approx 1/2$). Namely, if $\mathcal{C}(1,s)$’s CPA does not exceed
$\mathcal{C}(1,s)$’s tCPA, giving the items $\\{E(1,s)_{t}\mid t\in[n]\\}$ and
$\\{N(1,s)_{t}\mid t\in[n]\textrm{ and }t\neq s\\}$ to $\mathcal{C}(1,s)$ and
charging the above payments per value will not violate $\mathcal{C}(1,s)$’s
tCPA. Therefore, WLOG bidder $\mathcal{C}(1,s)$ gets value $4n-3$ from the
items $\\{E(1,s)_{t}\mid t\in[n]\\}$ and $\\{N(1,s)_{t}\mid t\in[n]\textrm{
and }t\neq s\\}$ and pays $\sum_{t\in[n]}\delta_{1}A_{st}+n-1$.

On the other hand, because bidder $\mathcal{C}(2,t)$ has value $1$ and bidder
$\mathcal{C}(1,s)$ has value $\delta_{1}B_{st}$ for the item $E(1,t)_{s}$, and
by Lemma 4 $\mathcal{C}(2,t)$’s bidding parameter is at least $1$, if bidder
$\mathcal{C}(1,s)$ wins any fraction of the item $E(1,t)_{s}$, the payment per
value $\mathcal{C}(1,s)$ makes is at least $1/(\delta_{1}B_{st})$ (or bidder
$\mathcal{C}(1,s)$ never wins any fraction of this item if $B_{st}=0$). For
$t\neq s$ and $t\in[n]$, because bidder $\mathcal{C}(1,t)$ has value $3$ and
bidder $\mathcal{C}(1,s)$ has value $1$ for the item $N(1,t)_{s}$, and
$\mathcal{C}(1,t)$’s bidding parameter is at least $1$ by Lemma 4, if bidder
$\mathcal{C}(1,s)$ wins any fraction of the item $N(1,t)_{s}$, the payment per
value $\mathcal{C}(1,s)$ makes is at least $3$. Notice that the payments per
value for these items are all much higher than $\mathcal{C}(1,s)$’s tCPA, and
hence, we can assume WLOG $\mathcal{C}(1,s)$ does not win any fraction of
these items. Namely, if bidder $\mathcal{C}(1,s)$’s CPA does not exceed
$\mathcal{C}(1,s)$’s tCPA, taking the items $\\{E(2,t)_{s}\mid t\in[n]\\}$ and
$\\{N(1,t)_{s}\mid t\in[n]\textrm{ and }t\neq s\\}$ away from bidder
$\mathcal{C}(1,s)$ will not violate $\mathcal{C}(1,s)$’s tCPA. Therefore, WLOG
bidder $\mathcal{C}(1,s)$ gets zero value from the items $\\{E(2,t)_{s}\mid
t\in[n]\\}$ and $\\{N(1,t)_{s}\mid t\in[n]\textrm{ and }t\neq s\\}$ and pays
zero.

At the end of each paragraph above, we stated the values bidder
$\mathcal{C}(1,s)$ gets from different items and the associated payments. In
summary, bidder $\mathcal{C}(1,s)$’s total value is at most $2n^{3}+4n-2$, and
the total payment is at least
$n^{3}+3(1-2\delta_{2})+\sum_{t\in[n]}\delta_{1}A_{st}+n-1$. Thus,
$\mathcal{C}(1,s)$’s CPA exceeds $\mathcal{C}(1,s)$’s tCPA, which is a
contradiction. ∎

######  Lemma 9.

In any uniform-bidding equilibrium, for all $p\in\\{1,2\\}$, there exists
$s\in[n]$ such that bidder $\mathcal{C}(p,s)$’s bidding parameter is strictly
greater than $1+1/n$.

###### Proof.

We prove the lemma for $p=1$ (the case of $p=2$ is analogous). Suppose for
contradiction that for all $s\in[n]$, bidder $\mathcal{C}(1,s)$’s bidding
parameter is in $[1,1+1/n]$ (we know that it is at least $1$ by Lemma 4), we
upper bound bidder $\mathcal{C}(1,s)$’s CPA.

First, bidder $\mathcal{C}(1,s)$ gets the item $L(1,s)$ for free, since there
is no competition for this item. Moreover, bidder $\mathcal{C}(1,s)$ can get a
fraction of the item $H(p,s)$, since $\mathcal{C}(1,s)$ and $\mathcal{T}_{1}$
have the same value $n^{3}$ for this item, and by Lemma 6 $\mathcal{T}_{1}$’s
bidding parameter is $1$ which is no larger than $\mathcal{C}(1,s)$’s. Let
$\tau\in[0,1]$ denote the fraction of the item $H(p,s)$ which bidder
$\mathcal{C}(1,s)$ wins, and hence $\mathcal{C}(1,s)$ gets value $\tau n^{3}$
from $H(p,s)$ and pays $\tau n^{3}$. Furthermore, For each $t\in[n]$, bidder
$\mathcal{C}(1,s)$ gets the full item $E(1,s)_{t}$ and pays at most
$3\delta_{1}A_{st}$, because bidder $\mathcal{C}(2,t)$ has value
$\delta_{1}A_{st}$ for this item, and $\mathcal{C}(2,t)$’s bidding parameter
is less than $3$ by Lemma 8. For each $t\in[n]$ and $t\neq s$, bidder
$\mathcal{C}(1,s)$ gets the full item $N(1,s)_{t}$ and pays at most $1+1/n$,
because bidder $\mathcal{C}(1,t)$ has value $1$ for this item, and
$\mathcal{C}(1,t)$’s bidding parameter is $\leq 1+1/n$ by our assumption.
Finally, by Lemma 7, $\mathcal{C}(1,s)$ wins at least $1-2\delta_{2}$ fraction
of $N(1,s)_{s}$ and pays at most $1+1/n$ (because $\mathcal{C}(1,s)$’s bidding
parameter times $\mathcal{C}(1,s)$’s value for the full item $N(1,s)_{s}$ is
$\leq 1+1/n$). In addition, it is easy to verify that with bidding parameter
$\leq 1+1/n$, bidder $\mathcal{C}(1,s)$ can not get any fraction of the items
$\\{E(2,t)_{s}\mid t\in[n]\\}$ and $\\{N(1,t)_{s}\mid t\in[n]\textrm{ and
}t\neq s\\}$.

In summary, bidder $\mathcal{C}(1,s)$ gets total value at least
$(1+\tau)n^{3}+4n-2-2\delta_{2}$ and makes total payment at most $\tau
n^{3}+(n-1)(1+1/n)+\sum_{t\in[n]}3\delta_{1}A_{st}+1$. Therefore, the
resulting upper bound of bidder $\mathcal{C}(1,s)$’s CPA is maximized when
$\tau=1$, and the maximum is

$\frac{n^{3}+n-1/n+\sum_{t\in[n]}3\delta_{1}A_{st}+1}{2n^{3}+4n-2-2\delta_{2}},$

which is strictly less than $\mathcal{C}(1,s)$’s tCPA. Therefore, if
$\mathcal{C}(1,s)$ raises the bidding parameter until the first time
$\mathcal{C}(1,s)$ ties for a new item (such item exists, e.g.,
$\\{N(1,t)_{s}\mid t\in[n]\textrm{ and }t\neq s\\}$), $\mathcal{C}(1,s)$ can
afford a fraction of that item, which contradicts the fourth property in
Definition 6. (One might notice that raising $\mathcal{C}(1,s)$’s bidding
parameter will break the tie for the item $N(1,s)_{s}$ between
$\mathcal{C}(1,s)$ and $\mathcal{D}(1,s)$, but this is not an issue, because
in the above calculation for the upper bound of the total payment made by
$\mathcal{C}(1,s)$, we already take the payment for the full item $N(1,s)_{s}$
into account.) ∎

Now we let $\tilde{x}_{s}$ denote bidder $\mathcal{C}(1,s)$’s bidding
parameter and let $\tilde{y}_{t}$ denote a bidder $\mathcal{C}(2,t)$’s bidding
parameter in a uniform-bidding equilibrium. We define a probability vector
$x=(x_{1},\dots,x_{n})$ which corresponds to a mixed strategy for player 1 and
a probability vector $y=(y_{1},\dots,y_{n})$ which corresponds to a mixed
strategy for player 2 in the bimatrix game $\mathcal{G}(A,B)$ as follows

$\displaystyle
x_{s}=\frac{\tilde{x}_{s}-1}{\sum_{i\in[n]}(\tilde{x}_{i}-1)},\,\,y_{t}=\frac{\tilde{y}_{t}-1}{\sum_{i\in[n]}(\tilde{y}_{i}-1)}.$

Note that $x$ is a valid probability vector, because for all $i\in[n]$,
$\tilde{x}_{i}\geq 1$ by Lemma 4, and there exists $i\in[n]$ such that
$\tilde{x}_{i}>1$ by Lemma 9. Similarly, $y$ is also a valid probability
vector. The next lemma implies that $(x,y)$ is an $O(1/n)$-approximate Nash
equilibrium of $\mathcal{G}(A,B)$, which proves Theorem 9, because $(x,y)$
obviously can be computed efficiently from the uniform-bidding equilibrium of
$\mathcal{I}(A,B)$, and finding an $O(1/n)$-approximate Nash equilibrium of
$\mathcal{G}(A,B)$ is PPAD-hard in general by Lemma 3.

######  Lemma 10.

For all $s\in[n]$, if bidder $\mathcal{C}(1,s)$’s bidding parameter
$\tilde{x}_{s}$ is strictly greater than $1$, then the $s$-th strategy is a
$O(1/n)$-approximate best response101010We say a pure strategy is an
$\varepsilon$-approximate best response to the other player’s mixed strategy
if the expected cost of this pure strategy is at most the expected cost of any
other pure strategy plus $\varepsilon$. for player $1$ to player 2’s mixed
strategy $y$ in the 0-1 bimatrix game $\mathcal{G}(A,B)$. Similarly, if bidder
$\mathcal{C}(2,t)$’s bidding parameter $\tilde{y}_{t}$ is strictly greater
than $1$, then the $t$-th strategy is a $O(1/n)$-approximate best response for
player $2$ to player 1’s mixed strategy $x$ in $\mathcal{G}(A,B)$.

###### Proof.

We prove the first part of the lemma, i.e., if $\tilde{x}_{s}>1$, then the
$s$-th strategy is an $O(1/n)$-approximate best response to $y$. (The other
part is analogous.) Formally, we want to show for all $s^{\prime}\in[n]$ and
$s^{\prime}\neq s$,
$\sum_{t\in[n]}A_{st}y_{t}\leq\sum_{t\in[n]}A_{s^{\prime}t}y_{t}+O(1/n)$. By
definition of $y_{t}$, this inequality is equivalent to

$\displaystyle\sum_{t\in[n]}A_{st}(\tilde{y}_{t}-1)$
$\displaystyle\leq\sum_{t\in[n]}A_{s^{\prime}t}(\tilde{y}_{t}-1)+O(1/n)\sum_{i\in[n]}(\tilde{y}_{i}-1).$

By Lemma 4 and Lemma 9, $\sum_{i\in[n]}(\tilde{y}_{i}-1)$ is at least $1/n$.
Hence, it suffices to prove that for all $s^{\prime}\in[n]$ and
$s^{\prime}\neq s$,

$\displaystyle\sum_{t\in[n]}A_{st}(\tilde{y}_{t}-1)$
$\displaystyle\leq\sum_{t\in[n]}A_{s^{\prime}t}(\tilde{y}_{t}-1)+O(1/n^{2}).$
(14)

First of all, we show that for all $i\in[n]$, bidder $\mathcal{C}(1,i)$’s tCPA
must be binding WLOG. Specifically, by Lemma 8, bidder $\mathcal{C}(1,i)$’s
bidding parameter is less than $3$, which implies that $\mathcal{C}(1,i)$ does
not get any fraction of the items $\\{N(1,t)_{i}\mid t\in[n]\textrm{ and
}t\neq i\\}$. However, if $\mathcal{C}(1,i)$’s tCPA is not binding,
$\mathcal{C}(1,i)$ can raise the bidding parameter and afford certain fraction
of those items, which contradicts the fourth property in Definition 6. The
only exception is that $\mathcal{C}(1,i)$ might have only won a fraction of
the item $N(1,i)_{i}$ because of a tie with bidder $\mathcal{D}(1,i)$ (or the
item $H(p,s)$ in case of a tie with bidder $\mathcal{T}_{1}$), and then
raising the bidding parameter might violate $\mathcal{C}(1,i)$’s tCPA
constraint if $\mathcal{C}(1,i)$ can not afford the full item. However, in
this case, we can simply increase the fraction of the item $N(1,i)_{i}$ (or
$H(p,s)$ respectively) that $\mathcal{C}(1,i)$ gets and decrease the fraction
that $\mathcal{D}(1,i)$ (or $\mathcal{T}_{1}$ respectively) gets in the
allocation vector of the uniform-bidding equilibrium until
$\mathcal{C}(1,i)$’s tCPA is binding, and the result is still a uniform-
bidding equilibrium. Thus,

$\displaystyle\textrm{bidder $\mathcal{C}(1,s)$'s CPA}=\textrm{bidder
$\mathcal{C}(1,s)$'s
${\mbox{tCPA}}$}=\frac{n^{3}+n+\delta_{1}\sum_{t\in[n]}A_{st}+3/2}{2n^{3}+4n-2},$
$\displaystyle\textrm{bidder $\mathcal{C}(1,s^{\prime})$'s CPA}=\textrm{bidder
$\mathcal{C}(1,s^{\prime})$'s
${\mbox{tCPA}}$}=\frac{n^{3}+n+\delta_{1}\sum_{t\in[n]}A_{s^{\prime}t}+3/2}{2n^{3}+4n-2}.$

It follows that

$\textrm{bidder $\mathcal{C}(1,s)$'s CPA}-\textrm{bidder
$\mathcal{C}(1,s^{\prime})$'s
CPA}=\frac{\sum_{t\in[n]}\delta_{1}A_{st}-\sum_{t\in[n]}\delta_{1}A_{s^{\prime}t}}{2n^{3}+4n-2}.$
(15)

Next, we calculate bidder $\mathcal{C}(1,s)$’s and bidder
$\mathcal{C}(1,s^{\prime})$’s total payment and total value respectively to
get different bounds for their CPAs.

First, for any $i\in[n]$ (including $s$ and $s^{\prime}$), since except
$\mathcal{C}(1,i)$, only bidder $\mathcal{C}(1,t)$ bids $\tilde{x}_{t}$ on the
item $N(1,i)_{t}$ ($\tilde{x}_{t}$ is $\mathcal{C}(1,t)$’s bidding parameter,
and $1$ is $\mathcal{C}(1,t)$’s value for $N(1,i)_{t}$), and by Lemma 8,
$\tilde{x}_{t}<3$ (which is less than bidder $\mathcal{C}(1,i)$’s bid
$3\tilde{x}_{i}\geq 3$), it follows that bidder $\mathcal{C}(1,i)$ wins all
the items $\\{N(1,i)_{t}\mid t\in[n]\textrm{ and }t\neq i\\}$ and pays
$\sum_{t\in[n]\textrm{ and }t\neq i}\tilde{x}_{t}$. Moreover, by Lemma 7,
bidder $\mathcal{C}(1,i)$ wins at least $1-2\delta_{2}$ fraction of
$N(1,i)_{i}$ (and at most the full item), and because bidders
$\mathcal{C}(1,i)$ and $\mathcal{D}(1,i)$ have the same bidding parameter by
Lemma 5 and the same value $1$ for $N(1,i)_{i}$, $\mathcal{C}(1,i)$ pays at
least $\tilde{x}_{i}(1-2\delta_{2})$ (and at most $\tilde{x}_{i}$) for
$N(1,i)_{i}$. Moreover, since except $\mathcal{C}(1,i)$, only bidder
$\mathcal{C}(2,t)$ bids $\tilde{y}_{t}\delta_{1}A_{it}$ on the item
$E(1,i)_{t}$ ($\tilde{y}_{t}$ is $\mathcal{C}(2,t)$’s bidding parameter, and
$\delta_{1}A_{it}$ is $\mathcal{C}(2,t)$’s value for $E(1,i)_{t}$), and by
Lemma 8, $\tilde{y}_{t}\delta_{1}A_{it}<3\delta_{1}A_{it}$ (which is less than
bidder $\mathcal{C}(1,i)$’s bid $\tilde{x}_{i}\geq 1$ for $E(1,i)_{t}$), it
follows that bidder $\mathcal{C}(1,i)$ wins all the items $\\{E(1,i)_{t}\mid
t\in[n]\\}$ and pays $\sum_{t\in[n]}\delta_{1}A_{it}\tilde{y}_{t}$.
Furthermore, bidder $\mathcal{C}(1,i)$ wins the item $L(1,i)$ for free since
there is no competition for this item. In addition, it is easy to verify that
with bidding parameter $<3$, bidder $\mathcal{C}(1,i)$ can not get any
fraction of the items $\\{E(2,t)_{i}\mid t\in[n]\\}$ and $\\{N(1,t)_{i}\mid
t\in[n]\textrm{ and }t\neq i\\}$.

Finally, we calculate $\mathcal{C}(1,i)$’s value and cost for the item
$H(1,i)$. To this end, we need to do case analysis for $s$ and $s^{\prime}$
(because although bidder $\mathcal{C}(1,s)$’s bidding parameter
$\tilde{x}_{s}>1$ by our assumption, bidder $\mathcal{C}(1,s^{\prime})$’s
bidding parameter $\tilde{x}_{s^{\prime}}$ could be $>1$ or exactly $1$).
Since $\mathcal{T}_{1}$ is the only bidder other than $\mathcal{C}(1,s)$ bids
$n^{3}$ on the item $H(1,s)$ ($n^{3}$ is $\mathcal{T}_{1}$’s value for
$H(1,s)$, and $1$ is $\mathcal{T}_{1}$’s bidding parameter by Lemma 6), it
follows that $\mathcal{C}(1,s)$ wins $H(1,s)$ by paying $n^{3}$. Similarly,
$\mathcal{T}_{1}$ also bids $n^{3}$ on the item $H(1,s^{\prime})$. However,
since $\tilde{x}_{s^{\prime}}$ can be $>1$ or exactly $1$, we only know that
bidder $\mathcal{C}(1,s^{\prime})$ wins at least a fraction of the item
$H(1,s^{\prime})$. Let $\tau$ denote the fraction of $H(1,s^{\prime})$ which
$\mathcal{C}(1,s^{\prime})$ wins, and then $\mathcal{C}(1,s^{\prime})$ pays
$\tau n^{3}$ for this item.

In summary, bidder $\mathcal{C}(1,s)$ gets total value at most $2n^{3}+4n-2$
and makes total payment at least
$n^{3}+\sum_{t\in[n]}\tilde{x}_{t}-2\delta_{2}\tilde{x}_{s}+\sum_{t\in[n]}\delta_{1}A_{st}\tilde{y}_{t}$.
Thus,

bidder $\mathcal{C}(1,s)$’s CPA
$\displaystyle\geq\frac{n^{3}+\sum_{t\in[n]}\tilde{x}_{t}-2\delta_{2}\tilde{x}_{s}+\sum_{t\in[n]}\delta_{1}A_{st}\tilde{y}_{t}}{2n^{3}+4n-2}$
$\displaystyle=\frac{n^{3}+\sum_{t\in[n]}\tilde{x}_{t}+\sum_{t\in[n]}\delta_{1}A_{st}\tilde{y}_{t}-O(\delta_{2})}{2n^{3}+4n-2}.$

Bidder $\mathcal{C}(1,s^{\prime})$ gets total value at least
$(1+\tau)n^{3}+4n-2-2\delta_{2}$ and makes total payment at most
$(1+\tau)n^{3}+\sum_{t\in[n]}\tilde{x}_{t}+\sum_{t\in[n]}\delta_{1}A_{s^{\prime}t}\tilde{y}_{t}$.
Thus,

$\displaystyle\textrm{bidder $\mathcal{C}(1,s^{\prime})$'s CPA}\leq$
$\displaystyle\frac{\tau
n^{3}+\sum_{t\in[n]}\tilde{x}_{t}+\sum_{t\in[n]}\delta_{1}A_{s^{\prime}t}\tilde{y}_{t}}{(1+\tau)n^{3}+4n-2-2\delta_{2}}$
$\displaystyle\leq$
$\displaystyle\frac{n^{3}+\sum_{t\in[n]}\tilde{x}_{t}+\sum_{t\in[n]}\delta_{1}A_{s^{\prime}t}\tilde{y}_{t}}{2n^{3}+4n-2-2\delta_{2}}$
(because the first upper bound is maximized when $\tau=1$) $\displaystyle=$
$\displaystyle\frac{n^{3}+\sum_{t\in[n]}\tilde{x}_{t}+\sum_{t\in[n]}\delta_{1}A_{s^{\prime}t}\tilde{y}_{t}}{2n^{3}+4n-2}\cdot\left(1+\frac{2\delta_{2}}{2n^{3}+4n-2-2\delta_{2}}\right)$
$\displaystyle=$
$\displaystyle\frac{n^{3}+\sum_{t\in[n]}\tilde{x}_{t}+\sum_{t\in[n]}\delta_{1}A_{s^{\prime}t}\tilde{y}_{t}+O(\delta_{2})}{2n^{3}+4n-2}.$

Combining our lower bound of bidder $\mathcal{C}(1,s)$’s CPA and upper bound
of bidder $\mathcal{C}(1,s^{\prime})$’s CPA, we get

$\textrm{bidder $\mathcal{C}(1,s)$'s CPA}-\textrm{bidder
$\mathcal{C}(1,s^{\prime})$'s
CPA}\geq\frac{\sum_{t\in[n]}\delta_{1}A_{st}\tilde{y}_{t}-\sum_{t\in[n]}\delta_{1}A_{s^{\prime}t}\tilde{y}_{t}-O(\delta_{2})}{2n^{3}+4n-2}.$
(16)

Putting Eq. (15) and Eq. (16) together, we have that

$\sum_{t\in[n]}\delta_{1}A_{st}\tilde{y}_{t}-\sum_{t\in[n]}\delta_{1}A_{s^{\prime}t}\tilde{y}_{t}-O(\delta_{2})\leq\sum_{t\in[n]}\delta_{1}A_{st}-\sum_{t\in[n]}\delta_{1}A_{s^{\prime}t},$

which implies that

$\sum_{t\in[n]}A_{st}(\tilde{y}_{t}-1)-\sum_{t\in[n]}A_{s^{\prime}t}(\tilde{y}_{t}-1)\leq
O(\delta_{2}/\delta_{1})=O(1/n^{2}).$

This is exactly Eq. (14), which completes the proof. ∎

##  Appendix C Proof of Upper Bound of Price of Anarchy

###### Proof of Theorem 4.

We will construct two instances such that $PoA=O(1/\log(T_{max}/T_{min}))$ for
the first instance, and $PoA=O(1/\log(\beta_{max}/\beta_{min}))$ for the
second instance. The theorem follows by picking the instance with worse $PoA$
upper bound from those two instances (depending on which of $T_{max}/T_{min}$
and $\beta_{max}/\beta_{min}$ is larger). We let
$\varepsilon=\frac{1}{8^{n}}$.

The tCPA-instance. Bidders: There is a tCPA bidder $j_{2}$ with tCPA $1$, and
there is another set of tCPA bidders
$J_{1}:=\bigcup_{\ell\in[n]}J_{1}^{\ell}$, where $J_{1}^{\ell}$ contains
$2^{n-\ell}$ tCPA bidders with tCPA $2^{\ell}$ for each $\ell\in[n]$.
Moreover, there is two QL bidders $q_{1}$ and $q_{2}$.

Channels: There are two channels $k_{1}$ and $k_{2}$. Channel $k_{2}$ owns
only one impression $i_{2}$ which is of value $1$ to bidder $j_{2}$ and value
zero to everyone else. Channel $k_{1}$ owns impressions
$\\{i_{1},i_{1}^{\prime}\\}\cup\\{i_{1}^{j}\mid j\in J_{1}\\}$. Impression
$i_{1}$ is of value $1-2\varepsilon$ to bidder $j_{2}$, value $1$ to bidder
$q_{1}$, and value zero to everyone else. Impression $i_{1}^{\prime}$ is of
value $\varepsilon$ to bidder $j_{2}$, value $1$ to bidder $q_{2}$, and value
zero to everyone else. For any $j\in J_{1}^{\ell}$ for each $\ell\in[n]$,
impression $i_{1}^{j}$ is of value $1$ to bidder $j$, value $\varepsilon
2^{\ell}$ to bidder $j_{2}$, and value zero to everyone else.

Global model: We first consider the global model and prove that the total
revenue is $n2^{n}$ if both channels set zero reserve prices. Since only
bidder $j_{2}$ has non-zero value for impression $i_{2}$, and the reserve
price is zero, bidder $j_{2}$ will get $i_{2}$ of value $1$ for zero cost.
Thus, bidder $j_{2}$’s tCPA constraint is not tight if $j_{2}$ only gets
impression $i_{2}$. It follows by item (4) of Definition 1 that bidder $j_{2}$
should increase the bidding parameter until getting tied for a new impression.

Now we show that bidder $j_{2}$ must be tied first for impression $i_{1}$ and
then impression $i_{1}^{\prime}$, before getting tied for any impression in
$\\{i_{1}^{j}\mid j\in J_{1}\\}$. Notice that by Assumption 1, bidder $q_{1}$
would bid $1$ for impression $i_{1}$, and bidder $q_{2}$ would bid $1$ for
impression $i_{1}^{\prime}$, and bidder $j\in J_{1}^{\ell}$ for any
$\ell\in[n]$ would bid at least $2^{\ell}$ for impression $i_{1}^{j}$. For
bidder $j_{2}$ to be tied with a bid $1$ for impression $i_{1}$, $j_{2}$’s
bidding parameter only needs to be $\frac{1}{1-2\varepsilon}$, and moreover,
for bidder $j_{2}$ to be tied with a bid $1$ for impression $i_{1}^{\prime}$,
$j_{2}$’s bidding parameter needs to be $\frac{1}{\varepsilon}$, and
furthermore, for bidder $j_{2}$ to be tied with a bid $2^{\ell}$ for
impression $i_{1}^{j}$ with $j\in J_{1}^{\ell}$ for any $\ell\in[n]$,
$j_{2}$’s bidding parameter needs to be at least $\frac{2}{\varepsilon}$.
Thus, $j_{2}$ must be tied for impression $i_{1}$ first. Notice that even if
impression $i_{1}$ is fully sold to bidder $j_{2}$ at a cost $1$, bidder
$j_{2}$’s total spend for impressions $i_{1}$ and $i_{2}$ divided by their
total value is $\frac{1}{2-2\varepsilon}$, which is still below $j_{2}$’s
tCPA. It follows by item (4) of Definition 1 that bidder $j_{2}$ will increase
the bidding parameter to $\frac{1}{\varepsilon}$ to be tied for impression
$i_{1}^{\prime}$ and get a small fraction of $i_{1}^{\prime}$.

From the discussion of the above two paragraphs, it follows that bidder
$j_{2}$’s bidding parameter is at least $\frac{1}{\varepsilon}$. Hence, bidder
$j_{2}$’s bid is at least $2^{\ell}$ for impression $i_{1}^{j}$ with $j\in
J_{1}^{\ell}$ for any $\ell\in[n]$, and because $j_{2}$ is bidding above the
reserve price for impression $i_{1}^{j}$ (which is zero), by item (2) of
Definition 1, impression $i_{1}^{j}$ must be fully sold (for a cost at least
$2^{\ell}$). It follows that channel $k_{2}$’s revenue is at least
$\sum_{\ell\in[n]}2^{\ell}\cdot|J_{1}^{\ell}|=\sum_{\ell\in[n]}2^{\ell}\cdot
2^{n-\ell}=n2^{n}$.

Local model: By Assumption 1, bidder $j_{2}$ would use a bidding parameter at
least $j_{2}$’s tCPA $1$. Thus, in the local model, if channel $k_{2}$ sets a
reserve price $1-\varepsilon$ for impression $i_{2}$, by item (2) of
Definition 1, $i_{2}$ will be fully sold to bidder $j_{2}$ for a cost
$1-\varepsilon$ in the subgame equilibrium regardless of channel $k_{1}$’s
reserve price. Hence, we know that channel $k_{2}$’s revenue in the local
model is at least $1-\varepsilon$. In other word, in the local model, bidder
$j_{2}$ spends at least $1-\varepsilon$ for impression $i_{2}$.

Now we show that in the local model, bidder $j_{2}$’s bidding parameter is at
most $\frac{1}{1-2\varepsilon}$ in the subgame equilibrium. Suppose for
contradiction bidder $j_{2}$’s bidding parameter is strictly larger than
$\frac{1}{1-2\varepsilon}$, then it follows that $j_{2}$’s bid for impression
$i_{1}$ is strictly larger than $1$, and thus, bidder $j_{2}$ would win the
full impression $i_{1}$ for a cost larger than $1$. Therefore, the total spend
for impressions $i_{1}$ and $i_{2}$ divided by their total value is at least
$\frac{2-\varepsilon}{2-2\varepsilon}>1$ (and taking other impressions into
account will only make this worse as other impressions need bidder $j_{2}$ to
use even higher bidding parameter), which violates bidder $j_{2}$’s tCPA
constraint.

Therefore, with a bidding parameter at most $\frac{1}{1-2\varepsilon}$, bidder
$j_{2}$ bids at most $\frac{\varepsilon 2^{\ell}}{1-2\varepsilon}$ for
impression $i_{1}^{j}$ with $j\in J_{1}^{\ell}$ for any $\ell\in[n]$. Note
that $\frac{\varepsilon 2^{\ell}}{1-2\varepsilon}\leq\frac{\varepsilon
2^{n}}{1-2\varepsilon}\leq 2^{-n}$ by our choice of $\varepsilon$. Thus,
bidder $j_{2}$’s bid for impression $i_{1}^{j}$ with $j\in J_{1}^{\ell}$ for
any $\ell\in[n]$ is negligible compared to the value of impression $i_{1}^{j}$
to bidders $j$, which means that bidder $j_{2}$’s bid can only make a
negligible difference for the cost of impression $i_{1}^{j}$ to bidders $j$.
Finally, since channel $k_{2}$ uses a uniform reserve price, and $J_{1}$ is
essentially the same “equal-revenue” instance as in Lemma 3, we have that the
revenue of channel $k_{2}$ is $O(2^{n})$.

To conclude, $PoA$ for our tCPA instance is
$O(1/n)=O(1/\log(T_{max}/T_{min}))$.

The Budgeted-instance. The construction is analogous to the tCPA-instance:

Bidders: There is a Budgeted bidder $j_{2}$ with budget $1$, and there is
another set of Budgeted bidders $J_{1}:=\bigcup_{\ell\in[n]}J_{1}^{\ell}$,
where $J_{1}^{\ell}$ contains $2^{n-\ell}$ Budgeted bidders with budget
$2^{\ell}$ for each $\ell\in[n]$. Moreover, there is two QL bidders $q_{1}$
and $q_{2}$.

Channels: There are two channels $k_{1}$ and $k_{2}$. Channel $k_{2}$ owns
only one impression $i_{2}$ which is of value $1$ to bidder $j_{2}$ and value
zero to everyone else. Channel $k_{1}$ owns impressions
$\\{i_{1},i_{1}^{\prime}\\}\cup\\{i_{1}^{j}\mid j\in J_{1}\\}$. Impression
$i_{1}$ is of value $1$ to bidder $j_{2}$, value $1-\varepsilon$ to bidder
$q_{1}$, and value zero to everyone else. Impression $i_{1}^{\prime}$ is of
value $\varepsilon$ to bidder $j_{2}$, value $1$ to bidder $q_{2}$, and value
zero to everyone else. For any $j\in J_{1}^{\ell}$ for each $\ell\in[n]$,
impression $i_{1}^{j}$ is of value $1$ to bidder $j$, value $\varepsilon
2^{\ell}$ to bidder $j_{2}$, and value zero to everyone else.

The proof of $PoA\leq O(1/\log({\beta_{max}}/{\beta_{min}}))$ for the
Budgeted-instance is analogous to our proof for the tCPA instance. ∎

##  Appendix D Proofs for Scaled Channels

###  D.1 Proof of Theorem 7

###### Proof of Theorem 7.

Consider the following instance. There are two symmetric channels (i.e.,
$\gamma_{k}=1/2)$ and two tCPA bidders with targets $T_{1}=2$ and $T_{2}=1$.
There are five types of impressions owned by the channels ordered by the
publisher price on each of them: $I_{1},I_{2},I_{3},I_{4}$ and $I_{5}$ where
$\delta>\epsilon$. The publishers reserve prices and bidders valuations are
described in Figure 1.

Figure 1: Instances used in Theorem 7 to show that $PoA=0$.

Global model: Observe that for this case a feasible solution for the channels
is to set a uniform reserve price of $1$. For this subgame, since all
impressions cost at least $1$, Bidder 2 does not have any slack to buy
impressions that are more than $1$. Hence, Bidder 2 bids $b_{2,i}=v_{2,i}$.
Consequently, Bidder $1$ bids $b_{1,i}=(2+\delta)v_{1,i}$. The outcome of the
auctions is that Bidder 1 gets all impressions $I_{1},I_{2}$ for a price of
$1$ and a subset of impressions of $I^{\prime}_{5}\subseteq I_{5}$ for a price
$2+\delta$ with $|I^{\prime}_{5}|=(|I_{1}|+(1+\epsilon)|I_{2}|)/\delta$ so
that Bidder 1 tCPA constraint is tight. Thus, in this subgame, the revenue
collected by the two channels is approximately
$|I_{1}|+|I_{2}|+|I_{3}|+(1+2/\delta)(|I_{1}|+|I_{2}|)$ for small $\epsilon$.
Since setting a reserve price of $1$ in both channels is a feasible policy in
global model, we conclude that for small $\epsilon$,
$Rev(Global)\geq|I_{1}|+|I_{2}|+|I_{3}|+(1+2/\delta)(|I_{1}|+|I_{2}|)$.

Local model: We assert that there is an equilibrium where both channels set
reserve prices to $0$. In the on-path subgame of the equilibrium, Bidder $1$
bids $b_{1,i}=(2+\delta)v_{1,i}$ and Bidder $2$ bids $b_{2,i}=2v_{2,i}$. With
this bidding strategies, Bidder 1 gets all impressions $I_{1},I_{2}$ and, by
assuming $|I_{1}|<|I_{2}|$, we have that Bidder $1$ has slack to get a subset
$I_{5}^{\prime}\subseteq I_{5}$ to make its tCPA constraint binding. Bidder
$2$ gets all impressions $I_{3}$ and subset $I^{\prime}_{4}\subseteq I_{4}$ to
make its tCPA constraint binding. Under this bidding behavior, for small
$\epsilon$, we have that $I^{\prime}_{4},I^{\prime}_{5}$ are small
$O(\epsilon)$. Hence, the revenue each channel obtains is approximately
$(2(|I_{1}|+|I_{2}|)+|I_{3}|)/2$.

We now show that setting reserve prices to $0$ is an equilibrium for the
channels. Since the game is symmetric for each channel we only consider
channel 1’s deviations. If Channel 1 sets a reserve $r_{1}>2+\delta$, in the
subgame, Bidder 1 and Bidder 2 only buy impressions from Channel 2. Hence,
Channel 1 gets a revenue of $0$. If $r_{1}\in(2,2+\delta]$, Bidder $2$ buys
impressions only from channel 2 which implies that Channel 1 loses $|I_{3}|/2$
relative to setting $r_{1}=0$. Bidder 1, instead, pays $r_{1}$ for impressions
$I_{1},I_{2}$. Compared to setting a reserve $r_{1}=0$, the gain channel 1
obtains from bidder 1 is no more than $\delta(|I_{1}|+|I_{2}|)$. Thus, for
small $\delta$, deviating to $r_{1}\in[2+\epsilon,2+\delta)$ is not
profitable. If $r_{1}\leq 2$, then the revenue coming from Bidder $1$ is the
same as the case of $r_{1}=0$, since the price is determined by bidder $2$’s
bid. Regarding the revenue coming from bidder $2$, we have that Channel 1 gets
$(1-\epsilon)r_{1}$ on impressions $I_{3}$ and gets $x$ impressions of $I_{4}$
where $x=\frac{(1-\epsilon)(2-r_{1})}{2(p_{4}-1)}|I_{3}|$. Thus, the revenue
gains by Channel 1 is $(1-\epsilon)|I_{3}|+x(1-p_{4}/2)$. Since $p_{4}=2$ we
have that Channel 1 is indifferent on setting any reserve price
$r_{1}\in[0,2]$. We conclude that setting a reserve price $r_{1}=0$ is optimal
and hence an equilibrium.

To conclude the proof, by comparing the global and local models we obtain that
for $\epsilon$ small,

$PoA\leq\frac{2(|I_{1}|+|I_{2}|)+|I_{3}|}{|I_{1}|+|I_{2}|+|I_{3}|+(1+2/\delta)(|I_{1}|+|I_{2}|)}.$

We conclude the proof by taking $\delta\to 0$. ∎

###  D.2 Proof of Theorem 8

We split the proof Theorem 8 in the following steps.

First, we show that to bound the $PoA$ without loss of generality we can focus
on instances where the bidder is a tCPA bidder.

######  Lemma 11.

Suppose that there is a single bidder in the game. If the bidder is either a
Budgeted bidder or QL bidder then $RevG(Local)=RevG(Global)$.

###### Proof.

If the bidder is a QL bidder, the channel’s reserve price optimization problem
is independent of the other channels. Thus, both Global and Local models
achieve the same revenue.

If the bidder is a Budgeted bidder, we claim that in all equilibria of the
local model the bidder spend its budget. Suppose not, then one of the channel
can slightly increase the reserve price while keeping the Budgeted bidder
unconstrained. Thus, the bidder does not change its bids and the channel
deviating increases its revenue, which is contradiction. We conclude that the
total revenue in local model is the bidder’s budget which matches the optimal
liquid welfare. This implies that $RevG(Local)=RevG(Global)$. ∎

The next step characterizes the optimal reserve price for the global model.

######  Lemma 12 (Global model: optimal reserves).

For a single tCPA bidder with constraint $T$ the solution of the global model
is that every channel sets the lowest reserve price such that the tCPA bidder
constraint is tight. That is, channels set
$\underline{r}=\operatorname*{arg\,min}\\{\sum_{i\in I}v_{i}=T\sum_{i\in
I}\max\\{r,p_{i}\\}\\}$.

###### Proof of Lemma 12.

The proof-idea follows from the fact that the revenue from a tCPA-constraint
bidder is roughly tCPA-target times the volume of impressions acquired by the
bidder. Because volume is inversely proportional to reserve prices, in the
global model, all channels set a reserve price as low as possible conditional
that the tCPA constraint remains binding.

We fist show that in the global model without loss all channels can set the
same reserve price. Indeed, because the bidder is using a uniform bid across
all impressions, we have that its final bid in the value-space is the same in
each channel. In particular, observe that from the bidder’s standpoint it is
equivalent to face a reserve price $r_{k}$ on Channel $k$’s impressions or to
face the same reserve price $r=\sum_{k\in K}\gamma_{k}r_{k}$ in all channels.
Thus, from the bidder’s perspective its bidding behavior does not change by