Saeed Alaei
Abstract:
We typically assume that the input to an algorithm is not affected by how the algorithm computes its output. However this assumption is not true when the input comes from strategic agents who have their own preferences over the possible outcomes of the algorithm. An example of this is the problem of matching a set of items to a set of agents where the input consists of the reported valuations of the agents for the items. A mechanism is an algorithm that takes into account the incentives of the agents. Without loss of generality we restrict our attention to truthful mechanisms, i.e., those which incentivize agents to report truthfully (usually through some payment). In Bayesian mechanism design, typically the goal is to design a truthful mechanism to maximize an objective (e.g., welfare, revenue, etc) in expectation assuming that the distribution of the input is known. Enforcing truthfulness requires the mechanism to simultaneously optimize over all possible profiles of reports by the agents; consequently the size of the underlying optimization problem grows exponentially in the number of agents.
We propose a general framework for solving optimization problems arising in Bayesian mechanism design in polynomial time. Our framework is based on reducing the multi-agent optimization problem to a set of almost disjoint single agent problems. Our work also reveals interesting qualitative characteristics of optimal mechanisms.
Our main techniques can also be applied to any stochastic optimization problem of the following abstract form: we would like to select (possibly at random) a point x from R^d so as to maximize the the value of a concave objective function R(E[x]), i.e., the objective function depends only on the expected value of x; the set of feasible choices for x depends on a random variable t with known distribution D; for each realization of t, the set of feasible choices for x, denoted by X_t, is a bounded subset of R^d. Formally, the problem is to identify a selection policy, say s, which maps each realization of t to a distribution over X_t, with the objective of maximizing R(E_{t~D}[E_{x~s(t)}[x]]). It is enough if we construct an oracle that can compute s(t) for any given t.
Part of this talk is a joint work with Hu Fu, Nima Haghpanah, Jason Hartline and Azarakhsh Malekian and part of it is from my Ph.D. thesis.