Mechanism Design via Multi- to Single-agent Reduction

Опубликовано 12 августа 2016, 0:00

Mechanism design can be described as designing algorithms for optimization problems where the input is privately known to selfish agents (i.e., the type of each agent); thus, to obtain an optimal outcome with respect to the actual types, a mechanism must consider agents' incentives for (mis-)reporting their types. A Bayesian mechanism design problem can often be interpreted as an stochastic optimization problem where the agents' types come from known distributions. This problem can usually be solved by a linear program which considers all possible combination of agents' types, which is of exponential size in the type space of each agent. I show that, when (a) agent's type are distributed independently, (b) the objective function is linearly separable over the agents (e.g., revenue or welfare), and (c) outcomes of different agents are coupled by polymatroidal constraints, the problem can be solved optimally in time polynomial in the type space of each agent. Furthermore, for a larger class of environments, I show that such problems can be approximated within a factor of $1/2$ of the optimal. In particular, I show that, for a large class of combinatorial auction problems, if the only coupling constraints are the supply constraints, the problem can be solve within a factor of 1-1/(sqrt(k+3)) of the optimal, assuming that the maximum demand of any agent is no more than 1/k of the supply. The techniques developed for the above problems have applications in online algorithms.