The Complexity of Pacing for Second-Price Auctions

Introduction

Online auctions are a mainstay of the Internet advertising industry. Whenever a user visits a webpage or searches for a keyword, interested advertisers participate in an auction to win the opportunity to promote their content to the user. Advertisers typically participate in thousands of these online ad auctions every day and are often budget constrained, which makes budget management a crucial component of online advertising. This paper is concerned with a specific method of budget management in auctions: pacing (also known as multiplicative pacing), which has found use at platforms such as Facebook, where pacing is routinely employed as one of the ways to manage budgets on behalf of advertisers.https://www.facebook.com/business/help/1754368491258883?id=561906377587030

Pacing involves multiplicatively scaling down bids of advertisers in order to ensure a smooth depletion of their budgets over the entire advertising campaign, which is comprised of a large number of individual auctions. Consider the setting in which a group of buyers (advertisers) participate in a series of independent second-price auctions for a collection of items (the opportunity to display an ad to a user). If all buyers bid their valuesBidding your value is a dominant strategy in second price auctions without budgets. in every auction, they might all deplete their budgets before the last auction. As a remedy, pacing associates a pacing multiplier to each buyer, which lies between zero and one, such that each buyer bids her value scaled down by her pacing multiplier. The pacing multiplier is strictly smaller than one only if the buyer would deplete her budget by bidding her true value in each auction.

Pacing has the desirable property that, if we fix the bids of competing buyers, then pacing allows a buyer to win the items which provide the best return on investment (ratio of value to price) subject to her budget constraint. In a recent work, Balseiro and Gur (2019) exploit this property to prove the optimality of pacing for budget management: For a budget-constrained buyer who repeatedly participates in second-price auctions for which her values are drawn i.i.d. from some distribution, the optimal bidding strategy is to use pacing, both when the bids of the adversary are stochastic or adverserial. In other words, when considering the problem of bidding under budget constraints from the perspective of a single buyer, pacing is provably the best strategy to use.

In this paper, we study the situation where every buyer uses pacing to attempt to bid optimally in second-price auctions. We prove that, unfortunately, if every buyer tries to bid optimally through pacing, then the resulting dynamics are not likely to converge efficiently to an equilibrium. We do so by investigating the computational complexity of finding an equilibrium of the game in which each buyer’s strategy involves selecting a pacing multiplier, called a second-price pacing game. The natural notion of equilibrium in this game is the pacing equilibrium (see Definition 1), which was introduced and shown to always exist by Conitzer et al. (2021). The authors of Conitzer et al. (2021) also studied the computation of pacing equilibria by developing mixed-integer programming methods and applied them to real-world auction data, but found them plagued with poor scalability. They went on to conjecture that computing a pacing equilibrium could be PPAD-complete.While we cite the 2021 journal version of that paper, the conjecture was made first in the 2017 arXiv version of that paper. It was also published in their 2018 conference version of the paper, which appeared at the Conference on Web and Internet Economics (WINE) that year.

Our paper resolves this open problem: it is indeed a PPAD-complete problem, and this holds for a broad class of approximate versions of the problem as well. This provides mathematical support for the repeatedly observed empirical fact that pacing-based bidding strategies often do not converge quickly, and the resulting equilibria seem hard to compute. These two facts are evidenced by the lack of efficient dynamics and efficient algorithms for computing equilibria, despite the significant attention pacing has received for more than a decade (see Section 1.4). Through our result, we show that multi-buyer pacing is fundamentally intractable and this lack of efficient dynamics/algorithms is likely here to stay. Before delving deeper, we provide a short primer on PPAD for those unfamiliar with it. This can be safely skipped by any reader already familiar with the topic.

Like the well-known complexity class NP, PPAD (Polynomial Parity Argument in a Directed graph, introduced by Papadimitriou (1994)) is a collection of computational problems. As with the definition of NP-hardness and NP-completeness, a problem is said to be PPAD-hard if it is at least as hard as every problem in PPAD; a problem is said to be PPAD-complete if it is contained in PPAD and is PPAD-hard. The analogy to NP extends further: the PPAD-hardness of a problem can be established by providing a polynomial-time reduction from a problem already known to be PPAD-hard. One of the quintessential PPAD-complete problems, and the one we will employ in our reductions, is that of computing a Nash equilibrium of a bimatrix game (Daskalakis et al., 2009; Chen and Deng, 2006). The Nash equilibrium problem has been studied extensively for decades and yet, despite much effort, no polynomial-time algorithm is known for it. Moreover, a recent spate of results showed that it is hard to solve, assuming certain strong cryptographic assumptions (Bitansky et al., 2015; Garg et al., 2016; Rosen et al., 2017; Hubacek and Yogev, 2017; Choudhuri et al., 2019). This has motivated the conjecture that PPAD-hard problems cannot be solved efficiently. In this paper, we show that the problem of finding a pacing equilibrium is PPAD-hard. This shows that computing a pacing equilibrium is hard, unless all problems in PPAD can be solved efficiently.

On the other hand, showing that a problem is in PPAD amounts to giving a polynomial-time reduction to a problem in PPAD. For this purpose we will avail ourselves of the fact that the algorithmic version of Sperner’s lemma is known to be in PPAD (Papadimitriou, 1994; Chen and Deng, 2009), and reduce the problem of finding a pacing equilibrium to it. We refer the interested reader to Goldberg (2011) and Chapter 4 of Roughgarden (2020) for a survey of PPAD and its complete problems.

We first prove that finding a pacing equilibrium is in PPAD. In particular, this implies that, when values and budgets of buyers are rational in the game, there always exists a pacing equilibrium in which every entry is rational and can be written using polynomially many bits. (In contrast, the existence proof of Conitzer et al. (2021) uses a convergence argument, from which it is not clear whether an equilibrium with rational entries always exists.)

Finding a pacing equilibrium in a second-price pacing game is in PPAD.

Next we show that the problem of finding an approximate pacing equilibrium is PPAD-hard. Our notion of approximation relaxes the definition of (exact) pacing equilibria in two ways: (i) buyers who bid close to (but not necessarily exactly equal to) the highest bid may also win fractions of an item; (ii) each buyer either spends most of her budget, or her pacing multiplier is close to one. We use two parameters $\delta$ and $\gamma$ to capture these two relaxations quantitatively and such a solution is called a $(\delta,\gamma)$-approximate pacing equilibrium (see Definition 2).

For any constant $c>0$, finding a $(\delta,\gamma)$-approximate pacing equilibrium in a second-price pacing game with $n$ players is PPAD-hard when $\delta=\gamma=1/n^{c}$.

Note that, by virtue of being a relaxation, finding an approximate pacing equilibrium is in PPAD as a direct consequence of Theorem 1. Similarly, the PPAD-hardness of finding an exact pacing equilibrium follows from Theorem 2. Therefore, both problems of finding an exact and an approximate pacing equilibrium are complete in PPAD. To the best of our knowledge, our results are the first PPAD-completeness results for budget-management in second-price auction systems such as those applied in large-scale Internet advertising.

Implications. Our hardness result has implications for Borgs et al. (2007), in which the authors studied dynamic first-price and second-price auctions with budgets. They proved that pacing combined with perturbations can lead to efficient convergence of bidding dynamics under first-price auctions. They conjectured a similar convergence in the analogous second-price setting and provided experimental support for it. Our definition of approximate pacing equilibria (Definition 2) is able to capture their random-perturbation model, thereby bringing it under the purview of our hardness result Theorem 2: if such a convergence occurs in the second-price case, then it must do so inefficiently assuming PPAD does not have polynomial-time algorithms (see Subsection 3.2). Moreover, since our model also admits a stochastic interpretation, if all of the buyers employ some pacing algorithm for repeated second-price auctions with correlated value distributions and global budget constraints, then the resulting dynamics will not always converge efficiently to an equilibrium, assuming PPAD does not have polynomial-time algorithms. In particular, this statement applies to the pacing algorithm given by Balseiro and Gur (2019), which is an optimal bidding algorithm for a single budget-constrained buyer under both adversarial and independent-stochastic competition. Informally, the central message here is that, when multiple budget-constrained buyers bid in a way that is optimal for them individually, the resulting dynamics will not in general stabilize to an equilibrium.

Furthermore, due to connections between pacing equilibria and supply-aware market equilibria Conitzer et al. (2021) with linear utilities, our PPAD-hardness result has novel consequences when interpreted in the language of market equilibria: our result shows that a natural refinement of supply-aware market equilibria with linear utilities is PPAD-hard (finding one with prices corresponding to second-price auctions).

2 Techniques Used

We prove the PPAD-hardness of finding approximate pacing equilibria (Theorem 2) by giving a reduction from the problem of finding an $\epsilon$-well-supported Nash equilibrium in win-lose bimatrix games. The second-price rule plays an important role in this reduction. Consider an item with two interested buyers, one of which has a much higher value than the other, so much so that she always wins the good in any pacing equilibrium. Then, the payment made by this buyer on this item is determined by the bid of the lower-valued buyer, which is equal to her value times her multiplier. This allows us to construct gadgets which capture Nash equilibria of any bimatrix game with pacing multipliers, by using the second-price rule to account for the expected cost of each action of a player with respect to the other player’s mixed strategy. A complicating factor in our proof is that pacing multipliers are always positive, whereas some actions are played with probability zero in a Nash equilibrium. To address this issue, we construct our gadgets such that they have a discontinuous behavior: there is a baseline pacing amount which corresponds to playing the corresponding action with probability zero, and only larger pacing values correspond to probabilities.

To prove the PPAD-membership of finding a pacing equilibrium (Theorem 1), we reduce the problem to the algorithmic version of Sperner’s Lemma. A direct reduction proves challenging due to the discontinuous way in which the allocation of an item varies with pacing multipliers: In a pacing equilibrium, an item can only be assigned to buyers whose bids are exactly equal to the highest bid. Similar issues were encountered in PPAD-membership proofs for market equilibrium computation Vazirani and Yannakakis (2011b). For this reason, we start by proving the PPAD-membership of finding approximate pacing equilibria, in which items can be allocated smoothly. Then we bootstrap this result to show the PPAD-membership of exact pacing equilibrium in two steps. The first step starts with an approximate pacing equilibrium and rounds it to obtain a pacing equilibrium in which only buyers tied for the highest bid on a good share it. We still allow the relaxation that each buyer can either spend most of her budget or set her pacing multiplier close to one. Finally, we do away with this remaining relaxation by using a LP-based technique similar to the one used in Etessami and Yannakakis (2010); Vazirani and Yannakakis (2011b) and Filos-Ratsikas et al. (2020), thereby showing the PPAD-membership of finding an exact pacing equilibrium.

3 Pacing in Internet Advertising

To motivate pacing equilibrium as a solution concept, this section describes how the solution concept arises in practice as part of internet advertising platforms such as those operated by e.g. Facebook, Google, or Twitter. As discussed previously, pacing equilibrium may arise through individual buyers optimizing their spending due to their budget constraint. A second reason that pacing equilibrium is of practical interest is due to proxy bidders. When an advertiser starts a campaign, they often specify only a small set of parameters: their value for a click (or some other notion of converting an ad into value, say a video view), their budget, and their targeting criteria which specify the subset of users they are interested in (e.g. “people who surf” if the ad is for surfboards). Then, whenever an auction is run to determine which ads to show to a given user, the bid from a given advertiser is submitted by the proxy bidder acting on behalf of that advertiser. The proxy bidder calculates the value that advertiser $i$ has for being shown to the user in auction $j$ as $v_{ij}=v_{i}\cdot CTR_{ij}$, where $v_{i}$ is the value per click and $CTR_{ij}$ is the estimated probability that the user will click on the ad. If there were no budgets, then the proxy bidder should submit the bid $v_{ij}$, due to the truthfulness of the second-price auction. But in the presence of budgets, this may negatively affect the overall utility achieved by the advertiser, since they will run out of budget well before the campaign ends, and thus miss out on later strong bang-per-buck opportunities.

To address their budget constraints, the advertisers are typically offered one or more options for budget-management strategies that can be employed by the proxy bidders. Pacing as defined in this paper, via multiplicative bid scaling, is offered by Facebook by default (Conitzer et al., 2021; Facebook, 2017), and it is also offered on other platforms. Intuitively speaking, the proxy bidder attempts to choose a pacing multiplier which will spend the advertiser’s budget evenly across the campaign length. To ensure that this will happen, the pacing multiplier is adapted over time using a control algorithm: the algorithm will adjust the pacing multiplier up or down depending on whether the proxy bidder is currently under or overspending. Since we do not consider the online aspect of the problem, the pacing equilibrium solution concept that we study corresponds to the steady-state that this adaptive process would ideally arrive at (this is analogous to what was done by Conitzer et al. (2021); Balseiro et al. (2015, 2017)). See Conitzer et al. (2021) for a longer discussion of the pacing equilibrium model and how it relates to real-world systems.

4 Additional Related Work

There is a large literature on budgets in auctions, largely inspired by the Internet advertising industry. Here we survey the ones most related to our paper. We start by surveying the literature on multi-item first or second-price auctions with budgets and the associated equilibrium issues there, since that is the setting we study. We briefly mention some pointers to alternative approaches and models such as mechanism design or online matching.

Balseiro et al. (2015) studied budget management in second-price auctions using a fluid mean-field model, and showed that in this model existence is guaranteed, and closed-form solutions for equilibria are derived for certain settings. Balseiro et al. (2017) studied several different pacing mechanisms for second-price auctions, including multiplicative pacing, and showed existence results for their setting, as well as other analytical and numerical properties. Conitzer et al. (2019) studied the model of Conitzer et al. (2021), but with each auction using a first-price rule. There, pacing equilibrium no longer constitutes best responses, but instead has a market equilibrium interpretation. In the first-price setting, pacing equilibria turn out to be easy to compute, due to a direct relationship to market equilibria. Babaioff et al. (2020) studied non-quasi-linear agents participating in mechanisms designed for quasi-linear agents. They studied a generalization of budget constraints where agents have a concave disutility in payment, and showed that a Nash equilibria exists which employs multiplicative scaling. Since pacing equilibrium is a special case of Nash equilibrium in the more general buyer utility model studied in Babaioff et al. (2020), our hardness results extend to their setting. Balseiro and Gur (2019) developed online learning methods for individual agents adapting their pacing multipliers over time, and showed that this converges to an equilibrium under certain stochastic independence assumptions. Assuming PPAD $\neq$ P, our results can be interpreted to mean that, in the general setting which allows for correlation and discrete valuations, no dynamics can converge efficiently in the worst case (see Proposition 10 of Conitzer et al. (2021) for a formal statement connecting the stochastic and deterministic settings).

An alternative approach for handling budget constraints in multi-item settings is to design a mechanism that accounts for this explicitly, see e.g. Ashlagi et al. (2010); Goel et al. (2015); Dobzinski et al. (2012); Dobzinski and Leme (2014). Another approach to budget-constrained allocation in online advertising is to treat the problem as an online matching problem. This research was initiated by Mehta et al. (2007), see e.g. Mehta (2013) for a survey.

Our results are strongly related to the problem of computing market equilibria under a supply-aware model (see Subsection 3.2 for a discussion). There have been several PPAD-completeness results for various Fisher market models (without supply-awareness). However, these results are all for models with more complex utility functions, which give rise to the hardness. Chen and Teng (2009) and Vazirani and Yannakakis (2011a) showed that for additively-separable piecewise-linear concave utilities, finding an equilibrium in a Fisher market is PPAD-complete. Bei et al. (2016) showed PPAD-hardness of finding market equilibria with budget-capped utilities (this is proved using a variation on the piecewise-linear utilities proof of Chen and Teng (2009)). In the case of indivisible goods, Othman et al. (2016) showed that finding an approximate market equilibrium is hard, even one which is guaranteed to exist Budish (2011). For the Arrow-Debreu exchange economy, Chen et al. (2017) showed that finding an equilibrium is PPAD-hard.

Finally, in additional to Nash equilibrium and market equilibrium, many interesting problems have been proven to be PPAD complete in domains like auctions (Filos-Ratsikas et al., 2021; Chen et al., 2021), fair division (Deng et al., 2012; Filos-Ratsikas et al., 2020) and optimization (Fearnley et al., 2021).

Model

We start with the definition of Second-price Pacing Games. In a Second-price Pacing Game (SPP game as a shorthand) $G=(n,m,(v_{ij}),(B_{i}))$, there are $n$ buyers and $m$ (indivisible) goods. Each good is sold through independent (single slot) second-price auctions. We use $v_{ij}\geq 0$, $i\in[n]$ and $j\in[m]$, to denote the value of good $j$ to buyer $i$, and $B_{i}>0$ to denote the budget of buyer $i$. We will require (1) for each $j\in[m]$, $v_{ij}>0$ for some $i\in[n]$, and (2) for each $i\in[n]$, $v_{ij}>0$ for some $j\in[m]$. Each buyer $i$ plays the game by picking a pacing multiplier $\alpha_{i}\in$ and then bidding $\alpha_{i}v_{ij}$ on good $j$ for each $j\in[m]$.

To finish describing the game, one approach is to specify a tie-breaking rule: a rule that determines the probabilities with which a good is allocated among the highest bidders. However, Conitzer et al. (2021) showed that the choice of tie-breaking rule affects equilibrium existence. This motivated them to introduce an equilibrium notion called the pacing equilibrium, which is not concerned with any specific tie-breaking rule, but instead includes the probability distribution used to allocate each good as part of the equilibrium (see Definition 1). We will take a similar approach and work with pacing equilibrium, focusing on its computational aspects. It is worth pointing out that this only makes our hardness results stronger because they apply to any tie-breaking rule (such as the one used by Borgs et al. (2007), which works via random perturbations; see Section 3.3 for a detailed discussion of the implications of our hardness results).

With slight abuse of notation, we will write $x_{ij}\geq 0$ to denote the fraction of good $j$ allocated to buyer $i$, which, in our indivisible goods regime, should be interpreted to mean the probability of allocating good $j$ to buyer $i$. Therefore, the allocation should always satisfy $\sum_{i\in[n]}x_{ij}\leq 1$ for all $j\in[m]$. In addition, only buyers $i$ with the highest bid for good $j$ can have $x_{ij}>0$ and they pay for good $j$ under the second-price rule.

Formally, when the buyers use pacing multipliers $\alpha=(\alpha_{1},\dots,\alpha_{n})$, we let $h_{j}(\alpha)=\max_{i\in[n]}\alpha_{i}v_{ij}$ denote the highest bid on good $j$ and $p_{j}(\alpha)$ denote the second highest bid on good $j$, i.e., $p_{j}(\alpha)$ is the second largest element among $\alpha_{1}v_{1j},\dots,\alpha_{n}v_{nj}$ (in particular, $p_{j}(\alpha)=h_{j}(\alpha)$ when there is a tie for the highest bid). Only buyers who bid $h_{j}(\alpha)$ can purchase (fractions of) good $j$ under the price $p_{j}(\alpha)$. Thus, under an allocation $x=(x_{ij})$, the total payment of buyer $i$ is given by $\sum_{j\in[m]}x_{ij}p_{j}(\alpha)$, which should not exceed the budget $B_{i}$ of buyer $i$.

Next, we define the notion of pacing equilibria Conitzer et al. (2021) of SPP games. A pacing equilibrium consists of a tuple of pacing multipliers $\alpha=(\alpha_{i})$ and an allocation $x=(x_{ij})$ of goods that satisfy the two conditions described above (i.e., only buyers with the highest bid can be allocated a good and their budgets are satisfied, as captured in (a) and (c) below). In addition, we require (b) the full allocation of any good with a positive bid and (d) that there is no unnecessary pacing: if a buyer $i$ does not spend her whole budget, then her pacing multiplier should be one. Intuitively, this makes sense because if her budget is not binding, then she should participate as if each auction is a regular second-price auction.

Given an SPP game $G=(n,m,(v_{ij}),(B_{i}))$, we say $(\alpha,x)$ with $\alpha=(\alpha_{i})\in^{n}$, $x=(x_{ij})\in^{nm}$ and $\sum_{i\in[n]}x_{ij}\leq 1$ for all $j\in[m]$ is a pacing equilibrium if

Only buyers with the highest bid win the good: $x_{ij}>0$ implies $\alpha_{i}v_{ij}=h_{j}(\alpha)$.

Full allocation of each good with a positive bid: $h_{j}(\alpha)>0$ implies $\sum_{i\in[n]}x_{ij}=1$.

Budgets are satisfied: $\sum_{j\in[m]}x_{ij}p_{j}(\alpha)\leq B_{i}$.

No unnecessary pacing: $\sum_{j\in[m]}x_{ij}p_{j}(\alpha)<B_{i}$ implies $\alpha_{i}=1$.

We will work with an approximate version of pacing equilibria in both of our PPAD-hardness and PPAD-membership results. In an approximate pacing equilibrium, we make two relaxations on (b) and (d); the two parameters used to capture these two relaxations are $\delta$ and $\gamma$, respectively.

Given an SPP game $G=(n,m,(v_{ij}),(B_{i}))$ and parameters $\delta,\gamma\in[0,1)$, we say $(\alpha,x)$, with $\alpha=(\alpha_{i})\in^{n}$, $x=(x_{ij})\in^{nm}$ and $\sum_{i\in[n]}x_{ij}\leq 1$ for all $j\in[m]$, is a $(\delta,\gamma)$-approximate pacing equilibrium of $G$ if

Only buyers close to the highest bid win the good: $x_{ij}>0$ implies $\alpha_{i}v_{ij}\geq(1-\delta)h_{j}(\alpha)$.

Full allocation of each good with a positive bid: $h_{j}(\alpha)>0$ implies $\sum_{i\in[n]}x_{ij}=1$.

Budgets are satisfied: $\sum_{j\in[m]}x_{ij}p_{j}(\alpha)\leq B_{i}$.

Not too much unnecessary pacing: $\sum_{j\in[m]}x_{ij}p_{j}(\alpha)<(1-\gamma)B_{i}$ implies $\alpha_{i}\geq 1-\gamma$.

For convenience we will write $(\delta,\gamma)$-approximate PE to denote $(\delta,\gamma)$-approximate pacing equilibrium, and write $\gamma$-approximate PE to denote $(0,\gamma)$-approximate PE. It is clear from the definition that when $\delta=\gamma=0$, $(\delta,\gamma)$-approximate PE captures the exact pacing equilibria of a SPP game.

Remark. We can incorporate reserve prices in our model. Definition 1 can be extended in a natural way to model the presence of reserve prices (see Definition 4). All our results continue to hold with this extension. We refer the reader to Appendix C for a full discussion. ∎

Before moving on to our results, we motivate the definition of pacing equilibrium by connecting it more concretely to practice and previous work. Consider a collection of $n$ buyers that participate repeatedly in $T$ second-price auctions. For each auction $t\in[T]$, the good to be sold is drawn from a collection of $m$ possible goods, with good $j$ being selected with probability $d_{j}>0$. Moreover, suppose the value $v^{\prime}_{ij}$ that buyer $i$ has for good $j$ is given by $\epsilon_{ij}v_{ij}/d_{j}$ for some $v_{ij}\geq 0$, where $\epsilon_{ij}$ is drawn independently for each buyer-good pair from some continuous distribution supported over $[1-\delta,1]$. The $\epsilon_{ij}$ component of the value can also be thought of as a perturbation that arises from errors in estimating the click-through-rate (probability of a click) which is a crucial factor in determining the value of an advertiser in internet advertising. Finally, let $B^{\prime}_{i}$ denote the budget of buyer $i$, which is the maximum amount she is willing to spend over all $T$ auctions.

Balseiro and Gur (2019) prove that, if we fix the bidding strategy of the other buyers, then it is optimal for a buyer to use pacing-based strategy to bid. The optimal pacing-based algorithm of Balseiro and Gur (2019) iteratively updates the pacing multiplier and satisfies the following properties: (i) If the buyer spends less than her per-period budget $B_{i}=B_{i}^{\prime}/T$ in an iteration, her pacing multiplier is increased, and if the payment is greater than her per-period budget, then the multiplier is decreased; (ii) The pacing multiplier is constrained to belong to $$ because bidding more than the value leads to negative utility. These properties are also satisfied by the algorithm proposed by Borgs et al. (2007) and forms the basis of pacing algorithms used in practice which aim to smooth the expenditure of a buyer by evenly spending the budget over all auctions, i.e., aim to spend the per-period budget in each period if possible. If all of the buyers use an algorithm that satisfies these properties, the system can only stabilize when all of the buyers satisfy the no-unnecessary-pacing condition.

The no-unnecessary-pacing condition and the optimality of pacing stem from strong duality, as argued in Balseiro et al. (2015) and Balseiro and Gur (2019). We provide a brief overview of their argument here. When $T$ is large and $B^{\prime}_{i}=\Theta(T)$, as is the case in online advertising, concentration arguments kick in and the problem of repeatedly bidding in $T$ auctions can be interpreted as repeatedly bidding in the following single-shot game: Each buyer wishes to maximize her expected utility (value $-$ payment) while keeping her expenditure below $B_{i}=B^{\prime}_{i}/T$ in expectation over the randomness in the values (see Balseiro et al. 2015; Balseiro and Gur 2019 for more details). This single-shot game captures the crux of the problem and its variants have been extensively studied in the literature (Balseiro et al., 2015, 2017; Babaioff et al., 2020; Balseiro et al., 2022). In fact, Balseiro and Gur (2019) show that, under some fairly stringent assumptions, their algorithm efficiently converges to an approximate pacing equilibrium of this single-shot game when all of the buyers employ it. But, these assumptions require independence of values across buyers and strong monotonicity of payments as a function of the pacing multipliers, both of which are unlikely to hold in practice. As we show in this paper, if $\text{PPAD}\neq\text{P}$, then the convergence can no longer be efficient in the absence of these assumptions. In the rest of this subsection, we will restrict our focus to this single-shot game and connect it to SPP games and pacing equilibria.

Fix buyer $i$ and let $f_{j}$ denote the highest bid from buyers other than $i$ on good $j$. Then, the optimization problem faced by buyer $i$ in the single-shot game is given by

where $b(j,\cdot)$ denotes the bidding strategy of buyer $i$ for good $j$. Assume that the distribution of $f_{j}$ conditioned on $v^{\prime}_{ij}$ (value of buyer $i$ for good $j$) is continuous. Then, using the strong-duality argument of Balseiro et al. (2015) or Balseiro et al. (2022), it can be shown that strong duality holds, where the dual problem is given by

Therefore, if $\mu_{i}^{*}\geq 0$ is the optimal dual solution, then an optimal bidding strategy for buyer $i$ is $b(j,v_{ij}^{\prime})=v_{ij}^{\prime}/(1+\mu_{i}^{*})$ (i.e., to pace her value with the multiplier $\alpha_{i}=1/(1+\mu_{i}^{*})$) since it is optimal for the inner Lagrangian optimization problem over $b$. Note that this argument does not require other buyers to use a pacing-based strategy. Thus, it establishes that a pacing-based best response always exists.

Strong duality also implies that any optimal primal-dual solution pair satisfies complementary slackness: $\mu^{*}_{i}=0$ if

The fixed-point argument of Balseiro et al. (2015) further shows that a pacing-based Nash equilibrium exists for the single-shot game where all of the buyers use pacing with multipliers $\alpha_{i}=1/(1+\mu_{i})$. Moreover, if a collection of feasible dual multipliers satisfy complementary slackness and the corresponding pacing-based strategies satisfy the budget constraints, then they form a Nash equilibrium of the single-shot game described above. Now, let $\alpha_{i}=1/(1+\mu_{i}^{*})$ be a collection of equilibrium pacing multipliers. Then, the complementary slackness condition for buyer $i$ can equivalently be written as a no-unnecessary-pacing condition: $\alpha_{i}=0$ if

As a consequence, every pacing equilibrium of this single-shot game is also a Nash equilibrium, where we define a pacing equilibrium to be any collection of pacing multipliers that satisfy the no-unnecessary-pacing condition and satisfy the budget constraint. Even if one has no interest in duality, the no-unnecessary-pacing condition is also extremely desirable in practice when the platform manages the budget of the buyer on her behalf — it ensures that the platform bids the value of the buyer on each good unless doing so would violate her budget. Thus, as outlined above, pacing equilibrium is an important refinement of Nash equilibrium for the single-shot game in both theory and practice.

Next, we connect pacing equilibria in single-shot games to approximate pacing equilibria in SPP games. Observe that, when all of the buyers use pacing to bid, $f_{j}=\max_{k\neq i}\alpha_{k}\epsilon_{kj}v_{kj}/d_{j}$. Hence, the expected payment of buyer $i$ in this single-shot game can be rewritten as

If we ignore the perturbations $\epsilon_{ij}$, this is exactly the payment of buyer $i$ in the SPP game with values $v_{ij}$ and pacing multipliers $\alpha_{i}$. To account for the perturbations and connect the single-shot game to the SPP game, we can define a perturbed SPP game (like Borgs et al. 2007) as one in which (i) the value of buyer $i$ for good $j$ is given by $\epsilon_{ij}v_{ij}$; (ii) each item is sold through second-price auction; (iii) the strategy of each buyer is her pacing multiplier $\alpha_{i}\in$; (iv) $\epsilon_{ij}$ are drawn i.i.d. from some distribution with a positive density over $[1-\delta,1]$; (v) each buyer wishes to maximize her expected utility while satisfying her budget constraint in expectation over the perturbations ($-\infty$ utility if the budget constraint is violated). We define an approximate pacing equilibrium of this perturbed SPP game as simply a collection of budget-feasible pacing multipliers that satisfy the not-too-much-unnecessary-condition (see Appendix D). Recall that approximate pacing equilibrium of SPP games allows for arbitrary allocation between all buyers close to the highest bid, and therefore includes the allocation induced by perturbations as a special case. In Appendix D, we use this fact to show that computing a pacing equilibrium of perturbed SPP games is harder than computing an approximate pacing equilibrium in (unperturbed) SPP games, and therefore PPAD-hard due to Theorem 3.

Finally, as we make $\delta$ smaller, this perturbed SPP game gets closer to a true SPP game. Unfortunately, the duality-based existence argument of Balseiro et al. (2015) and Balseiro et al. (2022) breaks down when $\delta=0$ because ties are no longer a zero-probability event. The following example shows that a pacing equilibrium may not exist in this case under the uniform tie-breaking rule.

Consider a setting with two buyers and one good. $v_{11}=1$, $v_{21}=v\gg 1$ and $B_{1}=\infty$, $B_{2}=1/4$. Then, in any pacing equilibrium we have $\alpha_{1}=1$ because of the no-unnecessary-pacing condition. Now, if $\alpha_{2}\geq 1/v$, then buyer 2 spends at least $1/2$ due to the uniform tie-breaking rule, which violates her budget. Hence, $\alpha_{2}<1/v_{2}$ and buyer two wins nothing and spends 0, thereby violating the no-unnecessary pacing condition.

Conitzer et al. (2021) show that a pacing equilibrium does exist if the ties are broken carefully, which was their motivation behind making the tie-breaking rule a part of the equilibrium concept. This equilibrium tie-breaking rule can be thought of as the limiting expected allocation in the perturbed equilibrium as $\delta$ approaches zero. They also show that, in an unperturbed SPP game, if we fix the bids of other buyers and allow a buyer to pick her bids along with the fraction of each good she wants, it is a best-response for her to use pacing to bid because it allows her to win goods that yield the highest value per unit cost—using the multiplier $\alpha_{i}$ ensures that a buyer wins a good if and only if $\alpha_{i}$ times her value is greater than the second-highest bid, i.e., if the value per unit cost is above $1/\alpha_{i}$. Conitzer et al. (2021) also provide a discussion on the undesirable properties of Nash equilibria in SPP games enroute to motivating pacing equilibria as a more desirable solution concept. Nevertheless, we would like to note that our hardness result can be extended to Nash equilibria: In Appendix D, we prove that computing a Nash equilibrium of the perturbed SPP game is also PPAD-hard. We do so by showing that a minor modification of the game constructed in our hardness reduction for Theorem 3 only admits Nash equilibria that are also pacing equilibria.

Hardness Results

In this section we investigate the hardness of computing approximate pacing equilibria and show that the problem is PPAD-hard for second-price pacing games. Our most general result (Theorem 2) shows that the problem of finding a $(\delta,\gamma)$-approximate PE in a SPP game is PPAD-hard, even when $\delta$ and $\gamma$ are polynomially small in the number of players. Our result is shown by reducing the problem of computing a Nash equilibriun in a $\{0,1\}$-cost bimatrix game to that of finding a $(\delta,\gamma)$-approximate PE in a corresponding SPP game. Because we wish to show the result for $(\delta,\gamma)$-approximate PE, we must start our reduction from such approximate PE. In order to manage the resulting approximation factors, we are forced to introduce a number of additional bookkeeping gadgets, and correspondingly work with the problem of computing $\epsilon$-well-supported Nash equilibria of $\{0,1\}$-cost bimatrix games, as opposed to standard Nash equilibria. Taken together, all these facts lead to a longer proof that may obfuscate the main ideas underlying our reduction. To better highlight the key ideas in our reduction and motivate our techniques, we are going to start by proving that finding an exact pacing equilibrium in a SPP game is PPAD-hard, by showing a reduction from the problem of finding an exact Nash equilibrium in a $\{0,1\}$-cost bimatrix game.

Our reduction will be from the problem of computing a Nash equilibrium in a $\{0,1\}$-cost bimatrix game. Let $\Delta_{n}$ denote the set of probability distributions over $[n]$. The input of the bimatrix problem is a pair of cost matrices $A,B\in\{0,1\}^{n\times n}$ and the goal is to find a Nash equilibrium $(x,y)\in\Delta_{n}\times\Delta_{n}$, meaning that $x$ minimizes cost given $y$, i.e. $x^{T}Ay\leq\hat{x}^{T}Ay$ for all $\hat{x}\in\Delta_{n}$, and similarly $y$ minimizes cost given $x$, i.e. $x^{T}By\leq x^{T}B\hat{y}$ for all $\hat{y}\in\Delta_{n}$. Equivalently, $(x,y)$ is a Nash equilibrium if $x_{i}>0$ for any $i\in[n]$ implies that $\sum_{j}A_{ij}y_{j}\leq\sum_{j}A_{kj}y_{j}$ for all $k\in[n]$, and $y_{j}>0$ for any $j\in[n]$ implies that $\sum_{i}x_{i}B_{ij}\leq\sum_{i}x_{i}B_{ik}$ for all $k\in[n]$. This problem is known to be PPAD-complete Chen et al. (2007).

Given a $\{0,1\}$-cost bimatrix game $(A,B)$ with $A,B\in\{0,1\}^{n\times n}$, we would like to construct an SPP game $G$ in time polynomial in $n$, such that every exact PE of $G$ can be mapped back to a Nash equilibrium of the bimatrix game $(A,B)$ in polynomial time.

We now formally define the SPP game $G$ in the next section, and then the following sections show the hardness result based on $G$.

The game $G$ has the following set of goods:

Normalization goods: $n$ goods $\{N(p,s)_{1},\dots,N(p,s)_{n}\}$ for each $p\in\{1,2\}$ and $s\in[n]$.

Expenditure goods: $n$ goods $\{E(p,s)_{1},\dots,E(p,s)_{n}\}$ for each $p\in\{1,2\}$ and $s\in[n]$.

Threshold goods: 1 good $T(p,s)$ for each $p\in\{1,2\}$ and $s\in[n]$.

Set $\nu=1/(16n)$. The set of buyers in $G$ is defined as follows, where we write $V(\cdot,\cdot)$ to denote the value of a good (the second component) to a buyer (the first component):

It is clear from the definition of $G$ that it can be constructed from $(A,B)$ in polynomial time.

1.2 Structure of Pacing Equilibria of G𝐺G

All of threshold good $T(p,s)$ by spending $n^{4}$ because she has the higher value.

All of expenditure good $E(p,s)_{t}$, for each $t\in[n]$, by spending at least $\nu A_{st}/2$ if $p=1$ and $\nu B_{ts}/2$ if $p=2$ because she has the higher value.

The following inequalities hold: $\sum_{s\in[n]}x_{s}^{\prime}>0$ and $\sum_{s\in[n]}y_{s}^{\prime}>0$.

At most $1/2$ on each normalization good $N(1,1)_{t}$, $t\in[n]$, because the highest competing bid is 1/2 on these goods.

At most $n^{4}$ on the threshold good $T(1,1)$ because that is the highest competing bid.

At most $\nu A_{1t}$ on each expenditure good $E(1,1)_{t}$, $t\in[n]$, because that is the highest possible competing bid.

1.3 Extracting Bimatrix Game Equilibria from G𝐺G

Now, we are ready to define the mixed strategies $(x,y)$ for the bimatrix game $(A,B)$. Set player 1’s mixed strategy $x$ to be $x_{s}=x_{s}^{\prime}/\sum_{i}x_{i}^{\prime}$ and player 2’s mixed strategy $y$ to be $y_{s}=y_{s}^{\prime}/\sum_{i}y_{i}^{\prime}$. These are valid mixed strategies because of Lemma 1 and Lemma 2. The next lemma shows that $(x,y)$ is indeed a Nash equilibrium of $(A,B)$.

$(x,y)$ is a Nash equilibrium for the bimatrix game $(A,B)$.

$n^{4}$ on the threshold good $T(1,s)$ because her bid is strictly greater than $n^{4}$.

Note that the RHS above after replacing $s$ with $s^{*}$:

Thus, given a $\{0,1\}$-cost bimatrix game $(A,B)$, we have defined an SPP game $G$ which satisfies the following properties: (i) $G$ can be constructed in polynomial time; (ii) any PE $\mathcal{E}$ of $G$ can be used to construct a Nash equilibrium $(x,y)$ of $(A,B)$ in polynomial time. As a result, the problem of finding an exact pacing equilibrium in a second-price pacing game is PPAD-hard.

2 Hardness of Finding Approximate Pacing Equilibria

We next state our main hardness result, which extends the PPAD-hardness of finding pacing equilibria to the approximate case of finding $(\delta,\gamma)$-approximate pacing equilibria.

The problem of computing a $(\delta,\gamma)$-approximate PE of an SPP game $G=(n,m,(v_{ij}),$ $(B_{i}))$ with $\delta=\gamma=1/n^{7}$ is PPAD-hard.

The proof is relegated to Appendix A. It uses similar ideas but entails more involved bookkeeping to incorporate approximations introduced in $(\delta,\gamma)$-approximate PE. Theorem 2 follows from Theorem 3 by standard padding arguments (i.e., adding dummy buyers to the game).

3 Implications of The Hardness Result

Before concluding this section, we discuss some implications of our hardness results. In Borgs et al. (2007), the authors introduced a natural bidding heuristic for optimizing the utility of budget-constrained agents who repeatedly participate in day-long auction campaigns for $m$ items, where the set of agents and items remains the same every day. The heuristic maintains a pacing multiplier for each agent, which is increased by a small amount if the buyer ran out of her daily budget before the end of the previous day, and decreased otherwise. They use random perturbation to avoid instabilities, which gives an agent who bids close to the highest bid a fraction of the item in expectation. If we ignore the intra-day temporal aspects of their model, their setting can be thought of as repeatedly playing the perturbed SPP game from Section 2.1 every day. In Theorem 1 of Borgs et al. (2007), they prove that their heuristic efficiently converges for first-price auctions. Furthermore, they conjecture the convergence of the heuristic for second-price auctions to pacing multipliers which satisfy the following conditions: (i) Every agent runs out of her daily-budget close to the end of the day; (ii) Every agent either spends most of her daily budget or has a pacing multiplier close to one. In Theorem 6 of Appendix D, we show that Theorem 3 implies that computing an approximate pacing equilibrium of the perturbed SPP game is also PPAD hard. As a consequence, if PPAD $\neq$ P, then ALGORITHM 1 of Borgs et al. (2007) does not always converge efficiently for second-price auctions, i.e., the number of days/time-steps required for convergence cannot scale as a polynomial function of the input size and $(1/\delta,1/\gamma)$ in the worst-case. In other words, we have shown that Theorem 1 of Borgs et al. (2007) cannot be extended to second-price auctions in any way that maintains efficient convergence unless PPAD $=$ P, thereby making progress towards their open conjecture.

Moreover, recall from Section 2.1 that if all of the buyers employ pacing algorithms, like the one proposed by Balseiro and Gur (2019), and the resulting dynamics converge, then they will converge to an approximate pacing equilibrium. Our hardness result (Theorem 3 and Theorem 6) implies that there exists a (correlated) value distribution such that the algorithm of Balseiro and Gur (2019), which is optimal for a single buyer against an adversarial/stochastic competition, does not converge efficiently to an equilibrium when employed by all the buyers, unless PPAD$=$P.

Our hardness results are also pertinent to the relationship between pacing equilibria and market equilibria. In Proposition 5 of Conitzer et al. (2021), the authors show that every pacing equilibrium in a second-price pacing game has an equivalent supply-aware market equilibrium with linear utilities, where supply-aware means that the buyers are aware of the supplies of each item and choose their demand set accordingly. Thus, the relationship between pacing equilibria and market equilibria, in combination with Theorem 3, implies that there exists a refinement of the set of supply-aware market equilibria with linear utilities which is PPAD-hard to compute.

Existence of Pacing Equilibria and Membership in PPAD

We prove Theorem 1 in this section, i.e., the problem of finding a pacing equilibrium of an SPP game is in PPAD. One consequence of this result is that every SPP game with rational values $v_{ij}$ and budgets $B_{i}$ has a pacing equilibrium $(\alpha,x)$ with rational entries.

Our plan is as follows. We first introduce a restricted version of approximate pacing equilibria called smooth $(\delta,\gamma)$-approximate PE (see Definition 3), which will only be used in Section 4.1. We prove in Section 4.1 that the problem of finding a smooth $(\delta,\gamma)$-approximate PE (when $\delta$ and $\gamma$ are input parameters encoded in binary) is in PPAD. Given that the smooth version (Definition 3) is a restriction of $(\delta,\gamma)$-approximate PE (Definition 2), this implies that the problem of computing a $(\delta,\gamma)$-approximate PE is in PPAD.

Next we give in Section 4.2 an efficient algorithm that can round any $(\delta,\gamma/2)$-approximate PE into a $\gamma$-approximate PE when $\delta$ is sufficiently small. This, combined with the PPAD-membership of $(\delta,\gamma)$-approximate PE, shows that the problem of computing $\gamma$-approximate PE is also in PPAD.

Finally we show in Section 4.3 that, when $\gamma$ is sufficiently small, any $\gamma$-approximate PE of $G$ can be used to build a linear program which can then be solved to obtain an exact pacing equilibrium of $G$. It follows that the problem of computing an exact pacing equilibrium is in PPAD.

We start with the definition of smooth $(\delta,\gamma)$-approximate PE. It is a refinement of $(\delta,\gamma)$-approximate PE in which the pacing multipliers $(\alpha_{i})$ fully determine the allocations $(x_{ij})$. Note that this is not the case for $(\delta,\gamma)$-approximate PE in general: potentially there can be $(\delta,\gamma)$-approximate PE with identical multipliers but different allocations. The smooth version we consider below, on the other hand, specifies the allocations as continuous functions of multipliers.

Given an SPP game $G=(n,m,(v_{ij}),(B_{i}))$ and two parameters \delta{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{\in(0,1)}},\gamma\in[0,1), we say that $(\alpha,x)$ with $\alpha=(\alpha_{i})\in^{n}$, $x=(x_{ij})\in^{nm}$ and $\sum_{i\in[n]}x_{ij}\leq 1$ for all $j\in[m]$ is a smooth $(\delta,\gamma)$-approximate PE of $G$ if

Only buyers close to the highest bid win the good and the allocation $x$ is completely specified by $\alpha$: For each $i\in[n]$ and $j\in[m]$, $x_{ij}$ (as a function of $\alpha$) is given by

where $[y]^{+}$ is $y$ if $y\geq 0$ and otherwise. (We assume by default that $0/0=0$.)

Budgets are satisfied: $\sum_{j\in[m]}x_{ij}(\alpha)p_{j}(\alpha)\leq B_{i}$.

Not too much unnecessary pacing: $\sum_{j\in[m]}x_{ij}(\alpha)p_{j}(\alpha)<(1-\gamma)B_{i}$ implies $\alpha_{i}\geq 1-\gamma$.

Observe from the definition that, if $(\alpha,x)$ is a smooth $(\delta,\gamma)$-approximate PE of an SPP game $G$, then it must be a $(\delta,\gamma)$-approximate PE of $G$ as well. Therefore, the PPAD membership of computing a smooth $(\delta,\gamma)$-approximate PE in an SPP game implies directly the PPAD membership for $(\delta,\gamma)$-approximate PE. A similar statement holds for establishing their existence.

The main tools we will use are Sperner’s Lemma and the search problem it defines.

High-dimensional Sperner’s Lemma. We review Sperner’s lemma. Consider a $(n-1)$-dimensional simplex $S=\{\sum_{i=1}^{n}\alpha_{i}v_{i}\hskip 1.70709pt|\hskip 1.70709pt\alpha_{i}\geq 0,\sum_{i=1}^{n}\alpha_{i}=1\}$, where $v_{1},\dots,v_{n}$ are $n$ vertices of $S$. A triangulation of $S$ is a partition of $S$ into smaller subsimplices such that any two subsimplices either are disjoint or share a full face of a certain dimension. A Sperner coloring $T$ of a triangulation of $S$ is then an assignment of $n$ colors $\{1,\ldots,n\}$ to vertices of the triangulation (union of the vertices of subsimplices that make up the triangulation) such that

Vertices of the original simplex $S$ each receive a different color: $T(v_{i})=i$ for each $i\in[n]$.

Vertices on each face of $S$ are colored using only the colors of the vertices defining that face: For any vertex $u=\sum_{i}\beta_{i}v_{i}$ in the triangulation, we have $T(u)\neq j$ if $\beta_{j}=0$.

A panchromatic subsimplex of $T$ is one in the triangulation whose vertices have all the $n$ colors.

Sperner’s Lemma: Every Sperner coloring $T$ of any triangulation of $S$ has a panchromatic subsimplex.

Before proceeding with the formal proof of PPAD membership (with its added burden of rigorously attending to complexity-theoretic details), we provide an informal argument for the existence of smooth $(\delta,\gamma)$-approximate PE which forms the basis of its PPAD membership proof. Let $G$ be an SPP game and $S$ be the standard simplex $S=\{\beta=(\beta_{1},\dots,\beta_{n})\hskip 1.70709pt|\hskip 1.70709pt\beta_{i}\geq 0,\sum_{i}\beta_{i}=1\}$ from now on. We will assign a color to each point $\beta\in S$ (informally) as follows: Construct a pacing multiplier $\alpha_{i}(t)=t\beta_{i}$ for each $i\in[n]$, where $t$ is a scalar. Increase $t$, starting at , and instruct each buyer $i\in[n]$ to say “Stop” when either $\alpha_{i}(t)=1$ or $\sum_{j}x_{ij}(\alpha(t))p_{j}(\alpha(t))=B_{i}$ happens. Color $\beta$ with $k$ if buyer $k$ is the first to say “Stop” (with tie breaking done arbitrarily, e.g., taking the smallest such $k$).

Let $t^{*}(\beta)$ be the value of $t$ at which some buyer says “Stop” for the first time. Then the buyer that says “Stop” first is either spending her budget or is not paced, i.e. she satisfies both the budget constraint (b) and the ‘No unnecessary pacing’ condition (c) (see Definition 1). Now, by taking a triangulation of $S$, it is easy to verify that the coloring described above induces a Sperner coloring and thus, Sperner’s lemma implies the existence of a panchromatic subsimplex $Q$. It follows from our coloring that every buyer says “Stop” at one of the vertices of $Q$ and hence, every buyer satisfies (b) and (c) of Definition 1 at one of its vertices. By proving the Lipschitzness of $t^{*}(\beta)$ and the total expenditures of buyers, both as functions of $\beta$, we show that when the triangulation is fine enough, any point $\beta$ in a panchromatic subsimplex yields a $(\delta,\gamma)$-approximate PE of $G$.

A proof of the following PPAD membership result can be found in Etessami and Yannakakis (2010) (see the proof of item 2 of Proposition 2.2; note that on page 2548 they reduce the problem they are interested in to the problem of finding a panchromatic subsimplex in a Sperner coloring over Kuhn’s triangulation and then show the latter is in PPAD):

Given a Boolean circuitThe circuit has $O(n\log(1/\omega))$ input variables to encode a point of $S_{\omega}$ and has $\lceil\log n\rceil$ output gates to encode the output of the Sperner coloring $T$. that encodes a Sperner coloring $T:S_{\omega}\rightarrow[n]$ of Kuhn’s triangulation for some $\omega$ and $n$, the problem of finding a panchromatic subsimplex is in PPAD.

We prove the PPAD membership of the problem of finding a smooth $(\delta,\gamma)$-approximate PE by giving a polynomial-time reduction to the problem described in Theorem 4. Given an SPP game $G=(n,m,(v_{ij}),(B_{i}))$ and parameters $\delta$ and $\gamma$ (which we assume without loss of generality that $\delta,\gamma<1/4$), we set the parameter $\omega$ to be

where $B_{\min}:=\min_{i\in[n]}B_{i}$ and $|G|$ denotes the number of bits needed to represent $G$. We define a coloring $T:S_{\omega}\rightarrow[n]$, following ideas described in the sketch of existence above, and prove that $T$ satisfies the following properties:

Every panchromatic subsimplex of $T$ in the triangulation can be used to compute a smooth $(\delta,\gamma)$-approximate PE of the SPP game $G$ in polynomial time.

There is a polynomial-time algorithm that outputs $T(\beta)$ on inputs $G$, $\omega$, $\delta$ and $\beta\in S_{\omega}$.

The PPAD membership of computing a smooth $(\delta,\gamma)$-approximate PE in an SPP game follows directly by combining Theorem 4 and Lemma 4.

We now give the definition of the coloring $T:S_{\omega}\rightarrow[n]$. Let $\beta=(\beta_{1},\ldots,\beta_{n})$ be a vertex of $S_{\omega}$. Set $\alpha_{i}(t)=t\beta_{i}$, where $t$ is a positive scalar. As discussed earlier, we set the color $T(\beta)$ of $\beta$ by increasing $t$, starting at , and instructing each buyer $i$ to say “Stop” when either $\alpha_{i}(t)=1$ or

The color $T(\beta)$ of $\beta$ is set to be $k\in[n]$ if buyer $k$ is the first buyer to say “Stop” (with arbitrary tie breaking, e.g., by taking the smallest such $k$).

which does not depend on $t$. Also, for $t\geq 0$, $p_{j}(\alpha(t))=tp_{j}(\beta)$, where we write $p_{j}(\beta)$ to denote the second largest element among $\beta_{1}v_{1j},\dots,\beta_{n}v_{nj}$. For each buyer $i\in[n]$, define

where the first term is $+\infty$ if $\beta_{i}=0$ and the second term is $+\infty$ if $\sum_{j}x_{ij}(\beta)p_{j}(\beta)=0$. Note that $t_{i}(\beta)$ is exactly the value of $t$ at which buyer $i$ would say “Stop” in the informal coloring procedure described earlier. Given our assumption of $B_{i}>0$, we have $t_{i}(\beta)>0$ for all $i\in[n]$. Additionally, define $t^{*}(\beta)=\min_{i\in[n]}t_{i}(\beta)$. Given that $\beta_{i}$’s sum to $1$, we have that $t^{*}(\beta)\leq n$ because $\beta_{i}\geq 1/n$ for some $i\in[n]$. We record the discussion as the following lemma:

For every $\beta\in S_{\omega}$ we have $0<t^{*}(\beta)\leq n$.

Finally, the color $T(\beta)$ of $\beta\in S_{\omega}$ is set to be the smallest $i\in[n]$ such that $t_{i}(\beta)=t^{*}(\beta)$. We are now ready to prove Lemma 4.

Part (3) of Lemma 4 follows from the description of $T$. To prove part (1) ($T$ is a Sperner coloring), consider a vertex $\beta\in S_{\omega}$ on the facet of $S$ opposite to the vertex $e_{i}$, i.e., $\beta_{i}=0$. Hence, $t_{i}(\beta)=\infty$, which by Lemma 5 implies that $T(\beta)\neq i$ given that $t^{*}(\beta)\leq n$.

To prove part (2), we show that if $q$ is a vertex of any panchromatic subsimplex of $T$, then $(\alpha,x)$ must be a smooth $(\delta,\gamma)$-approximate PE of $G$ where $\alpha=t^{*}(q)\cdot q$ and $x=(x_{ij})$ has $x_{ij}=x_{ij}(q)$.

First it follows from the definition of $t^{*}(\beta)$ and $x_{ij}(\beta)$ that $\alpha_{i}\in$ and $x_{ij}\in$. Conditions (a) and (b) of Definition 3 also trivially hold for all vertices of the triangulation. It suffices to prove (c) for all $i\in[n]$, which means the complementarity condition that either $\alpha_{i}\geq 1-\gamma$ or the expenditure of buyer $i$ is at least $(1-\gamma)B_{i}$. Fix an arbitrary $i\in[n]$.

For this purpose we note that given the subsimplex is panchromatic, it has a vertex $q^{\prime}$ such that $T(q^{\prime})=i$, which implies that if we used $q^{\prime}$ to define $\alpha^{\prime}$ and $x^{\prime}$ (i.e. $\smash{\alpha^{\prime}=t^{*}(q^{\prime})\cdot q^{\prime}}$ and $\smash{x^{\prime}_{ij}=x_{ij}(q^{\prime})}$), then they would satisfy the above complementarity condition for buyer $\smash{i}$ with $\smash{\gamma=0}$. The following claim shows that both the multiplier $t^{*}(\beta)\cdot\beta_{i}$ and the total expenditure of buyer $i$:

are smooth as functions of $\beta$. Intuitively this allows us to use the complementarity condition for buyer $i$ at $q^{\prime}$ to show that the same condition holds at $q$ approximately given that $\|q-q^{\prime}\|_{\infty}\leq 2\omega$ (as a property of subsimplices in Kuhn’s triangulation).

Let $L=(2^{|G|}/\delta)^{10,000}$. Then for any panchromatic subsimplex $S_{0}$ of $T$ and buyer $i\in[n]$, the following Lipschitz conditions hold for all $\beta,\beta^{\prime}\in S_{0}$:

We use Claim 1 to finish the proof of the lemma and consign the claim’s proof to Appendix B. Given $T(q^{\prime})=i$, one of the following two cases holds:

$t^{*}(q^{\prime})\cdot q_{i}^{\prime}=1$, which by Claim 1 and our chocie of $\omega$ implies

$t^{*}(q^{\prime})\sum_{j}x_{ij}(q^{\prime})p_{j}(q^{\prime})=B_{i}$, which in combination with Claim 1 and our choice of $\omega$ implies that the expenditure of buyer $i$ exceeds $(1-\gamma)B_{i}$:

Since $i\in[n]$ was arbitrary, this finishes the proof that $(\alpha,x)$ is a smooth $(\delta,\gamma)$-approximate approximate PE. ∎

2 PPAD Membership of Computing γ𝛾\gamma-approximate PE

Consider an SPP game $G=(n,m,\{v_{ij}\}_{i,j},\{B_{i}\}_{i})$. As before, we will use $|G|$ to denote the number of bits required to represent $G$. The main result of this subsection shows that (informally) when $\delta$ is small enough, any $(\delta,\gamma/2)$-approximate PE of $G$ can be efficiently rounded to a $\gamma$-approximate PE. It follows from the PPAD membership of $(\delta,\gamma)$-approximate PE established in the previous subsection that the problem of computing a $\gamma$-approximate PE is in PPAD as well.

Before presenting the rounding algorithm, we motivate the main idea behind it. Observe that the major difference between $(\delta,\gamma)$-approximate PE and $\gamma$-approximate PE is the ability of buyers that don’t have the highest bid to win the good in the former. In order to round a $(\delta,\gamma^{\prime})$-approximate PE $(\alpha^{*},x^{*})$ to obtain a $\gamma$-approximate PE $(\alpha^{\prime},x^{\prime})$ of $G$ (where $\gamma^{\prime}=\gamma/2$ in the rest of this subsection), we set $x^{\prime}=x^{*}$ and need to round $\alpha^{*}$ to $\alpha^{\prime}$ to ensure that all the winners are tied for the highest bid and at the same time, the multiplier and total expenditure of each buyer changes only slightly.

We now present an informal argument that demonstrates how this is achieved in our rounding algorithm when there are only two buyers ($n=2$). Define the set of all valuation ratios

To finish the proof that $(\alpha^{\prime},x^{*})$ is a $\gamma$-approximate PE, it suffices to show that the budget constraint and the not too much unnecessary pacing condition still hold approximately after the small scaling of $\alpha_{2}^{*}$. In the rest of this subsection, we extend the aforementioned line of reasoning to design a rounding algorithm for the general setting, and prove its correctness.

$(1-\delta)^{2^{n}}>(1-\gamma^{\prime})$ and $(1-\delta)^{2^{n}}z>1$ for all $z\in\mathcal{V}$ such that $z>1$.

It suffices to set $\delta$ to be $1/2^{N}$ where $N$ is polynomial in $|G|$ and $\log(1/\gamma)$.

Let $(\alpha^{*},x^{*})$ be a $(\delta,\gamma^{\prime})$-approximate PE of $G=(n,m,(v_{ij}),(B_{i}))$, where $\gamma^{\prime}=\gamma/2$ and $\delta$ satisfies the two conditions above. We will use $W_{j}$ to denote the winners of the good $j$ under $x^{*}$: $W_{j}$ consists of buyers $i$ with $x_{ij}^{*}>0$. Moreover, recall that $h_{j}(\alpha)$ denotes the highest bid on good $j$ when the pacing multipliers are given by $\alpha$. Our rounding algorithm is presented in Algorithm 1. The polynomial reduction then follows from the following performance guarantee of the rounding algorithm, which we prove in the rest of the subsection:

The rounding algorithm takes $(\alpha^{*},x^{*})$, $\delta$ and $G$ as input and runs in polynomial time. Let $\alpha^{\prime}$ be the tuple of multipliers returned by the rounding algorithm. Then $(\alpha^{\prime},x^{*})$ is a $\gamma$-approximate PE of $G$.

The rounding algorithm maintains an undirected graph $\mathcal{G}$ over vertices $[n]$ as buyers. $\mathcal{G}$ starting out with an empty edge set and edges are added according to Algorithm 1 to keep track of the rounding-updates performed on $\alpha$. We use $C_{\mathcal{G}}(i)$ to denote the connected component of $i$ in the graph $\mathcal{G}$. The algorithm also maintains an edge labeling $I(\cdot)$ that maps each edge of the graph $\mathcal{G}$ to a good $j\in[m]$ (which intuitively is the good that caused the creation of this edge). We remark that the labeling $I(\cdot)$ is only relevant for the analysis of the algorithm below. Now, we proceed to prove Lemma 6.

Suppose in the $t_{0}$ iteration of the while loop, $\{i,k\}$ is the edge that was just added to $\mathcal{G}$ with $I(\{i,k\})=j$, then at the end of this iteration we have $C_{\mathcal{G}}(i)=C_{\mathcal{G}}(k)$ and

Moreover, (#) holds for all iterations $t\geq t_{0}$.

We prove the lemma using induction on the iterations on the while loop. For the base case $t=t_{0}$, note that (#) holds at the end of the iteration due to Step 2 of Algorithm 1. Moreover, since edge $\{i,k\}$ is added to $\mathcal{G}$ in Step 3, we also have $C_{\mathcal{G}}(i)=C_{\mathcal{G}}(k)$ at the end of iteration $t_{0}$. Moreover, since no edges are removed during the run of Algorithm 1, $\{i,k\}\in E$ for iterations after $t_{0}$, and hence $C_{\mathcal{G}}(i)=C_{\mathcal{G}}(k)$ at the end of all iterations $t\geq t_{0}$. Suppose (#) holds at the end of iteration $t-1$ for some $t-1\geq t_{0}$. Then, either both $\alpha_{i}$ and $\alpha_{k}$ will both be updated identically or neither of them will be updated because $C_{\mathcal{G}}(i)=C_{\mathcal{G}}(k)$, thereby maintaining (#). This completes the induction and establishes the lemma. ∎

Next we prove that at the end of each iteration, bids for the same good from buyers in the same component of $\mathcal{G}$ are either tied or not very close.

After each iteration of the while loop, and for each good $j\in[m]$, all buyers from the same connected component of $\mathcal{G}$ are either tied for $j$, or their bids for $j$ are multiplicatively separated by a factor larger than $(1-\delta)^{2^{n}}$.

Let $\mathcal{G}$ be the current graph and $a,b\in[n]$ be two buyers in the same connected component of $\mathcal{G}$. Assuming $\alpha_{a}v_{aj}>\alpha_{b}v_{bj}$ for some $j\in[m]$, we show below that $(1-\delta)^{2^{n}}\alpha_{a}v_{aj}>\alpha_{b}v_{bj}$ from which the lemma follows. Given that $a$ and $b$ are connected in $\mathcal{G}$, we write $\{a,i_{1}\},\{i_{1},i_{2}\},\dots,$ $\{i_{L},b\}$ to denote a path from $a$ to $b$ in $\mathcal{G}$ with $L<n$. Then, using Lemma 7, we can write

Hence, $\alpha_{a}v_{aj}/\alpha_{a}v_{bj}\in\mathcal{V}$ and $\alpha_{a}v_{aj}/\alpha_{b}v_{bj}>1$. Therefore, our choice of $\delta$ implies that

Initially (in $\alpha^{*}$) we have every $i\in W_{j}$ has $\alpha_{i}^{*}v_{ij}\geq(1-\delta)h_{j}(\alpha^{*})$ (given that $(\alpha^{*},x^{*})$ is a $(\delta,\gamma^{\prime})$-approximate PE). The next lemma shows that, at the end of each iteration, $\alpha_{i}v_{ij}$ of every $i\in W_{j}$ (note that $W_{j}$ is always defined using the original allocation $x^{*}$) remains not far from $h_{j}(\alpha)$.

After $t$ iterations of the while loop, every $j\in[m]$ and $i\in W_{j}$ satisfy

The proof follows from induction. The base case of $t=0$ follows from definition.

Suppose the statement holds after $(t-1)$ iterations, and let’s focus on some $j\in[m]$ and $i\in W_{j}$ during the $t$-th iteration. By our inductive hypothesis, we have

before the start of the $t$-th iteration. On the other hand, note that all changes to $\alpha$ occur in step 2 of the while loop, and moreover, all such changes result in an increase of some entries of $\alpha$. It also follows from the inductive hypothesis and the choices of $k,i,j$ in step 1 of the while loop that entries of $\alpha$ can only go up by a multiplicative factor of at most $\smash{{1}/{(1-\delta)^{2^{t-1}}}}$. Therefore, after the $t$-th iteration, we have

Lemmas 8 and 9 imply that, in each of the first $n$ iterations of the while loop, buyers $i$ and $k$ picked in step 1 must belong to different connected components of $\mathcal{G}$. As a result, there are at most $n-1$ iterations of the while loop given that we merge two connected components in each loop. On the one hand, this implies that the rounding algorithm terminates in polynomial time. On the other hand, at the termination of the while loop, for every good $j\in[m]$, we have $\alpha_{i}v_{ij}=h_{j}(\alpha)$ for all $i\in W_{j}$, i.e., every winner of $j$ under $x^{*}$ has the highest bid for $j$.

The next lemma shows that the $\alpha^{\prime}$ returned by the rounding algorithm is close to $\alpha^{*}$.

Let $\alpha^{\prime}$ be the tuple of multipliers returned by the rounding algorithm. Then

By Lemma 9, in iteration $t$ of the while loop, each entry of $\alpha$ either stays the same or increases multiplicatively by a factor of at most $\smash{1/(1-\delta)^{2^{t-1}}}$. As there are at most $n-1$ iterations of the while loop, we have for every $i\in[n]$:

We have already shown that the algorithm runs in polynomial time. Assuming that $(\alpha^{*},x^{*})$ is a $(\delta,\gamma^{\prime})$-approximate PE of $\mathcal{G}$, we show that $(\alpha^{\prime},x^{*})$ is a $\gamma$-approximate PE of $\mathcal{G}$ by establishing conditions (a)-(d) of Definition 2. Using Lemma 10, we have $\alpha^{\prime}\in^{n}$. Condition (a) has already been established earlier using Lemmas 8 and 9. Condition (b) holds because we kept the same allocation $x^{*}$ and given how we obtain $\alpha^{\prime}$ from $\alpha^{*}$, the set of goods $j$ with $h_{j}(\alpha^{*})>0$ is the same as that in $\alpha^{\prime}$. Condition (c) follows easily from Lemma 10. So it suffices to verify that (d) holds with $\gamma$.