Approximately classic judgement aggregation
Tóm tắt
This paper analyzes judgement aggregation problems in which a group of agents independently votes on a set of complex propositions subject to an interdependency constraint. It considers the issue of judgement aggregation from the perspective of approximation; that is, it generalizes the classic framework of judgement aggregation by relaxing the two main constraints assumed in the literature, Consistency and Independence. In doing so, it also considers mechanisms that only approximately satisfy these constraints, that is, satisfy them up to a small fraction of the inputs. The main question raised is whether the relaxation of these constraints significantly alters the class of aggregation mechanisms that meet the two (relaxed) constraints. The main result of this paper is that in the case of a subclass of a natural class of aggregation problems termed “truth-functional agendas,” the set of aggregation mechanisms that meet the constraints does not extend nontrivially when the constraints are relaxed. This paper also shows connections between this new general framework and the works on approximation of preference aggregation as well as the field of Property Testing and particularly linear testing of Boolean functions.
Tài liệu tham khảo
Arrow, K.J.: A difficulty in the concept of social welfare. J. Polit. Econ. 58, 328 (1950)
Banzhaf III, J.F.: Weighted voting doesn’t work: a mathematical analysis. Rutgers Law Rev. 19, 317–343 (1965)
Bellare, M., Coppersmith, D., Håstad, J., Kiwi, M.A., Sudan, M.: Linearity testing in characteristic two. In: FOCS ’95: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pp. 432–441. IEEE Computer Society (1995)
Black, D.: The Theory of Committees and Elections. Kluwer Academic Publishers (1957). Reprint at 1986
Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47, 549–595 (1993)
Bollobás, B.: Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability. Cambridge University Press (1986)
Bovens, L., Rabinowicz, W.: Democratic answers to complex questions—an epistemic perspective. Synthese 150, 131–153 (2006)
Campbell, D.E., Kelly, J.S.: t or 1 - t. That is the trade-off. Econometrica 61, 1355–1365 (1993)
Campbell, D.E., Kelly, J.S.: Information and preference aggregation. Soc. Choice Welf. 17, 3–24 (2000)
Caragiannis, I., Kaklamanis, C., Karanikolas, N., Procaccia, A.D.: Socially desirable approximations for Dodgson’s voting rule. In: Parkes, D.C., Dellarocas, C., Tennenholtz, M. (eds.) Proc. 11th ACM Conference on Electronic Commerce, pp. 253–262 (2010)
Chapman, B.: Rational aggregation. Polit. Philos. Econ. 1(3), 337–354 (2002)
Chen, V., Sudan, M., Xie, N.: Property testing via set-theoretic operations. In: Proceedings 2nd Innovations in Computer Science (ICS 2011), pp. 211–222 (2011)
Claussen, C.A., Røisland, Ø.: The discursive dilemma in monetary policy. Working Paper Series 240, Sveriges Riksbank (Central Bank of Sweden) (2010)
Crama, Y., Hammer, P.L.: Boolean functions: theory, algorithms, and applications, chapter 1—Fundamental concepts and applications, pp. 3–66. Encyclopedia of Mathematics and its Applications. Cambridge University Press (2011)
de Wolf, R.: A brief introduction to Fourier analysis on the Boolean cube. Theory of Computing 1, 1–20 (2008)
Dietrich, F.: Judgment aggregation: (im)possibility theorems. J. Econ. Theory 126, 286–298 (2006)
Dietrich, F., List, C.: Arrow’s theorem in judgment aggregation. Soc. Choice Welf. 29, 19–33 (2007)
Dietrich, F., List, C.: Judgment aggregation by quota rules. J. Theoret. Polit. 19, 391–424 (2007)
Dietrich, F., List, C.: Strategy-proof judgment aggregation. Econ. Philos. 23, 269–300 (2007)
Dokow, E., Holzman, R.: Aggregation of binary evaluations for truth-functional agendas. Soc. Choice Welf. 32, 221–241 (2009)
Dokow, E., Holzman, R.: Aggregation of binary evaluations. J. Econ. Theory 145, 495–511 (2010)
Dokow, E., Holzman, R.: Aggregation of non-binary evaluations. Adv. Appl. Math. 45, 487–504 (2010)
Elkind, E., Faliszewski, P., Slinko, A.: On the role of distances in defining voting rules. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS ’10), pp. 375–382 (2010)
Fischer, E.: The art of uninformed decisions: a primer to property testing. Science 75, 97–126 (2001)
Fishburn, P., Rubinstein, A.: Aggregation of equivalence relations. J. Classif. 3, 61–65 (1986)
Friedgut, E., Kalai, G., Nisan, N.: Elections can be manipulated often. In: FOCS ’08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 243–249 (2008)
Gibbard, A.: Manipulation of voting schemes: a general result. Econometrica 41, 587–601 (1973)
Goldreich, O.: Combinatorial property testing (a survey). In: Randomization Methods in Algorithm Design: DIMACS Workshop, 12–14 December 1997, p. 45 (1999)
Kalai, G.: A Fourier-theoretic perspective on the Condorcet paradox and Arrow’s theorem. Adv. Appl. Math. 29, 412–426 (2002)
Keller, N.: A tight quantitative version of Arrow’s impossibility theorem. J. Eur. Math. Soc. 14, 1331–1355 (2012)
Kemeny, J.G.: Mathematics without numbers. Daedalus 88, 577–591 (1959)
Kornhauser, L.A.: Modeling collegial courts. II. Legal doctrine. J. Law Econ. Organ. 8, 441–470 (1992)
Kornhauser, L.A., Sager, L.G.: Unpacking the court. Yale Law J. 96, 82–117 (1986)
Lang, J., Pigozzi, G., Slavkovik, M., van der Torre, L.: Judgment aggregation rules based on minimization. In: Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2009), pp. 238–246 (2011)
Lang, J., Xia, L.: Sequential composition of voting rules in multi-issue domains. Math. Soc. Sci. (Special Issue: Voting Theory and Preference Modeling) 57(3), 304–324 (2009)
List, C.: A model of path-dependence in decisions over multiple propositions. Am. Polit. Sci. Rev. 98, 495–513 (2004)
List, C.: The probability of inconsistencies in complex collective decisions. Soc. Choice Welf. 24, 3–32 (2005)
List, C.: Judgment aggregation: a short introduction. In: Gabbay, D.M., Thagard, P., Woods, J., Mäki, U. (eds.) Philosophy of Economics, 1st edn. Elsevier (2012)
List, C., Pettit, P.: Aggregating sets of judgments: an impossibility result. Econ. Philos. 18, 89–110 (2002)
List, C., Polak, B.: Introduction to judgment aggregation. J. Econ. Theory 145, 441–466 (2010)
List, C., Puppe, C.: Judgement aggregation: a survey. In: Pattanaik, P., Anand, P., Puppe, C. (eds.) The Handbook of Rational and Social Choice. Oxford University Press (2009)
Miller, A.D.: Group identification. Game. Econ. Behav. 63, 188–202 (2008)
Monderer, D., Samet, D.: Chapter 54: Variations on the Shapley value. In: Aumann, R., Hart, S. (eds.) Handbook of Game Theory with Economic Applications, vol. 3, pp. 2055–2076. Elsevier (2002)
Mongin, P.: Factoring out the impossibility of logical aggregation. J. Econ. Theory 141, 100–113 (2008)
Mossel, E.: A quantitative arrow theorem. Probab. Theory Relat. Fields 154, 49–88 (2012)
Nehama, I.: Approximate judgement aggregation. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) Internet and Network Economics. Lecture Notes in Computer Science, vol. 7090, pp. 302–313. Springer, Berlin/Heidelberg (2011)
Nehring, K.: Arrow’s theorem as a corollary. Econ. Lett. 80, 379–382 (2003)
Nehring, K., Puppe, C.: Consistent judgement aggregation: the truth-functional case. Soc. Choice Welf. 31, 41–57 (2008)
O’Donnell, R.: Some topics in analysis of Boolean functions. In: Proceedings of the 40th annual ACM Symposium on Theory of Computing (STOC ’08), pp. 569–578 (2008)
Pettit, P.: Deliberative democracy and the discursive dilemma. Philosophical Issues 11, 268–299 (2001)
Pigozzi, G.: Belief merging and the discursive dilemma: an argument-based account to paradoxes of judgment aggregation. Synthese 152, 285–298 (2006)
Ron, D.: Property testing (a tutorial). In: Rajasekaran, S., Pardalos, P.M., Reif, J.H., Rolim, J. (eds.) Handbook of Randomized Computing, vol. 2, chapter 15, pp. 597–649. Kluwer Academic Publishers (2001)
Rubinstein, A., Fishburn, P.C.: Algebraic aggregation theory. J. Econ. Theory 38, 63–77 (1986)
Rubinstein, A., Kasher, A.: On the question “who is a j?”: a social choice approach. Logique et Analyse 160, 385–395 (1997)
Satterthwaite, M.A.: Strategy-proofness and arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions. J. Econ. Theory 10, 187–217 (1975)
Winter, E.: Chapter 53: the shapley value. In: Aumann, R., Hart, S. (eds.) Handbook of Game Theory with Economic Applications, vol. 3, pp. 2025–2054. Elsevier (2002)