Constrained Random Matching

I study the problem of object exchange under strict ordinal preferences and with constraints on the ex-post allocations, such as those arising in kidney exchange. Deterministic mechanisms often have poor properties in this environment. I explicitly define an individually rational, ordinally efficient and anonymous random mechanism for the simple case of pairwise kidney exchange, which is based on the Probabilistic Serial mechanism. I then extend the idea behind this mechanism to arrive at a constrained ordinally efficient mechanism regardless of what the ex-post constraints on the outcome are, including individual rationality, limits on the trading-cycle lengths, maximizing the number of exchanges etc. Several mechanisms from the existing literature are special cases of this mechanism.