Optimal mechanism design and money burning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal mechanism design and money burning

Full text

Pdf (261 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the 40th annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

SESSION: 3A table of contents

Pages 75-84

Year of Publication: 2008

ISBN:978-1-60558-047-0

Authors

Jason D. Hartline	Northwestern University, Evanston, IL, USA
Tim Roughgarden	Stanford University, Stanford, CA, USA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 64, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1374376.1374390 What is a DOI?

ABSTRACT

Mechanism design is now a standard tool in computer science for aligning the incentives of self-interested agents with the objectives of a system designer. There is, however, a fundamental disconnect between the traditional application domains of mechanism design (such as auctions) and those arising in computer science (such as networks): while monetary "transfers" (i.e., payments) are essential for most of the known positive results in mechanism design, they are undesirable or even technologically infeasible in many computer systems. Classical impossibility results imply that the reach of mechanisms without transfers is severely limited. Computer systems typically do have the ability to reduce service quality--routing systems can drop or delay traffic, scheduling protocols can delay the release of jobs, and computational payment schemes can require computational payments from users (e.g., in spam-fighting systems). Service degradation is tantamount to requiring that users "burn money", and such "payments" can be used to influence the preferences of the agents at a cost of degrading the social surplus. We develop a framework for the design and analysis of "money-burning mechanisms" to maximize the residual surplus-the total value of the chosen outcome minus the payments required. Our primary contributions are the following. * We define a general template for prior-free optimal mechanism design that explicitly connects Bayesian optimal mechanism design, the dominant paradigm in economics, with worst-case analysis. In particular, we establish a general and principled way to identify appropriate performance benchmarks in prior-free mechanism design. * For general single-parameter agent settings, we characterize the Bayesian optimal money-burning mechanism. * For multi-unit auctions, we design a near-optimal prior-free money-burning mechanism: for every valuation profile, its expected residual surplus is within a constant factor of our benchmark, the residual surplus of the best Bayesian optimal mechanism for this profile. * For multi-unit auctions, we quantify the benefit of general transfers over money-burning: optimal money-burning mechanisms always obtain a logarithmic fraction of the full social surplus, and this bound is tight.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Archer, C. Papadimitriou, K. Tawar, and E. Tardos. An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents. In SODA '03.
	2	A. Archer and E. Tardos. Frugal path mechanisms. ACM TALG, 3(1):Article 3, 2007.
	3	K. Arrow. Social Choice and Individual Values. Wiley, 1951.
	4	M. Balcan, A. Blum, J. Hartline, and Y. Mansour. Mechanism design via machine learning. In FOCS '05.
	5	S. Chakravarty and T. R. Kaplan. Manna from heaven or forty years in the desert: Optimal allocation without transfer payments. Working paper, 2006.
	6	G. Christodoulou, E. Koutsoupias, and A. Nanavati. Coordination mechanisms. In ICALP '04, pages 345--357.
	7	E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
	8	R. Cole, Y. Dodis, and T. Roughgarden. How much can taxes help selfish routing? JCSS, 72(3):444--467, 2006.
	9	D. Condorelli. Weak cartels at standard auctions. Working paper, 2007.
	10	C. Dwork, A. Goldberg, and M. Naor. On memory-bound functions for fighting spam. In CRYPTO' 03, pages 426--444.
	11	C. Dwork and M. Naor. Pricing via processing or combating junk mail. In CRYPTO '92, pages 139--147.
	12	E. Elkind, A. Sahai, and K. Steiglitz. Frugality in path auctions. In SODA '04, pages 701--709.
	13	U. Feige, A. Flaxman, J. Hartline, and R. Kleinberg. On the Competitive Ratio of the Random Sampling Auction. In WINE '05, pages 878--886.
	14	J. Feigenbaum, C. Papadimitriou, and S. Shenker. Sharing the cost of multicast transmissions. JCSS, 63(1):21--41, 2001.
	15	J. Feigenbaum, M. Schapira, and S. Shenker. Distributed algorithmic mechanism design. In Nisan et al. \citeAGT, chapter 14, pages 363--384.
	16	A. Fiat, A. Goldberg, J. Hartline, and A. Karlin. Generalized competitive auctions. In STOC '02, pages 72--81.
	17	A. Gibbard. Manipulation of voting schemes: a general result. Econometrica, 41:211--215, 1973.
	18	A. V. Goldberg, J. D. Hartline, A. Karlin, M. Saks, and A. Wright. Competitive auctions. Games and Economic Behavior, 55:242--269, 2006.
	19	A. V. Goldberg, J. D. Hartline, and A. Wright. Competitive auctions and digital goods. In SODA '01, pages 735--744.
	20	T. Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
	21	M. Guo and V. Conitzer. Worst-case optimal redistribution of VCG payments. In EC '07, pages 30--39.
	22	J. Hartline and A. Karlin. Profit maximization in mechanism design. In Nisan et al. \citeAGT, chapter 13, pages 331--362.
	23	A. Karlin, D. Kempe, and T. Tamir. Beyond VCG: Frugality in truthful mechanisms. In FOCS '05, pages 615--626.
	24	H. Levin, M. Schapira, and A. Zohar. Interdomain routing and games. In STOC '08. To appear.
	25	D. Liu and J. Camp. Proof of work can work. In Fifth Workshop on the Economics of Info. Sec., 2006.
	26	P. McAfee and J. McMillan. Bidding rings. American Economic Review, 82:579--599, 1992.
	27	H. Moulin. Efficient, strategy-proof and almost budget-balanced assignment. Working Paper, 2007.
	28	R. Myerson. Optimal auction design. Mathematics of Operations Research, 6:58--73, 1981.
	29	N. Nisan, T. Roughgarden, É. Tardos, and V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007.
	30	J. Riley and W. Samuelson. Optimal auctions. American Economic Review, 71:381--92, 1981.
	31	T. Roughgarden. Selfish Routing and the Price of Anarchy. MIT Press, 2005.
	32	M. Satterthwaite. Strategy-proofness and Arrow's condition: Existence and correspondence theorems for voting proceedures and social welfare functions. Journal of Economic Theory, pages 187--217, 1975.
	33	J. Schummer and R. V. Vohra. Mechanism design without money. In Nisan et al. \citeAGT, chapter 10, pages 243--265.
	34	K. Talwar. The price of truth: Frugality in truthful mechanisms. In STACS '03, pages 608--619.
	35	W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. J. of Finance, 16:8--37, 1961.