Notes on Auto-bidding and Auctions Survey [Aggarwal-et-al-24]

Query

This notion of a query is not explicitly defined in the paper, though it comes up multiple times. My understanding is that, a query can be a search query that a user provides (like Google, Instagram). Nevertheless, it could generally be any event where ads are eligible to be shown. As a result, each query (or ad opportunity) triggers its own auction, with slots for multiple ads.

As of reading this paper, it is unclear to me an auction is defined at what level. Is it per-query, or a bundle of queries (where each query has a bundle of slots)? - [04/17/2025]

Answer. [02:23PM - 04/19/2025]:This paper Aggarwal, Varadaraja, Mehta - WINE19 gives an answer. It is indeed that there is an auction for each query, and each query has a bundle of slots.

The setting

$n$ autobidding agents.
$m$ auctions (e.g., for $m$ bundles of impressions).
Valuation. The valuation for an agent $i$ winning an auction $j$ is $v_{ij}$ .
Such valuations can be given by trained ML models such as predicted click-through rate and predicted conversion-rate.
Slots. Each auction (trigger by a query as we discussed above) has $\ell$ slots, indexed by $k$ , with decreasing (w.r.t. $k$ ) importance characterized by the decay parameters $\beta_{jk} \in [0, 1]$ . Specifically, an agent winning slot $k$ in auction $j$ receives a value of $\beta_{jk} v_{ij}$ . (An agent can win multiple slots in the same auction).
W.l.o.g., one can assume that $\beta_{j1} := 1$ , and auctions have the same number of slots (as one can add dummy slots with decay factor $0$ ).
Auctions. Fix an auction $j$ with $\ell$ slots. Each player $i$ submits a single bid $b_{ij}$ for the entire auction.
a. The input to the auction is then the vector of bids $b_j = (b_{1j}, b_{2j}, \ldots, b_{nj})$ .
b. The output of the auction for each agent is the $(i)$ allocation $x_{ijk} (b_j) \in [0, 1]$ for each slot $k = 1, ..., \ell$ , and $(ii)$ a payment $p_{ij}(b_j) \in \mathbb{R}$ .
When each auction has only a single slot, we omit the index $k$ .
Question. [12:20PM - 04/16/2025]
How to make sense of a fractional assignment of a slot? I can understand a fractional assignment of an auction (e.g., the setting in FPPE), which correspond to the proportion of the pool of slots allocated to an agent. But, again, even this interpretation does not make complete sense here since slots are not homogeneous, each of them has its own decay parameter.
Maybe the fractional assignment is interpreted as the probability of winning a slot, then the sum of assignments (over all agents) for each slot should be $1$ . Not sure if this is the case.

Problems from a bidding agent's perspective

Goal: Submit bids that maximize some objectives subject to some constraints.

The discussion below considers auctions with a single slot, omitting the index $k$ . Nevertheless, my guess is that it can be extended to the case of multiple slots where the total valuation received by an agent $i$ from an auction $j$ is of the form $\sum_{k=1}^\ell x_{ijk} \cdot \beta_{jk} v_{ij}$ .

Objectives of an agent $i$

Utility-maximization: $\sum_{j \in [m]} x_{ij} v_{ij} - p_{ij}$
Value-maximization: $\sum_{j \in [m]} x_{ij} v_{ij}$

Value maximization focuses on maximizing clicks or conversions, regardless of cost, appealing to advertisers who prioritize these metrics. It indirectly considers payments through a constraint on payments or the return on spend. Utility maximization, common in economics, maximizes the difference between value and payments, requiring values to be expressed in monetary terms, which can be difficult for advertisers.

Hybrid: $\sum_{j \in [m]} x_{ij} v_{ij} - \lambda p_{ij}$ , for some $\lambda \in [0, 1]$ . Note that this factor $\lambda$ is universal across all auctions and agents.

Constraints of an agent $i$

Budget: $\sum_{j \in [m]} p_{ij} \leq B_i$ for some budget $B_i$ .
Return-on-spend (RoS): $\sum_{j \in [m]} x_{ij} v_{ij} \geq \tau_i \cdot \sum_{j \in [m]} p_{ij}$ for some $\tau_i \geq 1$ .

Re-emphasize that the valuations $v_{ij}$ is independent to the bids, whereas the allocations $x_{ij}$ and payments $p_{ij}$ (should) depend on the bids.

Formulation

$\max{} \sum_{j \in [m]} x_{ij} v_{ij} - \lambda \cdot p_{ij}$

s.t. Budget and RoS constraints.

Question. [1:28PM - 04/16/2025]

Why this is a formulation for bidding agents? What are the variables?

If I understand correctly, agents can only submit bids; they cannot explicitly choose either the payment amount or the allocations. Now, this objective function is not a function of the bids. So, how can an agent optimize this function? It seems to me that this program is for auctioneers (to improve the welfare of the agents), not for agents themselves.

My current guess is that, bids are implicitly optimized since they are used to compute the allocations and payments, whereas the function that maps bids to allocations and payments is defined by the auction mechanism. If this is the case, what is the advantage of this program over the one that directly optimizes the bids? Do they solve the dual instead or something?

Problems from an auctioneer's perspective

Goal: Design an auction mechanism that maximizes some objectives subject to some constraints.

Objectives

Revenue: $\sum_{i \in [n]} \sum_{j \in [m]} p_{ij}$
Liquid welfare (LWEL):

\begin{equation*} \sum_{i \in [n]} \min{} \{B_i, \frac{\sum_{j \in [m]} x_{ij} v_{ij}}{\tau_i}\} \end{equation*}

Fix and agent $i$ . Let

\begin{equation*} \gamma_i := \frac{\sum_{j \in [m]} x_{ij} v_{ij}}{\tau_i} \end{equation*}

Note that by the RoS constraint, $\gamma_i \geq \sum_{j \in [m]} p_{ij}$ . Further, by the budget constraint, $B_i \geq \sum_{j \in [m]} p_{ij}$ .

Liquid welfare is the maximum amount of money that can be extracted from an agent while satisfying the constraints. Here is one way to think about it. Fix an agent $i$ .

a. If $\gamma_i \geq B_i$ , then in the best case, the total payment (i.e., $\sum_{j \in [m]} p_{ij}$ ) of an agent $i$ can be made to equals to its budget (i.e., bind the budget constraint), while the RoS constraint remains satisfied. In this case, LWEL equals to $B_i$ .

b. On the other hand, if $\gamma_i < B_i$ , then in the best case, one can make the total payment of an agent $i$ to equals to $\gamma_i$ (i.e., RoS is binding). In this case, LWEL equals to $\gamma_i$ .

The observation follows:

Observation 1. Given an instance of the problem, for any outcome of the auction (i.e., payments and allocations), its resulting liquid welfare is at least its revenue. The equality holds if and only if for each agent, either the RoS constraint or the budget constraint (or both) is binding.

For value-maximization agents, under their optimal strategy (assuming others' fixed), it is often the case that either Budget or RoS binds, unless there is no chance for them to obtain higher values by increasing their spend. For this reason, liquid welfare receives significantly more attention in the literature especially with value-maximization agents.

Bidding algorithms

Fix an agent $i$ . We omit the index $i$ in the discussion below.

LP for truthful auction

Let $p_j$ be the price of an ad for this advertiser for query $j$ .
I guess that the price $p_j$ is the payment for the auction $j$ (for agent $i$ ), and such auction is triggered by a query $j$ . Also, my guess is that there is only a single slot in the auction.
What is "and ad for an advertiser"?
Note: While reading their formulation further, it seems that this price $p_j$ is not the same as the payment $p_{ij}$ for the auction $j$ . Rather, $p_{ij} = x_{ij} \cdot p_j$ , which makes sense.
Suppose, for argument, we know the query sequence and the values of $p_j$ in advance.
Question. [09:49AM - 04/18/2025]
As pointed out by the authors, the price of an ad depends on the bids and auction mechanism. So, it is not clear to me how to know the price in advance. Is this assumption only made to get analytical results?

The formulations of the primal and dual (from the perspective of a single bidding agent $i$ ) are as follows

Primal

\begin{align*} &\max{} \;\; \sum_{j \in [m]} (v_{ij} - \lambda p_j) \cdot x_{ij} \\\\ &\text{s.t.} \;\; \sum_{j \in [m]} p_j \cdot x_{ij} \leq B_i^{c} + \sum_{j \in [m]} w_{ij}^c x_{ij}, \;\; \forall c \in C\\\\ & \;\;\;\;\;\;\;\; x_{ij} \in [0, 1], \;\; \forall j \in [m] \\ \end{align*}

Here $C$ is a set of parameters that captures different variants of Budget and RoS constraints. One example can be $C = \{c_1, c_2\}$ where $B_i^{c_1} = B_i$ , $w_{ij}^{c_1} = 0$ (i.e., the budget constrain) and $B_i^{c_2} = 0$ , $w_{ij}^{c_2} = 1/\tau_i \cdot v_{ij}$ (i.e., the RoS constraint).

One can verify that the dual is as follows:

Dual

\begin{align*} &\max{} \;\; \sum_{j \in [m]} \delta_j + \sum_{c \in C} \alpha_c B_i^c \\\\ & \text{s.t.} \;\; \delta_j \geq \sum_{c \in C} \alpha_c \cdot (w_{ij}^c - p_j) + v_{ij} - \lambda p_j, \;\; \forall j \in [m]\\\\ & \;\;\;\;\;\;\; \delta_j \geq 0, \;\; \forall j \in [m]\\\\ & \;\;\;\;\;\;\; \alpha_c \geq 0, \;\; \forall c \in C\\\\ \end{align*}

Here, $\alpha$ and $\delta$ are the dual variables for the first and the second sets of constraints in the primal, respectively.

For truthful auctions, assuming that the optimal values of the dual variables $\alpha_c$ are known, they following bidding formula always lead to an auction outcome that incurs an optimal primal solution:

b_{ij} = \frac{v_{ij} + \sum_{c \in C} \alpha_c w_{ij}^c}{\lambda + \sum_{c \in C} \alpha_c}

Variants of the above bidding formula can be derived for different types of bidders. Let $\alpha_B$ and $\alpha_R$ be the optimal dual variables for the budget and RoS constraints, respectively.

Value-maximization ( $\lambda = 0$ ):

\left(\frac{1 + \alpha_R \cdot 1/\tau_i}{\alpha_B + \alpha_R}\right) \cdot v_{ij}

Value-maximization without Budget:

\left( \frac{1}{\alpha_R} + \frac{1}{\tau_i} \right) \cdot v_{ij}

Utility-maximization without RoS ( $\lambda = 1$ ):

\frac{1}{1 + \alpha_B} \cdot v_{ij}

The bid formula depends on the knowledge of the optimal duals; in practice these can be estimated via ML techniques from past data, and updated via control loops.

Online setting

There is an active line of work on online bidding algorithms, where the input models and be stochastic or adversarial; the auctions can be truthful or un-truthful. See page 7 to 9 of the paper for a survey of the literature.

Rest of the paper

The authors then provided a detailed summary of $(i)$ efficiency of different solution concepts; $(ii)$ convergence; $(iii)$ optimal auction design.

Multi-channel settings

Channels can be coming from the same platform (e.g., Google, Facebook) or different platforms. Here, one can study either bidding problems or auction design problems. This is an interesting setting. I want to work on one such problems.