Speaker: Nima Haghpanah, Northwestern University

We generalize the ``marginal revenue'' approach to optimal mechanism design to environments with multi-dimensional agent preferences. This approach can be viewed as a reduction from multi- to single-agent mechanism design. For a single agent, marginal revenue describes the change in performance as a function of the ex ante probability that the agent is served. When the distribution of preferences is well behaved, the optimal mechanism for multiple agents is to serve the agents with the highest marginal revenue. This is a generalization of Myerson's (1981) virtual-value-based construction.

When the distribution of preferences is not well behaved, the marginal revenue approach fails, and so does any virtual-value-based construction. In these environments we consider performance as a function of the interim allocation rule. Given a construction of the performance-optimal mechanism for any interim allocation rule for a single agent, the optimal mechanism for multiple agents can be constructed. The construction requires joint feasibility of the interim allocation rule. This joint feasibility is known as Border's (1991) condition. In general, Border's condition has exponentially many constraints; however, we give a polynomial time separation oracle from which the optimal mechanism can be tractably constructed.