摘要: 社会选择理论是研究如何表达和聚合个体选择的一门学问。而社会选择理论与计算机科学的融合产生了称为计算社会选择的交叉学科,该学科成为社会计算的重要研究内容之一,在人工智能、经济和计算性理论领域引起了轰动。其一方面引入了复杂性分析和算法设计等计算机学科中常用的技术来对社会选择机制进行研究;另一方面也通过引入社会选择理论中的概念来推动计算机技术的发展,特别是在多智能体系统研究中有着成功的应用。投票理论是计算社会选择中最重要的研究主题之一。首先介绍常见的投票方法以及投票理论的形式化框架;再对投票理论中所关心的操纵问题做分析;然后介绍在组合域上的投票;最后对其他相关问题作简要介绍,并对该领域未来的发展与应用做出展望。
[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] Grdenfors 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! |
|