Mechanism design over discrete domains

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Mechanism design over discrete domains

Full text

Pdf (358 KB)

Source

Electronic Commerce archive
Proceedings of the 9th ACM conference on Electronic commerce table of contents

Chicago, Il, USA

SESSION: Characterizing incentive compatibility table of contents

Pages 31-37

Year of Publication: 2008

ISBN:978-1-60558-169-9

Authors

Ahuva Mu'alem	California Institute of Technology
Michael Schapira	Hebrew University of Jerusalem, Israel

Sponsors

ACM: Association for Computing Machinery
SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 70, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/1386790.1386797 What is a DOI?

ABSTRACT

Often, we wish to design incentive-compatible algorithms for settings in which the players' private information is drawn from discrete domains (e.g., integer values). Our main result is identifying discrete settings in which an algorithm can be made incentive-compatible iff the function it computes upholds a simple monotonicity constraint, known as weak-monotonicity. To the best of our knowledge, this is the first such characterization of incentive-compatibility in discrete domains (such characterizations were previously known only for inherently non-discrete domains, e.g., convex domains). We demonstrate the usefulness of this result by showing an application to the TCP-inspired congestion-control problem presented in [20].

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 , É. 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	Aaron Archer , Éva Tardos, Frugal path mechanisms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.991-999, January 06-08, 2002, San Francisco, California
	3	S. Bikhchandani, S. Chatterji, R. Lavi, A. Mu'alem, N. Nisan, and A. Sen. Weak monotonicity characterizes deterministic dominant strategy implementation. Econometrica, 74(4):1109--1132, July 2006.
	4	George Christodoulou, Elias Koutsoupias, and Annamaria Kovacs. Mechanism design for fractional scheduling on unrelated machines. In Lars Arge, Christian Cachin, Tomasz Jurdzinski, and Andrzej Tarlecki, editors, ICALP, volume 4596 of Lecture Notes in Computer Science, pages 40--52. Springer, 2007.
	5	George Christodoulou , Elias Koutsoupias , Angelina Vidali, A lower bound for scheduling mechanisms, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1163-1170, January 07-09, 2007, New Orleans, Louisiana
	6	V.G. Deineko and G. Woeginger. Some problems around travelling salesmen, dart boards, and euro-coins. Bulletin of the European Association for Theoretical Computer Science, 90:43--52, October 2006.
	7	A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
	8	Andrew Goldberg, Jason Hartline, Anna Karlin, and Andrew Wright. Competitive auctions, 2004. Working paper. Preliminary versions presented at SODA'01 and STOC'02.
	9	Hongwei Gui, Rudolf Muller, and Rakesh Vohra. Characterizing dominant strategy mechanisms with multi-dimensional types, 2004. Working paper.
	10	Ron Lavi , Ahuva Mu'alem , Noam Nisan, Towards a Characterization of Truthful Combinatorial Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.574, October 11-14, 2003
	11	Ron Lavi , Chaitanya Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250947]
	12	Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002 [doi>10.1145/585265.585266]
	13	William S. Lovejoy, Optimal Mechanisms with Finite Agent Types, Management Science, v.52 n.5, p.788-803, May 2006 [doi>10.1287/mnsc.1050.0502]
	14	Dov Monderer. Monotonicity and implementability, 2007. Working paper.
	15	Ahuva Mu'alem , Michael Schapira, Setting lower bounds on truthfulness: extended abstract, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1143-1152, January 07-09, 2007, New Orleans, Louisiana
	16	Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35:166--196, 2001.
	17	Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007
	18	J.C. Rochet. A necessary and sufficient condition for rationalizability in a quasi-linear context. Journal of Mathematical Economics, 16:191--200, 1987.
	19	Michael Saks , Lan Yu, Weak monotonicity suffices for truthfulness on convex domains, Proceedings of the 6th ACM conference on Electronic commerce, p.286-293, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064040]
	20	Michael Schapira and Aviv Zohar. Congestion-control games, 2008. Working paper.
	21	Lan Yu. Private communication, 2005.