\section{Throttling in First-price Auctions}

We begin by studying throttling equilibria in the first-price auction setting. We start by showing that, for first-price auctions, there always exists a unique throttling equilibrium. We then describe a simple and efficient t\^{a}tonnement-style algorithm for  approximate throttling equilibria.

\subsection{Existence of First-Price Throttling Equilibria}

To show existence, we will characterize the throttling equilibrium as a component-wise maximum of the set of all budget-feasible throttling parameters. This argument is inspired from the technique used in \citet{conitzer2019pacing} for pacing equilibria in first-price auctions. We use the following definition to make the argument precise. 

\begin{definition}[Budget-feasible Throttling Parameters]
	Given a throttling game $\left(n, m, (b_{ij}), (B_i)\right)$, a vector of throttling parameters $\theta \in [0,1]^n$ is called budget-feasible if every buyer satisfies her budget constraints, i.e., $\sum_j p(\theta)_{ij} \leq B_i$ for all buyers $i \in [n]$.
\end{definition}

The following lemma captures the crucial fact that the component-wise maximum of two budget-feasible throttling parameters is also budget-feasible.

\begin{lemma}\label{lemma:pairwise_max}
	Given a throttling game $\left(n, m, (b_{ij}), (B_i)\right)$, if $\theta, \tilde{\theta} \in [0,1]^n$ are budget-feasible, then $\max(\theta, \tilde{\theta}) \coloneqq (\max(\theta_i, \tilde{\theta}_i))_i$ is also budget-feasible.
\end{lemma}

\begin{proof}
	Fix $i \in [m]$ and $j \in [m]$. Without loss of generality, we assume that $\theta_i \geq \tilde{\theta}_i$. Observe that
	\begin{align*}
		p(\max(\theta, \tilde{\theta}))_{ij} 	= \prod_{k: b_{kj} > b_{ij}} (1 - \max(\theta_k, \tilde{\theta}_k)) \theta_i b_{ij} \leq \prod_{k: b_{kj} > b_{ij}} (1 - \theta_k) \theta_i b_{ij} = p(\theta)_{ij}
	\end{align*}
	Summing over all goods $j \in [m]$ completes the proof.
\end{proof}


The maximality property shown in \cref{lemma:pairwise_max} is analogous to the maximality property of multiplicative pacing: there it is also the case that component-wise maxima over pacing vectors preserves budget feasibility for first-price auctions, and this was used by \citet{conitzer2019pacing} to show several structural properties of pacing equilibria.
Next we show that the maximality property allows us to establish the existence and uniqueness of throttling equilibria for first-price auction.

\begin{theorem}\label{thm:existence-first-price}
	For every throttling game $\left(n, m, (b_{ij}), (B_i)\right)$, there exists a unique throttling equilibrium $\theta^* \in [0,1]^n$ which is given by
 $
		\theta^*_i = \sup\{\theta_i \in [0,1] \mid \exists\ \theta_{-i} \text{ such that } \theta = (\theta_i, \theta_{-i}) \text{ is budget-feasible}\}.$ 
\end{theorem}

\begin{proof}
	Set $\theta^*_i = \sup\{\theta_i \in [0,1] \mid \exists\ \theta_{-i} \text{ such that } \theta = (\theta_i, \theta_{-i}) \text{ is budget-feasible}\}$ for all $i \in [n]$. First, we show that $\theta_i^*$ is budget-feasible. Observe that the function $\theta \mapsto \left(\sum_j p(\theta)_{1j}, \dots, \sum_j p(\theta)_{nj} \right)$ is continuous. Therefore, the pre-image of the set $\bigtimes_{i=1}^n[0,B_i]$ under this function is closed. In other words, the set of all budget-feasible throttling parameters is closed. Fix $\epsilon > 0$. For all $i \in [n]$, by the definition of $\theta^*_i$, there exists $\theta^{(i)} \in [0,1]^n$ which is budget feasible and $\theta^{(i)}_i > \theta_i^* - \epsilon$. Iterative application of Lemma~\ref{lemma:pairwise_max} yields the budget-feasibility of the vector $\theta$ defined by $\theta_i = \max_{k \in [n]} \theta^{(k)}_i$. Moreover, $\theta_i > \theta^*_i - \epsilon$ for all $i \in [n]$ because $\theta^{(i)}_i > \theta_i^* - \epsilon$ for all $i \in [n]$. Since $\epsilon> 0$ was arbitrary, we have shown that there exists a sequence of budget-feasible throttling parameters which converges to $\theta^*$, which implies that $\theta^*$ is budget-feasible because the set of budget-feasible throttling parameters is closed.
	
	Next, we show that $\theta^*$ also satisfies the `No unnecessary pacing' property. Suppose there exists $i \in [n]$ such that $\sum_j p(\theta^*)_{ij} < B_i$ and $\theta^*_i < 1$. Then, by the continuity of $\theta \mapsto \sum_j p(\theta)_{ij}$, there exists $\theta_i$ such that $\theta^*_i < \theta_i< 1$ and $\sum_j p(\theta_i, \theta^*_{-i})_{ij} < B_i$, which contradicts the definition of $\theta^*$. Therefore, for all $i \in [n]$,  we have $\sum_j p(\theta^*)_{ij} < B_i$ implies $\theta^*_i = 1$. Thus, $\theta^*$ is a throttling equilibrium.
	
	Finally, we prove uniqueness of $\theta^*$. Suppose there is a throttling equilibrium $\theta \in [0,1]^n$ such that $\theta_i \neq \theta^*_i$ for some $i \in [n]$. Then, the set of buyers $C \subset [n]$ for whom $\theta_i^* > \theta_i$ is non-empty. Note that $\theta_i < 1$ for all $i \in C$. Hence, every buyer in $C$ spends her entire budget under $\theta$. On the other hand, since $\theta_i^* > \theta_i$ for all $i \in C$ and $\theta_i^* = \theta_i$ for $i\notin C$, the total payment made by buyers in $C$ under $\theta^*$ is strictly greater than the payment under $\theta$, which contradicts the budget-feasibility of $\theta^*$. Therefore, $\theta^*$ is the unique throttling equilibrium.
\end{proof}

We conclude this subsection by noting that in Appendix~\ref{appendix:irrationality} we describe a throttling game for which the unique throttling equilibrium has irrational throttling parameters for some buyers. In other words, rational throttling equilibrium need not always exist. Since irrational numbers cannot be represented exactly with a finite number of bits in the standard floating point representation, it leads us to consider algorithms for finding \emph{approximate} throttling equilibrium instead.



\subsection{An Algorithm for Computing Approximate First-Price Throttling Equilibria}

In this subsection, we define a simple t\^atonnement-style algorithm and prove that it yields an approximate throttling equilibrium in polynomial time.

\begin{algorithm}[H] 
   \caption{Dynamics for First-price Auction}
   \label{alg:dynamics}
  
    \begin{algorithmic}\vspace{0.08cm}
            \item[\textbf{Input:}] Throttling game $\left(n, m, (b_{ij}), (B_i)\right)$ and approximation parameter $\delta \in (0,1/2)$
            \item[\textbf{Initialize:}] $\theta_i = \min\{B_i/ (2\sum_j b_{ij}), 1\}$ for all $i \in [n]$
            \item[\textbf{While}] there exists a buyer $i \in [n]$
            such that $\theta_i < 1 - \delta$ and $\sum_j p(\theta)_{ij} < (1 - \delta) B_i$:
            \begin{itemize}
                \item For all $i \in [n]$ such that $\theta_i < 1 - \delta$ and $\sum_j p(\theta)_{ij} < (1 - \delta) B_i$, set $\theta_i \leftarrow \theta_i/(1 - \delta)$ 
            \end{itemize}
            \item[\textbf{Return:}] $\theta$
    \end{algorithmic}
\end{algorithm}

Before proceeding to prove the correctness and efficiency of Algorithm~\ref{alg:dynamics}, we note some of its properties. Typically, in online advertising auctions, buyers participate in a large number of auctions throughout their campaign, and the platform periodically updates their throttling parameters to ensure that they don't finish their budgets prematurely and loose out on valuable advertising opportunity. The above algorithm is especially suited for this setting due to its decentralized and easy-to-implement updates to the throttling parameter. 
Moreover, it also lends credence to the notion of throttling equilibrium as a solution concept because the update step in Algorithm~\ref{alg:dynamics} can be implemented independently by the buyers, resulting in decentralized dynamics which converge to a throttling equilibrium in polynomially-many steps. We refer the reader to \cite{borgs2007dynamics} for a detailed model under which Algorithm~\ref{alg:dynamics} can be naturally interpreted as decentralized dynamics for online advertising auctions.

In the next lemma, we show that, throughout the run of Algorithm~\ref{alg:dynamics}, all the buyers always satisfy their budget constraints.

\begin{lemma}\label{lemma:no_budget_violation}
	Consider the run of Algorithm~\ref{alg:dynamics} on the throttling game $\left(n, m, (b_{ij}), (B_i)\right)$ and approximation parameter $\delta \in (0,1/2)$. Then, after every iteration of the while loop, we have $\sum_{j} p(\theta)_{ij} \leq B_i$ for all $i \in [n]$. 
\end{lemma}
\begin{proof}
	We prove the lemma using induction on the number of iterations of the while loop. Note that $\sum_{j} p(\theta)_{ij} \leq B_i$ for all $i \in [n]$ before the first iteration of the while loop by virtue of our initialization. Let $\theta$ and $\theta'$ represent the throttling parameters after the $t$-th iteration and the $(t+1)$-th iteration of the while loop. Suppose $\sum_{j} p(\theta)_{ij} \leq B_i$ for all $i \in [n]$. To complete the proof by induction, we need to show that $\sum_{j} p(\theta')_{ij} \leq B_i$ for all $i \in [n]$. Consider a buyer $i$. Suppose $\sum_{j} p(\theta)_{ij} \geq (1 - \delta) B_i$. By the update step of the algorithm, $\theta'_i = \theta_i$ and $\theta'_j \geq \theta_j$ for $j \neq i$. Therefore,
	\begin{align*}
 		\sum_{j} p(\theta')_{ij} = 	\sum_j \prod_{k: b_{kj} > b_{ij}} (1 - \theta'_k) \theta'_i b_{ij} \leq 	\sum_j \prod_{k: b_{kj} > b_{ij}} (1 - \theta_k) \theta_i b_{ij} = \sum_{j} p(\theta)_{ij} \leq B_i
	\end{align*}
	On the other hand, suppose $\sum_{j} p(\theta)_{ij} < (1 - \delta) B_i$. Then, by the update step of the algorithm, $\theta'_i \leq \theta_i/(1- \delta)$ and $\theta'_j \geq \theta_j$ for $j \neq i$. Therefore,
	\begin{align*}
		\sum_{j} p(\theta')_{ij} = 	\sum_j \prod_{k: b_{kj} > b_{ij}} (1 - \theta'_k) \theta'_i b_{ij} \leq \frac{1}{1-\delta} \cdot\sum_j \prod_{k: b_{kj} > b_{ij}} (1 - \theta_k) \theta_i b_{ij} = \frac{1}{1-\delta} \cdot\sum_{j} p(\theta)_{ij} < B_i
	\end{align*}
	This completes the proof of $\sum_{j} p(\theta')_{ij} \leq B_i$ for all buyers $i \in [n]$.
\end{proof}

We conclude this subsection by proving the correctness and efficiency of Algorithm~\ref{alg:dynamics}.

\begin{theorem}\label{thm:first-price-dynamics}
	Given a throttling game $\left(n, m, (b_{ij}), (B_i)\right)$ and an approximation parameter $\delta \in (0,1/2)$ as input, Algorithm~\ref{alg:dynamics} returns a $\delta$-approximate throttling equilibrium in polynomial time.
\end{theorem}

\begin{proof}
	Since each iteration of the while loop only performs basic arithmetic operations, to establish a polynomial run-time complexity, it suffices to show that the while loop terminates in polynomially-many steps. Note that $c = \min_i \min\{B_i/ (2\sum_j b_{ij}), 1\}$ is a lower bound on the initial value of the throttling parameter of every buyer. Due to the termination condition of the while loop and the update step, at each iteration of the while loop, there exists a buyer $i \in [n]$ whose throttling parameter is updated, i.e., there exists $i \in [n]$ such that $\theta_i < 1- \delta$ and $\theta_i \leftarrow \theta_i/(1 - \delta)$. Therefore, the number of iteration of the while loop $T$ satisfies the following relationships:
	\begin{align*}
		\frac{c}{(1 -\delta)^{T/n}} \leq 1 \iff T \leq \frac{n \log(1/c)}{\log(1/ (1-\delta))} \leq \frac{n\log(1/c)}{\delta}
	\end{align*}
	The second sequence of inequalities upper bounds the number of iterations of the while loop by a polynomial function of the problem size.
	
	To complete the proof, it suffices to show that at the termination of the while loop, $\theta$ is a $\delta$-approximate throttling equilibrium. Budget-feasibility follows  from Lemma~\ref{lemma:no_budget_violation}, and the `Not too much unnecessary throttling' condition is satisfied by virtue of the termination condition. 
\end{proof}
\section{Comparing Pacing and Throttling}\label{sec:TE-PE}

In this section, we compare two of the most popular budget management strategies: multiplicative pacing and throttling. First, we restate the definition of pacing equilibrium, as it appears in \cite{conitzer2018multiplicative, conitzer2019pacing}. Under pacing, each buyer $i$ has a pacing parameter $\alpha_i$ and, she bids $\alpha_i b_{ij}$ on good $j$. Let $p_j(\alpha)$ denote the price on good $j$ when all of the buyers use pacing, i.e., $p_j(\alpha)$ is the highest (second-highest) element among $\{\alpha_i v_{ij}\}_i$ for first-price (second-price) auctions. Then, a tuple $((\alpha_i), (x_{ij}))$ of pacing parameters and allocations $x_{ij}$ is called a pacing equilibrium if the following hold:
\begin{itemize}[noitemsep]
    \item[(a)] Only buyers with the highest bid win the good: $x_{ij} > 0$ implies $\alpha_i v_{ij}= \max_i \alpha_i b_{ij}$.\vspace{0.1cm}
    \item[(b)] Full allocation of each good with a positive bid:  $\max_i \alpha_i b_{ij} > 0$  implies $\sum_{i\in [n]} x_{ij} = 1$.\vspace{0.1cm
    \item[(c)] Budgets are satisfied: $\sum_{j\in [m]} x_{ij} p_j(\alpha) \leq B_i$.\vspace{0.1cm}
	\item[(d)]
	No unnecessary pacing: $\sum_{j\in [m]} x_{ij} p_j(\alpha) < B_i$ implies $\alpha_i=1$.\vspace{0.15cm}
\end{itemize}

\paragraph{Comparing Pacing and Throttling in First-Price Auctions}

We begin with a comparison of pacing equilibria and throttling equilibria for first-price auctions. In \cite{conitzer2019pacing}, the authors show that a unique pacing equilibrium always exists in first-price auctions and characterize it as the largest element in the collection of all budget-feasible vectors of pacing parameters. In Theorem~\ref{thm:existence-first-price}, we show the analogous result for throttling using similar techniques. However, unlike pacing equilibrium, which is known to be rational \cite{conitzer2019pacing}, there exist throttling games where the throttling equilibrium is irrational as we demonstrate through Example~\ref{example:first-price-irrational}. Furthermore, in \cite{borgs2007dynamics}, the authors develop t\^atonnement-style dynamics similar to those described in Algorithm~\ref{alg:dynamics}, which converge to an approximate pacing equilibrium in polynomial time. In combination with Theorem~\ref{thm:first-price-dynamics}, this provides evidence supporting the tractability of budget management for first-price auctions.

The uniqueness of pacing equilibrium and throttling equilibrium in first-price auctions is conducive to comparison, which we carry out for revenue. More specifically, in Theorem~\ref{thm:revenue-comparison}, we show that the revenue under the pacing equilibrium and the throttling equilibrium are always within a multiplicative factor of 2 of each other. Let REV(PE) and REV(TE) denote the revenue under the unique pacing equilibrium and the unique throttling equilibrium respectively. 

\begin{theorem}\label{thm:revenue-comparison}
    For any throttling game $\left(n, m, (b_{ij}), (B_i)\right)$, the revenue from the pacing equilibrium and the revenue from the throttling equilibrium are always within a factor of 2 of each other, i.e., REV(PE) $\leq 2 \times \text{REV(TE)}$ and REV(TE) $\leq 2 \times \text{REV(PE)}$.
\end{theorem}

\begin{proof}
    Consider a throttling game $\left(n, m, (b_{ij}), (B_i)\right)$. Let $\theta = (\theta_i)_i$ be the unique throttling equilibrium (TE) and $\alpha = (\alpha_i)_i$ be the unique pacing equilibrium (PE) for this game. We will use $p_j(\theta)$ and $p_j(\alpha)$ to denote the (expected) payment made to the seller on good $j$ under the TE and PE respectively. Then, REV(TE) $= \sum_j p_j(\theta)$ and REV(PE) $= \sum_j p_j(\alpha)$.
    
    First, we show that REV(PE) $\leq 2 \times \text{REV(TE)}$. Let $N \coloneqq \{i \in [n] \mid \theta_i = 1\}$ be the set of buyers who are not budget constrained under the TE. Moreover, define
    \begin{align*}
        M \coloneqq \{j \in [m] \mid \exists\ i\in N \text{ such that } i \text{ wins a non-zero fraction of } j \text{ under the PE } \alpha \}
    \end{align*}
    Note that, since $\theta_i = 1$ and $\alpha_i \leq 1$ for all $i \in N$, we get that the TE yields a higher revenue for the seller on all goods in the set $M$, i.e., $p_j(\theta) \geq p_j(\theta)$ for all $j \in N$. Therefore, REV(TE) $\geq \sum_{j \in M} p_j(\theta) \geq \sum_{j \in M} p_j(\alpha)$. Furthermore, the definition of throttling equilibrium implies that every buyer $i \notin N$ spends her entire budget $B_i$ under the TE. Hence, by our choice of $M$, we get $\sum_{j \notin M} p_j(\alpha) \leq \sum_{i \notin N} B_i \leq$ REV(TE). Combining the two statements yields REV(PE) $\leq 2 \times \text{REV(TE)}$, as desired.
    
    Next, we complete the proof by showing that REV(TE) $\leq 2 \times \text{REV(PE)}$. Let $S = \{i \in [n] \mid \alpha_i = 1\}$ be the set of buyers who are not budget constrained under the PE. Note that, for all $i \in S$ and $j \in [m]$, buyer $i$ bids $b_{ij}$ under the PE, which implies $p_j(\alpha) \geq \max_{i \in S} b_{ij}$ for all goods $j \in [m]$. Therefore, for any good $j \in [m]$, the total payment made by buyers in the set $S$ under the TE is at most $p_j(\alpha)$. As a consequence, the total payment made by buyers in $S$ under the TE is at most REV(PE). Furthermore, the buyers not in $S$ completely spend their budget under the TE so the total payment made by buyers not in $S$ under the TE is also at most REV(PE). Hence, we have the desired inequality REV(TE) $\leq 2 \times \text{REV(PE)}$.
\end{proof}

In Appendix~\ref{appendix:TE-PE}, we give examples to demonstrate that REV(TE) can be arbitrarily close to $2 \times \text{REV(PE)}$, and REV(PE) can be arbitrarily close to $(4/3) \times \text{REV(TE)}$. In other words, for Theorem~\ref{thm:revenue-comparison}, the inequality REV(TE) $\leq 2 \times \text{REV(PE)}$ is tight and the inequality REV(PE) $\leq 2 \times \text{REV(TE)}$ is not too loose.



\paragraph{Comparing Pacing and Throttling for Second-Price Auctions}
This subsection is devoted to the comparison of pacing equilibria and throttling equilibria in second-price auctions. We begin by noting that, in stark contrast to first-price auctions, there could be infinitely many throttling equilibria for second-price auctions as the following example demonstrates.

\begin{example}
    There are 2 goods and 2 buyers. The bids are given by $b_{11} = b_{22} = 2$, $b_{12} = b_{21} = 1$, and the budgets are given by $B_1 = B_2 = 1/2$. Then, it is straightforward to check that any pair of throttling parameters $\theta_1, \theta_2 \in [1/2, 1]$ such that $\theta_1 \theta_2 = 1/2$ forms a throttling equilibrium. 
\end{example}

\cite{conitzer2018multiplicative} demonstrate that this multiplicity also shows up for pacing equilibria in second-price auctions, which in combination with the multiplicity of throttling equilibria bodes unfavorably for potential comparisons of revenue. The similarities do not end with multiplicity: the problems of computing an approximate pacing equilibrium and computing an approximate throttling equilibrium are both PPAD-complete \cite{chen2021complexity}. As a consequence, we get that, unlike first-price auctions, no dynamics can converge to an approximate equilibrium in polynomial time for second-price auctions under either budget-management approach (assuming PPAD-hard problems cannot be solved in polynomial time). Furthermore, finding the revenue maximizing throttling equilibrium and finding the revenue maximizing pacing equilibrium are both NP-hard problems~\citep{conitzer2018multiplicative}. However, unlike throttling equilibria, a rational pacing equilibrium always exists \cite{chen2021complexity}.


\subsection{Proof of Theorem~\ref{thm:revenue_np_hard}}\label{appendix:NP-hard}

Consider an instance of 3-SAT with variables $\{x_1, \dots, x_n\}$ and clauses $\{C_1, \dots, C_m\}$. Our goal is to define an instance $\mathcal{I}$ of REV (a throttling game $G$ and a  target revenue $R$) which always has the same solution (Yes or No) as the 3-SAT instance, and has a size of the order $\text{poly}(n,m)$. We do so next, starting with an informal description to build intuition. To better understand the core motivations behind the gadgets, we will restrict our attention to exact throttling equilibria ($\delta = 0$) in the informal discussion that follows. As we will see in the formal proof, the target revenue $R$ can be chosen carefully to ensure that only exact throttling equilibria can achieve the revenue $R$. 

\textbf{Reciprocal Gadget:} Fix $i \in [n]$. Corresponding to variable $x_i$, there are two goods $\mathbb{A}_i$ and $\mathbb{B}_i$, and two buyers $V_i^+$ and $V_i^-$ in the throttling game $G$. Each buyer bids 1 for one of the goods and bids 2 for the other, with both buyers bidding differently on each good. Furthermore, we set the budgets of both buyers to be 1/2, and ensure that they do not spend any non-zero amount on goods other than $\mathbb{A}_i$ and $\mathbb{B}_i$. In equilibrium, this forces the throttling parameter of $V_i^+$ (which we denote by $\theta_i^+$) to be half of the reciprocal of the throttling parameter of $V_i^-$ (which we denote by $\theta_i^-$) and vice-versa. As a consequence, both throttling parameters lie in the interval $[1/2,1]$.

\textbf{Binary Gadget:} For each variable $x_i$, there are two additional goods $\S_i$ and $\mathbb{T}_i$, which receive a bid of 1 from buyers $V_i^+$ and $V_i^-$ respectively. The throttling game $G$ also has one unbounded buyer $U$ who has an infinite budget, and bids 2 on both goods $\S_i$ and $\mathbb{T}_i$. By the definition of throttling equilibria (Definition~\ref{def:exact_throt_eq}), the throttling parameter of $U$ is always 1 in equilibrium. Therefore, buyer $U$ wins both $\S_i$ and $\mathbb{T}_i$ with probability one, and pays $\theta_i^+ + \theta_i^-  = \theta_i^+ + 1/2\theta_i^+$ for it. Finally, observe that $t \mapsto t + 1/2t$, when restricted to $t \in [1/2,1]$, is maximized at $t = 1$ or $t = 1/2$. Therefore, by appropriately choosing the target revenue $R$, we can ensure that revenue $R$ is only achieved by throttling equilibria in which exactly one of the following holds: $(\theta_i^+ = 1, \theta_i^- = 1/2)$ or $(\theta_i^+ = 1/2, \theta_i^- = 1)$. This allows us to interpret $\theta_i^+ = 1$ as setting $x_i = 1$ and $\theta_i^- = 1$ as setting $x_i = 0$.

\textbf{Clause Gadget:} For each clause $C_j$, there is a good $\mathbb{C}_j$. If $C_j$ contains a non-negated literal $x_i$, then buyer $V_i^+$ bids 1 on good $\mathbb{C}_j$, and if it contains a negated literal $\neg x_i$, then buyer $V_i^-$ bids 1 on good $\mathbb{C}_j$. Furthermore, the unbounded buyer $U$ bids 2 on good $\mathbb{C}_j$, thereby always winning it. Hence, the total payment on good $\mathbb{C}_j$ is 1 if some literal is satisfied (corresponding throttling parameter is 1), and is 1/2 if no literal is satisfied (corresponding throttling parameters are 1/2). The rest of the reduction boils down to choosing $R$ appropriately.

\vspace{1em}


\begin{proof}[Proof of Theorem~\ref{thm:revenue_np_hard}]
Guided by the informal intuition described above, we proceed with the formal definition of the instance $\mathcal{I}$, which involves specifying the throttling game $G$ and the target revenue $R$. The throttling game $G$ consists of the following goods:
\begin{itemize}
    \item \textbf{Reciprocal Gadget:} For each variable $x_i$, there are two goods $\mathbb{A}_i$ and $\mathbb{B}_i$.
    \item \textbf{Binary Gadget:} For each variable $x_i$, there are two binary goods $\S_i$ and $\mathbb{T}_i$.
    \item \textbf{Clause Gadget:} For each clause $C_j$, there is a good $\mathbb{C}_j$.
\end{itemize}
Moreover, $G$ has the following set of buyers:
\begin{itemize}
    \item Corresponding to each variable $x_i$, there are two buyers $V_i^+$ and $V_i^-$ with non-zero bids only for the following goods:
    \begin{itemize}
        \item $b(V_i^+, \mathbb{A}_i) = 2$ and $b(V_i^+, \mathbb{B}_i) = 1$
        \item $b(V_i^-, \mathbb{A}_i) = 1$ and $b(V_i^-, \mathbb{B}_i) = 2$
        \item $b(V_i^+, \S_i) = 1$
        \item $b(V_i^-, \mathbb{T}_i) = 1$
        \item $b(V_i^+, \mathbb{C}_j) = 1$ if $x_i$ is a literal in $C_j$
        \item $b(V_i^-, \mathbb{C}_j) = 1$ if $\neg x_i$ is a literal in $C_j$
    \end{itemize}
    Moreover, the budget of both $V_i^+$ and $V_i^-$ is $1/2$ for all $i \in [n]$.
    \item There is one unbounded buyer $U$ with $b(U, \mathbb{C}_j) = 2$ for all $j \in [m]$ and $b(U, \S_i) = b(U, \mathbb{T}_i) = 2$ for all $i \in [n]$. Moreover, $U$ has a budget of $\infty$.
\end{itemize}

Set the target revenue to be $R = n + m + (3n/2)$. Suppose there exists a $\delta$-approximate throttling equilibrium $\Theta$, for some $\delta \in [0,1)$, with revenue greater than or equal to $R$. Let $\theta_i^+$ and $\theta_i^-$ denote the throttling parameters of $V_i^+$ and $V_i^-$ in $\Theta$. Then, $\theta_i^+ \theta_i^- \leq 1/2$ by virtue of the budget constraints. Therefore, the revenue from goods $\{\mathbb{A}_i\}_{i=1}^n \cup \{\mathbb{B}_i\}_{i=1}^n$ is at most $n$. Furthermore, it is easy to see that the revenue from goods $\{\mathbb{C}_j\}_{j=1}^m$ is at most $m$. Additionally, the total payment by buyer $U$ on goods $\S_i$ and $\mathbb{T}_i$ is at most $\theta_i^+ + \theta_i^- \leq \theta_i^+ + (1/2\theta_i^+)$. Note that $\theta_i^+ + (1/2\theta_i^+)$ is maximized at $\theta_i^+ = 1/2$ or $\theta_i^+ = 1$, with a value of $\theta_i^+ + (1/2\theta_i^+) = 3/2$. Therefore, the revenue from goods $\{\S_i\}_{i=1}^n \cup \{\mathbb{T}_i\}_{i=1}^n$ is at most $3n/2$. Hence, the total payment made on all the goods is at most $R$. 

For the total revenue under $\Theta$ to be greater than or equal to $R$, the revenue from $\{\S_i\}_{i=1}^n \cup \{\mathbb{T}_i\}_{i=1}^n$ must be at least $3n/2$ and the revenue from $\{\mathbb{C}_j\}_{j=1}^m$ must be at least $m$. Hence, under $\Theta$, buyer $U$ has a throttling parameter of $1$, and for each $i \in [n]$, either $(\theta_i^+ = 1, \theta_i^- = 1/2)$ or $(\theta_i^+ = 1/2, \theta_i^- = 1)$. Furthermore, the payment made by buyer $U$ on $\mathbb{C}_j$ is 1 for every $j \in [m]$. This allows us to assign values to the variables as follows: set $x_i = 1$ if $\theta_i^+ = 1$ and $x_i = 0$ if $\theta_i^- = 1$. With this assignment of the variables, each clause is satisfied since the payment made by buyer $U$ on $\mathbb{C}_j$ is 1 for all $j \in [m]$. Hence, we have shown that if there exists a $\delta$-approximate throttling equilibrium with revenue $R$ or greater, then there exists a satisfying assignment for the 3-SAT instance.

Conversely, note that if there exists a satisfying assignment for the 3-SAT instance, then setting $\theta_i^+ = 1$, $\theta_i^- = 1/2$ if $x_i = 1$ and $\theta_i^+ = 1/2$, $\theta_i^- = 1$ if $x_i = 0$ yields a throttling equilibrium with revenue equal to $R$. To complete the proof, observe that the size of the instance $|\mathcal{I}| = \text{poly}(n,m)$.
\end{proof}
\section{Appendix: Missing Proofs}

\subsection{Proof of Theorem~\ref{thm:second-price-PPAD-membership}}\label{appendix:PPAD-membership}


	Consider a throttling game $\left(n, m, (b_{ij}), (B_i)\right)$ and an approximation parameter $\delta \in (0,1/2)$. Define $f: [0,1]^n \to [0,1]^n$ as
		\begin{align*}
    		f_i(\theta) = \min\left\{ \frac{(1 - \delta/2)B_i}{\sum_j p(1, \theta_{-i})_{ij}}, 1 \right\} = \min\left\{ \frac{(1 - \delta/2)B_i}{\max\{\sum_j p(1, \theta_{-i})_{ij}, B_i/2\} }, 1 \right\} \quad \forall \theta \in [0,1]^n 
		\end{align*}
	
	First, we prove that $f$ is $L$-Lipschitz continuous with Lipschitz constant $L = 2mn \overline{B} \underline{B}^{-2} \overline{b}$, where $\overline{b} = \max_{i,j} b_{ij}$, $\overline{B} = \max_{i} B_i$. To achieve this, we will repeatedly use the following facts about Lipschitz functions. For Lipschitz continuous functions $f$ and $g$ with Lipschitz constants $L_1$ and $L_2$ respectively,
	\begin{itemize}
		\item $f + g$ is $L_1 + L_2$-Lipschitz continuous
		\item If $f$ and $g$ are bounded above by $M$, then $f \cdot g$ is $M(L_1 + L_2)$-Lipschitz continuous
		\item If $f$ is bounded below by $c$, then $1/f$ is $L_1/c^2$-Lipschitz continuous
		\item For a constant $C$, $\max\{f, C\}$ and $\min\{f,C\}$ are both $L_1$-Lipschitz continuous
	\end{itemize}
	Observe that
	\begin{align*}
	    p(1, \theta_{-i})_{ij} =\sum_{\ell: b_{\ell j} < b_{ij}}  b_{\ell j} \theta_\ell  \prod_{k \neq i: b_{kj} > b_{\ell j}} (1 - \theta_k)
	\end{align*}
	Therefore, for all $i \in [n]$, $\theta \mapsto p(1, \theta_{-i})_{ij}$ is $(2n\overline{b})$-Lipschitz continuous, which further implies that $\theta \mapsto \sum_{j} p(1, \theta_{-i})_{ij}$ is $2mn\overline{b}$-Lipschitz continuous. Finally, due to the second equality in the definition of $f$, we get that $f$ is $(2mn \overline{B} \underline{B}^{-2} \overline{b})$-Lipschitz continuous.
	
	Since BROUWER is in PPAD~\cite{chen2009settling}, to complete the proof, it suffices to show that a $(\delta \underline{B}/4m \overline{b})$-approximate fixed point $\theta^*$ of $f$, i.e, $\theta^*$ such that $\|f(\theta^*) - \theta^*\|_\infty \leq \delta \underline{B}/4m \overline{b}$, is a $\delta$-approximate throttling equilibrium. First, note that $p(1, \theta_{-i})_{ij} \leq \overline{b}$ for all $i \in [n], j \in [m]$. Therefore, $f(\theta)_i \geq \underline{B}/2m \overline{b}$ for all $i \in [n]$. Hence, for $i \in [n]$, we have
	\begin{align*}
		\biggr\lvert 1 - \frac{\theta_i^*}{f_i(\theta^*)} \biggr\rvert \leq 	\frac{\delta \underline{B}}{f_i(\theta^*) \cdot 4m \overline{b}} \leq \frac{\delta}{2}
	\end{align*}
	As a consequence, we get $\theta_i^* \leq (1 + \delta/2) f_i(\theta^*)$ and $ \theta^* \geq (1- \delta/2) f_i(\theta^*)$. The first inequality implies  which in turn implies
	\begin{align*}
		\sum_j p(\theta^*)_{ij} = \theta^*_i \cdot \sum_j p(1, \theta^*)_{ij} \leq (1 + \delta/2)(1 - \delta/2)B_i \leq B_i
	\end{align*}
	 and the second one implies that if $\theta^*_i < 1 - \delta/2$, then
	 \begin{align*}
	 	\sum_j p(\theta^*)_{ij} = \theta^*_i \cdot \sum_j p(1, \theta^*)_{ij} \geq (1 - \delta/2)^2 B_i \geq (1 - \delta)B_i
	 \end{align*}
	 Hence, $\theta^*$ is a $\delta$-approximate throttling equilibrium, thereby completing the proof.\qed

\section{Appendix: Examples for Section~\ref{sec:TE-PE}}\label{appendix:TE-PE}

First, we provide an example to show that the inequality REV(TE) $\leq 2 \times \text{REV(TE)}$ is tight.

\begin{example}
    Consider the throttling game in which there is 1 good and 2 buyers. The bids are given by $b_{11} = 1/\epsilon$, $b_{21} = 1 - \epsilon$ for $\epsilon > 0$ and the budgets are given by $B_1 = 1$, $B_2 = \infty$. Then, in the unique pacing equilibrium, we have $\alpha_1 = \epsilon$ and $\alpha_2 = 1$, whereas in the unique throttling equilibrium, we have $\theta_1 = \epsilon$ and $\theta_2 = 1$. Hence, REV(PE) = 1 and REV(TE) = $1 + (1 - \epsilon)^2$. Since, this is true for arbitrarily small $\epsilon$, we get that the inequality REV(TE) $\leq 2 \times \text{REV(TE)}$ is tight established in Theorem~\ref{thm:revenue-comparison} is tight.
\end{example}

Next, we give a family of examples for which REV(PE) is arbitrarily close to $(4/3) \times \text{REV(TE)}$.

\begin{example}
    Consider a throttling game with 2 goods and 2 buyers. Fix $\epsilon> 0$. The bids are given by $b_{11} = 1 + \epsilon$, $b_{12} = 1$ and $b_{21} = 1$. Moreover, the budgets are given by $B_1 = 1 - \epsilon$ and $B_2 = \infty$. Then, the unique pacing equilibrium is given by $\alpha_1 = 1 - \epsilon$, $\alpha_2 = 1$, and the unique throttling equilibrium is given by $\theta_1 = (1 - \epsilon)/(2 + \epsilon)$, $\theta_2 = 1$. Since $\epsilon$ was arbitrary, we can take it to be arbitrarily small. In which case, we get REV(PE) $\simeq$ 2 and REV(PE) $\simeq$ 1.5, as desired.
\end{example}
\section{Appendix: Examples of Irrational Throttling Equilibria}\label{appendix:irrationality}

\paragraph{First-Price Auctions:} First, we give an example for which the unique \emph{first-price} throttling equilibrium is irrational.

\begin{example}\label{example:first-price-irrational}
	Define a throttling game as follows:
	 There are 2 goods and 2 buyers, i.e., $m = 2$ and $n = 2$;
	 $b_{11} = b_{12} =  2$ and $b_{21} = 1, b_{22} = 3$;
    $B_1 = 2$ and $B_2 = 1$.

	Suppose, in equilibrium, the buyers use the throttling parameters $\theta_1$ and $\theta_2$. Then the payment of buyer 1 and buyer 2 are given by $2\theta_1 + 2(1 - \theta_2)\theta_1$ and $3\theta_2 + (1 -  \theta_1) \theta_2$ respectively. Therefore, for this game, in any throttling equilibrium, we have $0 < \theta_1, \theta_2 < 1$ and $\theta_3 = 1$, which implies
	  $  2\theta_1 + 2(1 - \theta_2)\theta_1 = 2$ and $3\theta_2 + (1 -  \theta_1) \theta_2 = 1
	$.
	Substituting $\theta_1 = 1/(2 - \theta_2)$ from the first equation into the second   yields
	\begin{align*}
 	   3\theta_2 + \theta_2 \cdot \frac{1 - \theta_2}{2 - \theta_2} = 1 
	\end{align*}
	which implies $4 \theta_2^2 - 7 \theta_2 + 1 = 0$. As $\theta_2 < 1$, Solving the quadratic gives $\theta_2 = (7 - \sqrt{33})/8$.
\end{example}


\paragraph{Second-Price Auctions:} Next, we give an example for which all \emph{second-price} throttling equilibria are irrational.

\begin{example}\label{example:irrational_eq}
	Define a throttling game as follows:
	\begin{itemize}
    	\item There are 4 goods and 3 buyers, i.e., $m = 4$ and $n = 3$
    	\item $b_{11} = b_{12} = 2$, $b_{14} = 1$, $b_{23} = b_{24} = 4$, $b_{22} = 1$, $b_{31} = 1$ and $b_{33} = 2$
    	\item $B_1 = B_2 = 1$ and $B_3 = \infty$
	\end{itemize}
	For this game, in any throttling equilibrium, we have $0 < \theta_1, \theta_2 < 1$ and $\theta_3 = 1$. Hence, if $\theta$ is a throttling equilibrium, then it satisfies
	$	    \theta_1 + \theta_1 \theta_2 = 1$ and $2\theta_2 + \theta_2 \theta_1 = 1 $.
	Substituting $\theta_1 = 1/(1 + \theta_2)$ from the first equation into the second equation yields
	\begin{align*}
 	   2\theta_2 + \theta_2 \cdot \frac{1}{1 + \theta_2} = 1 
	\end{align*}
	which further implies $2 \theta_2^2 + 2 \theta_2 - 1 = 0$. As $\theta_2 > 0$, solving the quadratic gives $\theta_2 = (\sqrt{3} - 1)/2$.
\end{example}
\subsection{Proof of Theorem~\ref{thm:two-buyer}}\label{appendix:two-buyer}

In this appendix, we analyze the correctness and runtime of Algorithm~\ref{alg:two_buyer}. To do so, we will make repeated use of the following crucial observation:
\begin{align} \label{two_buyer_payment}
    p(\theta)_{ij} =
    \begin{cases}
        \theta_i \theta_k b_{kj} &\text{if } b_{ij} > b_{kj} > 0\ \text{for some } k \in [n]\\
        0 &\text{otherwise}
    \end{cases}
\end{align}
In particular, this observation implies that $p(1, \theta_i)$ is a linear function of $\theta$.

The following lemma makes a step towards the proof of correctness of the algorithm by showing that the budget constraints are always satisfied.

\begin{lemma}\label{lemma:alg_budget}
    At the start of each iteration of the while loop, we have $\sum_j p(\theta)_{ij} \leq B_i$ for all $i \in [n]$.
\end{lemma}
\begin{proof}
    We will use induction on the number of iterations of the while loop to prove this lemma. By our choice of initialization of $\theta$, the budget constraints are satisfied before the first iteration of the while loop. Suppose the constraints are satisfied before the start of the $t$-th iteration and the value of $\theta$ at that stage is $\theta^{(0)}$. We will use $\theta^{(1)}$ and $\theta^{(2)}$ to the denote the value of $\theta$ after step 1 and step 2 of the $t$-th iteration respectively. Consider a buyer $i$ such that $\sum_j p(\theta^{(1)})_{ij} > B_i$. By equation~\ref{two_buyer_payment}, we get $$B_i < \sum_j p(\theta^{(1)})_{ij} \leq \left(\sum_j p(\theta^{(0)})_{ij}\right)/(1 - \gamma)^2$$ which further implies $\sum_j p(\theta^{(0)})_{ij} > (1 - \gamma)^2 B_i$. Therefore, the throttling parameter of buyer $i$ was not changed in step 1 of the $t$-th iteration, i.e., $\theta_i^{(0)} = \theta_i^{(1)}$. As a consequence, we get
    \begin{align*}
        \sum_j p(\theta^{(1)})_{ij} \leq \left(\sum_j p(\theta^{(0)})_{ij}\right)/(1 - \gamma)
    \end{align*}
    After step 2 of the $t$-th iteration, we get $\theta^{(2)} = (1 - \gamma) \theta^{(1)}$. Hence,
    \begin{align*}
        \sum_j p(\theta^{(2)})_{ij} \leq (1 - \gamma)\sum_j p(\theta^{(1)})_{ij} \leq \left(\sum_j p(\theta^{(0)})_{ij}\right) \leq B_i
    \end{align*}
    where the last inequality follows from our inductive hypothesis. As $\theta^{(2)}$ is the value of $\theta$ after the $t$-th iteration, the lemma follows by induction.
\end{proof}

The next lemma establishes that the algorithm never loses any progress, i.e., any buyer who satisfies the `Not too much unnecessary throttling condition' of Definition~\ref{def:throt_eq} at the beginning of some iteration of the while loop continues to do so at the end of it.

\begin{lemma}\label{lemma:alg_progress}
    If $\sum_j p(\theta)_{ij} \geq (1 - \gamma)^3 B_i$ or $\theta_i \geq 1 - \gamma$ at the start of some iteration of the while loop, then $\sum_j p(\theta)_{ij} \geq (1 - \gamma)^3 B_i$ or $\theta_i \geq 1 - \gamma$ at the end of that iteration.
\end{lemma}
\begin{proof}
    Consider an iteration of while loop which starts with $\theta = \theta^{(0)}$. We will use $\theta^{(1)}$ and $\theta^{(2)}$ to the denote the value of $\theta$ after step 1 and step 2 of this iteration. If $\sum_j p(\theta^{(0)})_{ij} \geq (1 - \gamma)^2 B_i$ at the beginning of the iteration, then $\sum_j p(\theta^{(2)})_{ij} \geq (1 - \gamma)^3 B_i$ because
    \begin{align*}
        \sum_j p(\theta^{(1)})_{ij} \geq (1 - \gamma)^2 B_i \quad \text{and} \quad \sum_j p(\theta^{(2)})_{ij} \geq (1 - \gamma) \sum_j p(\theta^{(1)})_{ij}
    \end{align*}
    Suppose $(1 - \gamma)^3 B_i \leq  \sum_j p(\theta^{(0)})_{ij} < (1 - \gamma)^2 B_i$ and $\theta^{(0)}_i < 1 -\gamma$ at the start of the iteration. Then, after step 1, we have $(1 - \gamma)^2 B_i \leq  \sum_j p(\theta^{(1)})_{ij} \leq B_i$. Hence, after step 2, we get $(1 - \gamma)^3 B_i \leq  \sum_j p(\theta^{(3)})_{ij}$. 
    
    Finally, suppose $(1 - \gamma)^3 B_i \leq  \sum_j p(\theta^{(0)})_{ij} < (1 - \gamma)^2 B_i$ and $\theta^{(0)}_i \geq 1 -\gamma$ at the start of the iteration. Then, after step 1, we have $\sum_j p(\theta^{(1)})_{ij} \leq B_i$. Hence, after step 2, we still have $\theta^{(2)}_i \geq (1 - \gamma)$. This completes the proof of the lemma.
\end{proof}

Finally, we combine the above lemmas to establish the correctness and polynomial-runtime of the algorithm.

\begin{proof}[Proof of Theorem~\ref{thm:two-buyer}]
    Let $\theta^*$ be the vector of throttling parameters returned by the algorithm. Lemma~\ref{lemma:alg_budget} implies that $\theta^*$ satisfies the budget constraints of every buyer. Furthermore, upon combining $(1 - \gamma)^3 \geq 1 - 3 \gamma$ with the termination condition of the while loop, we get that either $\theta^*_i \geq 1 - \gamma$ or $\sum_j p(\theta^*)_{ij} \geq (1 - 3\gamma) B_i$ for all $i \in [n]$, which makes $\theta^*$ a $(1 - 3 \gamma)$-approximate throttling equilibrium.
    
    Next, we bound the running time of the algorithm. Define $c = \min_i \min\{B_i/ (2\sum_j b_{ij}), 1\}$. Note that $c \leq \theta_i \leq 1$ for all $i \in [n]$ for the entire run of the algorithm. Based on Lemma~\ref{lemma:alg_progress}, we define
    \begin{align*}
        A(\theta) \coloneqq \{i \in [n] \mid\sum_j p(\theta)_{ij} \geq (1 - \gamma)^3 B_i \text{ or } \theta_i \geq 1 - \gamma
    \end{align*}
    Then Lemma~\ref{lemma:alg_progress} simply states that if $i \in A(\theta)$ at the start of iteration $T$ of the while loop, then $i \in A(\theta)$ at the start of all future iterations $t \geq T$. Moreover, recall that the while loop terminates when $A(\theta) = [n]$. 
    
    Observe that, in each iteration of the while loop, $\theta_i \leftarrow \theta_i/(1- \gamma)$ for some $i \notin A(\theta)$. Hence, the total number of iterations of the while loop $T$ satisfies the following equivalent statements:
    \begin{align*}
        \frac{c}{(1 -\gamma)^{T/n}} \leq 1 \iff T \leq \frac{n \log(1/c)}{\log(1/ (1-\gamma))} \leq \frac{n\log(1/c)}{\gamma}
    \end{align*}
    This completes the proof because each iteration takes polynomially many steps.
\end{proof}
\section{Conclusion and Future Work}

We defined the notion of a throttling equilibrium and studied its properties for both first-price and second-price auctions. Through our analysis of computational and structural properties, we found that throttling equilibria in first-price auctions satisfy the desirable properties of uniqueness and polynomial-time computability. 
In contrast, we showed that for second-price auctions, equilibrium multiplicity may occur, and computing a throttling equilibrium is PPAD hard.
This disparity between the two auction formats is reinforced when we compare throttling and pacing: our results show that the properties of throttling equilibrium across the two formats have a striking similarity to the properties of first-price versus second-price pacing equilibrium. 

There are many interesting directions for future work, such as what happens when a combination of pacing and throttling-based buyers exist in the market, whether the combination of throttling and pacing behaves well for second-price auctions, whether second-price throttling equilibria can be computed efficiently under some natural assumptions on the bids, and whether the tractability of budget management in first-price auctions holds more generally beyond throttling and pacing. 
\section{Throttling in Second-price Auctions}

In this section, we study throttling equilibria in second-price auctions. We begin by establishing the existence of exact throttling equilibria. Next, we show that, in contrast to first-price auctions, it is PPAD-hard to compute an approximate throttling equilibrium. To complete the characterization of its complexity, we then place the problem in PPAD. Moreover, we also show that, unlike first-price auctions, multiple throttling-equilibria can exist for second-price auctions, and finding the revenue-maximizing one is NP-hard. Finally, we complement these negative results with an efficient algorithm for the case when each good has at most two positive bids.

\subsection{Existence of Second-Price Throttling Equilibria}

The following theorem establishes the existence of an exact throttling equilibrium for every bid profile by invoking Brouwer's fixed-point theorem on an appropriately defined function.

\begin{theorem}\label{theorem:existence_second_price}
	For every throttling game $\left(n, m, (b_{ij}), (B_i)\right)$, there exists a throttling equilibrium $\theta^* \in [0,1]^n$.
\end{theorem}

\begin{proof}
	First, observe that we can write the expected payment of buyer $i$ on good $j$ under $\theta$ as 
	\begin{align}\label{eq:exp_pay}
		p(\theta)_{ij} = \sum_{\ell: b_{\ell j} < b_{ij}}  b_{\ell j} \theta_i  \theta_\ell  \prod_{k \neq i: b_{kj} > b_{\ell j}} (1 - \theta_k) = \theta_i \cdot \sum_{\ell: b_{\ell j} < b_{ij}}  b_{\ell j}  \theta_\ell  \prod_{k \neq i: b_{kj} > b_{\ell j}} (1 - \theta_k)	 = \theta_i \cdot p(1, \theta_{-i})_{ij}
	\end{align}

	Define $f: [0,1]^n \to [0,1]^n$ as
	\begin{align*}
    	f_i(\theta) = \min\left\{ \frac{B_i}{\sum_j p(1, \theta_{-i})_{ij}}, 1 \right\} \quad \forall \theta \in [0,1]^n
	\end{align*}
	where, we assume that $f_i(\theta) = 1$ if $\sum_j p(1, \theta_{-i})_{ij} = 0$. Note that $p(1, \theta_{-i})_{ij}$ is a continuous function of $\theta$ because it is a polynomial. Therefore, $f$ is continuous as a function of $\theta$ and hence, by Brouwer's fixed-point theorem, there exists a $\theta^*$ such that $f(\theta^*) = \theta^*$. As a consequence, for all buyers $i \in [n]$, we get the following equivalent statements
	\begin{align*}
		f_i(\theta^*) = \theta^*_i \iff \theta^*_i \cdot \sum_j p(1, \theta^*_{-i})_{ij} < B_i \text{ implies } \theta^*_i = 1 \iff \sum_j p(\theta^*)_{ij} < B_i \text{ implies } \theta^*_i = 1
	\end{align*}
	where the last equivalence follows from equation~\ref{eq:exp_pay}. Moreover, by definition of $f$, we get
	\begin{align*}
		\theta^*_i = f_i(\theta^*) \leq 	\frac{B_i}{\sum_j p(1, \theta_{-i})_{ij}}
	\end{align*}
	which in conjunction with equation~\ref{eq:exp_pay} implies $\sum_j p(\theta^*)_{ij} \leq B_i$. Therefore,  $\theta^*$ is a throttling equilibrium.
\end{proof}

Even though the above theorem establishes the existence of a throttling equilibrium for every throttling game, in Appendix~\ref{appendix:irrationality} we give an example of a throttling game for which all equilibria have a buyer with an irrational throttling parameter. This prompts us to study the problem of computing \emph{approximate} throttling equilibria, which we do in the following subsections.







\section{First Price Auctions}


\subsection{Complexity of Finding Approximate Second-Price Throttling Equilibria}
 
In the previous subsection, by way of our existence proof, we reduced the problem of finding an approximate throttling equilibrium to that of finding a Brouwer fixed point of the function $f$; but this is of little use if we want to actually compute an approximate throttling equilibrium: no known algorithm can compute a Brouwer fixed point in polynomial time and it is believed to be a hard problem. This is because the problem of computing an approximate Brouwer fixed point is a complete problem for the class PPAD \cite{papadimitriou1994complexity}; informally, this means that it is as hard as any other problem in the class, such as computing Nash equilibria of bimatrix games~\cite{daskalakis2009complexity, chen2009settling} or computing a market equilibrium under piece-wise linear concave utilities~\cite{chen2009spending, vazirani2011market}. These problems have eluded a polynomial-time algorithm for decades despite intensive effort.

However, through our reduction we have only shown that the problem of computing an approximate throttling equilibrium is easier than the problem of computing a Brouwer fixed point by showing that any algorithm for the latter can be employed to solve the former. Perhaps, computing an approximate throttling equilibrium is strictly easier? Unfortunately, this is not the case and the goal of this subsection is to prove it. More precisely, we show that the problem of finding an approximate throttling equilibrium is PPAD-hard, which in informal terms means that it is as hard as any other problem in the class PPAD, in particular that of computing a Brouwer fixed point. Before stating the hardness result itself, we note a consequence of particular importance: Under the assumption that PPAD-hard problems cannot be solved in polynomial time, no dynamics can efficiently converge to an approximate throttling equilibrium in polynomial time, which is in stark contrast to throttling in first-price auctions. Now, we state the main result of the section.
\color{black}
\begin{theorem}\label{thm:second-price-PPAD-hard}
There is a positive constant $\delta<1$ such that the problem
  of finding a $\delta$-approximate throttling equilibrium in a throttling game is PPAD-hard. 
This holds even when the number of buyers with non-zero bids 
  for each good is at most three.
\end{theorem}

  The proof of Theorem~\ref{thm:second-price-PPAD-hard} uses \emph{threshold games}, introduced recently by Papadimitriou and Peng \cite{PB2021}.
They showed that the problem of finding an approximate equilibrium in a threshold game is PPAD-complete. %
\begin{definition}[Threshold game \cite{PB2021}]
	\label{def:threshold}
	A threshold game is defined over a directed graph $\mathcal{G} = ([n], E)$. Each node $i\in [n]$ represents a player with strategy space $x_i\in [0,1]$. 
	Let $N_i$ be the set of nodes~$j\in [n]$ with $(j,i)\in E$.
Then $ (x_i:i\in [n]) \in [0, 1]^{n}$ is an $\epsilon$-\emph{approximate equilibrium} if every $x_i$ satisfies

	\begin{align*}
	x_i \in  
	\begin{cases}
	[0,\epsilon] & \sum_{j \in N_i} x_j > 0.5 + \epsilon\\
	[1-\epsilon,1] & \sum_{j \in N_i} x_j < 0.5 - \epsilon\\
	[0,1] & \sum_{j \in N_i}x_j \in[ 0.5 - \epsilon, 0.5+\epsilon] 
	\end{cases}
	\end{align*}
\end{definition}



\begin{theorem}[Theorem 4.7 of \cite{PB2021}]
	\label{thm:ppad-threshold}
	There is a positive constant $\epsilon<1$ such that the problem of 
  finding an $\epsilon$-approximate equilibrium in a threshold game is PPAD-hard. 
This holds even when the in-degree and out-degree of each node is at most three in the threshold game.
\end{theorem}

Given a threshold game $\mathcal{G}=([n],E)$, we let $O_i$ denote the set of nodes $j\in V$ with $(i,j)\in E$. 
So $|N_i|,|O_i|\le 3$ for every $i\in [n]$. To prove Theorem~\ref{thm:second-price-PPAD-hard}, we need to construct a throttling game $\mathcal{I}_\mathcal{G}$ from $\mathcal{G}$ such that any approximate throttling equilibrium of $\mathcal{I}_\mathcal{G}$ corresponds to an approximate equilibrium of the threshold game. Before rigorously diving into the construction, we give an informal description to build intuition.

 {With each node of $\mathcal{G}$, we will associate a collection of buyers and goods, with the goal of capturing the corresponding strategy and equilibrium conditions of the threshold game. Fix a node $i \in [n]$. We will define a strategy buyer $S(i)$ and set the strategy $x_i$ for node $i$ to be proportional to $1 - \theta_{S(i)}$. Next, in order to implement the equilibrium condition of the threshold game, our goal will be to define buyers and goods such that the linear form $\sum_{j \in N_i} x_j$ ends up being proportional to the total payment of a buyer who we will refer to as the threshold buyer $T(i)$. For each in-neighbour $j \in N_i$, we will define a neighbour good $G(i,j)$, for which the strategy buyer of the neighbour $S(j)$ places the highest bid of $6$ and the threshold buyer $T(i)$ places a bid of 5. Furthermore, for a reason that will become clear shortly, the strategy buyer $S(i)$ places a bid of 4 on $G(i,j)$. With these bids, the payment made by the threshold buyer $T(i)$ on all the neighbour goods $\{G(i,j)\}_j$ is proportional to $\theta_{T(i)} \theta_{S(i)} \sum_{j \in N_i} (1 - \theta_S(j)) = \theta_{T(i)} \theta_{S(i)} \sum_{j \in N_i} x_j$. Now, if we are somehow able to ensure that the throttling parameter of the strategy buyer $\theta_{S(i)}$ is inversely proportional to the throttling parameter of the threshold buyer $\theta_{T(i)}$, then the payment made by the threshold buyer on all the neighbour goods will be proportional to $\sum_{j \in N_i} x_j$, as desired. To achieve this, we define a reciprocal good $R(i)$. Finally, we set the budget of the threshold buyer $T(i)$ in such a way that comparing it to her payment, which is proportional to $\sum_{j \in N_i} x_j$, is tantamount to making a comparison between $\sum_{j \in N_i} x_j$ and $0.5$. The challenging part of the reduction lies in setting up the bids and budgets in a way that ensures that this comparison leads to an enforcement of the equilibrium condition of the threshold game.}

\begin{figure}
    \centering
    \includegraphics[width = 3.5in, angle = 0]{Throttling2.pdf}
    \caption{A diagrammatic representation of the non-zero bids made and received by the buyers and goods corresponding to a particular node of the threshold game. Consider a particular node of the threshold game, represented here by the black rectangle. It has three \textcolor{orange}{out neighbours}, depicted as orange rectangles, and three \textcolor{magenta}{in neighbours}, depicted as pink rectangles. The hollow circles represent goods and the solid circles represent buyers. Corresponding to each node of the threshold game, there is one \textcolor{OliveGreen}{strategic buyer}, shown here in green, and one \textcolor{brown}{threshold buyer}, shown in brown. Furthermore, for each node of the threshold game, there are three \textcolor{red}{neighbour goods}, shown in red, and one \textcolor{blue}{reciprocal good}, shown in blue. The lines represent non-zero bids.}
    \label{fig:PPAD}
\end{figure}

With this high level overview of the reduction in place, we move on to the rigorous construction of the throttling game $\mathcal{I}_\mathcal{G}$ from $\mathcal{G}$. First, $\mathcal{I}_\mathcal{G}$ contains the following set of goods:
\begin{itemize}
    \item For each $i \in [n]$ and $j \in N_i$, there is a \emph{neighbor good} $G(i,j)$.
    \item For each $i \in [n]$, there is a \emph{reciprocal good} $R(i)$.
\end{itemize}
Next, setting two constants $M$ and $\delta$ as $ M = {160}/{\delta}$ and 
$\delta=\min  \{\epsilon/(3 + \epsilon), \epsilon/2, 1/4  \},$
the throttling game $\mathcal{I}_\mathcal{G}$ has the following set of buyers:
\begin{flushleft}\begin{itemize}
    \item For each $i\in [n]$, there is a \emph{threshold buyer} $T(i)$ who has
    budget $1/2$ and has non-zero bids only on the following goods:
    $b(T(i), G(i,j)) = 5$ for all $j \in N_i$; and
     $b(T(i), R(i)) = M|O_i|$.
   
   
    \item For each $i \in [n]$, there is a \emph{strategy buyer} $S(i)$
    who has budget $M|O_i|/2$ and has non-zero bids only on the following goods:
     $b(S(i), R(i)) = M|O_i| + 1$;
      $b(S(i), G(i,j)) = 4$ for all $j \in N_i$; and
       $b(S(i), G(j, i)) = 6$ for all $j \in O_i$.
   
\end{itemize}\end{flushleft}
It is clear that $\mathcal{I}_\mathcal{G}$ can be constructed from $\mathcal{G}$ in polynomial time, and the number of buyers with non-zero bids
for each good is at most three.
Let $\theta$  be any $\delta$-approximate throttling equilibrium of $\mathcal{I}_\mathcal{G}$ 
and use it to define $(x_i:i\in [n])\in [0,1]^n$ as follows: 
\begin{equation}\label{heheeq}
x_i = \min\big\{2(1 - \theta_{S(i)}),1\big\},\quad\text{for all $i \in [n]$.}
\end{equation}
To complete the reduction, we will show that $  (x_i:i\in [n])$ is an $\epsilon$-approximate equilibrium of the threshold game $\mathcal{G}$. Since we are considering a particular $\theta$, we will suppress the dependence on $\theta$ of the payment made by buyer $B$ on good $G$ and simply denote it by $p(B,G)$. The next lemma notes the payment terms of buyers in $\mathcal{I}_\mathcal{G}$.

\begin{lemma}\label{lemma:buyer_payments}
    For all $i \in [n]$, we have
    \begin{flushleft}\begin{enumerate}
        \item $p(T(i), G(i,j)) = \left(1 - \theta_{S(j)}\right)\theta_{T(i)}\theta_{S(i)} 4$, for all $j \in N_i$; and $p(T(i), R(i)) = 0$.
        \item $p(S(i), R(i)) = \theta_{S(i)} \theta_{T(i)} M |O_i|$;
        $p(S(i), G(i,j)) = 0$, for all $j \in N_i$; and
        $$p(S(i), G(j,i)) = \theta_{S(i)} \left[\theta_{T(j)} 5\ +\ (1 - \theta_{T(j)}) \theta_{S(j)} 4 \right],\quad\text{for all $j \in O(i)$.}$$
    \end{enumerate}\end{flushleft}
\end{lemma}

In the next lemma, we bound the total payment made by strategy buyer $S(i)$ on the neighbor goods and provide lower bounds on the throttling parameters:

\begin{lemma} \label{lemma:neighbour_payment_bound}
    For all $i \in [n]$, we have $\theta_{S(i)} \geq (1 - 2 \delta)/2$, $\theta_{T(i)} \geq 1/32 $, and
    the total payment of $S(i)$ on the neighbor goods satisfies:
            \begin{align*}
                |O_i| \theta_{S(i)} \leq \sum_{j \in N_i} p(S(i), G(i,j)) + \sum_{j \in O_i} p(S(i), G(j,i)) \leq 5 |O_i| \theta_{S(i)}
            \end{align*}
   
    %
\end{lemma}
\begin{proof}
    For $i \in [n]$, using Lemma~\ref{lemma:buyer_payments}, we get
    \begin{align*}
        \sum_{j \in N_i} p(S(i), G(i,j)) + \sum_{j \in O_i} p(S(i), G(j,i)) =  \sum_{j \in O_i} \theta_{S(i)} \left[\theta_{T(j)} 5\ +\ (1 - \theta_{T(j)}) \theta_{S(j)} 4 \right] \leq 5 |O_i| \theta_{S(i)}.
    \end{align*}
    Suppose $\theta_{S(i)} < (1 - 2\delta)/2$ for some $i \in [n]$. Then, the total payment made by $S(i)$ is at most
    \begin{align*}
        \theta_{S(i)} \theta_{T(i)} M |O_i| + 5|O_i|\theta_{S(i)}
       
        < \frac{(1 - 2 \delta)M|O_i|}{2} + 5|O_i|
        < (1 - \delta) \cdot \frac{M|O_i|}{2}
    \end{align*}
    using $M>10/\delta$ by our choice of $M$.
    This contradicts the definition of $\delta$-approximate throttling equilibrium because $S(i)$ has a budget of $M|O_i|/2$. Therefore, we have $\theta_{S(i)}\ge (1-2\delta)/2$ and in particular, $\theta_{S(i)} \ge 1/4$ for all $i \in [n]$ using $\delta\le 1/4$. Hence,
    \begin{align*}
        \sum_{j \in N_i} p(S(i), G(i,j)) + \sum_{j \in O_i} p(S(i), G(j,i)) &=  \sum_{j \in O_i} \theta_{S(i)} \left[\theta_{T(j)} 5\ +\ (1 - \theta_{T(j)}) \theta_{S(j)} 4 \right]\\
        &> \sum_{j \in O_i} \theta_{S(i)} \left[\theta_{T(j)} \theta_{S(j)} 4\ +\ (1 - \theta_{T(j)}) \theta_{S(j)} 4 \right]\\
        &= 4\theta_{S(i)} \cdot \sum_{j \in O_i}  \theta_{S(j)} 
         \geq
          |O_i|\theta_{S(i)}.
    \end{align*}
   
    
    Suppose, $\theta_{T(i)} < 1/32$. By Lemma~\ref{lemma:buyer_payments} the total payment of threshold buyer $T(i)$ is at most $$\sum_{j\in N_i} 4\theta_{T(i)}\le 12 \theta_{T(i)}<\frac{3}{8}\le \frac{1-\delta}{2}$$ using $|N_i|\le 3$ and $\delta\ge 1/4$. 
   
    Hence, we have obtained a contradiction with the definition of $\delta$-approximate throttling equilibria. Therefore, $\theta_{T(i)} \geq 1/32$.
\end{proof}

We are now ready to complete the reduction.

\begin{lemma}
 $(x_i:i\in [n])$, as defined in (\ref{heheeq}), is an $\epsilon$-approximate equilibrium of the threshold game $\mathcal{G}$.
\end{lemma}
\begin{proof}
    Fix an $i \in [n]$. First consider the case when $\sum_{j \in N_i} x_j >0.5 + \epsilon$. Assume for a contradiction that $x_i > \epsilon$. Then, $\theta(S(i)) < 1 - (\epsilon/2) \leq 1 -\delta$ using $\delta\le \epsilon/2$. By the definition of $\delta$-approximate throttling equilibrium, the total payment of threshold buyer $S(i)$ is at least $(1 -\delta)M|O_i|/2$. Combining this observation with Lemma~\ref{lemma:buyer_payments} and Lemma~\ref{lemma:neighbour_payment_bound}, we get
    \begin{align*}
        \theta_{S(i)} \left[\theta_{T(i)} M |O_i| + 5|O_i|\right] \geq (1 -\delta) \cdot \frac{M|O_i|}{2}
    \end{align*}
and thus (using $\theta_{T(i)}\ge 1/32$ from Lemma \ref{lemma:neighbour_payment_bound}
  and our choice of $M=160/\delta$),
$$  \theta_{S(i)} \geq \frac{1-\delta}{2 \theta_{T(i)} + (10/M)} \geq \frac{1}{2 \theta_{T(i)}} \cdot \frac{1 -\delta}{1+\delta} \ \ \implies\ \  \theta_{T(i)}\theta_{S(i)} \geq \frac{1}{2 (1 + 2 \epsilon)}
   $$ using $\delta\le \epsilon/2$ and $\epsilon< 1$.
    Moreover, note that $\sum_{j \in N_i} x_j > 0.5 + \epsilon$ implies $$\sum_{j \in N_i} 2\left(1 - \theta_{S(j)}\right) > (1+2\epsilon)/2$$ Combining the above statements allows us to bound the total payment of buyer $T(i)$:
    \begin{align*}
        \sum_{j \in N_i} \left(1 - \theta_{S(j)}\right)\theta_{T(i)}\theta_{S(i)} 4 \geq \frac{4}{2 (1 + 2 \epsilon)} \cdot \sum_{j \in N_i} \left(1 - \theta_{S(j)}\right) > \frac{1}{2}.
    \end{align*}
    This yields a contradiction because $T(i)$ has budget  $1/2$. Hence $x_i \leq \epsilon$ when $\sum_{j \in N_i} x_j > 0.5 + \epsilon$.
    Next consider the case of $\sum_{j \in N_i} x_j < 0.5 - \epsilon$. The budget constraint of $S(i)$ and Lemma~\ref{lemma:neighbour_payment_bound} yield 
    \begin{align*}
        \theta_{S(i)} \left[\theta_{T(i)} M |O_i| + |O_i|\right] \leq \frac{M|O_i|}{2}
        \end{align*}
which implies that 
\begin{align}\label{heheeq2}\theta_{S(i)} \left[\theta_{T(i)} M |O_i| + \theta_{T(i)}|O_i|\right] \leq \frac{M|O_i|}{2}\ \ 
         \implies\ \  \theta_{T(i)}\theta_{S(i)} \leq \frac{1}{2(1 + (1/M))}< \frac{1}{2}. 
    \end{align}
By Lemma~\ref{lemma:neighbour_payment_bound}, we have $\theta_{S(j)} \geq (1 - 2 \delta)/2$ and thus, $2(1 - \theta_{S(j)}) \leq 1 + 2\delta$. Multiplying both sides by $(1 - 2\delta)$ yields $2(1 - \theta_{S(j)})(1 - 2\delta) \leq 1 - 4\delta^2 < 1$. In other words, we have
\begin{equation}\label{heheeq3}
2(1 - \theta_{S(j)})(1 - 2\delta) < \min\{2(1 - \theta_{S(j)}), 1\} = x_j
\end{equation}
for every $j\in [n]$. This together with $\sum_{j \in N_i} x_j < 0.5 - \epsilon$ implies $$(1 - 2\delta)\sum_{j \in N_i} 2\left(1 - \theta_{S(j)}\right) < (1-2\epsilon)/2.$$ Therefore, we get that the total payment of $T(i)$ satisfies the following bound
    \begin{align*}
        \sum_{j \in N_i} \left(1 - \theta_{S(j)}\right)\theta_{T(i)}\theta_{S(i)} 4 < \sum_{j \in N_i} 2\left(1 - \theta_{S(j)}\right) < \frac{1 - 2\epsilon}{2(1 - 2\delta)} \leq (1 - \delta) \cdot \frac{1}{2} 
    \end{align*}
    using $\delta\le \epsilon/2$.
    As a consequence of the definition of $\delta$-approximate throttling equilibria, we have that $\theta_{T(i)} \geq 1 -\delta$. Finally, using (\ref{heheeq2}) and (\ref{heheeq3}), we have
    \begin{align*}
        x_i > 2(1 - \theta_{S(i)}) (1 - 2 \delta) \geq 2\left(1 - \frac{1}{2\theta_{T(i)}}\right) (1 - 2 \delta) \geq \frac{(1 - 2\delta)^2}{1 - \delta} > \frac{1 - 4 \delta}{1 - \delta} \geq 1 - \epsilon,
    \end{align*}
    where the last inequality follows from $\delta \leq \epsilon/(3 + \epsilon)$.
\end{proof}


This completes the reduction, and thereby the proof of Theorem~\ref{thm:second-price-PPAD-hard}, because we have shown that for any $\delta$-approximate throttling equilibrium of the throttling game $\mathcal{I}_\mathcal{G}$, the strategy $(x_i)_i$ is an $\epsilon$-approximate equilibrium of the threshold game $\mathcal{G}$.




\paragraph{PPAD Membership of Approximate Second-Price Throttling Equilibria}

Next, we show that the problem of computing a $\delta$-approximate throttling equilibrium belongs to PPAD by showing a reduction to BROUWER: the problem of computing an approximate fixed point of a Lipschitz continuous function from a $n$-dimensional unit cube to itself, which known to be in PPAD~\cite{chen2009settling}. Its proof is motivated by the argument for existence of exact throttling equilibria given in Theorem~\ref{theorem:existence_second_price} and can be found in Appendix~\ref{appendix:PPAD-membership}

\begin{theorem}\label{thm:second-price-PPAD-membership}
	The problem of computing an approximate throttling equilibrium is in PPAD.
\end{theorem}





\subsection{NP-hardness of Revenue Maximization under Throttling}

To further strengthen our hardness result, next we establish the NP-hardness of computing the revenue-maximizing approximate throttling equilibrium. With revenue being one of the primary concerns of advertising platforms, this result provides further evidence of the computational difficulties which plague throttling equilibria in second-price auctions. We begin by defining the decision version of the revenue-maximization problem.

\begin{definition}[REV]
    Given a throttling game $G$ and target revenue $R$ as input, decide if there exists a $\delta$-approximate throttling equilibrium of $G$, for any $\delta \in [0,1)$, with revenue greater than or equal to $R$.
\end{definition}

Note that we allow for arbitrarily bad approximations to the throttling equilibrium by allowing $\delta$ to be any number in $[0,1)$. Theorem~\ref{thm:revenue_np_hard} states the problem of finding the revenue maximizing approximate throttling equilibrium is NP-hard. Its based on a reduction from 3-SAT to REV and has been relegated to Appendix~\ref{appendix:NP-hard}.
\begin{theorem}\label{thm:revenue_np_hard}
	REV is NP-hard.
\end{theorem}





 




\section{Introduction}

Online ad auctions are the workhorse of the internet advertising industry; when a user visits an internet-based platform, an auction is run among the interested advertisers to determine the ad to be displayed to the user. Due to the large volume of these auctions, many advertisers are budget constrained: if they are allowed to participate in all the auctions they are interested in, they would end up spending more than their budget. This motivates the platforms to offer budget-management services. The focus of this paper is a popular budget-management service known as \emph{throttling} (or alternatively as \emph{probabilistic pacing}) which is offered by internet giants like Facebook~\cite{facebookguide}, Google~\cite{karande2013optimizing} and LinkedIn~\cite{agarwal2014budget}. Throttling manages the expenditure of an advertiser by controlling the probability with which she participates in each individual auction.

The use of participation probability as a control lever allows the platform to evenly spread out an advertiser's expenditure throughout her advertising campaign, while ensuring that she does not spend more than her budget. Furthermore, in contrast to other budget-management methods like multiplicative pacing, throttling does not modify the bids of the advertisers to achieve this, which is essential for advertisers aiming to maintain a stable cost-per-opportunity~\cite{facebookguide}. Additionally, in practice, many advertisers do not opt into budget-management services that modify their bids, forcing the platform to satisfy their budget constraint by only controlling their participation probability, as in throttling~\citep{karande2013optimizing}. Importantly, throttling also gives advertisers a more representative sample of users for which they are eligible and their bid is competitive~\cite{karande2013optimizing}. 
This is in contrast to budget-management approaches that modify bids, such as multiplicative pacing, which biases the allocation towards users where the advertiser has a high probability of getting a click, relative to other advertisers.
Many advertisers place a premium on the predictability and representative samples offered by unmodified bids, motivating the platforms to offer throttling as a budget-management option. 

Throttling has received significant attention in previous work, the vast majority of which studies it from the perspective of a single buyer participating in repeated generalized second-price auctions (see Section~\ref{sec:related-works}). In contrast, the scenario where all of the buyers simultaneously employ throttling to manage their budgets, and the resulting system-level properties, have received very little attention. In this paper, we attempt to remedy this situation by providing a structural and computational analysis of simultaneous multi-buyer throttling for both first-price and second-price auctions. More specifically, we analyze the resulting games, with an emphasis on equilibria and repeated play.

\subsection{Main Contributions}

We define a \emph{throttling game} with budget-constrained buyers (advertisers) and stochastic good types (user types), in which each buyer chooses the probability with which she participates in the auction, with the goal of maximizing her expected utility while satisfying her budget constraint in expectation. Repeated play of this throttling game captures the repeated online ad auction setting in which each buyer employs throttling to manage their budget. Furthermore, we define the concept of \emph{throttling equilibrium} for this game, show its equivalence to pure strategy Nash equilibrium, and analyze it with an emphasis on its structural and computational properties. We summarize our results below.

\textbf{First-price Auctions:} We show that a throttling equilibrium always exists, and characterize it as the maximal element in the set of participation probabilities that result in all buyers satisfying their budgets (Theorem~\ref{thm:existence-first-price}). Furthermore, we use this characterization to establish its uniqueness.  On the computational front, we describe decentralized dynamics in which buyers repeatedly play the throttling game and make simple t\^{a}tonnement-style adjustments to their participation probabilities based on their expected expenditure (Algorithm~\ref{alg:dynamics}). We show that these t\^{a}tonnement-style dynamics converge to an approximate throttling equilibrium in polynomial time (Theorem~\ref{thm:first-price-dynamics}).

\textbf{Second-price Auctions:} We begin by establishing that a throttling equilibrium always exists for second-price auctions (Theorem~\ref{theorem:existence_second_price}), but find that it may not be unique, and for some games all throttling equilibria can be irrational. Next, we prove results about the computational complexity of finding throttling equilibria, which requires the use of terminology from computational complexity theory. Before summarizing those results, we make a note for readers who may not be familiar with complexity theory: In order to make our results more accessible, we provide an informal description of them at the head of every subsection, in an attempt to avoid letting complexity-theoretic terminology obscure the conclusions derived from the result. 
Continuing on with the summary of our results, we prove that the problem of computing approximate throttling equilibria is PPAD-hard even when 
each good has at most three bids, by showing a reduction from the PPAD-hard problem of computing an approximate equilibrium of a threshold game~\citep{PB2021} (Theorem~\ref{thm:second-price-PPAD-hard}). As a consequence, we show that, unlike first-price auctions, no dynamics can converge in polynomial time to a second-price throttling equilibrium (assuming PPAD-complete problems cannot be solved in polynomial time). Furthermore, we place the problem of computing approximate throttling equilibria  in the class PPAD by showing a reduction to the problem of finding a Brouwer fixed point of a Lipschitz mapping from a unit hypercube to itself (Theorem~\ref{thm:second-price-PPAD-membership}); the latter is known to be in PPAD via Sperner's lemma (e.g. see \cite{chen2009settling}). We provide additional evidence of the computational challenges that afflict throttling for second-price auctions by proving the NP-hardness of finding a revenue-maximizing approximate throttling equilibrium (Theorem~\ref{thm:revenue_np_hard}). We complement these hardness results by describing a polynomial-time algorithm for computing throttling equilibria for the special case in which there are at most two bids on each good (Algorithm~\ref{alg:two_buyer}), thereby precisely delineating the boundary of tractability.

\textbf{Comparing Pacing and Throttling:} As mentioned earlier, multiplicative pacing is another popular method of budget management, where buyers shade their bids to smoothly spend their budgets. In contrast to throttling, equilibria and dynamics in settings where all of the buyers use pacing have received significant attention~\cite{borgs2007dynamics, balseiro2015repeated, conitzer2018multiplicative, conitzer2019pacing, chen2021complexity}. This allows us to compare two of the most popular methods of budget management~\cite{informsarticle}. We show that, for first-price auctions, the revenue of the unique throttling equilibrium and the unique pacing equilibrium, although incomparable directly, are always within a factor of 2 of each other (Theorem~\ref{thm:revenue-comparison}). Moreover, we find that pacing and throttling equilibria share a remarkably similar computational and structural landscape, as summarized in Table~\ref{table:first_price} and Table~\ref{table:second_price}. In view of this comparison, our work can be seen as providing the analogous set of results for throttling equilibria that \cite{borgs2007dynamics, conitzer2018multiplicative, conitzer2019pacing, chen2021complexity} proved for pacing equilibria. Our results reaffirm what the analysis of pacing suggested: budget management for first-price auctions is more efficient as compared to second-price auctions. 


\begin{table}[H]
\scriptsize
\centering
\begin{tabular}{llllll}
                                & Existence                   & Rationality			&Multiplicity                     & Computational Complexity                        & Efficient Dynamics                              \\ 
\cline{2-6}
\multicolumn{1}{l|}{Throttling} & \multicolumn{1}{l|}{Always} & \multicolumn{1}{l|}{Not always} & \multicolumn{1}{l|}{Always unique} & \multicolumn{1}{l|}{Poly.-time for approx. eq.} & \multicolumn{1}{l|}{For approx. eq.}  \\ 
\cline{2-6}
\multicolumn{1}{l|}{Pacing}     & \multicolumn{1}{l|}{Always~\cite{conitzer2019pacing}} & \multicolumn{1}{l|}{Always~\cite{conitzer2019pacing}}  & \multicolumn{1}{l|}{Always unique~\cite{conitzer2019pacing}}   & \multicolumn{1}{l|}{Poly.-time for exact eq. ~\cite{conitzer2019pacing}}   & \multicolumn{1}{l|}{For approx. eq.~\cite{borgs2007dynamics}}  \\ 
\cline{2-6}
                                &                             &                                 &                                                 &                                       \\
                                &                             &                                 &                                                 &                                      
\end{tabular}\vspace{-0.5cm}
\caption{Comparison of throttling and pacing equilibria for \textbf{first-price} auctions.}
\label{table:first_price}
\end{table}



\begin{table}[H]
\scriptsize
\centering
\begin{tabular}{lllllll}
                                & Existence                   & Rationality                     & Multiplicity                  & Computational Complexity                                                                                   & Revenue Max.                 & Dynamics                            \\ 
\cline{2-7}
\multicolumn{1}{l|}{Throttling} & \multicolumn{1}{l|}{Always} & \multicolumn{1}{l|}{Not always} & \multicolumn{1}{l|}{Possible} & \multicolumn{1}{l|}{PPAD-complete for approx. eq.}                                                         & \multicolumn{1}{l|}{NP-hard} & \multicolumn{1}{l|}{Not efficient}  \\ 
\cline{2-7}
\multicolumn{1}{l|}{Pacing}     & \multicolumn{1}{l|}{Always~\cite{conitzer2018multiplicative}} & \multicolumn{1}{l|}{Always~\cite{chen2021complexity}}     & \multicolumn{1}{l|}{Possible~\cite{conitzer2018multiplicative}} & \multicolumn{1}{l|}{\begin{tabular}[c]{@{}l@{}}PPAD-complete for both exact\\and approx. eq.~\cite{chen2021complexity}\end{tabular}} & \multicolumn{1}{l|}{NP-hard~\cite{conitzer2018multiplicative}} & \multicolumn{1}{l|}{Not efficient~\cite{chen2021complexity}}  \\ 
\cline{2-7}
                                &                             &                                 &                               &                                                                                                            &                              &                                     \\
                                &                             &                                 &                               &                                                                                                            &                              &                                    
\end{tabular}\vspace{-0.5cm}
\caption{Comparison of throttling and pacing equilibria for \textbf{second-price} auctions.
\label{table:second_price}
\end{table}


\normalsize


\subsection{Additional Related Work}\label{sec:related-works}

Budget management in online ad auctions has received widespread attention in the literature. Here, we review the papers which most closely relate to ours. We begin by reviewing the work on throttling, then give a broad overview of the other models for bidding under budget constraints considered in the literature, and finally conclude with a discussion of the work on multiplicative pacing, which we use in our comparisons.

Among work on throttling,
\cite{balseiro2021budget} is the closest to ours, and acts as the inspiration for our model and terminology. In \cite{balseiro2021budget}, the authors study system equilibria under various budget management strategies in second-price auctions, one of them being throttling. They show that throttling satisfies desirable incentive properties, and, under the special case when buyer values are symmetric, they compare equilibrium seller revenue and total welfare for throttling to a variety of other budget management techniques. Crucially, unlike our work, \cite{balseiro2021budget} lacks a computational analysis and focuses solely on second-price auctions. Throttling has also received significant attention in other lines of research. \cite{agarwal2014budget} study throttling in generalized second-price (GSP) auctions from the perspective of a single buyer, provide an algorithm which determines the participation probability based on user traffic forecasts, and analyze its performance empirically on real data from LinkedIn. Similarly, \cite{xu2015smart} provide and empirically evaluate practical algorithms for throttling on data from demand-side platforms. \cite{karande2013optimizing} use throttling (under the name Vanilla Probabilistic Throttling) as the benchmark in the GSP auction setting to evaluate the budget management algorithm they describe on data from Google, and find that it empirically outperforms throttling on the metrics they study. Importantly, they do not engage in an equilibrium analysis, and their algorithm does not provide a representative sample of the traffic to advertisers.

There is also a significant body of work which proposes alternatives to pacing and throttling methods.
\cite{charles2013budget} study regret-free budget-smoothing policies in which the platform selects the random subset of buyers that participate in the GSP auction for each good. They show that such policies always exist, and, under the small-bids assumption, give an efficient algorithm for the special case of second-price auctions. 
There is also a significant body of work that models budget management in first-price auctions as an allocation problem under stochastic and adversarial input, starting with the work of \cite{mehta2007adwords}. See \cite{mehta2013online} for a survey.
We emphasize that in this work, our goal is to study the budget-management mechanisms that are employed in practice, which is why we focus on comparing pacing and throttling.

Unlike throttling, equilibrium analysis for the setting where all buyers simultaneously use multiplicative pacing is well-understood. \cite{conitzer2018multiplicative} define and study pacing equilibria in second-price auctions. They show that it always exists and study its structural properties. \cite{chen2021complexity} recently analyzed the computational complexity of finding pacing equilibria in second-price auctions, and proved that the problem is PPAD-complete. For first-price auctions, \cite{borgs2007dynamics} describe a simple t\^{a}tonnement-style dynamics and prove its efficient convergence to a pacing equilibrium. \cite{conitzer2019pacing} characterize the structural properties of pacing equilibria in first-price auctions and give a market-equilibrium based algorithm for computing it. A summary of these results can be found in the second row of Table~\ref{table:first_price} and Table~\ref{table:second_price}.


\section{Other stuff to think about}










{
\small
\bibliographystyle{plainnat}

\section{Model}

Consider a seller who has $m$ types of goods to sell, and $n$ budget constrained buyers who are interested in buying these goods. The seller runs an auction amongst the buyers in order to make the sale. We assume that the type of good to be sold is drawn from some known distribution $d = (d_1, \dots, d_m)$, i.e., the good to be sold is of type $j$ with probability $d_j$. Buyer $i$ bids $\tilde{b}_{ij}$ on good type $j$, for all $i \in [n], j \in [m]$, and has a per-auction budget of $B_i > 0$. 
To control their budget expenditure, each buyer $i$ is associated with a \emph{throttling parameter} $\theta_i \in [0,1]$, which represents the probability with which she participates in the auction: each buyer $i$ independently flips a biased coin which comes up heads with probability $\theta_i$, and submits their bid $\tilde{b}_{ij}$ if the coin comes up heads, while submitting no bid if the coin comes up tails. 

We focus on the setting where each buyer wishes to satisfy her budget constraint in expectation, i.e., buyer $i$ would like to spend less than $B_i$ in expectation over the good types and participation coin flips of all buyers. Requiring the budget constraints to be satisfied in expectation draws its motivation from the large number of auctions that are run by online-advertising platforms, in conjunction with concentration arguments, and has been employed by previous works on budget management in online auctions (see, e.g.,~\cite{gummadi2012repeated,abhishek2013optimal,balseiro2015repeated,balseiro2017budget,balseiro2019learning,conitzer2018multiplicative}). Additionally, in this paper, we restrict our attention to the two most commonly-used auction formats in online advertising: first-price auctions and second-price auctions. In a first-price auction, the participating buyer with the highest bid wins the good and pays her bid, whereas in a second-price auction, the participating buyer with the highest bid wins the good and pays the second-highest bid among the participating buyers. Our model  can be interpreted as a discrete version of the one defined in \cite{balseiro2021budget}.

Before proceeding further, we introduce some additional notation that allows us to capture the
stochastic nature of the good types via a rescaling of the bids, thereby allowing us to analyze the setting as a deterministic multi-good auction problem:
Set $b_{ij} \coloneqq d_j \tilde{b}_{ij}$ for all $i \in [n], j \in [m]$. Since the participation of buyers is independent of the good type and we are only concerned with expected payments, the good type distribution $d = (d_j)_j$ and the bids $\{\tilde{b}_{ij}\}_{i,j}$ are consequential only insofar as they determine $\{b_{ij}\}_{i,j}$. Therefore, with some abuse of terminology, going forward, we refer to $b_{ij}$ as the bid of buyer $i$ on good $j$ (instead of $\tilde{b}_{ij}$, which will no longer be used).\footnote{This deterministic view is equivalent to the  model of \citet{conitzer2018multiplicative}, except that we focus on probabilistic throttling for managing budgets, whereas they focus on multiplicative pacing. Their model can similarly be viewed as a stochastic setting.}
Furthermore, to simplify our analysis, we will assume that ties are broken lexicographically, i.e., the smaller buyer number wins in case of a tie. Our results continue to hold for all other tie-breaking priority orders over the buyers (even when they are different for each good). The lexicographic tie-breaking rule allows for simplified notation, albeit with some abuse: We will write $b_{ij} > b_{kj}$ to mean that either $b_{ij}$ is strictly greater than $b_{kj}$, or $b_{ij} = b_{kj}$ and $i<k$. Finally, we refer to any tuple $\left(n, m, (b_{ij}), (B_i)\right)$
as a \emph{throttling game}. 

In online-advertising auctions, the buyers (or, more typically in practice, the platform on behalf of the buyers) attempt to satisfy their budget constraints by adjusting their throttling parameters. This naturally leads to a game where each buyer's strategy is her throttling parameter. We use $p(\theta)_{ij}$ to denote the expected payment of buyer $i$ on good $j$ when buyers use $\theta = (\theta_1, \dots, \theta_n)$ to decide their participation probabilities. Let $X_i$ be a random variable such that $X_i = 1$ if buyer $i$ participates and $X_i = 0$ if buyer $i$ does not participate. Then, by our modeling assumptions, $X_i$ is a Bernoulli$(\theta_i)$ random variable. More concretely, $p(\theta)_{ij}$ can be defined as follows:
\begin{itemize}
	\item First-price auction: $p(\theta)_{ij} = \mathbb{E} \left[X_i b_{ij} \prod_{k: b_{kj} > b_{ij}} (1 - X_k)  \right] = \theta_i b_{ij} \prod_{k: b_{kj} > b_{ij}} (1 - \theta_k)$
	\item Second-price auction:
	\begin{align*}
	    p(\theta)_{ij} &= \mathbb{E} \left[ \sum_{\ell: b_{\ell j} < b_{ij}}  b_{\ell j} X_i  X_\ell  \prod_{k \neq i: b_{kj} > b_{\ell j}} (1 - X_k) \right] 
	     = \sum_{\ell: b_{\ell j} < b_{ij}}  b_{\ell j} \theta_i  \theta_\ell  \prod_{k \neq i: b_{kj} > b_{\ell j}} (1 - \theta_k)
	\end{align*}
\end{itemize}

We overload $p(\theta)_{ij}$ to represent the expected payment in both auction formats; the auction format will be clear from the context. Next, we define the equilibrium concept which will be the main object of study in this work.

\begin{definition}[Throttling Equilibrium]\label{def:exact_throt_eq}
	Given a throttling game $\left(n, m, (b_{ij}), (B_i)\right)$, a vector of throttling parameters $\theta = (\theta_1, \dots, \theta_n) \in [0,1]^n$ is called an $\delta$-approximate throttling equilibrium if:
    \begin{enumerate}
        \item Budget constraints are satisfied: $\sum_j p(\theta)_{ij} \leq B_i$ for all $i \in [n]$
        \item No unnecessary throttling occurs: If $\sum_j p(\theta)_{ij} < B_i$, then $\theta_i = 1$
    \end{enumerate}
\end{definition}

The above definition applies to both first-price and second-price auctions using the corresponding payment rule $p(\theta)_{ij}$. Definition~\ref{def:exact_throt_eq} draws its motivation from the fact that, in a natural utility model, throttling equilibria are essentially equivalent to pure Nash Equilibria, which we describe next. Consider a throttling game $\left(n, m, (b_{ij}), (B_i)\right)$. Fix an auction format: either first-price or second-price. Suppose buyer $i$ has value $v_{ij}$ for good type $j$ for all $i \in [n], j \in [m]$. We make the natural assumption that the buyers bid less than their value, i.e., $d_i v_{ij} \geq b_{ij}$ for all $i \in [n], j \in [m]$ in second-price auctions and strictly less than their value, i.e., $d_i v_{ij} > b_{ij}$ for all $i \in [n], j \in [m]$ in first-price auctions. Define a new game $G$ in which each buyer $i$'s strategy is her throttling parameter $\theta_i$ and her utility function is given by 
\begin{align*}
	u_i(\theta) = \begin{cases}
		\sum_j \left(v_{ij} d_i  \theta_i \prod_{k: b_{kj} > b_{ij}} (1 - \theta_k)  - p(\theta)_{ij} \right) & \text{if } \sum_j p(\theta)_{ij} \leq B_i\\
		-\infty &\text{otherwise}
	\end{cases}	
\end{align*}
This utility is simply the expected quasi-linear utility modified to ascribe a utility value of negative infinity for budget violations. Since all of the buyers get a non-negative utility from winning any good, increasing the throttling parameter improves utility so long as the budget constraint is satisfied. This makes it easy to see that every throttling equilibrium of the throttling game $\left(n, m, (b_{ij}), (B_i)\right)$ is a Nash equilibrium of the corresponding game $G$. Furthermore, it is also straightforward to check that a pure Nash equilibrium of $G$ is not a throttling equilibrium only in the following scenario: There is a buyer who spends 0 in the Nash equilibrium and has a throttling parameter strictly less than 1. In this scenario, setting the throttling parameter of all such buyers to 1 yields a throttling equilibrium with exactly the same expected allocation and payment for all the buyers as under the Nash equilibrium. Hence, given a throttling game $\left(n, m, (b_{ij}), (B_i)\right)$, for every pure Nash equilibrium of the corresponding game $G$, there is a throttling equilibrium with the same expected allocation and revenue.

We conclude this section by defining an approximate version of throttling equilibrium, which allows us to side-step issues of irrationality that can plague exact equilibria (see Example~\ref{example:first-price-irrational} and Example~\ref{example:irrational_eq}).

\begin{definition}[Approximate Throttling Equilibrium]\label{def:throt_eq}
    Given a throttling game $\left(n, m, (b_{ij}), (B_i)\right)$, a vector of throttling parameters $\theta = (\theta_1, \dots, \theta_n)$ is called an $\delta$-approximate throttling equilibrium if:
    \begin{enumerate}
        \item Budget constraints are satisfied: $\sum_j p(\theta)_{ij} \leq B_i$ for all $i \in [n]$
        \item Not too much unnecessary throttling occurs: If $\sum_j p(\theta)_{ij} < (1- \delta) B_i$, then $\theta_i \geq 1- \delta$
    \end{enumerate}
\end{definition}
\subsection{An Algorithm for Second-Price Throttling Equilibria with Two Buyers Per Good}

Next, we contrast the hardness results of the previous subsection with an algorithm for the case when each good receives at most two non-zero bids. Since goods with only one positive bid never result in a payment, without loss of generality, we can assume that every good has exactly two buyers with positive bids. More precisely, in this subsection, we will assume that $|\{i \in [n] \mid b_{ij}>0\}| = 2$ for all $j \in [m]$. This special case demarcates the boundary of tractability for computing throttling equilibria in second-price auctions: Our PPAD-hardness result (Theorem~\ref{thm:second-price-PPAD-hard}) holds for the slightly more general case of each good receiving at most three positive bids. We begin by describing the algorithm (Algorithm~\ref{alg:two_buyer}).

\begin{algorithm}[H] 
   \caption{Algorithm for the Two Buyer Case}
   \label{alg:two_buyer}
  
    \begin{algorithmic}\vspace{0.08cm}
            \item[\textbf{Input:}] Throttling game $\left(n, m, (b_{ij}), (B_i)\right)$ and parameter $\gamma > 0$
            \item[\textbf{Initialize:}] $\theta_i = \min\{B_i/ (2\sum_j b_{ij}), 1\}$ for all $i \in [n]$
            \item[\textbf{While}] there exists a buyer $i \in [n]$
            such that $\theta_i < 1 - \gamma$ and $\sum_j p(\theta)_{ij} < (1 - \gamma)^3 B_i$:
            \begin{enumerate}
                \item For all $i \in [n]$ such that $\theta_i < 1 - \gamma$ and $\sum_j p(\theta)_{ij} < (1 - \gamma)^2 B_i$, set $\theta_i \leftarrow \theta_i/(1 - \gamma)$
                \item For all $i \in [n]$ such that $\sum_j p(\theta)_{ij} > B_i$, set $\theta_i \leftarrow (1 - \gamma)\theta_i$ \vspace{0.1cm}  
            \end{enumerate}
            \item[\textbf{Return:}] $\theta$
    \end{algorithmic}
 \end{algorithm

The following theorem, whose proof can be found in Appendix~\ref{appendix:two-buyer}, establishes the correctness and polynomial runtime of Algorithm~\ref{alg:two_buyer}.

\begin{theorem}\label{thm:two-buyer}
    Algorithm~\ref{alg:two_buyer} returns a $(1 - 3 \gamma)$-approximate throttling equilibrium in time which is polynomial in the size of the instance and $1/\gamma$.
\end{theorem}

