Uncovering and Displaying the Coherent Groups of Rank Data by Exploratory Riffle Shuffling

Vartan Choulakian, Jacques Allard

Université de Moncton, Moncton, Canada.

DOI: 10.4236/ojs.2021.111010                

Abstract

Let n respondents rank order d items, and suppose that . Our main task is to uncover and display the structure of the observed rank data by an exploratory riffle shuffling procedure which sequentially decomposes the n voters into a finite number of coherent groups plus a noisy group: where the noisy group represents the outlier voters and each coherent group is composed of a finite number of coherent clusters. We consider exploratory riffle shuffling of a set of items to be equivalent to optimal two blocks seriation of the items with crossing of some scores between the two blocks. A riffle shuffled coherent cluster of voters within its coherent group is essentially characterized by the following facts: 1) Voters have identical first TCA factor score, where TCA designates taxicab correspondence analysis, an L₁ variant of correspondence analysis; 2) Any preference is easily interpreted as riffle shuffling of its items; 3) The nature of different riffle shuffling of items can be seen in the structure of the contingency table of the first-order marginals constructed from the Borda scorings of the voters; 4) The first TCA factor scores of the items of a coherent cluster are interpreted as Borda scale of the items. We also introduce a crossing index, which measures the extent of crossing of scores of voters between the two blocks seriation of the items. The novel approach is explained on the benchmarking SUSHI data set, where we show that this data set has a very simple structure, which can also be communicated in a tabular form.

Keywords

Borda Score and Scale, Exploratory Riffle Shuffle, Coherent Group, Coherent Cluster, Crossing Index, Taxicab Correspondence Analysis

1. Introduction

Ordering the elements of a set is a common decision making activity, such as, voting for a political candidate, choosing a consumer product, etc. So there is a huge literature concerning the analysis and interpretation of preference data scattered in different disciplines. Often rank data is heterogenous: it is composed of a finite mixture of components. The traditional methods of finding mixture components of rank data are mostly based on parametric probability models, distance or latent class models, and are useful for sparse data and not for diffuse data.

Rank data are sparse if there are at most a small finite number of permutations that capture the majority of the preferences; otherwise they are diffuse. As a running example in this paper, we will consider the famous benchmarking SUSHI data set enumerating $n=5000$ preferences of $d=10$ sushis, see [1]. The SUSHI data set is diffuse, because there are at most three counts for one observed permutation. It has been analyzed, among others by [2] [3] [4].

A second data set that we shall also analyze is the APA dataset of size $n=5738$ by $d=5$, see [5]. APA data set is also considered as non-sparse by [2], because all the 120 permutations exist with positive probability.

For a general background on statistical methods for rank data, see the excellent monograph by [6] and the book [7].

1.1. Riffle Shuffle

The riffle shuffle, see [8], is considered the most popular method of card shuffling, in which one cuts a deck of d cards (aka items) into two piles of sizes d₁ and d₂, respectively, and successively drops the cards, one by one, so that the piles are interleaved into one deck again.

Let V, named a voting profile, be a set of n preferences on d items. Based on riffle shuffling ideas, [2] proposed the notion of riffled independence to model the joint probability distribution of observed preferences of V. Independently, [9] used it for visual exploration of V, naming it two blocks partition of the Borda scored items with crossing of some scores; this will be further developed here under the following important.

Assumption: $d\ll n$. This means that the sample size n is quite large compared to the number of items d.

SUSHI and APA data sets satisfy this assumption.

The most important first step in the application of a riffle shuffling procedure is how to partition the d items into two disjoint subsets. In the probabilistic riffle shuffling approach of [2], the partitioning step is essentially done using some adhoc approach in the case of the SUSHI data set or based on background second order information of the items in the case of the APA data set. While in the exploratory riffle shuffling approach of this paper an optimal partition is obtained by maximizing the cut norm of row centered data, or equivalently by taxicab correspondence analysis of nega coded data.

We compare the two formulations of riffle shuffle, probabilistic and exploratory, in section 10.

1.2. Aim

Our aim is to explore and display a given voting profile V by sequentially partitioning it into G coherent groups plus a noisy group; that is,

$V={\displaystyle {\cup }_{g=1}^{G}cohG\left(g\right)\cup noisyG}\mathrm{,}$ (1)

where G represents the number of coherent groups and $cohG\left(g\right)$ is the gth coherent group. Furthermore, each coherent group is partitioned into a finite number of coherent clusters; that is,

$cohG\left(g\right)={\displaystyle {\cup }_{\alpha =1}^{c_g}coh{C}_g\left(\alpha \right)}\text{for}g=\mathrm{1,}\cdots \mathrm{,}G\mathrm{,}$ (2)

where $c_g$ represents the number of coherent clusters in the gth coherent group. So the coherent clusters are the building blocks for the coherent groups. We note the following facts:

Fact 1: The assumption $d\ll n$ induces the new notion of coherency for the clusters and consequently for the groups; it is a stronger characterization than the notion of interpretability for groups as discussed in [9].

Fact 2: Each coherent group and its clusters have the same latent variable summarized by the Borda scale.

Fact 3: Given that the proposed method sequentially peels the data like Occam’s razor, the number of groups G is calculated automatically. Furthermore, outliers or uninformative voters belonging to the $noisyG$ are easily tagged.

Fact 4: The approach is exploratory, visual, data analytic and is developed within the framework of taxicab correspondence analysis (TCA). TCA is an L₁ variant of correspondence analysis developed by [10]. TCA is a dimension reduction technique similar to principal component analysis. In this paper, we shall use only the first TCA factor scores of the items and of the voters.

Two major advantages of our method are: First, we can easily identify outliers. For the SUSHI data, our method tags 12.36% of the voters as outliers, which form the noisy group. While no outliers in the SUSHI data have been identified in [3] [4]. Second, it provides a tabular summary of the preferences which compose a coherent group. For instance, consider the first mixture component of the SUSHI data given in [4], where the modal ordering is almost the same as the Borda scale ordering of the ten sushis in cohG(1) obtained by our method, see Table 14 in this paper. The sample size of their first mixture component is 27.56%, which is much smaller than 48.36%, the sample size of our cohG(1), see Table 14. However, Table 13 of this paper provides a tabular-visual summary of the 2418 preferences which form cohG(1). The visual summary describes different kinds of equivalent similar riffle shufflings of the 2418 preferences, and it provides further insight into the structure of the data. Such interesting visual summaries are missing in [3] [4].

1.3. Highlights of a Coherent Cluster

A coherent cluster of voters has interesting mathematical properties and is essentially characterized by the following facts:

1) Voters have identical unique first TCA factor score.

2) Any voter preference is easily interpreted as a particular riffle shuffling of its items.

3) The nature of riffle shuffling of the items can be observed in the structure of the contingency table of the first-order marginals constructed from the Borda scorings of the voters belonging to the coherent cluster.

4) The first TCA factor scores of the items of a coherent cluster are interpreted as Borda scale of the items.

5) We also introduce the crossing index, which measures the extent of interleaving or the crossing of scores of voters between two blocks seriation of the items in a coherent cluster.

1.4. Organization

This paper has eleven sections and its contents are organized as follows: Section 2 presents an overview of TCA; section 3 presents some preliminaries on the Borda coding of the data and related tables and concepts; section 4 presents Theorem 1, which shows that the first principal dimension of TCA clusters the voters into a finite number of clusters; section 5 discusses coherent clusters and their mathematical properties; section 6 discusses riffle shuffling in a coherent cluster; section 7 introduces the crossing index; section 8 introduces the coherent groups; section 9 presents the analysis of APA data set; section 10 presents a comparison of the two formulations of riffle shuffle probabilistic and exploratory; and finally we conclude in section 11.

All mathematical proofs are relegated to the Appendix. Details of the computation are shown only for the first coherent group of SUSHI data set.

2. An Overview of Taxicab Correspondence Analysis

Consider a $n\times p$ matrix $X$ where $X_{ij}\ge 0$. We have ${\displaystyle {\sum }_{j=1}^p}{\displaystyle {\sum }_{i=1}^n}{X}_{ij}=X_{\ast \ast }$. Let $P=X/X_{\ast \ast }$ be the correspondence matrix associated to $X$ ; and as usual, we define $p_{i\ast }={\displaystyle {\sum }_{j=1}^p}{p}_{ij}$, $p_{\ast j}={\displaystyle {\sum }_{i=1}^n}{p}_{ij}$. Let $D_n=Diag\left(p_{i\ast }\right)$ a diagonal matrix with diagonal elements $p_{i\ast }$. Similarly $D_p=Diag\left(p_{\ast j}\right)$. Let $k=rank\left(P\right)-1$.

In TCA the calculation of the dispersion measures $\left({\delta }_{\alpha }\right)$, principal axes $\left(u_{\alpha }\mathrm{,}{v}_{\alpha }\right)$, principal basic vectors $\left(a_{\alpha }\mathrm{,}{b}_{\alpha }\right)$, and principal factor scores $\left(f_{\alpha }\mathrm{,}{g}_{\alpha }\right)$ for $\alpha =\mathrm{1,}\cdots \mathrm{,}k$ is done in a stepwise manner. We put $P_1=\left(p_{ij}^{\left(1\right)}=p_{ij}-p_{i\ast }{p}_{\ast j}\right)$. Let $P_{\alpha }$ be the residual correspondence matrix at the α-th iteration.

The variational definitions of the TCA at the α-th iteration are

$\begin{array}{c}{\delta }_{\alpha }=\underset{u\in {ℝ}^p}{\max }\frac{{\Vert P_{\alpha }u\Vert }_1}{{\Vert u\Vert }_{\infty }}=\underset{v\in {ℝ}^n}{\max }\frac{{\Vert {P^{\prime }}_{\alpha }v\Vert }_1}{{\Vert v\Vert }_{\infty }}=\underset{u\in {ℝ}^p\mathrm{,}v\in {ℝ}^n}{\max }\frac{v^{\prime }{P}_{\alpha }u}{{\Vert u\Vert }_{\infty }{\Vert v\Vert }_{\infty }}\\ =\max {\Vert P_{\alpha }u\Vert }_1\text{subject}\text{to}u\in {\left\{-\mathrm{1,}+1\right\}}^p\\ =\max {\Vert {P^{\prime }}_{\alpha }v\Vert }_1\text{subject}\text{to}v\in {\left\{-\mathrm{1,}+1\right\}}^n\\ =\max v^{\prime }{P}_{a}u\text{subject}\text{to}u\in {\left\{-\mathrm{1,}+1\right\}}^p\mathrm{,}v\in {\left\{-\mathrm{1,}+1\right\}}^n\mathrm{.}\end{array}$

The α-th principal axes are

$u_{\alpha }=\arg \underset{u\in {\left\{-\mathrm{1,}+1\right\}}^p}{\max }{\Vert P_{\alpha }u\Vert }_1\text{and}{v}_{\alpha }=\arg \underset{v\in {\left\{-\mathrm{1,}+1\right\}}^n}{\max }{\Vert {P^{\prime }}_{\alpha }v\Vert }_1\text{,}$ (3)

and the α-th basic principal vectors are

$a_{\alpha }=P_{\alpha }{u}_{\alpha }\text{and}{b}_{\alpha }={P^{\prime }}_{\alpha }{v}_{\alpha }\mathrm{,}$ (4)

and the α-th principal factor scores are

$f_{\alpha }=D_n^{-1}{a}_{\alpha }\text{and}{g}_{\alpha }=D_p^{-1}{b}_{\alpha }\mathrm{<mo>\; ;\; </mo>}$ (5)

furthermore the following relations are also useful

$u_{\alpha }=sgn\left(b_{\alpha }\right)=sgn\left(g_{\alpha }\right)\text{and}{v}_{\alpha }=sgn\left(a_{\alpha }\right)=sgn\left(f_{\alpha }\right)\mathrm{,}$ (6)

where $sgn\left(\mathrm{.}\right)$ is the coordinatewise sign function, $sgn\left(x\right)=1$ if $x>0$, and $sgn\left(x\right)=-1$ if $x\le 0$. The α-th taxicab dispersion measure ${\delta }_{\alpha }$ can be represented in many different ways

$\begin{array}{c}{\delta }_{\alpha }={\Vert P_{\alpha }{u}_{\alpha }\Vert }_1={\Vert a_{\alpha }\Vert }_1={a^{\prime }}_{\alpha }{v}_{\alpha }={\Vert D_n{f}_{\alpha }\Vert }_1={u^{\prime }}_{\alpha }{D}_n{f}_{\alpha }\mathrm{,}\\ ={\Vert {P^{\prime }}_{\alpha }{v}_{\alpha }\Vert }_1={\Vert b_{\alpha }\Vert }_1={b^{\prime }}_{\alpha }{u}_{\alpha }={\Vert D_p{g}_{\alpha }\Vert }_1={v^{\prime }}_{\alpha }{D}_p{g}_{\alpha }\mathrm{.}\end{array}$ (7)

The $\left(\alpha +1\right)$ -th residual correspondence matrix is

$P_{\alpha +1}=P_{\alpha }-D_n{f}_{\alpha }{g^{\prime }}_{\alpha }{D}_p/{\delta }_{\alpha }\mathrm{.}$ (8)

An interpretation of the term $D_n{g}_{\alpha }{f^{\prime }}_{\alpha }{D}_p/{\delta }_{\alpha }$ in (8) is that, it represents the best rank-1 approximation of the residual correspondence matrix $P_{\alpha }$, in the sense of taxicab norm.

In CA and TCA, the principal factor scores are centered; that is,

${\displaystyle \underset{i=1}{\overset{n}{\sum }}}{f}_{\alpha }\left(i\right)p_{i\ast }=0={\displaystyle \underset{j=1}{\overset{p}{\sum }}}{g}_{\alpha }\left(j\right)p_{\ast j}\text{for}\alpha =1,\cdots ,k.$ (9)

The reconstitution formula in TCA and CA is

$p_{ij}=p_{i.}{p}_{.j}\left[1+{\displaystyle \underset{\alpha =1}{\overset{k}{\sum }}}{f}_{\alpha }\left(i\right)g_{\alpha }\left(j\right)/{\delta }_{\alpha }\right].$ (10)

In TCA, the calculation of the principal component weights, $u_{\alpha }$ and $v_{\alpha }$, and the principal factor scores, $g_{\alpha }$ and $f_{\alpha }$, can be accomplished by two algorithms. The first one is based on complete enumeration based on equation (3). The second one is based on iterating the transition formulae (4, 5, 6). This is an ascent algorithm; that is, it increases the value of the objective function at each iteration, see [11]. The iterative algorithm could converge to a local maximum; so it should be restarted from several initial configurations. The rows or the columns of the data can be used as starting values.

The TCA map is obtained by plotting $\left(g_1\mathrm{,}{g}_2\right)$ or $\left(f_1\mathrm{,}{f}_2\right)$.

3. Preliminaries

In this section we review 1) The Borda scoring of a voting profile V into R and the Borda scale; 2) Contingency table of the first order marginals of R; 3) The coded tables $R_{double}$ and $R_{nega}$.

3.1. Borda Scorings and Borda Scale

Let $A=\left\{a_1\mathrm{,}{a}_2\mathrm{,}\cdots \mathrm{,}{a}_d\right\}$ denote a set of d alternatives/candidates/items, and V a set of n voters/individuals/judges. In this paper, we consider the linear orderings/rankings/preferences, in which all d objects are rank-ordered according to their levels of desirability by the n voters. We denote a linear order by a sequence $s=\left(a_{k_1}\succ a_{k_2}\succ \cdots \succ a_{k_d}\right)$, where $a_{k_1}\succ a_{k_2}$ means that the alternative $a_{k_1}$ is preferred to the alternative $a_{k_2}$. The Borda scoring of $s$, see [12], is the vector $b\left(s\right)$ where to the element $a_{k_j}$ the score of $\left(d-j\right)$ is assigned, because $a_{k_j}$ is preferred to $\left(d-j\right)$ other alternatives; or equivalently it is the jth most preferred alternative. Let $R=\left(r_{ij}\right)$ be the matrix having n rows and d columns, where $r_{ij}$ designates the Borda score of the ith voter’s preference of the jth alternative. We note that theith row of $R$ will be an element of $S_d$ the set of permutations of the elements of the set $\left\{\mathrm{0,1,2,}\cdots \mathrm{,}d-1\right\}$. A toy example of $R$ is presented in Table 1 for $n=4$ and $d=3$.

The Borda scale of the elements of A is $\beta ={1^{\prime }}_{n}R/n$, where $1_n$ is a column vector of 1’s having n coordinates. The Borda scale seriates/orders the d items of the set A according to their average scores: $\beta \left(j\right)>\beta \left(i\right)$ means item j is preferred to item i, and $\beta \left(j\right)=\beta \left(i\right)$ means both items $\left(a_i\mathrm{,}{a}_j\right)$ are equally preferred. In the toy example of Table 1, the Borda scale seriates $\left\{A\mathrm{,}B\right\}\succ C$.

Similarly, we define the reverse Borda score of $s$ to be the vector $\bar{b}\left(s\right)$, which assigns to the element $a_{k_j}$ the score of $\left(j-1\right)$. We denote $\bar{R}=\left({\bar{r}}_{ij}\right)$ to be the matrix having n rows and d columns, where ${\bar{r}}_{ij}$ designates the reverse Borda score of the ith judge’s nonpreference of the jth alternative. The reverse Borda scale of the d items is $\bar{\beta }={1^{\prime }}_n\bar{R}/n$.

We note that

$R+\bar{R}=\left(d-1\right)1_n{1^{\prime }}_n$

and

$\beta +\bar{\beta }=\left(d-1\right){1^{\prime }}_d$.

3.2. Contingency Tableof First-Order Marginals

The contingency table of first-order marginals of an observed voting profile V on

Table 1. Toy example with $n=4$ preferences of $d=3$ items.

d items is a square $d\times d$ matrix M, where $M\left(i\mathrm{,}j\right)$ stores the number of times that itemj has Borda score i for $i=0,\cdots ,d-1$, see [ [6], p. 17]. Table 2 displays the matrix M for the toy example R displayed in Table 1. We note the following facts:

1) It has uniform row and column marginals equal to the sample size.

2) We can compute the Borda scale $\beta$ from it.

3) It reveals the nature of crossing of scores attributed to the items for a given binary partition of the items. For the toy example, consider the partition $\left\{C\right\}$ and $\left\{B\mathrm{,}A\right\}$ with attributed scores of $\left\{0\right\}$ and $\left\{\mathrm{1,2}\right\}$ respectively (this is the first step in a riffle shuffle). Then the highlighted cells (marked in bold) in Table 2 show that there are two crossing of scores, permutation (transposition) of the scores 0 and 1, between the sets $\left\{C\right\}$ and $\left\{B\mathrm{,}A\right\}$, (this is the second step in a random shuffle). Furthermore, the third row of Table 2 shows that the score 2 is equally attributed to both items of the set $\left\{B\mathrm{,}A\right\}$ and it never crossed to $\left\{C\right\}$.

3.3. Coded Tables R_double and R_nega

Our methodological approach is based on Benzécri’s platform, see [ [13], p.1113], that we quote: “the main problem inductive statistics has to face is to build tables that, through appropriate coding and eventual supplementation, give to the available data such a shape that the analysis is able to extract from it the answer to any question that we are allowed to ask”. Italics are ours.

There are three elements in Benzécri’s platform: 1) coding, a kind of pre-processing of data, will be discussed in the following paragraph; 2) eventual supplementation consists in applying TCA and not correspondence analysis (CA), because in the CA case we do not have a result similar to Theorem 1; 3) question that we are allowed to ask is to explore and visualize rank data.

Within the CA framework, there are two codings of rank data $R_{double}$ and $R_{nega}$.

3.3.1. R_double

The first one is the doubled table of size $\left(2n\right)\times d$

$R_{double}=\left(\begin{array}{c}R\\ \bar{R}\end{array}\right)$

proposed independently by [14] [15], where they showed that CA of $R_{double}$ is

Table 2. The matrix of first-order marginals of R.

equivalent to the dual scaling of Nishisato coding of rank data, see [16]. CA of $R_{double}$ is equivalent to CA of its first residual correspondence matrix

$P_{double}^1=\frac{1}{t}\left(\begin{array}{c}{r}_{ij}-\frac{d-1}{2}\\ -\left(r_{ij}-\frac{d-1}{2}\right)\end{array}\right)\mathrm{,}$

where $t=nd\left(d-1\right)$. The structure of $P_{double}^1$ shows that each row is centered as in Carroll’s multidimensional preference analysis procedure, MDPREF, exposed in Alvo and Yu (2014, p. 15). In TCA the objective function to maximize is a combinatorial problem, see Equation (3); and the first iteration in TCA of $R_{double}$ corresponds to computing

$\begin{array}{c}{\delta }_1^{double}={\max }_{v\in {\left\{-\mathrm{1,1}\right\}}^n}{\Vert \left(v^t\mathrm{<mo>\; |\; </mo>}-v^t\right)P_{double}^1\Vert }_1\\ ={\max }_{v\in {\left\{-\mathrm{1,1}\right\}}^n}\frac{2}{t}{\displaystyle {\sum }_{j=1}^d\left|{\displaystyle {\sum }_{i=1}^n\left(r_{ij}-\frac{d-1}{2}\right)v_i}\right|}\end{array}$ (11)

3.3.2. R_nega

In the second approach, we summarize $\bar{R}$ by its column total; that is, we create a row named $nega=n\bar{\beta }={1^{\prime }}_n\bar{R}$, then we vertically concatenate nega to R, thus obtaining

$R_{nega}=\left(\begin{array}{c}R\\ nega\end{array}\right)$

of size $\left(n+1\right)\times d$.

[17] discussed the relationship between TCA of $R_{double}$ and TCA of $R_{nega}$ : TCA of $R_{nega}$ can be considered as constrained TCA of $R_{double}$, because we are constraining the vector $-v^t=-1_n^t$ in (11); that is, the objective function to maximize corresponds to computing

$\begin{array}{c}{\delta }_1={\max }_{v\in {\left\{-\mathrm{1,1}\right\}}^n}{\Vert \left(v^t\mathrm{<mo>\; |\; </mo>}-1_n^t\right)P_{double}^1\Vert }_1\\ ={\max }_{v\in {\left\{-\mathrm{1,1}\right\}}^n}{\Vert \left(v^t-1\right)P_{nega}^1\Vert }_1\\ ={\max }_{v\in {\left\{-\mathrm{1,1}\right\}}^n}\frac{1}{t}{\displaystyle {\sum }_{j=1}^d\left|{\displaystyle {\sum }_{i=1}^n\left(r_{ij}-\frac{d-1}{2}\right)\left(v_i+1\right)}\right|}\end{array}$ (12)

So, we see that if in (11) the optimal value of $v=1_n$, then ${\delta }_1^{double}={\delta }_1$, otherwise ${\delta }_1^{double}>{\delta }_1$.

Let

$v_1=\arg \underset{v\in {\left\{-\mathrm{1,1}\right\}}^n}{\max }\frac{1}{t}{\displaystyle \underset{j=1}{\overset{d}{\sum }}}\left|{\displaystyle \underset{i=1}{\overset{n}{\sum }}}\left(r_{ij}-\frac{d-1}{2}\right)\left(v_i+1\right)\right|\mathrm{.}$

Define the set of indices $I_{+}=\left\{i|v_{1i}=1\right\}$ and $I_{-}=\left\{i|v_{1i}=-1\right\}$, where $v_1=\left(v_{1i}\right)$. Then

${\delta }_1=\frac{2}{t}{\displaystyle \underset{j=1}{\overset{d}{\sum }}}\left|{\displaystyle \underset{i\in I_{+}}{\sum }}\left(r_{ij}-\frac{d-1}{2}\right)\right|$ (13)

shows that the summation in (13) is restricted to the subset of assessors that belong to $I_{+}$. The subset $I_{+}$ indexes the voters having the same direction in their votes. Given that we are uniquely interested in the first TCA dimension, all the necessary information is encapsulated in $I_{+}$, as discussed in [9] [17] using other arguments.

Furthermore, ${\delta }_1$ in (13) equals four times the cut norm of $R_{centered}\left(i\mathrm{,}j\right)=\frac{1}{t}\left(r_{ij}-\frac{d-1}{2}\right)$, where the cut norm is defined to be

${\Vert R_{centered}\Vert }_{cut}=\underset{S\mathrm{,}T}{\max }\frac{1}{t}{\displaystyle \underset{j\in S}{\sum }}{\displaystyle \underset{i\in T}{\sum }}\left(r_{ij}-\frac{d-1}{2}\right)=\frac{1}{t}{\displaystyle \underset{j\in S_{+}}{\sum }}{\displaystyle \underset{i\in I_{+}}{\sum }}\left(r_{ij}-\frac{d-1}{2}\right)={\delta }_1/4\mathrm{,}$

where $S\subseteq \left\{\mathrm{1,}\cdots \mathrm{,}d\right\}$ and $T\subseteq I$ ; it shows that the subsets $I_{+}$ and $S_{+}$ are positively associated, for further details see for instance, [18] [19].

In the sequel, we will consider only the application of TCA to $R_{nega}$.

4. First TCA Voter Factor Scores of R_nega

We show the results on the SUSHI data set enumerating $n=5000$ preferences of $d=10$ sushis, see [1]. Even though, our interest concerns only the first TCA voter factor scores of a voting profile $V_1$, it is a common practice in CA circles to present the principal map of the row and column projections.

Figure 1 and Figure 2 display the principal maps obtained from CA and TCA of $R_{nega}$ of the SUSHI data denoted by $V_1$. We observe that, TCA clusters the voters into a finite number of discrete patterns, while CA does not: This is the main reason that we prefer the use of TCA to the use of the classical well-known dimension reduction technique CA.

We have the following theorem concerning the first TCA principal factor

Figure 1. CA map of SUSHI rank data.

Figure 2. TCA map of SUSHI rank data.

scores of the voters belonging to a profile $V_1$, $f_1\left(i\right)$ for $i=1,\cdots ,n$, where the first principal axis partitions the d items into $d_1$ and $d_2$ parts such that $d=d_1+d_2$.

Theorem 1

a) The maximum number of distinct clusters of the n voters belonging to $V_1$ on the first TCA principal axis (distinct $f_1\left(i\right)$ values for $i\in V_1$ ) is $d_1{d}_2+1$.

b) The maximum value that $f_1\left(i\right)$ can attain is $2\frac{d_1{d}_2}{d\left(d-1\right)}$.

c) The minimum value that $f_1\left(i\right)$ can attain is $-2\frac{d_1{d}_2}{d\left(d-1\right)}$.

d) If the number of distinct clusters is maximum, $d_1{d}_2+1$, then the gap between two contiguous $f_1\left(i\right)$ values is $\frac{4}{d\left(d-1\right)}$.

Remark 1

a) We fix $f_1\left(nega\right)<0$ to eliminate the sign indeterminacy of the first bilinear term in (10).

b) We partition $V_1$ into $d_1{d}_2+1$ clusters, $V_1={\displaystyle {\cup }_{\alpha \mathrm{<mo>\; =\; </mo>1}}^{d_1{d}_2+1}{V}_{\mathrm{1,}\alpha }}$, where the voters of the αth cluster are characterized by their first TCA factor score; that is, $V_{1,\alpha }=\left\{i\in V_1:f_1^{V_1}\left(i\right)=2\frac{d_1{d}_2}{d\left(d-1\right)}-\left(\alpha -1\right)\frac{4}{d\left(d-1\right)}\right\}$ for $\alpha =\mathrm{1,}\cdots \mathrm{,}{d}_1{d}_2+1$.

Example 1: In Figure 2, $d_1=4$ and $d_2=6$, and we observe:

Fact 1: by Theorem 1a, 5000 preferences are clustered into $d_1{d}_2+1=25$ clusters on the first TCA principal axis.

Fact 2: by Theorem 1b, the maximum value of $f_1\left(i\right)=48/90$.

Fact 3: by Theorem 1c, the minimum value of $f_1\left(i\right)=-48/90$.

Fact 4: by Theorem 1d, the gap separating two contiguous clusters of voters on the first TCA principal axis is 4/90.

A cluster of voters defined in Remark 1b, $V_{\mathrm{1,}\alpha }$ for $\alpha =1,\cdots ,d_1{d}_2+1$, can be classified as coherent or incoherent. And this will be discussed in the next section.

5. Coherent Cluster

The following definition characterizes a coherent cluster.

Definition 1 (Coherency of a cluster of voters $V_{\mathrm{1,}\alpha }$ for $\alpha =1,\cdots ,d_1{d}_2+1$ )

A cluster of voters $V_{\mathrm{1,}\alpha }\subseteq V_1$ is coherent if $f_1^{V_{1,\alpha }}\left(v\right)=2\frac{d_1{d}_2}{d\left(d-1\right)}-\left(\alpha -1\right)\frac{4}{d\left(d-1\right)}$ for all $v\in V_{\mathrm{1,}\alpha }$, where $f_1^{V_{1,\alpha }}\left(i\right)$ is the first TCA factor score of the voter $i\in V_{\mathrm{1,}\alpha }$ obtained from TCA of subprofile $V_{\mathrm{1,}\alpha }$.

Remark 2:

a) It is important to distinguish between $f_1^{V_1}\left(i\right)$ for $i=1,\cdots ,\left|V_1\right|$ where $n=\left|V_1\right|$, and $f_1^{V_{1,\alpha }}\left(i\right)$ for $i=1,\cdots ,\left|V_{1,\alpha }\right|$, where $\left|V_{1,\alpha }\right|$ represents the sample size of the cluster $\left|V_{1,\alpha }\right|$.

b) Definition 1 implies that a cluster $V_{\mathrm{1,}\alpha }$ is coherent when for all voters $i\in V_{\mathrm{1,}\alpha }$ the first TCA factor score $f_1^{V_{1,\alpha }}\left(i\right)$ does not depend on the voter i, but it depends on $\left(\alpha \mathrm{,}{d}_1\mathrm{,}{d}_2\right)$.

Corollary 1: It follows from Remark 1a and Equation (13) that, a necessary condition, but not sufficient, for a cluster $V_{\mathrm{1,}\alpha }$ to be coherent is that its first TCA factor score obtained from TCA of $V_1$ is strictly positive; that is, $0<f_1^{V_1}\left(i\right)$ for $i\in V_{\mathrm{1,}\alpha }$.

Example 2: Figures 3-9 show the coherency of the clusters of voters $V_{\mathrm{1,}\alpha }$ for $\alpha =1,\cdots ,7$, where dots represent clusters of voters; while Figure 10 shows the incoherence of the cluster $V_{\mathrm{1,8}}$. Further, the first three columns of Table 3 display the mathematical formulation of the 7 coherent clusters $coh{C}_1\left(\alpha \right)=V_{\mathrm{1,}\alpha }$ for $\alpha =1,\cdots ,7$ as defined in Remark 1b and their sample sizes $\left|V_{\mathrm{1,}\alpha }\right|$.

Proposition 1: For a voting profile V, ${\delta }_1\left(V\right)\ge \left|f_1\left(nega\right)\right|$, where ${\delta }_1\left(V\right)$ is the first TCA dispersion value obtained from TCA of V, and $f_1\left(nega\right)$ is the first TCA factor score of the row nega.

The equality in Proposition 1 is attained only for coherent clusters as shown in the following result.

Proposition 2: The first TCA dispersion value of a coherent cluster $coh{C}_1\left(\alpha \right)$ satisfies

${\delta }_1\left(coh{C}_1\left(\alpha \right)\right)=\left|f_1^{V_{1,\alpha }}\left(nega\right)\right|=2\frac{d_1{d}_2}{d\left(d-1\right)}-\left(\alpha -1\right)\frac{4}{d\left(d-1\right)}$

Example 3: propostion 2 can be observed by looking at the columns 3 and 4 of Table 3 which concern the 7 coherent clusters $coh{C}_1\left(\alpha \right)=V_{\mathrm{1,}\alpha }$ for $\alpha =1,\cdots ,7$.

Figure 3. TCA map of $V_{\mathrm{1,1}}$.

Figure 4. TCA map of $V_{\mathrm{1,2}}$.

Figure 5. TCA map of $V_{\mathrm{1,3}}$.

Figure 6. TCA map of $V_{\mathrm{1,4}}$.

Figure 7. TCA map of $V_{\mathrm{1,5}}$.

Figure 8. TCA map of $V_{\mathrm{1,6}}$.

Figure 9. TCA map of $V_{\mathrm{1,7}}$.

Figure 10. TCA map of $V_{\mathrm{1,8}}$.

Table 3. Characteristics of $coh{C}_1\left(\alpha \right)=V_{\mathrm{1,}\alpha }$ of SUSHI data.

While for the incoherent cluster $V_{\mathrm{1,8}}$ with sample size of $\left|V_{\mathrm{1,8}}\right|=335$, we observe: $V_{1,8}=\left\{i:f_1^{V_1}\left(i\right)=20/90=0.222\right\}$, and by Proposition 1, ${\delta }_1\left(V_{1,8}\right)=0.2354>2/9$. This means that the 335 voters belonging to $V_{\mathrm{1,8}}$ form a cluster within the whole sample of 5000 voters, but separated as 335 voters they do not form a coherent cluster.

Interpretability of a Coherent Cluster

The following result shows that for coherent clusters, the first TCA dimension can be interpreted as Borda scaled factor.

Proposition 3: The first TCA column factor score of the item j, $g_1\left(j\right)$, is an affine function of the Borda scale $\beta \left(j\right)$ ; that is, $g_1\left(j\right)=\frac{2}{d-1}\beta \left(j\right)-1$ for $j=1,\cdots ,d$. Or $corr\left(g_1\mathrm{,}\beta \right)=1$.

Remark 3:

The first TCA principal factor score of item j for $j=1,\cdots ,d$ is bounded: $-1\le g_1\left(j\right)\le 1$, because $0\le \beta \left(j\right)\le d-1$.

Example 4: Table 4 displays the Borda scales of the items, sushis, in the seven coherent clusters $coh{C}_1\left(\alpha \right)=V_{\mathrm{1,}\alpha }$ for $\alpha =1,\cdots ,7$. To identify the sushi type, one has to refer to Figure 2; for instance, j10 corresponds to 10 cucumber roll in Figure 2. We observe the following main fact: For each of the seven coherent clusters, the first TCA principal axis produced the same binary partition of the items: $J_1=\left\{\text{j}10,\text{j}7,\text{j}4,\text{j}9\right\}$ characterized by $4.5>\beta \left(j_1\right)$ for $j_1\in J_1$, and $J_2=\left\{\text{j}3,\text{j}1,\text{j}2,\text{j}6,\text{j}5,\text{j}8\right\}$ characterized by $\beta \left(j_1\right)>4.5$ for $j_2\in J_2$. The six sushis in $J_2$ have Borda scales above average score of $4.5=\left(0+9\right)/2$ ; while the four sushis in $J_1$ have Borda scales below average score of 4.5.

Now we ask the question what are the differences among the seven coherent clusters? The answer is riffle shuffling of the scores of the items, which we discuss next.

6. Exploratory Riffle Shuffling

[8] is the seminal reference on riffle shuffling of cards. [2] generalized the notion

Table 4. Borda scales of the 10 sushis in the seven coherent clusters.

of independence of two subsets of items to riffled independence to uncover the structure of rank data. Within the framework of data analysis of preferences, exploratory riffle shuffling can be described in the following way. We have two sets: J a set of d distinct items andS a set of d Borda scores. We partition both sets into two disjoint subsets of sizes $d_1$ and $d_2=d-d_1$ ; that is, $J=J_1\cup J_2$ with $J_1=\left\{j_1,j_2,\cdots ,j_{d_1}\right\}$ and $S=S_1\cup S_2$ with $S_1=\left\{0,1,\cdots ,d_1-1\right\}$. Riffle shuffling consists of two steps. In the first step, we attribute the scores of $S_1$ to $J_1$ and the scores of $S_2$ to $J_2$. In the second step, we permute some scores attributed to $J_1$ with the same number of scores attributed to $J_2$. The second step can be mathematically described as an application of a permutation $\tau$, such that ${\tau }_J\left(S_1,S_2\right)=\left({\tau }_{J_1}\left(S_1\right),{\tau }_{J_2}\left(S_2\right)\right)$. We interpret ${\tau }_{J_1}\left(S_1\right)$ as the set of scores attributed to $J_1$, and ${\tau }_{J_2}\left(S_2\right)$ as the set of scores attributed to $J_2$.

Example 5: Table 5 displays a toy example with $n=7$ voters’ Borda scorings of $d=10$ items with $J_1=\left\{\text{a},\text{b},\text{c},\text{d}\right\}$ and $J_2=\left\{\text{e},\text{f},\text{g},\text{h},\text{i},\text{j}\right\}$. We observe the following: a) The first four voters have only done the first step in a riffle shuffle: each one of them has attributed the scores in $S_1=\left\{0,1,2,3\right\}$ to the items in $J_1$ and the scores in $S_2=\left\{4,5,6,7,8,9\right\}$ to the items in $J_2$. This can be described as ${\tau }_J\left(S_1\mathrm{,}{S}_2\right)=\left(S_1\mathrm{,}{S}_2\right)$ ; that is the permutation $\tau$ is the identity permutation; so there is no crossing of scores between $J_1$ and $J_2$. b) Voters 5, 6 and 7 have done both steps in a riffle shuffle. Voters 5 and 6 have permuted score 3 with 5, so we have ${\tau }_{J_1}\left(S_1\right)=\left\{0,1,2,5\right\}$ and ${\tau }_{J_2}\left(S_2\right)=\left\{4,3,6,7,8,9\right\}$. Voter 7 has permuted the scores $\left\{2,3\right\}$ with $\left\{4,5\right\}$, so we have ${\tau }_{J_1}\left(S_1\right)=\left\{0,1,4,5\right\}$ and ${\tau }_{J_2}\left(S_2\right)=\left\{2,3,6,7,8,9\right\}$.

Further, we note by $\left|{\tau }_{J_1}\left(S_1\right)\right|$ the number of voters who have done the riffle shuffle $\left({\tau }_{J_1}\left(S_1\right),{\tau }_{J_2}\left(S_2\right)\right)$. So $\left|{\tau }_{J_1}\left(S_1\right)=\left\{0,1,2,3\right\}\right|=4$, $\left|\left\{0,1,2,5\right\}\right|=2$ and $\left|\left\{0,1,4,5\right\}\right|=1$. The permuted scores between the two blocks of items are in bold in Table 5.

Remark 4: A useful observation that we get from Example 5 is that we can concentrate our study either on $J_1$ or on $J_2$ : For if we know ${\tau }_{J_1}\left(S_1\right)$, the scores attributed to $J_1$, we can deduce ${\tau }_{J_2}\left(S_2\right)$, the scores attributed to $J_2$ because of mutual exclusivity constraints ensuring that any two items, say a and

Table 5. Borda scorings of 10 items by 7 voters.

b, never map to the same rank by a voter.

A simple measure of magnitude of $\left(d_1\mathrm{,}{d}_2\right)$ riffle shuffling of a voter i is the sum of its Borda scores attributed to the items in $J_1$ ; that is,

$T_i\left({\tau }_{J_1}\left(S_1\right)\right)={\displaystyle \underset{j\in J_1}{\sum }}{r}_{ij},$

where $r_{ij}$ is the Borda score attributed to item j by voter i. In Table 5, for the first four voters, $T_i\left({\tau }_{J_1}\left(S_1\right)\right)=6$ for $i=1,2,3,4$, which is the minimum attainable sum of scores; it implies that for these voters there is no crossing of scores between the two blocks $J_1$ and $J_2$. While for voters 5 and 6, $T_i\left({\tau }_{J_1}\left(S_1\right)\right)=8$ for $i=5,6$ ; for voter 7, $T_7\left({\tau }_{J_1}\left(S_1\right)\right)=10$. These values show that the crossing of scores between the two blocks $J_1$ and $J_2$ of voters 5 and 6 are at a lower level than the crossing of scores for voter 7.

For relatively small sample sizes, it is easy to enumerate the different types of $\left(d_1\mathrm{,}{d}_2\right)$ riffle shuffles. For relatively large sample sizes, we use the contingency table of first-order marginals, that we discuss next.

Types of (d₁, d₂) Riffle Shufflings in a Coherent Cluster

The contingency table of first order marginals of an observed voting profile V on d items is a square $d\times d$ matrix M, where $M\left(i\mathrm{,}j\right)$ stores the number of times that item j has Borda score i for $i=\mathrm{0,}\cdots \mathrm{,}d-1$, see subsection 3.2. It helps us to observe types of $\left(d_1\mathrm{,}{d}_2\right)$ riffle shufflings in a coherent cluster as we explain in Example 6.

Example 6: Tables 6-12 display $M_{\mathrm{1,}\alpha }$ for $\alpha =\mathrm{1,}\cdots \mathrm{,7}$, the contingency tables of first-order marginals of the seven coherent clusters of the SUSHI data, respectively. We observe the following:

Each one of them reveals the nature of the riffle shuffles of its coherent cluster,

Table 6. $M_{\mathrm{1,1}}$, contingency table of first-order marginals of $coh{C}_1\left(1\right)$.

Table 7. $M_{\mathrm{1,2}}$, contingency table of first-order marginals of $coh{C}_1\left(3\right)$.

Table 8. $M_{\mathrm{1,3}}$, contingency table of first-order marginals of $coh{C}_1\left(3\right)$.

Table 9. $M_{\mathrm{1,4}}$, contingency table of first-order marginals of $coh{C}_1\left(4\right)$.

Table 10. $M_{\mathrm{1,5}}$, contingency table of first-order marginals of $coh{C}_1\left(5\right)$.

Table 11. $M_{\mathrm{1,6}}$, contingency table of first-order marginals of $coh{C}_1\left(6\right)$.

Table 12. $M_{\mathrm{1,7}}$, contingency table of first-order marginals of $coh{C}_1\left(7\right)$.

Table 13. Types of riffle shuffles in the 7 coherent clusters of SUSHI data.

which are summarized in Table 13. The number of observed $\left(\mathrm{4,6}\right)$ blocks of scores for the seven coherent clusters, $\left({\tau }_{J_1}\left(S_1\right),{\tau }_{J_2}\left(S_2\right)\right)$, is only 27 in Table 13 out of the possible total number of $\mathrm{10\; <mo>\; !\; </mo>}/\left(\mathrm{4\; <mo>\; !\; </mo>6\; <mo>\; !\; </mo>}\right)=210$. The counts of the observed $\left(\mathrm{4,6}\right)$ blocks do not seem to be uniformly distributed in Table 13. Furthermore, we observe that as $\alpha$ increases from 1 to 7, the magnitude of riffle shuffles, $T_v\left({\tau }_{J_1}\left(S_1\right)\right)$, increases in the coherent clusters from 6 to 12. Integers in bold in Table 13 are the shuffled-crossed scores.

The counts in Table 13 are calculated from $M_{\mathrm{1,}\alpha }$ for $\alpha =\mathrm{1,}\cdots \mathrm{,7}$, by reasoning on the permutation of scores between the sets $S_1$ and $S_2$. Here are the details, where $J_1=\left\{\text{j}10,\text{j}7,\text{j}4,\text{j}9\right\}$.

a) $coh{C}_1(\; 1\; )$

$\left|\left\{\mathrm{0,1,2,3}\right\}\right|=314$, which is the number of 0 s attributed to $J_1$ in $M_{\mathrm{1,1}}$. Among the $M_{\mathrm{1,}\alpha }$ for $\alpha =\mathrm{1,}\cdots \mathrm{,7}$, note that $M_{\mathrm{1,1}}$ is the only contingency table of first-order marginals which is block diagonal.

b) $coh{C}_1(\; 2\; )$

$\left|\left\{0,1,2,4\right\}\right|=235$, which is the number of 4 s attributed to $J_1$ in $M_{\mathrm{1,2}}$.

c) $coh{C}_1(\; 3\; )$

$\left|\left\{\mathrm{0,1,2,5}\right\}\right|=171$, which is the number of 5 s attributed to $J_1$ in $M_{\mathrm{1,3}}$.

$\left|\left\{\mathrm{0,1,}4\mathrm{,3}\right\}\right|=155$, which is the number of 4 s attributed to $J_1$ in $M_{\mathrm{1,3}}$.

d) $coh{C}_1(\; 4\; )$

$\left\{\left\{\mathrm{0,1,2,}6\right\}\right\}=96$, which is the number of 6 s attributed to $J_1$ in $M_{\mathrm{1,4}}$.

$\left|\left\{\mathrm{0,1,}5\mathrm{,3}\right\}\right|=119$, which is the number of 5 s attributed to $J_1$ in $M_{\mathrm{1,4}}$.

$\left|\left\{\mathrm{0,}4\mathrm{,2,3}\right\}\right|=100$, which is the number of 4 s attributed to $J_1$ in $M_{\mathrm{1,4}}$.

e) $coh{C}_1(\; 5\; )$

$\left|\left\{\mathrm{0,1,2,}7\right\}\right|=79$, which is the number of 7 s attributed to $J_1$ in $M_{\mathrm{1,5}}$.

$\left|\left\{\mathrm{0,1,}6\mathrm{,3}\right\}\right|=84$, which is the number of 6 s attributed to $J_1$ in $M_{\mathrm{1,5}}$.

$\left|\left\{\mathrm{0,}5\mathrm{,2,3}\right\}\right|=85$, which is the number of 1 s not attributed to $J_1$ in $M_{\mathrm{1,5}}$.

$\left|\left\{\mathrm{0,1,}4\mathrm{,}5\right\}\right|+\left|\left\{\mathrm{0,}5\mathrm{,2,3}\right\}\right|=170$, which is the total number of 5 s attributed to $J_1$ in $M_{\mathrm{1,5}}$ ; so $\left|\left\{\mathrm{0,1,}4\mathrm{,}5\right\}\right|=170-85=85$.

$\left|\left\{4\mathrm{,1,2,3}\right\}\right|=119$, which is the number of 0 s not attributed to $J_1$ in $M_{\mathrm{1,5}}$.

f) $coh{C}_1(\; 6\; )$

$\left|\left\{\mathrm{0,1,2,}8\right\}\right|=48$, which is the number of 8 s attributed to $J_1$ in $M_{\mathrm{1,6}}$.

$\left|\left\{\mathrm{0,1,}7\mathrm{,3}\right\}\right|=63$, which is the number of 7 s attributed to $J_1$ in $M_{\mathrm{1,6}}$.

$\left|\left\{5\mathrm{,1,2,3}\right\}\right|=98$, which is the number of 0 s not attributed to $J_1$ in $M_{\mathrm{1,6}}$.

$\left|\left\{\mathrm{0,}4\mathrm{,2,}5\right\}\right|=152-98=54$, where 152 is the total number of 5 s attributed to $J_1$ in $M_{\mathrm{1,6}}$.

$\left|\left\{\mathrm{0,1,}4\mathrm{,}6\right\}\right|=113-54=59$, where 113 is the total number of 4 s attributed to $J_1$ in $M_{\mathrm{1,6}}$.

$\left|\left\{\mathrm{0,}6\mathrm{,2,3}\right\}\right|=112-59=53$, where 112 is the total number of 6 s attributed to $J_1$ in $M_{\mathrm{1,6}}$.

g) $coh{C}_1(\; 7\; )$

$\left|\left\{\mathrm{0,1,2,}9\right\}\right|=26$, which is the number of 9 s attributed to $J_1$ in $M_{\mathrm{1,7}}$.

$\left|\left\{\mathrm{0,1,}8\mathrm{,3}\right\}\right|=26$, which is the number of 8 s attributed to $J_1$ in $M_{\mathrm{1,7}}$.

For the remaining counts, we have to solve the following system of 7 linear equations, where, $u=\left|\left\{\mathrm{0,}7\mathrm{,2,3}\right\}\right|$, $t=\left|\left\{\mathrm{0,}4\mathrm{,}5\mathrm{,3}\right\}\right|$, $s=\left|\left\{\mathrm{0,}4\mathrm{,2,}6\right\}\right|$, $w=\left|\left\{\mathrm{0,1,}4,7\right\}\right|$, $z=\left|\left\{\mathrm{0,1,}5,6\right\}\right|$, $x=\left|\left\{6\mathrm{,1,2,3}\right\}\right|$, and $y=\left|\left\{4\mathrm{,1,2,5}\right\}\right|$.

$x+y=147$, which is the number of 0 s not attributed to $J_1$ in $M_{\mathrm{1,7}}$.

$u+w=72$, which is the number of 7 s attributed to $J_1$ in $M_{\mathrm{1,7}}$.

$s+z+x=169$, which is the number of 6 s attributed to $J_1$ in $M_{\mathrm{1,7}}$.

$t+z+y=157$, which is the number of 5 s attributed to $J_1$ in $M_{\mathrm{1,7}}$.

$t+s+w+y=185$, which is the number of 4 s attributed to $J_1$ in $M_{\mathrm{1,7}}$.

$u+t+x=158$, which is the number of 3 s attributed to $J_1$ in $M_{\mathrm{1,7}}$.

$u+s+x+y=218$, which is the number of 2 s attributed to $J_1$ in $M_{\mathrm{1,7}}$.

7. Crossing Index

The following $\left(d_1\mathrm{,}{d}_2\right)$ crossing index is based on the internal dispersion of a voting profile.

Definition 3: For a voting profile V we define its crossing index to be

$Cross\left(V\right)=1-\frac{{\delta }_1\left(V_{d_1,d_2}\right)}{\underset{V}{\max }{\delta }_1\left(V_{d_1,d_2}\right)}=1-\frac{{\delta }_1\left(V_{d_1,d_2}\right)}{2\frac{d_1{d}_2}{d\left(d-1\right)}}$ by Proposition 2.

where ${\delta }_1\left(V_{d_1,d_2}\right)$ is the first taxicab dispersion obtained from TCA of V and $\left(d_1\mathrm{,}{d}_2\right)$ represents the optimal TCA binary partition of the d items of V such that $d=d_1+d_2$.

Proposition 4: The crossing index of a coherent cluster is

$Cross\left(cohC\left(\alpha \right)\right)=\frac{2\left(\alpha -1\right)}{d_1{d}_2}\mathrm{.}$

Example 7: The last column in Table 3 contains the values of the crossing indices of the seven coherent clusters of the first iteration of SUSHI data. We observe: a) $Cross\left(coh{C}_1\left(1\right)\right)=0$, because the structure of its matrix of first-order marginals, $M_{\mathrm{1,1}}$, is block diagonal; which means that the permutation $\tau$ is the identical permutation, so there are no crossing of scores between the two subsets of items $J_1$ and $J_2$ in $coh{C}_1\left(1\right)$. b) $Cross\left(coh{C}_1\left(\alpha \right)\right)$ for $\alpha =1,\cdots ,7$ is a uniformly increasing function of $\alpha$, similar in spirit to the $T_v\left({\tau }_{J_1}\left(S_1\right)\right)$ statistic. c) For the incoherent cluster $V_{\mathrm{1,8}}$, we have: ${\delta }_1\left(V_{\mathrm{1,8}}\right)=0.2354$ given in Example 3; and $d_1=d_2=5$ from Figure 10. So

$Cross\left(V_{1,8}\right)=1-\frac{0.2354}{2\times 5\times 5/\left(10\times 9\right)}=1-0.4237=0.5763$.

8. Coherent Group

Our aim is to explore a given voting profile V by uncovering its coherent mixture groups, see Equation (1); that is, $V={\displaystyle {\cup }_{g=1}^{G}cohG\left(g\right)\cup noisyG}$, where G represents the number of coherent groups and $cohG\left(g\right)$ is the gth coherent group. The computation is done by an iterative procedure in $n_G$ steps for $n_G\ge G$ that we describe:

For $g=1$ ; let $V_1=V$ ; compute $cohG\left(1\right)$ from $V_1$, then partition $V_1=V_2\cup cohG\left(1\right)$ ;

For $g=2$ ; compute $cohG\left(2\right)$ from $V_2$, then partition $V_2=V_3\cup cohG\left(2\right)$ ;

By continuing the above procedure, after $n_G$ steps, we get $V={\displaystyle {\cup }_{g\mathrm{<mo>\; =\; </mo>1}}^{n_G}cohG\left(g\right)}$.

However, some of the higher ordered coherent groups may have relatively small sample sizes; so by considering these as outliers, we lump them together thus forming the noisy group denoted by $noisyG$ in Equation (1).

Let us recall the definition of a coherent group given in Equation (2)

$cohG\left(g\right)={\displaystyle {\cup }_{\alpha =1}^{c_g}coh{C}_g\left(\alpha \right)}\text{for}g=1,\cdots ,G;$

that is, a coherent group is the union of its coherent clusters. This implies that the sample size of $cohG\left(g\right)$ equals the sum of the sample sizes of its coherent clusters

$\left|cohG\left(g\right)\right|={\displaystyle \underset{\alpha =1}{\overset{c_g}{\sum }}}\left|coh{C}_g\left(\alpha \right)\right|.$

As an example, for the SUSHI data, from the 2^nd column of Table 3 we can compute the sample size of the first coherent group

$\left|cohG\left(1\right)\right|={\displaystyle \underset{\alpha =1}{\overset{c_g=7}{\sum }}}\left|coh{C}_1\left(\alpha \right)\right|=2418.$

Furthermore, $cohG\left(1\right)$ is composed of 27 observed riffle shuffles summarized in Table 13, which provides quite a detailed view of its inner structure.

The next result shows important characteristics of a coherent group inherited from its coherent clusters.

Theorem 2: (Properties of a coherent group $cohG(\; g\; )\; )$

a) The first principal column factor score $g_1$ of the d items in a coherent group is the weighted average of the first principal column factor score $g_1$ of the d items of its coherent clusters; that is,

$g_1\left(j\in cohG\left(g\right)\right)={\displaystyle \underset{\alpha =1}{\overset{c_g}{\sum }}}\frac{\left|coh{C}_g\left(\alpha \right)\right|}{\left|cohG\left(g\right)\right|}{g}_1\left(j\in coh{C}_g\left(\alpha \right)\right)\text{for}j=\mathrm{1,}\cdots \mathrm{,}d$

$=\frac{2}{d-1}{\displaystyle \underset{\alpha =1}{\overset{c_g}{\sum }}}\frac{\left|coh{C}_g\left(\alpha \right)\right|}{\left|cohG\left(g\right)\right|}\beta \left(j\in coh{C}_g\left(\alpha \right)\right)-1$ by Proposition 3.

And $corr\left(g_1\left(cohG\left(g\right)\right)\mathrm{,}\beta \left(cohG\left(g\right)\right)\right)=1$.

b) The first TCA dispersion value of a coherent group is the weighted average of the first TCA dispersion values of its coherent clusters; that is,

${\delta }_1\left(cohG\left(g\right)\right)={\displaystyle \underset{\alpha =1}{\overset{c_g}{\sum }}}\frac{\left|coh{C}_g\left(\alpha \right)\right|}{\left|cohG\left(g\right)\right|}{\delta }_1\left(coh{C}_g\left(\alpha \right)\right).$

c) The crossing index of a coherent group is the weighted average of the crossing indices of its coherent clusters; that is,

$Cross\left(cohG\left(g\right)\right)={\displaystyle \underset{\alpha =1}{\overset{c_g}{\sum }}}\frac{\left|coh{C}_g\left(\alpha \right)\right|}{\left|cohG\left(g\right)\right|}Cross\left(coh{C}_g\left(\alpha \right)\right)\mathrm{.}$

Example 8: Table 14 summarizes the first four coherent groups of SUSHI data, which emerged after 5 iterations. For $g=1$, we get $cohG\left(1\right)={\displaystyle {\cup }_{\alpha =1}^{c_1=7}coh{C}_1\left(\alpha \right)}$ ; that is, the first coherent group of voters, the majority, is composed of 48.36% of the sample with crossing index of 27.3%. Standard errors of the Borda scale of the items in $cohG\left(1\right)$ in Table 14 are:

$\left(\mathrm{0.046,0.051,0.042,0.042,0.053,0.047,0.037,0.034,0.037,0.025}\right)\mathrm{.}$

We can discern the following grouped seriation (bucket ranking) of the items

$\text{j}8\succ \text{j}5\succ \text{j}6\succ \left\{\text{j}\mathrm{3,}\text{j}2\right\}\succ \text{j}1\succ \left\{\text{j}\mathrm{9,}\text{j}4\right\}\succ \left\{\text{j}7\right\}\succ \left\{\text{j}10\right\}\mathrm{.}$

The groupings are based on the standard 95% confidence intervals of the Borda scale of the items.

The 2^nd coherent group $cohG\left(2\right)$, summarized by its Borda scales in Table 14, is made up of eight coherent clusters; it is composed of 19.0% of the sample with crossing index of 35.38%. The voters in this coherent group disapprove {uni(seaurchin), sake(salmonroe)}, which are considered more “daring sushis”.

The third coherent group $cohG\left(3\right)$, summarized by its Borda scales in Table 14, is made up of eight coherent clusters; it is composed of 13.24% of the sample with crossing index of 27.3%. The voters in this coherent group prefer the three types of tuna sushis with sea urchin sushis.

The fourth coherent group $cohG\left(4\right)$, summarized by its Borda scales in Table 14, is made up of eight coherent clusters; it is composed of 6.94% of the sample with crossing index of 35.27%. The voters disapprove the three types of tuna sushis.

Remark 6:

a) Note that the number of preferred sushis in $cohG\left(1\right)$ and $cohG\left(2\right)$ are six; that is $\left|J_2\right|=6$. While the number of preferred sushis in $cohG\left(3\right)$ and $cohG\left(4\right)$ are four.

b) The four coherent groups summarized in Table 14 can also be described as two bipolar latent factors: By noting that the only major difference between the first two coherent groups is that (5. uni (sea urchin), 6. sake (salmon roe)) are swapped with (7. tamago (egg), 4. ika (squid)). While the only major difference between the third and fourth coherent groups is that the three tunas are swapped with (4. ika (squid), 5. uni (sea urchin), 1. ebi (shrimp)).

c) We consider the fifth group as noisy (outliers not shown) composed of 12.36% of the remaining sample: it contains $cohG\left(5\right)={\displaystyle {\cup }_{\alpha =1}^{2}coh{C}_5\left(\alpha \right)}$ whose sample size is 38, a very small number. For the sake of completeness we also provide the sample sizes of its two coherent clusters $\left|coh{C}_5\left(1\right)\right|=22$ and $\left|coh{C}_5\left(2\right)\right|=16$.

9. APA Data Set

The 1980 American Psychological Association (APA) presidential election had five candidates: $\left\{A\mathrm{,}C\right\}$ were research psychologists, $\left\{D\mathrm{,}E\right\}$ were clinical

Table 14. The first four coherent groups of SUSHI data and related statistics.

psychologists and B was a community psychologist. In this election, voters ranked the five candidates in order of preference. Among the 15,449 votes, 5738 votes ranked all five candidates. We consider the data set which records the 5738 complete votes; it is available in [ [20], p. 96] and [ [5], Table 1]. The winner was candidate C.

Table 15 compares the results obtained by our method and the best distance-based mixture model given in [21]. Distance-based models have two parameters, a central modal ranking and a precision parameter. The precision parameter measures the peakedness of the distribution. [21] found that the Cayley distance produced better results than the Kendall and Spearman distances using BIC (Bayesian information criterion) and ICL (integrated complete likelihood) criteria. Parts a and b of Table 15, are reproduced from [ [21], Table 4 and Table 5].

Part c of Table 15 summarizes the results of our approach, where we only describe the first four coherent groups: We find only the first two coherent groups as meaningfully interpretable based on the a priori knowledge of the candidates. Voters in $cohG\left(1\right)$, with sample size of 31%, prefer the research oriented psychologists $\left\{A\mathrm{,}C\right\}$ over the rest. Voters in $cohG\left(2\right)$, with sample size of 23.7%, prefer the clinical psychologists $\left\{D\mathrm{,}E\right\}$ over the rest. We interpret $cohG\left(3\right)$ and $cohG\left(4\right)$ as mixed B with 14.23% and 12% of the voters, respectively. Additionally, there is a $noisyG$ making up 19.1% of the sample, which comprises $cohG\left(5\right)$ displayed in Table 15.

[5] discussed this data set quite in detail; surprisingly, our results confirm his observations: a) There are two groups of candidates, $\left\{A\mathrm{,}C\right\}$ and $\left\{D\mathrm{,}E\right\}$. The voters line up behind one group or the other; b) The APA divides into academicians and clinicians who are on uneasy terms. Voters seem to choose one type or the other, and then choose within; but the group effect predominates; c) Candidate B seems to fall in the middle, perhaps closer to D and E.

The following important observation emerges from the comparison of results in Table 15. We have two distinct concepts of groups for rank data, categorical and latent variable based. To see this, consider groups 3 and 4 in part a of Table 15:

Table 15. A summary of results derived from three methods of analysis of APA election data. Parts (a) and (b) are from Murphy and Martin (2003).

Group 3 is based on the modal category $B\succ C\succ A\succ D\succ E$ and group 4 is based on the modal category $B\succ C\succ A\succ E\succ D$. The only difference between these two modal categories is the permutation of the least ranked two clinical psychologist candidates $\left\{D\mathrm{,}E\right\}$ ; this difference is not important and does not appear in our approach, which is a latent variable approach.

Description

The eight coherent clusters of the first four coherent groups can simply be described as:

$co{h}_{1}C\left(1\right)\mathrm{<mo>\; :\; </mo>}{T}_v\left({\tau }_{J_2}\left(S_2\right)={\tau }_{\left\{A\mathrm{,}C\right\}}\left\{\mathrm{3,4}\right\}=\left\{\mathrm{3,4}\right\}\right)=7$ for $v=\mathrm{1,}\cdots \mathrm{,1233}$.

$co{h}_{1}C\left(2\right)\mathrm{<mo>\; :\; </mo>}{T}_v\left({\tau }_{J_2}\left(S_2\right)={\tau }_{\left\{A\mathrm{,}C\right\}}\left\{\mathrm{3,4}\right\}=\left\{2\mathrm{,4}\right\}\right)=6$ for $v=\mathrm{1,}\cdots \mathrm{,545}$.

$co{h}_{2}C\left(1\right)\mathrm{<mo>\; :\; </mo>}{T}_v\left({\tau }_{J_2}\left(S_2\right)={\tau }_{\left\{D\mathrm{,}E\right\}}\left\{\mathrm{3,4}\right\}=\left\{\mathrm{3,4}\right\}\right)=7$ for $v=\mathrm{1,}\cdots \mathrm{,834}$.

$co{h}_{2}C\left(2\right)\mathrm{<mo>\; :\; </mo>}{T}_v\left({\tau }_{J_2}\left(S_2\right)={\tau }_{\left\{D\mathrm{,}E\right\}}\left\{\mathrm{3,4}\right\}=\left\{2\mathrm{,4}\right\}\right)=6$ for $v=\mathrm{1,}\cdots \mathrm{,526}$.

$co{h}_{3}C\left(1\right)\mathrm{<mo>\; :\; </mo>}{T}_v\left({\tau }_{J_1}\left(S_1\right)={\tau }_{\left\{C\mathrm{,}E\right\}}\left\{\mathrm{0,1}\right\}=\left\{\mathrm{0,1}\right\}\right)=1$ for $v=1,\cdots ,512$.

$co{h}_{3}C\left(2\right)\mathrm{<mo>\; :\; </mo>}{T}_v\left({\tau }_{J_1}\left(S_1\right)={\tau }_{\left\{C\mathrm{,}E\right\}}\left\{\mathrm{0,1}\right\}=\left\{\mathrm{0,}2\right\}\right)=2$ for $v=1,\cdots ,305$.

$co{h}_{4}C\left(1\right)\mathrm{<mo>\; :\; </mo>}{T}_v\left({\tau }_{J_1}\left(S_1\right)={\tau }_{\left\{A\mathrm{,}D\right\}}\left\{\mathrm{0,1}\right\}=\left\{\mathrm{0,1}\right\}\right)=1$ for $v=1,\cdots ,350$.

$co{h}_{4}C\left(2\right)\mathrm{<mo>\; :\; </mo>}{T}_v\left({\tau }_{J_1}\left(S_1\right)={\tau }_{\left\{A\mathrm{,}D\right\}}\left\{\mathrm{0,1}\right\}=\left\{\mathrm{0,}2\right\}\right)=2$ for $v=1,\cdots ,338$.

In this case, we can also visualize all the orderings belonging to a coherent group: Figure 11 and Figure 12 display all the preferences belonging to the two coherent clusters of the first coherent group. The label CAEBD162 in Figure 11 should be interpreted as the preference $C\succ A\succ E\succ B\succ D$ repeated 162 times.

Figure 11. TCA map of $Co{h}_1{C}_1$ of APA data.

Figure 12. TCA map of $Co{h}_1{C}_2$ of APA data.

10. Riffle Independence Model

Riffle independence is a nonparametric probabilistic modelling method of preferences developed by [2], which generalizes the independence model. It can be described in the following way:

(a) Partition the set J of d distinct items into two disjoint subsets $J_1$ of size $d_1$ and $J_2$ of size $d_2$. Then generate an ordering of items within each subset according to a certain ranking model. This implies that any ordering of the d items can be written as a direct product of two disconnected orderings; which in its turn implies the independence of the two subsets $J_1$ and $J_2$. So the model complexity of this step is of order $d_1\mathrm{<mo>\; !\; </mo>}+d_2\mathrm{<mo>\; !\; </mo>}$.

(b) Interleave the two independent orderings for these two subsets using a riffle shuffle to form a combined ordering. An interleaving is a binary mapping from the set of orderings to $\left\{J_1\mathrm{,}{J}_2\right\}$. The model complexity of this step is of order $d\mathrm{<mo>\; !\; </mo>}/\left(d_1\mathrm{<mo>\; !\; </mo>}{d}_2\mathrm{<mo>\; !\; </mo>}\right)$. The interleaving step generates the riffled independence of the two subsets $J_1$ and $J_2$.

So the combined model complexity of both steps is $d_1\mathrm{<mo>\; !\; </mo>}+d_2\mathrm{<mo>\; !\; </mo>}+d\mathrm{<mo>\; !\; </mo>}/\left(d_1\mathrm{<mo>\; !\; </mo>}{d}_2\mathrm{<mo>\; !\; </mo>}\right)$ which is much smaller than $d\mathrm{<mo>\; !\; </mo>}=\left(d_1+d_2\right)\mathrm{<mo>\; !\; </mo>}$.

For example, consider an ordering of the items in the set $J=\left\{A,B,C,D,E,F\right\}$ from its two subsets $J_1=\left\{A,C\right\}$ and $J_2=\left\{B,D,E,F\right\}$. In the first step, relative orderings of the items in $J_1$ and $J_2$ are drawn independently. Suppose we obtain the relative ordering $\phi \left(J_1\right)=\left(C\succ A\right)$ in $J_1$, and the relative ordering $\phi \left(J_2\right)=\left(B\succ D\succ F\succ E\right)$ in $J_2$. Then, in the second step, the two relative orderings are combined by interleaving the items in the two subsets. For instance, if the interleaving process is $\omega \left(J_1\mathrm{,}{J}_2\right)=\left(J_1\mathrm{,}{J}_2\mathrm{,}{J}_2\mathrm{,}{J}_1\mathrm{,}{J}_2\mathrm{,}{J}_2\right)$, where the relative ordering of the items in each subset remains unchanged, the combined ordering is then determined by the composition

$\omega \left(J_1\mathrm{,}{J}_2\right)\ast \left(\phi \left(J_1\right)\mathrm{,}\phi \left(J_2\right)\right)=\left(C\succ B\succ D\succ A\succ F\succ E\right)=\phi \left(J\right)\mathrm{.}$

Given the two subsets $J_1$ and $J_2$ with their orderings $\phi \left(J_1\right)$ and $\phi \left(J_2\right)$ and interleaving $\omega \left(J_1\mathrm{,}{J}_2\right)$ generated from models with probability distributions $f_{J_1}\mathrm{,}{g}_{J_2}$ and $m_{\omega }$, respectively, the probability of observed ordering under the riffle independence model is

$P\left(\phi \left(J\right)\right)=m_{\omega }\left(\omega \left(J_1,J_2\right)\right)f_{J_1}\left(\phi \left(J_1\right)\right)g_{J_2}\left(\phi \left(J_2\right)\right).$

There are two formulations of riffle shuffle for rank data in statistics: probabilistic and exploratory. In the riffled independence model, the set of items is partitioned recursively, while in the exploratory approach the set of voters is partitioned recursively.

11. Conclusions

The main contribution of this paper is the introduction of an exploratory riffle shuffling procedure to reveal and display the structure of diffuse rank data for large sample sizes. The new notion of a coherent cluster, that we developed, is simply based on the geometric notion of taxicab projection of points on the first TCA axis globally and locally; furthermore, it has nice mathematical properties. Coherent clusters of a coherent group represent the same latent variable opposing preferred items to disliked items, and can easily be interpreted and displayed.

Like Occam’s razor, step by step, our procedure peels the essential structural layers (coherent groups) of rank data.

Our method was able to discover some other aspects of the rank data, such as outliers or small groups, which are eclipsed or masked by well-established methods, such as distance or random utility-based methods. The major reason for this is that in random utility-based methods the multivariate nature of a preference is reduced to binary preferences (paired comparisons), and in Mallows distance related methods distances between any two preferences are bounded.

We presented a new index, Cross, that quantifies the extent of crossing of scores between the optimal binary partition of the items that resulted from TCA. The crossing index of a group is based on the first taxicab dispersion measure: it takes values between 0 and 100%, so it is easily interpretable.

The proposed approach can easily be generalized to the analysis of rankings with ties and partial rankings.

The package TaxicabCA written in R available on CRAN can be used to do the calculations.

Acknowledgements

Choulakian’s research has been supported by NSERC grant (RGPIN-2017-05092) of Canada.

Appendix

Let $R=\left(r_{ij}\right)$ for $i=1,\cdots ,n$ and $j=1,\cdots ,d$ represent the Borda scorings for preferences, where $r_{ij}$ takes values $\mathrm{0,}\cdots \mathrm{,}d-1$. Similarly, let $\bar{R}$ represent the reverse Borda scorings, whose column sums are the cordinates of the row named $nega=n\bar{\beta }={1^{\prime }}_n\bar{R}$. We consider the application of TCA to the data set

$R_{nega}=\left(\begin{array}{c}R\\ nega\end{array}\right)$

of size $\left(n+1\right)\times d$. So let

$P=R_{nega}/t$

be the correspondence table associated with $R_{nega}$, where $t=2n{\displaystyle {\sum }_{j=0}^{d-1}}j=nd\left(d-1\right)$. We have

$p_{i\ast }=\frac{1}{2n}\text{for}i=\mathrm{1,}\cdots \mathrm{,}n$ (14)

$=\frac{1}{2}\text{for}i=n+\mathrm{1,}$ (15)

and

$p_{\ast j}=\frac{1}{d}\text{for}j=\mathrm{1,}\cdots \mathrm{,}d\mathrm{.}$ (16)

The first residuel correspondence matrix will be

$p_{ij}^{\left(1\right)}=p_{ij}-p_{i\ast }{p}_{\ast j}$ (17)

$=\frac{r_{ij}}{t}-\frac{1}{2n}\mathrm{.}\frac{1}{d}\text{for}i=\mathrm{1,}\cdots \mathrm{,}n$ (18)

$=\frac{neg{a}_j}{t}-\frac{1}{2}\mathrm{.}\frac{1}{d}\text{for}i=n+1.$ (19)

Consider the nontrivial binary partition of the set $S=\left\{\mathrm{0,1,}\cdots \mathrm{,}d-1\right\}$ into $S=S_1\cup S_2$, where $\left|S_1\right|=d_1$, $\left|S_2\right|=d_2$ and $d=d_1+d_2$. To eliminate the sign indeterminacy in the first TCA principal axis, we fix $v_1\left(nega\right)=v_1\left(n+1\right)=-1$ ; and we designate by $S_1$ the set of item indices such that the first TCA principal axis coordinates are negative, that is, $u_1\left(j\right)=-1$ for $j\in S_1$. It follows that $u_1\left(j\right)=1$ for $j\in S_2$.

Now we have by (4) for $i=1,\cdots ,n$

$\begin{array}{c}{a}_{i1}={\displaystyle {\sum }_{j=1}^d{u}_1\left(j\right)p_{ij}^{\left(1\right)}}\\ ={\displaystyle {\sum }_{j\in S_1}{u}_1\left(j\right)p_{ij}^{\left(1\right)}}+{\displaystyle {\sum }_{j\in S_2}{u}_1\left(j\right)p_{ij}^{\left(1\right)}}\\ =-{\displaystyle {\sum }_{j\in S_1}{p}_{ij}^{\left(1\right)}}+{\displaystyle {\sum }_{j\in S_2}{p}_{ij}^{\left(1\right)}}\\ =-2{\displaystyle {\sum }_{j\in S_1}{p}_{ij}^{\left(1\right)}}\text{by}\left(\text{17}\right)\\ =-2{\displaystyle {\sum }_{j\in S_1}\left(\frac{r_{ij}}{t}-\frac{1}{2n}\mathrm{.}\frac{1}{d}\right)}\text{by}\left(\text{18}\right)\\ =\frac{d_1}{nd}-\frac{2}{t}{\displaystyle {\sum }_{j\in S_1}{r}_{ij}}\mathrm{<mo>\; ;\; </mo>}\end{array}$ (20)

and from which we deduce by (5) for $i=1,\cdots ,n$

$f_{i1}=\frac{a_{i1}}{p_{i\ast }}=\frac{2d_1}{d}-\frac{4}{d\left(d-1\right)}{\displaystyle {\sum }_{j\in S_1}{r}_{ij}}\mathrm{.}$ (21)

We have the following Theorem concerning the first TCA principal factor scores of respondents $f_{i1}$ for $i=1,\cdots ,n$.

Theorem 1:

a) The maximum number of distinct clusters of n respondents on the first TCA principal axis (distinct $f_{i1}$ values) is $d_1{d}_2+1$.

Proof: We consider the two extreme cases of $S_1$ and calculate the summation term in (21):

For $S_1=\left\{0,1,\cdots ,d_1-1\right\}$, ${\displaystyle {\sum }_{j\in S_1}{r}_{ij}}={\displaystyle {\sum }_{j=0}^{d_1-1}}j=\frac{d_1\left(d_1-1\right)}{2}$.

For $S_1=\left\{d-d_1,1,\cdots ,d-1\right\}$, ${\displaystyle {\sum }_{j\in S_1}{r}_{ij}}={\displaystyle {\sum }_{j=d-d_1}^{d-1}}j={\displaystyle {\sum }_{j=d_2}^{d-1}}j=\frac{d_1\left(d_2+d-1\right)}{2}$.

It follows that

$\frac{d_1\left(d_1-1\right)}{2}\le {\displaystyle \underset{j\in S_1}{\sum }}{r}_{ij}\le \frac{d_1\left(d_2+d-1\right)}{2};$

so ${\displaystyle {\sum }_{j\in S_1}}{r}_{ij}$ can take at most $\frac{d_1\left(d_2+d-1\right)}{2}-\frac{d_1\left(d_1-1\right)}{2}+1=d_1{d}_2+1$ values.

b) The maximum value that $f_{i1}$ can attain is $2\frac{d_1{d}_2}{d\left(d-1\right)}$.

Proof: From (21) and Part a, it follows that the maximum value that $f_{i1}$ can attain is $\left(\frac{2d_1}{d}-\frac{4}{d\left(d-1\right)}\frac{d_1\left(d_1-1\right)}{2}\right)=2\frac{d_1{d}_2}{d\left(d-1\right)}$.

c) The minimum value that $f_{i1}$ can attain is $-2\frac{d_1{d}_2}{d\left(d-1\right)}$.

Proof: From (21) and Part a, it follows that the minimum value that $f_{i1}$ can attain is $\left(\frac{2d_1}{d}-\frac{4}{d\left(d-1\right)}\frac{d_1\left(d_2+d-1\right)}{2}\right)=-2\frac{d_1{d}_2}{d\left(d-1\right)}$.

d) If the number of distinct clusters is maximum, $d_1{d}_2+1$, then the gap between two contiguous $f_{i1}$ values is $\frac{4}{d\left(d-1\right)}$.

Proof: Suppose that the number of distinct clusters is maximum, $d_1{d}_2+1$. We consider the first TCA factor score $f_{i1}=\frac{2d_1}{d}-\frac{4}{d\left(d-1\right)}{\displaystyle {\sum }_{j\in S_1}}{r}_{ij}$ which is different in value from the two extreme values $\pm 2\frac{d_1{d}_2}{d\left(d-1\right)}$. Then $f_{i_{1}1}=\frac{2d_1}{d}-\frac{4}{d\left(d-1\right)}\left(-1+{\displaystyle {\sum }_{j\in S_1}}{r}_{ij}\right)$ will be the contiguous higher value to $f_{i1}$ ; and similarly $f_{i_{2}1}=\frac{2d_1}{d}-\frac{4}{d\left(d-1\right)}\left(1+{\displaystyle {\sum }_{j\in S_1}}{r}_{ij}\right)$ will be the contiguous lower value to $f_{i1}$ ; and the required result follows.

Proposition 1: For a voting profile V, ${\delta }_1\ge \left|f_1\left(nega\right)\right|$.

Proof: Let $a_1=\left(\begin{array}{c}{a}_{11}\\ a_1\left(nega\right)\end{array}\right)$. We need the following three observations.

First, it is well known that $a_1$ is centered by (5) and (9),

${1^{\prime }}_{n+1}{a}_1=0={1^{\prime }}_n{a}_{11}+a_1\left(nega\right)\mathrm{<mo>\; ;\; </mo>}$

from which we get,

$\left|{1^{\prime }}_n{a}_{11}\right|=\left|a_1\left(nega\right)\right|\mathrm{.}$ (22)

Second, by triangle inequality of the L₁ norm we have

${\Vert a_{11}\Vert }_1\ge \left|{1^{\prime }}_n{a}_{11}\right|\mathrm{.}$ (23)

Third, the marginal relative frequency of the nega row is $p_{nega\ast }=1/2$ by (15), and $f_{i1}=a_{i1}/p_{i\ast }$ for $i=1,\cdots ,n+1$ by (5); so we have

$f_1\left(nega\right)=2a_1\left(nega\right)\mathrm{.}$ (24)

Now we have by (7)

$\begin{array}{c}{\delta }_1={\Vert a_1\Vert }_1={\Vert a_{11}\Vert }_1+\left|a_1\left(nega\right)\right|\\ \ge \left|{1^{\prime }}_n{a}_{11}\right|+\left|a_1\left(nega\right)\right|\text{by}\left(\text{23}\right)\\ =2\left|a_1\left(nega\right)\right|\text{by}\left(\text{22}\right)\\ =\left|f_1\left(nega\right)\right|\text{by}\left(\text{24}\right)\end{array}$ (25)

Propostion 2: Let $coh{C}_m\left(\alpha \right)=V_{m\mathrm{,}\alpha }$ be the αth coherent cluster of the mth coherent group characterized by $f_1^{V_{m\mathrm{,}\alpha }}\left(\sigma \right)=f_{\alpha }^{V_m}$ for all $\sigma \in coh{C}_m\left(\alpha \right)$. Then ${\delta }_1=f_{\alpha }^{V_m}=-f_1\left(nega\right)$.

Proof: By Definition 1 of the coherency of the cluster $V_{m\mathrm{,}\alpha }$, we have $0<f_1^{V_{m,\alpha }}\left(i\right)=f_{\alpha }^{V_m}$ for $i=\mathrm{1,}\cdots \mathrm{,}\left|coh{C}_m\left(\alpha \right)\right|$ ; by (5) it follows that $0<a_{i1}=f_{\alpha }^{V_m}/n$ for $i=\mathrm{1,}\cdots \mathrm{,}\left|coh{C}_m\left(\alpha \right)\right|$ ; so (25) becomes equality, ${\Vert a_{11}\Vert }_1={\displaystyle {\sum }_{i=1}^n}{a}_{i1}=\left|{1^{\prime }}_n{a}_{11}\right|$, and the required result follows.

Proposition 3 is a corollary to the following general result

Theorem 3: If the first TCA principal axis of the columns of $R_{nega}$ is $v_1=\left(\begin{array}{c}{1}_n\\ -1\end{array}\right)$, then

the first principal column factor score $g_1$ of the d items is an affine function of the Borda scale $\beta$ ; that is, $g_1\left(j\right)=\frac{2}{d-1}\beta \left(j\right)-1$ or $corr\left(g_1\mathrm{,}\beta \right)=1$.

Proof: Suppose that $v_1=\left(\begin{array}{c}{1}_n\\ -1\end{array}\right)$ ; then by (4) for $j=1,\cdots ,d$

$\begin{array}{c}{b}_1\left(j\right)={\displaystyle \underset{i=1}{\overset{n+1}{\sum }}}{v}_1\left(i\right)p_{ij}^{\left(1\right)}\\ ={\displaystyle \underset{i=1}{\overset{n}{\sum }}}{p}_{ij}^{\left(1\right)}-p_{\left(n+1\right)j}^{(\; 1\; )}\end{array}$

$=2{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{p}_{ij}^{\left(1\right)}$ by (17)

$=2{\displaystyle \underset{i=1}{\overset{n}{\sum }}}\left(p_{ij}-p_{i\ast }{p}_{\ast j}\right)$

$=2{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{r}_{ij}/t-p_{\ast j}$ by (14)

$=2n\beta \left(j\right)/t-p_{\ast j}$

Thus by (5) for $j=1,\cdots ,d$

$g_1\left(j\right)=b_1\left(j\right)/p_{\ast j}=\frac{2n\beta \left(j\right)/t-p_{\ast j}}{p_{\ast j}}=\frac{2\beta \left(j\right)}{d-1}-1.$

Proposition 4: The crossing index of a coherent cluster is

$Cross\left(cohC\left(\alpha \right)\right)=\frac{2\left(\alpha -1\right)}{d_1{d}_2}\mathrm{.}$

Proof: Easily shown by using Definition 3 and Proposition 2.

The proof of Theorem 2a easily follows from Theorem 3. The proof of Theorem 2b is similar to the proof of Proposition 1. The proof of Theorem 2c is similar to the proof of Proposition 4.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Kamishima, T. (2003) Nantonac Collaborative Filtering: Recommendation Based on Order Responses. Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington DC, August 2003, 583-588. https://doi.org/10.1145/956750.956823
[2]	Huang, J. and Guestrin, C. (2012) Uncovering the Riffled Independence Structure of Ranked Data. Electronic Journal of Statistics, 6, 199-230. https://doi.org/10.1214/12-EJS670
[3]	Lu, T. and Boutilier, C. (2014) Effective Sampling and Learning for Mallows Models with Pairwise Preference Data. Journal of Machine Learning Research, 15, 3783-3829.
[4]	Vitelli, V., Sørenson, Ø., Crispino, M., Frigessi, A. and Arjas, E. (2018) Probabilistic Preference Learning with the Mallows Rank Model. Journal of Machine Learning Research, 18, 1-49.
[5]	Diaconis, P. (1989) A Generalization of Spectral Analysis with Application to Ranked Data. Annals of Statistics, 17, 949-979. https://doi.org/10.1214/aos/1176347251
[6]	Marden, J.I. (1995) Analyzing and Modeling of Rank Data. Chapman & Hall, London
[7]	Alvo, M. and Yu, P. (2014) Statistical Methods for Ranking Data. Springer, New York. https://doi.org/10.1007/978-1-4939-1471-5
[8]	Bayer, D. and Diaconis, P. (1992) Trailing the Dovetail Shuffle to Its Lair. Annals of Probability, 2, 294-313. https://doi.org/10.1214/aoap/1177005705
[9]	Choulakian, V. (2016) Globally Homogenous Mixture Components and Local Heterogeneity of Rank Data. arXiv:1608.05058
[10]	Choulakian, V. (2006) Taxicab Correspondence Analysis. Psychometrika, 71, 333-345. https://doi.org/10.1007/s11336-004-1231-4
[11]	Choulakian, V. (2016) Matrix Factorizations Based on Induced Norms. Statistics, Optimization and Information Computing, 4, 1-14. https://doi.org/10.19139/soic.v4i1.160
[12]	De Borda, J. (1781) Mémoire sur les élections au scrutin. Histoire de L’Académie Royale des Sciences, 102, 657-665.
[13]	Benzécri, J.P. (1991) Comment on Leo A. Goodman’s Invited Paper. Journal of the American Statistical Association, 86, 1112-1115. https://doi.org/10.1080/01621459.1991.10475157
[14]	Van de Velden, M. (2000) Dual Scaling and Correspondence Analysis of Rank Order Data. In: Heijmans, R.D.H., Pollock, D.S.G. and Satorra, A. Eds., Innovations in Multivariate Statistical Analysis, Vol. 36, Kluwer Academic Publishers, Dordrecht, 87-99. https://doi.org/10.1007/978-1-4615-4603-0_6
[15]	Torres, A. and Greenacre, M. (2002) Dual Scaling and Correspondence Analysis of Preferences, Paired Comparisons and Ratings. International Journal of Research in Marketing, 19, 401-405. https://doi.org/10.1016/S0167-8116(02)00101-5
[16]	Nishisato, S. (1980) Analysis of Categorical Data: Dual Scaling and Its Applications. University of Toronto Press, Toronto. https://doi.org/10.3138/9781487577995
[17]	Choulakian, V. (2014) Taxicab Correspondence Analysis of Ratings and Rankings. Journal de la Société Française de Statistique, 155, 1-23.
[18]	Khot, S. and Naor, A. (2012) Grothendieck-Type Inequalities in Combinatorial Optimization. Communications on Pure and Applied Mathematics, 65, 992-1035. https://doi.org/10.1002/cpa.21398
[19]	Choulakian, V. and Abou-Samra, G. (2020) Mean Absolute Deviations about the Mean, Cut Norm and Taxicab Correspondence Analysis. Open Journal of Statistics, 10, 97-112. https://doi.org/10.4236/ojs.2020.101008
[20]	Diaconis, P. (1988) Group Representations in Probability and Statistics. Institute of Mathematical Statistics, Hayward, CA.
[21]	Murphy, T.B. and Martin, D. (2003) Mixtures of Distance-Based Models for Ranking Data. Computational Statistics and Data Analysis, 41, 645-655. https://doi.org/10.1016/S0167-9473(02)00165-2