Learning vs. Optimizing Bidders in Budgeted Auctions
Giannis Fikioris, Balasubramanian Sivan, Éva Tardos · 2026
Read Learning vs. Optimizing Bidders in Budgeted Auctions by Giannis Fikioris, Balasubramanian Sivan, Éva Tardos (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-08517.txt.
Introduction
Fikioris, Sivan, and Tardos study repeated second price auctions where both a learning bidder and a strategic bidder face strict budgets. They generalize the Stackelberg equilibrium to a budgeted version, proving the optimizer's best plan splits into at most k plus 1 phases for a k dimensional budget. They also show a standard proportional bid pacing rule is strategically robust: the optimizer cannot beat its budgeted equilibrium payoff against it.
Catalog record
| CREATOR | Giannis Fikioris, Balasubramanian Sivan, Éva Tardos |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 139898 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.08517
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning vs. Optimizing Bidders in Budgeted Auctions Giannis Fikioris, Balasubramanian Sivan, Éva Tardos Abstract The study of repeated interactions between a learner and a utility-maximizing optimizer has yielded deep insights into the manipulability of learning algorithms. However, existing literature primarily focuses on independent, unlinked rounds, largely ignoring the ubiquitous practical reality of budget constraints. In this paper, we study this interaction in repeated second-price auctions in a Bayesian setting between a learning agent and a strategic agent, both subject to strict budget constraints, showing that such cross-round constraints fundamentally alter the strategic landscape. First, we generalize the classic Stackelberg equilibrium to the Budgeted Stackelberg Equilibrium . We prove that an optimizer’s optimal strategy in a budgeted setting requires time-multiplexing; for a k k -dimensional budget constraint, the optimal strategy strictly decomposes into up to k + 1 k+1 distinct phases, with each phase employing a possibly unique mixed strategy (the case of k = 0 k=0 recovers the classic Stackelberg equilibrium where the optimizer repeatedly uses a single mixed strategy). Second, we address the intriguing question of non-manipulability. We prove that when the learner employs a standard Proportional controller (the “P” of the PID-controller) to pace their bids, the optimizer’s utility is upper bounded by their objective value in the Budgeted Stackelberg Equilibrium baseline. By bounding the dynamics of the PID controller via a novel analysis, our results establish that this widely used control-theoretic heuristic is actually strategically robust. 1 Introduction The study of online learning in strategic environments has blossomed over the past decade into a fertile and dynamic area of theoretical computer science. A recent central theme of this literature is understanding the long-run outcomes when a standard, no-regret learning algorithm interacts with a fully rational, utility-maximizing optimizer. In these asymmetric interactions, prior work has consistently asked: What extra utility can an optimizer extract when playing against a predictable learner, rather than a strategic opponent? Which learning algorithms are fundamentally robust against such manipulation? This inquiry has yielded a rich understanding of optimizer-learner dynamics. We know that against standard no-regret learners, optimizers can always earn an average objective of their Stackelberg value in the single-shot game [ 26 ] (by simply playing their Stackelberg strategy in each round), and often much more than this. Preventing this manipulation requires learners to minimize stronger notions of regret—swap regret in normal form games [ 26 , 40 ] and profile swap regret in broader polytope games [ 4 ] . However, all of this foundational work operates under a simplifying assumption: decisions are made round-by-round, independent of the past. In this paper, we add to this line of work a new, practically ubiquitous, dimension: budget constraints . In real-world repeated interactions—most notably in digital advertising and online auctions [ 32 , 42 ] —agents rarely operate with infinite liquidity. Bidding under budget constraints is a thriving area of research in its own right, precisely because budgets fundamentally alter strategic behavior, even in traditionally truthful mechanisms like second-price auctions. In a further departure from prior work, which has overwhelmingly modeled the optimizer as an unconstrained seller (e.g., dynamically setting reserve prices to extract revenue: see [ 17 , 38 ] ) and the learner as a buyer , we shift this paradigm to study a setting where both the optimizer and the learner are competing buyers , with budget constraints. We study the interaction between two budget-constrained agents participating in repeated auctions (we primarily focus on second-price auctions, and also show, under some assumptions, that our results extend to first-price auctions), where item values are drawn repeatedly from a joint distribution. One agent employs a learning algorithm to compute their bids, while the opponent is a strategic optimizer. Both share the same objective: maximizing their total accumulated value subject to a budget constraint. Budgets introduce a significant theoretical wrinkle—by linking decisions across rounds, budgets shatter the isolation of the repeated game framework. First, from the optimizer’s perspective, it is unclear what the generalization of the Stackelberg strategy is when they are budget constrained. Second, from the learner’s perspective, it is unclear whether they can achieve standard properties like no-regret, and best respond to the optimizer’s strategy. The learner being able to do as good as their best distribution in hindsight becomes complicated because of the “spend or save” dilemma introduced by the budget constraints (see [ 36 ] ), that forces the learner to weigh the value of spending today against the opportunity cost of having depleted funds tomorrow. The budget constraint’s introduction of coupling across rounds raises a sequence of challenging, fundamental questions: What is the baseline objective value an optimizer is guaranteed to obtain against any learner in a budgeted setting? What strategy achieves this? Are there strategically robust learning algorithms guaranteeing that the optimizer cannot extract anything beyond this baseline? Our Contributions In this paper, we resolve these questions by characterizing the limits of manipulation in budgeted settings and identifying a simple and practical learning algorithm that achieves non-manipulability in second-price auctions, which, under certain assumptions, extend to first-price auctions. The Budgeted Stackelberg Equilibrium. Our first contribution generalizes the classic notion of a Stackelberg equilibrium to accommodate cross-round constraints, introducing what we call the Budgeted Stackelberg Equilibrium (BSE), Definition 2.1 . In a standard repeated game, an optimizer achieves their Stackelberg value by repeatedly sampling actions from a single, optimal mixed strategy, and the learner learning to best respond to this. When the optimizer has a budget constraint, we show that this approach is insufficient. Because the optimizer’s value as a leader is not necessarily concave as a function of their spending (see Fig. 1(a) ), they can achieve strictly higher utility by modulating their spend rate over time—for instance, aggressively overspending in an initial phase of length qT , and underspending for the remaining (1-q)T rounds. We show that an optimizer with a k -dimensional budget constraint might need to use up to k+1 different strategies in k+1 distinct temporal phases ( Lemmas 2.2 and B.2 ). For k=0 , i.e., for an unbudgeted optimizer, this recovers the classic definition of Stackelberg equilibrium. For the optimizer to achieve this increased utility by time-multiplexing, the learner needs to react to the change in the optimizer’s strategy. Even in the absence of budget constraints, employing a no-regret algorithm is insufficient for the learner to react to a time-multiplexed optimizer strategy, and we would need no-adaptive regret algorithms. But from a budget-constrained learner’s perspective, a time-multiplexing optimizer would make it impossible for them to best respond, even against the single best distribution in hindsight. [ 36 ] shows this is indeed the case, as the learner cannot avoid linear regret in an adversarial bandits with knapsacks setting 1 1 1 In fact, the adversary in the counterexample from [ 36 ] looks similar to the optimizer’s two-phase strategy that we use. . Without knowledge of when and what the optimizer would do in the future, a budget-constrained learner’s reasonable strategy is to optimize their value while spending their budget evenly over time. This boils down to making the learner “best respond” to each of the optimizer’s phases. Existing learning algorithms for budgeted auctions, such as [ 9 ] , do learn