Saeed Alaei

Research Scientist

A Convex Optimization Approach to Bayesian Mechanism Design

  Computer Engineering Department, Floor 4, Kharazmi Hall
  Wednesday, 30 December 2015
  15:10 - 16:10

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 is 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

Saeed Alaei is a research scientist at Google. He received a Ph.D in Computer Science from University of Maryland-College Park. He was a postdoctoral research associate at Cornell University prior to joining Google. His research interests include combinatorial and convex optimization, mechanism design/algorithmic game theory, and online algorithms. The focus of his research is on developing general algorithms and techniques for efficiently solving optimization problems arising in various contexts with a focus on mechanism design and algorithmic game theory.