IDEAS home Printed from https://ideas.repec.org/p/boc/bocoec/870.html
   My bibliography  Save this paper

Decomposing Random Mechanisms

Author

Listed:
  • Marek Pycia

    () (UCLA)

  • M. Utku Ünver

    (Boston College)

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.

Suggested Citation

  • Marek Pycia & M. Utku Ünver, 2014. "Decomposing Random Mechanisms," Boston College Working Papers in Economics 870, Boston College Department of Economics.
  • Handle: RePEc:boc:bocoec:870
    as

    Download full text from publisher

    File URL: http://fmwww.bc.edu/EC-P/wp870.pdf
    File Function: main text
    Download Restriction: no

    Other versions of this item:

    References listed on IDEAS

    as
    1. Herbert A. Simon, 1955. "A Behavioral Model of Rational Choice," The Quarterly Journal of Economics, Oxford University Press, vol. 69(1), pages 99-118.
    2. Sato, Shin, 2013. "A sufficient condition for the equivalence of strategy-proofness and nonmanipulability by preferences adjacent to the sincere one," Journal of Economic Theory, Elsevier, vol. 148(1), pages 259-278.
    3. Atila Abdulkadiroglu & Tayfun Sönmez, 2003. "School Choice: A Mechanism Design Approach," American Economic Review, American Economic Association, vol. 93(3), pages 729-747, June.
    4. Atila Abdulkadiroglu & Tayfun Sonmez, 1998. "Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems," Econometrica, Econometric Society, vol. 66(3), pages 689-702, May.
    5. Chatterji, Shurojit & Sen, Arunava & Zeng, Huaxia, 2014. "Random dictatorship domains," Games and Economic Behavior, Elsevier, vol. 86(C), pages 212-236.
    6. Vohra,Rakesh V., 2011. "Mechanism Design," Cambridge Books, Cambridge University Press, number 9781107004368.
    7. Chatterji, Shurojit & Roy, Souvik & Sen, Arunava, 2012. "The structure of strategy-proof random social choice functions over product domains and lexicographically separable preferences," Journal of Mathematical Economics, Elsevier, vol. 48(6), pages 353-366.
    8. Gibbard, Allan, 1978. "Straightforwardness of Game Forms with Lotteries as Outcomes," Econometrica, Econometric Society, vol. 46(3), pages 595-614, May.
    9. H. Moulin, 1980. "On strategy-proofness and single peakedness," Public Choice, Springer, vol. 35(4), pages 437-455, January.
    10. Bogomolnaia, Anna & Moulin, Herve, 2001. "A New Solution to the Random Assignment Problem," Journal of Economic Theory, Elsevier, vol. 100(2), pages 295-328, October.
    11. Picot, Jérémy & Sen, Arunava, 2012. "An extreme point characterization of random strategy-proof social choice functions: The two alternative case," Economics Letters, Elsevier, vol. 115(1), pages 49-52.
    12. Ehlers, Lars & Peters, Hans & Storcken, Ton, 2002. "Strategy-Proof Probabilistic Decision Schemes for One-Dimensional Single-Peaked Preferences," Journal of Economic Theory, Elsevier, vol. 105(2), pages 408-434, August.
    13. Gibbard, Allan, 1977. "Manipulation of Schemes That Mix Voting with Chance," Econometrica, Econometric Society, vol. 45(3), pages 665-681, April.
    14. Yasuhito Tanaka, 2003. "An alternative direct proof of Gibbard’s random dictatorship theorem," Review of Economic Design, Springer;Society for Economic Design, vol. 8(3), pages 319-328, October.
    15. Shurojit Chatterji & Arunava Sen & Huaxia Zeng, 2012. "Random Dictatorship Domains," Working Papers 27-2012, Singapore Management University, School of Economics.
    16. Satterthwaite, Mark Allen, 1975. "Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions," Journal of Economic Theory, Elsevier, vol. 10(2), pages 187-217, April.
    17. Jay Sethuraman & Teo Chung Piaw & Rakesh V. Vohra, 2003. "Integer Programming and Arrovian Social Welfare Functions," Mathematics of Operations Research, INFORMS, vol. 28(2), pages 309-326, May.
    18. Peters, Hans & Roy, Souvik & Sen, Arunava & Storcken, Ton, 2014. "Probabilistic strategy-proof rules over single-peaked domains," Journal of Mathematical Economics, Elsevier, vol. 52(C), pages 123-127.
    19. Vohra,Rakesh V., 2011. "Mechanism Design," Cambridge Books, Cambridge University Press, number 9780521179461.
    20. Hylland, Aanund & Zeckhauser, Richard, 1979. "The Efficient Allocation of Individuals to Positions," Journal of Political Economy, University of Chicago Press, vol. 87(2), pages 293-314, April.
    21. Abdulkadiroglu, Atila & Sonmez, Tayfun, 1999. "House Allocation with Existing Tenants," Journal of Economic Theory, Elsevier, vol. 88(2), pages 233-260, October.
    22. Eric Budish & Yeon-Koo Che & Fuhito Kojima & Paul Milgrom, 2013. "Designing Random Allocation Mechanisms: Theory and Applications," American Economic Review, American Economic Association, vol. 103(2), pages 585-623, April.
    23. Gibbard, Allan, 1973. "Manipulation of Voting Schemes: A General Result," Econometrica, Econometric Society, vol. 41(4), pages 587-601, July.
    24. Gabriel Carroll, 2012. "When Are Local Incentive Constraints Sufficient?," Econometrica, Econometric Society, vol. 80(2), pages 661-686, March.
    25. P. C. Fishburn, 1984. "Probabilistic Social Choice Based on Simple Voting Comparisons," Review of Economic Studies, Oxford University Press, vol. 51(4), pages 683-692.
    26. Alvin E. Roth & Uriel G. Rothblum, 1999. "Truncation Strategies in Matching Markets--In Search of Advice for Participants," Econometrica, Econometric Society, vol. 67(1), pages 21-44, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. repec:eee:gamebe:v:109:y:2018:i:c:p:413-435 is not listed on IDEAS
    2. repec:eee:matsoc:v:90:y:2017:i:c:p:28-34 is not listed on IDEAS
    3. Lars EHLERS & Dipjyoti MAJUMDAR & Debasis MISHRA & Arunava SEN, 2016. "Continuity and Incentive Compatibility in Cardinal Voting Mechanisms," Cahiers de recherche 04-2016, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    4. Shurojit Chatterji & Arunava Sen & Huaxia Zeng, 2014. "A CHaracterization of Single-Peaked Preferences via Random Social Choice Functions," Working Papers 13-2014, Singapore Management University, School of Economics.
    5. Chatterji, Shurojit & Sen, Arunava & Zeng, Huaxia, 2016. "A characterization of single-peaked preferences via random social choice functions," Theoretical Economics, Econometric Society, vol. 11(2), May.

    More about this item

    Keywords

    Random mechanisms; ordinal mechanisms; total unimodularity; singlepeaked preferences; voting; individual rationality; strategy-proofness; unanimity; anonymity; generalized median voter rules; universal truthfulness;

    JEL classification:

    • C60 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - General
    • D71 - Microeconomics - - Analysis of Collective Decision-Making - - - Social Choice; Clubs; Committees; Associations
    • D72 - Microeconomics - - Analysis of Collective Decision-Making - - - Political Processes: Rent-seeking, Lobbying, Elections, Legislatures, and Voting Behavior

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:boc:bocoec:870. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Christopher F Baum). General contact details of provider: http://edirc.repec.org/data/debocus.html .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.