nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Robustness Among Multiwinner Voting Rules

verfasst von : Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk, Rolf Niedermeier, Piotr Skowron, Nimrod Talmon

Erschienen in: Algorithmic Game Theory

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We investigate how robust are results of committee elections to small changes in the input preference orders, depending on the voting rules used. We find that for typical rules the effect of making a single swap of adjacent candidates in a single preference order is either that (1) at most one committee member can be replaced, or (2) it is possible that the whole committee can be replaced. We also show that the problem of computing the smallest number of swaps that lead to changing the election outcome is typically \({\mathrm {NP}}\)-hard, but there are natural \({\mathrm {FPT}}\) algorithms. Finally, for a number of rules we assess experimentally the average number of random swaps necessary to change the election result.

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 "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

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

Vorheriges Kapitel Earning Limits in Fisher Markets with Spending-Constraint Utilities

Nächstes Kapitel Computing Constrained Approximate Equilibria in Polymatrix Games

Indeed, the formal definition is more complex due to taking care of ties.

We also construct somewhat artificial rules with robustness levels between 1 and k.

We found STV to be computationally too intensive for our experiments, so we used a simplified variant where all internal ties are broken lexicographically. We omit NED for similar reasons (but we expect the results to be similar as for k-Copeland).

Aziz, H., Elkind, E., Faliszewski, P., Lackner, M., Skowron, P.: The Condorcet principle for multiwinner elections: from shortlisting to proportionality. arXiv preprint arXiv:1701.08023 (2017)

Barberà, S., Coelho, D.: How to choose a non-controversial list with \(k\) names. Soc. Choice Welf. 31(1), 79–96 (2008)MathSciNetCrossRef

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

Blom, M., Stuckey, P., Teague, V.: Towards computing victory margins in STV elections. arXiv preprint arXiv:1703.03511 (2017)

Bredereck, R., Faliszewski, P., Kaczmarczyk, A., Niedermeier, R., Skowron, P., Talmon, N.: Robustness among multiwinner voting rules. arXiv preprint arXiv:1707.01417 (2017)

Caragiannis, I., Hemaspaandra, E., Hemaspaandra, L.: Dodgson’s rule and Young’s rule. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D. (eds.) Handbook of Computational Social Choice. Cambridge University Press, Cambridge (2016)

Cary, D.: Estimating the margin of victory for instant-runoff voting. Presented at EVT/WOTE-2011, August 2011

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

Coelho, D.: Understanding, evaluating and selecting voting rules through games and axioms. Ph.D. thesis, Universitat Autònoma de Barcelona (2004)

10.

Conitzer, V., Rognlie, M., Xia, L.: Preference functions that score rankings and maximum likelihood estimation. In: Proceedings of IJCAI-2009, pp. 109–115, July 2009

11.

Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Heidelberg (2015)CrossRef

12.

Elkind, E., Faliszewski, P., Skowron, P., Slinko, A.: Properties of multiwinner voting rules. Social Choice Welf. 48(3), 599–632 (2017)MathSciNetCrossRef

13.

Elkind, E., Faliszewski, P., Slinko, A.: Swap bribery. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) SAGT 2009. LNCS, vol. 5814, pp. 299–310. Springer, Heidelberg (2009). doi:10.1007/978-3-642-04645-2_27CrossRef

14.

Faliszewski, P., Skowron, P., Slinko, A., Talmon, N.: Committee scoring rules: axiomatic classification and hierarchy. In: Proceedings of IJCAI-2016, pp. 250–256 (2016)

15.

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

16.

Kaczmarczyk, A., Faliszewski, P.: Algorithms for destructive shift bribery. In: Proceedings of AAMAS-2016, pp. 305–313 (2016)

17.

Kamwa, E.: On stable voting rules for selecting committees. J. Math. Econ. 70, 36–44 (2017)MathSciNetCrossRef

18.

Lenstra Jr., H.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538–548 (1983)MathSciNetCrossRef

19.

Lu, T., Boutilier, C.: Budgeted social choice: from consensus to personalized decision making. In: Proceedings of IJCAI-2011, pp. 280–286 (2011)

20.

Magrino, T., Rivest, R., Shen, E., Wagner, D.: Computing the margin of victory in IRV elections. Presented at EVT/WOTE-2011, August 2011

21.

Mattei, N., Walsh, T.: Preflib: a library for preferences. In: Proceedings of the 3rd International Conference on Algorithmic Decision Theory, pp. 259–270 (2013)CrossRef

22.

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

23.

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

24.

Sekar, S. Sikdar., Xia, L.: Condorcet consistent bundling with social choice. In: Proceedings of AAMAS-2017, May 2017

25.

Shiryaev, D., Yu, L., Elkind, E.: On elections with robust winners. In: Proceedings of AAMAS-2013, pp. 415–422 (2013)

26.

Xia, L.: Computing the margin of victory for various voting rules. In: Proceedings of EC-2012, pp. 982–999, June 2012

Titel: Robustness Among Multiwinner Voting Rules
verfasst von: Robert Bredereck
Piotr Faliszewski
Andrzej Kaczmarczyk
Rolf Niedermeier
Piotr Skowron
Nimrod Talmon
Verlag: Springer International Publishing
Buch: Algorithmic Game Theory
Print ISBN: 978-3-319-66699-0

Electronic ISBN: 978-3-319-66700-3

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-66700-3_7

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 "Technik"

Springer Professional "Wirtschaft"

Premium Partner