Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertising
About
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 benchmarks
| Task | Dataset | Result | Rank | |
|---|---|---|---|---|
| Price of Anarchy analysis | Auction Setting Budget + RoS Valuation maximizing agents Concave Valuation Functions Pure Nash Equilibrium | -- | 2 | |
| Price of Anarchy analysis | Auction Setting Budget + RoS Mix: both valuation and utility maximizing agents Concave Valuation Functions Pure Nash Equilibrium | Price of Anarchy (PoA)2 | 1 | |
| Price of Anarchy analysis | Auction Setting Budget + RoS, Hybrid agents Concave Valuation Functions (Pure Nash Equilibrium) | PoA1 | 1 | |
| Price of Anarchy analysis | Auction Setting RoS, Valuation maximizing agents Concave Valuation Functions Pure Nash Equilibrium | -- | 1 | |
| Price of Anarchy analysis | Auction Setting RoS Mix: both valuation and utility maximizing agents Concave Valuation Functions Pure Nash Equilibrium | -- | 1 |