pith. sign in

arxiv: 2604.12799 · v2 · submitted 2026-04-14 · 💻 cs.GT · cs.AI· cs.DS

Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertising

Nguyen Kim Thang This is my paper

Pith reviewed 2026-05-10 14:10 UTC · model grok-4.3

classification 💻 cs.GT cs.AIcs.DS
keywords proportional mechanismsauto-biddingprice of anarchyliquid welfareonline advertisingNash equilibriaauction designduality
0
0 comments X

The pith

A modified proportional mechanism for auto-bidding auctions achieves a price of anarchy of 1 plus a term that shrinks as the number of bidders grows.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies proportional mechanisms in online auto-bidding advertising and measures their efficiency at pure Nash equilibria using liquid welfare. It first proves that the standard version has a tight price of anarchy bound of exactly 2. The authors then present a modified payment scheme that improves the bound to 1 plus O(1) divided by the number of agents minus one. This new bound gets arbitrarily close to 1 when many bidding agents are present. The analysis relies on duality and KKT conditions drawn from linear and convex programming.

Core claim

For the standard proportional mechanism the price of anarchy is tightly 2 under liquid welfare. The modified version replaces the payment rule with an alternative scheme and obtains the improved bound 1 + O(1)/(n-1) for n bidding agents. The proof proceeds by applying duality and the Karush-Kuhn-Tucker optimality conditions to bound the ratio of equilibrium liquid welfare to the optimal liquid welfare.

What carries the argument

The alternative payment scheme inside the modified proportional mechanism, whose equilibrium efficiency is bounded via duality and KKT conditions from linear and convex programming.

If this is right

  • The efficiency ratio approaches the optimal liquid welfare value as the number of agents increases.
  • The new bound is strictly better than the previous barrier of 2 for any n greater than or equal to 2.
  • The same duality-plus-KKT technique may be reused to derive PoA results for other mechanism families.
  • For large markets the welfare loss from strategic bidding becomes negligible under the revised payments.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Platform designers could test the alternative payment rule in large-scale ad exchanges to measure realized welfare gains.
  • The approach may extend to other budget-constrained online auction formats where equilibrium analysis has been difficult.
  • If the liquid-welfare objective aligns with platform goals, the modified rule offers a practical lever for efficiency without changing the allocation rule.
  • Empirical studies could check whether observed bidding behavior in real auto-bidding systems approximates the pure equilibria analyzed here.

Load-bearing premise

Bidders play pure Nash equilibria of the game induced by the mechanism and the liquid-welfare objective, and the budgeted auto-bidding model faithfully represents real advertiser behavior.

What would settle it

A concrete valuation profile and pure Nash equilibrium in the modified mechanism with five bidders where the realized liquid welfare is less than 80 percent of the optimum would contradict the claimed bound.

read the original abstract

The rise of automated bidding strategies in online advertising presents new challenges in designing and analyzing efficient auction mechanisms. In this paper, we focus on proportional mechanisms within the context of auto-bidding and study the efficiency of pure Nash equilibria, specifically the price of anarchy (PoA), under the liquid welfare objective. We first establish a tight PoA bound of 2 for the standard proportional mechanism. Next, we introduce a modified version with an alternative payment scheme that achieves a PoA bound of $1 + \frac{O(1)}{n-1}$ where $n \geq 2$ denotes the number of bidding agents. This improvement surpasses the existing PoA barrier of 2 and approaches full efficiency as the number of agents increases. Our methodology leverages duality and the Karush-Kuhn-Tucker (KKT) conditions from linear and convex programming. Due to its conceptual simplicity, our approach may offer broader applications for establishing PoA bounds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper analyzes the price of anarchy (PoA) of proportional mechanisms for auto-bidding in online advertising under the liquid welfare objective. It first proves a tight PoA bound of 2 for the standard proportional mechanism. It then introduces a modified mechanism with an alternative payment scheme that achieves a PoA bound of 1 + O(1)/(n-1) for n ≥ 2 bidders. The bounds are derived by mapping the first-order conditions of pure Nash equilibria to the KKT stationarity conditions of the liquid-welfare linear program and applying duality.

Significance. If the results hold, the work improves upon the known PoA barrier of 2 by providing a bound that approaches full efficiency (PoA=1) as the number of bidders grows, which is a meaningful advance for mechanism design in auto-bidding settings. The duality-plus-KKT approach for establishing PoA bounds is a conceptual strength that could apply to other mechanism design problems involving budgets and welfare objectives.

major comments (2)
  1. [analysis of the modified mechanism] The derivation of the PoA bound 1 + O(1)/(n-1) for the modified mechanism (in the section introducing the alternative payment scheme) maps pure-NE first-order conditions to KKT conditions of the liquid-welfare LP. However, this mapping presupposes the existence of a pure Nash equilibrium under the new payment rule. No existence proof, quasi-concavity argument for the utility function, or invocation of a fixed-point theorem (e.g., Kakutani) is supplied for the modified payment scheme, in contrast to the standard mechanism where PoA=2 is already established. This renders the bound conditional on existence and is load-bearing for the central claim.
  2. [§3 and modified-mechanism analysis] §3 (standard mechanism) and the modified-mechanism section: the paper states that the PoA=2 bound is tight, but the tightness argument for the standard case is not cross-referenced to the modified case, leaving unclear whether the same instance family can be used to show that the new bound cannot be improved beyond 1 + O(1)/(n-1) without additional assumptions.
minor comments (2)
  1. The abstract and main text use the notation 'O(1)' in the bound 1 + O(1)/(n-1); the exact constant or functional form should be stated explicitly (e.g., 1 + 2/(n-1)) to allow verification of the improvement over 2 for small n.
  2. Notation for the liquid welfare objective and the per-bidder budget caps should be introduced once with a clear definition before the KKT mapping is applied, to improve readability of the duality argument.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable feedback on our paper. We address each of the major comments below and outline the revisions we will make to the manuscript.

read point-by-point responses

  1. Referee: [analysis of the modified mechanism] The derivation of the PoA bound 1 + O(1)/(n-1) for the modified mechanism (in the section introducing the alternative payment scheme) maps pure-NE first-order conditions to KKT conditions of the liquid-welfare LP. However, this mapping presupposes the existence of a pure Nash equilibrium under the new payment rule. No existence proof, quasi-concavity argument for the utility function, or invocation of a fixed-point theorem (e.g., Kakutani) is supplied for the modified payment scheme, in contrast to the standard mechanism where PoA=2 is already established. This renders the bound conditional on existence and is load-bearing for the central claim.

    Authors: We acknowledge that the manuscript does not provide an explicit proof of existence for pure Nash equilibria under the modified payment scheme. To address this, we will add a dedicated subsection in the modified mechanism analysis proving existence. Specifically, we will show that the strategy space for each bidder is a compact convex set and that the utility function is continuous and quasi-concave, which allows us to apply Kakutani's fixed-point theorem to guarantee the existence of a pure Nash equilibrium. This revision will render the PoA bound unconditional and strengthen the central claim. revision: yes

  2. Referee: [§3 and modified-mechanism analysis] §3 (standard mechanism) and the modified-mechanism section: the paper states that the PoA=2 bound is tight, but the tightness argument for the standard case is not cross-referenced to the modified case, leaving unclear whether the same instance family can be used to show that the new bound cannot be improved beyond 1 + O(1)/(n-1) without additional assumptions.

    Authors: We appreciate this observation. The tightness of the PoA bound of 2 is established specifically for the standard proportional mechanism using a particular family of instances in Section 3. For the modified mechanism, we prove an upper bound of 1 + O(1)/(n-1) on the PoA but do not assert that this bound is tight. The same instances may not achieve the worst-case ratio under the alternative payment scheme. We will revise the manuscript to include a cross-reference to the tightness proof in Section 3 and add a clarifying remark stating that whether the improved bound is tight remains an open question, potentially requiring additional assumptions or different instances for a matching lower bound. revision: yes

Circularity Check

0 steps flagged

No circularity: PoA bounds derived via external duality and KKT mapping

full rationale

The paper establishes the PoA=2 bound for the standard mechanism and the improved 1+O(1)/(n-1) bound for the modified payment rule by mapping pure-NE first-order conditions to KKT stationarity of the liquid-welfare LP, then invoking duality. This chain uses standard convex-programming facts external to the paper and does not reduce any claimed prediction or bound to a fitted parameter, self-definition, or prior self-citation. The standard bound is re-derived inside the paper rather than imported as a load-bearing premise. No ansatz smuggling, renaming of known results, or uniqueness theorems from overlapping authors appear. The derivation therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The analysis rests on standard mechanism-design assumptions without introducing new free parameters or invented entities.

axioms (2)
  • domain assumption Bidders are rational agents who play pure Nash equilibria
    Invoked throughout the PoA analysis for both mechanisms.
  • domain assumption Quasi-linear utilities and budget constraints define bidder preferences
    Required for the liquid welfare objective and auto-bidding model.

pith-pipeline@v0.9.0 · 5455 in / 1325 out tokens · 60645 ms · 2026-05-10T14:10:19.640453+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Autobidding with con- straints

    Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. Autobidding with con- straints. InProc. 15th Conference on Web and Internet Economics, pages 17–30, 2019

    work page 2019

  2. [2]

    Auto-bidding and auctions in online advertising: A survey.ACM SIGecom Exchanges, 22(1): 159–183, 2024

    Gagan Aggarwal, Ashwinkumar Badanidiyuru, Santiago R Balseiro, Kshipra Bhawalkar, Yuan Deng, Zhe Feng, Gagan Goel, Christopher Liaw, Haihao Lu, Mohammad Mahdian, et al. Auto-bidding and auctions in online advertising: A survey.ACM SIGecom Exchanges, 22(1): 159–183, 2024

    work page 2024

  3. [3]

    Robust auction design in the auto-bidding world.Advances in Neural Information Processing Systems, 34: 17777–17788, 2021

    Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. Robust auction design in the auto-bidding world.Advances in Neural Information Processing Systems, 34: 17777–17788, 2021

    work page 2021

  4. [4]

    Voudouris

    Ioannis Caragiannis and Alexandros A. Voudouris. Welfare guarantees for proportional allo- cations.Theory Comput. Syst., 59(4):581–599, 2016

    work page 2016

  5. [5]

    Voudouris

    Ioannis Caragiannis and Alexandros A. Voudouris. The efficiency of resource allocation mech- anisms for budget-constrained users.Math. Oper. Res., 46(2):503–523, 2021

    work page 2021

  6. [6]

    On the efficiency of the proportional allocation mechanism for divisible resources.Theory Comput

    George Christodoulou, Alkmini Sgouritsa, and Bo Tang. On the efficiency of the proportional allocation mechanism for divisible resources.Theory Comput. Syst., 59(4):600–618, 2016

    work page 2016

  7. [7]

    A social equilibrium existence theorem.Proceedings of the national academy of sciences, 38(10):886–893, 1952

    Gerard Debreu. A social equilibrium existence theorem.Proceedings of the national academy of sciences, 38(10):886–893, 1952

    work page 1952

  8. [8]

    Efficiency of the first- price auction in the autobidding world.Advances in Neural Information Processing Systems, 37:139270–139293, 2024

    Yuan Deng, Jieming Mao, Vahab Mirrokni, Hanrui Zhang, and Song Zuo. Efficiency of the first- price auction in the autobidding world.Advances in Neural Information Processing Systems, 37:139270–139293, 2024

    work page 2024

  9. [9]

    Fixed-point and minimax theorems in locally convex topological linear spaces.Pro- ceedings of the National Academy of Sciences, 38(2):121–126, 1952

    Ky Fan. Fixed-point and minimax theorems in locally convex topological linear spaces.Pro- ceedings of the National Academy of Sciences, 38(2):121–126, 1952

    work page 1952

  10. [10]

    Liquid welfare guarantees for no-regret learning in sequential budgeted auctions

    Giannis Fikioris and Éva Tardos. Liquid welfare guarantees for no-regret learning in sequential budgeted auctions. InProc. 24th Conference on Economics and Computation, pages 678–698, 2023

    work page 2023

  11. [11]

    Budget pacing in repeated auctions: Regret and efficiency without convergence

    Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. Budget pacing in repeated auctions: Regret and efficiency without convergence. In14th Innovations in Theoretical Computer Science Conference, pages 52–1, 2023

    work page 2023

  12. [12]

    A further generalization of the kakutani fixed point theorem, with ap- plication to nash equilibrium points.Proceedings of the American Mathematical Society, 3(1): 170–174, 1952

    Irving L Glicksberg. A further generalization of the kakutani fixed point theorem, with ap- plication to nash equilibrium points.Proceedings of the American Mathematical Society, 3(1): 170–174, 1952

    work page 1952

  13. [13]

    Efficiency loss in a network resource allocation game

    Ramesh Johari and John N Tsitsiklis. Efficiency loss in a network resource allocation game. Mathematics of Operations Research, 29(3):407–435, 2004

    work page 2004

  14. [14]

    Efficiency of scalar-parameterized mechanisms.Opera- tions Research, 57(4):823–839, 2009

    Ramesh Johari and John N Tsitsiklis. Efficiency of scalar-parameterized mechanisms.Opera- tions Research, 57(4):823–839, 2009

    work page 2009

  15. [15]

    Efficiency of non-truthful auctions in auto-bidding: The power of randomization

    Christopher Liaw, Aranyak Mehta, and Andres Perlroth. Efficiency of non-truthful auctions in auto-bidding: The power of randomization. InProceedings of the ACM Web Conference 2023, pages 3561–3571, 2023. 15

    work page 2023

  16. [16]

    Efficiency of non-truthful auctions in auto-bidding with budget constraints

    Christopher Liaw, Aranyak Mehta, and Wennan Zhu. Efficiency of non-truthful auctions in auto-bidding with budget constraints. InProceedings of the ACM Web Conference, pages 223–234, 2024

    work page 2024

  17. [17]

    Autobidders with budget and roi constraints: Efficiency, regret, and pacing dynamics

    Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, and Mengxiao Zhang. Autobidders with budget and roi constraints: Efficiency, regret, and pacing dynamics. InProc. 37th Annual Conference on Learning Theory, pages 3642–3643, 2024

    work page 2024

  18. [18]

    Rajiv Maheswaran and Tamer Basar. Efficient signal proportional allocation (espa) mecha- nisms: Decentralized social welfare maximization for divisible resources.IEEE Journal on Selected Areas in Communications, 24(5):1000–1009, 2006

    work page 2006

  19. [19]

    Auction design in an auto-bidding setting: Randomization improves efficiency beyond vcg

    Aranyak Mehta. Auction design in an auto-bidding setting: Randomization improves efficiency beyond vcg. InProceedings of the ACM Web Conference, pages 173–181, 2022

    work page 2022

  20. [20]

    Composable and efficient mechanisms

    Vasilis Syrgkanis and Eva Tardos. Composable and efficient mechanisms. InProceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 211–220. ACM, 2013

    work page 2013

  21. [21]

    Vcg-kelly mechanisms for allocation of divisible goods: Adapting vcg mechanisms to one-dimensional signals.IEEE Journal on Selected Areas in Communica- tions, 25(6):1237–1243, 2007

    Sichao Yang and Bruce Hajek. Vcg-kelly mechanisms for allocation of divisible goods: Adapting vcg mechanisms to one-dimensional signals.IEEE Journal on Selected Areas in Communica- tions, 25(6):1237–1243, 2007. 16

    work page 2007