Eliciting Private Information from Selfish Agents
- Author(s): Frongillo, Rafael M.
- Advisor(s): Papadimitriou, Christos H
- et al.
Ever since the Internet opened the floodgates to millions of users, each looking after their
own interests, modern algorithm design has needed to be increasingly robust to strategic
manipulation. Often, it is the inputs to these algorithms which are provided by strategic
agents, who may lie for their own benefit, necessitating the design of algorithms which
incentivize the truthful revelation of private information - but how can this be done? This is a
fundamental question with answers from many disciplines, from mechanism design to scoring
rules and prediction markets. Each domain has its own model with its own assumptions, yet
all seek schemes to gather private information from selfish agents, by leveraging incentives.
Together, we refer to such models as elicitation.
This dissertation unifies and advances the theory of incentivized information elicitation.
Using tools from convex analysis, we introduce a new model of elicitation with a matching
characterization theorem which together encompass mechanism design, scoring rules, prediction markets, and other models. This lays a firm foundation on which the rest of the
dissertation is built.
It is natural to consider a setting where agents report some alternate representation of
their private information, called a property, rather than reporting it directly. We extend
our model and characterization to this setting, revealing even deeper ties to convex analysis
and convex duality, and we use these connections to prove new results for linear, smooth
nonlinear, and finite-valued properties. Exploring the linear case further, we show a new
four-fold equivalence between scoring rules, prediction markets, Bregman divergences, and
generalized exponential families.
Applied to mechanism design, our framework offers a new perspective. By focusing on
the (convex) consumer surplus function, we simplify a number of existing results, from the
classic revenue equivalence theorem, to more recent characterizations of mechanism implementability.
Finally, we follow a line of research on the interpretation of prediction markets, relating
a new stochastic framework to the classic Walrasian equilibrium and to stochastic mirror
descent, thereby strengthening ties between prediction markets and machine learning.