Mechanism Design for Constrained Matching + Facility Location on Discrete Cycles and Grids

28/06/2017 - 12:00

The theory of two-sided matching (e.g., assigning residents to hospitals, students to schools) has been extensively developed, and it has been applied to design clearinghouse mechanisms in various markets in practice. As the theory has been applied to increasingly diverse types of environments, however, researchers and practitioners have encountered various forms of distributional constraints. As these features have been precluded from consideration until recently, they pose new challenges for market designers. One example of such distributional constraints is a minimum quota, e.g., school districts may need at least a certain number of students in each school in order for the school to operate. In this talk, I present an overview of research on designing mechanisms that work under distributional


In this work we study a facility location problem from a perspective of mechanism design. We focus on the problem of locating a facility deterministically on discrete graphs with cycles, including grids and hypercubes. We further assume that mechanisms are defined for any number
of participating agents, so that we can discuss consistency properties of mechanisms' behavior with respect to the number of agents. One of such well-studied properties is false-name-proofness, requiring that no agent can benefit by adding fake agents into the market. Our contribution is two fold. First, for cycle graphs, we show that there exists a false-name-proof and Pareto efficient mechanism if and only if the underlying graph has at most five vertices. Second, for l*m-grid
graphs (where l,m >= 2), we show that such a mechanism exists if and only if either l=2 or m=2 holds. We finally show that for any n(>2)-dimensional binary-cube graphs, there is no such mechanisms.