Optimization-friendly generic mechanisms without money

Date: 

Friday, October 1, 2021, 1:00pm to 2:30pm

PresenterMark Braverman
TopicOptimization-friendly generic mechanisms without money

Fall 2021

The EconCS Group holds an Economics and Computer Science research seminar each semester.

Fall 2021 meetings are held at 1 - 2:30 PM on Fridays. Seminar Coordinators for Fall '21 are Srivatsa R Sai and Daniel Halpern.

Abstract: Our goal is to develop a generic framework for converting modern gradient-descent-based optimization algorithms into mechanisms where inputs come from self-interested agents. We focus on aggregating preferences from n players in a context without money. Special cases of this setting include voting, allocation of items by lottery, and matching. Our key technical contribution is a new meta-algorithm we call APEX (Adaptive Pricing Equalizing Externalities). The framework is sufficiently general to be combined with any optimization algorithm that is based on local search. In the talk, I'll outline the algorithm and open problem/research directions that it raises, with a particular focus towards mechanism design + ML. If time permits, I will discuss a special case of applying the framework to the problem of one-sided allocation with lotteries. In this case, we obtain a strengthening of the 1979 result by Hylland and Zeckhauser on allocation via a competitive equilibrium from equal incomes (CEEI). The [HZ79] result posits that there is a (fractional) allocation and a set of item prices such that the allocation is a competitive equilibrium given prices. We further show that there is always a reweighing of the players' utility values such that running the standard unit-demand VCG with reweighed utilities leads to HZ-equilibrium prices. Interestingly, not all HZ competitive equilibria come from VCG prices.