This thesis focuses on improving computational and economic aspects of mechanism design, and on improving critical components of integer programming algorithms. Various marketplaces in the world today, from spectrum allocation to strategic sourcing to display advertisements to financial exchanges and more, benefit from carefully engineered rules to govern the efficient exchange of items. Mechanism design offers a principled way to design the rules to such market-based systems in order to implement desired market outcomes subject to strategic self-interested participants. It is the prominent approach to many market design problems and has been deployed in the real world with high impact. On the computational front, integer programming is the go-to method for solving discrete optimization problems that arise in market design applications and beyond.

Within mechanism design, our focus is on the design of better mechanisms that take advantage of any and all information available to the mechanism designer. Our new mechanisms provably generalize and improve the state of the art, and signifi cantly expand the scope of what forms of information can be expressed and used to boost performance. We apply our advances in mechanism design to combinatorial markets where bidders have complex, combinatorial preferences over a rich space of outcomes. Here, our new combinatorial auctions directly improve over existing designs that have been used to conduct high-stakes auctions around the world.

Within integer programming, our focus is on the theory and practice of cutting planes, which are one of the most critical components of integer programming solvers. We invent new cutting planes that deliver strong theoretical and practical performance, and develop a comprehensive generalization theory for data-driven parameter configuration within the branch-and-cut algorithm.

In both areas, we fundamentally advance the classical state of knowledge and introduce new data-driven perspectives, all in support of the thesis that high performance–e.g., revenue, social welfare, run-time, memory, etc.–in marketplaces can only be fully realized by a synergy of approaches in mechanism design, integer programming, and machine learning.

250 pages

Thesis Committee:
Maria-Florina Balcan (Co-Chair)
Tuomas Sandholm (Co-Chair)
Gérard Cornuejols
Craig Boutilier (Google)
Peter Cramton (University of Maryland)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Creative Commons: CC-BY (Attribution)

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu