Jamie Morgenstern

Market Algorithms: Incentives, Learning, and Privacy Degree Type: Ph.D. in Computer Science
Advisor(s): Avrim Blum, Frank Pfenning
Graduated: May 2015

Abstract:

In this thesis, we study applications of learning theory and differential privacy in the area of mechanism design. Mechanism design aims to optimize over data held by self-interested agents, each of whom will manipulate that data if doing so causes the mechanism to output something more preferred to the agent. Algorithms with learning-theoretic and privacy guarantees are forced to depend upon their inputs in a limited way, suggesting their usefulness in the design of algorithms with limited capacity for manipulation by strategic agents. We explore the particular applications of designing truthful stable matching algorithms, designing simple auctions (using learning theory to choose revenue-optimal auctions, to find equilibrium strategies, and to learn bidder's valuation distributions), and coordinating strategic agents' behavior in a privacy-preserving manner.

Thesis Committee:
Avrim Blum (Chair)
Ariel Procaccia
Tuomas Sandholm
Michael Kearns (University of Pennsylvania)

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Keywords:
Mechanism design, privacy, learning theory, mechanism design without money