Plurality, Borda Count, or Anti-plurality: Regress Convergence Phenomenon in the Procedural Choice

Abstract

We focus on voters’ preference profiles where at least two of the three selected voting rules (e.g. plurality, Borda count, and anti-plurality) produce different outcomes—thus, the voting body needs a procedural choice. While this situation evokes an infinite regress argument for the choice of rules to choose rules to choose rules to…and so on, we introduce a new concept named regress convergence, where every voting rule in the menu ultimately gives the same outcome within the finite steps of regress. We study the mechanism of this phenomenon in a large consequential society having a triplet of scoring rules. The results show that, in the menu of plurality, Borda count, and anti-plurality, the probability that the regress convergence happens is 98.2% under the Impartial Culture assumption and 98.8% under the Impartial Anonymous Culture assumption.

1 Introduction

In modern democratic societies, the choice of voting rules has an important role. Saari [17] shows that a single profile of ten candidates could result in millions of different rankings for ten candidates simply depending on the choice of scoring rule. Even when there are three candidates, Saari shows that a preference profile could support up to seven different rankings¹ by changing the scoring rule. Nurmi [14] also argues the discrepancies within popular voting rules, the plurality, Borda count, max-min, and Copeland’s method. Therefore, in addition to the choice of candidates, society must also choose their voting rules, which will also require to choose a voting rule for the choice of a voting rule. In this way, procedural choice falls into an infinite regress.

To overcome this problem, a growing number of studies have been carried out both from axiomatic and probabilistic viewpoints. Barbera and Jackson [2] and Koray [10] axiomatically studied the properties, called self-stability and self-selectivity, of a single voting rule for two and three or more alternatives, respectively. These concepts demand that a voting rule should choose itself among the other voting rules at hand in the voting on the voting rules. Later on, the concepts are extended to apply for the set of voting rules. A set of voting rules is (first-level) stable if for any profile there is exactly one rule that chooses itself (Houy [9]), or if there is at least one self-selective voting rule (Diss and Merlin [4]). Using the methods developed by Saari and Tataru [18] and Merlin et al. [13], Diss and Merlin [4] estimate the likelihood that the set of plurality (P), Borda (B) and anti-plurality (A) is stable under the Impartial Culture (IC) assumption within a large society. Diss et al. [3] also determines corresponding probabilities under the Impartial Anonymous Culture (IAC) assumption. These estimations show that the set of $\left\{ {P,B,A} \right\}$ is stable with a probability 84.49% under IC and 84.10% under IAC within a large society.

The objective of the present article is to propose a new way to analyze and solve the regress argument. Specifically, we formulate a phenomenon, named regress convergence, where the regress argument is supposed to naturally disappear within the finite steps of regress, and we show that this phenomenon occurs quite frequently in the choice of triplets of scoring rules. The regress convergence is a phenomenon where every voting rule in the agenda ultimately designates the same outcome.² Let us explain this with an example. Suppose a society of 14 individuals chooses one of three candidates $a,b,c$, and there is an ex ante agreement on the set of voting rules, $F = \left\{ {P,B,A} \right\}.$ When the preference profile on the set of candidates $X$ is given as $L_{1-10}^{0} :abc,$ and $L_{11-14}^{0} :bca$ (individuals $1,2, \ldots ,10$ prefer $a$ to $b$ and $b$ to $c$ and individuals $11,12,13,14$ prefer $b$ to $c$ and $c$ to $a)$, the three voting rules $P, B,$ and $A$ yield $\left\{ a \right\},\left\{ a \right\},$ and $\left\{ b \right\},$ respectively. Suppose now that the same society votes on which rule in $F$ to use. If everyone is consequential (i.e., preferring those rules that yield better candidates for themselves) and is supposed to submit a linear ordering, it is natural to think that the first 10 individuals submit either $^{{\prime \prime }} PBA^{{\prime \prime }}$ or $^{{\prime \prime }} BPA,^{{\prime \prime }}$ and the remaining four individuals submit $^{{\prime \prime }} APB^{{\prime \prime }}$ or $^{{\prime \prime }} ABP^{{\prime \prime }}$. Suppose that they submit the following: $L_{1-4}^{1} :PBA$, $L_{5 - 10}^{1} :BPA$, and $L_{11-14}^{1} :APB$. For this profile $\left( {L_{1}^{1} ,L_{2}^{1} \ldots ,L_{14}^{1} } \right)$, $P$ yields $\left\{ B \right\}$ while $B$ and $A$ yield $\left\{ P \right\}$ (See Fig. 1).

Fig. 1.

Example of a regress convergence.Footnote

Note that no rule chooses itself in the figure. Therefore, the weak convergence does not logically imply the stability of the menu of SCRs in either Houy [9]’s or Diss and Merlin [4]’s sense. We can also say that the existence of a self-selective rule does not imply regress convergence (See the trivial deadlock described in Definition 5 and Fig. 2).

$F^{1}$ denotes the set of voting rules for the choice of candidates and $F^{2}$ denotes the set of voting rules for the choice of $F^{1}$.

Note that each $P^{2} ,B^{2}$, and $A^{2}$ (a rule to choose the rule) ultimately reach the same outcome $\left\{ a \right\}$. This means that no matter which rule in $F^{2}$ is selected, the outcome is the same. Hence, further regress has no meaning for the determination of the ultimate outcome. In a large and consequential society, our result shows that the regress convergence phenomenon is not so rare. Indeed, under the menu of $\left\{ {P,B,A} \right\}$, for example, the phenomenon occurs at more than 98% under either IC or IAC (Corollary 1).

The present article is organized as follows. Section 2 introduces the notation. Section 3 states basic results, and some of the results are expanded in the discussion found in Sect. 4. The conclusion is stated in Sect. 5, and all proofs are in the Appendix.

2 Notation

Suppose a society $N = \left\{ {1,2, \ldots ,n} \right\}\left( {n \ge 3} \right)$ makes a collective decision over the choice of $m$ alternatives without an agreement on the Social Choice Rule (SCR). Let $X = \left\{ {x_{1} , \ldots ,x_{m} } \right\}$ be the set of alternatives. Suppose also that they have in their mind $m$ possible SCRs, denoted by $f_{1} ,f_{2} , \ldots ,f_{m}$. We call this combination a menu of SCRs. For any nonempty set $A$, we denote by ${\mathcal{L}}\left( A \right)$ the set of all linear orderings over A.

Each individual $i \in N$ is supposed to have a linear preference $L_{i}^{0} { \in \mathcal{L}}\left( X \right)$. The combination of $L_{1}^{0} , \ldots ,L_{n}^{0}$ is called a level-$0$ preference profile. An SCR $f$ over a nonempty set $A$ is a correspondence $f:\left( {{\mathcal{L}}\left( A \right)} \right)^{n} \twoheadrightarrow A$ such that $\phi \ne f\left( L \right) \subseteq A$ for all $L{ \in }\left( {{\mathcal{L}}\left( A \right)} \right)^{n}$. A scoring SCR $f$ for $m$ options is an SCR that assigns to each alternative $s_{j} \left( {j = 1,2, \ldots ,m} \right)$ points if it is ranked at the $j^{th}$ position in the preferences, where $1 = s_{1} \ge s_{2} \ge \cdots \ge s_{m} \ge 0$ ⁴. Then, $f\left( L \right)$ is defined as the set of options with the highest scores. We often express score assignments as $f:\left[ {s_{1} ,s_{2} , \ldots ,s_{m} } \right]$. If $m = 3$, the plurality rule $f_{P}$ has the assignment $\left[ {1,0,0} \right]$, the Borda count $f_{B}$ has the assignment $\left[ {1,1/2,0} \right]$, and the anti-plurality rule $f_{A}$ has the assignment $\left[ {1,1,0} \right]$. For any $m \in {\mathbb{N}}$, a k-approval voting $f_{{E_{k} }}$ is a scoring SCR such that $s_{1} = s_{2} = \cdots = s_{k} = 1$ and $s_{k + 1} = s_{k + 2} = \cdots = s_{m} = 0$.

The regress argument, i.e., the choice of SCRs for the choice of SCRs for the choice of…and so on, is supposed to be as follows (the terms in italics are formally defined later). It starts from the choice of X using the set of SCRs $F^{1}$ (level-1 issue). If the society finds a regress convergence, then the regress stops. Otherwise, the society goes up to the choice of $F^{1}$ using the set of SCRs $F^{2}$ (level-2 issue). If the society finds a regress convergence, then the regress stops. Otherwise, the society makes the choice of $F^{2}$ using $F^{3}$ (level-3 issue), and so on there is regress convergence at some level. Note also that each individual is supposed to be consequential throughout the regress process.

Definition 1 (Level).

Let $X = F^{0}$. For any $k \in {\mathbb{N}}\mathop \cup \nolimits \left\{ 0 \right\}$, the level-k issue is the choice from $F^{k - 1}$ using $f_{1} ,f_{2} , \ldots ,f_{m}$. At this level, each SCR $f_{j} \left( {j = 1,2, \ldots ,m} \right)$ is called a level-k SCR and is often denoted by $f_{j}^{k}$. We denote by $F^{k} = \left\{ {f_{1}^{k} , \ldots ,f_{m}^{k} } \right\}$ the set of level-k SCRs.

Definition 2 (Class ${\mathbf{C}} \subseteq {\mathbf{X}}$ of ${\mathbf{f}}^{{\mathbf{k}}} \in {\mathbf{F}}^{{\mathbf{k}}}$).

For any level-1 SCR $f \in {\mathcal{F}}^{1}$, its class at $L^{0} \in \left( {{\mathcal{L}}\left( X \right)} \right)^{n}$ is $f\left( {L^{0} } \right)\left( { \subseteq X} \right)$. For $k \ge 2$, the class of $g \in {\mathcal{F}}^{k}$ at $L^{0} \in \left( {{\mathcal{L}}\left( X \right)} \right)^{n}$, $L^{1} \in \left( {{\mathcal{L}}\left( {F^{1} } \right)} \right)^{n}$, …, $L^{k - 1} \in \left( {{\mathcal{L}}\left( {F^{k - 1} } \right)} \right)^{n}$, denoted $C_{g} \left[ {L^{0} , \ldots ,L^{k - 1} } \right]$ or simply $C_{g}$, is the union of each class of $h \in g\left( {L^{k - 1} } \right)$ at $L^{0} ,L^{1} , \ldots ,L^{k - 2}$.

Definition 3 (Consequentialism).

Let $k \in {\mathbb{N}}$ and $L^{j} \in \left( {{\mathcal{L}}\left( {F^{j} } \right)} \right)^{n}$ $\left( {j = 0,1, \ldots ,k - 1} \right)$. $L^{k} \in \left( {{\mathcal{L}}\left( {F^{k} } \right)} \right)^{n}$ is called a consequentially induced level-k profile from $L^{0} , \ldots ,L^{k - 1}$ if for all $i \in N$, $x,y \in X$, $f,g \in F^{k}$, if $C_{f} = \left\{ x \right\}$, $C_{g} = \left\{ y \right\}$, and $xL_{i}^{0} y$, then $fL_{i}^{k} g$. We denote by ${\mathcal{L}}^{k} \left[ {L^{0}, \ldots ,L^{k} } \right]$ the set of all such profiles.

When $L^{0} ,L^{1} , \ldots ,L^{k}$ is a sequence of profiles such that $L^{j}$ $\left( {j = 1, \ldots ,k} \right)$ is a consequentially induced level-j profile from the preceding profiles, we simply say $L^{0} , \ldots ,L^{k}$ as a consequential sequence of profiles. We are now ready to formally state how the regress argument could stop. The weak regress convergence (Definition 4) and the trivial deadlock (Definition 5) are thought to be a success and failure, respectively, in the procedural regress argument. In either case, further regress is thought to be meaningless.

Definition 4 (Weak Regress Convergence).

Let $\left\{ {f_{1} , \ldots ,f_{m} } \right\}$ be the menu of SCRs. A level-0 preference profile $L^{0} = \left( {L_{1}^{0} ,L_{2}^{0} , \ldots ,L_{n}^{0} } \right) \in \left( {{\mathcal{L}}\left( X \right)} \right)^{n}$ weakly converges to $C \subseteq X$ if and only if a consequential sequence of profiles $L^{0} ,L^{1} \ldots ,L^{k}$ exist such that $f_{1}^{k} ,f_{2}^{k} , \ldots ,f_{m}^{k}$ are all in the same class C at $L^{0} , \ldots ,L^{k}$.

Definition 5 (Trivial Deadlock).

Let $\left\{ {f_{1} , \ldots ,f_{m} } \right\}$ be the menu of SCRs. A level-0 preference profile $L^{0} \in \left( {{\mathcal{L}}\left( X \right)} \right)^{n}$ is said to cause a trivial deadlock if and only if $f_{1} \left( {L^{0} } \right),f_{2} \left( {L^{0} } \right), \ldots ,f_{m} \left( {L^{0} } \right)$ are mutually distinct singletons.⁵

Example 1.

Suppose $m = 3$ and the menu of SCRs is $\left\{ {f_{P} ,f_{B} ,f_{A} } \right\}$. If $f_{P}^{1} \left( {L^{0} } \right) = \left\{ {x_{1} } \right\}$, $f_{B}^{1} \left( {L^{0} } \right) = \left\{ {x_{2} } \right\}$, and $f_{A}^{1} \left( {L^{0} } \right) = \left\{ {x_{3} } \right\}$ (as in Fig. 2), it is clear that for all $k \in {\mathbb{N}}$, a consequentially induced $L^{k}$ is unique and $f_{P}^{k + 1} \left( {L^{k} } \right) = \left\{ {f_{P}^{k} } \right\}$, $f_{B}^{k + 1} \left( {L^{k} } \right) = \left\{ {f_{B}^{k} } \right\}$, and $f_{A}^{k + 1} = \left\{ {f_{A}^{k} } \right\}$. Therefore, no matter how high of a level we see, the structure does not change at all, which makes the regress argument meaningless in a negative sense (Fig. 2).

Fig. 2.

A graph image of trivial deadlock

Finally, we discuss the asymptotic probabilities as $n \to \infty$. Among the probabilistic studies of voting events, there are two major assumptions on the distribution of preferences. One is called the Impartial Culture (IC). It assumes that each voter independently chooses, with equal likelihood, one of the linear orderings over X. Therefore, each profile $L^{0} \in \left( {{\mathcal{L}}\left( X \right)} \right)^{n}$ occurs with probability $1/\left( {m\text{!}} \right)^{n}$. The other assumption is called the Impartial Anonymous Culture (IAC). This assumes that every voting situation, a combination of the numbers of individuals who each have a specific linear ordering, occurs with equal likelihood. Hence, each $\left( {n_{1} , \ldots ,n_{{m\text{!}}} } \right)$, where $n_{j}$ represents the number of individuals who have the $j^{th}$ linear ordering, occurs with the probability $1/_{{n + m\text{!} - 1}} C_{n}$. While the probability of certain events, such as the Condorcet winner exists, can differ according to which assumption is used, there are two common properties when $n \to \infty$. The first common property is that the probability that a specific scoring rule yields a tied outcome is negligible as $n \to \infty$ ⁶ (Marchant [12]; Pritchard and Wilson [15]; Pritchard and Wilson [16]; Diss and Merlin [4]). Let us denote by $p_{I}$ the probability that at least one level-1 SCR in $F^{1}$ yields a tied outcome. Because IC and IAC both say that $p_{I} \to 0$ as $n \to \infty$, we can focus only on the cases where each level-1 SCR yields a singleton outcome. The second common property is that the probability that exactly $\alpha \in \left[ {0,1} \right]$ of the whole individuals prefer x to y for some $x,y \in X,$ where $\alpha$ is a fixed constant, is negligible as $n \to \infty$. We show this in the appendix (Lemma 3).⁷ We denote by $q_{\alpha }$ the probability that exactly $\alpha$ of the whole individuals prefer x to y for some $x,y \in X.$

In sum, either under IC or IAC, the probabilities $p_{I}$ and $q_{\alpha }$ (for several $\alpha$ s) are both negligible as $n \to \infty$. Based on this property, we next evaluate $p_{WC}$ , the probability that those level-0 profiles occur that weakly converge, and $p_{D}$ , the probability that those occur that cause a trivial deadlock.

3 Results

Beginning with preliminary lemmas, we show our central result Proposition 1. It shows under several conditions that the regress argument can be solved (with weak convergence) unless it falls in the trivial deadlock.

Lemma 1.

Let $n \ge m$ and $F = \left\{ {g_{1} ,g_{2} , \ldots ,g_{p} ,h_{1} ,h_{2} , \ldots ,h_{q} } \right\}$ $\left( {p \ge q \ge 0} \right)$ be the menu of scoring SCRs, where $m = p + q \ge 3.$ For given consequential sequence of profiles $L^{0} , \ldots ,L^{k - 1}$ and alternatives $x,y \in X,$ suppose the following holds:

$$ C_{{g_{j}^{k} }} \left[ {L^{0} ,L^{1} , \ldots ,L^{k - 1} } \right] = \left\{ x \right\}\, {\text{for all }}j = 1,2, \ldots ,p $$

(1)

$$ C_{{h_{j}^{k} }} \left[ {L^{0} ,L^{1} , \ldots ,L^{k - 1} } \right] = \left\{ y \right\}\, {\text{for all }}j = 1,2, \ldots ,q. $$

(2)

If ${\# }\left\{ {\left. {i \in N} \right|xL_{i}^{0} y} \right\} > {\# }\left\{ {\left. {i \in N} \right|yL_{i}^{0} x} \right\},$ then $L^{0}$ weakly converges to $\left\{ x \right\}.$

Lemma 2.

Let $n \ge m,$ $m = 3 \, {\text{or}}4,$ and $x,y \in X$ such that ${\# }\left\{ {\left. {i \in N} \right | xL_{i}^{0} y} \right\} \ne n/2.$ If the menu of SCRs is $F = \left\{ {f_{{E_{1} }} ,f_{{E_{2} }} , \ldots ,f_{{E_{m - 1} }} ,f_{B} } \right\}$ and the class of each level-$k$ SCR is either $\left\{ x \right\}$ or $\left\{ y \right\}$ at given $L^{0} , \ldots ,L^{k - 1}$ , then $L^{0}$ weakly converges.

Proposition 1.

Suppose ${m} = {{3}}$ and n is large (${n} \to \infty$ ). Denote the three scoring SCRs as ${f}_{{i}}:\left[ {{1},{s}_{{i}} ,{{0}}} \right]\left( {{i} = {{1,2,3}}} \right),$ where ${1} \ge {s}_{{{1}}} > {s}_{{{2}}} > {s}_{{{3}}} \ge {{0}}.$ Either under IC or IAC, we have ${p}_{{{WC}}} \approx {1} - {p}_{{D}}$ whenever the following holds:

$$ s_{3} \ge 1/2 \, {\text{or}}\left[ {s_{3} < 1/2 \, {\text{and}} \, s_{2} \le \frac{{1 + s_{3} }}{{2 - s_{3} }}} \right]. $$

(3)

It is worth noting that if the menu of SCRs contains $\left\{ {f_{B},\,f_{A} } \right\}$ or $\left\{ {f_{P},\,f_{B} } \right\},$ then the condition 0 automatically holds irrespective of the last one. Therefore, once a large consequential society admits the menu $\left\{ {f_{P},\,f_{B} ,f_{A} } \right\},$ for example, Proposition 1 shows there are approximately only two possibilities: they face a trivial deadlock, or they are endowed with the ability to realize the weak convergence. The probability $p_{D}$ under IC and IAC is determined by Diss and Merlin [4] and Diss et al. [3]. Based on their probability calculation, we have the following.

Corollary 1.

Let ${n} \to \infty$ and ${m} = {{3}},$ where the menu of SCRs is given by $\left\{ {{f}_{{P}} ,{f}_{{B}} ,{f}_{{A}} } \right\}.$ Under IC, the regress weakly converges with a probability of 98.2%. Under IAC, the regress weakly converges with the probability of 98.8%.

4 Discussion

4.1 Uniqueness of the Convergent Outcome

$L^{0} \in {\mathcal{L}}\left( X \right)$ is said to weakly converge if at least one consequential sequence of (subsequent) profiles $L^{1},\,L^{2}, \ldots$ exists⁸ that adjust the rules’ ultimate judgments at a certain level. The existence of such $L^{1} ,L^{2} , \ldots$ guarantees that we can stop the apparent infinite regress arguments through finite steps of regress. One might, however, be concerned that the same $L^{0}$ might weakly converge to a distinct C and $C^{{\prime }}$ by the choice of the sequence. Now, we show that the set of $\left\{ {f_{P} ,f_{B} ,f_{A} } \right\}$ guarantees the uniqueness of the convergent outcome with a slightly stronger assumption on the meta-preferences.

Definition 5 (Strong Convergence).

Let $\left\{ {{f}_{{{1}}},\, \ldots ,{f}_{{m}} } \right\}$ be the menu of SCRs. A level-0 preference profile ${L}^{0} \in \left( {{\mathbf{\mathcal{L}}}\left( {X} \right)} \right)^{{n}}$ strongly converges to $C \subseteq X$ if and only if it weakly converges to C, and if it does not weakly converge to any other $C^{\prime} \subseteq X.$ (Note that strong convergence implies weak convergence but not vice versa.)

Expected Utility assumption (EU). For given $L^{0} \in \left( {{\mathcal{L}}\left( X \right)} \right)^{n}$ and their utility representations $u_{i}^{0} :X \to {\mathbb{R}}\left( {i \in N} \right),$ i.e. $u_{i}^{0} \left( x \right) \ge u_{i}^{0} \left( y \right) \Leftrightarrow xL_{i}^{0} y,$ the subsequent sequence of profiles $L^{1} ,L^{2} , \ldots$ satisfies EU if they satisfy the following:

• (1) Each $i \in N$ has utility function $u_{i}^{k}$ over $F^{k}$ such that $\forall f,g \in F^{k} \left( {k \in {\mathbb{N}}} \right),$

  $$ u_{i}^{k} \left( f \right) \ge u_{i}^{k} \left( g \right) \Leftrightarrow \frac{{\mathop \sum \nolimits_{{x \in C_{f} }} u_{i}^{0} \left( x \right)}}{{\left| {C_{f} } \right|}} \ge \frac{{\mathop \sum \nolimits_{{y \in C_{g} }} u_{i}^{0} \left( y \right)}}{{\left| {C_{g} } \right|}} $$

  (4)

• (2) Let $R_{i}^{k}$ be a weak ordering represented by $u_{i}^{k}$. $L_{i}^{k}$ is compatible with $R_{i}^{k}$ (i.e. $L_{i}^{k}$ is obtained by breaking the indifferences in $R_{i}^{k}$ ).

(Note that EU logically implies consequentialism (Definition 3), but not vice versa.)

Under EU, we modify Definition 4 by substituting “a consequential sequence of profiles $L^{0} ,L^{1} , \ldots$” with “a sequence of profiles $L^{0} ,L^{1} , \ldots$ satisfying EU”.

Proposition 2.

Assume ${m} = {{3}},$ ${n} \to \infty$, EU, and either IC or IAC. Then, for the menu of SCRs ${F} = \left\{ {{f}_{{P}} ,{f}_{{B}} ,{f}_{{A}} } \right\},$ we have ${p}_{{{SC}}} \approx {1} - {p}_{{D}}$, where ${p}_{{{SC}}}$ is the probability that ${L}^{{0}}$ occurs that strongly converges.

Based on Proposition 2, a large consequential society holding $\left\{ {f_{P} ,f_{B} ,f_{A} } \right\}$ as the menu of SCRs has only two possibilities: either the society faces a trivial deadlock (with at most 1.8% under IC and 1.2% under IAC) or they can know the possible regress convergence without implementing the regress arguments.

4.2 Tie-Breaking by the Scoring Rules

Finally, we deal with the choice of Social Choice Function (SCF) (i.e., not a correspondence but a function). Suppose we provide SCRs with neutral tie-breaking systems. Especially, for any SCR $f_{Y}$, we denote by $f_{{Y^{\text{ * }} }}$ the SCF that breaks ties in favor of $i_{Y} \in N$, named the tie breaker of $f_{Y}$. Note that different SCRs are allowed to have different tie breakers (for example, the plurality tie breaker $i_{P} = 1$ and the Borda count tie breaker $i_{B} = 2)$. Then, Proposition 2 can be revised for a relatively small n (it is straightforward to revise the proofs of Lemma 2 and Proposition 2, so we omit the proof).

Proposition 3.

Let us assume n is odd (${n} \ge {3})$, ${m} = {3}$, and the menu of SCFs is either $\left\{ {{f}_{{{P}^{*} }} ,{f}_{{{X}^{*} }} ,{f}_{{{A}^{*} }} } \right\}$, where ${f}_{{X}}$ is either the Borda count, Black’s rule, Copeland’s method, or the Hare system.⁹ Then, any level-0 profile ${L}^{0}$ either causes trivial deadlock or strongly converges.

5 Conclusion

We analyzed the regress arguments for procedural choice in a large $\left( {n \to \infty } \right)$ consequential society. Once the society admits the menu of SCRs (plurality, Borda count, and anti-plurality), the probability that at least two of them give different outcomes is about 46.5% under IC (from Table 7 of Diss and Merlin [4]). While this fact emphasizes the importance of procedural choice, Proposition 1 says that at more than 98% (either under IC or IAC), we can derive a weak convergence. Furthermore, our Proposition 2 and Proposition 3 show even further that there are ways to uniquely determine the possible convergent outcome.

A different interpretation of our results can be obtained when compared with Suzuki and Horita [19], who argue the difficulties of ranking meta-procedures with a menu of all the possible SCFs. On the other hand, the present paper shows that the difficulty of procedural choice quite frequently disappears when the society considers a relatively small menu of voting rules, such as plurality, Borda count, and anti-plurality. It can be an interesting future topic to determine the tradeoff between the size of the menu and the possibility of resolving the regress problem.¹⁰

A Appendix

Extra Notation: If $f^{k} \in F^{k}$ is obvious in the context, we denote by $s\left( {f^{k - 1} :L^{k - 1} } \right)$ the score of $f^{k - 1} \in F^{k - 1}$ at $L^{k - 1}$ evaluated by $f^{k}$. If $L^{k - 1}$ is also obvious, we write as $s\left( {f^{k - 1} } \right)$.

Lemma 3.

For any $x,y \in X$ and $\alpha \in \left[ {0,1} \right]$, and either under IC or IAC assumption, $P\left( \alpha \right)$, the probability that exactly $n\alpha$ individuals prefer x to y, converges to zero as $n \to \infty$.

Proof of Lemma 3.

We can suppose $n\alpha \in {\mathbb{N}}$. [Under IC] We have the following:

$$ P\left( \alpha \right) = \left( {\begin{array}{*{20}c} n \\ {n\alpha } \\ \end{array} } \right)\left( {\frac{1}{2}} \right)^{n\alpha } \left( {\frac{1}{2}} \right)^{{n\left( {1 - \alpha } \right)}} = \left( {\begin{array}{*{20}c} n \\ {n\alpha } \\ \end{array} } \right)\left( {\frac{1}{2}} \right)^{n}. $$

Because the proof is similar, we show only for even n. Let $n = 2k\left( {k \in {\mathbb{N}}} \right)$. Then,

$$ P\left( \alpha \right) \le P\left( {\frac{1}{2}} \right) = \left( {\begin{array}{*{20}c} {2k} \\ k \\ \end{array} } \right)\left( {\frac{1}{2}} \right)^{2k} = \frac{{\left( {2k} \right)\text{!}}}{{k!k\text{!}}}\left( {\frac{1}{2}} \right)^{2k} $$

Using Stirling’s approximation, we can evaluate the RHS as

$$ \mathop {\lim }\limits_{{\begin{array}{*{20}c} {k \to \infty } \\ {\left( { \Leftrightarrow n \to \infty } \right)} \\ \end{array} }} \frac{{\left( {2k} \right)\text{!}}}{{k\text{!}k\text{!}}}\left( {\frac{1}{2}} \right)^{2k} = \mathop {\lim }\limits_{k \to \infty } \frac{{\sqrt {2\pi \cdot 2k} \left( {\frac{2k}{e}} \right)^{2k} }}{{\left( {\sqrt {2\pi k} \left( {\frac{k}{e}} \right)^{k} } \right)^{2} }}\left( {\frac{1}{2}} \right)^{2k} = \mathop {\lim }\limits_{k \to \infty } \frac{1}{{\sqrt {\pi n} }} = 0. $$

[Under IAC] Let $a = {\# }\left\{ {\left. {i \in N} \right| xL_{i}^{0} y} \right\} = n\alpha$ and $b = n-a$. The probability is described as:

$$ P\left( \alpha \right) = \left( {\begin{array}{*{20}c} {a + \frac{{m\text{!}}}{2} - 1} \\ a \\ \end{array} } \right) \cdot \left( {\begin{array}{*{20}c} {b + \frac{{m\text{!}}}{2} - 1} \\ b \\ \end{array} } \right)/\left( {\begin{array}{*{20}c} {a + b + m\text{!} - 1} \\ {a + b} \\ \end{array} } \right). $$

With a simple calculation, this is shown to converge to zero as $n = a + b \to \infty$. ■

Proof of Lemma 1.

Assume that $F = \left\{ {g_{1} , \ldots ,g_{p} ,h_{1} , \ldots ,h_{q} } \right\}$ and $L^{0} ,L^{1} , \ldots ,L^{k - 1}$ satisfy the given condition. Let $A = \left\{ {1,2, \ldots ,a} \right\} = \left\{ {\left. {i \in N} \right| xL_{i}^{0} y} \right\}$. If $q = 0$, the lemma is obvious. So, we assume $p \ge q > 0$. It follows that $0 < \left| A \right| = a < n$ (if $a = 0$, e.g., no level-1 SCR chooses $\left\{ x \right\}$, which contradicts with $p > 0)$. Since $n \ge m$, we have $a \ge \left( {n/2} \right) \ge \left( {m/2} \right) \ge q$. Let $L^{k}$ be a profile on $F^{k}$ defined as follows:

$$ \begin{aligned} & L_{i}^{k} :g_{1}^{k} ,g_{2}^{k} , \ldots ,g_{p}^{k} ,h_{1}^{k} ,h_{2}^{k} , \ldots ,h_{i - 1}^{k} ,h_{i + 1}^{k} , \ldots ,h_{q}^{k} ,h_{i}^{k}\ \text{for all}\ 1 \le i \le q \\ & L_{i}^{k} :g_{1}^{k} ,g_{2}^{k} , \ldots ,g_{p}^{k} ,h_{1}^{k} ,h_{2}^{k} , \ldots ,h_{q}^{k} \, \text{for all}\ q + 1 \le i \le a \\ & L_{i}^{k} :h_{1}^{k} ,h_{2}^{k} , \ldots ,h_{q}^{k} ,g_{1}^{k} ,g_{2}^{k} , \ldots ,g_{p}^{k} \, \text{for} \, \text{all}\,i \in N{ \setminus }A. \\ \end{aligned} $$

In words, this is a level-k profile where everyone (except the first q individuals) orders $\left\{ {g_{1}^{k} , \ldots ,g_{p}^{k} } \right\}$ and $\left\{ {h_{1}^{k} , \ldots ,h_{q}^{k} } \right\}$ lexicographically. Clearly, we have $L^{k} \in {\mathcal{L}}^{k} \left[ {L^{0} , \ldots ,L^{k - 1} } \right]$. Take any $f^{k + 1} :\left[ {1 = s_{1} ,s_{2} , \ldots ,s_{m} = 0} \right] \in F^{k + 1}$ and consider the scores evaluated by this $f^{k + 1}$. Note that $h_{1}^{k}$ has the largest score among $h_{1}^{k} , \ldots ,h_{q}^{k}$. We have

$$ \begin{array}{*{20}c} {s\left( {g_{1}^{k} } \right) - s\left( {h_{1}^{k} } \right) = \left\{ {a + \left( {n - a} \right)s_{q + 1} } \right\} - \left\{ {n - a + \left( {a - 1} \right)s_{p + 1} } \right\}} \\ { \ge 2a - n + \left( {n - a} \right)s_{q + 1} - \left( {a - 1} \right)s_{q + 1} \left( {\because p \ge q \Rightarrow s_{q + 1} \ge s_{p + 1} } \right)} \\ { = \left( {2a - n} \right)\left( {1 - s_{q + 1} } \right) + s_{q + 1} > 0 \left( {\because 2a > n \, {\text{and}} \, 0 \le s_{q + 1} \le 1} \right).} \\ \end{array} $$

Since this holds for any $f^{k + 1} \in F^{k + 1}$, we obtain the weak convergence to $\left\{ x \right\}$ (via $L^{k}$). ■

Proof of Lemma 2.

Let $A = \left\{ {1,2, \ldots ,a} \right\} = \left\{ {\left. {i \in N} \right| xL_{i}^{0} y} \right\}$, $G\text{ := }\left\{ {\left. g \right|C_{g} = \left\{ x \right\}} \right\} = \left\{ {g_{1}^{k} , \ldots ,g_{p}^{k} } \right\}$ $\left( {p = \left| G \right|} \right)$ and $H\text{ := }\left\{ {\left. h \right|C_{h} = \left\{ y \right\}} \right\} = \left\{ {h_{1}^{k} , \ldots ,h_{q}^{k} } \right\}$ $\left( {q = \left| H \right|} \right)$. With Lemma 1, we have only to consider $0 < a < n - a$ and $p > q > 0$, i.e. $\left( {p,q} \right) = \left( {2,1} \right)$ if $m = 3$ or $\left( {p,q} \right) = \left( {3,1} \right)$ if $m = 4$. Since the proof is similar, we show for the latter, $m = 4$. We can check that for all $L^{k} \in {\mathcal{L}}^{k} \left[ {L^{0} , \ldots ,L^{k - 1} } \right]$, $f_{{E_{1} }} \left( {L^{k} } \right) \subseteq H$ and the scores (at $L^{k}$) satisfy

$$ S\text{ := }s_{B} \left( {g_{1}^{k} } \right) + s_{B} \left( {g_{2}^{k} } \right) + s_{B} \left( {g_{3}^{k} } \right) = a\left( {s_{1} + s_{2} + s_{3} } \right) + \left( {n - a} \right)\left( {s_{2} + s_{3} + s_{4} } \right) = n + a. $$

Let $p_{1} , \ldots ,p_{6}$ be preferences over G such that $p_{1} :g_{1}^{k} g_{2}^{k} g_{3}^{k}$, $p_{2} :g_{3}^{k} g_{2}^{k} g_{1}^{k}$, $p_{3} :g_{3}^{k} g_{1}^{k} g_{2}^{k}$, $p_{4} :g_{2}^{k} g_{1}^{k} g_{3}^{k}$, $p_{5} :g_{1}^{k} g_{3}^{k} g_{2}^{k}$, and $p_{6} :g_{2}^{k} g_{3}^{k} g_{1}^{k}$. We construct $L^{k} \in {\mathcal{L}}^{k} \left[ {L^{0} , \ldots ,L^{k - 1} } \right]$ as follows: if $i \equiv j$ (mod 6) then $\left. {L_{i}^{k} } \right|_{G} = p_{j}$ $\left( {j = 1,2, \ldots ,6} \right)$, and $g_{\mu }^{k} L_{i}^{k} h_{1}^{k} \left( {\mu = 1,2,3} \right) \Leftrightarrow i \le a$. Because of the symmetry, we obtain that $s_{B} \left( {g_{j}^{k} :L^{k} } \right) - S/3 \in \left\{ { - 1/3,0,1/3} \right\}$ $\left( {j = 1,2,3} \right)$. Hence,

$$ D\left( {L^{k} } \right)\text{ := }s_{B} \left( {h_{1}^{k} :L^{k} } \right) - \hbox{max} \left\{ {s_{B} \left( {g_{1}^{k} :L^{k} } \right),s_{B} \left( {g_{2}^{k} :L^{k} } \right),s_{B} \left( {g_{3}^{k} :L^{k} } \right)} \right\} \ge \frac{2}{3}\left( {n - 2a} \right) - \frac{1}{3}. $$

Since $n - 2a \ge 1$, we have $D\left( {L^{k} } \right) > 0$. (1) The case of $n - 2a \ge 2$. Then, we have $D\left( {L^{k} } \right) \ge 1$. Suppose $\left\{ {g,h_{1}^{k} } \right\} \in f_{{E_{{j{^{\prime}} }} }} \left( {L^{k} } \right)$ for some $g \in G$ and $j^{\prime} = 2,3$. Let j be the smallest such $j^{\prime}$. Since $s_{j} \left( {h_{1}^{k} } \right) = n - a < n$, there exists $i_{g} \in N$ whose $L_{{i_{g} }}^{k}$ assign zero point to g and one point to $g^{\prime} \in G{ \backslash}\left\{ g \right\}$. Let $L^{\prime k}$ be a profile where $i_{g}$ swaps g and $g^{\prime}$. Then, we have $s_{j} \left( {g:L^{\prime k} } \right) > s_{j} \left( {g:L^{k} } \right) = s_{j} \left( {h_{1}^{k} :L^{k} } \right) > s_{j} \left( {h_{1}^{k} :L^{\prime k} } \right)$. Therefore, $f_{{E_{j} }} \left( {L^{\prime k} } \right) = \left\{ g \right\} \subseteq G$. Since the change in Borda score of $g_{1}^{k} ,g_{2}^{k} ,g_{3}^{k}$ is at most $2/3$, we still have $D\left( {L^{\prime k} } \right) \ge 1 - \left( {2/3} \right) > 0$. (2) The case of $n - 2a = 1$. Since n is odd, we can write $n = 6\mu + \nu$, where $\mu \in {\mathbb{N}}\mathop \cup \nolimits \left\{ 0 \right\}$ and $\nu = 1,3,5$. Note that the swap of $\left. {L_{i}^{k} } \right|_{G}$ and $\left. {L_{j}^{k} } \right|_{G}$ for any $i,j \in N$ does not at all affect $s_{1} \left( \cdot \right)$ and $s_{B} \left( \cdot \right)$. If $n = 6\mu + 1$ ($\mu \ge 1$ since $n \ge m = 4)$, let $\left( {{\mathcal{L}}^{\left( 1 \right)} } \right)^{n} \in {\mathcal{L}}^{k} \left[ {L^{0} , \ldots ,L^{k - 1} } \right]$ be defined as: $1 \le i \le \mu \Rightarrow L^{{\left( 1 \right)}_{i}^{k}} :p_{3}$, $\mu + 1 \le i \le 2\mu \Rightarrow L^{{\left( 1 \right)}_{i}^{k}} :p_{4}$, $2\mu + 1 \le i \le 3\mu \Rightarrow L^{{\left( 1 \right)}_{i}^{k}} :p_{5}$, $3\mu + 1 \le i \le 4\mu \Rightarrow L^{{\left( 1 \right)}_{i}^{k}} :p_{1}$, $4\mu + 1 \le i \le 5\mu \Rightarrow L^{{\left( 1 \right)}_{i}^{k}} :p_{2}$, $5\mu + 1 \le i \le 6\mu \Rightarrow L^{{\left( 1 \right)}_{i}^{k}} :p_{6}$, and $i = 6\mu + 1 \Rightarrow L^{{\left( 1 \right)}_{i}^{k}} :p_{1}$. Then, we have $s_{3} \left( {g_{1}^{k} :L^{{\left( 1 \right)}^{k}} } \right) \ge s_{2} \left( {g_{1}^{k} :L^{{\left( 1 \right)}^{k}} } \right) = 3\mu + 2 > 3\mu + 1 = s_{2} \left( {h_{1}^{k} :L^{{\left( 1 \right)}^{k}} } \right) = s_{3} \left( {h_{1}^{k} :L^{{\left( 1 \right)}^{k}} } \right)$. Hence, it follows that $f_{{E_{2} }}^{k + 1} \left( {L^{{\left( 1 \right)}^{k}} } \right) \subseteq G$ and $f_{{E_{3} }}^{k + 1} \left( {L^{{\left( 1 \right)}^{k}} } \right) \subseteq G$. For the other cases of $n = 6\mu + 3$ and $n = 6\mu + 5$, the following $L^{{\left( 2 \right)}^{k}}$ ($g_{3}^{k}$ wins) and $L^{{\left( 3 \right)}^{k}}$ ($g_{1}^{k}$ wins), respectively, gives the corresponding inequalities. $L^{{\left( 2 \right)}^{k}}$ is defined as: $1 \le i \le \mu \Rightarrow p_{4}$, $\mu + 1 \le i \le 2\mu \Rightarrow p_{5}$, $2\mu + 1 \le i \le 3\mu \Rightarrow p_{6}$, $i = 3\mu + 1 \Rightarrow p_{1}$, $3\mu + 2 \le i \le 4\mu + 1 \Rightarrow p_{1}$, $4\mu + 2 \le i \le 5\mu + 1 \Rightarrow p_{2}$, $5\mu + 2 \le i \le 6\mu + 1 \Rightarrow p_{3}$, $i = 6\mu + 2 \Rightarrow p_{2}$, and $i = 6\mu + 3 \Rightarrow p_{3}$. $L^{{\left( 3 \right)}^{k}}$ is defined as follows: $1 \le i \le \mu \Rightarrow p_{2}$, $\mu + 1 \le i \le 2\mu \Rightarrow p_{3}$, $2\mu + 1 \le i \le 3\mu \Rightarrow p_{4}$, $i = 3\mu + 1 \Rightarrow p_{3}$, $i = 3\mu + 2 \Rightarrow p_{4}$, $3\mu + 3 \le i \le 4\mu + 2 \Rightarrow p_{1}$, $4\mu + 3 \le i \le 5\mu + 2 \Rightarrow p_{5}$, $5\mu + 3 \le i \le 6\mu + 2 \Rightarrow p_{6}$, $i = 6\mu + 3 \Rightarrow p_{1}$, and $i = 6\mu + 4 \Rightarrow p_{2}$, and $i = 6\mu + 5 \Rightarrow p_{5}$.

In either case above, at least 2 level-$\left( {k + 1} \right)$ SCRs has class $\left\{ x \right\}$ and the other two have either $\left\{ x \right\}$ or $\left\{ y \right\}$. So, we can apply Lemma 1 to get the weak convergence (if $m = 3$, with Lemma 4 and the technique shown above, we can verify $L^{k} \in {\mathcal{L}}^{k} \left[ {L^{0} , \ldots ,L^{k - 1} } \right]$ such that $f_{{E_{1} }}^{k + 1} \left( {L^{k} } \right) = f_{B}^{k + 1} \left( {L^{k} } \right) = \left\{ {h_{1}^{k} } \right\}$ and $f_{{E_{2} }}^{k + 1} \left( {L^{k} } \right)$ is either $\left\{ {g_{1}^{k} } \right\}$ or $\left\{ {h_{1}^{k} } \right\})$.

Lemma 4.

Let $m = 3$ and $F^{k} = \left\{ {g_{1}^{k} ,g_{2}^{k} ,g_{3}^{k} } \right\}$, where $g_{j}^{k} :\left[ {1,s_{j} ,0} \right]$. Assume $C_{{g_{1}^{k} }} = C_{{g_{2}^{k} }} = \left\{ x \right\}$ and $C_{{g_{3}^{k} }} = \left\{ y \right\}$. Then, there exists $L^{k} \in {\mathcal{L}}^{k} \left[ {L^{0} ,L^{1} , \ldots ,L^{k - 1} } \right]$ such that $\left| {s_{j} \left( {g_{1}^{k} :L^{k} } \right) - s_{j} \left( {g_{2}^{k} :L^{k} } \right)} \right| \le 1$ for all $j = 1,2,3$, where $s_{j} \left( {\:} \right)$ denotes the score evaluated by $g_{j}^{k + 1}$.

Proof of Lemma 4.

Let $A = \left\{ {1,2, \ldots ,a} \right\} = \left\{ {\left. {i \in N} \right| xL_{i}^{0} y} \right\}$. We assume that both a and $n - a$ are odd. The cases where at least one of them is even can be similarly (and more simply) proven. Note that the fact that $C_{{g_{1}^{k} }} = \left\{ x \right\}$ and $C_{{g_{3}^{k} }} = \left\{ y \right\}$ guarantees $a > 0$ and $n - a > 0$. Let $L^{k} \in \left( {{\mathcal{L}}\left( {F^{k} } \right)} \right)^{n}$ be such that $g_{1}^{k} L_{i}^{k} g_{2}^{k} L_{i}^{k} g_{3}^{k}$ for all $i: 1 \le i \le \frac{a}{2} + \frac{1}{2}$, $g_{2}^{k} L_{i}^{k} g_{1}^{k} L_{i}^{k} g_{3}^{k}$ for all $i: 1 \le i \le \frac{a}{2} - \frac{1}{2}$, $g_{3}^{k} L_{i}^{k} g_{2}^{k} L_{i}^{k} g_{1}^{k}$ for all $i: 1 \le i \le \frac{n - a}{2} - \frac{1}{2}$, and $g_{3}^{k} L_{i}^{k} g_{1}^{k} L_{i}^{k} g_{2}^{k}$ for all $i: 1 \le i \le \frac{n - a}{2} + \frac{1}{2}$. Clearly, $L^{k} \in {\mathcal{L}}^{k} \left[ {L^{0} ,L^{1} , \ldots ,L^{k - 1} } \right]$. We have also that

$$ \left| {s\left( {g_{1}^{k} } \right) - s\left( {g_{2}^{k} } \right)} \right| = \left| {\left( {1 - s} \right) - s} \right| = \left| {1-2s} \right|. $$

The assumption of $0 \le s \le 1$ indicates that this absolute value is at most one. ■

Proof of Proposition 1.

Take any distinct $x,y \in X$. Let $A = \left\{ {\left. {i \in N} \right| xL_{i} y} \right\}$ and $\alpha \text{ := }\left| A \right|/n$. The only nontrivial case is such that $g_{1}^{1} \left( {L^{0} } \right) = g_{2}^{1} \left( {L^{0} } \right) = \left\{ x \right\}$ and $g_{3}^{1} \left( {L^{0} } \right) = \left\{ y \right\}$, where $F^{1} = \left\{ {g_{1}^{1} ,g_{2}^{1} ,g_{3}^{1} } \right\}$. Due to Lemma 1, we need only consider $\alpha < 1/2$. Take any $f:\left[ {1,s,0} \right] \in F^{2}$. With Lemma 4, we have the following:

$$ \begin{aligned} & s\left( {g_{3}^{1} :L^{1} } \right) = n - \left| A \right|, \mathop {\hbox{max} }\limits_{{L^{1} \in {\mathcal{L}}\left[ {L^{0} } \right]}} s\left( {g_{1}^{1} :L^{1} } \right) = \left| A \right| + s\left( {n - \left| A \right|} \right) \\ & \mathop {\hbox{min} }\limits_{{L^{1} \in {\mathcal{L}}\left[ {L^{0} } \right]}} \hbox{max} \left\{ {\left\{ {s\left( {g_{1}^{1} :L^{1} } \right),s\left( {g_{2}^{2} :L^{1} } \right)} \right\}} \right\} \le \frac{1}{2}\left\{ {\left| A \right|\left( {1 + s} \right) + \left( {n - \left| A \right|} \right)s} \right\} + \frac{1}{2}. \\ \end{aligned} $$

Therefore, f can choose $\left\{ {g_{1}^{1} } \right\}$ (or $\left\{ {g_{2}^{1} } \right\})$ if and only if

$$ \left| A \right| + s\left( {n - \left| A \right|} \right) > n - \left| A \right| \Leftrightarrow s > \frac{n - 2\left| A \right|}{n - \left| A \right|} = \frac{1-2\alpha }{1 - \alpha } = \varphi \left( \alpha \right). $$

Also, f can choose $\left\{ {g_{3}^{1} } \right\}$ if

$$ \begin{aligned} & \frac{1}{2}\left\{ {\left| A \right|\left( {1 + s} \right) + \left( {n - \left| A \right|} \right)s} \right\} + \frac{1}{2} < n - \left| A \right| \\ & \Leftrightarrow s < 2 - \frac{3\left| A \right|}{n} - \frac{1}{n} = 2-3\alpha - \frac{1}{n}\left( { \to 2-3{\alpha } = \psi \left( \alpha \right) \, {\text{as}}n \to \infty } \right). \\ \end{aligned} $$

If $\alpha < 1/3$, we have $\psi \left( \alpha \right) > 1$. Thus, any scoring SCR $f:\left[ {1,s,0} \right]$ can choose $\left\{ {g_{3}^{1} } \right\}$. If $1/3 < \alpha < 1/2$, we have three cases. (note that events such as $\alpha = 1/3$ or $\psi \left( \alpha \right) - 1/n < s < \psi \left( \alpha \right)$ can be negligible because of Lemma 3).(1) The case of $s_{3} \ge \varphi \left( {1/3} \right) = 1/2.$ Then, each $f_{1}^{2} ,f_{2}^{2} ,f_{3}^{3}$ can exclude $g_{3}^{1}$ for any $\alpha \in (1/3,1/2).$ (2) The case of $s_{3} < \varphi \left( {1/3} \right)$ and $s_{2} \le \psi \left( {\varphi^{ - 1} \left( {s_{3} } \right)} \right)$. Note that the event $\alpha = \varphi^{ - 1} \left( {s_{3} } \right)$ is negligible because of Lemma 3. If $1/3 < \alpha < \varphi^{ - 1} \left( {s_{3} } \right)$, we have $\psi \left( \alpha \right) > s_{2}$, which implies that $L^{1} \in {\mathcal{L}}^{1} \left[ {L^{0} } \right]$ exists such that $f_{2}^{2} \left( {L^{1} } \right) = f_{3}^{2} \left( {L^{1} } \right) = \left\{ {g_{3}^{1} } \right\}$ and $f_{1}^{2} \left( {L^{0} } \right)$ is either $\left\{ {g_{1}^{1} } \right\}$ or $\left\{ {g_{3}^{1} } \right\}$. In either case, with Lemma 1, $L^{0}$ is shown to weakly converge to $\left\{ y \right\}$. If $\varphi^{ - 1} \left( {s_{3} } \right) < \alpha < 1/2$, $L^{1} \in {\mathcal{L}}\left[ {L^{0} } \right]$ exists such that $f_{1}^{2} \left( {L^{1} } \right) = f_{2}^{2} \left( {L^{1} } \right) = f_{3}^{2} \left( {L^{1} } \right) = \left\{ {g_{1}^{1} } \right\}$. (3) The case of $s_{3} < \varphi \left( {1/3} \right)$ and $s_{2} > \psi \left( {\varphi^{ - 1} \left( {s_{3} } \right)} \right)$. In this case, an interval of $\alpha$ (with a positive Lebesgue measure) exists where $f_{1}^{1}$ and $f_{2}^{1}$ necessarily choose $\left\{ {g_{1}^{1} } \right\}$ or $\left\{ {g_{2}^{1} } \right\}$ and $f_{3}^{2}$ necessarily chooses $\left\{ {g_{3}^{1} } \right\}$. If $\alpha$ is in this interval, we cannot solve the regress, because inductively we can show for all $k \ge 3$ that $f_{1}^{k} \left( {L^{k - 1} } \right)$ and $f_{2}^{k} \left( {L^{k - 1} } \right)$ are either $\left\{ {f_{1}^{k - 1} } \right\}$ or $\left\{ {f_{2}^{k - 1} } \right\}$ and $f_{3}^{k} \left( {L^{k - 1} } \right) = \left\{ {f_{3}^{k - 1} } \right\}$. ■

Proof of Corollary 1.

Under IC, trivial deadlock corresponds with cases 1, 2, 9, 10, 11, and 27 in Diss and Merlin [4]. Their Table 7 (p. 302) shows that each probability is $0.00299346$. Therefore, $p_{D} = 0.00299346 \times 6{ \fallingdotseq }1.8{\% }$. Under IAC, trivial deadlock corresponds with the cases 1, 2, 9, 10, 11, and 27 in Diss et al. [3]. Their Table 9 (p. 62) shows that each probability is $1/504$. Therefore, $p_{D} = \left( {1/504} \right) \times 6{ \fallingdotseq }1.2{\% }$. ■

Proof of Proposition 2.

The only nontrivial case is $f_{1}^{1} \left( {L^{0} } \right) = f_{2}^{1} \left( {L^{0} } \right) = \left\{ x \right\}$ and $f_{3}^{1} \left( {L^{0} } \right) = \left\{ y \right\}$, where $F^{1} = \left\{ {f_{1}^{1} ,f_{2}^{1} ,f_{3}^{1} } \right\}$ for distinct $x,y \in X$. Let $A = \left\{ {\left. {i \in N} \right| xL_{i}^{0} y} \right\} = \left\{ {1,2, \ldots ,a} \right\}$. We show that $L^{0}$ strongly converges unless $\alpha$ takes several specific values. The case of $\alpha > 2/3$ or $\alpha < 1/3$ is straightforward. Because the proof is similar, we show for $1/3 < \alpha < 1/2$. To prove the uniqueness of convergence to $\left\{ y \right\}$, we inductively show that for any level $k \ge 2$, $f^{k} \in F^{k}$ exists whose class is $\left\{ y \right\}$. For $k = 2$, it follows that $f_{P}^{2} \left( {L^{1} } \right) = \left\{ {f_{3}^{1} } \right\}$. Assume that the statement holds until $k - 1\left( { \ge 2} \right)$ and $C_{{g_{1}^{k - 1} }} = \left\{ y \right\}$. For the other two rules $g_{2}^{k}$ and $g_{3}^{k}$, the class is either $\left\{ x \right\},\left\{ {x,y} \right\},$ or $\left\{ y \right\}$. Because $g_{2}^{k - 1}$ and $g_{3}^{k - 1}$ are symmetric, there are six possible cases on the combination of $\left( {C_{{g_{1}^{k - 1} }} ,C_{{g_{2}^{k - 1} }} ,C_{{g_{3}^{k - 1} }} } \right)$: Case 1: $\left( {\left\{ y \right\},\left\{ x \right\},\left\{ x \right\}} \right)$, Case 2: $\left( {\left\{ y \right\},\left\{ x \right\},\left\{ {x,y} \right\}} \right)$, Case 3: $\left( {\left\{ y \right\},\left\{ x \right\},\left\{ y \right\}} \right)$, Case 4: $\left( {\left\{ y \right\},\left\{ {x,y} \right\},\left\{ {x,y} \right\}} \right)$, Case 5: $\left( {\left\{ y \right\},\left\{ {x,y} \right\},\left\{ y \right\}} \right)$, and Case 6: $\left( {\left\{ y \right\},\left\{ y \right\},\left\{ y \right\}} \right)$. For each case, we show that at least one of $f_{P}^{k} ,f_{B}^{k} ,f_{A}^{k}$ has class $\left\{ y \right\}$. For cases 1, 3, and 6, this is obvious. For case 2, ${\mathcal{L}}^{k - 1} \left[ {L^{0} , \ldots ,L^{k - 2} } \right]$ is a singleton: $L_{i}^{k - 1} : f_{3}^{k - 1} f_{2}^{k - 1} f_{1}^{k - 1}$ for all $i \in A$ and $L_{i}^{k - 1} :f_{1}^{k - 1} f_{3}^{k - 1} f_{2}^{k - 1}$ for all $i \notin A$. Because $a < n/2$, we have $f_{P}^{k} \left( {L^{k - 1} } \right) = \left\{ {f_{1}^{k - 1} } \right\}$, which means $C_{{f_{P}^{k} }} = \left\{ y \right\}$. Case 4 is similarly shown. For case 5, we have $f_{A}^{k} \left( {L^{k - 1} } \right) \subseteq \left\{ {f_{1}^{k - 1} ,f_{3}^{k - 1} } \right\}$ for all $L^{k - 1} \in {\mathcal{L}}^{k - 1} \left[ {L^{0} , \ldots ,L^{k - 1} } \right]$. ■

Sketch of the proof that $\left\{ {\varvec{f}_{{\varvec{E}_{1} }} ,\varvec{f}_{{\varvec{E}_{2} }} ,\varvec{f}_{{\varvec{E}_{3} }} ,\varvec{f}_{\varvec{B}} } \right\}$ satisfies $\varvec{p}_{{\varvec{WC}}} \approx {\varvec{1}} - \varvec{p}_{\varvec{D}}$ under EU and IAC.

Because of Lemma 1 and Lemma 2, the only nontrivial case is $f_{1}^{1} \left( {L^{0} } \right) = f_{2}^{1} \left( {L^{0} } \right) = \left\{ {x_{1} } \right\}$, $f_{3}^{1} \left( {L^{0} } \right) = \left\{ {x_{2} } \right\}$, and $f_{4}^{1} \left( {L^{0} } \right) = \left\{ {x_{3} } \right\}$. If $f_{1}^{k} ,f_{2}^{k} ,f_{3}^{k} ,f_{4}^{k}$ can drop $x_{j} \in X$ at some $k \in {\mathbb{N}}$, the proof is similar to $m = 3$ (using EU). Otherwise, for each $x = x_{1} ,x_{2} ,x_{3}$, at least one $f_{x}^{k} \in F^{k}$ exists such that $x \in f_{x}^{k} \left( {L^{k - 1} } \right)$ for all $L^{k - 1} \in {\mathcal{L}}^{k - 1} \left[{L^{0} , \ldots ,L^{k - 2} } \right]$ … $\left({\star } \right)$. Since ties between $f_{3}^{1}$ and $f_{4}^{1}$ are negligible (when $n \to \infty$), each $f_{x}^{k}$ is assumed to be distinct. Furthermore, at least one individual is expected to exist who ranks $x_{j}$ last. Then, $f_{A}$ cannot be a $f_{x}$. Therefore, combinations of $\left({f_{{x_{1} }}^{k} ,f_{{x_{2} }}^{k} ,f_{{x_{3} }}^{k} } \right)$ are the permutations of $f_{{E_{1} }} ,f_{{E_{2} }} ,f_{B}$. For each combination, we obtain a linear system of inequalities on the number of individuals who have specific preferences on $\left\{{x_{1} ,x_{2} ,x_{3} } \right\}$ (considering $k = 2,3)$. With Fourier-Motzkin elimination, we can find that at no case does $\left({\star} \right)$ occur. ■