Abstract
In this paper we analyze judgement aggregation problems in which a group of agents independently votes on a set of complex propositions that has some interdependency constraint between them (e.g., transitivity when describing preferences). We consider the issue of judgement aggregation from the perspective of approximation. That is, we generalize the previous results by studying approximate judgement aggregation. We relax the main two constraints assumed in the current literature, Consistency and Independence and consider mechanisms that only approximately satisfy these constraints, that is, satisfy them up to a small portion of the inputs. The main question we raise is whether the relaxation of these notions significantly alters the class of satisfying aggregation mechanisms. The recent works for preference aggregation of Kalai, Mossel, and Keller fit into this framework. The main result of this paper is that, as in the case of preference aggregation, in the case of a subclass of a natural class of aggregation problems termed ‘truth-functional agendas’, the set of satisfying aggregation mechanisms does not extend non-trivially when relaxing the constraints. Our proof techniques involve boolean Fourier transform and analysis of voter influences for voting protocols.
The question we raise for Approximate Aggregation can be stated in terms of Property Testing. For instance, as a corollary from our result we get a generalization of the classic result for property testing of linearity of boolean functions.
The research was supported by a grant from the Israeli Science Foundation (ISF) and by the Google Inter-university center for Electronic Markets and Auctions.
Previous versions of this work were presented at Bertinoro Workshop on Frontiers in Mechanism Design 2010, Third International Workshop on Computational Social Choice, Düsseldorf 2010, and Computation and Economics Seminar at the Hebrew University. The author would like to thank the participants in these workshops for their comments.
Due to space constraint the proofs of all theorems are omitted as well as some discussion on the implications of this work to other fields. The long version of this paper can be found on the author website[33].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bellare, M., Coppersmith, D., Hastad, J., Kiwi, M., Sudan, M.: Linearity testing in characteristic two. In: FOCS 1995: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p. 432. IEEE Computer Society Press, Washington, DC, USA (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. Journal of Computer and System Sciences 47(3), 549–595 (1993)
Bovens, L., Rabinowicz, W.: Democratic answers to complex questions an epistemic perspective. Synthese 150, 131–153 (2006)
Caragiannis, I., Kaklamanis, C., Karanikolas, N., Procaccia, A.D.: Socially desirable approximations for dodgson’s voting rule. In: Proc. 11th ACM Conference on Electronic Commerce (2010)
Dietrich, F., List, C.: Arrows theorem in judgment aggregation. Social Choice and Welfare 29(1), 19–33 (2007)
Dietrich, F.: Judgment aggregation (im)possibility theorems. Journal of Economic Theory 126(1), 286–298 (2006)
Dietrich, F., List, C.: Judgment aggregation by quota rules. Journal of Theoretical Politics 19(4), 391–424 (2007)
Dokow, E., Holzman, R.: Aggregation of binary evaluations for truth-functional agendas. Social Choice and Welfare 32(2), 221–241 (2009)
Dokow, E., Holzman, R.: Aggregation of binary evaluations. Journal of Economic Theory 145(2), 495–511 (2010)
Dokow, E., Holzman, R.: Aggregation of non-binary evaluations. Advances in Applied Mathematics 45(4), 487–504 (2010)
Elkind, E., Faliszewski, P., Slinko, A.: Distance rationalization of voting rules. In: The Third International Workshop on Computational Social Choice, COMSOC 2010 (2010)
Fishburn, P., Rubinstein, A.: Aggregation of equivalence relations. Journal of Classification 3(1), 61–65 (1986)
Friedgut, E., Kalai, G., Nisan, N.: Elections can be manipulated often. In: FOCS 2008: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 243–249. IEEE Computer Society Press, Washington, DC, USA (2008)
Kalai, G.: A fourier-theoretic perspective on the condorcet paradox and arrow’s theorem. Adv. Appl. Math. 29(3), 412–426 (2002)
Keller, N.: A tight quantitative version of Arrow’s impossibility theorem. Arxiv preprint arXiv:1003.3956 (2010)
Kemeny, J.G.: Mathematics without numbers. Daedalus 88(4), 577–591 (1959)
Kornhauser, L.A.: Modeling collegial courts. ii. legal doctrine. Journal of Law, Economics and Organization 8(3), 441–470 (1992)
Kornhauser, L.A., Sager, L.G.: Unpacking the court. The Yale Law Journal 96(1), 82–117 (1986)
List, C.: A model of path-dependence in decisions over multiple propositions. American Political Science Review 98(03), 495–513 (2004)
List, C.: The probability of inconsistencies in complex collective decisions. Social Choice and Welfare 24(1), 3–32 (2005)
List, C.: Judgment aggregation: a short introduction (August 2008), http://philsci-archive.pitt.edu/4319/
List, C., Pettit, P.: Aggregating sets of judgments: An impossibility result. Economics and Philosophy 18, 89–110 (2002)
List, C., Puppe, C.: Judgement aggregation: A survey. In: Anand, P., Puppe, P.P. (eds.) The Handbook of Rational and Social Choice. Oxford University Press, USA (2009)
Miller, A.D.: Group identification. Games and Economic Behavior 63(1), 188–202 (2008)
Mossel, E.: A quantitative arrow theorem. Probability Theory and Related Fields (forthcoming)
Nehring, K.: Arrows theorem as a corollary. Economics Letters 80(3), 379–382 (2003)
Nehring, K., Puppe, C.: Consistent judgement aggregation: The truth-functional case. Social Choice and Welfare 31(1), 41–57 (2008)
Pettit, P.: Deliberative democracy and the discursive dilemma. Philosophical Issues 11(1), 268–299 (2001)
Pigozzi, G.: Belief merging and the discursive dilemma: An argument-based account to paradoxes of judgment aggregation. Synthese 152(2), 285–298 (2006)
Rubinstein, A., Kasher, A.: On the question ”Who is a J?”: A social choice approach. Princeton Economic Theory Papers 00s5, Economics Department. Princeton University (1998)
Rubinstein, A., Fishburn, P.C.: Algebraic aggregation theory. Journal of Economic Theory 38(1), 63–77 (1986)
Nehama, I.: Approximate judgement aggregation. Discussion Paper Series - DP574R, Center for Rationality and Interactive Decision Theory, Hebrew University, Jerusalem (October 2011), http://ideas.repec.org/p/huj/dispap/dp574.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nehama, I. (2011). Approximate Judgement Aggregation. In: Chen, N., Elkind, E., Koutsoupias, E. (eds) Internet and Network Economics. WINE 2011. Lecture Notes in Computer Science, vol 7090. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25510-6_26
Download citation
DOI: https://doi.org/10.1007/978-3-642-25510-6_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25509-0
Online ISBN: 978-3-642-25510-6
eBook Packages: Computer ScienceComputer Science (R0)