Decomposing Random Mechanisms

Marek Pycia and Utku Unver

No 870, Boston College Working Papers in Economics from Boston College Department of Economics

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.

Keywords: Random mechanisms; ordinal mechanisms; total unimodularity; singlepeaked preferences; voting; individual rationality; strategy-proofness; unanimity; anonymity; generalized median voter rules; universal truthfulness (search for similar items in EconPapers)
JEL-codes: C60 D71 D72 (search for similar items in EconPapers)
Date: 2014-09-30
New Economics Papers: this item is included in nep-cdm and nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://fmwww.bc.edu/EC-P/wp870.pdf main text (application/pdf)

Related works:
Journal Article: Decomposing random mechanisms (2015)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:boc:bocoec:870

Access Statistics for this paper

More papers in Boston College Working Papers in Economics from Boston College Department of Economics Boston College, 140 Commonwealth Avenue, Chestnut Hill MA 02467 USA. Contact information at EDIRC.
Bibliographic data for series maintained by Christopher F Baum ().