Truthful germs are contagious: A local-to-global characterization of truthfulness

• 成果类型: Article
• 署名作者: Archer, Aaron; Kleinberg, Robert
• 署名单位: Alphabet Inc.; Google Incorporated; Cornell University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2014.01.004
• 发表日期: 2014
• 页码: 340-366
• 关键词: Truthful mechanism design; implementation theory; incentive compatibility; Local-to-global characterization; Multi-dimensional types; Cyclic monotonicity; Weak monotonicity; Vortex-freeness; Truthful stitching; Rochet's theorem; Stokes's theorem; Saks-Yu theorem; First-order logic; Orthogonal polynomials

摘要

We study the question of which social choice functions from an abstract type space to a set of outcomes are truthful, i.e., implementable by truthful mechanisms, when utilities are quasi-linear. For convex domains, our main theorem characterizes truthful social choice functions as those satisfying two properties: local weak monotonicity and vortex-freeness. The first of these constrains the function values at any two sufficiently proximal points, while the second asserts that its line integrals around sufficiently small triangular loops must vanish. The characterization implies a local-to-global principle that allows one to deduce truthfulness of a function from its behavior on arbitrarily small neighborhoods of each point. Other consequences include a simple alternate derivation of the Saks-Yu Theorem that weak monotonicity characterizes truthfulness of functions having a convex domain and finite range, and a sufficient condition for constructing truthful functions by stitching together truthful subfunctions on different subsets of the domain. (C) 2014 Published by Elsevier Inc.