Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertising

A new research paper by Nguyen Kim Thang tackles a core problem in the multi-billion dollar online advertising market: the efficiency of auctions when automated bidding agents are involved. The work focuses on 'proportional mechanisms,' a common auction format, and analyzes their performance using game theory's Price of Anarchy (PoA) metric under a 'liquid welfare' objective. The researcher first established that the standard proportional mechanism has a tight PoA bound of 2, meaning the worst-case efficiency loss can be up to 50% compared to an optimal outcome.

Crucially, Thang then introduced a modified version of the mechanism with an alternative payment scheme. This new design achieves a dramatically improved PoA bound of 1 + O(1)/(n-1), where 'n' is the number of bidding agents (advertisers). This bound breaks the previously known barrier of 2 and, importantly, approaches 1 (representing full efficiency) as the number of agents increases. The methodology leverages advanced mathematical tools from optimization, including duality theory and Karush-Kuhn-Tucker (KKT) conditions, to prove these bounds. The conceptual simplicity of the modified payment rule suggests it could be practically implementable by major ad platforms like Google Ads or Meta Ads to reduce economic waste.

The findings are significant because they provide a theoretical blueprint for making automated ad auctions more efficient at scale. As auto-bidding tools become ubiquitous, ensuring the underlying auction mechanics are robust and fair is critical for platform health and advertiser ROI. This research moves the field beyond known limitations and offers a path toward near-optimal allocation of ad inventory, which could translate to better value for advertisers and potentially lower costs for end consumers.