Header

UZH-Logo

Maintenance Infos

Decomposing random mechanisms


Pycia, Marek; Ünver, M Utku (2015). Decomposing random mechanisms. Journal of Mathematical Economics, 61:21-33.

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 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.

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 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.

Statistics

Citations

Dimensions.ai Metrics
9 citations in Web of Science®
10 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

0 downloads since deposited on 01 Jun 2018
0 downloads since 12 months

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Economics
Dewey Decimal Classification:330 Economics
Scopus Subject Areas:Social Sciences & Humanities > Economics and Econometrics
Physical Sciences > Applied Mathematics
Uncontrolled Keywords:Random mechanisms, total unimodularity, single-peaked preferences, individual rationality, strategy-proofness, universal truthfulness
Language:English
Date:December 2015
Deposited On:01 Jun 2018 12:22
Last Modified:31 Jul 2020 01:50
Publisher:Elsevier
ISSN:0304-4068
OA Status:Closed
Publisher DOI:https://doi.org/10.1016/j.jmateco.2015.06.002

Download

Closed Access: Download allowed only for UZH members

Content: Published Version
Filetype: PDF - Registered users only
Size: 732kB
View at publisher