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

Jonas KargeJonas Karge, Sebastian RudolphSebastian Rudolph

Jonas Karge, Sebastian Rudolph
The More the Worst-Case-Merrier: A Generalized Condorcet Jury Theorem for Belief Fusion
In Gabriele Kern-Isberner, Gerhard Lakemeyer, Thomas Meyer, eds., Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning, 205-–214, 2022

Details
Bibtex

KurzfassungAbstract
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.
Projekt:Project: ScaDS.AI
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{KR2022,
  author    = {Jonas Karge and Sebastian Rudolph},
  title     = {The More the Worst-Case-Merrier: A Generalized Condorcet Jury
               Theorem for Belief Fusion},
  editor    = {Gabriele Kern-Isberner and Gerhard Lakemeyer and Thomas Meyer},
  booktitle = {Proceedings of the 19th International Conference on Principles of
               Knowledge Representation and Reasoning},
  year      = {2022},
  pages     = {205-{\textendash}214}
}