Computer Science ›› 2021, Vol. 48 ›› Issue (1): 217-225.doi: 10.11896/jsjkx.200600013

• Artificial Intelligence • Previous Articles     Next Articles

Survey on Multi-winner Voting Theory

LI Li   

  1. School of Administrative Law,Southwest University of Political Science and Law,Chongqing 401120,China
  • Received:2020-06-01 Revised:2020-08-19 Online:2021-01-15 Published:2021-01-15
  • About author:LI Li,born in 1982,Ph.D,lecturer,master supervisor.Her main research interests include modern logic and artificial intelligence.
  • Supported by:
    National Social Science Fund Project(18BZX133) and Chongqing Social Science Association Planning Project(2016BS009).

Abstract: With the advent of the intelligent age,the way of collective decision-making is also changing.People are no longer satis-fied with a single-winner decision result,but need a committee which is composed of multiple winners as a winner set,and this committee set is applied to the recommendation system and search engine,policy vote and corporate decision-making,etc.The biggest advantage of the multi-winner voting theory is that the decision cost is low and the decision efficiency is quite high,which is an excellent collective decision method.The research core of multi-winner voting theory lies in finding multi-winner voting rules which are suitable for different application scenarios.This paper introduces two categories of multi-winner decision-making methods,the committee's voting rules and the multi-winner voting rules based on approval voting.The two types of rules represent the research directions of two different types of multi-winner voting theory.This paper explains the representative multi-winner voting rules under the two categories of rules based on the establishment of a logic model,and tries to discuss the development trend of the multi-winner voting theory by sorting out the current influential literatures.It is expected to help more researchers to solve problems in practice with this theory.

Key words: Multi-winner voting rules, Collective decision-making, Committee, Computational social choice, Voting model

CLC Number: 

  • TP3-05
[1] ARROW K J.Social Choice and Individual Values [M].YaleUniversity Press,1963:137-221.
[2] ZHANG N,CHEN R,GUO S K,State-of-the-art and Future of Voting Theory[J].Computer Science,2015,42(5):1-9.
[3] PROCACCIA A D,ROSENSCHEIN J S,ZOHAR A.Multi-Winner Elections:Complexity of Manipulation,Control and Winner-Determination[C]//IJCAI.2007,7:1476-1481.
[4] ELKIND E,FALISZEWSKI P,LASLIER J F,et al.What do Multiwinner Voting Rules do? An Experiment over the Two-dimensional Euclidean Domain[C]//Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence.2017:494-501.
[5] LACKNER M,SKOWRON P.Consistent Approval-based Multi-winner Rules[C]//Proceedings of the 2018 ACM Conference on Economics and Computation.2018:47-48.
[6] MAUDET N,JÉRME LANG,ENDRISS U,et al.A Short Introduction to Computational Social Choice[C]// Proc Confe-rence on Current Trends in Theory & Practice of Computer Scie-nce.2007.
[7] NI X.The political meaning of public choice theory[J].Explore,1997(4):49-53.
[8] LIU L.Mechanism Design for Operation Room Scheduling Considering Surgeons' time Preferences[D].Dalian:Dalian University of Technology,2019.
[8] BRILL M,LASLIER J F,SKOWRON P.Multiwinner approval rules as apportionment methods[J].Journal of Theoretical Politics,2018,30(3):358-382.
[10] WANG Y Q.The Analysis of the Preference Aggregation in Social Choice[D].Chengdu:University of Electronic Science and Technology,2018.
[11] ELKIND E,FALISZEWSKI P,SKOWRON P,et al.Properties of Multi-Winner Voting Rules [J].Social Choice and Welfare,2017,48(3):599-632.
[12] SKOWRON P,FALISZEWSKI P,SLINKO A.Achieving Fully Proportional Representation:Approximability Results [J].Artificial Intelligence,2015,222:67-103.
[13] SKOWRON P,FALISZEWSKI P.Fully Proportional Representation With Approval Ballots:Approximating The Maxcover Problem with Bounded Frequencies in FPT Time[C]//Procee-dings of the Twenty-Ninth AAAI Conference on Artificial Intelligence.2015:2124-2130.
[14] AZIZ H,GASPERS S,GUDMUNDSSON J,et al.Computatio-nal Aspects of Multi-Winner Approval Voting[C]//Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems.2015:107-115.
[15] BRAMS S J,FISHBURN P C.Voting Procedures [J].Handbook of Social Choice and Welfare,2002,1:173-236.
[16] LASLIER J F,SANVER R.Handbook on Approval Voting[M].Springer,2010:41-102.
[17] MUELLER D C.Public Choice III[M].Cambridge University Press,2003:65-206.
[18] BARBERÀ S,COELHO D.How to Choose a Non-Controversial List with K Names [J].Social Choice and Welfare,2008,31(1):79-96.
[19] FALISZEWSKI P,SKOWRON P,SLINKO A,et al.Multi-winner Rules on Paths From k-Borda to Chamberlin-Courant[C]//IJCAI.2017:192-198.
[20] BRAMS S J,KILGOUR D M,SANVER M R.A Minimax Procedure for Electing Committees [J].Public Choice,2007,132(3/4):401-420.
[21] FALISZEWSKI P,SKOWRON P,SLINKO A,et al.Multi-winner Analogues of the Plurality Rule:Axiomatic and Algorithmic Perspectives [J].Social Choice and Welfare,2018,51(3):513-550.
[22] BLACK D.The Theory of Committees and Elections[J].Econometrica,1958,12(4):6670-6679.
[23] DUMMETT M.Voting Procedures[J].American Journal of Sociology,1986:173-236.
[24] WOODALL D.Properties of Preferential Election Rules [J].Voting Matters,1994,3:8-15.
[25] TIDEMAN N,RICHARDSON D.Better Voting Methodsthrough Technology:the Refinement-Manageability Trade-Off in the Single Transferable Vote [J].Public Choice,2000,103(1/2):13-34.
[26] MONROE B L.Fully Proportional Representation [J].American Political Science Review,1995,89(4):925-940.
[27] PROCACCIA A D,ROSENSCHEIN J S,ZOHAR A.On theComplexity of Achieving Proportional Representation [J].Social Choice and Welfare,2008,30(3):353-362.
[28] BETZLER N,SLINKO A,UHLMANN J.On the Computation of Fully Proportional Representation [J].Journal of Artificial Intelligence Research,2013,47:475-519.
[29] KILGOUR D M.Approval Elections with a Variable Number of Winners [J].Theory and Decision,2016,81(2):199-211.
[30] BRAMS S J,NAGEL J H.Approval Voting in Practice [J].Public Choice,1991,71(1/2):1-17.
[1] ZHANG Nan, CHEN Rong and GUO Shi-kai. State-of-the-art and Future of Voting Theory [J]. Computer Science, 2015, 42(5): 1-9.
[2] . [J]. Computer Science, 2008, 35(1): 160-163.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[2] HAN Kui-kui, XIE Zai-peng and LV Xin. Fog Computing Task Scheduling Strategy Based on Improved Genetic Algorithm[J]. Computer Science, 2018, 45(4): 137 -142 .
[3] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[4] TONG Ze-ping, LI Tao, LI Li-jie and REN Liang. Study on Collaborative Optimization of Supply Chain with Uncertain Demand and Capacity Constraint[J]. Computer Science, 2018, 45(4): 260 -265 .
[5] XU Zhou-bo, ZHANG Kun, NING Li-hua and GU Tian-long. Summary of Graph Edit Distance[J]. Computer Science, 2018, 45(4): 11 -18 .
[6] ZHAO Li-bo, LIU Qi, FU Fang-ling and HE Ling. Automatic Detection of Hypernasality Grades Based on Discrete Wavelet Transformation and Cepstrum Analysis[J]. Computer Science, 2018, 45(4): 278 -284 .
[7] HU Qing-cheng, ZHANG Yong, XING Chun-xiao. K-clique Heuristic Algorithm for Influence Maximization in Social Network[J]. Computer Science, 2018, 45(6): 32 -35 .
[8] ZHANG Yu, GAO Ke-ning, YU Ge. Method of Link Prediction in Social Networks Using Node Attribute Information[J]. Computer Science, 2018, 45(6): 41 -45 .
[9] WANG Zhi, WANG Jian-jun, WANG Wen-dong. Matrix Completion Algorithm Based on Subspace Thresholding Pursuit[J]. Computer Science, 2018, 45(6): 193 -196 .
[10] JI Hai-juan, ZHOU Cong-hua, LIU Zhi-feng. Symbolic Aggregate Approximation Method of Time Series Based on Beginning and End Distance[J]. Computer Science, 2018, 45(6): 216 -221 .