Decomposing Random Mechanisms

Abstract

Random mechanisms have been used in real-life situations for reasons such as fairness. Voting and matching are two examples of such situations. We investigate whether desirable properties of a random mechanism survive decomposition of the mechanism as a lottery over deterministic mechanisms that also hold such properties. To this end, we represent properties of mechanisms--such as ordinal strategy-proofness or individual rationality--using linear constraints. Using the theory of totally unimodular matrices from combinatorial integer programming, we show that total unimodularity is a sufficient condition for the decomposability of linear constraints on random mechanisms. As two illustrative examples, we show that individual rationality is totally unimodular in general, and that strategy-proofness is totally unimodular in some individual choice models. However, strategy-proofness, unanimity, and feasibility together are not totally unimodular in collective choice environments in general. We thus introduce a direct constructive approach for such problems. Using this approach, we prove that feasibility, strategy-proofness, and unanimity, with and without anonymity, are decomposable on non-dictatorial single-peaked voting domains.