Weak monotonicity suffices for truthfulness on convex domains

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Weak monotonicity suffices for truthfulness on convex domains

Full text

Pdf (203 KB)

Source

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

Vancouver, BC, Canada

Pages: 286 - 293

Year of Publication: 2005

ISBN:1-59593-049-3

Authors

Michael Saks	Rutgers University, Piscataway, NJ
Lan Yu	Rutgers University, Piscataway, NJ

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 63, Citation Count: 14

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/1064009.1064040 What is a DOI?

ABSTRACT

Weak monotonicity is a simple necessary condition for a social choice function to be implementable by a truthful mechanism. Roberts [10] showed that it is sufficient for all social choice functions whose domain is unrestricted. Lavi, Mu'alem and Nisan [6] proved the sufficiency of weak monotonicity for functions over order-based domains and Gui, Muller and Vohra [5] proved sufficiency for order-based domains with range constraints and for domains defined by other special types of linear inequality constraints. Here we show the more general result, conjectured by Lavi, Mu'alem and Nisan [6], that weak monotonicity is sufficient for functions defined on any convex domain.

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	Yair Bartal , Rica Gonen , Noam Nisan, Incentive compatible multi unit combinatorial auctions, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846250]
	3	S. Bikhchandani, S. Chatterjee, and A. Sen. Incentive compatibility in multi-unit auctions. Technical report, UCLA Department of Economics, Dec. 2004.
	4	A. Goldberg, J. Hartline, A. Karlin, M. Saks and A. Wright. Competitive Auctions, 2004.
	5	H. Gui, R. Muller, and R. Vohra. Dominant strategy mechanisms with multidimensional types. Technical Report 047, Maastricht: METEOR, Maastricht Research School of Economics of Technology and Organization, 2004. available at http://ideas.repec.org/p/dgr/umamet/2004047.html.
	6	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
	7	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]
	8	A. Mas-Colell, M. Whinston, and J. Green. Microeconomic Theory. Oxford University Press, 1995.
	9	N. Nisan. Algorithms for selfish agents. Lecture Notes in Computer Science, 1563:1--15, 1999.
	10	K. Roberts. The characterization of implementable choice rules. Aggregation and Revelation of Preferences, J-J. Laffont (ed.), North Holland Publishing Company.
	11	J.-C. Rochet. A necessary and sufficient condition for rationalizability in a quasi-linear context. Journal of Mathematical Economics, 16:191--200, 1987.
	12	I. Rozenshtrom. Dominant strategy implementation with quasi-linear preferences. Master's thesis, Dept. of Economics, The Hebrew University, Jerusalem, Israel, 1999.

CITED BY 14

	Nir Andelman , Yishay Mansour, A sufficient condition for truthfulness with single parameter agents, Proceedings of the 7th ACM conference on Electronic commerce, p.8-17, June 11-15, 2006, Ann Arbor, Michigan, USA
	Taiki Todo , Atsushi Iwasaki , Makoto Yokoo , Yuko Sakurai, Characterizing false-name-proof allocation rules in combinatorial auctions, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, May 10-15, 2009, Budapest, Hungary
	Vincent Conitzer , Tuomas Sandholm, Failures of the VCG mechanism in combinatorial auctions and exchanges, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	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
	Ron Lavi, Searching for the possibility: impossibility border of truthful mechanism design, ACM SIGecom Exchanges, v.7 n.1, p.25-29, December 2007
	Dov Monderer, Implementable allocation rules, ACM SIGecom Exchanges, v.7 n.2, p.1-3, December 2008
	Ahuva Mu'alem , Michael Schapria, Characterizing truthfulness in discrete domains, ACM SIGecom Exchanges, v.7 n.2, p.1-3, December 2008
	Ahuva Mu'alem , Michael Schapira, Mechanism design over discrete domains, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA
	Aaron Archer , Robert Kleinberg, Characterizing truthful mechanisms with convex type spaces, ACM SIGecom Exchanges, v.7 n.3, p.1-9, November 2008
	Aaron Archer , Robert Kleinberg, Truthful germs are contagious: a local to global characterization of truthfulness, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA
	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
	Moshe Babaioff , Ron Lavi , Elan Pavlov, Mechanism design for single-value domains, Proceedings of the 20th national conference on Artificial intelligence, p.241-247, July 09-13, 2005, Pittsburgh, Pennsylvania
	Changyuan Yu, Truthful mechanisms for two-range-values variant of unrelated scheduling, Theoretical Computer Science, v.410 n.21-23, p.2196-2206, May, 2009
	Itai Ashlagi , Shahar Dobzinski , Ron Lavi, An optimal lower bound for anonymous scheduling mechanisms, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA