计算机科学 ›› 2021, Vol. 48 ›› Issue (1): 217-225.doi: 10.11896/jsjkx.200600013

• 人工智能 • 上一篇    下一篇

多赢家投票理论的研究进展

李莉   

  1. 西南政法大学行政法学院 重庆 401120
  • 收稿日期:2020-06-01 修回日期:2020-08-19 出版日期:2021-01-15 发布日期:2021-01-15
  • 通讯作者: 李莉(395770202@qq.com)
  • 基金资助:
    国家社科基金项目(18BZX133);重庆市社科联项目(2016BS009)

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: Collective decision-making, Committee, Computational social choice, Multi-winner voting rules, Voting model

中图分类号: 

  • 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] 张 楠,陈 荣,郭世凯.
投票理论研究现状及其展望
State-of-the-art and Future of Voting Theory
计算机科学, 2015, 42(5): 1-9. https://doi.org/10.11896/j.issn.1002-137X.2015.05.001
[2] .
一种含两层专家网络的委员会机器模型

计算机科学, 2008, 35(1): 160-163.
[3] 余胜生 张剑 周敬利.
基于H.264标准的混合编码算法分析

计算机科学, 2005, 32(5): 109-111.
[4] 无.
2005年全国开放式分布与并行计算学术会议征文通知

计算机科学, 2005, 32(4): 232-232.
[5] 无.
第十届中国机器学习会议

计算机科学, 2005, 32(10): 94-94.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!