Abstract:
When aggregating logically interconnected judgments from n agents, the result might be logically inconsistent. This phenomenon is known as the doctrinal paradox, which plays a central role in the field of judgment aggregation. Previous work has mostly focused on the worst-case analysis of the doctrinal paradox, which has lead to many impossibility results. Little is known about its practical occurrence, except for the study on its likelihood under a few i.i.d. distributions.
In this paper, we characterize the likelihood of the doctrinal paradox under a much more general and realistic model called smoothed social choice framework introduced in a NeurIPS 2020 paper. In the framework, agents' ground truth judgments can be arbitrarily correlated, while the noises are independent. Our main theorem states that under mild conditions, the smoothed likelihood of the doctrinal paradox is either $0$, $\exp(-\Theta(n))$, $\Theta(n^{-1/2})$ or $\Theta(1)$. This not only answers open questions by List in 2005, but also draws clear lines between situations with frequent and with vanishing paradoxes.
In this paper, we characterize the likelihood of the doctrinal paradox under a much more general and realistic model called smoothed social choice framework introduced in a NeurIPS 2020 paper. In the framework, agents' ground truth judgments can be arbitrarily correlated, while the noises are independent. Our main theorem states that under mild conditions, the smoothed likelihood of the doctrinal paradox is either $0$, $\exp(-\Theta(n))$, $\Theta(n^{-1/2})$ or $\Theta(1)$. This not only answers open questions by List in 2005, but also draws clear lines between situations with frequent and with vanishing paradoxes.
Introduction Video
Sessions where this paper appears
-
Poster Session 5
Sat, February 26 12:45 AM - 2:30 AM (+00:00)
Blue 6
-
Poster Session 8
Sun, February 27 12:45 AM - 2:30 AM (+00:00)
Blue 6