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.

151 pages

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

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu