Corelab Seminar

Manolis Zampetakis (NTUA)
Mechanism Design with Verification

The basic mechanism design model assumes that each agent can follow any of its strategies, independently of its type. Thus the mechanism cannot use any "real-world" information about the agents. This is the norm in mechanism design and it models well the negotiation stage in which agents do nothing but communicate. A simple type of modification to the model suggests itself: a problem definition may limit the set of strategies A_i available to each agent as a function of its type t_i. In this work we investigate the way mechanism design changes under the assumption of verification. The first deference in the mechanism design with verification is the existence of non-truthful implementations of social choice functions. We present the reason why this way of implementation is not really helpful in the solution concept of dominant strategy equilibrium and we present a way it could be useful using the concept of Nash equilibrium. In this work, we also 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. Since the simplest symmetric verification is the local verification, specific cases of our result are closely related, in the case without money, to the research about the equivalence of local truthfulness and global truthfulness. 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.