Partition-Mallows Model and Its Inference
for Rank Aggregation

The partition model in BARD (Deng et al.,, 2014) assumes that $U$ can be partitioned into two non-overlapping subsets: $U=U_{R}\cup U_{B}$, with $U_{R}$ representing the set of relevant entities and $U_{B}$ for the background ones. Let $I=\{I_{i}\}_{i\in U}$ be the vector of group indicators, where $I_{i}=\mathbb{I}(E_{i}\in U_{R})$ and $\mathbb{I}(\cdot)$ is the indicator function. This formulation makes sense in many applications where people are only concerned about a fixed number of top-ranked entities. Under this formulation, the information in a ranking list $\tau_{k}$ can be equivalently represented by a triplet $(\tau_{k}^{0},\tau_{k}^{1\mid 0},\tau_{k}^{1})$, where $\tau_{k}^{0}$ denotes relative rankings of all background entities, $\tau_{k}^{1\mid 0}$ denotes relative rankings of relevant entities among the background entities and $\tau_{k}^{1}$ denotes relative rankings of all relevant entities.

Deng et al., (2014) suggested a three-component model for $\tau_{k}$ by taking advantage of its equivalent decomposition:

$\displaystyle P(\tau_{k}\mid I)=P(\tau_{k}^{0},\tau_{k}^{1\mid 0},\tau_{k}^{1}\mid I)=P(\tau_{k}^{0}\mid I)\times P(\tau_{k}^{1\mid 0}\mid I)\times P(\tau_{k}^{1}\mid\tau_{k}^{1\mid 0},I),$

(1)

where both $P(\tau_{k}^{0}\mid I)$ (relative ranking of the background entities) and $P(\tau_{k}^{1}\mid\tau_{k}^{1\mid 0},I)$ (relative ranking of the relevant entities conditional on their set of positions relative to background entities) are uniform, and the relative ranking of a relevant entity $E_{i}$ among background ones follows a power-law distribution with parameter $\gamma_{k}>0$, i.e.,

$$P(\tau_{k}^{1\mid 0}(i)=t\mid I)=q(t\mid\gamma_{k},n_{0})\propto t^{-\gamma_{k}}\cdot\mathbb{I}(1\leq t\leq n_{0}+1),$$

leading to the following explicit forms for the three terms in equation (1):

	$\displaystyle P(\tau_{k}^{0}\mid I)$	$\displaystyle=$	$\displaystyle\frac{1}{n_{0}!},$		(2)
	$\displaystyle P(\tau_{k}^{1\mid 0}\mid I)$	$\displaystyle=$	$\displaystyle\prod_{i\in U_{R}}q(\tau_{k}^{1\mid 0}(i)\mid\gamma_{k},I)=\frac{1}{(B_{\tau_{k},I})^{\gamma_{k}}\times(C_{\gamma_{k},n_{1}})^{n_{1}}},$		(3)
	$\displaystyle P(\tau_{k}^{1}\mid\tau_{k}^{1\mid 0},I)$	$\displaystyle=$	$\displaystyle\frac{1}{A_{\tau_{k},I}}\times\mathbb{I}\big{(}\tau_{k}^{1}\in\mathcal{A}_{U_{R}}(\tau_{k}^{1\mid 0})\big{)},$		(4)

where $n_{1}=\sum_{i=1}^{n}I_{i}$ and $n_{0}=n-n_{1}$ are the counts of relevant and background entities respectively, $B_{\tau_{k},I}=\prod_{i\in U_{R}}\tau_{k}^{1\mid 0}(i)$, $C_{\gamma_{k},n_{1}}=\sum_{t=1}^{n_{0}+1}t^{-\gamma_{k}}$ is the normalizing constant of the power-law distribution, $\mathcal{A}_{U_{R}}(\tau_{k}^{1\mid 0})$ is the set of $\tau_{k}^{1}$’s that are compatible with $\tau_{k}^{1\mid 0}$, and $A_{\tau_{k},I}=\#\{\mathcal{A}_{U_{R}}(\tau_{k}^{1\mid 0})\}=\prod_{t=1}^{n_{0}+1}(n_{\tau_{k},t}^{1\mid 0}!)$ with $n_{\tau_{k},t}^{1\mid 0}=\sum_{i\in U_{R}}\mathbb{I}(\tau_{k}^{1\mid 0}(i)=t)$.

Intuitively, this model assumes that each ranker first randomly places all background entities to generate $\tau_{k}^{0}$, then “inserts” each relevant entity independently into the list of background entities according to a truncated power-law distribution to generate $\tau_{k}^{1\mid 0}$, and finally draws $\tau_{k}^{1}$ uniformly from $\mathcal{A}_{U_{R}}(\tau_{k}^{1\mid 0})$. In other words, $\tau_{k}^{0}$ serves as a baseline for modeling $\tau_{k}^{1\mid 0}$ and $\tau_{k}^{1}$. It is easy to see from the model that a more reliable ranker should possess a larger $\gamma_{k}$. With the assumption of independent rankers, we have the full-data likelihood:

	$\displaystyle P(\tau_{1},\cdots,\tau_{m}\mid I,\boldsymbol{\gamma})$	$\displaystyle=$	$\displaystyle\prod_{k=1}^{m}P(\tau_{k}\mid I,\gamma_{k})$		(5)
		$\displaystyle=$	$\displaystyle[(n_{0})!]^{-m}\times\prod_{k=1}^{m}\frac{\mathbb{I}\big{(}\tau_{k}^{1}\in\mathcal{A}_{U_{R}}(\tau_{k}^{1\mid 0})\big{)}}{A_{\tau_{k},I}\times(B_{\tau_{k},I})^{\gamma_{k}}\times\big{(}C_{\gamma_{k},n_{1}}\big{)}^{n_{1}}},$

where $\boldsymbol{\gamma}=(\gamma_{1},\cdots,\gamma_{m})$. A detailed Bayesian inference procedure for $(I,\boldsymbol{\gamma})$ via Markov chain Monte Carlo can be found in Deng et al., (2014).

Mallows, (1957) proposed the following probability model for a ranking list $\tau$ of $n$ entities:

$$\pi(\tau\mid\tau_{0},\phi)=\dfrac{1}{Z_{n}(\phi)}\cdot\exp\{-\phi\cdot d(\tau,\tau_{0})\},$$

(6)

where $\tau_{0}$ denotes the true ranking list, $\phi>0$ characterizing the reliability of $\tau$, function $d(\cdot,\cdot)$ is a distance metric between two ranking lists, and

$$Z_{n}(\phi)=\sum_{\tau^{\prime}}\exp\{-\phi\cdot d(\tau^{\prime},\tau_{0})\}=\frac{\prod_{t=2}^{n}(1-e^{-t\phi})}{(1-e^{-\phi})^{n-1}}$$

(7)

being the normalizing constant, whose analytic form was derived in Diaconis, (1988). Clearly, a larger $\phi$ means that $\tau$ is more stable and concentrates in a tighter neighborhood of $\tau_{0}$. A common choice of $d(\cdot,\cdot)$ is the Kendall tau distance.

The Mallows model under the Kendall tau distance can also be equivalently described by an alternative multistage model, which selects and positions entities one by one in a sequential fashion, where $\phi$ serves as a common parameter that governs the probabilistic behavior of each entity in the stochastic process (Mallows,, 1957). Later on, Fligner and Verducci, (1986) extended the Mallows model by allowing $\phi$ to vary at different stages, i.e., introducing a position-specific parameter $\phi_{i}$ for each position $i$, which leads to a very flexible, in many cases too flexible, framework to model rank data. To stabilize the generalized Mallows model by Fligner and Verducci, (1986), Li et al., (2020) proposed to put a structural constraint on $\phi_{i}$s of the form $\phi_{i}=\phi\cdot(1-\alpha^{i})$ with $0<\phi<1$ and $0\leq\alpha\leq 1$. As a probabilistic model for rank data, the Mallows model enjoys great interpretability, model compactness, inference and computation efficiency. For a comprehensive review of the Mallows model and its extensions, see Irurozki et al., (2014) and Li et al., (2020).

To combine the partition model with the Mallows model, a naive strategy is to simply replace the uniform model for the relevant entities, i.e., $P(\tau_{k}^{1}\mid\tau_{k}^{1|0},I)$ in (1), by the Mallows model, which leads to the updated Equation (4) as below:

$$P(\tau_{k}^{1}\mid\tau_{k}^{1\mid 0},I)=\frac{\pi(\tau_{k}^{1})}{Z_{\tau_{k},I}}\times\mathbb{I}\big{(}\tau_{k}^{1}\in\mathcal{A}_{U_{R}}(\tau_{k}^{1\mid 0})\big{)},$$

where $\pi(\tau_{k}^{1})$ is the Mallows density of $\tau_{k}^{1}$ and $Z_{\tau_{k},I}=\sum_{\tau\in\mathcal{A}_{U_{R}}(\tau_{k}^{1\mid 0})}\pi(\tau)$ is the normalizing constant of the Mallows model with a constraint due to the compatibility of $\tau_{k}^{1}$ with respect to $\mathcal{A}_{U_{R}}(\tau_{k}^{1\mid 0})$. Apparently, the calculation of $Z_{\tau_{k},I}$, which involves the summation over the whole space of $\mathcal{A}_{U_{R}}(\tau_{k}^{1\mid 0})$, whose size is $A_{\tau_{k},I}=\#\{\mathcal{A}_{U_{R}}(\tau_{k}^{1\mid 0})\}=\prod_{t=1}^{n_{0}+1}(n_{\tau_{k},t}^{1\mid 0}!)$, is infeasible for most practical cases, rendering such a naive combination of the Mallows model and the partition model impractical.

To avoid the challenging computation caused by the constraints due to $\mathcal{A}_{U_{R}}(\tau_{k}^{1\mid 0})$, we rewrite the partition model by switching the roles of $\tau_{k}^{0}$ and $\tau_{k}^{1}$ in the model: instead of decomposing $\tau_{k}$ as $(\tau_{k}^{0},\tau_{k}^{1\mid 0},\tau_{k}^{1})$ conditioning on the group indicators $I$, we decompose $\tau_{k}$ into an alternative triplet $(\tau_{k}^{1},\tau_{k}^{0\mid 1},\tau_{k}^{0})$, where $\tau_{k}^{0\mid 1}$ denotes the relative reverse rankings of background entities among the relevant ones. Formally, we note that $\tau_{k}^{0\mid 1}(i)\triangleq n_{1}+2-\tau_{k|\{i\}\cup U_{R}}(i)$ for any $i\in U_{R}$, where $\tau_{k|\{i\}\cup U_{R}}(i)$ denotes the relative ranking of a background entity among the relevant ones. In this reverse partition model, we first order the relevant entities according to a certain distribution and then use them as a reference system to “insert” the background entities. Figure 1 illustrates the equivalence between $\tau_{k}$ and its two alternative presentations, $(\tau_{k}^{0},\tau_{k}^{1\mid 0},\tau_{k}^{1})$ and $(\tau_{k}^{1},\tau_{k}^{0\mid 1},\tau_{k}^{0})$.

Given the group indicator vector $I$, the reverse partition model based on $(\tau_{k}^{1},\tau_{k}^{0\mid 1},\tau_{k}^{0})$ gives rise to the following distributional form for $\tau_{k}$:

$\displaystyle P(\tau_{k}\mid I)=P(\tau_{k}^{1},\tau_{k}^{0\mid 1},\tau_{k}^{0}\mid I)=P(\tau_{k}^{1}\mid I)\times P(\tau_{k}^{0\mid 1}\mid I)\times P(\tau_{k}^{0}\mid\tau_{k}^{0\mid 1},I),$

(8)

which is analogous to (1) for the original partition model in BARD. Comparing to (1), however, the new form (8) enables us to specify an unconstrained marginal distribution for $\tau_{k}^{1}$. Moreover, due to the symmetry between $\tau_{k}^{1\mid 0}$ and $\tau_{k}^{0\mid 1}$, it is highly likely that the power-law distribution, which was shown in Deng et al., (2014) to approximate the distribution of $\tau_{k}^{1\mid 0}(i)$ well for each $E_{i}\in U_{R}$, can also model $\tau_{k}^{0\mid 1}(i)$ for each $E_{i}\in U_{B}$ reasonably well. Detailed numerical validations are shown in Supplementary Material.

If we assume that all relevant entities are exchangeable, all background entities are exchangeable, and the relative reserve ranking of a background entity among the relevant entities follows a power-law distribution, we have

	$\displaystyle P(\tau_{k}^{1}\mid I)$	$\displaystyle=$	$\displaystyle\frac{1}{n_{1}!},$		(9)
	$\displaystyle P(\tau_{k}^{0\mid 1}\mid I,\gamma_{k})$	$\displaystyle=$	$\displaystyle\prod_{i\in U_{B}}P(\tau_{k}^{0\mid 1}(i)\mid I,\gamma_{k})=\frac{1}{(B^{*}_{\tau_{k},I})^{\gamma_{k}}\times(C^{*}_{\gamma_{k},n_{1}})^{n_{0}}},$		(10)
	$\displaystyle P(\tau_{k}^{0}\mid\tau_{k}^{0\mid 1},I)$	$\displaystyle=$	$\displaystyle\frac{1}{A^{*}_{\tau_{k},I}}\times\mathbb{I}\big{(}\tau_{k}^{0}\in\mathcal{A}_{U_{R}}(\tau_{k}^{0\mid 1})\big{)},$		(11)

where $n_{1}$ and $n_{0}$ are numbers of relevant and background entities, respectively, $B^{*}_{\tau_{k},I}=\prod_{i\in U_{B}}\tau_{k}^{0\mid 1}(i)$ is the unnormalized part of the power-law, $C^{*}_{\gamma_{k},n_{1}}=\sum_{t=1}^{n_{1}+1}t^{-\gamma_{k}}$ is the normalizing constant, $\mathcal{A}_{U_{B}}(\tau_{k}^{0\mid 1})$ is the set of all $\tau_{k}^{0}$ that are compatible with a given $\tau_{k}^{0\mid 1}$, and $A^{*}_{\tau_{k},I}=\#\{\mathcal{A}_{U_{B}}(\tau_{k}^{0\mid 1})\}=\prod_{t=1}^{n_{1}+1}(n_{\tau_{k},t}^{0\mid 1}!)$ with $n_{\tau_{k},t}^{0\mid 1}=\sum_{i\in U_{B}}\mathbb{I}(\tau_{k}^{0\mid 1}(i)=t)$. Apparently, the likelihood of this reverse-partition model shares the same structure as that of the original partition model in BARD, and thus can be inferred in a similar way.

The reverse partition model introduced in section  3.1 allows us to freely model $\tau_{k}^{1}$ beyond a uniform distribution, which is infeasible for the original partition model in BARD. Here we employ the Mallows model for $\tau_{k}^{1}$ due to its interpretability, compactness and computability. To achieve this, we replace the group indicator vector $I$ in the partition model by a more general indicator vector $\mathcal{I}=\{\mathcal{I}_{i}\}_{i=1}^{n}$, which takes value in $\Omega_{\mathcal{I}}$, the space of all permutations of $\{1,\cdots,n_{1},\underbrace{0,\ldots,0}_{n_{0}}\}$, with $\mathcal{I}_{i}=0$ if $E_{i}\in U_{B}$, and $\mathcal{I}_{i}=k>0$ if $E_{i}\in U_{R}$ and is ranked at position $k$ among all relevant entities in $U_{R}$. Figure 1 provides an illustrative example of assigning an enhanced indicator vector $\mathcal{I}$ to a universe of 10 entities with $n_{1}=5$.

Based on the status of $\mathcal{I}$, we can define subvectors $\mathcal{I}^{+}$ and $\mathcal{I}^{0}$, where $\mathcal{I}^{+}$ stands for the subvector of $\mathcal{I}$ containing all positive elements in $\mathcal{I}$, and $\mathcal{I}^{0}$ for the remaining zero elements in $\mathcal{I}$. Figure 1 demonstrates the constructions of $\mathcal{I}$, $\mathcal{I}^{+}$ and $\mathcal{I}^{0}$, and the equivalence between $\tau_{k}$, $(\tau_{k}^{0},\tau_{k}^{1\mid 0},\tau_{k}^{1})$, and $(\tau_{k}^{1},\tau_{k}^{0\mid 1},\tau_{k}^{0})$ given $\mathcal{I}$. Note that different from the partition model in BARD, in which we allow the number of relevant entities represented by $n_{1}$ to vary nearby its expected value, the number of relevant entities in the new model, is assumed to be fixed and known for conceptual and computational convenience. In other words, we have $|U_{R}|=n_{1}$ in the new setting.

As an analogy of Equations (1) and (8), we have the following decomposition of $\tau_{k}$ given the enhanced indicator vector $\mathcal{I}$:

$\displaystyle P(\tau_{k}\mid\mathcal{I})=P(\tau_{k}^{1},\tau_{k}^{0\mid 1},\tau_{k}^{0}\mid\mathcal{I})=P(\tau_{k}^{1}\mid\mathcal{I})\times P(\tau_{k}^{0\mid 1}\mid\mathcal{I})\times P(\tau_{k}^{0}\mid\tau_{k}^{0\mid 1},\mathcal{I}).$

(12)

Assume that $\tau_{k}^{1}\mid\mathcal{I}$ follows the Mallows model (with parameter $\phi_{k}$) centered at $\mathcal{I}^{+}$:

$\displaystyle P(\tau_{k}^{1}\mid\mathcal{I},\phi_{k})=P(\tau_{k}^{1}\mid\mathcal{I}^{+},\phi_{k})=\frac{\exp\{-\phi_{k}\cdot d_{\tau}(\tau_{k}^{1},\mathcal{I}^{+})\}}{Z_{n_{1}}(\phi_{k})},$

(13)

where $d_{\tau}(\cdot,\cdot)$ denotes Kendall tau distance and $Z_{n_{1}}(\phi_{k})$ is defined as in (7). Clearly, a larger $\phi_{k}$ indicates that ranker $\tau_{k}$ is of a higher quality, as the distribution is more concentrated at the “true ranking” defined by $\mathcal{I}^{+}$. Since the relative ranking of background entities are of no interest to us, we still assume that they are randomly ranked. Together with the power-law assumption for $\tau_{k}^{0\mid 1}(i)$, we have

	$\displaystyle P(\tau_{k}^{0\mid 1}\mid\mathcal{I})$	$\displaystyle=$	$\displaystyle P(\tau_{k}^{0\mid 1}\mid I,\gamma_{k})=\frac{1}{(B^{*}_{\gamma_{k},I})^{\gamma_{k}}\times(C^{*}_{\gamma_{k},n_{1}})^{n-n_{1}}},$		(14)
	$\displaystyle P(\tau_{k}^{0}\mid\tau_{k}^{0\mid 1},\mathcal{I})$	$\displaystyle=$	$\displaystyle P(\tau_{k}^{0}\mid\tau_{k}^{0\mid 1},I)=\frac{1}{A^{*}_{\tau_{k},I}}\times\mathbb{I}\big{(}\tau_{k}^{0}\in\mathcal{A}_{U_{R}}(\tau_{k}^{0\mid 1})\big{)},$		(15)

where notations $A^{*}_{\tau_{k},I}$, $B^{*}_{\tau_{k},I}$ and $C^{*}_{\gamma_{k},n_{1}}$ are the same as in the reverse-partition model. We call the resulting model the Partition-Mallows model, abbreviated as PAMA.

Different from the partition and reverse partition models, which quantify the quality of ranker $\tau_{k}$ with only one parameter $\gamma_{k}$ in the power-law distribution, the PAMA model contains two quality parameters $\phi_{k}$ and $\gamma_{k}$, with the former indicating the ranker’s ability of ranking relevant entities and the latter reflecting the ranker’s ability in differentiating relevant entities from background ones. Intuitively, $\phi_{k}$ and $\gamma_{k}$ reflect the quality of ranker $\tau_{k}$ in two different aspects. However, considering that a good ranker is typically strong in both dimensions, it looks quite natural to further simplify the model by assuming

$$\phi_{k}=\phi\cdot\gamma_{k},$$

(16)

with $\phi>0$ being a common factor for all rankers. This assumption, while reducing the number of free parameters by almost half, captures the natural positive correlation between $\phi_{k}$ and $\gamma_{k}$ and serves as a first-order (i.e., linear) approximation to the functional relationship between $\phi_{k}$ and $\gamma_{k}$. A wide range of numerical studies based on simulated data suggest that the linear approximation showed in (16) works reasonably well for many typical scenarios for rank aggregation. In contrast, the more flexible model with both $\phi_{k}$ and $\gamma_{k}$ as free parameters (which is referred to as PAMA^∗) suffers from unstable performance from time to time. Detailed evidences to support assumption (16) can be found in Supplementary Material.

Plugging in (16) into (13), we have a simplified model for $\tau_{k}^{1}$ given $\mathcal{I}$ as follows:

$\displaystyle P(\tau_{k}^{1}\mid\mathcal{I},\phi,\gamma_{k})=P(\tau_{k}^{1}\mid\mathcal{I}^{+},\phi,\gamma_{k})=\frac{\exp\{-\phi\cdot\gamma_{k}\cdot d_{\tau}(\tau_{k}^{1},\mathcal{I}^{+})\}}{Z_{n_{1}}(\phi\cdot\gamma_{k})}.$

(17)

Combining (14), (15) and (17), we get the full likelihood of $\tau_{k}$:

	$\displaystyle P(\tau_{k}\mid\mathcal{I},\phi,\gamma_{k})$	$\displaystyle=$	$\displaystyle P(\tau_{k}^{1}\mid\mathcal{I},\phi,\gamma_{k})\times P(\tau_{k}^{0|1}\mid\mathcal{I},\gamma_{k})\times P(\tau_{k}^{0}\mid\tau_{k}^{0|1},\mathcal{I})$		(18)
		$\displaystyle=$	$\displaystyle\frac{\mathbb{I}\big{(}\tau_{k}^{0}\in\mathcal{A}_{U_{R}}(\tau_{k}^{0\mid 1})\big{)}}{A^{*}_{\tau_{k},I}\times(B^{*}_{\tau_{k},I})^{\gamma_{k}}\times(C^{*}_{\gamma_{k},n_{1}})^{n-n_{1}}\times(D^{*}_{\tau_{k},\mathcal{I}})^{\phi\cdot\gamma_{k}}\times E^{*}_{\phi,\gamma_{k}}},$

where $D^{*}_{\tau_{k},\mathcal{I}}=\exp\{d_{\tau}(\tau_{k}^{1},\mathcal{I}^{+})\}$, $E^{*}_{\phi,\gamma_{k}}=Z_{n_{1}}(\phi\cdot\gamma_{k})=\frac{\prod_{t=2}^{n_{1}}(1-e^{-t\phi\gamma_{k}})}{(1-e^{-\phi\gamma_{k}})^{n_{1}-1}}$, and $A^{*}_{\tau_{k},\mathcal{I}}$, $B^{*}_{\tau_{k},\mathcal{I}}$ and $C^{*}_{\tau_{k},n_{1}}$ keep the same meaning as in the reverse partition model. At last, for the set of observed ranking lists $\boldsymbol{\tau}=(\tau_{1},\cdots,\tau_{m})$ from $m$ independent rankers, we have the joint likelihood:

$\displaystyle P(\boldsymbol{\tau}\mid\mathcal{I},\phi,\boldsymbol{\gamma})$

$\displaystyle=$

$\displaystyle\prod_{k=1}^{m}P(\tau_{k}\mid\mathcal{I},\phi,\gamma_{k}).$

(19)

Let $\Omega_{n}$ be the space of all permutations of $\{1,\cdots,n\}$ in which $\tau_{k}$ takes value, and let ${\boldsymbol{\theta}}=(\mathcal{I},\phi,\boldsymbol{\gamma})$ be the vector of model parameters. The PAMA model in (19), i.e., $P(\boldsymbol{\tau}\mid{\boldsymbol{\theta}})$, defines a family of probability distributions on $\Omega_{n}^{m}$ indexed by parameter ${\boldsymbol{\theta}}$ taking values in space $\boldsymbol{\Theta}=\Omega_{\mathcal{I}}\times\Omega_{\phi}\times\Omega_{\boldsymbol{\gamma}}$, where $\Omega_{\mathcal{I}}$ is the space of all permutations of $\{1,\cdots,n_{1},{\bf 0}_{n_{0}}\}$, $\Omega_{\phi}=(0,+\infty)$ and $\Omega_{\boldsymbol{\gamma}}=[0,+\infty)^{m}$. We show here that the PAMA model defined in (19) is identifiable and the model parameters can be estimated consistently under mild conditions.

To show that parameters in the PAMA model can be estimated consistently, we will first construct a consistent estimator for the indicator vector $\mathcal{I}$ as $m\rightarrow\infty$ but with the number of ranked entities $n$ fixed, and show later that $\phi$ can also be consistently estimated once $\mathcal{I}$ is given. To this end, we define $\bar{\tau}(i)=m^{-1}\sum_{k=1}^{m}\tau_{k}(i)$ to be the average rank of entity $E_{i}$ across all $m$ rankers, and assume that the ranker-specific quality parameters $\gamma_{1},\cdots,\gamma_{m}$ are i.i.d. samples from a non-atomic probability measure $F(\gamma)$ defined on $[0,\infty)$ with a finite first moment (referred to as condition $\boldsymbol{C}_{\gamma}$ hereinafter). Then, by the strong law of large numbers we have

$$\bar{\tau}(i)=\frac{1}{m}\sum_{k=1}^{m}\tau_{k}(i)\rightarrow\mathbb{E}\big{[}\tau(i)\big{]}\ a.s.\ \ \mbox{with}\ m\rightarrow\ \infty,$$

(21)

since $\{\tau_{k}(i)\}_{k=1}^{m}$ are i.i.d. random variables with expectation

$$\mathbb{E}\big{[}\tau(i)\big{]}=\mathbb{E}\Big{[}\mathbb{E}\big{[}\tau(i)\mid\gamma\big{]}\Big{]}=\int\mathbb{E}\big{[}\tau(i)\mid\gamma\big{]}dF(\gamma),$$

where $\mathbb{E}\big{[}\tau(i)\mid\gamma\big{]}$ is the conditional mean of $\tau(i)$ given the model parameters $(\mathcal{I},\phi,\gamma)$, i.e.,

$$\mathbb{E}\big{[}\tau(i)\mid\gamma\big{]}=\sum_{t=1}^{n}t\cdot P\big{(}\tau(i)=t\mid\mathcal{I},\phi,\gamma\big{)}.$$

Clearly, $\mathbb{E}\big{[}\tau(i)\big{]}$ is a function of $\phi$ given $\mathcal{I}$ and $F(\gamma)$. We define $e_{i}(\phi)\triangleq\mathbb{E}\big{[}\tau(i)\big{]}$ to emphasize $\mathbb{E}\big{[}\tau(i)\big{]}$’s nature as a continuous function of $\phi$. Without loss of generality, we suppose that $U_{R}=\{1,\cdots,n_{1}\}$ and $U_{B}=\{n_{1}+1,\cdots,n\}$, i.e., $\mathcal{I}=(1,\cdots,n_{1},0,\cdots,0)$, hereinafter. Then, the partition structure and the Mallows model embedded in the PAMA model lead to the following facts:

$$e_{1}(\phi)<\cdots<e_{n_{1}}(\phi)\ \mbox{and}\ e_{n_{1}+1}(\phi)=\cdots=e_{n}(\phi)=e_{0},\ \forall\ \phi\in\Omega_{\phi}.$$

(22)

Note that $e_{i}(\phi)$ degenerates to a constant with respect to $\phi$ (i.e., $e_{0}$) for all $i>n_{1}$ because parameter $\phi$ influences only the relative rankings of relevant entities in the Mallows model. The value of $e_{0}$ is completely determined by $F(\gamma)$. For the BARD model, it is easy to see that $e_{1}=\cdots=e_{n_{1}}\leq e_{n_{1}+1}=\cdots=e_{n}.$

Figure 2 shows some empirical estimates of the $e_{i}(\phi)$’s based on $m=100,000$ independent samples drawn from PAMA models with $n=30$, $n_{1}=15$, and $F(\gamma)=U(0,2)$, but three different $\phi$ values: (a) $\phi=0$, which corresponds to the BARD model; (b) $\phi=0.2$; and (c) $\phi=0.5$. One surprise is that in case (c), some relevant entities may have a larger $e_{i}(\phi)$ (worse ranking) than the average rank of background entities. Lemma 1 guarantees that for almost all $\phi\in\Omega_{\phi}$, $e_{0}$ is different from $e_{i}(\phi)$ for $i=1,\cdots,n_{1}$. The proof of Lemma 1 can be found in Supplementary Material.

The facts demonstrated in (22) and (23) suggest the following three-step strategy to estimate $\mathcal{I}$: (a) find the subset $S_{0}$ of $n_{0}=(n-n_{1})$ entities from $U$ so that the within-subset variation of the $\bar{\tau}(i)$’s is the smallest, i.e.,

$$S_{0}=\operatorname*{arg\,min}_{S\in U,\ |S|=n_{0}}\sum_{i\in S}(e_{i}-\bar{e}_{S})^{2},\ \ \mbox{with}\ \bar{e}_{S}=n_{0}^{-1}\sum_{i\in S}e_{i},$$

(24)

and let $\tilde{U}_{B}=S_{0}$ be an estimate of $U_{B}$; (b) rank the entities in $U\setminus S_{0}$ by $\bar{\tau}(i)$ increasingly and use the obtained ranking $\tilde{\mathcal{I}}^{+}$ as an estimate of $\mathcal{I}^{+}$; (c) combine the above two steps to obtain the estimate $\tilde{\mathcal{I}}$ of $\mathcal{I}$. This can be achieved by defining $\tilde{U}_{R}=U\setminus\tilde{U}_{B}$ and $\tilde{\mathcal{I}}^{+}=rank(\{\bar{\tau}(i):i\in\tilde{U}_{R}\}),$ and obtain $\tilde{\mathcal{I}}=(\tilde{\mathcal{I}}_{1},\cdots,\tilde{\mathcal{I}}_{n})$, with $\tilde{\mathcal{I}}_{i}=\tilde{\mathcal{I}}^{+}_{i}\cdot\mathbb{I}(i\in\tilde{U}_{R}).$

Note that $\tilde{U}_{B}$ is based on the mean ranks, $\{\bar{\tau}(i)\}_{i\in U}$, thus is clearly a moment estimator. Although this three-step estimation strategy is neither statistically efficient nor computationally feasible (step (a) is NP-hard), it nevertheless serves as a prototype for developing the consistency theory. Theorem 2 guarantees that $\tilde{\mathcal{I}}$ is a consistent estimator of $\mathcal{I}$ under mild conditions.

Theorem 2 tells us that estimating $\mathcal{I}$ is straightforward if the number of independent rankers $m$ goes to infinity: a simple moment method ignoring the quality difference of rankers can provide us a consistent estimate of $\mathcal{I}$. In a practical problem where only a finite number of rankers are involved, however, more efficient statistical inference of the PAMA model based on Bayesian or frequentist principles becomes more attractive as effectively utilizing the quality information of different rankers is critical.

With $n_{0}$ and $n_{1}$ fixed, parameter $\gamma_{k}$, which governs the power-law distribution for the rank list $\tau_{k}$, cannot be estimated consistently. Thus, its distribution $F(\gamma)$ cannot be determined nonparametrically even when the number of rank lists $m$ goes to infinity. We impose a parametric form $F_{\psi}(\gamma)$ with $\psi$ as the hyper-parameter and refer to the resulting hierarchical-structured model as PAMA-H, which has the following marginal likelihood of $(\phi,\psi)$ given $\mathcal{I}$:

$$L(\phi,\psi\mid\mathcal{I})=\int P(\boldsymbol{\tau}\mid\mathcal{I},\phi,\boldsymbol{\gamma})dF_{\psi}(\boldsymbol{\gamma})=\prod_{k=1}^{m}\int P(\tau_{k}\mid\mathcal{I},\phi,\gamma_{k})dF_{\psi}(\gamma_{k})=\prod_{k=1}^{m}L_{k}(\phi,\psi\mid\mathcal{I}).$$

We show in Theorem 3 that the MLE based on the above marginal likelihood is consistent.

Under the PAMA model, the MLE of ${\boldsymbol{\theta}}=(\mathcal{I},\phi,\boldsymbol{\gamma})$ is $\hat{{\boldsymbol{\theta}}}=\arg\max_{{\boldsymbol{\theta}}}l({\boldsymbol{\theta}})$, where

$$l({\boldsymbol{\theta}})=\log P(\tau_{1},\tau_{2},\cdots,\tau_{m}\mid{\boldsymbol{\theta}})$$

(25)

is the logarithm of the likelihood function (19). Here, we adopt the Gauss-Seidel iterative method in Yang, (2018), also known as backfitting or cyclic coordinate ascent, to implement the optimization. Starting from an initial point ${\boldsymbol{\theta}}^{(0)}$, the Gauss-Seidel method iteratively updates one coordinate of ${\boldsymbol{\theta}}$ at each step with the other coordinates held fixed at their current values. A Newton-like method is adopted to update $\phi$ and $\gamma_{k}$. Since $\mathcal{I}$ is a discrete vector, we find favorable values of $\mathcal{I}$ by swapping two neighboring entities to check whether $g(\mathcal{I}\mid\boldsymbol{\gamma}^{(s+1)},\phi^{(s+1)})$ increases. More details of the algorithm are provided in Supplementary Material.

With the MLE $\hat{\boldsymbol{\theta}}=(\hat{\mathcal{I}},\hat{\phi},\hat{\boldsymbol{\gamma}})$, we define $U_{R}(\hat{\mathcal{I}})=\{i\in U:\ \hat{\mathcal{I}}_{i}>0\}$ and $U_{B}(\hat{\mathcal{I}})=\{i\in U:\ \hat{\mathcal{I}}_{i}=0\}$, and generate the final aggregated ranking list $\hat{\tau}$ based on the rules below: (a) set the top-$n_{1}$ list of $\hat{\tau}$ as $\hat{\tau}_{n_{1}}=sort(i\in U_{R}(\hat{\mathcal{I}})\ by\ \hat{\mathcal{I}}_{i}\uparrow)$, (b) all entities in $U_{B}(\hat{\mathcal{I}})$ tie for positions behind. Hereinafter, we refer to this MLE-based rank aggregation procedure under PAMA model as PAMA_F.

For the PAMA-H model, a similar procedure can be applied to find the MLE of ${\boldsymbol{\theta}}=(\mathcal{I},\phi,\psi)$, with the $\boldsymbol{\gamma}=(\gamma_{1},\cdots,\gamma_{m})$ being treated as the missing data. With the MLE $\hat{\boldsymbol{\theta}}=(\hat{\mathcal{I}},\hat{\phi},\hat{\psi})$, we can generate the final aggregated ranking list $\hat{\tau}$ based on $\hat{\mathcal{I}}$ in the same way as in PAMA, and evaluate the quality of ranker $\tau_{k}$ via the mean or mode of the conditional distribution below:

$$f(\gamma_{k}\mid\tau_{k};\hat{\mathcal{I}},\hat{\phi},\hat{\psi})\propto f(\gamma_{k}\mid\hat{\psi})\cdot P(\tau_{k}\mid\hat{\mathcal{I}},\hat{\phi},\gamma_{k}).$$

In this paper, we refer to the above MLE-based rank aggregation procedure under PAMA-H model as PAMA_HF. The procedure is detailed in Supplementary Material.