Notes on Efficient Auctions [Deng etal.-21]

Paper link

Table of contents

• Problem Setting
• Auctions
  • Boosting
  • GSP and VCG
• Auto-bidders
  • Assumptions
  • Uniform bidding
• Optimization problem
  • OPT
  • Revenue
  • An upper bound
  • A lower bound for second-price and uniform boosting
  • Extend the lower bound to VCG

Surplus-maximizing bidders vs auto-bidders

1. A surplus-maximizing bidder aims to optimize is quasilinear utility (i.e., the total value received minus the payment).

   • Here, the payment appears in the objective function.

2. An auto-bidder is usually provided with constraints such as budget and average cost-per-conversion, where the goal is to optimize metrics such as the number of conversions.

   • Here, the payment appears in the constraints only.

Problem setting

An instance of the problem: $I = \langle n, m, \{s\}_j, \{v\}_{ij}, \{q\}_{jk} \rangle$.

1. $n$ bidders

2. $m$ position auctions; $s_j$ denote the number of slots of auction $j \in [m]$.

   • An example. Each advertiser chooses a set of relevant keywords. When a keyword is searched by a user, associated advertisers enters an auction, bidding for the collection of slots (positions) on the page. Here, each auction $j \in [m]$ is triggered by a keyword search, where there are $s_j$ available slots to display adds.

3. Each bidder $i$ has a baseline valuation $v_{ij}$ for each auction $j$ (i.e., for each keyword).

   • Note, not explicitly for each slot in an auction.

4. In an auction $j$, slots are ranked based on their importance. Let $q_{jk} \in [0, 1]$ denote the normalized importance factor, which is non-increasing in $k$. That is, $q_{j1}$ is the most important slot and $q_{js_j}$ is the least important slot.

   • $q_{jk}$ can be interpreted as the click-through rate of $k$th slot in auction $j$.

Auctions

1. $b_{ij}$ denotes $i$'s bid in auction $j$.

   • Each bidder $i$ submits one bid per-auction, not per-item in an auction.

   • Also note that, bids are not parts of a problem instance.

2. $x_{ijk}$ is the binary allocation, either $0$ or $1$, of $k$th slot in auction $j$ to player $i$.

3. $p_{ij}$ is the payment of player $i$ in auction $j$.

   • The revenue of the auctioneer is
   $$R = \sum_{i \in [n], j \in [m]} p_{ij}$$

Boosting

In each auction $j$, a player $i$ receives a boost $z_{ij} \geq 0$.

• The ranking score (used by the mechanism to determine the allocations) of $i$ in auction $j$ becomes

$$b_{ij} + z_{ij}$$

GSP and VCG

Two types of auctions are considered: GSP and VCG.

Allocation rules

The allocation rules are the same for the two auctions:

• Give the $k$th important slot to the bidder with the $k$th highest ranking score (after boosting).

  Question [2:14PM - 05/05/2025]

  Why is this a valid allocation rule for VCG, if we allocate based on the boosted bids rather than the original bids (for now, we assume they bid their valuations).

  Is it the case that a higher bid always implies a higher boost? If not, then this rule does not maximizes the welfare in general.

  For example, if there could be a bidder with a very low bid (low valuation), but somehow receives a very high boost. Under this rule, it gets a high-position slot.

  Also, why is this rule monotone? If not, then the resulting VCG auction is not incentive compatible?

  Partial answer. [06:40PM - 05/07/2025]

  My guess is that this rule is monotone (since the payment rule below indeed implements it) because the we only consider boosting mechanisms where boosts are independent of or monotone w.r.t the bids (e.g., uniform boosting introduced later).

  Otherwise, this allocation rule is clearly not monotone for arbitrary computation of boosts based on the bids. For instance, if we have a rule which decreases the boost of a bidder if its bid is increased, then this rule is not monotone, since biding more might lead to a lower rank.

Payment rules

Fix an auction $j$ and a bidder $i$. Let $\hat{b}_{jk}$ denote the $k$th highest ranking score in auction $j$. Suppose $i$ is assigned to slot $k$.

Let $(\cdot)^+$ denote $\max \{0, \cdot\}$.

1. GSP:

$$p_{ij} = (\hat{b}_{j \; k+1} - z_{ij})^+ \cdot q_{jk}$$

• For quasilinear utilities, this is IR because $\hat{b}_{j k} = b_{ij} + z_{ij} \geq \hat{b}_{j \; k+1}$.

• Let $i'$ be the bidder assigned to the $(k+1)$th important slot. Note that an alternative payment rule: $(\hat{b}_{j \; k+1} - z_{i'j})^+ \cdot q_{jk}$ might not be IR. This is because the ranking (to computing allocation) is not based on the original bid but the boosted bid.

• The resulting auction is not IC (under quasilinear utilities). This is fine since GSP is not IC to begin with.

2. VCG:

   $$p_{ij} = \sum_{t = k + 1}^{s_j} (\hat{b}_{tj} - z_{ij})^+ \cdot (q_{t-1 \; j} - q_{tj})$$

   • The intuition of this definition is clear: if we discard $i$, the allocations of those who are ranked higher than $i$ are not affected, whereas the allocation of those lowered ranked gets move one position higher in the rank in an optimal allocation.

   • Note. For this definition of payment to make sense, I think we are working with the assumption that the number of bidders equals to the number of slots in each auction. This can be assumed since we can always add proxy slots with zero CTRs.

     • If there are more bidders than slots, then the above payment forgets to account for the bidder with the $(s_j +1)$th highest ranking score.

   • For quasilinear utilities, the resulting auction is IR since $\hat{b}_{tj} - z_{ij} \leq b_{ij}$, for $t = k+1, ..., s_j$ (assuming quasilinear utilities). It is also not hard to verify that the auction is IC for quasilinear utilities.

Auto-bidders

Assumptions

1. All bidders considered are auto-bidders with budget and ROS constraints.

2. W.l.o.g., ROS means the total payment is at most the total values received.

Uniform bidding strategies

1. Each bidder $i$ computes a pacing multiplier $\alpha_i$ (the same multiplier used in all auction), where for each auction $j \in [m]$,

$$b_{ij} = \alpha_i v_{ij}$$

• Note that, for an individual auction, it is possible that the bidder's value received is less than its payment for that auction (see the example of Lemma 3.2 in the paper.) What ROS means is that the total payment is at most the total values received, over all auctions.

• The multiplier $\alpha_i$ can be greater than $1$ (see the example in Lemma 3.2 in the paper.), as long as the budget and the ROS constraints are satisfied.

2. The goal of each bidders is to find an $\alpha_i$ that is value-maximizing:

$$\sum_{j \in [m]} \sum_{k \in [s_j]} x_{ijk} \cdot v_{ij} \cdot q_{kj}$$

over the outcomes of the $m$ auctions, s.t. the budget constraint and ROS are satisfied.

The set of multipliers

Fix an auction. We say a multiplier vector $\vec{\alpha}$ is valid (w.r.t this auction) if no bidder violates its budget and ROS constraint under $\vec{\alpha}$. We say $\vec{\alpha}$ is dominant if all bidder's $\alpha_i$ is maximal (i.e., any slight increase violates its budget constraint or ROS).

Let $\Theta$ be the set of multiplier vectors that are both valid and dominant.

Note that, given a problem instance and a mechanism, the set $\Theta$ is fixed.

The optimization problem

Goal is to design auctions (an allocation rule + a payment rule) that maximizes the liquid welfare:

$$\text{LW}(x) = \sum_{i \in [n]} \min{} \left\{B_i, \sum_{j \in [m]} \sum_{k \in [s_j]} x_{ijk} \cdot v_{ij} \cdot q_{jk} \right\}$$

Fix $i$, one can interpret the $\min \{...\}$ part as the maximum payment one can extract from $i$, under the budget constraint and the ROS constraint.

Remark

Note that liquid welfare is not computed from the bids or the payments. Given a problem instance $(n, m \{v\}_i, \{s\}_j, \{q\}_{kj})$, LW is uniquely determined by an allocation $x$ (no auctions even need to be further defined). This leads to my following question:

OPT

Given a problem instance, OPT is the maximum liquid welfare among all possible allocations. Note that, it is not over all possible (DSIC) auctions, since an allocation is enough to compute LW.

The performance of a mechanism $\mathcal{A}$ is defined as is its competitive ratio:

$$\min_{\alpha \in \Theta} \frac{\text{LW}(x(\alpha, \mathcal{A}))}{OPT}$$

Since this is a maximization problem, the higher the competitive ratio (at most $1$), the better the mechanism.

Revenue

Defined as

$$R = \sum_{i \in [n], j \in [m]} \; p_{ij}(\alpha, \mathcal{A})$$

An upper bound on the competitive ratio

Here is an instance of the problem given in the paper. This instance establishes an upper bound of

$$\frac{c+1}{c+2}$$

of competitive ratio for VCG and GSP under uniform boosting (defined below).

Problem instance

1. Two bidders.

2. Two single-slot auctions.

   • In this case, both VCG and GSP reduced to second-price auctions (with boosting).

3. Uniform boosting:

$$z_{ij} = c \cdot v_{ij}$$

for a uniform $c \geq 0$ over the bidders. In this case, the boosted bid of bidder $i$ in auction $j$ is of the form: $(\alpha_i + c) \cdot v_{ij}$.

4. There is only RoS constraint, no budget constraint (i.e., $B_i = \infty$ for all users $i$).

5. The importance factors of the slots are normalized to $1$.

Upper bound example

1. Any $d > 0$, small $\epsilon > 0$, boost weight $c \leq d$.

2. For auction 1: $v_{11} = 1 + d$, $v_{21} = 0$.

3. For auction 2: $v_{12} = \epsilon$, $v_{22} = 1$.

4. The particular $\alpha \in \Theta$ is defined as follows:

   • Bidder $1$: $\alpha_1 > (c + 1) / \epsilon$.

   • Bidder $2$: $\alpha_2 = 1$.

Remark

One can easily verify the correctness of the lemma based on the definitions of the auctions, boots, and the competitive ratio.

Nevertheless, I believe that the computation in the proof given in the paper is not completely correct. Though, it does not affect the correctness of the lemma.

In particular. Here are two claims made in that proof that I found incorrect:

1. [Page 5] It is straightforward to verify that the return on ad spend constraints are satisfied: the first bidder receives total value $1 + d + \epsilon$ and pays $1$.

Note. Unless I understood their mechanism wrongly, otherwise, the payment of bidder $1$ is not $1$.

First, the payment from the first auction for the first bidder is always zero. Now consider the second auction. Note that, in the definition of auction with boosting, the payment of the first bidder is the boosted bid of the second bidder ($c + 1$ in this case) minus the boost of the first bidder ($\epsilon c$ in this case). Thus, the payment of the first bidder in the second auction is $1 + (1 - \epsilon) c$.

Note that, since $c \leq d$, we still have $1 + d + \epsilon \geq 1 + (1 - \epsilon) c$. That is, the RoS constraint is satisfied.

2. [Page 5] For the second bidder to deviate, she has to use a bid multiplier $\alpha_2 \geq \alpha_1 \cdot \epsilon > c + 1$ to win the second auction, resulting in a payment $c + 1$.

Note. Not completely sure how the above bounds on the multiplier and the payments are derived. First, it is clear that bidder $2$ never wins the first auction, since her valuation is $0$. For the second auction, the boosted bid of bidder $1$ is $\epsilon \cdot (\alpha_c + 1)$. Thus, for bidder $2$ to win the second auction, her multiplier must be greater than $\epsilon \cdot \alpha_1 - (1 - \epsilon) \cdot c$. Also, the payment of bidder $2$, in the case of winning the second auction, is

$$\epsilon \cdot \alpha_1 - (1 - \epsilon) \cdot c \geq (c + 1) - (1 - \epsilon) \cdot c > 1.$$

for fixed $\epsilon > 0$.

Note that the claim by the authors still holds: if bidder $2$ were to change her multiplier to win auction $2$, her payment will be greater than her value received, violating the RoS constraint.

A lower bound for second-price under uniform boosting

Assumptions

1. There is no budget constraint for all bidders.

2. The underlying $m$ auctions are second-price auctions with uniform boost of weight $c$.

   • Single-slot auctions.

Remark - Why boosting helps in the above case

Here is my currently understanding of why boosting helps. Consider the case without boosting (i.e., $c = 0$). Here, we have

$$p_{i^*_j \; j} \geq \alpha_{i^{OPT}_j} \cdot v_{i^{OPT}_j \; j} \geq v_{i^{OPT}_j \; j}$$

It follows that

$$\begin{align} \text{Wel}(x) \geq R(x) \geq \sum_{j \in [m] \setminus A} v_{i^{OPT}_j \; j} \end{align}$$

As a result,

$$\begin{align*} OPT &= \text{Wel}(x) + \sum_{j \in [m] \setminus A} v_{i^{OPT}_j \; j} - \sum_{j \in [m] \setminus A} v_{i^{*}_j \; j}\\ &\leq 2 \cdot \text{Wel}(x) - \sum_{j \in [m] \setminus A} v_{i^{*}_j \; j} \end{align*}$$

Thereby a competitive ratio of $2 - \epsilon$ (Note that, if $\sum_{j \in [m] \setminus A} v_{i^{*}_j \; j}$ is zero, then either $A$ is empty, and thus Wel = OPT, or the valuations of the winners in $[m] \setminus A$ are zero - but in this case, the boosted bids are also zero, again, Wel = OPT).

With uniform boosting, the payment is increased (ideally by a lot):

$$\begin{align*} p_{i^*_j \; j} &\geq (c + 1) \cdot v_{i^{OPT}_j \; j} - c \cdot v_{i^*_j \; j} \\ &= v_{i^{OPT}_j \; j} + c \cdot (v_{i^{OPT}_j \; j} - v_{i^*_j \; j}) \end{align*}$$

As a result, the lower bound on the welfare is increased:

$$\text{Wel}(x) \geq R(x) \geq (c + 1) \cdot \sum_{j \in [m] \setminus A} v_{i^{OPT}_j \; j} - c \cdot \sum_{j \in [m] \setminus A} v_{i^*_j \; j}$$

Importantly, in the case without boosting, $\text{Wel}(x)$ is lower bounded by a multiplicative factor of $1$ for $\sum_{j \in [m] \setminus A} v_{i^{OPT}_j \; j}$ (see Eq (2)). On the other hand, with boosting, $\text{Wel}(x)$ is now lower bounded by a multiplicative factor of $(c + 1)$ for $\sum_{j \in [m] \setminus A} v_{i^{OPT}_j \; j}$.

To intuitively explain this: Boosting amplifies the payments of mis-allocated items (i.e., those not awarded to the highest-valuing bidder). In such cases, the winner pay (much) higher than it would without boosting. In particular, the payment becomes large enough that, collectively, under RoS, the total welfare is close to the optimal case where each item is allocated to its highest-valued bidder.

Extend the lower bound to VCG

One can extend the above lower bound to multi-slot VCG auctions defined previously. Here, one key property of $c$-uniform boosting is the following:

• For any two bidders $i$ and $i'$, and for any auction $j$ such that $v_{ij} > v_{i'j}$, we have

$$z_{ij} - z_{i'j} \geq c \cdot (v_{ij} - v_{i'j})$$

In general, any boosting strategy that satisfies the above property is called $c$-value-competitive.