# the_semirandom_likelihood_of_doctrinal_paradoxes__8a6fe890.pdf

The Semi-random Likelihood of Doctrinal Paradoxes

Ao Liu and Lirong Xia

Department of Computer Science, Rensselaer Polytechnic Institute 110 8th St, Troy, NY 12180, USA liua6@rpi.edu, xial@cs.rpi.edu

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.

Introduction The field of judgement aggregation studies the aggregation of agents judgements (yes/no votes) on multiple logically interconnected propositions in a consistent way. For example, suppose a defendant is involved in a traffic accident where a victim is injured. A jury of n agents (jurors) are asked to make collective decisions on the following three propositions:

Proposition ω1: The injury is caused by the defendant. Proposition ω2: The injury is serious enough. Proposition ω3: The defendant is guilty.

Each agent is asked to provide a yes/no judgement to each proposition in a logically consistent way, i.e., her answer to ω3 is Y if and only if her answers to both ω1 and ω2 are Y, or equivalently, ω3 ω1 ω2 must hold. Then, agents judgements, called a profile, are aggregated by a rule r. One classical rule for judgement aggregation is proposition-wise majority, which performs majority voting on each proposition separately. Unfortunately, the output of proposition-wise majority can be logically

Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

inconsistent. This phenomenon is known as the doctrinal paradox, as shown in the following example. Example 1 (Doctrinal paradox). Suppose there are three three agents (n = 3), whose judgements on ω1, ω2, and ω3 are shown in Table 1. Notice that while every agent s judgements are consistent with the logic relationship ω3 ω1 ω2, the output of proposition-wise majority is inconsistent with the logic.

Propositions ω1 ω2 ω3 ω3 ? ω1 ω2 Agent 1 Y N N True Agent 2 N Y N True Agent 3 Y Y Y True Aggregation Y Y N False

Table 1: Doctrinal paradox. In general, the doctrinal paradox can happen for p 1 premises (logically independent propositions), plus one conclusion, whose value is determined by the values of the premises. The doctrinal paradox originated the whole field of judgement aggregation (Grossi and Pigozzi 2014), and continued to play a central role since then (List 2012; Grossi and Pigozzi 2014; Brandt et al. 2016). A large body of literature has shown the negative effects of the doctrinal paradox in law (Kornhauser and Sager 1986; Hanna 2009; Chilton and Tingley 2012), economics (Mongin 2019), computational social choice (Bonnefon 2010; Brandt et al. 2016), philosophy (Sorensen 2003; Mongin 2012) and psychology (Bonnefon 2011), etc. Unfortunately, the paradox is unavoidable under mild assumptions (List and Pettit 2002), and there is a large body of literature on impossibility theorems as well as ways for escaping from them (List and Polak 2010; Grossi and Pigozzi 2014; Endriss 2016). Despite the mathematical impossibilities, it is unclear how frequently doctrinal paradoxes happens in reality. Empirical studies have been limited by the lack of datasets, as many classical applications of judgement aggregations are in high-stakes, low frequent, privacy-sensitive domains, such as judicial systems. To embrace AI-powered e-democracy, we believe that it is now the right time to theoretically study the likelihood of the paradox under realistic models. A low likelihood is desirable, because it suggests that, despite the fact that the paradox exists in the worst case, it is likelihood not be a big concern in practice.

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

While this approach is highly popular in voting (Nurmi 1999; Gehrlein and Lepelley 2011; Diss and Merlin 2021), it has not received due attention in judgement aggregation. The only known exception is the paper by List (2005), who provided sufficient conditions for the likelihood of doctrinal paradox to converge to 1 and to 0, respectively, under some distributions for two or three premises. Therefore, the following research question remains largely open:

How likely does the doctrinal paradox occur under realistic models?

Successfully addressing this question faces two challenges. The first challenge is modeling, i.e., it is unclear what probabilistic models are realistic. A large body of literature in social choice focused on the i.i.d. uniform distribution, known as Impartial Culture (IC), which has been widely criticized of being unrealistic (Nehama 2011, 2013; Nurmi 1999; Brandl, Brandt, and Seedig 2016; Van Deemen 2014; Lehtinen and Kuorikoski 2007). The second challenge is the technical hardness in mathematically analyzing the likelihood. In fact, even characterizing the likelihood of doctrinal paradox under i.i.d. distributions is already highly challenging, and List s 2005 work (List 2005) left many i.i.d. distributions as open questions, including IC. Our Model. We adopt the semi-random social choice framework (Xia 2020, 2021b; Xia and Zheng 2021) to address the modeling challenge. The framework was inspired by the celebrated semi-random complexity analysis (Spielman and Teng 2009; Blum and Spencer 1995), and is more realistic and general than i.i.d. distributions, especially IC. We consider the setting with p 1 premises and one conclusion determined by the logical connection function f, where every agent s vote is a random variable whose distribution is in a set Π over all 2p judgements on premises (See the Preliminaries Section for the formal definitions of distributions over votes). Then, given the aggregation rule r, a max-adversary aims at maxing the likelihood of doctrinal paradox by setting agents distributions from Π. This leads to the definition of the max-semi-random likelihood of doctrinal paradox as follows. f DP max Π,r,f(n) sup π Πn Pr P π (P is a doctrinal paradox) ,

where π = (π1, , πn) Πn is the collection of the distributions of n agents chosen by the adversary, and profile P is the collection of n agents votes generated from π. Similarly, the min-semi-random likelihood of doctrinal paradox is defined as follows.

f DP min Π,r,f(n) inf π Πn Pr P π (P is a doctrinal paradox) .

Notice that in both definitions, agents ground truth preferences, represented by π, are arbitrarily correlated (the noises are still independent). The max-(respectively, min-) semi-random likelihood corresponds to the worst-case (best-case) analysis. A low max-semi-random likelihood is positive news, because it states that the paradox is unlikely to happen regardless of the adversary s choice. A high min-semi-random likelihood is strongly negative news, because it states that the paradox is likely to happen with

non-negligible probability, regardless of agents ground truth preferences.

Our Contributions. In this paper, we prove the following general characterization of the semi-random likelihood of doctrinal paradox. Theorem 1. (Semi-random Likelihood of Doctrinal Paradox, Informal.) Under mild assumptions, for any n N, any quota rule r, and any logical connection f, f DP max Π,r,f(n) is either 0, exp( Θ(n)), Θ(n 1/2) or Θ(1),

and f DP min Π,r,f(n) is either 0, exp( Θ(n)), Θ(n 1/2) or Θ(1). The formal statement of the theorem also characterizes the condition for each case to happen. As commented above, the first three cases (0, exp( Θ(n)), and Θ(n 1/2)) of f DP max Π,r,f(n) are positive news, because they state that the doctrinal paradox vanishes as n , see e.g., Example 7.

The last case (Θ(1)) of f DP min Π,r,f(n) is negative news. Notably, a direct corollary of Theorem 1 (Corollary 2) characterizes the likelihood of doctrinal paradox under i.i.d. distributions that are not covered by List (2005), in particular the uniform distribution which naturally corresponds to IC in social choice. Experiments on synthetic data in the next Section confirm our theoretical results.

Proof techniques. The proof of Theorem 1 addresses technical hardness in (List 2005) by first converting the semi-random doctrinal paradox to a union of polyhedra, and then applying (Xia 2021a, Theorem 2). Such applications can be highly non-trivial as commented in (Xia 2021a), which we believe to be the case of this paper and are our main technical contribution.

Related Work and Discussions. Our work extends the results by List (2005) on i.i.d. distributions in three dimensions. First, we characterize the semi-random likelihood of doctrinal paradox, which is more general and realistic than i.i.d. distributions. Second, our theorem works for arbitrary number of premises and arbitrary logic connection function, while List (2005) s results only work for two or three premises and conjunctive and disjunctive functions. Third, our theorem works for arbitrary quota rules, which extends the proposition-wise majority rule in (List 2005). As discussed above, as our theorem is a full characterization, a straightforward corollary of our theorem addresses the likelihood of doctrinal paradox under all i.i.d. cases that are left open in (List 2005). The modern formulation of doctrinal paradox was due to Kornhauser and Sager (1986), though a similar paradox was described by Poisson in 1937 (Poisson 1837) and by Vacca in 1921 (Vacca 1921), see (Grossi and Pigozzi 2014). The paradox is closely related to the more general discursive dilemma (Pettit 2001), where agents also vote on the logic relationship as in the last column in Table 1. Doctrinal paradox is also a special case of responsibility voids, where no individual in the committee can morally be responsible voting outcome (Braham and Van Hees 2011).

List and Pettit (2002) proved the first impossible theorem about doctrinal paradox, which has lead to many followup impossibility theorems (Pauly and Hees 2006; Mongin 2008; Dietrich and List 2008; Awad et al. 2017; Mongin 2019; Baharad, Neeman, and Rubinchik 2020; Marcoci and Nguyen 2020). Methods to escape from the paradox have been explored (Nehring and Pivato 2021; Rahwan and Tohm e 2010; Nehring and Puppe 2008; Lyon and Pacuit 2013). The connection between judgement aggregation and belief merging was established (Everaere, Konieczny, and Marquis 2017). Computational and machine learning aspects of judgement aggregation have also been explored, see, e.g., (Endriss, Grandi, and Porello 2012; Zhang and Conitzer 2019; Endriss et al. 2019; Baumeister et al. 2020).

Preliminaries Basics of Judgement Aggregation. Let [n] {1, , n} denote the set of n agents. Let p denote the number of premises. The binary judgement of agent j on the i-th premise is denoted by ωj,i {0, 1}, where ωj,i = 1 means Yes and ωj,i = 0 means No . The conclusion is often denoted by ϕ, and sometimes by ωp+1 for simplicity. Because all premises are binary, there are m = 2p different combinations of judgements on the premises. To better present the results, instead of asking the agents to submit their judgements ωj = (ωj,1, , ωj,p), equivalently, we ask each agent to submit an m-dimensional vector vj, called her vote, whose ωj-th component is 1 and all other components are 0 s. Let V { v {0, 1}m : m = 2p and || v||1 = 1} denote the set of all votes. For example, in the setting of Example 1, we have p = 2, m = 4, and the four judgements are ((0, 0), (0, 1), (1, 0), (1, 1)). Agent 1 s judgements are (1, 0), which means that her vote is (0, 0, 1, 0), where the third component corresponds to the weight on judgements (1, 0). A probability distribution over the 2p judgements is also called a fractional vote. Let Vfrc { v [0, 1]m : || v||1 = 1} denote the set of all fractional votes. Clearly, V Vfrc. For any fractional vote v and any judgement ω, we let v( ω) denote the weight (probability) on ω. For example, agent 2 s vote in Table 2 below is a fractional vote with 0.5 weight on each of (1, 0) and (1, 1). Let f : {0, 1}p {0, 1} denote the logical connection between the premises and the conclusion. That is, for any judgements ω {0, 1}p, f( ω) is the conclusion that is consistent with the logic. The domain of f can be naturally extended to (non-fractional) votes V. That is,

j [n], ϕj = f( vj) = f( ω), where vj( ω) = 1.

For example, in the setting of Example 1, the conclusion is 1 if and only if both premises are 1. Therefore,

f( v) = 1 if v = (0, 0, 0, 1) 0 otherwise For any 1 i p + 1, let Ωi denote the set of all judgements whose i-th proposition is 1. That is,

Ωi ω {0, 1}p : ω(i) = 1 i [p] ω {0, 1}p : f( ω) = 1 if i = p + 1 .

For example, in the setting of Example 1, Ω1 = {(1, 0), (1, 1)}, Ω2 = {(0, 1), (1, 1)}, and Ω3 = {(1, 1)}. For any n N, let P = ( v1, , vn) (Vfrc)n denote a (fractional) profile of n agents. A (judgement) aggregation rule is a function r : (Vfrc)n {0, 1}p+1, which takes a profile as input and outputs binary values for all premises and the conclusion. For any (fractional) profile P (Vfrc)n, we define Hist(P) P j [n] vj to be the histogram of P, which represents the total weight of each combination of judgements in P. We define fractional votes and fractional profiles to present conditions in the theorem. Notice that agents votes are in V, which means that they are nonfractional.

Quota Rules. A quota rule is a natural and wellstudied generalization of proposition-wise majority rule with different thresholds. Formally, given any vector of acceptance thresholds (threshold in short), denoted by q = (q1, , qp+1) [0, 1]p+1 and any vector of tiebreaking criteria (breaking in short), denoted by d = (d1, , dp+1) {0, 1}p+1, we define the quota rule r q, d(P) as follows. For any profile P (Vfrc)n and any i [p + 1], we let ni = P ω Ωi Hist(P)( ω) denote the total weight of agents whose i-th judgement is 1, then apply the quota rule with threshold qi and breaking di. That is,

i [p + 1], r q, d(P)(i)

( 1 if ni > qi n di if ni = qi n 0 otherwise , (1)

where r q, d(P)(i) is the i-th component of r q, d(P). We say that a profile P is tied in ωi if ni = qi n. Doctrinal Paradox. A profile P is said to be a doctrinal paradox under r, if r(P) is inconsistent with f. Formally, we have the following definition. Definition 1 (Doctrinal paradox). Given any n N, any logical connection function f, and any quota rule r, a profile P Vn frc is a doctrinal paradox, if r(P)(p + 1) = f r(P)(1), , r(P)(p) . The following example illustrates a fractional profile, a quota rule, and the aggregated judgements. Example 2. A (fractional) profile P of three votes, a quota rule r (which uses the majority rule with the breaking in favor of 1 on both premises and in favor of 0 on the conclusion), and the aggregation is shown in Table 2.

weight ω1 ω2 ϕ v Agent 1 1 1 0 0 (0, 0, 1, 0) Agent 2 1 0 1 0 (0, 1, 0, 0)

Agent 3 0.5 1 0 0 (0, 0, 0.5, 0.5) 0.5 1 1 1 Hist(P) (0, 1, 1.5, 0.5) ni 2 1.5 0.5 Breaking d 1 1 0 Threshold q 0.5 0.5 0.5 q n 1.5 1.5 1.5 r q, d(P) 1 1 0

Table 2: The profile, rule, and aggregation result for Example 2.

It can be seen from the table that r(P) = (1, 1, 0), which is inconsistent w.r.t. f. Therefore, P is a doctrinal paradox.

Characterization of Semi-random Likelihood of Doctrinal Paradox Intuition. Before formally present the theorem, we first take a high-level and intuitive approach to introduce the idea behind the characterization and highlight the challenges. Take the max part f DP max Π,r,f(n) for example. Suppose the (max-)adversary has chosen π = (π1, . . . , πn) Πn. Let π = Pn j=1 πj/n denote the center of π. Intuitively, various multivariate central limit theorems imply that the histogram of the profile P generated from π falls in an Θ(n 0.5) neighborhood of n π, denoted by Nn π, with high probability. As an approximation and relation, for now we allow the max-adversary to choose any π in the convex hull of Π (denoted by CH(Π)). Then, we can focus on the likelihood of doctrinal paradox in Nn π, which leads to the following four cases.

Case 1. If no profile of n votes is a doctrinal paradox, then f DP max Π,r,f(n) = 0 by definition. Case 2. Otherwise, if for all π CH(Π), Nn π does not contain a doctrinal paradox, then f DP max Π,r,f(n) is small. Notice

that f DP max Π,r,f(n) is not zero, because there is a small (exponential) probability that Hist(P) is not in Nn π. Case 3. Otherwise, if the adversary can only choose π CH(Π) that corresponds to a non-robust instance of doctrinal paradox, in the sense that Nn π includes some but not too many doctrinal paradoxes. Then, f DP max Π,r,f(n) should be larger than that in the previous case. This is the most challenging case, because it is unclear how to characterize conditions for it to happen, and how large the likelihood is. While standard techniques may lead to an O(n 0.5) upper bound, it is unclear if f DP max Π,r,f(n) can be lower. Case 4. Otherwise, the adversary can choose π CH(Π) that corresponds to a robust instance of doctrinal paradox, such that Nn π contains many paradoxes. In this case, f DP max Π,r,f(n) is large.

Case 1 is trivial. It turns out that Case 2 and Case 3 can be characterized by properties of distributions in the convex hull of Π. We first define effective refinements of distributions to reason about aggregated judgements in Nn π. Definition 2 ((Effective) Refinements). For any distribution π over V, any n N, and any quota rule r, we say that a vector α = (α1, , αp+1) {0, 1}p+1 is an effective refinement of π (at n), if the following two conditions hold:

(1) i [p + 1] such that π is not tied in ωi, αi = r(π)(i) (2) P Vn such that r(P) = α.

If condition (1) holds, then we call α a refinement of π. Let Eπ denote the set of all effective refinements of π. In words, condition (1) requires α to match the aggregated judgements on all non-tied propositions. Condition (2) re-

quires the existence of a profile of n votes, whose outcome under r is α. Example 3. In the setting of Example 2, π = (0.3, 0.2, 0, 0.5) is tied in the first premise (ω1) and the conclusion. There are four refinements of π: (0, 1, 0), (0, 1, 1) (1, 1, 0) and (1, 1, 1). (0, 1, 1) is not effective, because no profile can make conclusion ϕ = 1 while keeping ω1 to be 0. The other three refinements are effective when n 3. For example, (1, 1, 1) is effective because it is the aggregation of the profile where all agents have 1 judgements on both premises. Recall that CH(Π) denotes the convex hull of Π. Next, we define four conditions (κ1 to κ4) to present Theorem 1. While their formal definitions may appear technical, we believe that they have intuitive explanations as discussed right afterward. In fact, κ1, κ2, and κ4 correspond to case 1,2,3 discussed in the beginning of this section, respectively. κ3 is defined for min-semi-random likelihood. Definition 3 (Conditions κ1 to κ4). Given p premises, a logical connection function f, n N, and a quota rule r q, d, we define the following conditions. κ1: P Vn, P is not a doctrinal paradox. κ2: π CH(Π), α Eπ, α is consistent (under f). κ3: π CH(Π) such that α Eπ, α is consistent (under f). κ4: i [m] such that ωp+1 ωi and qp+1 = qi or ωp+1 ωi and qp+1 = 1 qi . Intuitively, κ1 requires that no profile of n votes is a doctrinal paradox. κ2 requires that the output of r q, d of every distribution π in CH(Π) is far away from any inconsistent judgements, in the sense that all judgements in Eπ are consistent. κ3 is weaker than κ2, because κ3 only requires that the condition in κ2 holds for some π CH(Π). κ4 says that the conclusion only relies on one premise and the thresholds are consistent with the relationship between the conclusion and the premise. Example 4 (Conditions κ1-κ4). Let f and r be the same as in Example 2. Let Π = {π1 = (0.25, 0.25, 0.25, 0.25), π2 = (0.04, 0.32, 0.32, 0.32)}. When n = 1, the paradox does not hold by definition. In the rest of this example, we assume n 2. κ1 is false. When n = 2, P = (1, 0, 0, 1) is the only doctrinal paradox. When n 3, P = (n + 1 2 n/3 n/3 , n/3 , n/3 , n/3 1) is a doctrinal paradox. κ2 is false. CH(Π) = {π = a π1+(1 a) π2 : a [0, 1]}. When a = 0, π is a doctrinal paradox and contains no ties. When a = 0, we have π = π1, and it is tied in conclusion and both premises. Its effective refinement α = (1, 1, 0) is a doctrinal paradox. κ3 is false. π2 is a doctrinal paradox and contains no ties. κ4 is false according to the definitions of f and r. We say that a distribution π is strictly positive, if there exists ϵ > 0 such that for every ω {0, 1}p, π( ω) ϵ. A set of distributions Π is strictly positive, if there exists ϵ > 0 such that every π Π is strictly positive (by ϵ). Being strictly positive is a mild requirement for voting systems (c.f. the argument for voting (Xia 2020)). We also note that specifying

the likelihood of doctrinal paradox is already highly challenging under IC, which is a much stronger assumption than strictly positive. Π is closed if it is a closed set in Rm. We now present the main theorem of this paper.

Theorem 1 (Semi-random Likelihood of Doctrinal Paradox). Given any closed and strictly positive set Π of distributions over V, any logical connection function f : V {0, 1}, and any quota rule r. For any n N,

f DP max Π,r,f(n) =

0 if κ1 is true exp( Θ(n)) otherwise, if κ2 is true Θ(n 1/2) otherwise, if κ4 is true Θ(1) otherwise

f DP min Π,r,f(n) =

0 if κ1 is true exp( Θ(n)) otherwise, if κ3 is true Θ(n 1/2) otherwise, if κ4 is true Θ(1) otherwise

Notice that both max and min semi-random likelihood of doctrinal paradox have four cases: the 0 case, the exponential case, the polynomial case, and the constant case. The first three cases are good news, particularly in the max part, which states that the doctrinal paradox vanishes when the number of agents is large. The last case is bad news, in particular for the min part, which states that the doctrinal paradox does not vanish. We believe that Theorem 1 is quite general as exemplified in the next subsection, because it works for any p 1, any logical connection function, any quote rule, and only makes mild assumptions on Π. We believe that asymptotic studies as done in Theorem 1 is important, because first, n is large in some classical applications such as combinatorial voting (Lang and Xia 2016). Second, even though n is typically small in some classical applications such as jury systems, we believe that modern technology will revolutionize such applications in the near future and promote them to the larger scale and broader applications. In this case, Theorem 1 allows us to analyze the practical relevance of the paradox, and provides a mathematical basis for choosing the best (quote) rule to minimize the likelihood of the paradox.

Applications of Theorem 1 In this subsection, we present a few examples of applications of Theorem 1. The first example illustrates the Θ(1) case.

Example 5 (Θ(1) case). Recall that in the setting of Example 4, we have: (κ1, κ2, κ3, κ4) = (true, false, false, false) if n = 1 (false, false, false, false) if n 2 According to Theorem 1, the max and min semi-random likelihood of doctrinal paradox are Θ(1), as shown in Table 3. A numerical verification can be found in Figure 2(a) in the next section.

The second example illustrates the exponential case, which is positive news.

Example 6 (Exponentially small case). Let us consider the same quota rule and the same logical connection as in Example 2 and 4. Let Π = {π1 =

n = 1 n 2 (Ex. 5) n 2 (Ex. 6) f DP max Π,r q, d,f(n) 0 Θ(1) exp( Θ(n))

f DP min Π,r q, d,f(n) 0 Θ(1) exp( Θ(n))

Table 3: Semi-random likelihood of DP in Example 5 and 6.

(0.12, 0.12, 0.12, 0.64), π2 = (0.1, 0.1, 0.1, 0.7)}. Following a similar reasoning as in Example 4, we have:

(κ1, κ2, κ3, κ4) = (true, false, false, false) if n = 1 (false, true, true, false) if n 2 According to Theorem 1, the max and min semi-random likelihood of doctrinal paradox are exp( Θ(n)), as shown in Table 3. See Figure 2(b) for a numerical verification.

The following example is also positive news because the doctrinal paradox vanishes as n , though not as fast as in Example 6 w.r.t. the max-adversary. Notice that the max and min semi-random likelihood of doctrinal paradox are asymptotically different.

Example 7 (Θ(n 1/2), exp( Θ(n)) and 0 cases). Let the logical connection be ϕ ω1, Π = {π1 = (0.9, 0.1), π2 = (0.3, 0.7)}1 and quota rule r q, d where q1 = q3 = 0.5, d1 = 1, and d3 = 0. We have: (κ1, κ2, κ3, κ4) = (true, false, false, true) if n is odd (false, false, true, true) if n is even .

According to Theorem 1, the max and min semi-random likelihood are presented in Table 4. Also see Figure 2(c) the next Section for a numerical verification.

Semi-random likelihood n is odd n is even f DP max Π,r q, d,f(n) 0 Θ(n 1/2) DPmin Π,r q, d,f(n) 0 exp( Θ(n))

Table 4: Semi-random likelihood of DP in Example 7.

The following corollary of Theorem 1 with Π = {π} address the open questions in (List 2005) about the probabilities of doctrinal paradox under all i.i.d. distributions, all q, all quota rules, and all logical connection funcations.

Corollary 2 (Likelihood of doctrinal paradox under i.i.d. distributions as in (List 2005)). Given any strictly positive distribution π over V, any logical connection function f : V {0, 1}, and any quota rule r. For any n N,

Pr P (π)n (P is a doctrinal paradox) =

0 if κ1 is true exp( Θ(n)) otherwise, if all α Eπ are consistent, Θ(n 1/2) otherwise, if κ4 is true Θ(1) otherwise

1Because the doctrinal paradox only depends on the votes to premise ωj (or conclusion ϕ), we use the marginal distribution on ωi to simplify notations. Here, π = (pr, 1 pr) mean ωi = 0 with probability pr while ωi = 1 with probability 1 pr.

In particular, when π is the uniform distribution over V and the aggregation rule is the majority, the likelihood of doctrinal paradox is either Θ(1) or 0 depending on the logical connection function f.

Proof Sketch of Theorem 1

The proof proceeds in three steps. In Step 1, we model doctrinal paradox as unions of polyhedra. In Step 2, we apply (Xia 2021a, Theorem 2) to obtain a characterization. In Step 3, we close the gap between Step 2 and Theorem 1 by translating conditions and degree of polynomial in Step 2 to their counterparts in Theorem 1. Step 1: Polyhedra Presentation. We show that the region of doctrinal paradox can be presented by a set of polyhedra, each of which is in the m-dimensional Euclidean space with the form H = n x : A x b o . For any i [p + 1], we first define vector ci {qi 1, qi}m as follows:

ci( ω) qi 1 if ω Ωi qi otherwise . (2)

For any profile P, it is not hard to verify that the sign of ci Hist(P) is closely related to the aggregation result by the quota rule. We define sign function sign( ) and 1( ) as follows,

sign(x) 1 if x > 0 1 otherwise and

1(κ) 1 if κ is true 0 otherwise .

Then, we define A α

sign(α1) c T 1 ... sign(αp+1) c T p+1

sign(α1) d1 1(α1 = 1) ... sign(αp+1) dp+1 1(αp+1 = 1)

. Let H α = { x :

A α x b α} denote the polyhedra and let H α, 0 = { x : A α x 0} denote its characteristic cone. Let C = {H α : α {0, 1}p+1 is inconsistent} denote the set of all polyhedra corresponding to doctrinal paradox. The following example visualizes a polyhedron and its characteristic cone for doctrinal paradox.

Example 8 (Polyhedra representation of doctrinal paradox). We consider a system with one premise ω1. The logical connection between conclusion ϕ and premise ω1 is ϕ ω1. The parameters for quota rule are (q1, q2) = (0.25, 0.65) and (d1, d2) = (1, 1). According to Equation (2), we have c1 = (q1, q1 1)T and c2 = (q2, q2 1)T. Then, the aggregation results of α = (1, 0) and α = (0, 1) are both inconsistent. Thus, C = H(1,0), H(0,1) . H(1,0) is represented by A(1,0) and b(1,0) defined as follows.

A(1,0) = q1 q1 1 q2 1 q2

and b(1,0) = 0 1

𝜶= (𝟎, 𝟎) not a doctrinal paradox

Figure 1: H(1,0) in Example 8. The characteristic cone H(1,0), 0 is the combination of H(1,0) and the region between n1 = q2 n 1 and n1 = q2 n.

It is not hard to verify that for any profile P of n agents, A(1,0) Hist(P) b(1,0) if and only if

n1 q1 n and n1 q2 n 1,

where n1 represents the number of votes for ω1 = 1 in P. Figure 1 illustrates the regions corresponding to H(1,0) and its characteristic cone.

Consequently, the semi-random likelihood of doctrinal paradox is equivalent to the semi-random probability for the histogram of the randomly generated profile (which is a Poisson multivariate variable (PMV)) to be in C. Therefore, in Step 2 we apply (Xia 2021a, Theorem 2) to obtain a characterization for the PMV-in-C problem. However, the results are too technical and generic to be informative in judgement aggregation context (see Lemma 5 in Appendix B). Step 3 aims at obtaining the characterization as stated in Theorem 1 based on Lemma 5, which involves non-trivial calculations and simplifications. The full proof can be found in Appendix B.

Computational Verification of Conditions in Theorem 1 In practice, κ1-κ4 may not be easy to verify by hand. In this subsection, we briefly discuss algorithms for checking κ1-κ4 under any quota rule r q, d with rational threshold q w.r.t. any Π with finitely many vertices on its convex hull and the probabilities of all vertices are rational numbers. The runtime of these algorithms is polynomial in m (as well as log n for κ1). While m = 2p may seem exponentially large, notice that the input size (e.g., Π and the truth-table representation of f) can also be large, i.e., Θ(m). Suppose Π = {π1, . . . , πℓ} Qm.2 κ1-κ4 can be verified as follow, by combining the results of multiple (I)LP

2Throughout this section, we slightly abuse the notations and use Π to represent the set of all vertices in CH(Π).

2 6 10 14 n

Probability

(c) The setting of Example 7

(n-1/2) DPmax

exp(- (n)) DPmin

16 32 48 64 80 n

Probability (in log-scale)

(b) The setting of Example 6

exp(- (n)) DPmax

exp(- (n)) DPmin

0 25 50 75 100 n

Probability

(a) The setting of Example 5

Figure 2: A numerical verification of Theorem 1. Note that the plot for Example 6 is in log-scale.

whose variables are y = (y1, . . . , yℓ) that represent the multiplicity of πℓ. κ1 holds for any given n if and only if there exists an inconsistent α {0, 1}p+1 such that the following ILP is feasible.

A α ((π1)T, . . . , (πℓ)T) 1 1

where y are integers. Following Lenstra s theorem (Lenstra 1983), when ℓis viewed as a constant (and q and n are variables), the runtime of each ILP is polynomial in q and log n. Therefore, the overall complexity of checking κ1 is polynomial in m (= 2p) and log n. Let An {0, 1}p+1 denote the set of all inconsistent α such that (3) has a feasible (nonnegative integer) solution, which will be used later. κ2 and κ3 can be verified by similar algorithms. Notice that Eπ only depends on whether each component of r(π) is positive, 0, or negative. Therefore, we can naturally define E β for every β {+, 0, }p+1. Let Bn denote the set of

all β, for each of which there exists α An that refines it. Then, for every β Bn, we define LP β, whose variables

are y 0 that do not need to be integers, to verify whether there exists π CH(Π) such that r q, d(π) = β. More precisely, for every j p + 1,

1 if βj = +, then LP β contains a linear constraint c T j

(Pℓ j=1 yj( πj)T) 1; 2 if βj = , then LP β contains a linear constraint c T j

(Pℓ j=1 yj( πj)T) 1; 3 if βj = 0, then LP β contains two linear constraints c T j

(Pℓ j=1 yj( πj)T) 0 and c T j (Pℓ j=1 yj( πj)T) 0.

Therefore, κ2 is true if for every β Bn, LP β is not

feasible. κ3 is true, if there exists β / Bn such that LP β is feasible. Notice that ℓis viewed as a constant, which means that LP β can be solved in time that is polynomial in m.

κ4 can be verified by enumerating all inputs of f, which takes time that is polynomial in m.

Experiments

We conduct numerical experiments to verify the results in Theorem 1. The first three experiments (Figure 2) follows the same setting as Example 5, 6, 7 respectively. In Figure 2, DPmax Π and DPmin Π (the blue circles and red stars) represent the estimated max-semi-random likelihood and the min-semi-random likelihood of doctrinal paradoxes. The dot curves illustrate the fittings of the estimated semi-random probabilities. The expressions and fitness of all fitting curves are presented in Appendix C. Recalling the notations used in our definition of f DP max Π,r,f(n), we say π Πn is one kind of distribution assignment. We run one million (106) independent trials to estimate the probability of doctrinal paradoxes under each distribution assignment. Then, DPmax Π (or DPmin Π ) takes the maximum (or the minimum) probability of doctrinal paradoxes among all distribution assignments. It is easy to see that the results are consistent with Theorem 1. For example, Figure 2(a) shows that both the maxsemi-random likelihood and the min-semi-random likelihood of doctrinal paradoxes are Θ(1), which matches the result in Table 3. Two additional sets of experiments, whose results are presented in Figure 3(b) in Appendix C, study a more complex setting of three premises.

Conclusions and Future Work

We made a first step towards understanding the likelihood of doctrinal paradox in the semi-random analysis framework. There are many immediate open questions. For example, can we characterize the semi-random likelihood of the paradox for general, more complicated propositions (sometimes called agendas)? Can we remove the strict positiveness assumption on Π? Can we prove semi-random impossibility theorems that extend the quantitative impossibility theorems under i.i.d. uniform distributions (Nehama 2013; Filmus et al. 2020)? Can we generalize the framework to discursive dilemmas or other kinds of responsibility voids? More generally, we believe that building a comprehensive picture of the semi-random properties of aggregation rules in judgement aggregation is a promising (yet challenging) direction in theory and in practice.

Acknowledgements

We thank anonymous reviewers and COMSOC-21 attendees for helpful comments. Lirong Xia is supported by NSF #1453542, ONR #N00014-17-1-2621, and a gift fund from Google. Ao Liu is supported by an RPI-IBM AI Horizons scholarship.

Awad, E.; Booth, R.; Tohm e, F.; and Rahwan, I. 2017. Judgement aggregation in multi-agent argumentation. Journal of Logic and Computation, 27(1): 227 259. Baharad, E.; Neeman, Z.; and Rubinchik, A. 2020. The rarity of consistent aggregators. Mathematical Social Sciences, 108: 146 149. Baumeister, D.; Erdelyi, G.; Erdelyi, O. J.; Rothe, J.; and Selker, A.-K. 2020. Complexity of control in judgment aggregation for uniform premise-based quota rules. Journal of Computer and System Sciences, 112: 13 33. Blum, A.; and Spencer, J. 1995. Coloring random and semirandom k-colorable graphs. Journal of Algorithms, 19(2): 204 234. Bonnefon, J.-F. 2010. Behavioral evidence for framing effects in the resolution of the doctrinal paradox. Social Choice and Welfare, 34: 631 641. Bonnefon, J.-F. 2011. The doctrinal paradox, a new challenge for behavioral psychologists. Advances in Psychological Science, 19(5): 617 623. Braham, M.; and Van Hees, M. 2011. Responsibility voids. The Philosophical Quarterly, 61(242): 6 15. Brandl, F.; Brandt, F.; and Seedig, H. G. 2016. Consistent probabilistic social choice. Econometrica, 84(5): 1839 1880. Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds. 2016. Handbook of Computational Social Choice. Cambridge University Press. Chilton, A.; and Tingley, D. 2012. The doctrinal paradox & international law. University of Pennsylvania Journal of International Law, 34(67). Dietrich, F.; and List, C. 2008. Judgment aggregation without full rationality. Social Choice and Welfare, 31(1): 15 39. Diss, M.; and Merlin, V., eds. 2021. Evaluating Voting Systems with Probability Models. Studies in Choice and Welfare. Springer International Publishing. Endriss, U. 2016. Judgment Aggregation. In Handbook of Computational Social Choice, chapter 17. Cambridge University Press. Endriss, U.; de Haan, R.; Lang, J.; and Slavkovik, M. 2019. The Complexity Landscape of Outcome Determination in Judgment Aggregation. Journal of Artificial Intelligence Research, 69: 687 731. Endriss, U.; Grandi, U.; and Porello, D. 2012. Complexity of Judgment Aggregation. Journal of Artificial Intelligence Research, 45: 481 514.

Everaere, P.; Konieczny, S.; and Marquis, P. 2017. An Introduction to Belief Merging and its Links with Judgment Aggregation. In Trends in Computational Social Choice, chapter 7, 123 143. AI Access. Filmus, Y.; Lifshitz, N.; Minzer, D.; and Mossel, E. 2020. AND testing and robust judgement aggregation. In Proceedings of STOC. Gehrlein, W. V.; and Lepelley, D. 2011. Voting Paradoxes and Group Coherence: The Condorcet Efficiency of Voting Rules. Springer. Grossi, D.; and Pigozzi, G. 2014. Judgment Aggregation: A Primer. Morgan & Claypool Publishers. Hanna, C. 2009. The paradox of progress: Translating evan stark s coercive control into legal doctrine for abused women. Violence Against Women, 15(2): 1458 1476. Kornhauser, L. A.; and Sager, L. G. 1986. Unpacking the Court. The Yale Law Journal, 96(1): 82 117. Lang, J.; and Xia, L. 2016. Voting in Combinatorial Domains. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A., eds., Handbook of Computational Social Choice, chapter 9. Cambridge University Press. Lehtinen, A.; and Kuorikoski, J. 2007. Unrealistic assumptions in rational choice theory. Philosophy of the Social Sciences, 37(2): 115 138. Lenstra, H. W. 1983. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8: 538 548. List, C. 2005. The probability of inconsistencies in complex collective decisions. Social Choice and Welfare, 24: 3 32. List, C. 2012. The theory of judgment aggregation: an introductory review. Synthese, 187: 179 207. List, C.; and Pettit, P. 2002. Aggregating sets of judgments: An impossibility result. Economics and philosophy, 18(1): 89 110. List, C.; and Polak, B. 2010. Introduction to judgment aggregation. Journal of Economic Theory, 145(2): 441 466. Lyon, A.; and Pacuit, E. 2013. The wisdom of crowds: Methods of human judgement aggregation. In Handbook of human computation, 599 614. Springer. Marcoci, A.; and Nguyen, J. 2020. Judgement aggregation in scientific collaborations: The case for waiving expertise. Studies in History and Philosophy of Science Part A, 84: 66 74. Mongin, P. 2008. Factoring out the impossibility of logical aggregation. Journal of Economic Theory, 141(1): 100 113. Mongin, P. 2012. The doctrinal paradox, the discursive dilemma, and logical aggregation theory. Theory and decision, 73(3): 315 355. Mongin, P. 2019. The Present and Future of Judgement Aggregation Theory. A Law and Economics Perspective. In The future of economic design, 417 429. Springer. Nehama, I. 2011. Approximate judgement aggregation. In International Workshop on Internet and Network Economics, 302 313. Springer.

Nehama, I. 2013. Approximately classic judgement aggregation. Annals of Mathematics and Artificial Intelligence, 68: 91 134. Nehring, K.; and Pivato, M. 2021. The median rule in judgement aggregation. Economic Theory. Nehring, K.; and Puppe, C. 2008. Consistent judgement aggregation: the truth-functional case. Social Choice and Welfare, 31(1): 41 57. Nurmi, H. 1999. Voting Paradoxes and How to Deal with Them. Springer-Verlag Berlin Heidelberg. Pauly, M.; and Hees, M. V. 2006. Logical constraints on judgement aggregation. Journal of Philosophical logic, 35(6): 569 585. Pettit, P. 2001. Deliberative democracy and the discursive dilemma. Philosophical Issues, 11: 268 299. Poisson, S. D. 1837. Recherches sur la probabilit e des jugements en mati ere criminelle et en mati ere civile. Rahwan, I.; and Tohm e, F. 2010. Collective argument evaluation as judgement aggregation. In Proceedings of AAMAS. Sorensen, R. 2003. A Brief History of the Paradox: Philosophy and the Labyrinths of the Mind. Oxford University Press. Spielman, D. A.; and Teng, S.-H. 2009. Smoothed Analysis: An Attempt to Explain the Behavior of Algorithms in Practice. Communications of the ACM, 52(10): 76 84. Vacca, R. 1921. Opinioni individuali e deliberazioni collettive. Rivista Internazionale di Filosofia del Diritto, 52(52 59). Van Deemen, A. 2014. On the empirical relevance of Condorcet s paradox. Public Choice, 158(3): 311 330. Xia, L. 2020. The Smoothed Possibility of Social Choice. In Proceedings of Neur IPS. Xia, L. 2021a. How Likely Are Large Elections Tied? In Proceedings of ACM EC. Xia, L. 2021b. The Semi-Random Satisfaction of Voting Axioms. Advances in Neural Information Processing Systems, 34. Xia, L.; and Zheng, W. 2021. The Smoothed Complexity of Computing Kemeny and Slater Rankings. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, 5742 5750. Zhang, H.; and Conitzer, V. 2019. A PAC Framework for Aggregating Agents Judgments. In Proceedings of AAAI.