멀티위너 투표

Multiwinner voting

복수 당선자 선거 [1]또는 위원회 투표 또는 위원회[2] 선거라고도 불리는[3] 다중 당선자 투표는 복수 후보가 선출되는 선거제도다.[4]당선자 수는 대개 미리 정해져 있다.예를 들어, 한 국가의 의회의 의석수 또는 위원회의 필요한 구성원 수일 수 있다.

다승자 투표가 유용한 시나리오는 많다.위원회 선출의 주요 목적에 따라 크게 세 가지 등급으로 분류할 수 있다.[5]

  1. 탁월함.여기서 각 투표자는 전문가로, 각 투표는 어느 후보가 특정 업무에 대해 '더 나은'지에 대한 자신의 의견을 표현한다."최고의" 후보를 찾는 것이 목표다.지원서 예로는 최종 평가 단계(예: 면접 사용)로 진행할 최종 합격자를 후보 직원 목록에서 선발하는 것이 있다.여기서 각 후보는 다른 후보들과 독립적으로 평가된다.만약 두 후보가 비슷하다면, 아마도 두 후보 모두 당선될 것이다(둘 다 좋다면), 혹은 둘 다 탈락될 것이다(둘 다 나쁘다면).
  2. 다양성.여기서 당선된 후보들은 최대한 달라야 한다.예를 들어, 후보지가 소방서와 같은 시설을 건설할 수 있는 장소라고 가정합시다.대부분의 시민들은 자연스럽게 도심에 있는 소방서를 선호한다.그러나 같은 장소에 두 개의 소방서를 둘 필요는 없다. 선택을 다양화하고 두 번째 정거장을 더 먼 곳에 두는 것이 좋다."우수"라는 설정과는 대조적으로, 만약 두 명의 후보가 비슷하다면, 그 중 정확히 한 명이 선출될 것이다.다양성이 중요한 또 다른 시나리오는 검색엔진이 디스플레이를 위해 결과를 선택하거나 항공사가 비행 중 상영을 위해 영화를 선택하는 경우다.
  3. 비례성.여기서 선출된 후보자들은 가능한 한 그들이 투표한 투표에 의해 측정된, 유권자들의 인구가 가진 다양한 의견을 과학적으로 균형 있게 대변해야 한다.이것은 국회의원 선거에서 공통적인 목표다; 비례대표를 보라.

기본개념

다승자 투표 연구의 주요 과제는 1승자 투표에서 개념의 합리적 적응을 찾는 것이다.투표 유형(승인 투표 대 순위 투표)에 따라 분류할 수 있다.

일부 선거제도는 개별 후보간 경쟁으로 복수 구성원을 선출한다.그러한 시스템은 다중 양도불능 투표와 단일 양도불능 투표의 일부 변형이다.

다른 시스템에서는 후보자를 위원회(슬레이트)에 묶고 투표로 위원회(또는 슬레이트)에 표를 던진다.이러한 위원회 기반 시스템은 다음과 같이 설명된다.

위원회 승인 투표

주요 기사:다승자 승인 투표

승인투표는 1인 선거와 때로는 다인 선거의 일반적인 방법이다.단독 당선자 선거에서는 각 유권자가 자신이 찬성하는 후보를 표시하고, 가장 많은 표를 얻은 후보가 승리한다.

다승자 투표로 어느 후보를 뽑아야 할지 결정하는 방법은 다양하다.어떤 사람들은 각 투표자들이 후보자들의 순위를 매기고, 어떤 사람들은 X표를 던진다.또한, 각 투표자는 단일 또는 복수 표를 던질 수 있다.

이미 1895년에 Tiele은 체중 기반 규칙의 가족을 제안했다.[3][6]패밀리의 각 규칙은 k의 약한 양의 가중치, w1,...,wk(여기서 k는 위원회 크기)로 정의된다.각 투표자는 투표자에 의해 승인된 p명의 후보자를 포함하는 각 위원회에 w1+의 점수를 부여한다.+wp. 총점이 가장 높은 위원회를 선출한다.티에일 가문에서 흔히 볼 수 있는 투표규칙은 다음과 같다.

  • 다중 양도 불가 투표(MNTV): 중량 벡터는 (1,1,1,...,1)이다.다원적 찬성투표라고도 한다.
  • 승인-챔버린-쿠랑트(ACC): 중량 벡터는 (1,0,...,0)이다.즉, 각 투표자는 자신이 승인한 후보자 중 한 명이 포함된 경우 위원회에 1점을 부여한다.
  • 비례 승인 투표(PAV): 중량 벡터는 고조파 진행(1, 1/2, 1/3, ...., 1/k)이다.

미니맥스 승인 투표와[7] 그 일반화, [8]프라그멘의 투표 규칙과 같은 다른 원칙에 근거한 규칙들이 있다.[9]그리고 균등주식의 방법.[10][11]

SNTV로 우승자를 계산하는 것은 다항 시간 내에 할 수 있지만 ACC에서는 NP-하드, [12]PAV로도 할 수 있다.

위원회에 대한 포지셔닝 채점 규칙

포지션 스코어링 규칙은 순위별 1위 투표에서 흔히 볼 수 있다.각 투표자는 최고에서 최저까지 순위를 매기고, 사전 지정된 함수는 자신의 순위를 기준으로 각 후보에게 점수를 부여하며, 총점이 가장 높은 후보가 당선된다.

이런 제도를 이용해 치러지는 다승자 투표에서 우리는 개별 후보보다는 위원회에 점수를 부여할 필요가 있다.이를 위한 방법에는 여러 가지가 있는데,[1] 예를 들면 다음과 같다.

  • 단일 비양도 투표: 각 투표자는 자신이 가장 선호하는 후보가 포함된 경우 위원회에 1점을 준다.즉, 다승자를 뽑는 경연에서 각 투표자가 단일 후보를 뽑고, 최다 득표자를 기록한 k 후보가 당선된다.이것은 첫 번째-과거-사후 투표를 일반화한다.다항식 시간으로 계산할 수 있다.
  • 다수의 양도할 수 없는 투표(블록 투표라고도 함): 각 투표자는 자신의 상단 k에 있는 각 열린 의석에 대해 위원회에 1점을 부여한다.즉, 각 투표자는 k석이 열려 있는 k후보와 최다 득표자가 당선된다.
  • k-Borda: 각 유권자는 각 위원회 위원에게 자신의 보다 숫자를 알려준다.각 투표자는 후보 순위를 매기고, 그 순위를 함께 매긴다.총 보르다 점수가 가장 높은 k 후보가 당선된다.
  • 보르다-참벌린-쿠란트(BCC):[13] 각 유권자는 각 위원회에 자신이 가장 선호하는 보르다 카운트를 부여한다.BCC로 승자를 계산하는 것은 NP-hard이다.[12]

콘도르셋 위원회

단일승자 투표에서 콘도르셋 승자는 다른 후보들을 상대로 한 선거 때마다 승리하는 후보다.콘도르셋 방식은 콘도르셋 당첨자가 있을 때마다 선정하는 방식이다.콘도르셋의 기준을 다승자 투표에 적응시키는 몇 가지 방법이 있다.

  • 첫 번째 적응은 피터 피시번(Peter Fishburn)에 의해 이루어졌다.[14][15] 만일 유권자 대다수가 다른 주머니쥐 위원회보다 선호한다면 위원회는 콘도르셋 위원회다.피시번은 유권자들이 찬성 세트의 위원 수(즉, 이분법적 선호도를 가지고 있다)에 따라 위원회를 서열화한다고 가정했다.후기 작품들은 유권자들이 보다 카운트와 같은 다른 기준으로 위원회의 순위를 매긴다고 가정했다.위원회가 이 기준을 충족하는지 확인하는 것은 coNP-완전하며, coNP-강력한 것은 콘도르셋 위원회의 존재 여부를 결정하는 것이다.[16]
  • 또 다른 적응은 게를린과[17] 라틀리프에 의해 이루어졌다.[18] 위원회는 각 후보가 다른 후보들에게 투표권자 과반수가 선호하는 경우 콘도르셋이다.다승자 투표 규칙은 콘도르셋이 존재할 때마다 선택하는 경우에 안정적이라고 불리기도 한다.[19]일부 안정적인 규칙은 다음과 같다.[20]
    • 멀티위너 코프랜드의 방법: 각 위원회는 "외부 패배 횟수"로 채점된다. 즉, c가 위원회에 속하고 d가 아닌 쌍(c,d)의 수, 유권자 과반수가 d를 선호한다.
    • Multiwin Minimax Condorcet 방법: 각 위원회는 c를 선호하는 유권자 수의 최소 쌍(c,d)에 대해 "외부 반대파의 크기"로 점수를 매긴다.
    • 다른 콘도르셋 규칙의 멀티위너 변형.[21]
  • 세 번째 적응은 Elkind, Lang, Saffidine에 의해 이루어졌다.[22] 콘도르셋 우승 세트는 세트에 없는 각 멤버에 대해 세트의 일부 멤버 c가 다수로 d보다 선호되는 세트다수가 d를 선호한다.이 정의에 기초해 미니맥스 콘도르세트의 다른 멀티위너 변형을 제시한다.

기타기준

파레토 효율적 위원회를 계산하는 것은 일반적으로 NP-hard이다.[23]

우수 선거

우수성은 위원회에서 '최우수' 후보를 담아야 한다는 것을 의미한다.우수 기반 투표 규칙을 심사 규칙이라고 하는 경우가 많다.[19]단일 최우수 후보 선정의 첫 단계, 즉 최종 후보 리스트를 작성하는 방법으로 자주 사용된다.그러한 규칙에 의해 충족되어야 하는 기본적인 속성은 위원회 단성(자원의 단성(house monotonicity, 자원 단성(house monotonicity)이라고도 한다): 규칙에 의해 일부 k 후보가 선출된 다음, 위원회 규모가 k+1로 증가하여 규칙이 재적용되면, 첫 번째 k 후보는 여전히 선출되어야 한다.위원회-모노톤 규칙의 일부 제품군은 다음과 같다.

  • 순차적 규칙:[19] 모든 단일 당첨자 투표 규칙을 사용하여 단일 후보를 선택한 후 위원회에 추가하십시오.프로세스를 k회 반복한다.
  • 최상의 규칙:[1] 점수 매기기 규칙을 사용하여 각 후보에게 점수를 할당하십시오.가장 높은 점수를 받은 k명의 후보자를 선택하라.

위원회 단조화의 속성은 안정성의 속성과 양립할 수 없다(콘도르셋의 기준의 특정적응). 크기 2의 고유한 콘도르셋 집합과 크기 3의 고유한 콘도르셋 집합을 인정하는 단일 투표 프로파일이 존재하며, 이들은 분리된다(크기 2의 집합은 크기 3의 집합에 포함되지 않는다).[19]

반면에, 포지셔닝 점수 규칙인 분리 가능한 포지셔닝 점수 규칙인 위원회-모노톤 계열이 존재한다.이러한 규칙은 다항 시간(기본적인 단일 우승자 점수 기능이 있는 경우)에도 계산할 수 있다.[1]예를 들어, k-Borda는 분리 가능한 반면, 다중 양도 불가능한 투표는 분리할 수 없다.

다양성 선거

다양성이란 최대한 많은 유권자의 1위 후보를 담아야 한다는 뜻이다.형식적으로 다양성 중심적 용도에 대해서는 다음과 같은 공리가 타당하다.

  • 좁은 상위 기준:[1] 모든 유권자의 최상위 후보가 포함된 k 크기의 위원회가 존재한다면, 그 위원회는 선출되어야 한다.
  • 최고 구성원 단성:[24] 위원회가 선출되고, 일부 유권자가 그가 가장 선호하는 승자의 계급을 위로 이동하면, 동일한 위원회가 선출되어야 한다.

비례선거

주요 기사:정당화된 표현

비례성은 각각의 응집력 있는 유권자 그룹(즉, 비슷한 선호를 가진 유권자 그룹)이 그 크기에 비례하는 다수의 당선자로 대표되어야 한다는 것을 의미한다.형식적으로 위원회가 k사이즈라면 유권자는 없고 일부 L*n/k 유권자는 같은 L 후보를 상위(또는 같은 L 후보를 승인)에 랭크하는 경우 이 L 후보를 선출해야 한다.이 원칙은 유권자가 정당에 투표할 때(정당명부 제도에서) 구현하기 쉬우나, 찬성 투표나 순위 투표에도 적용될 수 있다. 정당화된 대표성을 참조하라.

추가 읽기

  • 항목 집합 찾기: 비례 다중 프리젠테이션에서 그룹 추천까지.[25]
  • 예산 책정된 사회적 선택:컨센서스에서 맞춤형 의사 결정까지.[26]
  • 완전 비례 대표성 달성:근사성 결과.[27]

참고 항목

  • 참여형 예산편성 - 각 후보가 '비용'을 갖는 다승자 투표의 연장선으로 볼 수 있다.다승자 투표에서 각 후보의 가격은 1이고, 예산은 k이다.

참조

  1. ^ a b c d e Elkind, Edith; Faliszewski, Piotr; Skowron, Piotr; Slinko, Arkadii (2017-03-01). "Properties of multiwinner voting rules". Social Choice and Welfare. 48 (3): 599–632. doi:10.1007/s00355-017-1026-z. ISSN 1432-217X. PMC 7089675. PMID 32226187.
  2. ^ "RangeVoting.org - Glossary". rangevoting.org. Retrieved 2021-06-25.
  3. ^ a b Aziz, Haris; Brill, Markus; Conitzer, Vincent; Elkind, Edith; Freeman, Rupert; Walsh, Toby (2017). "Justified representation in approval-based committee voting". Social Choice and Welfare. 48 (2): 461–485. doi:10.1007/s00355-016-1019-3. S2CID 8564247.
  4. ^ Bock, Hans-Hermann; Day, William H.E.; McMorris, F.R. (1998-05-01). "Consensus rules for committee elections". Mathematical Social Sciences. 35 (3): 219–232. doi:10.1016/S0165-4896(97)00033-4. ISSN 0165-4896.
  5. ^ Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon (2017-10-26). "Multiwinner Voting: A New Challenge for Social Choice Theory". In Endriss, Ulle (ed.). Trends in Computational Social Choice. Lulu.com. ISBN 978-1-326-91209-3.{{cite book}}: CS1 maint : 복수이름 : 작성자 목록(링크)
  6. ^ Sánchez-Fernández, Luis; Elkind, Edith; Lackner, Martin; Fernández, Norberto; Fisteus, Jesús; Val, Pablo Basanta; Skowron, Piotr (2017-02-10). "Proportional Justified Representation". Proceedings of the AAAI Conference on Artificial Intelligence. 31 (1). ISSN 2374-3468.
  7. ^ Brams, Steven J.; Kilgour, D. Marc; Sanver, M. Remzi (2007-09-01). "A minimax procedure for electing committees". Public Choice. 132 (3): 401–420. doi:10.1007/s11127-007-9165-x. ISSN 1573-7101. S2CID 46632580.
  8. ^ Amanatidis, Georgios; Barrot, Nathanaël; Lang, Jérôme; Markakis, Evangelos; Ries, Bernard (2015-05-04). "Multiple Referenda and Multiwinner Elections Using Hamming Distances: Complexity and Manipulability". Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. AAMAS '15. Istanbul, Turkey: International Foundation for Autonomous Agents and Multiagent Systems: 715–723. ISBN 978-1-4503-3413-6.
  9. ^ Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin (2017-02-10). "Phragmén's Voting Methods and Justified Representation". Proceedings of the AAAI Conference on Artificial Intelligence. 31 (1). ISSN 2374-3468.
  10. ^ Peters, Dominik; Skowron, Piotr (2020). "Proportionality and the Limits of Welfarism". Proceedings of the 21st ACM Conference on Economics and Computation. EC'20: 793–794. arXiv:1911.11747. doi:10.1145/3391403.3399465. ISBN 9781450379755. S2CID 208291203.
  11. ^ Pierczyński, Grzegorz; Peters, Dominik; Skowron, Piotr (2020). "Proportional Participatory Budgeting with Additive Utilities". Proceedings of the 2021 Conference on Neural Information Processing Systems. NeurIPS'21. arXiv:2008.13276.
  12. ^ a b Procaccia, Ariel D.; Rosenschein, Jeffrey S.; Zohar, Aviv (2007-04-19). "On the complexity of achieving proportional representation". Social Choice and Welfare. 30 (3): 353–362. doi:10.1007/s00355-007-0235-2. S2CID 18126521.
  13. ^ Chamberlin, John R.; Courant, Paul N. (1983). "Representative Deliberations and Representative Decisions: Proportional Representation and the Borda Rule". The American Political Science Review. 77 (3): 718–733. doi:10.2307/1957270. ISSN 0003-0554. JSTOR 1957270.
  14. ^ Fishburn, Peter C. (1981-10-01). "Majority committees". Journal of Economic Theory. 25 (2): 255–268. doi:10.1016/0022-0531(81)90005-3. ISSN 0022-0531.
  15. ^ Fishburn, Peter C. (1981-12-01). "An Analysis of Simple Voting Systems for Electing Committees". SIAM Journal on Applied Mathematics. 41 (3): 499–502. doi:10.1137/0141041. ISSN 0036-1399.
  16. ^ Darmann, Andreas (2013-11-01). "How hard is it to tell which is a Condorcet committee?". Mathematical Social Sciences. 66 (3): 282–292. doi:10.1016/j.mathsocsci.2013.06.004. ISSN 0165-4896. PMC 4376023. PMID 25843993.
  17. ^ Gehrlein, William V. (1985-12-01). "The Condorcet criterion and committee selection". Mathematical Social Sciences. 10 (3): 199–209. doi:10.1016/0165-4896(85)90043-5. ISSN 0165-4896.
  18. ^ Ratliff, Thomas C. (2003-12-01). "Some startling inconsistencies when electing committees". Social Choice and Welfare. 21 (3): 433–454. doi:10.1007/s00355-003-0209-y. ISSN 1432-217X. S2CID 36949675.
  19. ^ a b c d Barberà, Salvador; Coelho, Danilo (2008). "How to choose a non-controversial list with k names". Social Choice and Welfare. 31 (1): 79–96. doi:10.1007/s00355-007-0268-6. ISSN 0176-1714. JSTOR 41107910. S2CID 16974573.
  20. ^ Coelho, Danilo; Barberà, Salvador (2005). Understanding, evaluating and selecting voting rules through games and axioms. Bellaterra: Universitat Autònoma de Barcelona. ISBN 978-84-689-0967-7.
  21. ^ Kamwa, Eric (2017-05-01). "On stable rules for selecting committees". Journal of Mathematical Economics. 70: 36–44. doi:10.1016/j.jmateco.2017.01.008. ISSN 0304-4068.
  22. ^ Elkind, Edith; Lang, Jérôme; Saffidine, Abdallah (2015). "Condorcet winning sets". Social Choice and Welfare. 44 (3): 493–517. doi:10.1007/s00355-014-0853-4. ISSN 0176-1714. JSTOR 43662603. S2CID 31128109.
  23. ^ Aziz, Haris; Monnot, Jérôme (2020-02-17). "Computing and testing Pareto optimal committees". Autonomous Agents and Multi-Agent Systems. 34 (1): 24. arXiv:1803.06644. doi:10.1007/s10458-020-09445-y. ISSN 1573-7454. S2CID 3955482.
  24. ^ Faliszewski, Piotr; Skowron, Piotr; Slinko, Arkadii; Talmon, Nimrod (2016-07-09). "Committee scoring rules: axiomatic classification and hierarchy". Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI'16. New York, New York, USA: AAAI Press: 250–256. ISBN 978-1-57735-770-4.
  25. ^ Skowron, Piotr; Faliszewski, Piotr; Lang, Jerome (2015-01-01). Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. AAAI'15. Vol. 1402. pp. 2131–2137. arXiv:1402.3044. Bibcode:2014arXiv1402.3044S. ISBN 978-0262511292.
  26. ^ Lu, Tyler; Boutilier, Craig (2011-01-01). Budgeted Social Choice: From Consensus to Personalized Decision Making. Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. IJCAI'11. pp. 280–286. doi:10.5591/978-1-57735-516-8/IJCAI11-057. ISBN 9781577355137.
  27. ^ Skowron, Piotr; Faliszewski, Piotr; Slinko, Arkadii (2015-05-01). "Achieving fully proportional representation: Approximability results". Artificial Intelligence. 222: 67–103. arXiv:1312.4026. doi:10.1016/j.artint.2015.01.003. S2CID 467056.