Computer Science ›› 2015, Vol. 42 ›› Issue (5): 1-9.doi: 10.11896/j.issn.1002-137X.2015.05.001

    Next Articles

State-of-the-art and Future of Voting Theory

ZHANG Nan, CHEN Rong and GUO Shi-kai   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Social choice theory is concerned with the design and analysis of methods for collective decision making.Computational social choice is an interdisciplinary field of study at the interface of social choice theory and computer science and has attracted much attention from people working in artificial intelligence,economic and theoretical computer science,promoting an exchange of ideas in both directions.On the one hand,it is concerned with the application of techniques developed in computer science,such as complexity analysis or algorithm design,to study social choice mechanisms.On the other hand,computational social choice is concerned with importing concepts from social choice theory into computing,and especially social choice theory has since found its place as one of the fundamental tools for the study of multiagent systems.Voting theory is one of the most important research topics in computational social choice currently.So the main topic for this paper is voting theory,which will be investigated from all sorts of angles.Firstly,some popular voting procedures and formal framework of voting theory were introduced.Secondly,strategic manipulation and ways of circumventing strategic manipulation were discussed.Then some of the problems associated with voting in combinatorial domains were highlighted,and several approaches that have been proposed to address them were introduced.Finally,a number of additional topics in voting theory were touched briefly.Meanwhile,some future directions of voting theory were also addressed shortly.

Key words: Computational social choice,Voting theory,Impossibility theorems,Manipulation,Combinatorial domains

[1] 孟小峰,李勇,祝建华.社会计算:大数据时代的机遇与挑战[J].计算机研究与发展,2013,50(12):2483-2491
[2] 肯尼斯·约瑟夫·阿罗.社会选择:个性与多准则[M].钱晓敏,孟岳良,译.北京:首都经济贸易大学出版社,2000
[3] http://www.illc.uva.nl/COMSOC/IJCAI-2011/
[4] http://www.preflib.org/beyond2014/
[5] http://ecai2010.appia.pt/index.php?option=com_content & task=view & id=86
[6] http://www.cs.rpi.edu/~xial/COMSOCIJCAI.htm
[7] http://link.springer.com/journal/10458/22/1/page/1
[8] http://www.illc.uva.nl/COMSOC/workshops.html
[9] Gale D,Shapley L S.College Admissions and the Stability of Marriage[J].American Mathematical Monthly,1962,69:9-15
[10] Chevaleyre Y,Endriss U,Lang J,et al.A Short Introduction to Computational Social Choice[C]∥Theory and Practice of Computer Science,2007(SOFSEM 2007).Berlin:Springer-Verlag,2007:51-69
[11] Pauly M.On the Role of Language in Social Choice Theory[J].Synthese,2008,163(2):227-243
[12] gotnes T,van der Hoek W,Wooldridge M.On the Logic of Preference and Judgment Aggregation[J].Autonomous Agents and Multi-agent Systems,2011,22(1):4-30
[13] Endriss U.Logic and Social Choice Theory[M]∥Gupta A,van Benthem J,eds.Logic and Philosophy Today,Volume 2.College Publications,2011:333-377
[14] Grandi U,Endriss U.First-Order Logic Formalisation of Impossibility Theorems in Preference Aggregation[J].Journal of Phi-losophical Logic,2013,42(4):595-618
[15] Brams S J,Fishburn P C.Voting Procedures[M]∥Arrow K J,et al.,eds.Handbook of Social Choice and Welfare,Volume 1.Elsevier,2002:173-236
[16] Fishburn P C,Brams S J.Paradoxes of Preferential Voting[J].Mathematics Magazine,1983,56(4):207-214
[17] de Condorcet M.Essai sur l’application de l’analyse à laprobabilité des décisions rendues a la pluralité des voix[M].Paris,1785
[18] Copeland A H.A “Reasonable” Social Welfare Function[J/OL].http://citeseerx.ist.psu.edu/showciting?cid=2845852
[19] Slater P.Inconsistencies in a Schedule of Paired Comparisons[J].Biometrika,1961,48(3/4):303-312
[20] Kemeny J G.Mathematics without Numbers[J].Daedalus,1959,88(4):571-591
[21] Banks J S.Sophisticated Voting Outcomes and Agenda Control[J].Social Choice and Welfare,1985,1(4):295-306
[22] Arrow K J.Social Choice and Individual Values(2nd edition)[M].Cowles Foundation,Yale University Press,1963
[23] Taylor A D.Social Choice and the Mathematics of Manipulation[M].Cambridge:Cambridge University Press,2005
[24] Sen A K.The Impossibility of a Paretian Liberal[J].Journal of Political Economics,1970,78(1):152-157
[25] Satterthwaite M A.Strategy-proofness and Arrow’s Conditions[J].Journal of Economic Theory,1975,10:187-217
[26] Kirman A P,Sondermann D.Arrow’s Theorem,Many Agents,and Invisible Dictators [J].Journal of Economic Theory,1972,5(3):267-277
[27] Sen A K.Social Choice Theory[M]∥Arrow K J,Intriligator M D,eds.Handbook of Mathematical Economics,Volume 3.North-Holland,1986:1073-1181
[28] Geanakoplos J.Three Brief Proofs of Arrow’s ImpossibilityTheorem[J].Economic Theory,2005,26(1):211-215
[29] Barberà S.Pivotal Voters:A New Proof of Arrow’s Theorem[J].Economics Letters,1980,6(1):13-16
[30] Nipkow T.Social Choice Theory in HOL:Arrow and Gibbard-Satterthwaite[J].Journal of Automated Reasoning,2009,43(3):289-304
[31] Tang Ping-zhong,Lin Fang-zhen.Computer- aided Proofs of Arrow’s and other Impossibility Theorems[J].Artificial Intelligence,2009,173(1):1041-1053
[32] Gibbard A.Manipulation of Voting Schemes:A General Result[J].Econometrica,1973,41(4):587-601
[33] Muller E,Satterthwaite M A.The Equivalence of Strong Positive Association and Strategy-Proofness[J].Journal of Economic Theory,1977,14(2):412-418
[34] Pini M S,Rossi F,Kristen Brent Venable,et al.Aggregating Partially Ordered Preferences[J].Journal of Logic and Computation,2009,19(3):475-502
[35] May K O.A Set of Independent Necessary and Sufficient Conditions for Simple Majority Deisions[J].Econometrica,1952,20(4):680-684
[36] Young H P.Social Choice Scoring Functions[J].SIAM Journal on Applied Mathematics,1975,28(4):824-838
[37] Meskanen T,Nurmi H.Closeness Counts in Social Choice[M]∥Braham M,Steffen F,eds.Power,Freedom,and Voting.Springer-Verlag,2008:289-306
[38] Elkind E,Faliszewski P,Slinko A.Distance Rationalization ofVoting Rules[C]∥Proc.3rd International Workshop on Computational Social Choice (COMSOC-2010).2010:379-390
[39] Elkind E,Faliszewski P,Slinko A M.On the Role of Distances in Defining Voting Rules[C]∥Proc.9th International Conference on Autonomous Agents and Multiagent Systems(AAMAS-2010).2010:375-382
[40] Dodgson C L,McLean I I,Urken A,et al.Classics of SocialChoice[M].University of Michigan Press,1995
[41] Farkas D,Nitzan S.The Borda Rule and Pareto Stability:AComment[J].Econometrica,1979,47(5):1305-1306
[42] Nitzan S.Some Measures of Closeness to Unanimity and their Implications[J].Theory and Decision,1981,13(2):129-138
[43] de Condorcet M,McLean I I,Urken A,et al.Classics of Social Choice[M].University of Michigan Press,1995
[44] Young H P.Optimal Voting Rules[J].Journal of Economic Per-spectives,1995,9(1):51-64
[45] Conitzer V,Sandholm T.Common Voting Rules as MaximumLikelihood Estimators[C]∥Uncertainty in Artificial Intelligence:Proceedings of The Twentieth Conference(UAI2005).San Mateo,CA:Morgan Kaufmann Publishers,2005:145-152
[46] Conitzer V,Walsh T,Xia Li-rong.Dominating Manipulations in Voting with Partial Information[C]∥Proc.AAAI-2011.2011:638-643
[47] Reijngoud A,Endriss U.Voter Response to Iterated Poll Information[C]∥Proc.AAMAS-2012.2012:635-644
[48] Kannai Y,Peleg B.A Note on the Extension of an Order on a Set to the Power Set[J].Journal of Economic Theory,1984,32(1):172-175
[49] Barberà S,Bossert W,Pattanaik P K.Ranking sets of objects[M]∥Barberà S,Hammond P,Seidl C,eds.Handbook of Utility Theory,Volume 2:Extensions.Boston:Kluwer Academic Publishers,2004
[50] Geist C.Automated Search for Impossibility Theorems in ChoiceTheory:Ranking Sets of Objects [D].Amsterdam:ILLC,University of Amsterdam,2010
[51] Geist C,Endriss U.Automated Search for Impossibility Theo-rems in Social Choice Theory:Ranking Sets of Objects[J].Journal of Artificial Intelligence Research,2011,40:143-174
[52] Kelly J S.Strategy-Proofness and Social Choice Functions without Single-Valuedness[J].Econometrica,1977,45(2):439-446
[53] Grdenfors P.Manipulation of Social Choice Functions[J].Journal of Economic Theory,1976,13(2):217-228
[54] Duggan J,Schwartz T.Strategic Manipulation w/o Resoluteness or Shared Beliefs:Gibbard-Satterthwaite Generalized[J].Social Choice and Welfare,2000,17(1):85-93
[55] Taylor A D.The Manipulability of Voting Systems[J].The American Mathematical Monthly,2002,109(4):321-337
[56] Endriss U,Pini M S,Rossi F,et al.Preference Aggregation over Restricted Ballot Languages:Sincerity and Strategy-Proofness[C]∥Proc.the 21st International Joint Conference on Artificial Intelligence.2009:122-127
[57] Vickrey W.Counterspeculation,Auctions,and CompetitiveSealed Tenders[J].Journal of Finance,1961,16(1):8-37
[58] Endriss U.Vote Manipulation in the Presence of Multiple Sincere Ballots[C]∥Proc.the 11th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2007),2007.Presses Universitaires de Louvain,2007:125-134
[59] Endriss U.Sincerity and Manipulation under Approval Voting[J].Theory and Decision,2013,74(3):335-355
[60] Black D.On the Rationale of Group Decision-Making[J].Journal of Political Economy,1948,56(1):23-34
[61] Moulin H.On Strategy-Proofness and Single Peakedness[J].Public Choice,1980,35(4):437-455
[62] Sen A K.A Possibility Theorem on Majority Decisions[J].Econometrica,1966,34(2):491-499
[63] III J J B,Tovey C A,Trick M A.The Computational Difficulty of Manipulating an Election[J].Social Choice and Welfare,1989,6(3):227-241
[64] III J J B,Orlin J B.Single Transferable Vote Resists Strategic Voting[J].Social Choice and Welfare,1991,8(4):341-354
[65] Conitzer V,Sandholm T,Lang J.When are Elections with Few Candidates Hard to Manipulate? [J].Journal of the ACM,2007,54(3):14
[66] Faliszewski P,Procaccia A D.AI’s War on Manipulation:AreWe Winning? [J].AI Magazine,2010,31(4):53-64
[67] Faliszewski P,Hemaspaandra E,Hemaspaandra L A,et al.ARicher Understanding of the Complexity of Election Systems[C]∥Fundamental Problems in Computing.Berlin:Springer-Verlag,2009:375-406
[68] Faliszewski P,Hemaspaandra E,Hemaspaandra L A.How Hard is Bribery in Elections? [J].Journal of Artificial Intelligence Research,2009,35:485-532
[69] Chevaleyre Y,Endriss U,Lang J,et al.Preference Handling in Combinatorial Domains:From AI to Social Choice[J].AI Magazine,2008,29(4):37-46
[70] Brams S J,Kilgour D M,Zwicker W S.The Paradox of Multiple Elections[J].Social Choice and Welfare,1998,15(2):211-236
[71] Brams S J,Kilgour D M,Sanver M R.A Minimax Procedure for Electing Committees[J].Public Choice,2007,132(3/4):401-420
[72] Grandi U,Endriss U.Binary Aggregation with Integrity Con-straints[C]∥Proc.the 22nd International Joint Conference on Artificial Intelligence (IJCAI-2011).2011:204-209
[73] Endriss U,Grandi U.Binary Aggregation by Selection of theMost Representative Voter[C]∥Proc.the 7th Multidisciplinary Workshop on Advances in Preference Handling (MPREF-2013).2013
[74] Lang J.Logical Preference Representation and CombinatorialVote[J].Annals of Mathematics and Artificial Intelligence,2004,42(1/3):37-71
[75] Uckelman J.More Than the Sum of its Parts:Compact Prefe-rence Representation over Combinatorial Domains[D].Amsterdam:University of Amsterdam,2009
[76] Lacy D,Niou E M S.A Problem with Referendums[J].Journal of Theoretical Politics,2000,12(1):5-31
[77] Boutilier C,Brafman R I,Domshlak C,et al.CP-nets:A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements[J].Journal of Artificial Intelligence Research,2004,21:135-191
[78] Lang J,Xia Li-rong.Sequential Composition of Voting Rules in Multi-issue Domains[J].Mathematical Social Sciences,2009,57(3):304-324
[79] III J J B,Tovey C A,Trick M A.Voting schemes for which it can be difficult to tell who won the election[J].Social Choice Welfare,1989,6(2):157-165
[80] Hemaspaandra E,Hemaspaandra L A,Rothe J.Exact Analysis of Dodgson Elections[J].Journal of the ACM,1997,44(6):806-825
[81] Hemaspaandra E,Spakowski H,Vogel J.The Complexity ofKemeny Elections [J].Theoretical Computer Science,2005,349(3):382-391
[82] Elkind E,Faliszewski P,Slinko A.On the Role of Distances in Defining Voting Rules[C]∥Proc.the 9th International Confe-rence on Autonomous Agents and Multiagent Systems(AAMAS-2010).2010
[83] Woeginger G J.Banks Winners in Tournaments are Difficult to Recognize[J].Social Choice and Welfare,2003,0(3):523-528
[84] Downey R G,Fellows M R.Parameterized Complexity[M].Berlin:Springer-Verlag,1999
[85] Betzler N,Guo Jiong,Niedermeier R.Parameterized Computational Complexity of Dodgson and Young Elections[J].Information and Computation,2010,208(2):165-177
[86] Betzler N,Bredereck R,Chen Jie-hua,et al.Studies in Computational Aspects of Voting:A Parameterized Complexity Perspective[M].The Multivariate Algorithmic Revolution and Beyond.Berlin:Springer,2012:318-363
[87] Konczak K,Lang J.Voting Procedures with Incomplete Preferences[C]∥Proc.IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling.2005
[88] Conitzer V,Sandholm T.Vote Elicitation:Complexity and Strategy-Proofness [C]∥Proc.the National Conference on Artificial Intelligence (AAAI-2002).2002:392-397
[89] Walsh T.Complexity of Terminating Preference Elicitation[C]∥Proc.AAMAS-2008.2008:967-974
[90] Betzler N,Dorn B.Towards a Dichotomy for the Possible Winner Problem in Elections Based on Scoring Rules[J].Journal of Computer and System Sciences,2010,76(8):812-836
[91] Xia Li-rong,Conitzer V.Determining Possible and necessaryWinners under Common Voting Rules Given Partial Orders[C]∥Proc.23rd AAAI Conference on Artificial Intelligence(AAAI-2008).Chicago,2008:202-207
[92] Chevaleyre Y,Lang J,Maudet N,et al.Possible Winners when New Candidates are Added:The Case of Scoring Rules[C]∥Proc.24th AAAI Conference on Artificial Intelligence(AAAI-2010) .Atlanta,2010:762-767
[93] Chevaleyre Y,Lang J,Maudet N,et al.Compiling the Votes of a Subelectorate[C]∥Proc.21st International Joint Conference on Artificial Intelligence(IJCAI-2009).2009:97-102
[94] Conitzer V,Sandholm T.Commu- nication Complexity of Common Voting Rules [C]∥Proc.6th ACM Conference on Electronic Commerce(EC-2005).Vancouver,2005
[95] Banzhaf J F.Weighted Voting Doesn’t Work:A Mathematical Analysis[J].Rutgers Law Review,1965,19(2):317-343
[96] Felsenthal D S,Machover M.The Measurement of Voting Power[M].Cheltenham:Edward Elgar Publishing,1998
[97] Shapley L S,Shubik M.A Method for Evaluating the Distribution of Power in a Committee System[J].American Political Science Review,1954,48(3):787-792
[98] Matsui Y,Matsui T.NP-Completeness for Calculating Power Indices of Weighted Majority Games[J].Theoretical Computer Science,2001,263(1/2):305-310
[99] Elkind E,Goldberg L A,Goldberg P W,et al.On the Computational Complexity of Weighted Voting Games[J].Annals of Mathematics and Artificial Intelligence,2009,56(2):109-131
[100] Balinski M L,Young H P.Fair Representation:Meeting theIdeal of One Man,One Vote(2nd edition)[M].Washington D.C:Bookings Institution Press,2001
[101] Bart Jacobs,Wolter Pieters.Electronic Voting in the Nether-lands:From Early Adoption to Early Abolishment[M].Foundations of Security Analysis and Design V Lecture Notes in Computer Science,Volume 5725.2009:121-144
[102] Rivest R L.The ThreeBallot Voting System[R].MIT-CSAIL.Cambridge,2006
[103] Laslier J-F.Tournament Solutions and Majority Voting[M].Berlin:Springer-Verlag,1997
[104] Brandt F,Fischer F,Harrenstein P,et al.A Computational Analysis of the Tourna- ment Equilibrium Set[J].Social Choice and Welfare,2010,34(4):597-609
[105] Davenport A,Kalagnanam J.A Computational Study of theKemeny Rule for Preference Aggregation[C]∥Proc.19th AAAI,2004.Menlo Park:AAAI Press,2004:697-702
[106] Conitzer V.Computing Slater Rankings Using Similarities a-mong Candidates[C]∥Proc.21st National Conference on Artificial Intelligence (AAAI-06).Boston:AAAI Press,2006:613-619
[107] McCabe-Dansted J C,Pritchard G,Slinko A.Approximabilityof Dodgson’s Rule[J].Social Choice and Welfare,2008,31(2):311-330
[108] Caragiannis I,Kaklamanis C,Karanikolas N,et al.Socially Desirable Approximations for Dodgson’s Voting Rule[C]∥Proc.11th ACM Conference on Electronic Commerce(EC-2010).Cambridge,2010:253-262
[109] Airiau S,Endriss U.Iterated Majority Voting[C]∥Proc.1st International Conference on Algorithmic Decision Theory (ADT-2009).Berlin:Springer-Verlag,2009:38-49
[110] Meir R,Polukarov M,Rosenschein J S,et al.Convergence toEquilibria in Plurality Voting [C]∥Proc.the 24th National Conference on Artificial Intelligence(AAAI-2010).Atlanta,2010:823-828
[111] Nguyen T T.Approximability and Inapproximability of Social Welfare Optimization in Multiagent Resource Allocation[D].Düsseldorf:University of Düsseldorf,2013

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!