- Published on
Notes on Efficient Auctions [Deng etal.-21]
Table of contents
Surplus-maximizing bidders vs auto-bidders
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.
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: .
bidders
position auctions; denote the number of slots of auction .
- 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 is triggered by a keyword search, where there are available slots to display adds.
Each bidder has a baseline valuation for each auction (i.e., for each keyword).
- Note, not explicitly for each slot in an auction.
In an auction , slots are ranked based on their importance. Let denote the normalized importance factor, which is non-increasing in . That is, is the most important slot and is the least important slot.
- can be interpreted as the click-through rate of th slot in auction .
Auctions
denotes 's bid in auction .
Each bidder submits one bid per-auction, not per-item in an auction.
Also note that, bids are not parts of a problem instance.
is the binary allocation, either or , of th slot in auction to player .
is the payment of player in auction .
- The revenue of the auctioneer is
Boosting
In each auction , a player receives a boost .
- The ranking score (used by the mechanism to determine the allocations) of in auction becomes
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 th important slot to the bidder with the 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 and a bidder . Let denote the th highest ranking score in auction . Suppose is assigned to slot .
Let denote .
- GSP:
For quasilinear utilities, this is IR because .
Let be the bidder assigned to the th important slot. Note that an alternative payment rule: 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.
VCG:
The intuition of this definition is clear: if we discard , the allocations of those who are ranked higher than 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 th highest ranking score.
For quasilinear utilities, the resulting auction is IR since , for (assuming quasilinear utilities). It is also not hard to verify that the auction is IC for quasilinear utilities.
Auto-bidders
Assumptions
All bidders considered are auto-bidders with budget and ROS constraints.
W.l.o.g., ROS means the total payment is at most the total values received.
Uniform bidding strategies
- Each bidder computes a pacing multiplier (the same multiplier used in all auction), where for each auction ,
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 can be greater than (see the example in Lemma 3.2 in the paper.), as long as the budget and the ROS constraints are satisfied.
- The goal of each bidders is to find an that is value-maximizing:
over the outcomes of the 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?
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:
Bidders Valuations Multiplier Bid 1 2 3 The three slots has CTRs , respectively.
Consider bidder who is assigned to slot . Suppose her budget constraint is .
Being assigned to slot , her quasilinear utility is . Nevertheless, note that if she raises her multiplier to (and thus her bid to ), she ends up taking the first slot. Indeed, increases here value to . But, also increases her payment to .
As a result, her new utility () is less than .
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.Value-maximizing. Suppose the utility function is the total value received, that is (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, the payment is always at most the values received (for GSP and VCG defined above), and the allocation function is monotone.
The set of multipliers
Fix an auction. We say a multiplier vector is valid (w.r.t this auction) if no bidder violates its budget and ROS constraint under . We say is dominant if all bidder's is maximal (i.e., any slight increase violates its budget constraint or ROS).
Let be the set of multiplier vectors that are both valid and dominant.Note that, given a problem instance and a mechanism, the set is fixed.
The optimization problem
Goal is to design auctions (an allocation rule + a payment rule) that maximizes the liquid welfare:
Fix , one can interpret the part as the maximum payment one can extract from , 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 , LW is uniquely determined by an allocation (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 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 is defined as is its competitive ratio:
Question [_:_PM - 05/07/2025]
I don't understand this definition.
The vector 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 ).
My current guess is that the definition of this competitive ratio is as follows:
That is, for each problem instance , is the competitive ratio of for that instance. Then the infimum is taken over all possible problem instances 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 ), 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 is a (pure) Nash if for each bidder , any unilateral deviation either decreases 's utility (which is its total values received) or violates either the budget or the ROS constraint.
Then, 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 s are Nash.
Revenue
Defined as
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
of competitive ratio for VCG and GSP under uniform boosting (defined below).
Problem instance
Two bidders.
Two single-slot auctions.
- In this case, both VCG and GSP reduced to second-price auctions (with boosting).
Uniform boosting:
for a uniform over the bidders. In this case, the boosted bid of bidder in auction is of the form: .
There is only RoS constraint, no budget constraint (i.e., for all users ).
The importance factors of the slots are normalized to .
Upper bound example
Any , small , boost weight .
For auction 1: , .
For auction 2: , .
The particular is defined as follows:
Bidder : .
Bidder : .
Lemma 3.2. The above instance incurs the following ratio for second-price auction with -uniform boosting:
Thus, establishing an upper bound of for the competitive ratio of VCG and GSP auctions with uniform boosting when and .
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:
- [Page 5] It is straightforward to verify that the return on ad spend constraints are satisfied: the first bidder receives total value and pays .
Note. Unless I understood their mechanism wrongly, otherwise, the payment of bidder is not .
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 ( in this case) minus the boost of the first bidder ( in this case). Thus, the payment of the first bidder in the second auction is .
Note that, since , we still have . That is, the RoS constraint is satisfied.
- [Page 5] For the second bidder to deviate, she has to use a bid multiplier to win the second auction, resulting in a payment .
Note. Not completely sure how the above bounds on the multiplier and the payments are derived. First, it is clear that bidder never wins the first auction, since her valuation is . For the second auction, the boosted bid of bidder is . Thus, for bidder to win the second auction, her multiplier must be greater than . Also, the payment of bidder , in the case of winning the second auction, is
for fixed .
Note that the claim by the authors still holds: if bidder were to change her multiplier to win auction , 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 's is clearly larger than . In fact, as , .
Further, it is not hard to see that, having is not a dominated strategy for bidder . In particular, if , bidder 1's final boosted bid in auction is , where as the boosted bid of bidder is . That is, bidder loses the second auction. Here, a dominant strategy for bidder is to set higher than 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 , the payment for bidder is still less than the value received.
This is quite confusing.
A lower bound for second-price under uniform boosting
Assumptions
There is no budget constraint for all bidders.
The underlying auctions are second-price auctions with uniform boost of weight .
- Single-slot auctions.
Theorem 3.3. When bidders have RoS constraints only, the competitive ratio is at least for the second-price auctions with uniform boosts of weight .
Proof sketch. Fix an instance (note that all auctions are single-slot auctions with importance factors normalized to for the slots), let 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 denote the optimal liquid welfare for this instance. Observe that
Consider any . Since is there is no budget constraint, it satisfies that for all bidders . Let be the allocation computed by the mechanism (i.e., second-price + uniform boosting) under . Let be the set of auctions whose winners under and are the same.
It is useful to note that the difference between the welfare of and is due to the auctions in . We now bound such difference.
For any , let and denote its winner under and , respectively. The payment of is lower bounded by
Note that non-winners pay zero. It follows that the total revenue under is at least:
Lastly, observe that under RoS constraints, . Thus:
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., ). Here, we have
It follows that
As a result,
Thereby a competitive ratio of (Note that, if is zero, then either is empty, and thus Wel = OPT, or the valuations of the winners in 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):
As a result, the lower bound on the welfare is increased:
Importantly, in the case without boosting, is lower bounded by a multiplicative factor of for (see Eq (2)). On the other hand, with boosting, is now lower bounded by a multiplicative factor of for .
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 -uniform boosting is the following:
- For any two bidders and , and for any auction such that , we have
In general, any boosting strategy that satisfies the above property is called -value-competitive.