Egalitarian judgment aggregation

Springer Science and Business Media LLC - Tập 37 - Trang 1-32 - 2023
Sirin Botan1, Ronald de Haan2, Marija Slavkovik3, Zoi Terzopoulou4
1School of Computer Science and Engineering, UNSW Sydney, Sydney, Australia
2Institute for Logic, Language and Computation (ILLC), University of Amsterdam, Amsterdam, The Netherlands
3Department of Information Science and Media Studies, University of Bergen, Bergen, Norway
4GATE, Saint-Etienne School of Economics, University of Lyon - Saint-Etienne, Saint-Étienne, France

Tóm tắt

Egalitarian considerations play a central role in many areas of social choice theory. Applications of egalitarian principles range from ensuring everyone gets an equal share of a cake when deciding how to divide it, to guaranteeing balance with respect to gender or ethnicity in committee elections. Yet, the egalitarian approach has received little attention in judgment aggregation—a powerful framework for aggregating logically interconnected issues. We make the first steps towards filling that gap. We introduce axioms capturing two classical interpretations of egalitarianism in judgment aggregation and situate these within the context of existing axioms in the pertinent framework of belief merging. We then explore the relationship between these axioms and several notions of strategyproofness from social choice theory at large. Finally, a novel egalitarian judgment aggregation rule stems from our analysis; we present complexity results concerning both outcome determination and strategic manipulation for that rule.

Tài liệu tham khảo

Amanatidis, G., Birmpas, G., & Markakis, E. (2016). On truthful mechanisms for maximin share allocations. In Proceedings of the 25th international joint conference on artificial intelligence (IJCAI). Barberà, S., Bossert, W., & Pattanaik, P. K. (2004). Ranking sets of objects. Handbook of utility theory (pp. 893–977). Springer. Baum, S. D. (2017). Social choice ethics in artificial intelligence. AI & Society 1–12. Baumeister, D., Erdélyi, G., Erdélyi, O. J., & Rothe, J. (2013). Computational aspects of manipulation and control in judgment aggregation. In Proceedings of the 3rd international conference on algorithmic decision theory (ADT). Baumeister, D., Erdélyi, G., Erdélyi, O. J., & Rothe, J. (2015). Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules. Mathematical Social Sciences, 76, 19–30. Baumeister, D., Rothe, J., & Selker, A. -K. (2017). Strategic behavior in judgment aggregation. In Trends in computational social choice (pp. 145–168). Lulu. com. Botan, S., de Haan, R., Slavkovik, M., & Terzopoulou, Z. (2021). Egalitarian judgment aggregation. In Proceedings of the 20th international conference on autonomous agents and multiagent systems (AAMAS). Botan, S. & Endriss, U. (2020). Majority-strategyproofness in judgment aggregation. In Proceedings of the 19th international conference on autonomous agents and multiagent systems (AAMAS). Brams, S. J., Jones, M. A., & Klamler, C. (2008). Proportional pie-cutting. International Journal of Game Theory, 36(3–4), 353–367. Brams, S. J., Kilgour, D. M., & Sanver, M. R. (2007). A minimax procedure for electing committees. Public Choice, 132(3), 401–420. Budish, E. (2011). The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6), 1061–1103. Caragiannis, I., Kalaitzis, D., & Markakis, E. (2010). Approximation algorithms and mechanism design for minimax approval voting. In Proceedings of the 24th AAAI conference on artificial intelligence (AAAI). Chen, Y., Lai, J. K., Parkes, D. C., & Procaccia, A. D. (2013). Truth, justice, and cake cutting. Games and Economic Behavior, 77(1), 284–297. Chen, Z.-Z., & Toda, S. (1995). The complexity of selecting maximal solutions. Information and Computation, 119, 231–239. Conitzer, V., Sinnott-Armstrong, W., Borg, J. S., Deng, Y., & Kramer, M. (2017). Moral decision making frameworks for artificial intelligence. In Proceedings of the 31st AAAI conference on artificial intelligence (AAAI). Cook, S. A. (1971). The complexity of theorem-proving procedures. In Proceedings of the 3rd annual ACM symposium on theory of computing (pp. 151–158). Shaker Heights. Dalton, H. (1920). The measurement of the inequality of incomes. Economic Journal, 30(119), 348–461. Dietrich, F., & List, C. (2007). Arrow’s theorem in judgment aggregation. Social Choice and Welfare, 29(1), 19–33. Dietrich, F., & List, C. (2007). Strategy-proof judgment aggregation. Economics & Philosophy, 23(3), 269–300. Duggan, J., & Schwartz, T. (2000). Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized. Social Choice and Welfare, 17(1), 85–93. Eiter, T., & Gottlob, G. (1995). On the computational cost of disjunctive logic programming: Propositional case. Annals of Mathematics and Artifficial Intelligence, 15(3–4), 289–323. Endriss, U. (2016). Judgment aggregation. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. D. Procaccia (Eds.), Handbook of computational social choice. Cambridge University Press. Endriss, U. (2016). Judgment aggregation. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. D. Procaccia (Eds.), Handbook of computational social choice. Cambridge University Press. Endriss, U. & de Haan, R. (2015). Complexity of the winner determination problem in judgment aggregation: Kemeny, Slater, Tideman, Young. In Proceedings of the 14th international conference on autonomous agents and multiagent systems (AAMAS). Endriss, U., de Haan, R., Lang, J., & Slavkovik, M. (2020). The complexity landscape of outcome determination in judgment aggregation. Journal of Artificial Intelligence Research. Endriss, U., Grandi, U., de Haan, R., & Lang, J. (2016). Succinctness of languages for judgment aggregation. In Proceedings of the 15th international conference on the principles of knowledge representation and reasoning (KR). Endriss, U., Grandi, U., & Porello, D. (2012). Complexity of judgment aggregation. Journal of Artificial Intelligence Research, 45, 481–514. Everaere, P., Konieczny, S., & Marquis, P. (2014). On egalitarian belief merging. In Proceedings of the 14th international conference on the principles of knowledge representation and reasoning (KR). Everaere, P., Konieczny, S., & Marquis, P. (2017). Belief merging and its links with judgment aggregation. In U. Endriss (Ed.), Trends in computational social choice (pp. 123–143). AI Access Foundation. Fishburn, P. C., & Brams, S. J. (1983). Paradoxes of preferential voting. Mathematics Magazine, 56(4), 207–214. Foley, D. K. (1967). Resource allocation and the public sector. Yale Economic Essays, 7(1), 45–98. Gärdenfors, P. (1976). Manipulation of social choice functions. Journal of Economic Theory, 13(2), 217–228. Gebser, M., Kaminski, R., Kaufmann, B., & Schaub, T. (2012). Answer set solving in practice. Synthesis lectures on artificial intelligence and machine learning. Morgan & Claypool Publishers. Gebser, M., Kaminski, R., & Schaub, T. (2011). Complex optimization in answer set programming. Theory and Practics of Logic Programming, 11(4–5), 821–839. Gelfond, M. (2006). Answer sets. In F. van Harmelen, V. Lifschitz, & B. Porter (Eds.), Handbook of knowledge representation. Elsevier. Goldreich, O. (2010). P, NP, and NP-completeness: The basics of complexity theory. Cambridge University Press. Grandi, U. & Endriss, U. (2010). Lifting rationality assumptions in binary aggregation. In Proceedings of the 24th AAAI conference on artificial intelligence (AAAI). Grossi, D. & Pigozzi, G. (2014). Judgment aggregation: A primer, volume 8 of synthesis lectures on artificial intelligence and machine learning. Morgan & Claypool Publishers. de Haan, R. (2018). Hunting for tractable languages for judgment aggregation. In Proceedings of the 16th international conference on the principles of knowledge representation and reasoning (KR). de Haan, R. & Slavkovik, M. (2017). Complexity results for aggregating judgments using scoring or distance-based procedures. In Proceedings of the 16th conference on autonomous agents and MultiAgent systems, AAMAS. de Haan, R. & Slavkovik, M. (2019). Answer set programming for judgment aggregation. In Proceedings of the 28th international joint conference on artificial intelligence (IJCAI). Hammond, P. J. (1976). Equity, arrow’s conditions, and rawls’ difference principle. Econometrica, 44(4), 793–804. Kelly, J. S. (1977). Strategy-proofness and social choice functions without singlevaluedness. Econometrica, 45(2), 439–446. Köbler, J. & Thierauf, T. (1990). Complexity classes with advice. In Proceedings of the 5th annual structure in complexity theory conference. Konieczny, S., & Pérez, R. P. (2011). Logic based merging. Journal of Philosophical Logic, 40(2), 239–270. Krajicek, J. (1995). Bounded arithmetic, propositional logic and complexity theory. Cambridge University Press. Krentel, M. W. (1988). The complexity of optimization problems. Journal of Computer and System Sciences, 36(3), 490–509. Kruger, J. & Terzopoulou, Z. (2020). Strategic manipulation with incomplete preferences: Possibilities and impossibilities for positional scoring rules. In Proceedings of the 19th international conference on autonomous agents and multiagent systems (AAMAS). Lackner, M. & Skowron, P. (2018). Approval-based multi-winner rules and strategic voting. In Proceedings of the 27th international joint conference on artificial intelligence (IJCAI). Lang, J., Pigozzi, G., Slavkovik, M., & van der Torre, L. (2011). Judgment aggregation rules based on minimization. In Proceedings of the 13th conference on theoretical aspects of rationality and knowledge (TARK). Lang, J. & Slavkovik, M. (2014). How hard is it to compute majority-preserving judgment aggregation rules? In Proceedings of the 21st European conference on artificial intelligence (ECAI). List, C., & Pettit, P. (2002). Aggregating sets of judgments: An impossibility result. Economics and Philosophy, 18(1), 89–110. Miller, M. K., & Osherson, D. (2009). Methods for distance-based judgment aggregation. Social Choice and Welfare, 32(4), 575–601. Mossel, E. & Tamuz, O. (2010). Truthful fair division. In Proceedings of the 3rd international symposium on algorithmic game theory (SAGT). Moulin, H. (1988). Axioms of cooperative decision making, volume 15 of econometric society monographs. Cambridge University Press. Nehring, K., Pivato, M., & Puppe, C. (2014). The condorcet set: Majority voting over interconnected propositions. Journal of Economic Theory, 151, 268–303. Noothigattu, R., Gaikwad, S. S., Awad, E., Dsouza, S., Rahwan, I., Ravikumar, P., & Procaccia, A. D. (2018). A voting-based system for ethical decision making. In Proceedings of the 32nd AAAI conference on artificial intelligence (AAAI). Peters, D. (2018). Proportionality and strategyproofness in multiwinner elections. In: Proceedings of the 17th international conference on autonomous agents and multiagent systems (AAMAS). Pigozzi, G. (2006). Belief merging and the discursive dilemma: An argument-based account to paradoxes of judgment aggregation. Synthese, 152(2), 285–298. Rawls, J. (1971). A theory of justice. Belknap Press. Sanver, M. R., & Zwicker, W. S. (2009). One-way monotonicity as a form of strategy-proofness. International Journal of Game Theory, 38(4), 553–574. Schaefer, T. J. (1978). The complexity of satisfiability problems. In Conference record of the 10th annual ACM symposium on theory of computing. ACM. Sen, A. (1997). Choice, welfare and measurement. Harvard University Press. Terzopoulou, Z. & Endriss, U. (2018). Modelling iterative judgment aggregation. In Proceedings of the 32nd AAAI conference on artificial intelligence (AAAI). Wagner, K. W. (1990). Bounded query classes. SIAM Journal on Computing, 19(5), 833–846. Zwicker, W. S. (2016). Introduction to the theory of voting. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. D. Procaccia (Eds.), Handbook of computational social choice. Cambridge University Press.