The Semi-random Likelihood of Doctrinal Paradoxes

No. 5: AAAI-22 Technical Tracks 5

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 36

AAAI Technical Track on Game Theory and Economic Paradigms

When aggregating logically interconnected judgements 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 judgement aggregation. Previous work has mostly focused on the worst-case analysis of the doctrinal paradox, leading to many impossibility results. Little is known about its likelihood of occurrence in practical settings, except for the study under certain distributions by List in 2005. In this paper, we characterize the likelihood of the doctrinal paradox under a general and realistic model called semi-random social choice framework (proposed by Xia in 2020). In the framework, agents' ground truth judgements can be arbitrarily correlated, while the noises are independent. Our main theorem states that under mild conditions, the semi-random likelihood of the doctrinal paradox is either 0, exp(-Θ(n)), Θ(n^~(-0.5)) or Θ(1). This not only answers open questions by List in 2005, but also draws clear lines between situations with frequent paradoxes and with vanishing paradoxes.

10.1609/aaai.v36i5.20446