Events

Previous month Previous day Next day Next month
See by year See by month See by week See Today Search Jump to month

     

Tuesday, March 18, 2014, 11:00am

   

saeed alaeiDr. Saeed Alaei

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.

 

 

 

 


Location Tech Toom L324
Tuesday, March 18, 2014 at 11:00am
Contact Amanda Zarate at amandaz@eecs.northwestern.edu or 847-491-3451

  Download as iCal file

Back