Mechanism Design for a Complex World: Rethinking Standard Assumptions

Thesis (Ph.D.)--University of Washington, 2019The 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. The primary research directions in this area concern designing mechanisms to maximize either revenue or social welfare when selling to agents of various valuation types. This thesis addresses barriers to progress in three fundamental directions in auction theory by rethinking standard models and assumptions and provides positive results in all three cases. First, we design revenue-optimal mechanisms in ``interdimensional'' settings---highly structured correlated settings that sit in between the assumed dichotomy of single-dimensional and multi-dimensional settings. Second, we propose a new model of proportional complementarities and construct an intuitive, simple mechanism that guarantees near-optimal revenue. Third, we study welfare maximization in the interdependent values setting without the single-crossing condition, and guarantee strong approximations for the most general setting of combinatorial auctions