The superdominance relation,the positional winner,and more missing links between Borda and Condorcet

Abstract

The field of social choice dates back to the eighteenth century, when Borda and Condorcet started a never-ending discussion about the use of either positional or pairwise information. Three centuries later, after countless axiomatic characterizations of voting rules, impossibility theorems and many other study subjects, researchers still debate whether positional information is really sensitive to manipulation or pairwise information disregards the transitivity of voters’ preferences. In a previous paper, we introduced the notions of supercovering relation and pairwise winner, which resulted in a meeting point for both points of view of the theory of social choice. In this paper, we continue this direction and propose the notions of superdominance relation and positional winner that will prove to be the alter egos of the supercovering relation and the pairwise winner when positional information (rather than pairwise information) is considered. Moreover, we analyse a new interesting choice set: the unsuperdominated set.

Keywords

Positional winner scorix superdominance relation votrix unsuperdominated set

1. Introduction

Back in the eighteenth century, Borda (1781) and Condorcet (1785) proposed two points of view of the theory of social choice based on the use of positional information and pairwise information, respectively. Although the two approaches may comply with each other in most cases, one could easily find examples in which they differ significantly. For instance, consider the example in which 101 voters are asked to rank four candidates – say a, b, c and d– resulting in 51 voters expressing the ranking $a ≻ b ≻ c ≻ d$ and 50 voters expressing the ranking $b ≻ c ≻ d ≻ a$ . According to the philosophy advocated by Borda, candidate b should be considered the best candidate since almost half of the number of voters consider b to be the best candidate, while the other voters consider b to be the second best candidate. Candidate a is here ‘penalized’ for being considered the worst candidate by almost half of the number of voters. However, candidate a is considered better than any other candidate by more than half of the number of voters, and, thus, according to the philosophy advocated by Condorcet, candidate a should be considered the best candidate.

In a previous paper (Pérez-Fernández and De Baets, 2018), we advocated that this disagreement arises because Condorcet’s proposal overlooks the transitivity of the rankings of the voters. Thus, we introduced a new way of comparing candidates based on pairwise information – the supercovering relation – and proved this relation to be a meeting point for the works of Borda and Condorcet. A new type of winner emerged, the pairwise winner, which is a candidate that supercovers all other candidates and assures both the Borda winner and the Condorcet winner to exist, and more importantly, to agree. In this paper, we introduce another way of comparing candidates based on positional information – the superdominance relation – that will also be proven to be a meeting point for the works of Borda and Condorcet. Similarly, another type of winner will emerge, the positional winner (a candidate that superdominates all other candidates), assuring again both the Borda winner and the Condorcet winner to exist and to agree.

Finally, we will propose a new choice set – the unsuperdominated set – that, like the unsupercovered set (Pérez-Fernández and De Baets, 2018) and unlike any choice set contained in the Smith set (Good, 1971; Smith, 1973)¹, does not need to reduce to the Condorcet winner in the case where it exists. Although this might seem controversial at first (and might go against the major part of the most recent research in the field), all these sets contained in the Smith set might be at least questionable for some examples (such as the one in the first paragraph of this introduction), even though they have actually been criticized for being rather large in the case where the Condorcet winner does not exist (Dutta, 1988).

The rest of the paper is organized as follows. We introduce the superdominance relation in Section 2. This superdominance relation is used to define the positional winner in Section 3 and the unsuperdominated set in Section 4. We round up with some conclusions and a brief discussion on open problems in Section 5.

2. The superdominance relation

In this paper, a set $C = {a_{1}, \dots, a_{k}}$ of k candidates is considered, and r voters are asked to compare the candidates. Each comparison is expressed as a strict linear order or ranking $≻_{j}$ on $C$ , that is, the asymmetric part of a total order $⪰_{j}$ on $C$ . This list of r rankings is called a profile of rankings and is denoted by $R = (≻_{j})_{j = 1}^{r}$ . The position at which candidate $a_{i}$ is ranked in ranking $≻_{j}$ is denoted by $P_{j} (a_{i})$ .

The matrix of which the element at the i-th row and the $ℓ$ -th column equals the number of times that the i-th candidate is ranked at the $ℓ$ -th position is called the scorix induced by the profile of rankings given by the voters (Pérez-Fernández et al., 2016b).

Definition 1. Let $C$ be a set of candidates and $R$ be the profile of r rankings on $C$ given by the voters. The matrix $S \in {0, 1, \dots, r}^{k \times k}$ defined as

S_{i ℓ} = # {j \in {1, \dots, r} | P_{j} (a_{i}) = ℓ}

for any $a_{i} \in C$ and any $ℓ \in {1, \dots, k}$ , is called the scorix induced by $R$ .

Note that the term scorix is a contraction of the commonly-used term ‘scoring matrix’ (Fine and Fine, 1974; Saari, 2000; Stein et al., 1994; Young, 1975), usually considered either in the form of a matrix or in the form of a list of vectors corresponding to the different rows of the scorix.

For any scorix S, the i-th row $(i \in {1, \dots, k})$ is called the vector of positions of candidate $a_{i}$ and is denoted by $S_{i}$ . Note that, for any $i \in {1, \dots, k}$ , it holds that $S_{i} \in {0, 1, \dots, r}^{k}$ .

If we consider a subset of the set of candidates, the given profile of rankings is unequivocally reduced to another profile of rankings on said subset. Formally, for any non-empty subset $C' \subseteq C$ , the restriction of $R$ to $C'$ is the profile $R' = (≻'_{j})_{j = 1}^{r}$ of r rankings on $C'$ such that, for any $j \in {1, \dots, r}$ and any $a_{i_{1}}, a_{i_{2}} \in C'$ , it holds that $a_{i_{1}} ≻'_{j} a_{i_{2}}$ if $a_{i_{1}} ≻_{j} a_{i_{2}}$ . A matrix is then said to be a sub-scorix of a scorix if it is the scorix associated with the restriction of the given profile of rankings to some subset of the set of candidates (Pérez-Fernández and De Baets, 2017).

Definition 2. Let $C$ be a set of k candidates, $R$ be the profile of r rankings on $C$ given by the voters and S be the scorix induced by $R$ . For any non-empty subset $C' \subseteq C$ , the scorix $S' \in {0, 1, \dots, r}^{k' \times k'}$ (where $k' = | C' |$ ) on $C'$ induced by the restriction of $R$ to $C'$ is called the sub-scorix of S on $C'$ .

In the case where the vector of positions of a candidate dominates the vector of positions of another candidate, the former candidate will always be ranked at a better position than the latter one by any scoring rule. This dominance relation is usually called the Borda dominance relation (Fishburn, 1974).

Definition 3. Let $C$ be a set of k candidates, $R$ be the profile of r rankings on $C$ given by the voters and S be the scorix induced by $R$ . For any $a_{i_{1}}, a_{i_{2}} \in C$ , $a_{i_{1}}$ is said to Borda-dominate $a_{i_{2}}$ , denoted by $a_{i_{1}} ⋗_{S} a_{i_{2}}$ , if, for any $t \in {1, \dots, k}$ , it holds that

\sum_{ℓ = 1}^{t} S_{i_{1} ℓ} \geq \sum_{ℓ = 1}^{t} S_{i_{2} ℓ}

the inequality being strict for at least one t.

If a candidate $a_{i_{1}}$ Borda-dominates a candidate $a_{i_{2}}$ , then we also say that the vector of positions of $a_{i_{1}}$ dominates the vector of positions of $a_{i_{2}}$ .

Next, we propose a natural relation based on the notions of Borda dominance and sub-scorix: the superdominance relation.

Definition 4. Let $C$ be a set of k candidates, $R$ be the profile of r rankings on $C$ given by the voters and S be the scorix induced by $R$ . For any $a_{i_{1}}, a_{i_{2}} \in C$ , $a_{i_{1}}$ is said to superdominate $a_{i_{2}}$ , denoted by $a_{i_{1}} ⋗ a_{i_{2}}$ , if, for any non-empty subset $C' \subseteq C$ such that $a_{i_{1}}, a_{i_{2}} \in C'$ and associated sub-scorix $S'$ of S on $C'$ , it holds that $a_{i_{1}} ⋗_{S'} a_{i_{2}}$ .

Obviously, the superdominance relation is included in the Borda dominance relation.

Proposition 1. Let $C$ be a set of k candidates, $R$ be the profile of r rankings on $C$ given by the voters and S be the scorix induced by $R$ . For any $a_{i_{1}}, a_{i_{2}} \in C$ , it holds that $a_{i_{1}} ⋗ a_{i_{2}}$ implies $a_{i_{1}} ⋗_{S} a_{i_{2}}$ .

Although the Borda dominance relation is known to be a strict order relation, the superdominance relation does not need to be transitive. Fortunately, the superdominance relation holds some interesting properties due to the fact that it is included in a strict order relation.

Proposition 2. Let $C$ be a set of k candidates, $R$ be the profile of r rankings on $C$ given by the voters and S be the scorix induced by $R$ . The relation ⋗ is irreflexive, antisymmetric and acyclic.

The preceding definitions are illustrated in the following example.

Example 1. Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings $R = (≻_{i})_{i = 1}^{10}$ provided by ten voters shown in Table 1.

Table 1.

Frequency of the rankings on $C$ = {a, b, c, d} expressed by ten voters.

$# ≻_{i}$	Rankings on $C$
4	$a ≻ b ≻ d ≻ c$
3	$b ≻ c ≻ a ≻ d$
3	$c ≻ a ≻ d ≻ b$

The scorix induced by $R$ is given by²

S = (\begin{matrix} 4 & 3 & 3 & 0 \\ 3 & 4 & 0 & 3 \\ 3 & 3 & 0 & 4 \\ 0 & 0 & 7 & 3 \end{matrix})

Note that, for instance, considering candidates a and d, it holds that

\begin{matrix} 4 = S_{11} > S_{41} = 0, \\ 7 = S_{11} + S_{12} > S_{41} + S_{42} = 0, \\ 10 = S_{11} + S_{12} + S_{13} > S_{41} + S_{42} + S_{43} = 7 \end{matrix}

Thus, it holds that $a ⋗_{S} d$ . In general, $⋗_{S}$ is given by

⋗_{S} = {(a, b), (a, c), (a, d), (b, c), (b, d)}

All the possible (proper) subsets of $C$ containing both a and d are ${a, b, d}$ , ${a, c, d}$ and ${a, d}$ . The corresponding sub-scorices of S on these subsets are the following

\begin{matrix} S^{abd} = (\begin{matrix} 7 & 3 & 0 \\ 3 & 4 & 3 \\ 0 & 3 & 7 \end{matrix}), \\ S^{acd} = (\begin{matrix} 4 & 6 & 0 \\ 6 & 0 & 4 \\ 0 & 4 & 6 \end{matrix}), \\ S^{ad} = (\begin{matrix} 10 & 0 \\ 0 & 10 \end{matrix}) \end{matrix}

Note that it holds that

\begin{matrix} 7 = S_{11}^{abd} > S_{31}^{abd} = 0, \\ 10 = S_{11}^{abd} + S_{12}^{abd} > S_{31}^{abd} + S_{32}^{abd} = 3, \\ 4 = S_{11}^{acd} > S_{31}^{acd} = 0, \\ 10 = S_{11}^{acd} + S_{12}^{acd} > S_{31}^{acd} + S_{32}^{acd} = 4, \\ 10 = S_{11}^{ad} > S_{21}^{ad} = 0 \end{matrix}

Thus, it holds that $a ⋗ d$ . Note that it does not hold that $a ⋗ c$ , since $4 = S_{11}^{acd} < S_{21}^{acd} = 6$ . In general, ⋗ is given by

⋗ = {(a, b), (a, d), (b, c), (b, d)}

Obviously, it holds that $⋗ \subseteq ⋗_{S}$ . Also, it is clear that ⋗ is not transitive.

The matrix of which the element at the $i_{1}$ -th row and the $i_{2}$ -th column equals the strength of support of the $i_{1}$ -th candidate over the $i_{2}$ -th candidate is called the votrix induced by the profile of rankings given by the voters (Pérez-Fernández et al., 2016a).

Definition 5. Let $C$ be a set of k candidates and $R$ be the profile of r rankings on $C$ given by the voters. The matrix $V \in {0, 1, \dots, r}^{k \times k}$ defined as

V_{i_{1} i_{2}} = # {j \in {1, \dots, r} | a_{i_{1}} ≻_{j} a_{i_{2}}}

for any $a_{i_{1}}, a_{i_{2}} \in C$ , is called the votrix induced by $R$ .

Note that the term votrix is a contraction of the commonly-used term ‘voting matrix’ (Black, 1958; Young, 1988).

The votrix is used for defining one of the most studied concepts in social choice theory: the notion of simple majority (Inada, 1969; May, 1952; Sen, 1966). A candidate is said to dominate (or to beat by simple majority) another candidate if the number of voters who prefer the first candidate to the second candidate is greater than the number of voters who prefer the second candidate to the first candidate. This relation is known to potentially be cyclic (the famous voting paradox).

Definition 6. Let $C$ be a set of k candidates, $R$ be the profile of r rankings on $C$ given by the voters and V be the votrix induced by $R$ . For any $a_{i_{1}}, a_{i_{2}} \in C$ , $a_{i_{1}}$ is said to dominate $a_{i_{2}}$ , denoted by $a_{i_{1}} ≻ a_{i_{2}}$ , if it holds that $V_{i_{1} i_{2}} > V_{i_{2} i_{1}}$ .

Note that the superdominance relation further restricts the dominance relation,³ thereby justifying its name.

Proposition 3. Let $C$ be a set of k candidates and $R$ be the profile of r rankings on $C$ given by the voters. For any $a_{i_{1}}, a_{i_{2}} \in C$ , it holds that $a_{i_{1}} ⋗ a_{i_{2}}$ implies $a_{i_{1}} ≻ a_{i_{2}}$ .

Proof. The result immediately follows by considering the sub-scorix $S'$ associated with the restriction of the profile to the subset $C' = {a_{i_{1}}, a_{i_{2}}}$ and the fact that, in such case, $S'_{i_{1} 1} = V_{i_{1} i_{2}}$ and $S'_{i_{2} 1} = V_{i_{2} i_{1}}$ .□

Other interesting relations between candidates are the covering relation (Miller, 1980) and the supercovering relation (Pérez-Fernández and De Baets, 2018).

Definition 7. Let $C$ be a set of k candidates and $R$ be the profile of r rankings on $C$ given by the voters. For any $a_{i_{1}}, a_{i_{2}} \in C$ , $a_{i_{1}}$ is said to cover $a_{i_{2}}$ , denoted by $a_{i_{1}} >> a_{i_{2}}$ , if the following conditions hold:

$V_{i_{1} i_{2}} > V_{i_{2} i_{1}}$ ,

$V_{i_{2} ℓ} > V_{ℓ i_{2}}$ implies $V_{i_{1} ℓ} > V_{ℓ i_{1}}$ , for any $a_{ℓ} \in C \ {a_{i_{1}}, a_{i_{2}}}$ .

Definition 8. Let $C$ be a set of k candidates and $R$ be the profile of r rankings on $C$ given by the voters. For any $a_{i_{1}}, a_{i_{2}} \in C$ , $a_{i_{1}}$ is said to supercover $a_{i_{2}}$ , denoted by $a_{i_{1}} \cdot >> a_{i_{2}}$ , if the following conditions hold:

$V_{i_{1} i_{2}} > V_{i_{2} i_{1}}$ ,

$V_{i_{1} ℓ} \geq V_{i_{2} ℓ}$ , for any $a_{ℓ} \in C \ {a_{i_{1}}, a_{i_{2}}}$ ,

$V_{ℓ i_{1}} \leq V_{ℓ i_{2}}$ , for any $a_{ℓ} \in C \ {a_{i_{1}}, a_{i_{2}}}$ .⁴

Example 2. Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings $R = (≻_{i})_{i = 1}^{10}$ from Example 1. The votrix induced by $R$ is given by

V = (\begin{matrix} 0 & 7 & 4 & 10 \\ 3 & 0 & 7 & 7 \\ 6 & 3 & 0 & 6 \\ 0 & 3 & 4 & 0 \end{matrix})

Note that, for instance, considering candidates a and d, it holds that

10 = V_{14} > V_{41} = 0

Thus, it holds that $a ≻ d$ . In general, ≻ is given by

≻ = {(a, b), (a, d), (b, c), (b, d), (c, a), (c, d)}

Note that ⋗ is included in ≻, but $⋗_{S}$ is not. Also, we can see that ≻ is not transitive (it is actually cyclic).

Since candidate a dominates candidate d and also dominates all the candidates dominated by d (actually, d does not dominate any other candidate), it holds that $a >> d$ . In general, >>is given by

>> = {(a, d), (b, d), (c, d)}

We can also see that

\begin{matrix} 10 = V_{14} > V_{41} = 0, \\ 7 = V_{12} \geq V_{42} = 3, \\ 4 = V_{13} \geq V_{43} = 4 \end{matrix}

Thus, it holds that $a \cdot >> d$ . In general, ·>> is given by

⋗ > = {(a, d), (b, d), (c, d)}

Note that none of the relations >> and ·>> is included or includes the relation ⋗ or the relation $⋗_{S}$ .

From the preceding example, we conclude that, although both the covering relation and the supercovering relation are also included in the dominance relation, there is no immediate relation between both relations and the superdominance relation.

Figure 1 displays the relation between the different types of relation on $C$ analysed in this section. In this figure, an arrow indicates that the relation from which the arrow starts includes the relation to which the arrow points.

Figure 1.

Relation between the different types of relation on $C$ .

3. The positional winner

A unanimous winner (Arrow et al., 2002) is a candidate that is considered the best by all the voters. In case such candidate exists, it is the obvious unique winner of the election.

Definition 9. Let $C$ be a set of k candidates, $R$ be the profile of r rankings on $C$ given by the voters and V be the votrix induced by $R$ . A candidate $a_{i_{1}}$ is called the unanimous winner if, for any other candidate $a_{i_{2}} \in C \ {a_{i_{1}}}$ , it holds that $V_{i_{1} i_{2}} = r$ .

Unfortunately, the unanimous winner rarely exists since voters tend to disagree on their preferences. The requirement of all voters to agree is often softened by requiring only more than half of the voters to agree, resulting in the majority winner (Nurmi, 1987).

Definition 10. Let $C$ be a set of k candidates and $R$ be the profile of r rankings on $C$ given by the voters. A candidate $a_{i_{1}}$ is called the majority winner if it holds that $# {j \in {1, \dots, r} | (\forall a_{i_{2}} \in C \ {a_{i_{1}}}) (a_{i_{1}} ≻_{j} a_{i_{2}})} > \frac{r}{2}$ .

However, although the majority winner is a notion weaker than the unanimous winner, it usually does not exist either in real-life situations. A notion weaker than the majority winner is due to Condorcet (1785). He proposed a new type of winner based on the notion of dominance: if a candidate dominates all other candidates, then it should be considered the winner.

Definition 11. Let $C$ be a set of k candidates and $R$ be the profile of r rankings on $C$ given by the voters. A candidate $a_{i_{1}}$ is called the Condorcet winner if, for any other candidate $a_{i_{2}} \in C \ {a_{i_{1}}}$ , it holds that $a_{i_{1}} ≻ a_{i_{2}}$ .

Another point of view than the one proposed by Condorcet is that of Borda (1781), who proposed instead to exploit the positions at which every candidate is ranked. He proposed introducing a score measuring the number of times that each candidate is preferred to another candidate, and select as the winner the candidate that maximizes this score. Formally, the Borda score of a candidate $a_{i}$ is defined as $B (a_{i}) = \sum_{a_{ℓ} \in C \ {a_{i}}} V_{i ℓ}$ .

Definition 12. Let $C$ be a set of k candidates and $R$ be the profile of r rankings on $C$ given by the voters. A candidate $a_{i_{1}}$ is called the Borda winner ⁵ if, for any other candidate $a_{i_{2}} \in C \ {a_{i_{1}}}$ , it holds that $B (a_{i_{1}}) > B (a_{i_{2}})$ .

Both the Condorcet and the Borda winners have equally attracted the interest (and the criticism) of the scientific community. Note that, when a voter expresses the ranking $a ≻ b ≻ c$ , it indicates that the voter has a stronger preference for a over c than for both a over b and b over c (something Borda takes account of and Condorcet ignores), but it does not imply that said voter has a stronger preference for a over c than a second voter expressing the ranking $a ≻ c ≻ b$ (something that Borda presumes and Condorcet does not).

In a previous paper, we proposed a natural link between the Borda winner and the Condorcet winner – the pairwise winner – which is a candidate that supercovers any other candidate (Pérez-Fernández and De Baets, 2018).

Definition 13. Let $C$ be a set of k candidates and $R$ be the profile of r rankings on $C$ given by the voters. A candidate $a_{i_{1}}$ is called the pairwise winner if, for any other candidate $a_{i_{2}} \in C \ {a_{i_{1}}}$ , it holds that $a_{i_{1}} \cdot >> a_{i_{2}}$ .

A candidate that Borda-dominates all other candidates has been frequently analysed in the field of social choice (Saari, 2000). As pointed out by Llamazares and Peña (2015), this candidate turns out to be the winning candidate for all scoring rules (Fishburn, 1973; Moulin, 1983). However, to the best of our knowledge, this candidate has not been given a name yet. We propose the term quasi-positional winner for referring to such a candidate, and also introduce a new type of winner – the positional winner – for referring to a candidate that superdominates all other candidates.

Definition 14. Let $C$ be a set of k candidates, $R$ be the profile of r rankings on $C$ given by the voters and S be the scorix induced by $R$ .

A candidate $a_{i_{1}}$ is called the quasi-positional winner if, for any other candidate $a_{i_{2}} \in C \ {a_{i_{1}}}$ , it holds that $a_{i_{1}} ⋗_{S} a_{i_{2}}$ .

A candidate $a_{i_{1}}$ is called the positional winner if, for any other candidate $a_{i_{2}} \in C \ {a_{i_{1}}}$ , it holds that $a_{i_{1}} ⋗ a_{i_{2}}$ .

It is known that the unanimous winner, the majority winner, the Borda winner, the Condorcet winner and the pairwise winner are not assured to exist but, if they do exist, they are assured to be unique. Note that this is also the case for the quasi-positional winner and the positional winner.

Proposition 4. Let $C$ be a set of k candidates and $R$ be the profile of r rankings on $C$ given by the voters.

A quasi-positional winner might not exist, but if a quasi-positional winner exists, then it is unique.

A positional winner might not exist, but if a positional winner exists, then it is unique.

Proof. For proving that both a quasi-positional winner and a positional winner might not exist, we provide an illustrative example. Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 2. Clearly, neither a quasi-positional winner nor a positional winner exists.

Table 2.

Frequency of the rankings on $C = {a, b, c, d}$ expressed by 101 voters.

$# ≻_{i}$	Rankings on $C$
51	$a ≻ b ≻ c ≻ d$
50	$b ≻ c ≻ d ≻ a$

Suppose that there exist two quasi-positional winners $a_{i_{1}}$ and $a_{i_{2}}$ . By definition, it holds that

\sum_{ℓ = 1}^{t} S_{i_{1} ℓ} \geq \sum_{ℓ = 1}^{t} S_{i_{2} ℓ}

and

\sum_{ℓ = 1}^{t'} S_{i_{2} ℓ} \geq \sum_{ℓ = 1}^{t'} S_{i_{1} ℓ}

for all $t, t' \in {1, \dots, n}$ , the inequalities being strict for at least one t and one $t'$ . This results in a contradiction. The same reasoning leads to the uniqueness of the positional winner. □

In the following two theorems, we position the quasi-positional winner and the positional winner among all other types of winner mentioned in this paper.

Theorem 1. Let $C$ be a set of k candidates and $R$ be the profile of r rankings on $C$ given by the voters.

If the unanimous winner exists, then the quasi-positional winner exists and it coincides with the unanimous winner. However, if the quasi-positional winner exists, then the unanimous winner might not exist.

If the quasi-positional winner exists, then the Borda winner exists and it coincides with the quasi-positional winner. However, if the Borda winner exists, then the quasi-positional winner might not exist.

If the quasi-positional winner exists, then the Condorcet winner might not exist. Similarly, if the Condorcet winner exists, then the quasi-positional winner might not exist. Actually, if both the Condorcet winner and the quasi-positional winner exist, then they do not need to coincide.

If the quasi-positional winner exists, then the majority winner might not exist. Similarly, if the majority winner exists, then the quasi-positional winner might not exist. However, if both the majority winner and the quasi-positional winner exist, then they coincide.

If the quasi-positional winner exists, then the pairwise winner might not exist. Similarly, if the pairwise winner exists, then the quasi-positional winner might not exist. However, if both the pairwise winner and the quasi-positional winner exist, then they coincide.

Proof.

(i) (a) If a candidate $a_{i_{1}}$ is the unanimous winner, then it is ranked at the first position by every voter. For any other candidate $a_{i_{2}} \in C \ {a_{i_{1}}}$ , it trivially holds that $r = S_{i_{1} 1} > S_{i_{2} 1} = 0$ . Furthermore, for any $ℓ \in {2, \dots, k}$ , it holds that $r = \sum_{j = 1}^{ℓ} S_{i_{1} ℓ} \geq \sum_{j = 1}^{ℓ} S_{i_{2} ℓ}$ . Thus, for any other candidate $a_{i_{2}} \in C \ {a_{i_{1}}}$ , it holds that $a_{i_{1}} ⋗_{S} a_{i_{2}}$ . Therefore, if the unanimous winner $a_{i_{1}}$ exists, then the quasi-positional winner exists and it coincides with $a_{i_{1}}$ .

(b) Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 1. Candidate a is the quasi-positional winner, but the unanimous winner does not exist.

(ii) (a) If the quasi-positional winner exists, then it is the winning candidate for all the scoring rules (Llamazares and Peña, 2015), and, therefore, it is the Borda winner.

(b) Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 2. Candidate b is the Borda winner, but the quasi-positional winner does not exist.

(iii) (a) Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 1. Candidate a is the quasi-positional winner, but the Condorcet winner does not exist.

(b) Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 2. Candidate a is the Condorcet winner, but the quasi-positional winner does not exist.

(c) Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 3. Candidate a is the quasi-positional winner and candidate b is the Condorcet winner.

(iv) (a) Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 1. Candidate a is the quasi-positional winner, but the majority winner does not exist.

(b) Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 2. Candidate a is the majority winner, but the quasi-positional winner does not exist.

(c) Note that if the majority winner exists, then the first component of the vector of positions of this candidate needs to be greater than half of the number of voters. Therefore, this vector of positions cannot be dominated by any other vector of positions. We conclude that, if the quasi-positional winner also exists, then the majority winner and the quasi-positional winner coincide.

(v) (a) Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 1. Candidate a is the quasi-positional winner, but the pairwise winner does not exist.

(b) Consider the set of candidates $C = {a, b, c}$ and the profile of rankings shown in Table 4. Candidate a is the pairwise winner, but the quasi-positional winner does not exist.

(c) As a result of (iii), we know that, if the quasi-positional winner exists, then the Borda winner exists and it coincides with the quasi-positional winner. As proved in Pérez-Fernandez and De Baets (2018), we know that, if the pairwise winner exists, then the Borda winner exists and it coincides with the pairwise winner. We conclude that, if both the quasi-positional winner and the pairwise winner exist, then the Borda winner exists and all three need to coincide.□

Table 3.

Frequency of the rankings on $C = {a, b, c, d}$ expressed by ten voters.

$# ≻_{i}$	Rankings on $C$
4	$a ≻ c ≻ b ≻ d$
3	$b ≻ a ≻ c ≻ d$
3	$d ≻ b ≻ a ≻ c$

Table 4.

Frequency of the rankings on $C = {a, b, c}$ expressed by ten voters.

$# ≻_{i}$	Rankings on $C$
4	$b ≻ a ≻ c$
3	$a ≻ c ≻ b$
3	$c ≻ a ≻ b$

Theorem 2. Let $C$ be a set of k candidates and $R$ be the profile of r rankings on $C$ given by the voters.

If the unanimous winner exists, then the positional winner exists and it coincides with the unanimous winner. However, if the positional winner exists, then the unanimous winner might not exist.

If the positional winner exists, then the quasi-positional winner exists and it coincides with the positional winner. However, if the quasi-positional winner exists, then the positional winner might not exist.

If the positional winner exists, then the Borda winner exists and it coincides with the positional winner. However, if the Borda winner exists, then the positional winner might not exist.

If the positional winner exists, then the Condorcet winner exists and it coincides with the positional winner. However, if the Condorcet winner exists, then the positional winner might not exist.

If the positional winner exists, then the majority winner might not exist. Similarly, if the majority winner exists, then the positional winner might not exist. However, if both the majority winner and the positional winner exist, then they coincide.

If the positional winner exists, then the pairwise winner might not exist. Similarly, if the pairwise winner exists, then the positional winner might not exist. However, if both the pairwise winner and the positional winner exist, then they coincide.

Proof. (i) (a) If a candidate $a_{i_{1}}$ is the unanimous winner, then it is ranked at the first position by every voter. For any other candidate $a_{i_{2}} \in C \ {a_{i_{1}}}$ , it trivially holds that $r = S_{i_{1} 1} > S_{i_{2} 1} = 0$ . Furthermore, for any $ℓ \in {2, \dots, k}$ , it holds that $r = \sum_{j = 1}^{ℓ} S_{i_{1} ℓ} \geq \sum_{j = 1}^{ℓ} S_{i_{2} ℓ}$ . This result trivially holds for any sub-scorix of S on any subset of the set of candidates containing $a_{i_{1}}$ and $a_{i_{2}}$ . Thus, for any other candidate $a_{i_{2}} \in C \ {a_{i_{1}}}$ , it holds that $a_{i_{1}} ⋗ a_{i_{2}}$ . Therefore, if the unanimous winner $a_{i_{1}}$ exists, then the positional winner exists and it coincides with $a_{i_{1}}$ .

(b) Consider the set of candidates $C = {a, b, c}$ and the profile of rankings shown in Table 5. Candidate a is the positional winner, but the unanimous winner does not exist.

Table 5.

Frequency of the rankings on $C = {a, b, c}$ expressed by ten voters.

$# ≻_{i}$	Rankings on $C$
5	$a ≻ b ≻ c$
2	$b ≻ c ≻ a$
2	$c ≻ a ≻ b$
1	$b ≻ a ≻ c$

(ii) (a) The result trivially follows from Proposition 1.

(b) Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 1. Candidate a is the quasi-positional winner, but the positional winner does not exist.

(iii) (a) The result trivially follows from (ii) and Theorem 1 (ii).

(b) Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 2. Candidate b is the Borda winner, but the positional winner does not exist.

(iv) (a) The result trivially follows from Proposition 3.

(b) Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 2. Candidate a is the Condorcet winner, but the positional winner does not exist.

(v) (a) Consider the set of candidates $C = {a, b, c}$ and the profile of rankings shown in Table 5. Candidate a is the positional winner, but the majority winner does not exist.

(b) Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 2. Candidate a is the majority winner, but the positional winner does not exist.

(c) Note that if the majority winner exists, then it coincides with the Condorcet winner. As a result of (iv), if the positional winner exists, then it coincides with the Condorcer winner. We conclude that, if both the majority winner and the quasi-positional winner exist, then they coincide.

(vi) (a) Consider the set of candidates $C = {a, b, c}$ and the profile of rankings shown in Table 5. Candidate a is the positional winner, but the pairwise winner does not exist.

(b) Consider the set of candidates $C = {a, b, c}$ and the profile of rankings shown in Table 4. Candidate a is the pairwise winner, but the positional winner does not exist.

(c) As a result of (ii) and (iii), we know that, if the positional winner exists, then the Borda winner exists and it coincides with the positional winner. As proved in Pérez-Fernández and De Baets (2018), we know that, if the pairwise winner exists, then the Borda winner exists and it coincides with the pairwise winner. We conclude that, if both the positional winner and the pairwise winner exist, then the Borda winner exists and all three need to coincide.□

Figure 2 displays the relation between the different types of winner analysed in this section. In this figure, an arrow indicates that, if the winner from which the arrow starts exists, then the winner to which the arrow points also exists and it coincides with the former.

Figure 2.

Relation between the different types of winner.

4. The unsuperdominated set

As discussed in the preceding section, all these types of winner might not exist in a real-life situation. In such case, it is common to define choice sets (Brandt et al., 2009) and restrict the choice of the best candidate to that choice set. In this section, we introduce the unsuperdominated set, that is, the set of all candidates for which there exists no candidate superdominating them.

Definition 15. Let $C$ be a set of k candidates and $R$ be the profile of r rankings on $C$ given by the voters. The unsuperdominated set is the subset $U_{⋗}$ of $C$ defined as

U_{⋗} = {a_{i_{1}} \in C | (∄ a_{i_{2}} \in C) (a_{i_{2}} ⋗ a_{i_{1}})}

Since the superdominance relation is acyclic and the set of candidates is finite, there always exists at least one candidate that belongs to the unsuperdominated set.

Proposition 5. Let $C$ be a set of k candidates, $R$ be the profile of r rankings on $C$ given by the voters and $U_{⋗}$ be the unsuperdominated set. It holds that $U_{⋗} \neq \emptyset$ .

All types of winner recalled in the preceding section belong to the unsuperdominated set in the event that they exist.

Proposition 6. Let $C$ be a set of k candidates, $R$ be the profile of r rankings on $C$ given by the voters and $U_{⋗}$ be the unsuperdominated set.

If the Borda winner $a_{B}$ exists, then $a_{B} \in U_{⋗}$ .

If the Condorcet winner $a_{C}$ exists, then $a_{C} \in U_{⋗}$ .

If the quasi-positional winner $a_{Q}$ exists, then $a_{Q} \in U_{⋗}$ .

If the positional winner $a_{P}$ exists, then $a_{P} \in U_{⋗}$ .

If the pairwise winner $a_{W}$ exists, then $a_{W} \in U_{⋗}$ .

If the majority winner $a_{M}$ exists, then $a_{M} \in U_{⋗}$ .

If the unanimous winner $a_{U}$ exists, then $a_{U} \in U_{⋗}$ .

Proof. (i) Suppose that there exists a candidate $a_{i}$ that superdominates the Borda winner $a_{B}$ . Since $a_{i} ⋗ a_{B}$ implies $a_{i} ⋗_{S} a_{B}$ , it holds that $B (a_{i}) > B (a_{B})$ , a contradiction.

(ii) Suppose that there exists a candidate $a_{i}$ that superdominates the Condorcet winner $a_{C}$ . Since ⋗ is contained in ≻, it holds that $a_{i} ≻ a_{C}$ , a contradiction.

(iii)–(vii) All other statements follow from (i) and (ii) and the fact that the existence of any among the quasi-positional winner, the positional winner, the pairwise winner, the majority winner and the unanimous winner implies the existence of and the compliance with at least one of either the Borda winner or the Condorcet winner.□

The existence of the positional winner implies that the unsuperdominated set is a singleton. However, the fact that the unsuperdominated set is a singleton does not imply that the positional winner exists. This is due to the fact that the superdominance relation is not transitive (only acyclic).

Proposition 7. Let $C$ be a set of k candidates, $R$ be the profile of r rankings on $C$ given by the voters and $U_{⋗}$ be the unsuperdominated set. The following statements hold:

If a candidate $a_{P}$ is the positional winner, then $U_{⋗} = {a_{P}}$ .

If $U_{⋗} = {a_{i}}$ , then $a_{i}$ does not need to be the positional winner.

Proof. (i) Let $a_{P}$ be the positional winner. By definition, for any other candidate $a_{i} \in C \ {a_{P}}$ , it holds that $a_{P} ⋗ a_{i}$ . It obviously follows that the unique candidate that can belong to the unsuperdominated set is $a_{P}$ . Due to Proposition 5, we know that $U \neq \emptyset$ . Therefore, we conclude that $U = {a_{P}}$ .

(ii) Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 1. It follows that $U_{⋗} = {a}$ , but a is not the positional winner.□

Some other natural choice sets are the core and the uncovered set (Miller, 1980), the unsupercovered set (Pérez-Fernández and De Baets, 2018) and the Smith set (Good, 1971; Smith, 1973).

Definition 16. Let $C$ be a set of k candidates and $R$ be the profile of r rankings on $C$ given by the voters.

The core is the subset $U_{≻}$ of $C$ defined as

U_{≻} = {a_{i_{1}} \in C | (∄ a_{i_{2}} \in C) (a_{i_{2}} ≻ a_{i_{1}})}

The uncovered set is the subset $U_{>>}$ of $C$ defined as

U_{>>} = {a_{i_{1}} \in C | (∄ a_{i_{2}} \in C) (a_{i_{2}} >> a_{i_{1}})}

The unsupercovered set is the subset $U_{\cdot >>}$ of $C$ defined as

U_{\cdot >>} = {a_{i_{1}} \in C | (∄ a_{i_{2}} \in C) (a_{i_{2}} \cdot >> a_{i_{1}})}

The Smith set is the smallest non-empty subset $S$ of $C$ such that any candidate in $S$ dominates any candidate outside of $S$ .

Remark 1. Since the relation ≻ might be cyclic, the core might be empty. However, the uncovered set, the unsupercovered set and the Smith set are always assured to be non-empty.

It is known that the core is contained in the uncovered set, which is, at the same time, contained in the Smith set. Moreover, since the dominance relation contains both the superdominance relation and the supercovering relation, the core is included in both the undominated set and the unsupercovered set. Actually, since the supercovering relation is included in the covering relation, the uncovered set is trivially included in the unsupercovered set. Next, we show four examples in which we prove that there are no relations outside the aforementioned ones between these five choice sets.

Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 1. It follows that $U_{≻} = \emptyset$ , $U_{⋗} = {a}$ , $U_{>>} = {a, b, c}$ , $U_{\cdot >>} = {a, b, c}$ and $S = {a, b, c}$ .

Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 2. It follows that $U_{≻} = {a}$ , $U_{⋗} = {a, b}$ , $U_{>>} = {a}$ , $U_{\cdot >>} = {a, b}$ and $S = {a}$ .

Consider the set of candidates $C = {a, b, c}$ and the profile of rankings shown in Table 4. It follows that $U_{≻} = {a}$ , $U_{⋗} = {a, b}$ , $U_{>>} = {a}$ , $U_{\cdot >>} = {a}$ and $S = {a}$ .

Consider the set of candidates $C = {a, b, c, d}$ and the profile of rankings shown in Table 6. It follows that $U_{≻} = \emptyset$ , $U_{⋗} = {a, c, d}$ , $U_{>>} = {a, c, d}$ , $U_{\cdot >>} = {a, c, d}$ and $S = {a, b, c, d}$ .

Table 6.

Frequency of the rankings on $C = {a, b, c, d}$ expressed by three voters.

$# ≻_{i}$	Rankings on $C$
1	$a ≻ b ≻ c ≻ d$
1	$d ≻ a ≻ b ≻ c$
1	$c ≻ d ≻ a ≻ b$

Figure 3 displays the relation between the different types of subset of $C$ analysed in this section. In this figure, an arrow indicates that the set from which the arrow starts is included in the set to which the arrow points.

Figure 3.

Relation between the different subsets of $C$ .

5. Conclusions and open problems

In this paper, we have followed the direction started in Pérez-Fernández and De Baets (2018), and we have proposed new interesting notions linking the works of Borda and Condorcet. In particular, the introduction of the superdominance relation – a natural way of comparing candidates based on positional information – and the positional winner – a candidate that superdominates all other candidates – is the main contribution of this paper. Moreover, we have presented the unsuperdominated set as a new natural choice set. Interestingly, the unsuperdominated set always contains the Condorcet winner if it exists, but, unlike the most prominent choice sets, it does not need to reduce to it.

Future research is anticipated in multiple directions. For instance, it is known that, under the Impartial Anonymous Culture (IAC) assumption (Gehrlein and Fishburn, 1976; Kuga and Nagatani, 1974), the probability of both the Borda winner and the Condorcet winner to exist and coincide equals $\frac{41}{48}$ for the case in which a set of three candidates is considered and the number of voters is assumed to be large enough (Gehrlein and Lepelley, 2001). Obviously, since we have identified a profile of rankings on a set of three candidates for which both the Borda winner and the Condorcet winner exist and coincide, but for which the positional winner (Table 4) or the pairwise winner (Table 5) does not exist, the probability of existence of either the positional winner or the pairwise winner needs to be strictly lower than $\frac{41}{48}$ . Also, as an anonymous reviewer to this paper pointed out, under the Impartial Culture (IC) assumption (Berg and Lepelley, 1994), the probability that all scoring rules select the same winner (and thus the probability of existence of the quasi-positional winner) equals approximately 0.53464 for the same case in which a set of three candidates is considered and the number of voters is assumed to be large enough (Merlin et al., 2000). Similarly, the probability that this quasi-positional winner turns out to be the Condorcet winner (and thus the probability of existence of the positional winner in a three-candidate setting) equals approximately 0.50116 (Merlin et al., 2000). A further study on these topics is yet to be addressed.

Footnotes

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: Raúl Pérez-Fernández acknwoledges the support of the Research Foundation of Flanders (FWO17/PDO/160).

ORCID iD

Raúl Pérez-Fernández

Notes

References

Arrow

Sen

Suzumura

(2002) Handbook of Social Choice and Welfare, volume 1. Amsterdam: North-Holland.

Banks

(1985) Sophisticated voting outcomes and agenda control. Social Choice and Welfare 3: 295–306.

Berg

Lepelley

(1994) On probability models in voting theory. Statistica Neerlandica 48(2): 133–146.

Black

(1958) The Theory of Committees and Elections. Cambridge: Cambridge University Press.

Borda

(1781) Mémoire sur les Élections au Scrutin. Paris: l’Académie Royale des Sciences.

Brandt

Fischer

Harrenstein

(2009) The computational complexity of choice sets. Mathematical Logic Quarterly 55(4): 444–459.

Condorcet

(1785) Essai sur l’Application de l’Analyse à la Probabilité des Décisions Rendues à la Pluralité des Voix. Paris: De l’Imprimerie Royale.

Copeland

(1951) A reasonable social welfare function. Seminar on Applications of Mathematics to the Social Sciences, University of Michigan.

Dutta

(1988) Covering sets and a new Condorcet choice correspondence. Journal of Economic Theory 44: 63–80.

10.

Fine

(1974) Social choice and individual ranking I. The Review of Economic Studies 41(3): 303–322.

11.

Fishburn

(1973) The Theory of Social Choice. New Jersey: Princeton University Press.

12.

Fishburn

(1974) Paradoxes of voting. The American Political Science Review 68(2): 537–546.

13.

Gehrlein

Fishburn

(1976) Condorcet’s paradox and anonymous preference profiles. Public Choice 26: 1–18.

14.

Gehrlein

Lepelley

(2001) The Condorcet efficiency of Borda Rule with anonymous voters. Mathematical Social Sciences 41: 39–50.

15.

Good

(1971) A note on Condorcet sets. Public Choice 10: 97–101.

16.

Inada

(1969) The simple majority decision rule. Econometrica 37(3): 490–506.

17.

Kuga

Nagatani

(1974) Voter antagonism and the paradox of voting. Econometrica 42(6): 1045–1067.

18.

Llamazares

Peña

(2015) Positional voting systems generated by cumulative standings functions. Group Decision and Negotiation 24(5): 777–801.

19.

May

(1952) A set of independent necessary and sufficient conditions for simple majority decision. Econometrica 20: 680–684.

20.

Merlin

Tataru

Valognes

(2000) On the probability that all decision rules select the same winner. Journal of Mathematical Economics 33: 183–207.

21.

Miller

(1980) A new solution set for tournaments and majority voting: further graph-theoretical approaches to the theory of voting. American Journal of Political Science 24(1): 68–96.

22.

Moulin

(1983) The Strategy of Social Choice. Amsterdam: North-Holland.

23.

Nurmi

(1987) Comparing Voting Systems. Dordrecht: Reidel.

24.

Pérez-Fernández

De Baets

(2017) Recursive monotonicity of the scorix: Borda meets condorcet. Group Decision and Negotiation 26(4): 793–813.

25.

Pérez-Fernández

De Baets

(2018) The supercovering relation, the pairwise winner, and more missing links between Borda and Condorcet. Social Choice and Welfare 50: 329–352.

26.

Pérez-Fernández

Rademaker

Alonso

et al . (2016a) Representations of votes facilitating monotonicity-based ranking rules: From votrix to votex. International Journal of Approximate Reasoning 73: 87–107.

27.

Pérez-Fernández

Rademaker

De Baets

(2016b) The scorix: A popular representation of votes revisited. International Journal of Approximate Reasoning 78: 241–251.

28.

Saari

(2000) Mathematical structure of voting paradoxes II: Positional voting. Economic Theory 15: 55–102.

29.

Schwartz

(1972) Rationality and the myth of the maximum. Noûs 6(2): 97–117.

30.

Sen

(1966) A possibility theorem on majority decisions. Econometrica 34(2): 491–499.

31.

Slater

(1961) Inconsistencies in a schedule of paired comparisons. Biometrika 48(3–4): 303–312.

32.

Smith

(1973) Aggregation of preferences with variable electorate. Econometrica 41: 1027–1041.

33.

Stein

Mizzi

Pfaffenberger

(1994) A stochastic dominance analysis of ranked voting systems with scoring. European Journal of Operational Research 74(1): 78–85.

34.

Young

(1975) Social choice scoring functions. SIAM Journal on Applied Mathematics 28(4): 824–838.

35.

Young

(1988) Condorcet’s theory of voting. American Political Science Review 82(4): 1231–1244.