KR2022Proceedings of the 19th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning

Haifa, Israel. July 31–August 5, 2022.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-01-0

Sponsored by
Published by

Copyright © 2022 International Joint Conferences on Artificial Intelligence Organization

The More the Worst-Case-Merrier: A Generalized Condorcet Jury Theorem for Belief Fusion

  1. Jonas Karge(TU Dresden)
  2. Sebastian Rudolph(TU Dresden)


  1. Belief revision and update, belief merging, information fusion
  2. Uncertainty, vagueness, many-valued and fuzzy logics
  3. Probabilistic reasoning and learning


In multi-agent belief fusion, there is increasing interest in results and methods from social choice theory.

As a theoretical cornerstone, the Condorcet Jury Theorem (CJT) states that given a number of equally competent, independent agents where each is more likely to guess the true out of two alternatives, the chances of determining this objective truth by majority voting increase with the number of participating agents, approaching certainty. Past generalizations of the CJT have shown that some of its underlying assumptions can be weakened. Motivated by requirements from practical belief fusion scenarios, we provide a significant further generalization that subsumes several of the previous ones. Our considered setting simultaneously allows for heterogeneous competence levels across the agents (even tolerating entirely incompetent or even malicious voters), and voting for any number of alternatives from a finite set. We derive practical lower bounds for the numbers of agents needed to give probabilistic guarantees for determining the true state through approval voting. We also demonstrate that the non-asymptotic part of the CJT fails in our setting for arbitrarily high numbers of voters.