Abstract
We investigate the reasons that make symmetric partial verification essentially useless in virtually all domains. Departing from previous work, we consider any possible (finite or infinite) domain and general symmetric verification. We identify a natural property, namely that the correspondence graph of a symmetric verification M is strongly connected by finite paths along which the preferences are consistent with the preferences at the endpoints, and prove that this property is sufficient for the equivalence of truthfulness and M-truthfulness. In fact, defining appropriate versions of this property, we obtain this result for deterministic and randomized mechanisms with and without money. Moreover, we show that a slightly relaxed version of this property is also necessary for the equivalence of truthfulness and M-truthfulness. Our conditions provide a generic and convenient way of checking whether truthful implementation can take advantage of any symmetric verification scheme in any domain. Since the simplest case of symmetric verification is local verification, our results imply, as a special case, the equivalence of local truthfulness and global truthfulness in the setting without money. To complete the picture, we consider asymmetric verification, and prove that a social choice function is M-truthfully implementable by some asymmetric verification M if and only if f does not admit a cycle of profitable deviations.
This research was supported by the project AlgoNow, co-financed by the European Union (European Social Fund - ESF) and Greek national funds, through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) - Research Funding Program: THALES, investing in knowledge society through the European Social Fund.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Archer, A., Kleinberg, R.: Characterizing truthful mechanisms with convex type spaces. ACM SIGecom Exchanges 7(3) (2008)
Archer, A., Kleinberg, R.: Truthful germs are contagious: A local-to-global characterization of truthfulness. In: Proc. of the 9th ACM Conference on Electronic Commerce (EC 2008), pp. 21–30 (2008)
Auletta, V., Penna, P., Persiano, G., Ventre, C.: Alternatives to truthfulness are hard to recognize. Autonomous Agents and Multi-Agent Systems 22(1), 200–216 (2011)
Auletta, V., De Prisco, R., Penna, P., Persiano, G.: The power of verification for one-parameter agents. Journal of Computer and System Sciences 75, 190–211 (2009)
Berger, A., Müller, R., Naeemi, S.H.: Characterizing incentive compatibility for convex valuations. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) SAGT 2009. LNCS, vol. 5814, pp. 24–35. Springer, Heidelberg (2009); Updated version as Research Memoranda 035, Maastricht Research School of Economics of Technology and Organization
Caragiannis, I., Elkind, E., Szegedy, M., Yu, L.: Mechanism design: from partial to probabilistic verification. In: Proc. of the 13th ACM Conference on Electronic Commerce (EC 2012), pp. 266–283 (2012)
Carroll, G.: When are local incentive constraints sufficient? Econometrica 80(2), 661–686 (2012)
Fotakis, D., Tzamos, C.: Winner-imposing strategyproof mechanisms for multiple Facility Location games. Theoretical Computer Science 472, 90–103 (2013)
Green, J., Laffont, J.: Partially verifiable information and mechanism design. Review of Economic Studies 53(3), 447–456 (1986)
Gui, H., Müller, R., Vohra, R.V.: Dominant strategy mechanisms with multi-dimensional types. Discussion Paper 1392, Northwestern University (2004)
Krysta, P., Ventre, C.: Combinatorial auctions with verification are tractable. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part II. LNCS, vol. 6347, pp. 39–50. Springer, Heidelberg (2010)
Nisan, N.: Introduction to Mechanism Design (for Computer Scientists). In: Algorithmic Game Theory, ch. 9, pp. 209–241 (2007)
Nisan, N., Ronen, A.: Algorithmic mechanism design. Games and Economic Behavior 35, 166–196 (2001)
Rochet, J.C.: A necessary and sufficient condition for rationalizability in a quasi-linear context. Journal of Mathematical Economics 16(2), 191–200 (1987)
Saks, M.E., Yu, L.: Weak monotonicity suffices for truthfulness on convex domains. In: Proc. of the 6th ACM Conference on Electronic Commerce (EC 2005), pp. 286–293 (2005)
Sato, S.: A sufficient condition for the equivalence of strategy-proofness and nonmanipulability by preferences adjacent to the sincere one. J. Economic Theory 148, 259–278 (2013)
Vohra, R.V.: Mechanism Design: A Linear Programming Approach. Cambridge University Press (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fotakis, D., Zampetakis, E. (2013). Truthfulness Flooded Domains and the Power of Verification for Mechanism Design. In: Chen, Y., Immorlica, N. (eds) Web and Internet Economics. WINE 2013. Lecture Notes in Computer Science, vol 8289. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45046-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-45046-4_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45045-7
Online ISBN: 978-3-642-45046-4
eBook Packages: Computer ScienceComputer Science (R0)