Published on

Notes on Efficient Auctions [Deng etal.-21]

Paper link

Table of contents

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=n,m,{s}j,{v}ij,{q}jkI = \langle n, m, \{s\}_j, \{v\}_{ij}, \{q\}_{jk} \rangle.

  1. nn bidders

  2. mm position auctions; sjs_j denote the number of slots of auction j[m]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[m]j \in [m] is triggered by a keyword search, where there are sjs_j available slots to display adds.
  3. Each bidder ii has a baseline valuation vijv_{ij} for each auction jj (i.e., for each keyword).

    • Note, not explicitly for each slot in an auction.
  4. In an auction jj, slots are ranked based on their importance. Let qjk[0,1]q_{jk} \in [0, 1] denote the normalized importance factor, which is non-increasing in kk. That is, qj1q_{j1} is the most important slot and qjsjq_{js_j} is the least important slot.

    • qjkq_{jk} can be interpreted as the click-through rate of kkth slot in auction jj.

Auctions

  1. bijb_{ij} denotes ii's bid in auction jj.

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

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

  2. xijkx_{ijk} is the binary allocation, either 00 or 11, of kkth slot in auction jj to player ii.

  3. pijp_{ij} is the payment of player ii in auction jj.

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

Boosting

In each auction jj, a player ii receives a boost zij0z_{ij} \geq 0.

  • The ranking score (used by the mechanism to determine the allocations) of ii in auction jj becomes
bij+zijb_{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 kkth important slot to the bidder with the kkth 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 jj and a bidder ii. Let b^jk\hat{b}_{jk} denote the kkth highest ranking score in auction jj. Suppose ii is assigned to slot kk.

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

  1. GSP:
pij=(b^j  k+1zij)+qjkp_{ij} = (\hat{b}_{j \; k+1} - z_{ij})^+ \cdot q_{jk}
  • For quasilinear utilities, this is IR because b^jk=bij+zijb^j  k+1\hat{b}_{j k} = b_{ij} + z_{ij} \geq \hat{b}_{j \; k+1}.

  • Let ii' be the bidder assigned to the (k+1)(k+1)th important slot. Note that an alternative payment rule: (b^j  k+1zij)+qjk(\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.

  1. VCG:

    pij=t=k+1sj(b^tjzij)+(qt1  jqtj)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 ii, the allocations of those who are ranked higher than ii 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 (sj+1)(s_j +1)th highest ranking score.
    • For quasilinear utilities, the resulting auction is IR since b^tjzijbij\hat{b}_{tj} - z_{ij} \leq b_{ij}, for t=k+1,...,sjt = 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 ii computes a pacing multiplier αi\alpha_i (the same multiplier used in all auction), where for each auction j[m]j \in [m],
bij=αivijb_{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 αi\alpha_i can be greater than 11 (see the example in Lemma 3.2 in the paper.), as long as the budget and the ROS constraints are satisfied.

  1. The goal of each bidders is to find an αi\alpha_i that is value-maximizing:
j[m]k[sj]xijkvijqkj\sum_{j \in [m]} \sum_{k \in [s_j]} x_{ijk} \cdot v_{ij} \cdot q_{kj}

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

Question [12:16PM - 05/07/2025]

[Page 4] Observe that using a bid multiplier strictly less than 1 before the bidder hits her budget constraint is a dominated strategy.

What is the utility of a players?

  1. Quasilinear. Previously, I thought it is quasilinear, and thus GSP and VCG stated above are both IC and IR. But, in this case, using a bid multiplier strictly less than 1 before the bidder hits her budget constraint is not a dominant strategy for GSP: increasing your bid might lead to paying more (which offsets the gained in values).

    • An example. Consider a simple GSP without boots, with three bidders and only a single auction with three slots:
    BiddersValuationsMultiplierBid
    1880.90.97.27.2
    210100.70.777
    3111111

    The three slots 1,2,31, 2, 3 has CTRs 0.6,0.5,0.40.6, 0.5, 0.4, respectively.

    Consider bidder 22 who is assigned to slot 22. Suppose her budget constraint is 55.

    Being assigned to slot 22, her quasilinear utility is (101)0.5=4.5(10 - 1) \cdot 0.5 = 4.5. Nevertheless, note that if she raises her multiplier to 0.80.8 (and thus her bid to 88), she ends up taking the first slot. Indeed, increases here value to 10×0.6=610 \times 0.6 = 6. But, also increases her payment to 7.2×0.6=4.327.2 \times 0.6 = 4.32.

    As a result, her new utility (64.326 - 4.32) is less than 4.54.5.

    Overall, using a bid multiplier strictly less than 1 before the bidder hits her budget constraint is not a dominant strategy, if utility functions are quasilinear.

  2. Value-maximizing. Suppose the utility function is the total value received, that is j[m]k[sj]xijkvijqkj\sum_{j \in [m]} \sum_{k \in [s_j]} x_{ijk} \cdot v_{ij} \cdot q_{kj} (this also the objective state above where bidders optimizes). Then indeed, using a bid multiplier strictly less than 1 before the bidder hits her budget constraint is a dominant strategies because for each bidder, (i)(i) the payment is always at most the values received (for GSP and VCG defined above), and (ii)(ii) the allocation function is monotone.

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 αi\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:

LW(x)=i[n]min{Bi,j[m]k[sj]xijkvijqjk}\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 ii, one can interpret the min{...}\min \{...\} part as the maximum payment one can extract from ii, 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)(n, m \{v\}_i, \{s\}_j, \{q\}_{kj}), LW is uniquely determined by an allocation xx (no auctions even need to be further defined). This leads to my following question:

Question [06:00PM - 05/07/2025]

Since valuations are given to the auctioneers, in each of the mm auctions, why cannot we simply assign bidders to slots greedily based on the ranking of their valuations (regardless of their bids)? This guarantees to maximize the liquid welfare, and we don't even care about the payment rule.

Of course, this provides no guarantees on the revenue. But payment is not an objective to optimize in this problem. Based on the statement of this problem, the greedy allocation indeed maximizes LW.

To summarize my question: the above formulation positions this problem to a centralized optimization problem (where valuations are known), ignoring the payments all together.

I think this is a very import 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 A\mathcal{A} is defined as is its competitive ratio:

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

Question [_:_PM - 05/07/2025]

I don't understand this definition.

The vector Θ\Theta is defined w.r.t a problem instance. Thus, the definition provided in the paper is for an instance of the problem (not sure what do they mean by over all problem instances on page 44).

My current guess is that the definition of this competitive ratio is as follows:

infΠminαΠΘLW(x(α,A))OPTΠ\inf_{\Pi} \min_{\alpha_{\Pi} \in \Theta} \frac{\text{LW}(x(\alpha, \mathcal{A}))}{OPT_{\Pi}}

That is, for each problem instance Π\Pi, minαΠΘLW(x(α,A))OPTΠ\min_{\alpha_{\Pi} \in \Theta} \frac{\text{LW}(x(\alpha, \mathcal{A}))}{OPT_{\Pi}} is the competitive ratio of A\mathcal{A} for that instance. Then the infimum is taken over all possible problem instances Π\Pi since we are interested in the worst-case (This is a very common format to bound the performance ratio of an algorithm).

I will work with this definition.

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

Question [06:25PM - 05/07/2025]

[Page 4] Here, we only assume the bidders are using strategies that are valid and undominated, while it is not necessary that their strategies must form a Nash equilibrium.

How a Nash is defined in this context?

If a Nash is defined as follows:

A multiplier vector α\alpha is a (pure) Nash if for each bidder ii, any unilateral deviation either decreases ii's utility (which is its total values received) or violates either the budget or the ROS constraint.

Then, Θ\Theta consists of all such Nash equilibria, right? At least this is the case of VCG and GSP auctions defined in this paper.

Somehow I think the notions of undominated and valid implies that these α\alphas are Nash.

Revenue

Defined as

R=i[n],j[m]  pij(α,A) 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

c+1c+2\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:

zij=cvijz_{ij} = c \cdot v_{ij}

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

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

  2. The importance factors of the slots are normalized to 11.

Upper bound example

  1. Any d>0d > 0, small ϵ>0\epsilon > 0, boost weight cdc \leq d.

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

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

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

    • Bidder 11: α1>(c+1)/ϵ\alpha_1 > (c + 1) / \epsilon.

    • Bidder 22: α2=1\alpha_2 = 1.

Lemma 3.2. The above instance incurs the following ratio for second-price auction with cc-uniform boosting:

LW(x(α,A))OPTd+1+ϵd+2\frac{LW(x(\alpha, \mathcal{A}))}{OPT} \leq \frac{d + 1 + \epsilon}{d + 2}

Thus, establishing an upper bound of (c+1)/(c+2)({c + 1})/({c + 2}) for the competitive ratio of VCG and GSP auctions with uniform boosting when c=dc = d and ϵ0\epsilon \to 0.

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+ϵ1 + d + \epsilon and pays 11.

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

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+1c + 1 in this case) minus the boost of the first bidder (ϵc\epsilon c in this case). Thus, the payment of the first bidder in the second auction is 1+(1ϵ)c1 + (1 - \epsilon) c.

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

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

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

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

for fixed ϵ>0\epsilon > 0.

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

Question [07:42PM - 05/09/2025]

Previously, the following was stated in the paper:

[Page 4] Observe that using a bid multiplier strictly less than 1 before the bidder hits her budget constraint is a dominated strategy.

But, in this example, bidder 11's α1>(c+1)/ϵ\alpha_1 > (c + 1) / \epsilon is clearly larger than 11. In fact, as ϵ0\epsilon \to 0, α1\alpha_1 \to \infty.

Further, it is not hard to see that, having α11\alpha_1 \to 1 is not a dominated strategy for bidder 11. In particular, if α1=1\alpha_1 = 1, bidder 1's final boosted bid in auction 22 is (c+1)ϵ(c + 1) \cdot \epsilon, where as the boosted bid of bidder 22 is (c+1)(c + 1). That is, bidder 11 loses the second auction. Here, a dominant strategy for bidder 11 is to set α1\alpha_1 higher than 11 to win the second auction.

This is a contradiction to the statement above.

Previously, I thought that using a bid multiplier strictly less than 1 is necessary to ensure that the payment is at most the value received. But, after seeing this upper bound example, even if α1>1\alpha_1 > 1, the payment for bidder 11 is still less than the value received.

This is quite confusing.

A lower bound for second-price under uniform boosting

Assumptions

  1. There is no budget constraint for all bidders.

  2. The underlying mm auctions are second-price auctions with uniform boost of weight cc.

    • Single-slot auctions.

Theorem 3.3. When bidders have RoS constraints only, the competitive ratio is at least (c+1)/(c+2)(c + 1) / (c + 2) for the second-price auctions with uniform boosts of weight cc.

Proof sketch. Fix an instance I=(n,m,{v}ij)I = (n, m, \{v\}_{ij}) (note that all auctions are single-slot auctions with importance factors normalized to 11 for the slots), let xOPTx^{OPT} be an allocation with optimal liquid welfare. Note that, since there is no budget constraint, the liquid welfare is reduced to the total value received by all bidders.

Let OPTOPT denote the optimal liquid welfare for this instance. Observe that

OPT=j[m]maxi[n]{vij}OPT = \sum_{j \in [m]} \max_{i \in [n]} \{v_{ij}\}

Consider any αΘ\alpha \in \Theta. Since is there is no budget constraint, it satisfies that αi1\alpha_i \geq 1 for all bidders ii. Let xx be the allocation computed by the mechanism (i.e., second-price + uniform boosting) under α\alpha. Let AA be the set of auctions whose winners under xx and xOPTx^{OPT} are the same.

It is useful to note that the difference between the welfare of xx and OPTOPT is due to the auctions in [m]A[m] \setminus A. We now bound such difference.

For any j[m]Aj \in [m] \setminus A, let iji^*_j and ijOPTi^{OPT}_j denote its winner under xx and xOPTx^{OPT}, respectively. The payment of iji^*_j is lower bounded by

pij  j=(b^2  jzij  j)+(αijOPTvijOPT  j+zijOPT  j)zij  j          (The second highest boosted bid is at least ijOPT’s boosted bid)vijOPT  j+cvijOPT  jcvij  j          (αi1 for all bidders i)(c+1)vijOPT  jcvij  j\begin{align*} p_{i^*_j \; j} &= (\hat{b}_{2 \; j} - z_{i^*_j \; j})^+ \\ &\geq \left( \alpha_{i^{OPT}_j} \cdot v_{i^{OPT}_j \; j} + z_{i^{OPT}_j \; j} \right) - z_{i^*_j \; j} \;\;\;\;\; (\text{The second highest boosted bid is at least $i^{OPT}_j$'s boosted bid})\\ &\geq v_{i^{OPT}_j \; j} + c \cdot v_{i^{OPT}_j \; j} - c \cdot v_{i^*_j \; j} \;\;\;\;\; (\text{$\alpha_i \geq 1$ for all bidders $i$})\\ &\geq (c + 1) \cdot v_{i^{OPT}_j \; j} - c \cdot v_{i^*_j \; j} \end{align*}

Note that non-winners pay zero. It follows that the total revenue under xx is at least:

R(x)=j[m],i[n]pijj[m]A,i[n]pijj[m]A((c+1)vijOPT  jcvij  j)\begin{align} R(x) = \sum_{j \in [m], i \in [n]} p_{ij} \geq \sum_{j \in [m] \setminus A, i \in [n]} p_{ij} \geq \sum_{j \in [m] \setminus A} \left( (c + 1) \cdot v_{i^{OPT}_j \; j} - c \cdot v_{i^*_j \; j} \right) \end{align}

Lastly, observe that under RoS constraints, Wel(x)R(x)\text{Wel}(x) \geq R(x). Thus:

OPT=jAvijOPT  j+j[m]AvijOPT  j=Wel(x)+j[m]AvijOPT  jj[m]Avij  jWel(x)+1c+1R(x)(1c1+c)j[m]Avij  j      (By Ineq (1))Wel(x)+1c+1Wel(x)(1c1+c)j[m]Avij  j      (By RoS)Wel(x)+1c+1Wel(x)=c+2c+1Wel(x)\begin{align*} OPT &= \sum_{j \in A} v_{i^{OPT}_j \; j} + \sum_{j \in [m] \setminus A} v_{i^{OPT}_j \; j}\\ &= \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 \text{Wel}(x) + \frac{1}{c + 1} \cdot R(x) - (1 - \frac{c}{1+c}) \sum_{j \in [m] \setminus A} v_{i^{*}_j \; j} \;\;\; (\text{By Ineq (1)})\\ &\leq \text{Wel}(x) + \frac{1}{c + 1} \cdot \text{Wel}(x) - (1 - \frac{c}{1+c}) \sum_{j \in [m] \setminus A} v_{i^{*}_j \; j} \;\;\; (\text{By RoS})\\ & \leq \text{Wel}(x) + \frac{1}{c + 1} \cdot \text{Wel}(x) \\ &= \frac{c + 2}{c + 1} \cdot \text{Wel}(x)\\ \end{align*}

This concludes the proof.

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=0c = 0). Here, we have

pij  jαijOPTvijOPT  jvijOPT  jp_{i^*_j \; j} \geq \alpha_{i^{OPT}_j} \cdot v_{i^{OPT}_j \; j} \geq v_{i^{OPT}_j \; j}

It follows that

Wel(x)R(x)j[m]AvijOPT  j\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,

OPT=Wel(x)+j[m]AvijOPT  jj[m]Avij  j2Wel(x)j[m]Avij  j\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ϵ2 - \epsilon (Note that, if j[m]Avij  j\sum_{j \in [m] \setminus A} v_{i^{*}_j \; j} is zero, then either AA is empty, and thus Wel = OPT, or the valuations of the winners in [m]A[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):

pij  j(c+1)vijOPT  jcvij  j=vijOPT  j+c(vijOPT  jvij  j)\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:

Wel(x)R(x)(c+1)j[m]AvijOPT  jcj[m]Avij  j\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, Wel(x)\text{Wel}(x) is lower bounded by a multiplicative factor of 11 for j[m]AvijOPT  j\sum_{j \in [m] \setminus A} v_{i^{OPT}_j \; j} (see Eq (2)). On the other hand, with boosting, Wel(x)\text{Wel}(x) is now lower bounded by a multiplicative factor of (c+1)(c + 1) for j[m]AvijOPT  j\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 cc-uniform boosting is the following:

  • For any two bidders ii and ii', and for any auction jj such that vij>vijv_{ij} > v_{i'j}, we have
zijzijc(vijvij)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 cc-value-competitive.