- Complexity of winner determination and strategic manipulation in judgment aggregation
- 3rd International Workshop on Computational Social Choice (COMSOC-2010), Düsseldorf, Germany
- Book/source title
- Proceedings of the 3rd International Workshop on Computational Social Choice (COMSOC-2010)
- Pages (from-to)
- Institut für Informatik, Heinrich-Heine-Universität Düsseldorf
- Document type
- Conference contribution
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
Judgment aggregation is an area of social choice theory that analyses procedures for aggregating the judgments of a group of agents regarding a set of interdependent propositions (modelled as formulas in propositional logic). The judgment aggregation framework gives rise to a number of algorithmic problems, including (1) computing a collective judgment from a profile of individual judgments (the winner determination problem), and (2) deciding whether a given agent can influence the outcome of a judgment aggregation procedure in her favour by reporting insincere judgments (the manipulation problem). We study the computational complexity of both these problems for two concrete judgment aggregation procedures that are complete and consistent and that have been argued to be useful in practice: the premise-based procedure and (a new variant of) distance-based merging. Our results suggest that manipulating these procedures is significantly harder than solving the corresponding winner determination problem.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.