Implementability of social choice functions

• Main Author: Yu, Lan
• Other Authors: School of Physical and Mathematical Sciences
• Format: Theses and Dissertations
• Language: English
• Published: 2014
• Subjects: DRNTU::Science::Mathematics::Applied mathematics::Game theory; DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: http://hdl.handle.net/10356/55608
• Institution: Nanyang Technological University

Algorithmic mechanism design is concerned with designing algorithms that implement a desired outcome-selecting function (called a social choice function), while taking into account the participating agents' selfish behavior. This work concentrates on a general and fundamental question of this field: which social choice functions are implementable? A truthful implementation incentivizes all agents to report their preferences truthfully. In the standard model of mechanism design, the renowned Revelation Principle implies that implementability equals truthful implementability. Towards obtaining useful characterizations of truthful social choice functions, this work includes two contributions. First, we prove the conjecture that weak monotonicity is sufficient for truthfulness for functions defined on a convex domain. The other characterization deals with the domain defined by one-dimensional single facility location game. The set of implementable functions is enriched when we allow assumptions on the center's ability to verify agents' inputs. Verification models give rise to non-truthful implementations and the set of truthfully implementable functions may also be enlarged. We discover inherent limitations of the existing partial verification model and propose the probabilistic verification model. In this model, a lie may be caught with certain probability; and if no lie is safe, every social choice function is truthfully implementable. We also investigate non-truthful implementations and optimal implementations that minimize center's expected payment.