The more the worst-case-merrier: A generalized Condorcet Jury Theorem for belief fusion
J. Karge, and S. Rudolph. Proceedings of the Nineteenth International Conference on Principles of Knowledge Representation and Reasoning, California, International Joint Conferences on Artificial Intelligence Organization, (July 2022)
Abstract
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.
Proceedings of the Nineteenth International Conference on Principles of Knowledge Representation and Reasoning
year
2022
month
jul
publisher
International Joint Conferences on Artificial Intelligence Organization
conference
19th International Conference on Principles of Knowledge Representation and Reasoning \KR-2022\
location
Haifa, Israel
Tags
Cite this publication
More citation styles
- please select -
%0 Conference Paper
%1 Karge2022-qz
%A Karge, Jonas
%A Rudolph, Sebastian
%B Proceedings of the Nineteenth International Conference on Principles of Knowledge Representation and Reasoning
%C California
%D 2022
%I International Joint Conferences on Artificial Intelligence Organization
%K
%T The more the worst-case-merrier: A generalized Condorcet Jury Theorem for belief fusion
%X 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.
@inproceedings{Karge2022-qz,
abstract = {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.},
added-at = {2024-09-10T11:56:37.000+0200},
address = {California},
author = {Karge, Jonas and Rudolph, Sebastian},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/2fe518222ba46f733dd6862db9020b0fd/scadsfct},
booktitle = {Proceedings of the Nineteenth International Conference on Principles of Knowledge Representation and Reasoning},
conference = {19th International Conference on Principles of Knowledge Representation and Reasoning \{KR-2022\}},
interhash = {69a0562cb2826fca6e8adf0aea1344e2},
intrahash = {fe518222ba46f733dd6862db9020b0fd},
keywords = {},
location = {Haifa, Israel},
month = jul,
publisher = {International Joint Conferences on Artificial Intelligence Organization},
timestamp = {2024-09-10T15:15:57.000+0200},
title = {The more the worst-case-merrier: A generalized Condorcet Jury Theorem for belief fusion},
year = 2022
}