Skip to main content.
Advanced search >
<< Back to previous page Print

<< Monday, May 13, 2013 >>

Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare

[Dissertation Talk] Eliciting Private Information from Selfish Agents

Seminar: Departmental | May 13 | 3-4 p.m. | 606 Soda Hall

Rafael M Frongillo, EECS

Electrical Engineering and Computer Sciences (EECS)

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 of users. 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 and 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.

In the talk, we will see the core model and an important generalization to the *property* case, where agents report some alternate representation of their information rather than reporting it directly. From there we will explore even deeper connections to convex analysis, including several notions of duality, with applications to mechanism design as well as a surprising equivalence between scoring rules, prediction markets, Bregman divergences, and generalized exponential families.