Tuesday, March 18, 2014, 11:00am
Post-Doctoral Research Associate, Computer Science Department, Cornell University
"A Convex Optimization Approach to Bayesian Mechanism Design"
Abstract: We typically assume the input to an algorithm is not affected by how the algorithm computes its output. However, this assumption fails when the input is reported by strategic agents who have personal preferences over the possible outputs. As an example consider the problem of efficiently assigning a set of items to a group of agents where the input consists of the reported valuations of agents for the items. In Bayesian mechanism design we aim to design algorithms that optimize their expected output by taking into account the effect of agents' strategic manipulation of the reported input, assuming the true distribution of inputs are known.
In this talk we consider an abstract Bayesian mechanism design problem and model it as a convex optimization problem. I present a generic decomposition framework yielding an exponential size reduction in the size of the underlying optimization problem, leading to polynomial time algorithms for computing optimal mechanisms. I then show an extension of this result to settings where agents arrive online in unknown order and must be served immediately.
At the end, I will generalize the above framework to a general class of (online) stochastic optimization problems with multiple independent inputs where the output and the objective can be linearly decomposed across the inputs, while the outputs are coupled by joint feasibility constraints. I will demonstrate two applications of this framework outside mechanism design: (1) an improved algorithm for online stochastic generalized assignment problem, and (2) near optimal multi-choice prophet inequalities.
Bio: Dr. Saeed Alaei is a post-doctoral research associate at the Computer Science Department at Cornell University. He received his Ph.D. from University of Maryland under supervision of Prof. Samir Khuller. His research interests include combinatorial optimization, mechanism design/algorithmic game theory, and online algorithms. The focus of his research is on developing generalmethods and techniques for efficiently solving optimization problems arising in
various contexts with a focus on mechanism design and algorithmic game theory.
Hosted by: EECS Dept.