  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
indicates compatibility and allows the vertices to match. We seek a mechanism
to maximize the number of matches despite self-interest, with agents that each
want to maximize the number of their own vertices 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 mechanism. 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 exchange by holding back pairs and harm social welfare. In this paper
we seek to design mechanisms that are strategyproof, in the sense that agents
cannot benefit from hiding vertices, and approximately maximize efficiency,
i.e., produce a matching that is close in cardinality to the maximum
cardinality matching. Our main result is the design and analysis of the
eponymous Mix-and-Match mechanism; we show that this randomized mechanism is
strategyproof and provides a 2-approximation. Lower bounds establish that the
mechanism is near optimal.
