Google Research

Non-Separable Dynamic Mechanism Design

SODA (2021) (to appear)


Dynamic mechanism design expands the scope on what type of allocation rules can be implemented andwhat revenue can be extracted when compared to static mechanisms. The case of separable environments(i.e. one player can be de-allocated while keeping the allocation of the remaining players intact) is verywell understood. The mechanisms in the literature don’t extend to the non-separable environments. Twoprototypical examples of such environments are: (i) public projects, where all players must have the sameallocation; and (ii) non-disposable goods, where each item must be allocated to some player. We show ageneral mechanism that can asymptotically extract the full surplus in such environments. Moreover, we fullycharacterize which abstract mechanism design environments allow for full surplus extraction in the limit. Ourcharacterization is based on the geometry ofachievable utility sets– a convex set characterizing the expectedutility profiles that can be implemented in a static mechanism.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work