nach oben

Social Choice and Welfare

Erschienen in:

01.03.2015

Condorcet winning sets

verfasst von: Edith Elkind, Jérôme Lang, Abdallah Saffidine

Erschienen in: Social Choice and Welfare | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

An alternative is said to be a Condorcet winner of an election if it is preferred to any other alternative by a majority of voters. While this is a very attractive solution concept, many elections do not have a Condorcet winner. In this paper, we propose a set-valued relaxation of this concept, which we call a Condorcet winning set: such sets consist of alternatives that collectively dominate any other alternative. We also consider a more general version of this concept, where instead of domination by a majority of voters we require domination by a given fraction \(\theta \) of voters; we refer to such sets as \(\theta \)-winning sets. We explore social choice-theoretic and algorithmic aspects of these solution concepts, both theoretically and empirically.

Vorheriger Artikel Political cronyism

Nächster Artikel Approval voting and Arrow’s impossibility theorem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

This complexity class consists of problems that can be solved in time \(2^{O((\log n)^c)}\) for some constant \(c\) on an input of size \(n\), and includes, in particular, the minimum dominating set problem (Megiddo and Vishkin 1988).

Alon N, Brightwell G, Kierstead HA, Kostochka AV, Winkler P (2006) Dominating sets in \(k\)-majority tournaments. J Comb Theory Ser B 96(3):374–387CrossRef

Alon N, Spencer J (1992) Probabilistic method. John Wiley, Hoboken

Betzler N, Slinko A, Uhlmann J (2013) On the computation of fully proportional representation. J Artif Intell Res 47:475–519

Cervone D, Hardin C, Zwicker W (2012) Personal communication

Cervone D, Zwicker W (2011) Personal communication

Chamberlin JR, Courant PN (1983) Representative deliberations and representative decisions: proportional representation and the Borda rule. Am Polit Sci Rev 77(3):718–733CrossRef

Cornaz D, Galand L, Spanjaard O (2012) Bounded single-peaked width and proportional representation. In: Proceedings of the 20th European conference on artificial intelligence (pp 270–275)

Elkind E, Faliszewski P, Skowron P, Slinko A (2014) Properties of multiwinner voting rules. In: Proceedings of the 13th international conference on autonomous agents and multiagent systems (pp 53–60)

Fishburn P (1981) An analysis of simple voting systems for electing committees. SIAM J Appl Math 41(3):499–502CrossRef

Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, New York

Gehrlein W (1985) The Condorcet criterion and committee selection. Math Soc Sci 10(3):199–209CrossRef

Geist C (2014) Finding preference profiles of Condorcet dimension k via SAT. arXiv:1402.4303

Jones B, Radcliff B, Taber C, Timpone R (1995) Condorcet winners and the paradox of voting: probability calculations for weak preference orders. Am Polit Sci Rev 89(1):137–144CrossRef

Kaymak B, Sanver R (2003) Sets of alternatives as Condorcet winners. Soc Choice Welf 20(3):477–494CrossRef

Laforest C (2012) Personal communication

Laslier J-F (1997) Tournament solutions and majority voting. Springer, New YorkCrossRef

Lu T, Boutilier C (2011) Budgeted social choice: from consensus to personalized decision making. In: Proceedings of the 22nd international joint conference on artificial intelligence

McGarvey D (1953) A theorem on the construction of voting paradoxes. Econometrica 21(4):608–610CrossRef

Megiddo N, Vishkin U (1988) On finding a minimum dominating set in a tournament. Theor Comput Sci 61:307–316CrossRef

Monroe BL (1995) Fully proportional representation. Am Polit Sci Rev 89:925–940CrossRef

Procaccia A, Rosenschein J, Zohar A (2008) On the complexity of achieving proportional representation. Soc Choice Welf 30(3):353–362CrossRef

Ratliff T (2003) Some startling inconsistencies when electing committees. Soc Choice Welf 21(3):433–454CrossRef

Scott A, Fey M (2012) The minimal covering set in large tournaments. Soc Choice Welf 38(1):1–9CrossRef

Skowron P, Faliszewski P, Slinko A (2013a) Achieving fully proportional representation is easy in practice. In: Proceedings of the 12th international conference on autonomous agents and multiagent systems (pp 399–406)

Skowron P, Faliszewski P, Slinko A (2013b) Fully proportional representation as resource allocation: approximability results. In: Proceedings of the 23rd international joint conference on artificial intelligence (pp 353–359)

Skowron P, Yu L, Faliszewski P, Elkind E (2013) The complexity of fully proportional representation for single-crossing electorates. In: Proceedings of the 6th international symposium on algorithmic game theory (pp 1–12)

Tideman T (1987) Independence of clones as a criterion for voting rules. Soc Choice Welf 4(3):185–206CrossRef

Yu L, Chan H, Elkind E (2013) Multiwinner elections under preferences that are single-peaked on a tree. In: Proceedings of the 23rd international joint conference on artificial intelligence (pp 425–431)

Titel: Condorcet winning sets
verfasst von: Edith Elkind
Jérôme Lang
Abdallah Saffidine
Publikationsdatum: 01.03.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Social Choice and Welfare / Ausgabe 3/2015
Print ISSN: 0176-1714
Elektronische ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-014-0853-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2015

Equity and efficiency in an overlapping generation model

Approval voting and Arrow’s impossibility theorem

Sorting out single-crossing preferences on networks

Satisficing behavior with a secondary criterion

Bribe-proof reallocation with single-peaked preferences

Empirical definition of social types in the analysis of inequality of opportunity: a latent classes approach