计算机科学 ›› 2021, Vol. 48 ›› Issue (1): 217-225.doi: 10.11896/jsjkx.200600013
李莉
LI Li
摘要: 随着智能时代的到来,集体决策的方式也在发生着改变,人们不再满足于单一的决策结果,需要多个赢家共同组成的委员会成为获胜集合,并将此集合应用于推荐系统、搜索引擎、政策表决以及企业决策等领域。多赢家投票理论最大的优点是决策成本低并且决策效率高,是非常优秀的集体决策方法。多赢家投票理论的研究核心在于找到适合不同应用场景的多赢家投票规则。文中分别介绍了两个大类的多赢家决策方法,即委员会得票规则和基于投赞成票的多赢家投票规则,这两类规则分别代表了两种不同类型的多赢家投票理论的研究方向。文中在建立逻辑模型的基础上分别详细介绍了几种极具代表性的多赢家投票规则,通过对目前有影响力的文献进行梳理,尝试对多赢家投票理论的发展趋势进行探讨,以期帮助更多研究者利用该理论解决实践中出现的问题。
中图分类号:
[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. |
|