Computer Science Thesis Proposal
Location:
In Person
-
Gordon Bell Conference Room, Gates Hillman 5117
Speaker:
SIDDHARTH PRASAD
,
Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://sid-prasad.github.io/
Mechanism Design and Integer Programming in the Data Age
Modern-day human-scale marketplaces such as recommender systems, advertisement markets, matching platforms, supply chain industries, electronic commerce platforms, and others must reckon with a balancing act of (i) understanding and respecting the incentives of the system's participants, (ii) obtaining optimal outcomes subject to those incentives, and (iii) ensuring that data is used in a sound manner to improve overall efficiency. The area of mechanism design from economics provides a rich language and toolkit to understand incentives and integer programming is an expressive optimization language that is the workhorse behind most practical solutions to real-world discrete optimization problems. This thesis studies how data-driven decisions can be integrated into fundamental algorithms from both areas to improve performance (economic, memory, run-time, etc.).
Within mechanism design, I focus on the design of revenue optimal mechanisms from a data-driven lens. I design algorithms, model new learning paradigms, and invent new mechanism classes for a variety of settings including two-part tariffs, combinatorial auctions, shrinking markets, and general multi-dimensional mechanism design. A highlight here is the first general tunable framework for integrating side information into mechanisms to boost revenue while preserving welfare and incentives. Within integer programming, I develop principled new methods for cutting plane configuration, which is one of the most important components in state-of-the-art branch-and-cut solvers. I develop a comprehensive generalization theory for cut selection that (i) unveils new geometric and combinatorial structure in the branch-and-cut algorithm and the class of Gomory cuts, (ii) improves and subsumes prior work via an abstract model of the underlying tree search, and (iii) is validated through experiments that demonstrate the impact of data-dependent parameter tuning. I also derive a new method of sequence-independent lifting for cutting planes that I validate through rigorous theory—by deriving broad conditions under which the new cuts define facets of the integer polytope—and extensive experiments.
I conclude with avenues for future work; most notably my preliminary ideas on combinatorial auctions with side information which calls for a blend of innovations in auction design and integer programming techniques.
Thesis Committee:
Maria-Florina Balcan (Co-chair)
Tuomas Sandholm (Co-chair)
Gérard Cornuéjols
Craig Boutilier (Google Research)
Peter Cramton (University of Maryland)