Title: Mechanism Design for a Complex World: Relaxing Simplifying Assumptions
Advisor: Anna Karlin
Supervisory Committee: Anna Karlin (Chair), Jacques Lawarree (GSR, Econ), Nikhil Devanur (MSR), Thomas Rothvoss, and Sebastien Bubeck (MSR)
Abstract:
The data used as input for many algorithms today comes from real human beings who have a stake in the outcome. In order to design algorithms that are robust to potential strategic manipulation, the field of algorithmic mechanism design formally models the strategic interests of the individuals and engineers their actions using game theory. However, these models often make simplifying assumptions---e.g., independence of values, independence of distributions, and complement-freeness of values---that limit the applicability of the resulting mechanisms.
This thesis focuses on three research thrusts that each single out a standard simplifying assumption, relax it, and expand the theory of mechanism design without it in order to further our understanding of mechanism design in settings that better model the real world. First, revenue maximization in "interdimensional settings," highly structured correlated settings that sit in between the typically assumed dichotomy of single-dimensional and multi-dimensional settings. Second, simple and approximately optimal mechanism design in a new model of proportional complements. Third, approximate welfare maximization for buyers with interdependent valuations, without single-crossing, and beyond single-parameter settings.