Jamie Morgenstern

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.