Abstract
Referring to a standard context of voting theory, and to the classic notion of voting situation, here we show that it is possible to observe any arbitrary set of elections’ outcomes, no matter how paradoxical it may appear. In this respect, we consider a set of candidates \(1, 2, \ldots , m \) and, for any subset A of \(\{1, 2, \ldots , m \}\), we fix a ranking among the candidates belonging to A. We wonder whether it is possible to find a population of voters whose preferences, expressed according to the Condorcet’s proposal, give rise to that family of rankings. We will show that, whatever be such family, a population of voters can be constructed that realize all the rankings of it. Our conclusions are similar to those coming from D. Saari’s results. Our results are, however, constructive and allow for the study of quantitative aspects of the wanted voters’ populations.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
In this paper we consider a standard scenario of voting theory that will be briefly described as follows. For more complete descriptions and presentations, Readers are addressed, e.g., to Nurmi (1999), Gehrlein and Lepelley (2017), Montes et al. (2020), Stearns (1959) and bibliography cited therein.
We think of a system of possible elections, based on a fixed set of potential candidates, labeled as 1, 2, ..., m, and on a fixed set of voters, \(v_{1},v_{2},...,v_{n}\). Denote by \(\left[ m\right] \equiv \{1,2,...,m\}\) the set of candidates and by V \(\equiv \{v_{1},v_{2},...,v_{n}\}\) the set of voters.
Each voter is supposed to cast one and only one vote, at any election. On the other hand different elections can be considered, respectively, characterized by the different subsets \(A\subseteq \left[ m\right] \) of participating candidates. The differences among elections’ outcomes, encountered at varying the subsets of candidates, are just at the core of the questions considered here.
Concerning the mechanism determining the vote of the single voter \(v_{l}\) (\(v_{l}\in V,l=1,...,n\)) in any of such elections, it is assumed that the individual preferences, among candidates, of \(v_{l}\) are complete, transitive, and also antisymmetric, coherently with the assumption that indifference is not allowed between any two candidates. Thus, individual preferences give rise to a linear preference ranking. In other words the preference ranking of \(v_{l}\) is described by a permutation \(r_{l}\) over the set [m]. Such a permutation is to be viewed as a piece of a-priori information, established independently of the special subsets of candidates which will be encountered in the elections. Thus, in an election characterized by a subset \(A\subseteq \left[ m\right] \) of candidates, the vote expressed by \(v_{l}\) is definitely addressed to the one who is the preferred candidate among the elements of A, according to the permutation \(r_{l}\), for \(l=1,...,n\).
As a further feature of our work, we concentrate attention on objects of the following type. For any subset \(A\subseteq \left[ m\right] \) (A containing two or more elements of \(\left[ m\right] \)), we fix an arbitrary ranking among the elements of A. Then we consider the collection \(\varvec{\sigma }\) of all such rankings, obtained by browsing all the subsets A. Such a collection gives rise to the notion of ranking pattern (see Definition 2 in the next section) which extends the one of majority graph, or preference pattern.
Coming back to the above scenario of Voting Theory, we now remind the notion of voting situation.
On this purpose we look at the collective of all the n voters and denote by \(N^{(m)}(j_{1},\ldots ,j_{m})\) the number of the voters who share the same linear preference ranking \(\left( j_{1},\ldots ,j_{m}\right) \), where \(j_{1}\) is the most preferred candidate and \(j_{m}\) is the least preferred one. The family of numbers \({\mathcal {N}}^{(m)}\equiv \{N^{(m)}(j_{1},\ldots ,j_{m})\}\), is typically referred to as the voting situation.
Maintaining the assumption that, for any \(A\subseteq \left[ m\right] \), any voter casts a single vote addressed to the preferred candidate in A, and comparing the numbers of votes so obtained by any single candidate \(j\in A\), a voting situation \({\mathcal {N}}^{(m)}\) determines a corresponding ranking pattern \(\varvec{\sigma }\), that will be termed ranking pattern q-concordant with \({\mathcal {N}}^{(m)}\) (see Definition 2 in the next section).
The problems solved in this paper can be simply formulated as follow:
Fixed, for given m, an arbitrary ranking pattern \(\varvec{\sigma }\) on the subsets of \(\left[ m\right] \), can we guarantee the existence of some q-concordant voting situations \({\mathcal {N}}^{(m)}\)?
If so, is it possible to construct at least one of such \({\mathcal {N}}^{(m)}\)? What can be said about the number of voters needed to realize such an \({\mathcal {N}}^{(m)}\)?
The above questions can be connected to the literature about the paradoxes studied in the voting theory.
An arbitrary ranking pattern may exhibit several types of surprising behavior. In particular one can observe different forms of Condorcet-type paradoxes. It is well known that the latter topic is related to non-transitivity of collective voting outcomes and is one of the starting points of voting theory.
The literature related to voting paradoxes has a long history (see e.g. Alon 2002; Fishburn 1981; Mala 1999; Saari 1989, 1995, 2018a). Along such literature a very wide catalogue of, more or less complex, special cases has been thoroughly analyzed to show the possibility of different types of paradoxes. In particular, important contributions have arisen as direct extensions of the original Condorcet observation which shows the possibility of the phenomenon of non-transitivity, in the presence of three candidates. Considering the case of an arbitrary number m of candidates, the basic result by McGarvey shows, for any preference pattern, the existence of a voting situation triggering that pattern. Also the mathematical results by Saari can be seen as extensions on the same line of the McGarvey’s theorem in McGarvey (1953). Several other important contributions in the same direction have been given in more recent times. See e.g. Nurmi (1999), Saari (2018b), Mala (1999) and references therein.
As also well known a somehow different literature, starting from the controversy between Borda and Condorcet, is concerned with the comparison among voting systems and, on the basis of a fixed voting situation, with different definitions of the election winners. See e.g. Fishburn (1981), Nurmi (1999), Perez-Fernandez and De Baets (2019), Klamler (2005), Van Newenhizen (1992) and references cited therein. Other parts of the literature have been devoted to analyzing the probability that paradoxes can manifest, in the case of random voting situations and under different stochastic models (see e.g. Kalai 2004; Hazla et al. 2020).
Following the same direction of Condorcet, McGarvey, Saari, our results actually lead to conclusions very similar to those of the results given by the latter Author. They are however constructive and provide some quantitative information about the number of voters needed to constructing concordant voting situations.
Within the family of all the ranking pattern, we distinguish the subclass of strict ranking patterns. In such particular case our solutions can be presented in closed forms.
In De Santis and Spizzichino (2023), the definition was given of ranking pattern p-concordant with a multivariate survival model and it has been proven that, for any strict ranking pattern, there exist p-concordant survival models (see Theorem 2 in De Santis and Spizzichino (2023), recalled here as Theorem 7 in “Appendix”). Starting from this result, here we prove the existence of q-concordant voting situations for any (strict or weak) ranking pattern (Theorems 1, 2).
Results proven here, however, also allow us to solve a problem that was left open in the paper (De Santis and Spizzichino 2023). In fact, concerning with weak ranking patterns, Theorem 2 leads to a general existence result about p-concordant voting situations (Corollary 1). Such a generalization of the results presented in De Santis and Spizzichino (2023) would not be smooth without the passage through the logic and the language of voting theory.
More precisely, the plan of the paper is as follows.
In Sect. 2, we recall notation, definitions, and preliminary results. In particular, we recall the definition of ranking pattern p-concordant with a probability model for a m-tuple of random variables. Based on this material we detail the identity between the considered voting-theory scenario and the study of probability distributions, induced by the m-tuples of random variables, over the space of the permutations of the elements of \(\left[ m\right] \) (Proposition 2).
Section 3 is devoted to presenting results concerning the construction of q-concordant voting situations. By exploiting and extending results presented in De Santis and Spizzichino (2023), we in particular single out a method to construct voting situations concordant with weak ranking patterns, by starting from voting situations concordant with strict ranking patterns (see Theorem 2).
Distinguishing between the two cases of strict and weak ranking patterns, the issue of possible values of the number of voters required for obtaining q-concordant voting situations is studied in Sect. 4. We in particular exhibit a universal value \(\overline{\theta }_{m}\) (depending on m, the total number of candidates) such that, for an arbitrary strict ranking pattern \(\varvec{\sigma }\), a q-concordant voting situation exists and can be produced with \(\overline{\theta }_{m}\) voters. Such a voting situation can be constructed explicitly (Theorems 4, 5).
In Sect. 5 we present a discussion based on some concluding remarks.
For the sake of self-consistency, in the Appendix we review definitions and main results on load-sharing models, which have been used in De Santis and Spizzichino (2023) for the construction of survival models p-concordant with strict ranking patterns.
2 Notation, definitions, and preliminary results
We start this section by introducing some concepts and notation which will be used next and which concern non-negative random variables.
Let \([m]:=\{1,...,m\}\) and denote by \(\Pi _{m}\) the set of permutations of the elements of [m].
Let \(X_{1},\dots ,X_{m}\) be non-negative random variables satisfying the no-tie condition
for \(i,j\in [ m]\) with \(i\ne j\). Let the symbols \(X_{1:m},\ldots ,X_{m:m}\) denote the order statistics of \(X_{1},\dots ,X_{m}\) and let \({\textbf{J}} \equiv \left( J_{1},\ldots ,J_{m}\right) \) denote the discrete random vector defined by the position
for any \(i,r\in [ m]\). For \((j_{1}, \ldots , j_{m} ) \in \Pi _{m}\), we set
and by \({\textbf{P}}_{{\textbf{J}}}\) we briefly denote the collection of all the m! probabilities in (3). Clearly, \({\textbf{P}}_{{\textbf{J}}}\) is determined by the joint probability distribution of \(X_{1},\dots ,X_{m}\) and, in its turn, it determines a probability distribution over the finite set \(\Pi _{m }\).
In view of our study, an object of central interest is the family
where \(\alpha _{j}(A)\) denotes the probability defined by
In some contexts it is useful to look at \(\alpha _{j}(A)\) as a winning probability.
Remark 1
Clearly, it may also be natural to alternatively consider situations where it is needed to single out the random variable with highest probability to be a maximum among a given set of other lifetimes. However the position in (4) is convenient in view of our proofs (see e.g. Proposition 1).
Remark 2
The family \({\mathcal {A}}_{(m)}\) is determined by \({\textbf{P}}_{{\textbf{J}}}\). In this respect a detailed formula is shown in Proposition 1 of De Santis and Spizzichino (2023).
Notice that the random variables \(X_1, \ldots , X_m\) can be interpreted as waiting times, respectively, associated to m different objects. In this respect, one can think of various contexts where it is needed to single out the lifetime (or the time-to-event) maximizing the probability to be a minimum among a given set of other lifetimes or times-to-event. Thus we are generally interested in comparisons of the type
In order to describe preference rankings among the elements of the subsets \(A\subseteq \left[ m\right] \), we introduce ranking functions \(\sigma (A,\cdot ):A\rightarrow \{1,2,\ldots ,|A|\}\). For \(i,j\in A\), it will be \(\sigma (A,i)<\sigma (A,j)\) if i precedes j in A whereas \(\sigma (A,i)=\sigma (A,j)\) when they are equivalent inA. More precisely \(\sigma (A,i)\) is equal to 1 plus the number of elements belonging to A and preceding i. Consider for example the case \(m=10\), \(A=\{3,4,6,8,9\}\), where 6 is the favorite element, followed by 4 and 8 with equal merit, then followed by 3 and finally with 9 as the less favorite element in A. Then
By using this notation we now give more formally the following
Definition 1
For \(A\subseteq \left[ m \right] \), a mapping \(\sigma (A,\cdot ):A\rightarrow \{1,2,\ldots ,|A|\}\) is a ranking function if it satisfies the following condition
for each \(i \in A\).
In the above definition the symbol \({\textbf{1}}_{[\sigma (A,i)-1]} (\cdot )\) obviously denotes the indicator function of the set \([\sigma (A,i)-1] = \{ 1, \ldots , \sigma (A,i)-1\}\).
The above definition is also termed standard competition ranking. Other analogous definitions have been considered in the literature, e.g. modified competition ranking, dense ranking. We point out that all such definitions are however equivalent as to the order relation between any two elements. Definition 4 below, in fact, is not affected by the special choice considered.
When some equivalence holds between two elements of A, we say that \(\sigma (A,\cdot )\) is a weak ranking function. When, on the contrary, the values \(\sigma (A,j)\), \(j\in A\), are all different then \(\sigma (A,\cdot ):A\rightarrow \{1,2,\ldots ,|A|\}\) is a bijective function, namely \(\sigma (A,\cdot )\) describes a permutation of the elements of A. This case will be designated by the term strict ranking function.
Definition 2
For \(m\ge 2\), a ranking pattern over [m] is a family of ranking functions \(\varvec{\sigma }\equiv \{\sigma (A,\cdot ):A\subseteq \left[ m\right] , \, |A|\ge 2 \}\). A ranking pattern is said to be strict when it does not contain any weak ranking function. The symbols \(\Sigma ^{(m)}\) and \({\hat{\Sigma }}^{(m)} \subset \Sigma ^{(m)}\) denote the collections of all the ranking patterns over [m] and of all the strict ranking patterns, respectively.
The symbol \(\sigma (A,i)\) has a two-fold meaning: on the one hand it has the basic meaning of ordinal number. On the other hand it is necessary, in our formulas, to treat it as a natural number.
A ranking pattern will be associated in a natural way to the family \({\mathcal {A}}_{(m)}\) as follows
Definition 3
The ranking pattern \(\varvec{\sigma }\equiv \{\sigma (A,\cdot ): A\subseteq \left[ m\right] , \, |A|\ge 2 \}\) and the m-tuple \((X_{1},\dots ,X_{m})\) are p-concordant whenever, for any \(A\subseteq \left[ m\right] \) and \(i,j\in A\) with \(i\ne j\)
Notice that the quantities \(\sigma (A,i)\) are natural numbers belonging to [|A|], whereas the quantities \(\alpha _{j}(A)\) are real numbers belonging to [0, 1]. Obviously for any m-tuple \((X_{1},\ldots ,X_{m})\) there exists one and only one p-concordant ranking pattern.
Let us now come back to the voting scenario described in the Introduction and fix a voting situation
For \(i\in [ m]\) and \({\varvec{j}}\equiv (j_{1},\ldots ,j_{m})\in \Pi _{m}\), the symbol \(\phi _{{\varvec{j}}}(i)\) will be used to denote the position of i within the vector \({\varvec{j}}\):
Thus \(\phi _{{\varvec{j}}}(\cdot )\) is a bijection on [m].
As anticipated in the Introduction, we are assuming that the voters’ individual behavior is á la Condorcet. Namely, in an election where \(A\subseteq [ m]\) is the set of the participating candidates, all the voters who share the same linear preference ranking \({\varvec{j}}\) will cast their individual vote in favor of \(i \in A \) if i is the favorite candidate within the set A, i.e. whenever \(\phi _{{\varvec{j}}}(i)<\phi _{{\varvec{j}}}(h)\), for any \(h\in A,\) with \(h\ne i\). More concisely, we can write the number of votes in favor of i as
We focus attention on the family
associated to \({\mathcal {N}}^{(m)}\). We also look at the total number of voters:
Sometime we use the notation \(n ( {\mathcal {N}}^{(m)} ) \) in place of n in order to stress the dependence on the voting situation \({\mathcal {N}}^{(m)} \). This notation will be essentially used in the case of comparisons between different voting situations with different total number of voters.
Furthermore we point out that also the family \({\textbf{N}}\) gives rise to a ranking pattern in analogy with the above Definition 3. For any \(A\subseteq [m]\), such a ranking pattern will assign smaller values to those candidates who receive larger numbers of votes.
Definition 4
A ranking pattern \(\varvec{\sigma }\equiv \{\sigma (A,\cdot );A\subseteq \left[ m\right] , |A|\ge 2 \}\) and a voting situation \({\mathcal {N}}^{(m)}\)are q-concordant whenever, for any \(A\subseteq \left[ m\right] \) and \(i,j\in A\) with \(i\ne j\)
We notice that the definitions of ranking function, ranking pattern, and q-concordance concern with very natural concepts, already considered in the literature under different notation. However, we have introduced special terms and symbols on the purpose of concise formulation of our results.
Keeping in mind that any voting situation \({\mathcal {N}}^{(m)}\) triggers a corresponding family \({\textbf{N}}\) and in order to detail the relation tying \({\textbf{N}}\) to \({\mathcal {N}}^{\left( m\right) }\), we now single out a discrete probability model, strictly related to \({\mathcal {N}}^{(m)}\) and defined as follows. Consider the finite probability space \((\Pi _{m},{\mathbb {P}}^{{\mathcal {N}}})\) with
for any \((j_{1},\ldots ,j_{m})\in \Pi _{m}\) and n given in (13).
On the space \((\Pi _{m},{\mathbb {P}}^{{\mathcal {N}}})\) we define the no-tie, discrete, random variables
for \(i\in [m]\) and where \(\phi _{\left( j_{1}...,j_{m}\right) }(i)\) is defined in (10).
Under such a position and recalling (2), the related discrete random variables \(({\widehat{J}}_{1},\ldots ,{\widehat{J}}_{m})\) are such that, for any \((j_{1},\ldots ,j_{m})\in \Pi _{m}\),
For what concerns the family \(\widehat{{\mathcal {A}}}_{(m)}\), associated with the random variables defined in (16), one has
The above identity allows us to compare the two settings of voting theory and survival models, respectively, concerning a voting situation \({\mathcal {N}} ^{(m)}\) with m candidates and the m discrete random variables \({\widehat{X}}_{1},...,{\widehat{X}}_{m}\). We can thus summarize as follows
Proposition 1
Let \({\mathcal {N}}^{(m)}\) be a voting situation and \({\widehat{X}}_{1},...,{\widehat{X}}_{m}\) be the random variables defined in (16). Then
for \(A\subseteq \left[ m\right] \) and \(i \in A\).
In view of the above Remark 2, we notice that two models sharing the same \(\mathbf {P_{J}}\) also give rise to the same \({\mathcal {A}} _{(m)}\). By combining Definitions 3 and 4 with Proposition 1, one obtains an interesting conclusion concerning a voting situation \({\mathcal {N}}^{(m)}\) and any random m-tuple \(\left( X_{1},\dots ,X_{m}\right) \) satisfying the relation
More precisely, we can state the following result
Proposition 2
Let \({\mathcal {N}}^{(m)}\) be a voting situation and let \(X_{1},\dots ,X_{m}\) be no-tie, non-negative, random variables such that the condition (20) holds. Then, for any ranking pattern \(\varvec{\sigma }\in \Sigma ^{(m)}\), the following two statements are equivalent:
(a) the m-tuple \((X_{1},\dots ,X_{m})\) is p-concordant with \(\varvec{\sigma }\);
(b) the voting situation \({\mathcal {N}}^{(m)}\) is q-concordant with \(\varvec{\sigma }\).
Even though an obvious remark, it is important to note that the condition (20) requires that all the probabilities \(p_{m}(j_{1},\ldots ,j_{m})\) are rational numbers, for \((j_{1},\ldots ,j_{m})\in \Pi _{m}\).
Example 1
Consider a triple of random variables \(X_{1},X_{2},X_{3}\) satisfying the following conditions
By a few simple computations (see Example 2 in [6] for details) one obtains
\((X_{1},X_2,X_{3})\) are p-concordant with the ranking pattern \(\varvec{\sigma }\) described as follows
As a direct application of Proposition 2, we can immediately realize that a voting situation q-concordant with \(\varvec{\sigma }\) can be obtained from the above quantities \(p(j_{1},j_{2},j_{3})\), by considering a population of \(n=21\) voters and by simply imposing the condition
3 Existence of q-concordant voting situations
This section is devoted to obtaining two different results about existence of voting situations that are q-concordant with a given ranking pattern \(\varvec{\sigma }\). In the first result (Theorem 1) we consider the special case where \(\varvec{\sigma }\) is a strict ranking pattern (i.e. \(\varvec{\sigma }\in {\widehat{\Sigma }}^{\left( m\right) }\)). Such a result, on its turn, will provide us with a basis to also prove the existence of q-concordant voting situations in the general case when \(\varvec{\sigma }\) is a weak ranking pattern (\(\varvec{\sigma } \in \Sigma ^{\left( m\right) }\)) (Theorem 2).
As first we address to Theorem 1, whose proof is obtained by combining the above Proposition 2 with Theorem 6 in Appendix. We point out that Theorem 6 immediately follows from Theorem 2 in De Santis and Spizzichino (2023). Since the proof of the latter result is rather complex, we have preferred here to present an independent proof for the qualitative, and weaker, Theorem 6.
Theorem 1
For any \(m \in {\mathbb {N}}\) and for any \(\varvec{\sigma }\in {\hat{\Sigma }}^{(m)}\), there exists a voting situation \({\mathcal {N}}^{(m)}\) which is q-concordant with \(\varvec{\sigma }\).
Proof
By Theorem 6 in Appendix, one can select a probability model (a survival model of the type \(LS (\varvec{\varepsilon },\varvec{\sigma })\)) that is p-concordant with \(\varvec{\sigma }\) and such that all the elements of the set
are rational. Let us now consider the numbers
where \(n\in {\mathbb {N}}\) is a suitable constant such that all the \(N^{(m)}(j_{1},\ldots ,j_{m})\)’s are integers. The voting situation \({\mathcal {N}}^{(m)}\) defined by
is q-concordant with \(\varvec{\sigma }\) by Proposition 2. \(\square \)
We can now turn to considering the case of weak ranking patterns. In the next Theorem 2 we extend Theorem 1 to the set \(\Sigma ^{(m)}\) of all ranking patterns (both strict and weak). The proof is obtained by starting from Theorem 1 and by applying a suitable induction procedure.
On the space of voting situations, we now consider the following operations, which also appear in other contexts of social choice theory:
-
1.
(Multiplication) For any \(\ell \in {\mathbb {N}}\) and for any voting situation \({\mathcal {N}}^{(m)}\) we consider the new voting situation defined as:
$$\begin{aligned} \ell \times {\mathcal {N}}^{(m)} = \{ \ell \cdot N^{(m)} (j_{1}, \ldots , j_{m}): (j_{1}, \ldots , j_{m}) \in \Pi _{m}\}. \end{aligned}$$ -
2.
(Addition) For any \(\ell \in {\mathbb {N}}\) and for any voting situation \({\mathcal {N}}^{(m)}\) we consider the new voting situation defined as:
$$\begin{aligned} \ell {\textcircled {+}}{\mathcal {N}}^{(m)} = \{ \ell +N^{(m)} (j_{1}, \ldots , j_{m}): (j_{1}, \ldots , j_{m}) \in \Pi _{m}\}. \end{aligned}$$ -
3.
(Internal addition) For any two voting situation \({\mathcal {N}}^{(m)}\) and \({{\mathcal {N}}^{\prime }}^{(m)} \) we consider the new voting situation defined as:
$$\begin{aligned} {\mathcal {N}}^{(m)} +{{\mathcal {N}}^{\prime }}^{(m)} =\{ N^{(m)}(j_{1}, \ldots , j_{m} ) + {N^{\prime }}^{(m)}(j_{1}, \ldots , j_{m} ):(j_{1}, \ldots , j_{m} ) \in \Pi _{m} \}. \end{aligned}$$
Such operations will in fact be useful in the formulation and in the proofs of the next results
We notice that the total number of voters for the above voting situations are, respectively, given by
For our purposes it is also useful to recall the attention on the following simple result.
Proposition 3
Let \(\ell \in {\mathbb {N}} \), \({\mathcal {N}}^{(m)} \) be a voting situation and let \(\varvec{\sigma } \in \Sigma ^{(m)}\) be the ranking pattern q-concordant with \({\mathcal {N}}^{(m)} \). Then \(\varvec{\sigma } \) is also q-concordant with \(\ell \times {\mathcal {N}}^{(m)} \) and \(\ell {\textcircled {+}}{\mathcal {N}}^{(m)} \).
Proof
First we notice that, when A is the set of candidates, the voting situation \(\ell \times {\mathcal {N}}^{(m)} \) assigns \(\ell \cdot n_{i} (A)\) votes to candidate i, see (11). Thus the proportion of votes assigned to each candidate remains the same as in the original voting situation \({\mathcal {N}}^{(m)} \). Hence \(\ell \times {\mathcal {N}}^{(m)} \) and \({\mathcal {N}}^{(m)} \) are q-concordant with the same ranking pattern \(\varvec{\sigma }\).
We now prove that \({\mathcal {N}}^{(m)} \) and \(\ell \textcircled {+} {\mathcal {N}} ^{(m)} \) are q-concordant with the same \(\varvec{\sigma } \in \Sigma ^{(m)}\). Let us consider \(A \subseteq [m] \) and two distinct elements \(a,b \in A \). For any given \((j_{1}, \ldots , j_{m} )\in \Pi _{m} \) let us consider the position of a and b, i.e. \(\phi _{(j_{1}, \ldots , j_{m} )}(a) \) and \(\phi _{(j_{1}, \ldots , j_{m} )}(b) \). We construct a new vector \((i_{1}, \ldots , i_{m})\in \Pi _{m}\) by just interchanging the position of a and b and leaving unchanged the positions of all the other components of the vector. By (11), one has that \(N^{(m)} (j_{1}, \ldots , j_{m} )\) gives a positive contribution to \(n_{a} (A)\) if and only if \(N^{(m)} (i_{1}, \ldots , i_{m} )\) gives a positive contribution to \(n_{b} (A)\). We conclude the proof by observing that, under the voting situation \(\ell \textcircled {+} {\mathcal {N}}^{(m)} \), the numbers \(n_{a} (A)\) and \(n_{b} (A)\) are incremented by the same amount, i.e. \(\ell \) multiplied by the cardinality of the set
\(\square \)
It is also useful to state the following result, whose proof is obvious.
Proposition 4
Let \({\mathcal {N}}^{(m)}\) and \(\mathcal {N'}^{(m)} \) be two voting situations. Then, for any \(A\subseteq [m] \) and \(i \in A\), the number of votes for i, under the voting situation \({\mathcal {N}}^{(m)} +\mathcal {N'}^{(m)}\) and when A is the set of candidates, is equal to \(n_i (A)+n'_i (A)\).
Now we proceed by proving that the result in Theorem 1 can be extended to the set \(\Sigma ^{(m)}\) of all possible ranking patterns.
On this purpose, we associate to a ranking pattern \(\varvec{\sigma }\in \Sigma ^{(m)}\) the index \({\mathfrak {I}} (\varvec{\sigma })\) to be defined as follows.
For \(\varvec{\sigma }\in \Sigma ^{(m)}\), \(A\subseteq [m]\) with \(|A|\ge 2\) and \(\ell \in [|A|]\), consider the subset of A defined by
and put
Now set
Notice that for given \(\varvec{\sigma }\) the index \(\eta (\varvec{\sigma },A)\) counts the number of ties among the elements of A and \({\mathfrak {I}}(\varvec{\sigma })\) counts the total number of ties among elements when all the sets \(A \subseteq [m]\) are considered. \({\mathfrak {I}}(\varvec{\sigma })\) can then be called index of weakness of \(\varvec{\sigma }\). Concerning the possible values for \({\mathfrak {I}}(\varvec{\sigma }) \), notice that \({\mathfrak {I}}(\varvec{\sigma })=0\) if and only if \(\varvec{\sigma }\in {\hat{\Sigma }}^{(m)}\) and \({\mathfrak {I}}(\varvec{\sigma })=\sum _{\ell =2}^{m} \left( {\begin{array}{c}m\\ \ell \end{array}}\right) (\ell -1)\) when all the candidates in A are equivalent for any \(A \subseteq [m] \).
In view of the proof of next theorem, we partition the set \(\Sigma ^{(m)}\) as the union of the subsets
Theorem 2
For any \(m \in {\mathbb {N}}\) and for any \(\varvec{\sigma }\in \Sigma ^{(m)}\), there exists a voting situation \({\mathcal {N}}^{(m)}\) which is q-concordant with \(\varvec{\sigma }\).
Proof
The theorem will be proven by induction on the index \({\mathfrak {c}}\). As first step of the induction, where \(\Sigma _{0}^{(m)}={{\hat{\Sigma }}}^{(m)}\), the validity of the claim is guaranteed by Theorem 1.
As an inductive hypothesis we assume, for \(k\in {\mathbb {N}}\cup \{0\}\), the existence of q-concordant voting situations for any \(\varvec{\sigma }\in {\Sigma }_{k}^{(m)}\) and we aim to prove the existence of q-concordant voting situations for any \(\varvec{\sigma }\in {\Sigma }_{k+1}^{(m)}\).
In what follows this task will be achieved by constructing, for any \(\varvec{\sigma }\in {\Sigma }_{k+1}^{(m)}\), two ranking patterns \(\varvec{\sigma ^{\prime }},\,\varvec{\sigma ^{\prime \prime }}\in {\Sigma }_{k}^{(m)}\) suitably constructed in terms of \(\varvec{\sigma }\). We can consider voting situations \({\mathcal {N}}_{1}^{(m)}\), \({\mathcal {N}}_{2}^{(m)}\), respectively, q-concordant with \(\varvec{\sigma ^{\prime }}\) and \(\varvec{\sigma ''}\) whose existence is guaranteed by the inductive hypothesis. Starting from \({\mathcal {N}}_{1}^{(m)}\), \({\mathcal {N}}_{2}^{(m)}\) we will construct a voting situation \({\mathcal {N}}^{(m)}\) in such a way to be q-concordant with \(\varvec{\sigma }\).
We now proceed by constructing \(\varvec{\sigma ^{\prime }}\) and \(\varvec{\sigma ''}\) as announced above. For fixed \(\varvec{\sigma }\in {\Sigma }_{k+1}^{(m)}\) select a set \(A\subseteq [m]\) and an \(\ell \in [|A|]\) such that \(S(\varvec{\sigma },A,\ell )\) has cardinality larger or equal than two. The existence of such a set \(S(\varvec{\sigma },A,\ell )\) is guaranteed by the condition \({\mathfrak {I}}(\varvec{\sigma })= k+1\ge 1\). Fix \(j\in S(\varvec{\sigma },A,\ell )\) and construct \(\varvec{\sigma ^{\prime }}\) and \(\varvec{\sigma ^{\prime \prime }}\) as follows. For \(B\subseteq [m]\) with \(B\ne A\) set
For any \(h\in A\) such that \(\sigma (A,h)\ne \ell \) we again require
For any \(i\in S(\varvec{\sigma },A,\ell ) \setminus \{j \}\) we set
and
Similarly, for any \(i\in S(\varvec{\sigma },A,\ell ) {\setminus }\{j \}\), we set
and
Notice that such a construction guarantees the condition \({\mathfrak {I}} (\varvec{\sigma ^{\prime }})={\mathfrak {I}}(\varvec{\sigma ^{\prime \prime } })=k\) and, in view of the inductive hypotheses, it is possible to find out two voting situations \({\mathcal {N}}_{1}^{(m)}\) and \({\mathcal {N}}_{2}^{(m)}\) such that \({\mathcal {N}}_{1}^{(m)}\) is q-concordant with \(\varvec{\sigma ^{\prime }}\) and \({\mathcal {N}}_{2}^{(m)}\) is q-concordant with \(\varvec{\sigma ^{\prime \prime }}\).
Denote by \(n_{i}^{\prime }(A),n_{i}^{\prime \prime }(A)\) the number of votes obtained by \(i\in A\), respectively, under \({\mathcal {N}}_{1}^{(m)}\) and \({\mathcal {N}}_{2}^{(m)}\), when A is the set of candidates. The above construction guarantees the conditions \(n_{i}^{\prime }(A)>n_{j}^{\prime }(A)\) and \(n_{i}^{\prime \prime }(A)<n_{j}^{\prime \prime }(A)\). In their turn, such conditions allow us, for those \(i,j\in S(\varvec{\sigma },A,\ell ) \) with \(\sigma (A,i)=\ell \) and \(i\ne j\), to consider the position
which defines a bona-fide voting situation. It remains to prove that \({{\mathcal {N}}}^{(m)}\) is q-concordant with \(\varvec{\sigma }\), as required.
As in the proof of Proposition 3 and by Proposition 4, the number of votes obtained by i, under \({\mathcal {N}}^{(m)}\), when A is the set of candidates, is given by
analogously
Therefore all the candidates belonging to \(S(\varvec{\sigma },A,\ell )\) obtain, according to \({{\mathcal {N}}}^{(m)}\), the same number of votes when the set of candidates is A.
By construction of \({\mathcal {N}}^{(m)}\), all the other relations of equality or inequality within pairs of candidates, respectively, coincide with those induced by \({\mathcal {N}} _{1}^{(m)}\) and \({\mathcal {N}}_{2}^{(m)}\). Therefore, by Propositions 3 and 4, \({\mathcal {N}}^{(m)}\) is q-concordant with \(\varvec{\sigma }\). \(\square \)
By recalling the Proposition 2 of Sect. 2, one can immediately obtain the following consequence of the above result concerning with the notion of ranking pattern p-concordant with a m-tuple of random variables.
Corollary 1
For any ranking pattern \(\varvec{\sigma }\in \) \(\Sigma ^{\left( m\right) }\), one can find a m-tuple of random variables \(X_{1},...,X_{m}\) such that \(\varvec{\sigma }\) is p-concordant with \(\left( X_{1},...,X_{m}\right) \).
In the next example we employ the method, developed in the above proof, to build a voting situation q-concordant with a weak ranking pattern by applying suitable operations over voting situations q-concordant with strict ranking patterns.
Example 2
Let \(m=3\) and consider the weak ranking pattern \(\varvec{\tilde{\sigma }}\) defined as follows:
Consider furthermore the two strict ranking pattern \(\varvec{\sigma }^{\prime }\) and \(\varvec{\sigma }^{\prime \prime }\) that coincide with \(\varvec{{\tilde{\sigma }} }\) everywhere except for the following values
and
A voting situation \({\mathcal {N}}'\) q-concordant with \(\varvec{\sigma }^{\prime }\) is
A voting situation \({\mathcal {N}}''\) q-concordant with \(\varvec{\sigma }^{\prime \prime }\) is
A voting situation \(\tilde{{\mathcal {N}}}\) q-concordant with \(\varvec{\tilde{\sigma }}\) can be obtained by operating over the afore-mentioned voting situations \({\mathcal {N}}'\) and \({\mathcal {N}}''\), according to the method developed in the proof of Theorem 2. More precisely, we apply the formula (23) to the special case \(A=\{1,2\},j=1,i=2\). Noticing that
from formula (23) one obtains
whence
4 On the number of voters for q-concordant voting situations
A classical issue in voting theory is the analysis of the number of voters required for obtaining voting situations which may give rise to selected types of voting paradoxes (see in particular Erdos and Moser 1964; Stearns 1959). In this section we point out some general aspects concerning numbers \(n({\mathcal {N}}^{\left( m\right) })\) (as defined by (13) above) for voting situations \({\mathcal {N}}^{\left( m\right) }\) q-concordant with ranking patterns. Still in this analysis, it is convenient to separate between the two cases of strict or general ranking patterns. The latter case will be considered first and a related result will be based on Theorem 2. Later on we turn to considering the case of strict ranking patterns, where one can rely on Theorem 2 of De Santis and Spizzichino (2023) (see also the Appendix). As it may be expected, more precise and stronger results will be obtained in such a case. In order to formulate our results we need the following notation. Let \(m \in {\mathbb {N}}\) be fixed. In other words, we fix the set [m] of possible candidates and define the sets \(\Theta _m \) and \( {{\hat{\Theta }}}_m\) as follows.
analogously
Let \(\varvec{\sigma }\) \(\in \Sigma ^{\left( m\right) }\) be an arbitrary ranking pattern and assume the presence of \( \theta \) voters, with \(\theta \) belonging to \(\Theta _{m}\). It is assured, in this case, that the different linear preference rankings (i.e. the different elements of \(\Pi _{m}\)) can be distributed in such a way to produce a voting situation q-concordant with \(\varvec{\sigma }\). One can then wonder if such an integer \(\theta \) can really exist. We are going to check that \(\Theta _{m}\) is a non-empty set, containing infinite elements. It is furthermore obvious from the above definition that \(\Theta _{m}\subseteq {\hat{\Theta }}_{m}\).
Theorem 3
For any \(m \in {\mathbb {N}}\) the following claims hold
-
(i)
\( \Theta _m\) is non-empty;
-
(ii)
any \(\theta \in \Theta _m\) is a multiple of \({{\,\textrm{lcm}\,}}\{ 2, \ldots , m \}\);
-
(iii)
if \(\theta \in \Theta _m\) then \((\theta + m !) \in \Theta _m \).
Proof
We start by proving (i). By Theorem 2, for \(\varvec{\sigma } \in \Sigma ^{(m)}\) one can select a voting situation \( {\mathcal {N}}_{\varvec{\sigma }}^{(m)} \) q-concordant with \(\varvec{\sigma }\) and, by recalling the position (13), set \(n_{\varvec{\sigma }}:=n\left( {\mathcal {N}}_{\varvec{\sigma }}^{(m)}\right) \). Set furthermore
By Proposition 3, the voting situation \(\frac{a\left( m\right) }{n_{\varvec{\sigma }}}\times {\mathcal {N}}_{\varvec{\sigma }}^{(m)}\) is q-concordant with \(\varvec{\sigma }\) as well. Moreover,
Thus \(a (m) \in \Theta _{m}\) and \(\Theta _{m}\) is non-empty.
Proof of (ii). Let \(A \subseteq [m ] \) with \(|A|=k \in \{2, \ldots , m\}\) and consider the special ranking pattern \(\hat{ \varvec{\sigma } }\in \Sigma ^{(m)}\) such that \({\hat{\sigma }} (A, i) =1 \) for any \(i \in A\). Therefore, for any voting situation \( {\mathcal {N}}_{\hat{ \varvec{\sigma }}}^{(m)} \) q-concordant with \(\hat{ \varvec{\sigma }}\), the integer \(n_{\hat{\varvec{\sigma }} } \) should be a multiple of k. Thus all the elements of \(\Theta _m\) are multiples of \({{\,\textrm{lcm}\,}}\{ 2, \ldots , m \}\).
Proof of (iii). In view of (i) we can fix \(\theta \in \Theta _{m}\). For \(\varvec{\sigma }\in \Sigma ^{(m)}\), let \({\mathcal {N}}_{\varvec{\sigma } }^{(m)}\) be a voting situation q-concordant with \(\varvec{\sigma }\) and such that \(n_{\varvec{\sigma }} =\theta \). By Proposition 3, 1\(\textcircled {+}{\mathcal {N}} _{\varvec{\sigma }}^{(m)}\) is q-concordant with \(\varvec{\sigma }\), as well. The proof can thus be concluded by noticing that \(n(1 \textcircled {+} {\mathcal {N}}_{\varvec{\sigma }}^{(m)})=m!+n({\mathcal {N}} _{\varvec{\sigma }}^{(m)})=m!+\theta \). \(\square \)
As a consequence of items (i) and (iii) of Theorem 3 it is seen that, for whatever \(m \in {\mathbb {N}}\), the set \(\Theta _m\) contains infinite natural numbers.
We now turn to specifically consider the set \( {{\hat{\Theta }}}_m \). As next Theorem 4 shows, it is possible in this case to explicitly determine an element \({\bar{\theta }}_m \in {{\hat{\Theta }}}_m \) and, furthermore, to check that all the integers large enough are eventually contained in \( {{\hat{\Theta }}}_m \). On this purpose it is necessary, once again, to rely on Theorem 2 of De Santis and Spizzichino (2023) and on the arguments contained in Appendix. Set
where
We notice that the integer \(z_{m}\) is such that, for the quantities \(\varepsilon (2),...,\varepsilon (m)\) introduced in (46) of Appendix one has \(\varepsilon (h)=z_{m}^{-h+1}\).
Theorem 4
For any \(m \in {\mathbb {N}}\) one has
-
(i)
the integer \(\bar{\theta }_{m}\) belongs to \({\hat{\Theta }} _{m}\);
-
(ii)
each integer \(\theta \ge \bar{\theta }_{m}\cdot m!\) belongs to \({\hat{\Theta }}_{m}\).
Proof
By Theorem 2 of De Santis and Spizzichino (2023) and Corollary 2 in Appendix, for a given \(\varvec{\sigma }\in {{\hat{\Sigma }}}^{(m)}\) the \(LS(\varvec{\varepsilon },\varvec{\sigma })\) model with
is p-concordant with \(\varvec{\sigma }\). By (41), (44) and (48), we can write an explicit formula for the probabilities \(p_m (j_1, \ldots , j_m)\)’s related to such a model. For any \((j_1, \ldots , j_m) \in \Pi _m \),
By (48), the k-th term of the previous product is
The numerator and denominator of (29) are integers. Thus, multiplying by the denominator
the ratio (29), one obtains an integer number. Noticing that
the Eq. (28) yields for \((j_1, \ldots , j_m) \in \Pi _m\)
The integer \({\bar{\theta }}_m:= \prod _{h=2}^m[h z_m^{h-1}- \frac{h(h-1)}{2}] \) does not depend on \(\varvec{\sigma }\), hence \({\bar{\theta }}_m \in {{\hat{\Theta }}}_m\), by Proposition 2.
We now prove (ii). Let us label by \({\textbf{j}}_1, {\textbf{j}}_2, \ldots , {\textbf{j}}_{m!} \) the elements in \(\Pi _m \). For a given \(\varvec{\sigma }\in {{\hat{\Sigma }}}^{(m)}\) we consider the voting situations \({\mathcal {N}}^{(m)}_{\varvec{\sigma }, {\bar{\theta }}_m }\) q-concordant with \(\varvec{\sigma }\) and such that \( n( {\mathcal {N}}^{(m)}_{\varvec{\sigma }, {\bar{\theta }}_m } ) =\bar{\theta }_m \). For \(c \in {\mathbb {N}}\) we now consider the voting situation \( {\mathcal {N}}^{(m)}_{\varvec{\sigma }, c \cdot {\bar{\theta }}_m } = c \times {\mathcal {N}}^{(m)}_{\varvec{\sigma }, {\bar{\theta }}_m} \).
Thus the following condition
is satisfied when the quantities \(n_i(A)\) and \(n_j (A)\) are those related to \( {\mathcal {N}}^{(m)}_{\varvec{\sigma }, c \cdot \bar{\theta }_m }\). For \(\theta >\bar{\theta }_m \cdot m!\) we will construct a voting situation
q-concordant with \(\varvec{\sigma } \) and such that \(n ({\mathcal {N}}^{(m)}_{\varvec{\sigma }, \theta }) = \theta \). Let
where
Let us check that \( n({\mathcal {N}}^{(m)}_{\varvec{\sigma }, \theta } )=\theta \):
Now fix \(\theta \) as a multiple of m! and such that \( \theta \ge {\bar{\theta }}_m \cdot m!\). In such a case the voting situation \({\mathcal {N}}^{(m)}_{\varvec{\sigma }, \theta }\) (defined by (33)) coincides with
Thus, by Proposition 3, \({\mathcal {N}}^{(m)}_{\varvec{\sigma }, \theta }\) is q-concordant with \(\varvec{\sigma }\) as well.
We now consider a \(\theta ' > {\bar{\theta }}_m \cdot m ! \) which is not a multiple of m!. We consider
The condition (32), with \(c = m!\), is satisfied with \(n_i(A)\) and \(n_j (A)\) that are quantities related to \({\mathcal {N}}^{(m)}_{\varvec{\sigma }, \theta }\). In order to conclude the proof it is enough to notice that, being \(\sum _{i=1}^{m!} \chi _i \le m ! -1\), all the inequalities between \(n_i(A)\) and \(n_j (A)\) are maintained for the voting situation \({\mathcal {N}}^{(m)}_{\varvec{\sigma }, \theta ' }\). \(\square \)
For a strict ranking pattern \(\varvec{\sigma }\in {\hat{\Sigma }}^{(m)}\) not only we know that voting situations exist which are q-concordant and are based on \(\bar{\theta }_{m}\) voters, as guaranteed by the preceding result, but we can also produce explicitly one of such voting situations by letting
As a matter of fact, the next result will be proven by just rephrasing arguments contained in the proof of Theorem 4.
Theorem 5
For any integer \(m\ge 2\), for any \(\varvec{\sigma }\in {\hat{\Sigma }}^{(m)}\), the voting situation \({\mathcal {N}}_{\varvec{\sigma },\bar{\theta }}^{(m)}:=\{N^{(m)}(j_{1},\ldots ,j_{m}):(j_{1},\ldots ,j_{m} )\in \Pi _{m}\}\) with \(N^{(m)}(j_{1},\ldots ,j_{m})\) defined by (34) is q-concordant with \(\varvec{\sigma }\) and \(n({\mathcal {N}}_{\varvec{\sigma },\bar{\theta }_{m}}^{(m)})=\bar{\theta }_{m}\).
Proof
For any \((j_{1},\ldots ,j_{m})\in \Pi _{m}\) the quantity \(N^{(m)}(j_{1},\ldots ,j_{m})\) in (34) coincides with the product \(p_m (j_1, \ldots , j_m) \cdot {\bar{\theta }}_m\) in (31). By Theorem 7 in the Appendix and by (47) we know that the model \(LS(\varvec{\varepsilon },\varvec{\sigma })\) is p-concordant with \(\varvec{\sigma }\). By applying Proposition 2 we obtain that \({\mathcal {N}} _{\varvec{\sigma },\bar{\theta }_{m}}^{(m)}\) is q-concordant with \(\varvec{\sigma }\). The claim \(n({\mathcal {N}}_{\varvec{\sigma },\bar{\theta }_{m}}^{(m)})=\bar{\theta }_{m}\) immediately follows by (31). \(\square \)
The above result then suggests a procedure, for constructing a q-concordant voting situation starting from a strict ranking pattern. Such a procedure will be applied in the next example. For the resulting voting situation, the corresponding number of voters is typically very large. One can however carry out some procedure to pass to a different q-concordant voting situation, in which the number of voters can be drastically reduced. On this purpose the operations on the voting situations, as defined in Sect. 3, can be conveniently used.
Example 3
For \(m=3\) consider the strict ranking pattern \(\varvec{\sigma }\) defined as follows:
Starting from above result and from the operations defined in Sect. 3, one can single out the following voting situation with \(n=43\) voters:
5 Discussion and concluding remarks
In this paper we have considered a standard context of voting theory based on a family of possible elections with a fixed set of voters and a fixed set of potential candidates. The different elections are, respectively, characterized by different subsets of participating candidates and, looking at the differences among their respective outcomes, attention has been focused on the concept of voting situation q-concordant with a ranking pattern. For such voting situations we have obtained results concerning with the issues of existence and construction and with cardinalities of the related voters’ populations. Such results aim to show that it is possible to observe any arbitrary set of elections’ outcomes and they thus lead to conclusions in the same direction of classical results by Saari (see e.g. Saari 1989).
For our developments we have used results based on the concept of ranking pattern p-concordant with probability models for non-negative random variables and on a special class of load-sharing models, as presented in De Santis and Spizzichino (2023).
In our analysis we have distinguished between the two cases of weak or strict ranking patterns, aiming to highlight the differences between the two cases. Obviously, the cardinality \(|{\hat{\Sigma }}^{(m)}|\) of the set of all the strict ranking patterns is smaller than \(|\Sigma ^{(m)}|\). In particular we point out the following relations:
where the last inequality can be explained by noticing that the term \(\left( {\begin{array}{c}m\\ h\end{array}}\right) \) denotes the number of subsets of [m] with cardinality h and \(h^{h}\) is the total number of functions \(\sigma (A,\cdot ):A\rightarrow \{1,2,\ldots ,|A|\}\), which are not necessarily ranking functions.
Constructive and quantitative results have been given in a closed form in the case of strict ranking patterns, whereas the results for the weak case are not in a closed form.
In this respect, however, a main implication of our work is shown in the above Corollary 1 and concerns with the existence of probability models p-concordant with weak ranking patterns. In fact, the passage to the setting of voting theory allows us to extend an existence result, given in De Santis and Spizzichino (2023), from the strict case to the weak case. More in details this issue will be discussed in the next Remark 3. Such an extension may have interesting applications also to the analysis of paradoxes arising in different fields of probability such as the context of intransitive dice, the classic games based on the occurrence of competing events in a sequence of trials, times of first occurrence for different words in random sampling of letters from an alphabet (see e.g. De Santis 2021; De Santis and Spizzichino 2012; Guibas and Odlyzko 1981).
Remark 3
For given \(m\ge 2\), let \(\varvec{\sigma }\in \Sigma ^{(m)}\) be a given weak ranking pattern. By means of Theorems 1 and 2, existence has been proven for a voting situation \({\mathcal {N}}_{\varvec{\sigma }}^{(m)}\equiv \) \(\{N_{\varvec{\sigma }}^{(m)}(j_{1},\ldots ,j_{m}):(j_{1},\ldots ,j_{m} )\in \Pi _{m}\}\) q-concordant with \(\varvec{\sigma }\). In view of Proposition 2, we know that a probability model p-concordant with \(\varvec{\sigma }\) is one satisfying the condition (20).
The existence of a load-sharing model satisfying such a condition, on the other hand, is guaranteed by Theorem 1 in the previous article (De Santis and Spizzichino 2023). We can thus conclude that, for any \(\varvec{\sigma }\in \Sigma ^{(m)}\), there exists a (order dependent) load-sharing model p-concordant with \(\varvec{\sigma }\).
Such a conclusion then fills a gap, present in De Santis and Spizzichino (2023), where the existence of a survival model p-concordant with \(\varvec{\sigma }\) was only guaranteed for the case of a strict ranking pattern.
A few examples, which illustrate other aspects of our results have been presented in the previous sections. More precisely, Example 1 presents an application of Proposition 2 and illustrates how the latter establishes a bridge between the two notions of p-concordance and q-concordance. We remind that p-concordance refers to m-tuples of lifetimes, whereas q-concordance refers to voting situations.
The method developed in the proof of Theorem 2 has been employed in Example 2 to build a voting situation q-concordant with a weak ranking pattern by applying suitable operations over voting situations q-concordant with strict ranking patterns.
In Example 3 a strict ranking pattern \(\varvec{\sigma }\) is considered and Theorem 5 is applied for constructing a q-concordant voting situation.
In the following example we construct a q-concordant voting situation in correspondence with any weak ranking pattern manifesting a very special set of equivalence relations.
Example 4
Here we consider the class of the weak ranking patterns \(\varvec{\sigma }\) such that, for any \(A\subseteq [m]\) with \(|A|\ge 3\),
and, for the rest, presenting arbitrary behavior on the subsets A with \(|A|=2\).
In other words, this class of ranking patterns gives rise to an extreme case where arbitrary outcomes are admitted as far as elections with exactly two candidates are considered, whereas all the candidates are perfectly equivalent in all the elections with more than two candidates. For any such \(\varvec{\sigma }\) we aim to determine a q-concordant voting situation. Notice that the solution of this problem might be seen as a reinforcement of the classical result by McGarvey (1953). A simple solution is given by the voting situation
with
Notice that the total number of voters here is \(n( {\mathcal {N}} ^{(m)}) =m!\). In particular, by taking \(m=4\) and
we obtain a q-concordant voting situation \( {\mathcal {N}} ^{(4)} \) such that \(n( {\mathcal {N}} ^{(4)}) =24 \) and
References
Alon, N.: Voting paradoxes and digraphs realizations. Adv. Appl. Math. 29(1), 126–135 (2002)
De Santis, E.: Ranking graphs through hitting times of Markov chains. Random Struct. Algorithms 59, 189–203 (2021)
De Santis, E., Spizzichino, F.: First occurrence of a word among the elements of a finite dictionary in random sequences of letters. Electron. J. Probab. 17(25), 9 (2012)
De Santis, E., Spizzichino, F.: Construction of aggregation paradoxes through load-sharing models. Adv. Appl. Probab. 55(1), 223–244 (2023)
De Santis, E., Malinovsky, Y., Spizzichino, F.: Stochastic precedence and minima among dependent variables. Methodol. Comput. Appl. Probab. 23, 187–205 (2021)
Erdos, P., Moser, L.: On the representation of directed graphs as unions of orderings. Magyar Tud. Akad. Mat. Kutató Int. Közl. 9, 125–132 (1964)
Fishburn, P.C.: Inverted orders for monotone scoring rules. Discrete Appl. Math. 3(1), 27–36 (1981)
Gehrlein, W.V., Lepelley, D.: Elections, Voting Rules and Paradoxical Outcomes. Studies in Choice and Welfare. Springer, Cham (2017)
Guibas, L.J., Odlyzko, A.M.: String overlaps, pattern matching, and nontransitive games. J. Comb. Theory Ser. A 30(2), 183–208 (1981)
Hazla, J., Mossel, E., Ross, N., Zheng, G.: The probability of intransitivity in dice and close elections. Probab. Theory Relat. Fields 178, 951–1009 (2020)
Kalai, G.: Social indeterminacy. Econometrica 72(5), 1565–1581 (2004)
Klamler, C.: Borda and Condorcet: some distance results. Theory Decis. 59, 97–109 (2005)
Mala, J.: On \(\lambda \)-majority voting paradoxes. Math. Soc. Sci. 37(1), 39–44 (1999)
McGarvey, D.C.: A theorem on the construction of voting paradoxes. Econometrica 21, 608–610 (1953)
Montes, I., Rademaker, M., Perez-Fernandez, R., De Baets, B.: A correspondence between voting procedures and stochastic orderings. Eur. J. Oper. Res. 285, 977–987 (2020)
Nurmi, H.: Voting Paradoxes and How to Deal with Them. Springer, Berlin (1999)
Perez-Fernandez, R., De Baets, B.: The superdominance relation, the positional winner, and more missing links between Borda and Condorcet. J. Theor. Politics 31, 46–65 (2019)
Saari, D.G.: A dictionary for voting paradoxes. J. Econ. Theory 48(2), 443–475 (1989)
Saari, D.G.: A chaotic exploration of aggregation paradoxes. SIAM Rev. 37(1), 37–52 (1995)
Saari, D.G.: Discovering aggregation properties via voting. In: Batchelder, W.H., Colonius, H., Dzhafarov, E.N. (eds.) New Handbook of Mathematical Psychology, vol. 2, pp. 271–321. Cambridge University Press, Cambridge (2018a)
Saari, D.G.: Mathematics Motivated by the Social and Behavioral Sciences. SIAM, Philadelphia (2018b)
Shaked, M., Shanthikumar, J.G.: Stochastic Orders and Their Applications. Probability and Mathematical Statistics. Academic Press, Inc., Boston (1994)
Shaked, M., Shanthikumar, J.G.: Multivariate conditional hazard rate functions: an overview. Appl. Stoch. Models Bus. Ind. 31(3), 285–296 (2015)
Spizzichino, F.: Reliability, signature, and relative quality functions of systems under time-homogeneous load-sharing models. Appl. Stoch. Models Bus. Ind. 35(2), 158–176 (2019)
Stearns, R.: The voting problem. Am. Math. Mon. 66, 761–763 (1959)
Van Newenhizen, J.: The Borda method is most likely to respect the Condorcet principle. Econ. Theory 2, 69–83 (1992)
Acknowledgements
We thank two anonymous Referees for interesting and helpful comments. Partially supported by Ateneo Sapienza Project Simmetrie e Disuguaglianze in Modelli Stocastici (2018). The second author is a member of the GNAMPA research group of INdAM (Istituto Nazionale di Alta Matematica).
Funding
Open access funding provided by Universitá degli Studi di Roma La Sapienza within the CRUI-CARE Agreement.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix
Appendix
In this Appendix we consider random variables \(X_{1},\dots ,X_{m}\) that admit an absolutely continuous joint probability distribution. Such a joint distribution can be also described in terms of the family of the Multivariate Conditional Hazard Rate (m.c.h.r.) functions, defined as follows: for \(1\le k<m,i_{1}\) \(\ne i_{2}\ne ...\ne i_{k}\in \left[ m\right] ,0\le t_{1}<t_{2}<...<t_{k}\le t\),
For definitions and properties of m.c.h.r. functions see in particular (Shaked and Shanthikumar 1994), the review paper (Shaked and Shanthikumar 2015) and, e.g., (Spizzichino 2019) and other references cited therein.
As pointed out in De Santis et al. (2021) and De Santis and Spizzichino (2023), the system of the m.c.h.r. functions is convenient to analyze some aspects of the quantities \(\alpha _{j}(A)\) defined in (4).
We focus on the special cases when the m-tuple \(\left( X_{1},\ldots ,X_{m}\right) \) is distributed according to a order dependent load-sharing model, i.e. when, for \(k\in [ m-1]\), for distinct \(i_{1},\ldots ,i_{k},j\in [m]\) and for an ordered sequence \(0<t_{1}<\cdots<t_{k}<t,\) one has
where \(\mu _{j}(i_{1},\ldots ,i_{k})\) and \(\mu _{j}(\emptyset )\) are non-negative quantities.
It is in particular interesting the case when the functions \(\mu _{j}(i_{1},\ldots ,i_{k})\) do not depend on the order of the components of the vector \((i_{1},\ldots ,i_{k})\). Such a case has been designated by the term non-order dependent load sharing and, with a minor abuse of notation, sometime we write \(\mu _{j}(I)\), with \(I=\{i_{1},\ldots ,i_{m}\}\), in place of \(\mu _{j}(i_{1},\ldots ,i_{k})\).
For a fixed family \({\mathcal {M}}\) of parameters \(\mu _{j}\left( \emptyset \right) \) and \(\mu _{j}(i_{1},\ldots ,i_{k})\) as in (38), for \(k\in \left[ m-1\right] \) and for \(i_{1}\ne \ldots \ne i_{k}\), set
As a relevant property of the corresponding load sharing model, one has \({\mathbb {P}}(J_{1}=j)=\frac{\mu _{j}(\emptyset )}{M(\emptyset )}\) and
(see also Spizzichino 2019; De Santis et al. 2021). Concerning with the joint probability distribution of \({\textbf{J}}\equiv \left( J_{1},...,J_{m}\right) \) one immediately obtains the following consequence, for \(h=2,...,m\):
See also Spizzichino (2019). Now we need to introduce the following notation.
For \(B \subset [m]\) and \(k = 1, \ldots , m -|B|\) let us define
When \(k=m-|B|\), \({\mathcal {D}}(B,k)\) is then the set of all the permutations of the elements of \(B^{c}\). In particular the set \({\mathcal {D}}(\emptyset ,m)\) becomes \(\Pi _{m}\).
Concerning with the probabilities \(\alpha _{j}(A)\) in the case of a load-sharing models, the following equation is readily obtained by combining relation (41) with Proposition 1 in De Santis and Spizzichino (2023):
Let now \(\varvec{\sigma }\in {\hat{\Sigma }}^{(m)}\) be an assigned strict ranking pattern and let \(\varepsilon (2),...,\varepsilon (m)\) be positive quantities such that \(\ (\sigma (A,i)-1)\varepsilon (|A|)<1\) for all \(A\subseteq \left[ m\right] \) and \(i\in A\).
Starting from \(\varvec{\sigma }\), in De Santis and Spizzichino (2023) a special class of load-sharing models has been defined by imposing parameters of the following form
For \(A=\{i\}\) we finally set \(\mu _{i}([m]\setminus A)=1\) and \(\varepsilon (1)=0\). The load-sharing model corresponding to such a choice of parameters is designated by the symbol \(LS\left( \varvec{\varepsilon },\varvec{\sigma }\right) \).
The interest in such a special class is justified by the following existence result.
Theorem 6
For \(m\in {\mathbb {N}}\), let \(\varvec{\sigma }\in {\hat{\Sigma }}^{(m)}\) be a ranking pattern. Then there exist constants \(\varepsilon (2),...,\varepsilon (m)\) such that a m-tuple \((X_{1},\ldots ,X_{m})\) distributed according to the model \(LS\left( \varvec{\varepsilon },\varvec{\sigma }\right) \), where \(\varvec{\varepsilon }=\left( 0,\varepsilon (2),...,\varepsilon (m)\right) \), has the following two properties:
-
(1)
it is p-concordant with \(\varvec{\sigma }\)
-
(2)
all the probabilities \(p_{m}(j_{1},\ldots ,j_{m})\) are rational numbers, for \((j_{1},\ldots ,j_{m})\in \Pi _{m}\).
As a matter of fact, the above claim may be obtained as a consequence of the following quantitative result proven in De Santis and Spizzichino (2023). However also a qualitative and autonomous proof will be provided in order to show the possibility of wider choices for \(\varvec{\varepsilon }=\left( 0,\varepsilon (2),...,\varepsilon (m)\right) \) (see below). Such a proof also points out the conceptual reasons way solutions can be found within the class of models of type \(LS\left( \varvec{\varepsilon },\varvec{\sigma }\right) \).
Theorem 7
For any \(\varvec{\sigma }\in {\hat{\Sigma }}\) and any \(\varvec{\varepsilon }=(0,\varepsilon (2),\ldots ,\varepsilon (m))\) such that, for \(\ell =2,...,m-1,\)
the model \(LS(\varvec{\varepsilon },\varvec{\sigma })\) is p-concordant with \(\varvec{\sigma }\).
The inequalities in (45) can be in particular obtained by letting, for \(h=2,...,m\),
For a given \(\varvec{\sigma }\in {\hat{\Sigma }}^{(m)}\), by Theorem 7 and (46) one can thus conclude with the following
Corollary 2
An m-tuple \((X_{1},\ldots ,X_{m})\) distributed according to a \(LS(\varvec{\varepsilon },\varvec{\sigma })\) load-sharing model with parameters of the form
is p-concordant with \(\varvec{\sigma }\).
Notice the following implication of the above formula (43) for a load sharing model described by the family \(\mathcal {M\equiv }\{\mu _{j} (I): I\subset \left[ m\right] , j \not \in I \}\): for given \(A\subseteq \left[ m\right] \), the probabilities \(\{\alpha _{j}(A):j\in A\}\) only depend on \(\{\mu _{j}(I):I\subseteq A^{c},j\not \in I\}\).
Remark 4
Specifically concerning with the case of a \(LS\left( \varvec{\varepsilon },\varvec{\sigma }\right) \) model, we can realize that, for given \(B\subseteq \left[ m\right] \) with \(|B|=n\le m\) and \(j\in B\), the probability \(\alpha _{j}(B)\) only depends on \(\varepsilon (n),\varepsilon (n+1)...,\varepsilon (m)\) and on the functions \(\sigma (D,\cdot )\) for \(D\subseteq \left[ m\right] \) with \(D\supseteq B\).
Notice furthermore that, for an arbitrary choice of \(\varvec{\varepsilon },\varvec{\sigma }\), the \(LS\left( \varvec{\varepsilon },\varvec{\sigma }\right) \) model has the set of numbers \(\mu _{j}([m]\setminus A)\) (for \(j\in A\)) that only depends on the cardinality of A. Thus, by (39) and (44), one has
for \(h\in [m]\) and for any \((i_{1}, \ldots , i_{m-h}) \in {\mathcal {D}} (\emptyset , m-h)\). The formulas (44), (47) and (48) give rise to a specially convenient form for the probability in (41).
We are now in a position to present the proof of Theorem 6.
Proof
Let us fix the given ranking pattern
In what follows we will inductively identify, for \(n=2,\ldots ,m\), a sequence of vectors \(\varvec{\varepsilon }^{\left( n\right) }\equiv \left( \varepsilon ^{(n)}(\ell ))_{\ell =2,\ldots ,m}\right) \) and we will consider the load-sharing models \(LS\left( \varvec{\varepsilon }^{\left( n\right) },\varvec{\sigma }\right) \) with parameters \(\mu _{j}^{( n) }(B)\) determined by (44) through \(\varvec{\sigma }\) and the vectors of coefficients \(\varvec{\varepsilon }^{\left( n\right) }\). In correspondence with \(LS\left( \varvec{\varepsilon }^{\left( n\right) },\varvec{\sigma }\right) \), denote furthermore by \(\alpha _{i}^{(n)}(A)\) (\(i\in A\))) the related quantities as defined in (4).
Along the construction of \(\varvec{\varepsilon }^{\left( n\right) } \equiv \left( \varepsilon ^{(n)}(\ell ))_{\ell =2,\ldots ,m}\right) \), \(n=2,...,m-1\), we will in particular impose the conditions
and notice that, in view of the formula (43) and Remark 4, they imply that
for any A \(\subseteq \left[ m\right] \) with \(|A|>n\).
For \(n=2,\ldots ,m\) consider now the sequence of claims \({\mathcal {H}}(n)\) defined as follows.
\(\varepsilon ^{(n)}(2),\ldots ,\varepsilon ^{(n)}(m)\text { such that }\)
for any A with \(|A|\le n\). Notice that \({\mathcal {H}}(m)\) coincides with the thesis of the theorem.
for any \(A\subseteq [m]\).
The claims \({\mathcal {H}}(n)\) (\(n=2,\ldots ,m\)) will now be proven by induction on n. This procedure will then lead us to obtain the claim \({\mathcal {H}}(m)\), namely the thesis of the Theorem.
In the first induction step \(n=2\) we consider the ranking functions \(\sigma (A,\cdot ) \) with \(A\subseteq [ m] \) and \(|A|=2\).
Initially, we set \(\varepsilon ^{(2)}(2)=\frac{1}{2}\) and \(\varepsilon ^{(2)}(\ell )=0\) for any \(\ell \ge 3\).
In this way, still by formula (43) and Eq. (44), one has that for \(A=\{i,j\}\), with \(i \ne j\), the implication
is satisfied.
This claim immediately follows from the circumstance that \(\varepsilon ^{(2)}(3)=\cdots =\varepsilon ^{(2)}(m)=0\) implies that all the terms, appearing in the summation in (43) are equal each other, excepting
We notice that the previous inequalities \(\alpha _{i}^{(2)}(A)>\alpha _{j} ^{(2)}(A)\) are strict.
Let us now pass, on the other hand, to considering a set \(A\subseteq [m]\) with \(|A|>2\). By (43) and Eq. (44) one has
regardless of the index \(i\in A\).
We now proceed inductively. For given \(n<m\) we maintain (49) and assume the induction hypothesis \({\mathcal {H}}(n)\), guaranteeing the existence of \(\varepsilon ^{(n)}(2),\varepsilon ^{(n)}(3),\ldots ,\varepsilon ^{(n)}(n)\) such that the implication
holds true for any A with \(|A|\le n\). By Remark 4 and due to (49), we again obtain that for any \(A\subseteq [m]\) with \(|A|>n\)
regardless of the index \(i\in A\).
We now want to show that also the claim \({\mathcal {H}}(n+1)\) holds. On this purpose, recalling the condition \(\varepsilon ^{(n+1)}(n+2)=\cdots =\varepsilon ^{(n+1)}(m)=0\), we set
It remains to conveniently choose the positive value \(\varepsilon ^{(n+1)}(n+1)\) in order to get
for any A with \(|A|\le n+1\).
The existence of such a value \(\varepsilon ^{(n+1)}(n+1)>0\) will follow from the inductive hypothesis \({\mathcal {H}}(n)\) and from the fact the probabilities \((\alpha _{i}^{(n+1)}(A))\) are continuous with respect to the collection of the intensities \((\mu _{i}^{(n+1)}(\cdot ))\) and therefore they are also continuous with respect to the collection of the coefficients \(\varepsilon ^{(n+1)}(\ell )\) (\(\ell =2,...,m\)). Thus, by continuity, the validity of (55) is maintained for any A with \(|A|\le n\), provided that \(\varepsilon ^{(n+1)}(n+1)>0\) is sufficiently small.
Notice that the assumption that all the inequalities in (53) are strict is unavoidable here.
Let us now consider the sets A with cardinality \(|A|=n+1\). Having selected such a value \(\varepsilon ^{(n+1)}(n+1)>0\), by (43), we obtain
This formula shows that if \(\sigma (A,i) > \sigma (A,j) \) then \(\alpha _{i} (A ) < \alpha _{j} (A)\). Thus (55) is satisfied also for A with \(|A|=n+1\) and the thesis is proven by induction.
The quantities \(\varepsilon (2), \ldots , \varepsilon (m)\), appearing in the above construction, are only required to be sufficiently small. More precisely, \(\varepsilon (n)\) is only required to belong to a suitable right neighbourhood of zero. Such a neighbourhood will possibly depend on \(\varepsilon (2), \ldots , \varepsilon (n-1)\). Therefore one can select \(\varepsilon (2), \ldots , \varepsilon (m)\in {\mathbb {Q}}_+\). With such a choice also the quantities \(\mu _i([m] \setminus A)\), defined in (44), turn out to be rational, for any \(A \subseteq [m]\) and \(i \in A\). Finally, by (41), one obtains that all the elements of \(\mathbf {P_J}\) are rational as well. \(\square \)
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
De Santis, E., Spizzichino, F. Construction of voting situations concordant with ranking patterns. Decisions Econ Finan 46, 129–156 (2023). https://doi.org/10.1007/s10203-023-00393-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10203-023-00393-2