Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Simple versus optimal mechanisms

Simple versus optimal mechanisms Simple versus Optimal Mechanisms JASON D. HARTLINE Northwestern University and TIM ROUGHGARDEN Stanford University 1. INTRODUCTION A striking theme in the theory of single-item auctions is that simple auctions are optimal. Foremost, Myerson [Myerson 1981] showed that practically prevalent reserve-price-based auctions are indeed expected revenue-maximizing in natural, though stylized, models. This is fortunate as these auctions are simple and easy to optimize (just set the reserve price). That practitioners widely employ reserveprice-based auctions ” in settings much more complex that those where they are provably optimal ” motivates our rst question: When are reserve-price-based mechanisms approximately optimal? Bulow and Klemperer [Bulow and Klemperer 1996] up the ante further by showing that the reserve price is unnecessary, in the sense that a seller of a single item earns more revenue from the Vickrey auction with one extra bidder than from the optimal auction with the original bidders. This guarantee for an auction even simpler than Vickrey with an optimal reserve motivates our second question: How generally does a Bulow-Klemperer-style result approximately hold? Our recent paper [Hartline and Roughgarden 2009] provides tight approximation guarantees for the expected revenue of simple auctions, relative to that of an optimal auction, in environments http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM SIGecom Exchanges Association for Computing Machinery

Simple versus optimal mechanisms

Download PDF
3 pages

Loading next page...
 
/lp/association-for-computing-machinery/simple-versus-optimal-mechanisms-Mx4K5eaFdV
Publisher
Association for Computing Machinery
Copyright
The ACM Portal is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.
Subject
Modeling methodologies
ISSN
1551-9031
DOI
10.1145/1598780.1598785
Publisher site
See Article on Publisher Site

Abstract

Simple versus Optimal Mechanisms JASON D. HARTLINE Northwestern University and TIM ROUGHGARDEN Stanford University 1. INTRODUCTION A striking theme in the theory of single-item auctions is that simple auctions are optimal. Foremost, Myerson [Myerson 1981] showed that practically prevalent reserve-price-based auctions are indeed expected revenue-maximizing in natural, though stylized, models. This is fortunate as these auctions are simple and easy to optimize (just set the reserve price). That practitioners widely employ reserveprice-based auctions ” in settings much more complex that those where they are provably optimal ” motivates our rst question: When are reserve-price-based mechanisms approximately optimal? Bulow and Klemperer [Bulow and Klemperer 1996] up the ante further by showing that the reserve price is unnecessary, in the sense that a seller of a single item earns more revenue from the Vickrey auction with one extra bidder than from the optimal auction with the original bidders. This guarantee for an auction even simpler than Vickrey with an optimal reserve motivates our second question: How generally does a Bulow-Klemperer-style result approximately hold? Our recent paper [Hartline and Roughgarden 2009] provides tight approximation guarantees for the expected revenue of simple auctions, relative to that of an optimal auction, in environments

Journal

ACM SIGecom Exchanges – Association for Computing Machinery

Published: Jul 1, 2009

References

  • Auctions versus negotiations
    BULOW J.