News Archives

Truthful Adaptive Sponsored Search Mechanisms

March 25, 2008

  • Date: Tuesday, March 25th, 2008 
  • Time: 11 am — 12:15 pm 
  • Place: ME 218

Rica Gonen Yahoo! Research

Abstract: The talk will focus on two recent papers in sponsored search auctions. The first presents a truthful sponsored search auction based on an incentive-compatible multi-armed bandit mechanism. The mechanism described combines several desirable traits.

The mechanism gives advertisers the incentive to report their true bid, learns the click-through rate for advertisements, allows for slots with different quality, and loses the minimum welfare during the sampling process.

The underlying generalization of the multi-armed bandit mechanism addresses the interplay between exploration and exploitation in an online setting that is truthful in high probability while allowing for slots of different quality.

As the mechanism progresses the algorithm more closely approximates the hidden variables (click-though rates) in order to allocate advertising slots to the best advertisements. The resulting mechanism obtains the optimal welfare apart from a tightly bounded loss of welfare caused by the bandit sampling process.

The second paper extends the model of the first paper by allowing for time constrained and budget constrained advertisers who arrive and depart in an online fashion. The paper presents an online sponsored search auction that motivates advertisers to report their true budget, arrival time, departure time, and value per click.

In tackling the problem of truthful budget, arrival and departure times, it turns out that it is not possible to achieve truthfulness in the classical sense. As such, we define a new concept called delta-gain.

delta-gain bounds the utility a player can gain by lying as opposed to his utility when telling the truth. We argue that for many practical applications if the delta-gain is small, then players will not invest time and effort in making strategic choices but will truthtell as a default strategy. These concepts capture the essence of dominant strategy mechanisms as they lead the advertiser to choose truthtelling over other strategies.

In order to achieve delta-gain truthful mechanism this paper also presents a new payment scheme, for an online budget-constrained auction mechanism. The payment scheme is a generalization of the VCG principles for an online scheduling environment with budgeted players.

Using the concepts of delta-gain truthful we present the only known budget-constrained sponsored search auction with truthful guarantees on budget, arrivals, departures, and valuations. Previous works that deal with advertiser budgets only deal with the non-strategic case.

Research Areas: My research focus is mechanism design or essentially any topic that captures the border between computer science theory, game theory and microeconomic theory. Among the topics I work on are: Combinatorial Auctions & Markets, Sponsored Search Mechanisms, Social Networks, Coalitions, Information Markets, Rational Cryptography, RationalDistributed Computation, Online Algorithms and Computation, and Approximation Algorithms.