General truthfulness characterizations via convex analysis

We present a model of truthful elicitation which generalizes and extends both mechanisms and scoring rules. Our main result is a characterization theorem, yielding characterizations of mechanisms and scoring rules as special cases, including a new characterization of scoring rules for non-convex sets of distributions. Conceptually, our results clarify the connection between scoring rules and mechanisms and show how phrasing results as statements in convex analysis provides simpler, more general, or more insightful proofs of mechanism design results about implementability and revenue equivalence.

Rafael Frongillo is a postdoc at MSR-NYC. He earned his Ph.D. at UC Berkeley, advised by Christos Papadimitriou and supported by the NDSEG fellowship. His research lies broadly in algorithmic economics, drawing techniques from game theory, convex analysis, machine learning, and dynamical systems. http://www.cs.berkeley.edu/~raf/