Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertising

• URL: http://arxiv.org/abs/2604.12799v1
• Date: Tue, 14 Apr 2026 14:29:05 GMT
• Title: Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertising
• Abstract summary: We study the efficiency of pure Nash equilibria, specifically the price of anarchy (PoA) under the liquid welfare objective.<n>We introduce a modified version with an alternative payment scheme that achieves a PoA bound of $1 + fracO(1)n-1$ where $n geq 2$ denotes the number of bidding agents.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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. Despite its conceptual simplicity, our approach proves powerful and may offer broader applications for establishing PoA bounds.

Related papers

• HOBA: Hierarchical On-Policy Bidding Agents for Adaptive Online Advertising [4.325040293861279]
  HOBA is a hierarchical reinforcement learning framework that decouples strategic reasoning, model selection, and bid execution across three time scales.<n> Experiments on the AuctionNet benchmark and a large-scale A/B test demonstrate consistent improvements over state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-06-17T15:00:34Z)
• Model Monotonicity in Autobidding Auctions: When Do Better Predictions Lead to Better Outcomes? [1.2691047660244335]
  We study the interaction between recommender system model quality, auction format, and autobidder behavior.<n>We show that first-price auctions with uniform bidding guarantee revenue monotonicity for tCPA bidders without budgets.<n>Our findings have practical implications for advertising platforms seeking to align model improvements with business outcomes.
  arXiv  Detail & Related papers  (2026-05-29T09:09:06Z)
• Diffusing to Coordinate: Efficient Online Multi-Agent Diffusion Policies [51.24079409973799]
  Diffusion-based generative models are well-positioned to meet the needs of online Multi-Agent Reinforcement Learning (MARL)<n>We propose among the first underlineOnline off-policy underlineMARL framework using underlineDiffusion policies to orchestrate coordination.<n>Our key innovation is a relaxed policy objective that maximizes scaled joint entropy, facilitating effective exploration without relying on tractable likelihood.
  arXiv  Detail & Related papers  (2026-02-20T15:38:02Z)
• SEGB: Self-Evolved Generative Bidding with Local Autoregressive Diffusion [9.051746879211764]
  Self-Evolved Generative Bidding (SEGB) is a framework that plans proactively and refines itself entirely offline.<n>SEGB first synthesizes plausible short-horizon future states to guide each bid, providing the agent with crucial, dynamic foresight.<n>It then performs value-guided policy refinement to iteratively discover superior strategies without any external intervention.
  arXiv  Detail & Related papers  (2025-12-31T09:05:59Z)
• HOB: A Holistically Optimized Bidding Strategy under Heterogeneous Auction Mechanisms with Organic Traffic [23.230940625345372]
  E-commerce advertising platforms typically sell commercial traffic through either second-price auction (SPA) or first-price auction (FPA)<n>For automated bidding systems, such a trend poses a critical challenge: determining optimal strategies across heterogeneous auction channels to fulfill diverse advertiser objectives.<n>We derive an efficient solution for optimal bidding under FPA channels, which takes into account the presence of organic traffic - traffic can be won for free.
  arXiv  Detail & Related papers  (2025-10-17T02:00:09Z)
• Nash Equilibrium Constrained Auto-bidding With Bi-level Reinforcement Learning [64.2367385090879]
  We propose a new formulation of the auto-bidding problem from the platform's perspective.<n>It aims to maximize the social welfare of all advertisers under the $epsilon$-NE constraint.<n>The NCB problem presents significant challenges due to its constrained bi-level structure and the typically large number of advertisers involved.
  arXiv  Detail & Related papers  (2025-03-13T12:25:36Z)
• Procurement Auctions via Approximately Optimal Submodular Optimization [53.93943270902349]
  We study procurement auctions, where an auctioneer seeks to acquire services from strategic sellers with private costs. Our goal is to design computationally efficient auctions that maximize the difference between the quality of the acquired services and the total cost of the sellers.
  arXiv  Detail & Related papers  (2024-11-20T18:06:55Z)
• Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents [52.75161794035767]
  We introduce a class of bandit algorithms that meet the two objectives of performance incentivization and robustness simultaneously.<n>We show that settings where the principal has no information about the arms' performance characteristics can be handled by combining ideas from second price auctions with our algorithms.
  arXiv  Detail & Related papers  (2023-12-13T06:54:49Z)
• Learning Payment-Free Resource Allocation Mechanisms [19.60309632660988]
  We consider the design of mechanisms that limited resources among self-interested agents using neural networks. We contribute a new end-to-end neural network architecture, ExS-Net, that accommodates the idea of "money-burning" for mechanism design without payments.
  arXiv  Detail & Related papers  (2023-11-18T01:21:54Z)
• Robust multi-item auction design using statistical learning: Overcoming uncertainty in bidders' types distributions [6.5920927560926295]
  Our proposed approach utilizes nonparametric density estimation to accurately estimate bidders' types from historical bids. To further enhance efficiency of our mechanism, we introduce two novel strategies for query reduction. Simulation experiments conducted on both small-scale and large-scale data demonstrate that our mechanism consistently outperforms existing methods in terms of revenue design and query reduction.
  arXiv  Detail & Related papers  (2023-02-02T08:32:55Z)
• Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approach [123.55983746427572]
  We propose novel learning algorithms to recover the dynamic Vickrey-Clarke-Grove (VCG) mechanism over multiple rounds of interaction.<n>A key contribution of our approach is incorporating reward-free online Reinforcement Learning (RL) to aid exploration over a rich policy space.
  arXiv  Detail & Related papers  (2022-02-25T16:17:23Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.