Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We study the question of how to easily recognize whether a social choice function f from an abstract type space to a set of outcomes is truthful, i.e. implementable by a truthful mechanism. In particular, if the restriction of f to every "simple" subset of the type space is truthful, does it imply that f is truthful? Saks and Yu proved one such theorem: when the set of outcomes is finite and the type space is convex, a function f is truthful if its restriction to every 2-element subset of the type space is truthful, a condition called weak monotonicity. This characterization fails for infinite outcome sets.

We provide a local-to-global characterization theorem for any set of outcomes (including infinite sets) and any convex space of types (including infinite-dimensional ones): a function f is truthful if its restriction to every sufficiently small 2-D neighborhood about each point is truthful. More precisely, f is truthful if and only if it satisfies local weak monotonicity and is vortex-free, meaning that the loop integral of f over every sufficiently small triangle vanishes. Our results apply equally well to multiple solution concepts, including dominant strategies, Nash and Bayes-Nash equilibrium, and to both deterministic and randomized mechanisms. When the type space is not convex, we show that f is truthful if and only if it extends to a truthful function on the convex hull of the original type space.

We use our characterization theorem to give a simple alternate derivation of the Saks-Yu theorem. Generalizing this, we give a sufficient condition for constructing a truthful function by "stitching together" truthful subfunctions on different subsets of the domain.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: 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
• 3: Sushil Bikhchandani, Shurojit Chatterji, Ron Lavi, Ahuva Mu'alem, Noam Nisan, and Arunava Sen. Weak monotonicity characterizes deterministic dominant strategy implementation. Econometrica, 74(4):1109--1132, July 2006.
• 4: E. H. Clarke. Multipart pricing of public goods. Public Choice, 8:17--33, 1971.
• 5: Theodore Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
• 6: Hongwei Gui, Rudolf Müller, and Rakesh Vohra. Dominant strategy mechanisms with multidimensional types. Research Memorandum 47, METEOR, Maastricht Research School of Economics of Technology and Organization, Maastricht, 2004.
• 7: R. Preston McAfee and John McMillan. Multidimensional incentive compatibility and mechanism design. Journal of Economic Theory, 46:335--354, 1988.
• 8: James Mirrlees. An exploration in the theory of optimum income taxation. Review of Economic Studies, 38:175--208, 1971.
• 9: Dov Monderer, Monotonicity and implementability: extended abstract, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA [doi>10.1145/1386790.1386799]
• 10: Rudolf Müller, Andrés Perea, and Sascha Wolf. A network approach to bayes-nash incentive compatible mechanisms. Games and Economic Behavior, 61(2):344--358, November 2007.
• 11: James R. Munkres. Topology. Prentice Hall, 1975.
• 12: Roger B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58--73, February 1981.
• 13: Kevin Roberts. The characterization of implementable choice rules. In Jean-Jacques Laffont, editor, Aggregation and Revelation of Preferences, pages 321--348. North-Holland, Amsterdam, 1979.
• 14: Jean-Charles Rochet. A necessary and sufficient condition for rationalizability in a quasi-linear context. Journal of Mathematical Economics, 16(2):191--200, April 1987.
• 15: 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]
• 16: Michael Spence. Competitive and optimal responses to signals. Journal of Economic Theory, 7:196--232, 1974.
• 17: William Vickrey. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.
• 18: Rakesh Vohra. Paths, cycles and mechanism design. Working paper, 2007.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Payment schemes

General Terms:
Algorithms, Economics, Theory

Keywords:
mechanism design, truthful, vortex-free, weak monotonicity