Decomposing random mechanisms

作者：Pycia Marek; Uenver M Utku

来源：Journal of Mathematical Economics, 2015, 61: 21-33.

DOI：10.1016/j.jmateco.2015.06.002

• Random mechanisms
• Total unimodularity
• Single-peaked preferences
• Individual rationality
• Strategy-proofness
• Universal truthfulness

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 the 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. We also introduce a second, more constructive approach to decomposition problems, and prove that feasibility, strategy-proofness, and unanimity, with and without anonymity, are decomposable in non-dictatorial single-peaked voting domains. Just importantly, we establish that strategy-proofness is not decomposable in some natural problems.

• 出版日期2015-12