Some Complexity Results for Distance-Based Judgment Aggregation

1. Bartholdi, J., Tovey, C.A., Trick, M.A.: Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare 6, 157–165 (1989)

   Article  MathSciNet  MATH  Google Scholar 

2. Baumeister, D., Erdélyi, G., Erdélyi, O.J., Rothe, J.: Control in judgment aggregation. In: Proceedings of the 6th European Starting AI Researcher Symposium, pp. 23–34 (2012)

   Google Scholar 

3. Baumeister, D., Erdélyi, G., Erdélyi, O.J., Rothe, J.: Computational aspects of manipulation and control in judgment aggregation. In: Proceedings of the 3rd International Conference on Algorithmic Decision Theory, ADT 2013 (forthcomming, 2013)

   Google Scholar 

4. Baumeister, D., Erdélyi, G., Rothe, J.: How hard is it to bribe the judges? A study of the complexity of bribery in judgment aggregation. In: Brafman, R., Roberts, F.S., Tsoukiàs, A. (eds.) ADT 2011. LNCS, vol. 6992, pp. 1–15. Springer, Heidelberg (2011)

   Chapter  Google Scholar 

5. Bulling, N., Farwer, B.: On the (un-)decidability of model checking resource-bounded agents. In: Proceedings of ECAI. Frontiers in Artificial Intelligence and Applications, vol. 215, pp. 567–572. IOS Press (2010)

   Google Scholar 

6. Chevaleyre, Y., Endriss, U., Lang, J., Maudet, N.: A short introduction to computational social choice. In: van Leeuwen, J., Italiano, G.F., van der Hoek, W., Meinel, C., Sack, H., Plášil, F. (eds.) SOFSEM 2007. LNCS, vol. 4362, pp. 51–69. Springer, Heidelberg (2007)

   Chapter  Google Scholar 

7. Conitzer, V., Sandholm, T.: Complexity of manipulating elections with few candidates. In: Proceedings of AAAI 2002, pp. 314–319. American Association of Artificial Intelligence (2002)

   Google Scholar 

8. Conitzer, V., Sandholm, T.: Communication complexity of common voting rules. In: Proceedings of the ACM Conference on Electronic Commerce, pp. 78–87 (2005)

   Google Scholar 

9. Dempster, A.P.: Upper and lower probabilities induced by a multivalued mapping. The Annals of Mathematical Statistics 38(2) (1967)

   Google Scholar 

10. Deza, M.M., Deza, E.: Encyclopedia of Distances. Springer (2009)

    Google Scholar 

11. Dietrich, F.: A generalised model of judgment aggregation. Social Choice and Welfare 28(4), 529–565 (2007)

    Article  MathSciNet  MATH  Google Scholar 

12. Dietrich, F.: Judgment aggregation by quota rules majority voting generalized. Journal of Theoretical Politics 19(4), 391–424 (2007)

    Article  MathSciNet  Google Scholar 

13. Dietrich, F.: Scoring rules for judgment aggregation. Social Choice and Welfare (to appear, 2013)

    Google Scholar 

14. Dietrich, F., Mongin, P.: The premiss-based approach to judgment aggregation. Journal of Economic Theory 145(2), 562–582 (2010)

    Article  MathSciNet  MATH  Google Scholar 

15. Dima, C., Tiplea, F.L.: Model-checking atl under imperfect information and perfect recall semantics is undecidable. CoRR, abs/1102.4225 (2011)

    Google Scholar 

16. Dokow, E., Holzman, R.: Aggregation of binary evaluations with abstentions. Journal of Economic Theory 145(2), 544–561 (2010)

    Article  MathSciNet  MATH  Google Scholar 

17. Duddy, C., Piggins, A.: Many-valued judgment aggregation: Characterizing the possibility/impossibility boundary. Journal of Economic Theory 148(2), 793–805 (2013)

    Article  MathSciNet  MATH  Google Scholar 

18. Eckert, D., Klamler, C., Mitlöhner, J., Schlötterer, C.: A distance-based comparison of basic voting rules. Central European Journal of Operations Research 14(4), 377–386 (2006)

    Article  MathSciNet  MATH  Google Scholar 

19. Eckert, D., Mitlöhner, J.: Logical representation and merging of preference information. In: Proceedings of the IJCAI 2005 Multidisciplinary Workshop on Preference Handling (2005)

    Google Scholar 

20. Endriss, U., Grandi, U., Porello, D.: Complexity of judgment aggregation: Safety of the agenda. In: Proceedings of AAMAS 2010, pp. 359–366 (2010)

    Google Scholar 

21. Endriss, U., Grandi, U., Porello, D.: Complexity of winner determination and strategic manipulation in judgment aggregation. In: Proceedings of COMSOC 2010 (2010)

    Google Scholar 

22. Endriss, U., Grandi, U., Porello, D.: Complexity of judgment aggregation. Journal of Artificial Intelligence Research 45, 481–514 (2012)

    MathSciNet  MATH  Google Scholar 

23. Escoffier, B., Lang, J., Öztürk, M.: Single-peaked consistency and its complexity. In: Proceedings of ECAI 2008, pp. 366–370. IOS Press (2008)

    Google Scholar 

24. Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.Y.: Reasoning about Knowledge. MIT Press (1995)

    Google Scholar 

25. Grabisch, M., Marichal, J.-L., Mesiar, R., Pap, E.: Aggregation Functions. Cambridge University Press (2009)

    Google Scholar 

26. Grossi, D.: Correspondences in the theory of aggregation. In: Bonanno, G., Löwe, B., van der Hoek, W. (eds.) LOFT 2008. LNCS, vol. 6006, pp. 34–60. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

27. Hemaspaandra, E., Spakowski, H., Vogel, J.: The complexity of kemeny elections. Theoretical Computer Science 349(3), 382–391 (2005)

    Article  MathSciNet  MATH  Google Scholar 

28. Konieczny, S., Lang, J., Marquis, P.: Distance-based merging: A general framework and some complexity results. In: Proceedings of KR 2002, pp. 97–108 (2002)

    Google Scholar 

29. Lang, J., Pigozzi, G., Slavkovik, M., van der Torre, L.: Judgment aggregation rules based on minimization. In: Proceedings of TARK, pp. 238–246 (2011)

    Google Scholar 

30. Lang, J., Slavkovik, M.: Judgment aggregation rules and voting rules. In: Perny, P., Pirlot, M., Tsoukiás, A. (eds.) ADT 2013. LNCS, vol. 8176, pp. 230–243. Springer, Heidelberg (2013)

    Google Scholar 

31. Li, N.: Decision paths in sequential non-binary judgment aggregation. Technical report, Universitat Autònoma de Barcelona (2010)

    Google Scholar 

32. List, C., Pettit, P.: Aggregating sets of judgments: An impossibility result. Economics and Philosophy 18(01), 89–110 (2002)

    Google Scholar 

33. List, C., Polak, B.: Introduction to judgment aggregation. Journal of Economic Theory 145(2), 441–466 (2010)

    Article  MathSciNet  MATH  Google Scholar 

34. Miller, M.K., Osherson, D.: Methods for distance-based judgment aggregation. Social Choice and Welfare 32(4), 575–601 (2009)

    Article  MathSciNet  MATH  Google Scholar 

35. Nehring, K., Pivato, M.: Incoherent majorities: The McGarvey problem in judgement aggregation. Discrete Applied Mathematics 159(15), 1488–1507 (2011)

    Article  MathSciNet  MATH  Google Scholar 

36. Pauly, M., van Hees, M.: Logical constraints on judgement aggregation. Journal of Philosophical Logic 35(6), 569–585 (2006)

    Article  MathSciNet  MATH  Google Scholar 

37. Peterson, G., Reif, J., Azhar, S.: Lower bounds for multiplayer noncooperative games of incomplete information. Computers and Mathematics with Applications 41(7), 957–992

    Google Scholar 

38. Pigozzi, G.: Belief merging and the discursive dilemma: an argument-based account to paradoxes of judgment aggregation. Synthese 152(2), 285–298 (2006)

    Article  MathSciNet  MATH  Google Scholar 

39. Shafer, G.: A Mathematical Theory of Evidence. Princeton University Press (1976)

    Google Scholar 

40. Slavkovik, M., Jamroga, W.: Distance-based judgment aggregation of three-valued judgments with weights. In: Proceedings of the IJCAI Workshop on Social Choice and Artificial Intelligence

    Google Scholar 

41. van der Hoek, W., Verbrugge, R.: Epistemic logic: A survey. Game Theory and Applications 8, 53–94 (2002)

    Google Scholar 

42. Wilson, R.: On the theory of aggregation. Journal of Economic Theory 10(1), 89–99 (1975)

    Article  MathSciNet  MATH  Google Scholar 

Download references