Document Open Access Logo

Justified Representation in Multiwinner Voting: Axioms and Algorithms

Author Edith Elkind

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.1.pdf
  • Filesize: 345 kB
  • 10 pages

Document Identifiers

Author Details

Edith Elkind

Cite As Get BibTex

Edith Elkind. Justified Representation in Multiwinner Voting: Axioms and Algorithms. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 1:1-1:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2017.1

Abstract

Suppose that a group of voters wants to select k 1 alternatives from a given set, and each voter indicates which of the alternatives are acceptable to her: the alternatives could be conference submissions, applicants for a scholarship or locations for a fast food chain. In this setting it is natural to require that the winning set represents the voters fairly, in the sense that large groups of voters with similar preferences have at least some of their approved alternatives in the winning set. We describe several ways to formalize this idea, and show how to use it to classify voting rules; surprisingly, two voting rules proposed in the XIXth century turn out to play an important role in our analysis.

Subject Classification

Keywords
  • voting
  • committee selection
  • axioms
  • PAV

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh. Justified representation in approval-based committee voting. Social Choice and Welfare, 48(2):461-485, 2017. Google Scholar
  2. H. Aziz, E. Elkind, S. Huang, M. Lackner, L. Sánchez Fernández, and P. Skowron. On the complexity of extended and proportional justified representation. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI-2018), 2018. Google Scholar
  3. H. Aziz, S. Gaspers, J. Gudmundsson, S. Mackenzie, N. Mattei, and T. Walsh. Computational aspects of multi-winner approval voting. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2015), pages 107-115, 2015. Google Scholar
  4. H. Aziz and S. Huang. Computational complexity of testing proportional justified representation. Technical Report arXiv:1612.06476, arXiv.org, 2016. Google Scholar
  5. H. Aziz and S. Huang. A polynomial-time algorithm to achieve extended justified representation. Technical Report arXiv:1703.10415, arXiv.org, 2017. Google Scholar
  6. H. Aziz and B. Lee. Achieving proportional representation via voting. Technical Report arXiv:1708.07580, arXiv.org, 2017. Google Scholar
  7. H. Aziz and T. Walsh. Justified representation in approval-based committee voting. In Proceedings of the 8th Multidisciplinary Workshop on Advances in Preference Handling (MPREF-2014), 2014. Google Scholar
  8. M. Brill, R. Freeman, S. Janson, and M. Lackner. Phragmén’s voting methods and justified representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI-2017), pages 406-413, 2017. Google Scholar
  9. E. Elkind, P. Faliszewski, P. Skowron, and A. Slinko. Properties of multiwinner voting rules. Social Choice and Welfare, 48(3):599-632, 2017. Google Scholar
  10. S. Janson. Phragmén’s and Thiele’s election methods. Technical Report arXiv:1611.08826, arXiv.org, 2016. Google Scholar
  11. D. Kilgour. Approval balloting for multi-winner elections. In J. Laslier and R. Sanver, editors, Handbook on Approval Voting, pages 105-124. Springer, 2010. Google Scholar
  12. M. Lackner and P. Skowron. Consistent approval-based multi-winner rules. Technical Report arXiv:1704.02453, arXiv.org, apr 2017. Google Scholar
  13. L. E. Phragmén. Sur une méthode nouvelle pour réaliser, dans les élections, la représentation proportionnelle des partis. Öfversigt af Kongliga Vetenskaps-Akademiens Förhandlingar, 51(3):133-137, 1894. Google Scholar
  14. A. Procaccia, J. Rosenschein, and A. Zohar. On the complexity of achieving proportional representation. Social Choice and Welfare, 30(3):353-362, April 2008. Google Scholar
  15. L. Sánchez Fernández, E. Elkind, and M. Lackner. Committees providing EJR can be computed efficiently. Technical Report arXiv:1704.00356, arXiv.org, 2017. Google Scholar
  16. L. Sánchez Fernández, E. Elkind, M. Lackner, N. Fernández García, J. Arias Fisteus, P. Basanta Val, and P. Skowron. Proportional justified representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI-2017), pages 670-676, 2017. Google Scholar
  17. L. Sánchez Fernández, N. Fernández García, and J. Arias Fisteus. Fully open extensions to the D'Hondt method. Technical Report arXiv:1609.05370, arXiv.org, 2016. Google Scholar
  18. L. Sánchez Fernández, N. Fernández García, J. Arias Fisteus, and P. Basanta Val. Some notes on justified representation. In Proceedings of the 10th Multidisciplinary Workshop on Advances in Preference Handling (MPREF-2016), 2016. Google Scholar
  19. P. Skowron, P. Faliszewski, and J. Lang. Finding a collective set of items: From proportional multirepresentation to group recommendation. Artificial Intelligence, 241:191-216, 2016. Google Scholar
  20. P. Skowron, M. Lackner, E. Elkind, and L. Sánchez Fernández. Optimal average satisfaction and extended justified representation in polynomial time. Technical Report arXiv:1704.00293, arXiv.org, apr 2017. Google Scholar
  21. T. N. Thiele. Om flerfoldsvalg. In Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, pages 415-441. 1895. Google Scholar
  22. N. Tideman. The single transferable vote. The Journal of Economic Perspectives, 9(1):27-38, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact