IDEAS home Printed from https://ideas.repec.org/p/arx/papers/1906.09671.html
   My bibliography  Save this paper

Single-crossing Implementation

Author

Listed:
  • Nathann Cohenn
  • Edith Elkind
  • Foram Lakhani

Abstract

An election over a finite set of candidates is called single-crossing if, as we sweep through the list of voters from left to right, the relative order of every pair of candidates changes at most once. Such elections have many attractive properties: e.g., their majority relation is transitive and they admit efficient algorithms for problems that are NP-hard in general. If a given election is not single-crossing, it is important to understand what are the obstacles that prevent it from having this property. In this paper, we propose a mapping between elections and graphs that provides us with a convenient encoding of such obstacles. This mapping enables us to use the toolbox of graph theory in order to analyze the complexity of detecting nearly single-crossing elections, i.e., elections that can be made single-crossing by a small number of modifications.

Suggested Citation

  • Nathann Cohenn & Edith Elkind & Foram Lakhani, 2019. "Single-crossing Implementation," Papers 1906.09671, arXiv.org.
    • Handle: RePEc:arx:papers:1906.09671
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/1906.09671
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Bredereck, Robert & Chen, Jiehua & Woeginger, Gerhard J., 2016. "Are there any nicely structured preference profiles nearby?," Mathematical Social Sciences, Elsevier, vol. 79(C), pages 61-73.
    2. Roberts, Kevin W. S., 1977. "Voting over income tax schedules," Journal of Public Economics, Elsevier, vol. 8(3), pages 329-340, December.
    3. Robert Bredereck & Jiehua Chen & Gerhard Woeginger, 2013. "A characterization of the single-crossing domain," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 41(4), pages 989-998, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jiehua Chen & Kirk R. Pruhs & Gerhard J. Woeginger, 2017. "The one-dimensional Euclidean domain: finitely many obstructions are not enough," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(2), pages 409-432, February.
    2. Jiehua Chen & Sven Grottke, 2021. "Small one-dimensional Euclidean preference profiles," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(1), pages 117-144, July.
    3. Slinko, Arkadii & Wu, Qinggong & Wu, Xingye, 2021. "A characterization of preference domains that are single-crossing and maximal Condorcet," Economics Letters, Elsevier, vol. 204(C).
    4. Bredereck, Robert & Chen, Jiehua & Woeginger, Gerhard J., 2016. "Are there any nicely structured preference profiles nearby?," Mathematical Social Sciences, Elsevier, vol. 79(C), pages 61-73.
    5. Edith Elkind & Piotr Faliszewski & Piotr Skowron, 2020. "A characterization of the single-peaked single-crossing domain," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(1), pages 167-181, January.
    6. Alexander Karpov, 2017. "Preference Diversity Orderings," Group Decision and Negotiation, Springer, vol. 26(4), pages 753-774, July.
    7. Persson, Torsten & Tabellini, Guido, 2002. "Political economics and public finance," Handbook of Public Economics, in: A. J. Auerbach & M. Feldstein (ed.), Handbook of Public Economics, edition 1, volume 3, chapter 24, pages 1549-1659, Elsevier.
    8. Smeulders, B., 2018. "Testing a mixture model of single-peaked preferences," Mathematical Social Sciences, Elsevier, vol. 93(C), pages 101-113.
    9. Imrohoroglu, Ayse & Merlo, Antonio & Rupert, Peter, 2000. "On the Political Economy of Income Redistribution and Crime," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 41(1), pages 1-25, February.
    10. Lourdes ROJAS RUBIO, 2022. "Inequality, Corruption and Support for Democracy," THEMA Working Papers 2022-20, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
    11. Georges Casamatta & Helmuth Cremer & Philippe De Donder, 2010. "Repeated electoral competition over nonlinear income tax schedules," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 35(4), pages 535-574, October.
    12. Dan Anderberg, 2007. "Inefficient households and the mix of government spending," Public Choice, Springer, vol. 131(1), pages 127-140, April.
    13. Michael Kremer, 1997. "Why are Worker Cooperatives So Rare?," NBER Working Papers 6118, National Bureau of Economic Research, Inc.
    14. Creedy, John & Moslehi, Solmaz, 2009. "Modelling the composition of government expenditure in democracies," European Journal of Political Economy, Elsevier, vol. 25(1), pages 42-55, March.
    15. Brett, Craig & Weymark, John A., 2016. "Voting over selfishly optimal nonlinear income tax schedules with a minimum-utility constraint," Journal of Mathematical Economics, Elsevier, vol. 67(C), pages 18-31.
    16. Dorsch, Michael T. & Maarek, Paul, 2020. "Economic downturns, inequality, and democratic improvements," European Journal of Political Economy, Elsevier, vol. 62(C).
    17. Philippe De Donder & Jean Hindriks, 2004. "Majority Support for Progressive Income Taxation with Corner Preferences," Public Choice, Springer, vol. 118(3_4), pages 437-449, March.
    18. Jenny de Freitas, 2009. "A probabilistic voting model of progressive taxation with incentive effects," Hacienda Pública Española / Review of Public Economics, IEF, vol. 190(3), pages 9-26, September.
    19. An, Zhiyong, 2013. "An alternative approach to income taxation," Economic Modelling, Elsevier, vol. 30(C), pages 875-878.
    20. Souvik Roy & Soumyarup Sadhukhan, 2019. "A characterization of random min–max domains and its applications," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 68(4), pages 887-906, November.

    More about this item

    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:arx:papers:1906.09671. See general information about how to correct material in RePEc.

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

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.