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.
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
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) 1 , 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
The matrix of which the element at the i-th row and the
for any
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
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
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).
the inequality being strict for at least one t.
If a candidate
Next, we propose a natural relation based on the notions of Borda dominance and sub-scorix: the superdominance relation.
Obviously, the superdominance relation is included in the Borda dominance relation.
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.
The preceding definitions are illustrated in the following example.
Frequency of the rankings on
The scorix induced by
Note that, for instance, considering candidates a and d, it holds that
Thus, it holds that
All the possible (proper) subsets of
Note that it holds that
Thus, it holds that
Obviously, it holds that
The matrix of which the element at the
for any
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).
Note that the superdominance relation further restricts the dominance relation, 3 thereby justifying its name.
Proof. The result immediately follows by considering the sub-scorix
Other interesting relations between candidates are the covering relation (Miller, 1980) and the supercovering relation (Pérez-Fernández and De Baets, 2018).
Note that, for instance, considering candidates a and d, it holds that
Thus, it holds that
Note that ⋗ is included in ≻, but
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
We can also see that
Thus, it holds that
Note that none of the relations >> and ·>> is included or includes the relation ⋗ or the relation
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

Relation between the different types of relation on
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.
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).
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.
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
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
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).
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.
A candidate
A candidate
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.
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
Frequency of the rankings on
Suppose that there exist two quasi-positional winners
and
for all
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.
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
(b) Consider the set of candidates
(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
(iii) (a) Consider the set of candidates
(b) Consider the set of candidates
(c) Consider the set of candidates
(iv) (a) Consider the set of candidates
(b) Consider the set of candidates
(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
(b) Consider the set of candidates
(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.□
Frequency of the rankings on
Frequency of the rankings on
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
(b) Consider the set of candidates
Frequency of the rankings on
(ii) (a) The result trivially follows from Proposition 1.
(b) Consider the set of candidates
(iii) (a) The result trivially follows from (ii) and Theorem 1 (ii).
(b) Consider the set of candidates
(iv) (a) The result trivially follows from Proposition 3.
(b) Consider the set of candidates
(v) (a) Consider the set of candidates
(b) Consider the set of candidates
(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
(b) Consider the set of candidates
(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.

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.
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.
All types of winner recalled in the preceding section belong to the unsuperdominated set in the event that they exist.
If the Borda winner
If the Condorcet winner
If the quasi-positional winner
If the positional winner
If the pairwise winner
If the majority winner
If the unanimous winner
Proof. (i) Suppose that there exists a candidate
(ii) Suppose that there exists a candidate
(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).
If a candidate
If
Proof. (i) Let
(ii) Consider the set of candidates
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).
The core is the subset
The uncovered set is the subset
The unsupercovered set is the subset
The Smith set is the smallest non-empty subset
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
Consider the set of candidates
Consider the set of candidates
Consider the set of candidates
Frequency of the rankings on
Figure 3 displays the relation between the different types of subset of

Relation between the different subsets of
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
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).
