mix and match.pdf

Mix and Match Itai Ashlagi Harvard Business School Boston, MA 02163, USA ******@ Felix Fischer Harvard SEAS Cambridge, MA 02138, USA ?******@ Ian A. Kash Harvard SEAS Cambridge, MA 02138, USA ******@ Ariel D. ia Harvard SEAS Cambridge, MA 02138, USA ******@ ABSTRACT Consider a matching problem on a graph where disjoint sets of vertices are privately owned by self-interested agents. An edge between a pair of vertices patibility and allows the vertices to match. We seek a mechanism to maxi- mize the number of matches despite self-interest, with agents that each want to maximize the number of their own ver- tices that match. Each agent can choose to hide some of its vertices, and then privately match the hidden vertices with any of its own vertices that go unmatched by the mecha- nism. A prominent application of this model is to kidney exchange, where agents correspond to hospitals and vertices to donor-patient pairs. Here hospitals may game an ex- change by holding back pairs and harm social welfare. In this paper we seek to design mechanisms that are strat- egyproof, in the sense that agents cannot bene?t from hiding vertices, and approximately maximize e?ciency, ., pro- duce a matching that is close in cardinality to the maximum cardinality matching. Our main result is the design and analysis of the eponymousMix-and-Ma