ICS 2011
|
|
Welcome to ICS2011
Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 112-124, 978-7-302-24517-9
Tsinghua University Press
We consider the problem of maximizing revenue in prior-free auctions for general single parameter settings. The setting is modeled by an arbitrary downward-closed set system, which captures many special cases such as single item, digital goods and single-minded combinatorial auctions. We relax the truthfulness requirement by the solution concept of Nash equilibria. Implementation by Nash equilibria is a natural and relevant framework in many applications of computer science, where auctions are run repeatedly and bidders can observe others' strategies, but the auctioneer needs to design a mechanism in advance and cannot use any information on the bidders' private valuations. We introduce a worst-case revenue benchmark which generalizes the second price of single item auction and the F2 benchmark, introduced by Goldberg et al., for digital goods. We design a mechanism whose Nash equilibria obtains at least a constant factor of this benchmark and prove that no truthful mechanisms can achieve a constant approximation. Preview: 
|
Copyright 2010-2011, Institute for Computer Science, Tsinghua University, All Rights Reserved.