Derandomization of auctions

ABSTRACT

We study the problem of designing seller-optimal auctions, i.e. auctions where the objective is to maximize revenue. Prior to this work, the only auctions known to be approximately optimal in the worst case employed randomization. Our main result is the existence of deterministic auctions that approximately match the performance guarantees of these randomized auctions. We give a fairly general derandomization technique for turning any randomized mechanism into an asymmetric deterministic one with approximately the same revenue. In doing so, we bypass the impossibility result for symmetric deterministic auctions and show that asymmetry is nearly as powerful as randomization for solving optimal mechanism design problems. Our general construction involves solving an exponential-sized flow problem and thus is not polynomial-time computable. To complete the picture, we give an explicit polynomial-time construction for derandomizing a specific auction with good worst-case revenue. Our results are based on toy problems that have a flavor similar to the hat problem from [3].

REFERENCES

• 1: A. Archer , É. Tardos, Truthful Mechanisms for One-Parameter Agents, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.482, October 14-17, 2001
• 2: Avrim Blum , Jason D. Hartline, Near-optimal online auctions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 3: Todd Ebert , John Doner, Applications of recursive operators to randomness and complexity, 1998
• 4: U. Feige. You Can Leave Your Hat On (if you guess its color). Technical Report MCS04-03, Computer Science and Applied Mathematics, The Weizmann Institute of Science, 2004.
• 5: Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Competitive generalized auctions, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509921]
• 6: Andrew V. Goldberg , Jason D. Hartline, Competitiveness via consensus, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 7: A. Goldberg, J. Hartline, A. Karlin, M. Saks, and A. Wright. Competitive auctions and digital goods. Games and Economic Behavior, 2002. Submitted for publication. An earlier version available as InterTrust Technical Report STAR-TR-99.09.01.
• 8: Andrew V. Goldberg , Jason D. Hartline , Andrew Wright, Competitive auctions and digital goods, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.735-744, January 07-09, 2001, Washington, D.C., United States
• 9: Daniel Lehmann , Liaden Ita O'Callaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Proceedings of the 1st ACM conference on Electronic commerce, p.96-102, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337016]
• 10: J. Mirrlees. An Exploration into the Theory of Optimal Income Taxation. Review of Economics Studies, 38:175--208, April 1971.
• 11: H. Moulin and S. Shenker. Strategyproof Sharing of Submodular Costs: Budget Balance vs. Efficiency. Economic Theory, 18:511--533, 2001.
• 12: I. Segal. Optimal Pricing Mechanism with Unknown Demand. American Economic Review, 93:509--29, 2003.
• 13: P. Winkler. Games People don't Play. In D. Wolfe and T. Rogers, editors, Puzzler's tribute. A feast for the mind. A K Peters, 2001.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Keywords:
auctions, derandomization, mechanism design