Taxonomy of powerful voters and manipulation in the framework of social choice functions
Tóm tắt
In this work we pursue the study of manipulability of social choice functions through “liftings”, that is, mappings which extend orderings over points to orderings over subsets of points. We discover a very weak notion of monotony which is closely related to independence of irrelevant alternatives. This allows us to establish an interesting and general theorem on manipulability. We show that this theorem is indeed equivalent to Arrow-Sen Theorem in the class of nonmanipulable social choice functions. As a consequence of this general theorem we obtain a manipulation theorem for linear profiles in the style of Gibbard-Satterthwaite Theorem but for social choice functions instead of voting schemes. We introduce the notion of nominator, which is a natural generalization of the notion of pairwise nominator introduced by Kelly. Then, we establish that, in the presence of rational properties over liftings, a social choice function is either manipulable, or it admits a nominator. In addition, we do a comparative study on different types of powerful voters (dictators, nominators, pairwise nominators and weak-dictators) present in the literature. Although, in general, they are non-equivalent notions, we show that under some natural conditions, modulo nonmanipulability, the last three are equivalent or even all the notions are equivalent.
Tài liệu tham khảo
citation_title=Social choice and individual values; citation_publication_date=1951; citation_id=CR1; citation_author=K Arrow; citation_publisher=Wiley
citation_title=An interview with Kenneth Arrow; citation_inbook_title=Handbook of Social Choice and Welfare, Handbooks in Economics; citation_publication_date=2011; citation_pages=4-24; citation_id=CR2; citation_author=K Arrow; citation_author=JS Kelly; citation_publisher=North-Holland
citation_title=Handbook of Social Choice and Welfare, Handbooks in Economics; citation_publication_date=2002; citation_id=CR3; citation_author=K Arrow; citation_author=AK Sen; citation_author=K Suzumura; citation_publisher=North-Holland
citation_journal_title=Econometrica; citation_title=The manipulation of social choice mechanisms that do not leave too much to chance; citation_author=S Barberà; citation_volume=45; citation_issue=7; citation_publication_date=1977; citation_pages=1573-1588; citation_doi=10.2307/1913950; citation_id=CR4
citation_title=Strategy-proof social choice; citation_inbook_title=Choice and Welfare, Handbooks in Economics; citation_publication_date=2011; citation_pages=731-831; citation_id=CR5; citation_author=S Barberà; citation_publisher=North-Holland
citation_title=Ranking sets of objects, Handbook of Utility Theory; citation_publication_date=2004; citation_id=CR6; citation_author=S Barberà; citation_author=W Bossert; citation_author=PK Pattanaik; citation_publisher=Kluwer Publisher
citation_journal_title=Journal of Economic Theory; citation_title=Manipulation of social decision functions; citation_author=S Barberà; citation_volume=15; citation_issue=2; citation_publication_date=1977; citation_pages=266-278; citation_doi=10.1016/0022-0531(77)90101-6; citation_id=CR7
de Borda JC (1784) Mémoire sur les élections au scrutin. Histoire de l’Académie Royale des Sciences
citation_journal_title=Journal of Economic theory; citation_title=Ranking opportunity sets: an axiomatic approach; citation_author=W Bossert, PK Pattanaik, Y Xu; citation_volume=63; citation_issue=2; citation_publication_date=1994; citation_pages=326-345; citation_doi=10.1006/jeth.1994.1045; citation_id=CR9
Brandt F (2011) Group-strategyproof irresolute social choice functions. In: Walsh T (ed.) IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pp 79–84
Brandt F, Brill M (2011) Necessary and sufficient conditions for the strategyproofness of irresolute social choice functions. In: Apt KR (ed.) Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2011), Groningen, The Netherlands, July 12-14, 2011, pp 136–142. ACM
Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (2016) (eds.): Handbook of Computational Social Choice. Cambridge University Press
Camacho F, Pino Pérez R (2011) Leximax relations in decision making through the dominance plausible rule. In: Liu W (ed) Symbolic and Quantitative Approaches to Reasoning with Uncertainty, vol 6717. ECSQARU 2011, Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, pp 569–581
citation_journal_title=Mathematical Social Sciences; citation_title=Decision-making through dominance plausible rule: New characterizations; citation_author=F Camacho, R Pino Pérez; citation_volume=113; citation_publication_date=2021; citation_pages=107-115; citation_doi=10.1016/j.mathsocsci.2021.05.003; citation_id=CR14
citation_journal_title=Social Choice and Welfare; citation_title=Multi-valued strategy-proof social choice rules; citation_author=S Ching, L Zhou; citation_volume=19; citation_issue=3; citation_publication_date=2002; citation_pages=569-580; citation_doi=10.1007/s003550100134; citation_id=CR15
citation_journal_title=Annales de l’Institut Henri Poincaré; citation_title=La prévision: Ses lois logiques, ses sources subjectives; citation_author=B Finetti; citation_volume=17; citation_publication_date=1937; citation_pages=1-68; citation_id=CR21
Dubois D, Fargier H (2004) A unified framework for order-of-magnitude confidence relations. In: UAI ’04, Proceedings of the 20th Conference in Uncertainty in Artificial Intelligence, July 7-11 2004, Banff, Canada, pp 138–145
Dubois D, Lang J, Prade H (1994) Possibilistic logic. In: Gabbay D, Hogger C, Robinson J (eds.) Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 3: Nonmonotonic Reasoning and Uncertain Reasoning, pp 439—513. Oxford University Press, Inc
citation_journal_title=Social Choice and Welfare; citation_title=Strategic manipulability without resoluteness or shared beliefs: Gibbard-satterthwaite generalized; citation_author=J Duggan, T Schwartz; citation_volume=17; citation_issue=1; citation_publication_date=2000; citation_pages=85-93; citation_doi=10.1007/PL00007177; citation_id=CR18
Endriss U (2017) (ed.): Trends in Computational Social Choice. AI Access
citation_journal_title=Public Choice; citation_title=Nonmanipulable multi-valued social decision functions; citation_author=A Feldman; citation_volume=34; citation_publication_date=1979; citation_pages=177-188; citation_doi=10.1007/BF00129525; citation_id=CR20
citation_journal_title=Theory and Decision; citation_title=Even-chance lotteries in social choice theory; citation_author=PC Fishburn; citation_volume=3; citation_issue=1; citation_publication_date=1972; citation_pages=18-40; citation_doi=10.1007/BF00139351; citation_id=CR22
citation_title=The theory of social choice; citation_publication_date=1973; citation_id=CR23; citation_author=PC Fishburn; citation_publisher=Princeton University Press
Friedman N, Halpern J (1998) Plausibility measures and default reasoning. arXiv preprint cs/9808007
citation_journal_title=Journal of Economic Theory; citation_title=Manipulation of social choice functions; citation_author=P Gärdenfors; citation_volume=13; citation_issue=2; citation_publication_date=1976; citation_pages=217-228; citation_doi=10.1016/0022-0531(76)90016-8; citation_id=CR25
citation_title=On definitions of manipulation of social choice functions; citation_inbook_title=Aggregation and revelation of preferences; citation_publication_date=1979; citation_pages=29-36; citation_id=CR26; citation_author=P Gärdenfors; citation_publisher=North-Holland
citation_journal_title=Journal of Artificial Intelligence Research; citation_title=Automated search for impossibility theorems in social choice theory: Ranking sets of objects; citation_author=C Geist, U Endriss; citation_volume=40; citation_publication_date=2011; citation_pages=143-174; citation_doi=10.1613/jair.3126; citation_id=CR27
citation_journal_title=Econometrica; citation_title=Manipulation of voting schemes: A general result; citation_author=A Gibbard; citation_volume=41; citation_issue=4; citation_publication_date=1973; citation_pages=587-601; citation_doi=10.2307/1914083; citation_id=CR28
citation_journal_title=Journal of Artificial Intelligence Research; citation_title=Defining relative likelihood in partially-ordered preferential structures; citation_author=JY Halpern; citation_volume=7; citation_publication_date=1997; citation_pages=1-24; citation_doi=10.1613/jair.391; citation_id=CR29
citation_journal_title=Theory and Decision; citation_title=The independence condition in the theory of social choice; citation_author=B Hansson; citation_volume=4; citation_publication_date=1973; citation_pages=25-49; citation_doi=10.1007/BF00133397; citation_id=CR30
citation_journal_title=Econometrica; citation_title=Strategy-proofness and social choice functions without singlevaluedness; citation_author=JS Kelly; citation_volume=45; citation_issue=2; citation_publication_date=1977; citation_pages=439-446; citation_doi=10.2307/1911220; citation_id=CR31
citation_title=Social Choice Theory: An Introduction; citation_publication_date=1988; citation_id=CR32; citation_author=JS Kelly; citation_publisher=Springer-Verlag
Lang J, van der Torre LW (2008) From belief change to preference change. In: Ghallab M, Spyropoulos C, Fakotakis N, Avouris N (eds.) Proceedings of 18th European Conference on Artificial Intelligence. ECAI 2008, Frontiers in Artificial Intelligence and Applications, vol. 178, pp 351–355. IOS Press
citation_journal_title=Revista Colombiana de Matemáticas; citation_title=A weak version of Barberà-Kelly’s theorem; citation_author=J Leal, R Pino Pérez; citation_volume=51; citation_publication_date=2017; citation_pages=173-194; citation_doi=10.15446/recolma.v51n2.70900; citation_id=CR34
Lewis D (1973) Counterfactuals and comparative possibility. In: Harper W, Stalnaker R, Pearce G (eds.) IFS. The University of Western Ontario Series in Philosophy of Science (A Series of Books in Philosophy of Science, Methodology, Epistemology, Logic, History of Science, and Related Fields), pp 57–85. Springer, Dordrecht
citation_journal_title=Artificial Intelligence; citation_title=Impossibility in belief merging; citation_author=A Mata Díaz, R Pino Pérez; citation_volume=251; citation_publication_date=2017; citation_pages=1-34; citation_doi=10.1016/j.artint.2017.06.003; citation_id=CR36
Mata Díaz A, Pino Pérez R (2018) Epistemic states, fusion and strategy-proofness. In: Fermé E, Villata S (eds.) Proceedings of the 17th International Workshop on Non-Monotonic Reasoning. NMR-2018, Tempe, Arizona, USA., pp 176–185
citation_journal_title=Revista Iberica de Sistemas e Tecnologias de Informaçao (RISTI); citation_title=Manipulability in logic-based fusion of belief bases: Indexes vs. liftings; citation_author=A Mata Díaz, R Pino Pérez; citation_volume=2019; citation_issue=E20; citation_publication_date=2019; citation_pages=490-503; citation_id=CR38
Mata Díaz A, Pino Pérez R (2021) Merging epistemic states and manipulation. In: Vejnarová J, Wilson N (eds.) Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 16th European Conference, ECSQARU 2021, Prague, Czech Republic, September 21-24, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12897, pp 457–470. Springer
citation_title=Axioms of cooperative decision making; citation_publication_date=1988; citation_id=CR40; citation_author=H Moulin; citation_publisher=Cambridge University Press
citation_journal_title=Journal of Logic and Computation; citation_title=Aggregating Partially Ordered Preferences; citation_author=M Pini, F Rossi, K Venable, T Walsh; citation_volume=19; citation_issue=3; citation_publication_date=2009; citation_pages=475-502; citation_doi=10.1093/logcom/exn012; citation_id=CR41
citation_journal_title=Journal of Economic Theory; citation_title=Strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions; citation_author=MA Satterthwaite; citation_volume=10; citation_issue=2; citation_publication_date=1975; citation_pages=187-217; citation_doi=10.1016/0022-0531(75)90050-2; citation_id=CR42
citation_journal_title=The Review of Economic Studies; citation_title=Quasi-transitivity, rational choice and collective decisions; citation_author=AK Sen; citation_volume=36; citation_issue=3; citation_publication_date=1969; citation_pages=381-393; citation_doi=10.2307/2296434; citation_id=CR43
citation_journal_title=The Review of Economic Studies; citation_title=Choice functions and revealed preference; citation_author=AK Sen; citation_volume=38; citation_issue=3; citation_publication_date=1971; citation_pages=307-317; citation_doi=10.2307/2296384; citation_id=CR44
citation_journal_title=Metroeconomica; citation_title=On the meaning and measure of uncertainty; citation_author=GLS Shackle; citation_volume=5; citation_publication_date=1953; citation_pages=97-115; citation_doi=10.1111/j.1467-999X.1953.tb00729.x; citation_id=CR45
citation_title=Uncertainty in economics and other reflections; citation_publication_date=1955; citation_id=CR46; citation_author=GLS Shackle; citation_publisher=Cambridge University Press
citation_title=Ordinal conditional functions: A dynamic theory of epistemic states; citation_inbook_title=The University of Western Ontario Series in Philosophy of Science (A Series of Books in Philosophy of Science, Methodology, Epistemology, Logic, History of Science, and Related Fields); citation_publication_date=1988; citation_pages=105-134; citation_id=CR47; citation_author=W Spohn; citation_publisher=Springer
citation_journal_title=The American Mathematical Monthly; citation_title=The manipulability of voting systems; citation_author=AD Taylor; citation_volume=109; citation_issue=4; citation_publication_date=2002; citation_pages=321-337; citation_doi=10.1080/00029890.2002.11920895; citation_id=CR48
citation_title=Social Choice and the Mathematics of Manipulation; citation_publication_date=2005; citation_id=CR49; citation_author=AD Taylor; citation_publisher=Cambridge University Press
citation_journal_title=Journal of Philosophical Logic; citation_title=Everything else being equal: A modal logic for ceteris paribus preferences; citation_author=J Benthem, P Girard, O Roy; citation_volume=38; citation_publication_date=2009; citation_pages=83-125; citation_doi=10.1007/s10992-008-9085-3; citation_id=CR50
citation_journal_title=Journal of Economic Theory; citation_title=Social choice theory without the Pareto principle; citation_author=R Wilson; citation_volume=5; citation_issue=3; citation_publication_date=1972; citation_pages=478-486; citation_doi=10.1016/0022-0531(72)90051-8; citation_id=CR51