Envy-Free Sponsored Search Auctions with Budgets

Bo Tang, Jinshan ZhangIJCAI 2015

Abstract

This paper investigates the design of envy-free sponsored search auctions in the presence of strict bidder budget constraints. Budget constraints introduce discontinuities in utility functions, rendering standard auction models like Generalized Second Price (GSP) inadequate. The authors characterize envy-freeness in this setting and propose a suite of algorithms, including an optimal mechanism for proportional bidder types and a Polynomial Time Approximation Scheme (PTAS) for general cases, to balance social welfare and platform revenue.

Introduction

In digital advertising, sponsored search auctions determine the placement and pricing of ads. Traditional models often assume bidders have quasi-linear utilities and infinite budgets. However, real-world advertisers operate under strict financial limits. When budgets are considered, an advertiser's utility becomes a discontinuous function of price: they derive value from clicks only as long as they can afford them. This "budget cliff" complicates the pursuit of fairness and efficiency.

The authors focus on envy-freeness, a criterion where no bidder prefers another's outcome (position and price) over their own, provided it is affordable. While well-defined in simple markets, budget constraints make achieving envy-freeness alongside social welfare maximization a significant challenge.

Theoretical Foundations

The researchers establish three fundamental properties of envy-free outcomes with budgets:

  1. Consistency: Higher-quality positions (higher click-through rates) must command higher prices.
  2. Monotonicity: Among bidders with identical budgets, those with higher valuations per click must be allocated superior positions.
  3. Transitivity: Fairness constraints can be logically chained across the set of bidders to ensure global envy-freeness.

Algorithmic Solutions

The paper introduces two primary mechanisms based on bidder characteristics:

  • Proportional Bidder Auction: For cases where "wealth" (budget) correlates with "valuation" (proportional types), the authors propose a deterministic auction that is proven to be both social-optimal and bidder-optimal.
  • General PTAS: For arbitrary bidder types, the problem becomes computationally harder. The authors develop a Polynomial Time Approximation Scheme (PTAS) that discretizes budgets and employs dynamic programming to find an $\epsilon$-envy-free allocation that maximizes welfare.

The Complexity of General Bidder Types

A key contribution of the paper is demonstrating the inherent trade-offs in general settings. Through specific constructed scenarios, the authors prove that it is mathematically impossible for a single auction to simultaneously maximize social welfare and minimize bidder payments (bidder-optimality) for all possible bidder configurations.

Figure 1: An illustration of a bipartite matching between bidders with specific valuations and budgets $(v_i, B_i)$ and positions with varying click-through rates $q_i$. This scenario helps demonstrate the constraints imposed by envy-freeness in budgeted environments.

Key Insights and Results

  • The Budget "Cliff": Budgets transform the auction landscape. An advertiser's preference for a slot is dictated not just by its value but by its affordability, creating utility discontinuities.
  • Fairness vs. Truthfulness: The authors prioritize envy-freeness over incentive compatibility (truthfulness). They argue that in long-term market environments, perceived fairness is often more critical for advertiser retention than preventing strategic misreporting.
  • Computational Efficiency: The PTAS runs in $O((n^2m/\epsilon)^{1/\epsilon})$ time. While the exponent depends on the desired precision, it remains polynomial in the number of bidders ($n$) and positions ($m$), offering a practical path for near-optimal allocations.

Conclusion

This work provides a rigorous framework for understanding envy-freeness in budgeted auctions. By identifying the "proportional" class as a tractable special case and providing approximation schemes for the general case, the authors bridge the gap between theoretical fairness and practical auction design. Future work may extend these concepts to more complex combinatorial auctions and multi-item matching markets.

Summary updated

BibTeX
@inproceedings{tang2015envy,
  author = {Bo Tang and Jinshan Zhang},
  title = {{Envy-Free Sponsored Search Auctions with Budgets}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure