STOR Colloquium: Alex Belloni (Duke University)

On Multi-dimensional Mechanism Design: Finite Dimensional Approximations and Efficient Computation
Multi-dimensional mechanism design problems have proven difficult to solve by extending techniques from the one-dimensional case. This problem can be formulated as an infinite-dimensional LP problem. First, we show that this infinite dimensional optimization problem can be approximated arbitrary well by a sequence of finite dimensional linear programming problems with an exponential number of constraint. Second, we provide an efficient method to compute the separation oracle associated with the exponentially many constraints. This implies that our finite dimensional approximation is solvable in polynomial time. Finally, we illustrate how the numerical solutions of the finite dimensional  approximations can provide insights into the nature of optimal solutions to the infinite dimensional problem in particular cases.

Refreshments will be served at 3:30pm in the 3rd floor lobby of Hanes Hall