Revenue Monotonicity Under Misspecified Bidders
作者： Robert Kleinberg , Makis Arsenis , Odysseas Drosis
DOI:
关键词:
摘要: We investigate revenue guarantees for auction mechanisms in a model where distribution is specified each bidder, but only some of the distributions are correct. The subset bidders whose correctly (henceforth, "green bidders") unknown to auctioneer. question we address whether auctioneer can run mechanism that guaranteed obtain at least as much revenue, expectation, would be obtained by running an optimal on green only. For single-parameter feasibility environments, find answer depends constraint. matroid using all (including incorrect ones) expectation bidders. any constraint not matroid, there exists way setting and true such opposite conclusion holds.
arxiv.org
harvard.edu参考文章(27)
Stephen E. Morris, Dirk Bergemann, An Introduction to Robust Mechanism Design ,(2013)
Uriel Feige, Joe Kilian, Heuristics for Semirandom Graph Problems Journal of Computer and System Sciences. ,vol. 63, pp. 639- 671 ,(2001) , 10.1006/JCSS.2001.1773
Roger B. Myerson, Optimal Auction Design Mathematics of Operations Research. ,vol. 6, pp. 58- 73 ,(1981) , 10.1287/MOOR.6.1.58
Eric van Damme, Rudolf Müller, Rakesh V. Vohra, Mini special issue: Electronic Market Design Games and Economic Behavior. ,vol. 55, pp. 213- 214 ,(2006) , 10.1016/J.GEB.2006.02.004
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan, Approximation algorithms for semi-random partitioning problems Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 367- 384 ,(2012) , 10.1145/2213977.2214013
Pablo Daniel Azar, Silvio Micali, Parametric digital auctions Proceedings of the 4th conference on Innovations in Theoretical Computer Science - ITCS '13. pp. 231- 232 ,(2013) , 10.1145/2422436.2422464
Peerapong Dhangwatnotai, Tim Roughgarden, Qiqi Yan, Revenue maximization with a single sample Games and Economic Behavior. ,vol. 91, pp. 318- 333 ,(2015) , 10.1016/J.GEB.2014.03.011
A. Blum, J. Spencer, Coloring random and semi-random k -colorable graphs Journal of Algorithms. ,vol. 19, pp. 204- 234 ,(1995) , 10.1006/JAGM.1995.1034
Jason D. Hartline, Tim Roughgarden, Simple versus optimal mechanisms Proceedings of the tenth ACM conference on Electronic commerce - EC '09. pp. 225- 234 ,(2009) , 10.1145/1566374.1566407
Baharak Rastegari, Anne Condon, Kevin Leyton-Brown, Revenue monotonicity in combinatorial auctions ACM SIGecom Exchanges. ,vol. 7, pp. 45- 47 ,(2007) , 10.1145/1345037.1345048