  We revisit the problem of designing optimal, individually rational matching
mechanisms (in a general sense, allowing for cycles in directed graphs), where
each player --- who is associated with a subset of vertices --- matches as many
of his own vertices when he opts into the matching mechanism as when he opts
out. We offer a new perspective on this problem by considering an arbitrary
graph, but assuming that vertices are associated with players at random. Our
main result asserts that, under certain conditions, any fixed optimal matching
is likely to be individually rational up to lower-order terms. We also show
that a simple and practical mechanism is (fully) individually rational, and
likely to be optimal up to lower-order terms. We discuss the implications of
our results for market design in general, and kidney exchange in particular.
