1 Introduction↩︎

Ranking a set of alternatives and aggregating multiple rankings into a single consensus ranking are fundamental tasks in social choice, information retrieval, meta-search, recommendation, and many other applications [1], [2]. Throughout the paper, a ranking of a finite set \(E\) is a total order on \(E\), which we identify with a bijection \(\pi:[n]\to E\) where \([n]=\{1,\dots,n\}\), \(n=|E|\), and \(\pi(i)\) is the element placed at position \(i\).

To compare rankings, we use the Kendall tau distance (a.k.a. bubble-sort distance). For two rankings \(\pi\) and \(\sigma\), their Kendall tau distance, denoted by \(d_{\mathrm{KT}}(\pi,\sigma)\), is the number of unordered pairs of elements on which \(\pi\) and \(\sigma\) disagree. This is one of the most standard distances in rank aggregation and voting theory. In the unconstrained setting, minimizing the sum of Kendall tau distances to the input rankings yields the classical Kemeny rule [3]–[5]. The Kemeny aggregation rule has strong axiomatic justification, but its computational side is difficult: computing an optimal Kemeny ranking is NP-hard [6], [7]. On the positive side, constant-factor approximations and even a PTAS are known [8], [9].

In this paper, we study constrained versions of ranking and rank aggregation problems. One natural source of constraints is fairness. Recent work on fair ranking has imposed group-fair representation requirements on top positions of a ranking. For instance, Celis–Straszak–Vishnoi [10] studied top-position fairness under metrics other than Kendall tau. In the Kendall tau setting, the closest fair ranking (CFR) problem and the fair rank aggregation (FRA) problem have been studied under proportionate fairness notions [11], [12]. In the model of Chakraborty–Das–Khan–Subramanian [11], the candidate set is partitioned into groups, and \(k\)-fairness requires the top-\(k\) prefix to satisfy lower and upper bounds on the number of candidates from each group. The stronger notion of block-fairness imposes analogous constraints on multiple prescribed prefixes. Under these notions, CFR admits exact polynomial-time algorithms, whereas FRA has mainly been studied via approximation algorithms [11]–[13].

Our starting point is the observation that the fairness constraints studied in CFR and FRA have a matroidal structure. The \(k\)-fairness constraint can be expressed as the requirement that the top-\(k\) set forms a base of an appropriate matroid, while the stronger block-fairness constraint naturally gives rise to a flag matroid, i.e., a sequence of matroids linked by quotient relations [14]–[17]. For matroids \(M\) and \(N\) on the same ground set, \(N\) is a quotient of \(M\) if their rank functions satisfy \(\mathrm{rk}_N(Y)-\mathrm{rk}_N(X)\leq \mathrm{rk}_M(Y)-\mathrm{rk}_M(X)\) for any \(X\subseteq Y\subseteq E\).

Our contributions↩︎

We study matroidal generalizations of closest fair ranking (CFR) and fair rank aggregation (FRA). In Matroid-CFR, given a ranking \(\pi\) and a matroid \(M\) of rank \(k\) on \(E\), the task is to find a ranking \(\sigma\) minimizing \(d_{\mathrm{KT}}(\sigma, \pi)\) subject to the top \(k\) elements of \(\sigma\) forming a base of \(M\). In Flag-Matroid-CFR, the constraint is given by a flag matroid \(\boldsymbol{M}=(M_1,M_2,\dots,M_s)\) with rank \(k_1<k_2<\cdots<k_s\): for each \(i\in[s]\), the top \(k_i\) elements of the output \(\sigma\) must form a base of \(M_i\). The corresponding aggregation problems are Matroid-FRA and Flag-Matroid-FRA, where multiple rankings \(\pi_1, \pi_2,\dots, \pi_m\) are given and the objective is \(\sum_{i=1}^m d_{\mathrm{KT}}(\sigma,\pi_i)\).

Exact closest ranking under flag matroid constraints.

Our main contribution is an exact polynomial-time algorithm for Flag-Matroid-CFR.

Matroid-CFR, i.e., a special case with a single matroid, serves as a warm-up. Once the top-\(k\) set is fixed, the optimal relative order of the chosen elements and of the remaining elements is inherited from the input ranking \(\pi\), and the objective reduces to a linear weight sum over the chosen base. Thus Matroid-CFR reduces to a minimum-weight base problem (Theorem 4).

The main difficulty lies in the genuine flag matroid case, where several prefix constraints must be satisfied simultaneously. Even after fixing the feasible prefixes, the objective does not decompose into independent layer-wise terms, because \(d_{\mathrm{KT}}(\cdot,\pi)\) depends on pairwise relative positions, including pairs crossing different layers. A natural integer-programming formulation therefore leads to a quadratic objective, and we are not aware of a direct reduction to a known polynomial-time solvable combinatorial optimization problem.

Our algorithm is nonetheless a simple greedy-type algorithm. The nontrivial part is proving that its output is indeed optimal. After relabeling the candidates so that \(\pi=\mathrm{id}\), minimizing \(d_{\mathrm{KT}}(\sigma,\pi)\) is equivalent to minimizing the inversion number \(\mathrm{inv}(\sigma)\). We then compare feasible rankings via the Bruhat order on the symmetric group and prove, using the tableau criterion of Björner–Brenti [18], that the greedy output is the Bruhat-minimum among all feasible rankings. This establishes the correctness of our greedy-type algorithm for Flag-Matroid-CFR (Corollary 1).

Once the closest-ranking problem becomes tractable, existing approximation frameworks for fair rank aggregation by Chakraborty–Das–Dey–Yan [13] extend to the matroidal setting because these algorithms use CFR-type procedures as subroutines. With appropriate generalizations of these procedures, we obtain a \((2+\varepsilon)\)-approximation algorithm for Matroid-FRA for every constant \(\varepsilon>0\) and a \(2.881\)-approximation algorithm for Flag-Matroid-FRA.

Natural classes of relevant flag matroids.

To demonstrate the scope of the framework, Section 3.3 presents explicit classes of matroids and flag matroids that can arise naturally in ranking and aggregation settings. While many examples of flag matroids in the literature come from algebraic or geometric constructions [14]–[16] or special combinatorial families such as lattice paths [19], our examples arise from familiar combinatorial constraint structures. Starting from a partition, a bipartite eligibility graph, or a laminar family, we show that two compatible parameter choices yield matroids in a quotient relation, and hence a flag matroid. These classes model, for instance, assignment-type feasibility constraints in reserve-based market design [20] and hierarchical group quotas in fairness-motivated selection and ranking settings [21], [22], beyond the original partition-based constraints.

Hardness of aggregation for a fixed number of voters.

We also study matroid-constrained rank aggregation when the number \(m\) of voters is fixed. For the unconstrained Kemeny problem, the complexity with constant number of voters has been well studied, where polynomial-time solvability is known for \(m\le 2\) (as folklore), whereas NP-hardness is known for every even \(m\ge 4\) [1] and every odd \(m\ge 7\) [23]; the cases \(m=3\) and \(m=5\) remain open [23], [24]. In contrast, we prove that Matroid-FRA is NP-hard for every fixed number of voters \(m\ge 2\), already under partition matroid constraints. Thus the constrained setting exhibits a sharp dichotomy: the case \(m=1\) is tractable, since it coincides with Matroid-CFR, whereas every fixed case \(m\ge 2\) is NP-hard.

Further related work↩︎

Classical rank aggregation under Kendall tau distance has been studied extensively from the viewpoints of social choice, approximation algorithms, and parameterized complexity; see, e.g., [2]–[5], [8], [23]–[26]. On the fairness side, recent work has considered both post-processing methods for fair rankings and aggregation under group-based quota constraints [10]–[13], [27]. Our work extends this line by replacing quota systems with general matroid and flag matroid feasibility constraints.

Matroids and matroid quotients are classical objects in matroid theory [28], [29]. Flag matroids are matroidal analogues of flags and form a special class of Coxeter matroids [14]–[16]. Recent work studies quotients in the broader framework of M-convex sets [17]. Our analysis of Flag-Matroid-CFR uses the Bruhat order on the symmetric group; for background, we refer to [18], [30].

The rest of the paper is organized as follows. We begin with preliminaries on rankings and Kendall tau distance in Section 2, and on matroids and flag matroids in Section 3. We then study the closest ranking problems in Section 4. After that, we present approximation consequences for the aggregation problems in Section 5 and prove hardness results for a fixed number of voters in Section 6. Proofs of statements marked with \((\star)\) are postponed to the appendices.

2 Fair Ranking Problems↩︎

Let \(E\) be a finite ground set with \(|E|=n\), whose elements we regard as candidates to be ranked. We use the notation \([k]=\{1,2,\dots, k\}\) for any positive integer \(k\).

A ranking of \(E\) is a bijection \(\pi:[n]\to E\), where \(\pi(i)\) denotes the \(i\)th ranked element. We also identify \(\pi\) with the list \((\pi(1),\pi(2),\dots,\pi(n))\) in which elements are arranged from best to worst. For \(e,f\in E\), we write \(e\prec_\pi f\) if \(\pi^{-1}(e)<\pi^{-1}(f)\) and write \(e\preceq_\pi f\) if \(e\prec_\pi f\) or \(e=f\). The notations \(e\succ_\pi f\) and \(e\succeq_\pi f\) are defined similarly.

For rankings \(\pi,\sigma:[n]\to E\), the Kendall tau distance between \(\pi\) and \(\sigma\) is defined by \[d_{\mathrm{KT}}(\pi,\sigma) = \left| \left\{ (e,f)\in E\times E \;\middle|\; e \prec_{\pi} f \text{ and } e \succ_{\sigma} f \right\} \right|.\] Equivalently, \(d_{\mathrm{KT}}(\pi,\sigma)\) counts the number of unordered pairs of elements on which \(\pi\) and \(\sigma\) disagree. It is well known that \(d_{\mathrm{KT}}\) is a metric on the set of rankings [1].

We now recall the fairness notions introduced in [11]. These notions aim to protect minorities while preventing any group from dominating the top positions. For a ranking \(\pi:[n]\to E\) and an integer \(k\in[n]\), let \(\mathsf{Top}_k(\pi)\mathrel{\vcenter{:}}= \{\pi(1),\pi(2),\dots,\pi(k)\}\) denote the set of top-\(k\) candidates in \(\pi\).

This notion imposes the constraint only at a single prefix length, namely \(k\). The next notion strengthens this requirement by imposing analogous constraints on multiple prefixes.

The Closest Fair Ranking (CFR) problem, investigated in [11], asks, given a ranking \(\pi\) on \(E=\bigsqcup_{i=1}^g G_i\), vectors \(\boldsymbol{\alpha},\boldsymbol{\beta}\in [0,1]^g\), and an integer \(k\), to find a \(k\)-fair ranking \(\sigma\) minimizing the Kendall tau distance \(d_{\mathrm{KT}}(\sigma,\pi)\).

The Fair Rank Aggregation (FRA) problem, investigated in [11], [13], asks, given \(m\) rankings \(\pi_1, \dots, \pi_m\) on \(E=\bigsqcup_{i=1}^g G_i\), vectors \(\boldsymbol{\alpha},\boldsymbol{\beta}\in [0,1]^g\), and an integer \(k\), to find a \(k\)-fair ranking \(\sigma\) minimizing \(\sum_{j=1}^m d_{\mathrm{KT}}(\sigma,\pi_j)\).

The block-fairness versions of these problems can also be defined. Efficient algorithms for CFR were given for the \(k\)-fair and block-\(k\)-fair versions [11]. In contrast, FRA is a generalization of the NP-hard Kemeny consensus problem, and previous work has focused on approximation [11], [13].

3 Matroids and Flag Matroids↩︎

We briefly recall standard facts on matroids and then introduce some basics of flag matroids; see, e.g., [28], [29] for more details on matroids and [14]–[16] for details on flag matroids. We also provide examples of flag matroids that arise from combinatorial structures.

3.1 Matroids↩︎

A matroid is a pair \(M=(E,\mathcal{I})\) consisting of a finite set \(E\) and a family \(\mathcal{I}\subseteq 2^E\) satisfying the following three axioms: (I1) \(\emptyset\in \mathcal{I}\), (I2) If \(I\subseteq J\in \mathcal{I}\), then \(I\in \mathcal{I}\), and (I3) If \(I,J\in \mathcal{I}\) and \(|I|<|J|\), then there exists \(e\in J\setminus I\) such that \(I\cup\{e\}\in \mathcal{I}\).

The set \(E\) is called the ground set, and \(\mathcal{I}\) the independent set family of \(M\). The base family \(\mathcal{B}\) of \(M\) consists of the inclusion-wise maximal members of \(\mathcal{I}\). By (I3), all members of \(\mathcal{B}\) have the same cardinality, say \(k\); this number is called the rank of \(M\).

A matroid can be specified by its base family, i.e., when \(\mathcal{B}\) is the base family of a matroid, the independent set family is given as \(\mathcal{I}=\set{I\subseteq E |\exists B\in \mathcal{B}: I\subseteq B}\).

In this paper, we mainly use the base-family viewpoint; we suppose that a matroid is represented in the form \(M=(E, \mathcal{B})\) using the base family. For algorithmic purposes, however, we assume access to an independence oracle, following the usual convention.

The rank function \(\mathrm{rk}_M:2^E\to \mathbb{Z}_+\) of a matroid \(M=(E, \mathcal{B})\) is given by \[\mathrm{rk}_M(S)=\max\{\,|S\cap B|\mid B\in \mathcal{B}\,\}\quad (S\subseteq E).\] It is also written with the independent set family \(\mathcal{I}\) as \(\mathrm{rk}_M(S)=\max\{\,|I|\mid I\in \mathcal{I}, I\subseteq S\,\}\).

Below, we fix a finite set \(E\) and write \(n=|E|\). For any ranking \(\pi:[n]\to E\) and any integer \(k\in [n]\), the Gale order on \(\binom{E}{k}\) induced by \(\pi\) is the partial order \(\preceq_\pi^{\mathrm G}\) on \(\binom{E}{k}\) defined as follows. For \(A,B\in \binom{E}{k}\), write \[\begin{align} A&=\{a_1,a_2,\dots,a_k\}, \quad a_1\prec_\pi a_2\prec_\pi \cdots \prec_\pi a_k,\\ B&=\{b_1,b_2,\dots,b_k\}, \quad b_1\prec_\pi b_2\prec_\pi \cdots \prec_\pi b_k, \end{align}\] and define \(\preceq_\pi^{\mathrm G}\) by \[A\preceq_\pi^{\mathrm G} B \quad\Longleftrightarrow\quad a_i\preceq_\pi b_i\;(i=1,2,\dots, k).\] One reformulation of Gale’s theorem [31] states that a family \(\mathcal{B}\subseteq \binom{E}{k}\) is the base family of a matroid on \(E\) if and only if, for every ranking \(\pi\) over \(E\), the family \(\mathcal{B}\) has a unique \(\preceq_\pi^{\mathrm G}\)-minimum member.

The unique \(\preceq_\pi^{\mathrm G}\)-minimum base is known to be computable by the greedy algorithm. For a matroid \(M=(E,\mathcal{B})\) and a ranking \(\pi\), the greedy algorithm on \(M\) with respect to \(\pi\) works as follows: start with \(X=\emptyset\), and for each \(i=1,2,\dots,n\), if \(X\cup\{\pi(i)\}\in \mathcal{I}\), then update \(X\gets X\cup\{\pi(i)\}\). The output is the final set \(X\). Clearly, this algorithm requires \(O(n)\) oracle calls. The algorithm is also known to compute a minimum-weight base. We summarize these well-known facts in the following proposition; see [29] and also [31], [32].

3.2 Flag Matroids↩︎

As in the previous subsection, \(E\) is a finite set with \(|E|=n\). Let \(\boldsymbol{k}=(k_1,\dots,k_s)\) be a strictly increasing sequence of integers with \(0\le k_1<\cdots<k_s\le n\). A flag of rank \(\boldsymbol{k}\) on \(E\) is a chain \[F_1\subsetneq F_2\subsetneq \cdots \subsetneq F_s \subseteq E \qquad\text{with}\qquad |F_i|=k_i \;\;(i=1,2,\dots,s).\] We write \(\mathcal{F}^{\boldsymbol{k}}_{E}\) for the set of all such flags.

A flag matroid of rank \(\boldsymbol{k}\) on \(E\) is a sequence \(\boldsymbol{M}=(M_1,\dots,M_s)\) of matroids on the same ground set \(E\) such that \(M_i\) has rank \(k_i\) for each \(i\in[s]\) and \(M_i\) is a quotient of \(M_{i+1}\) for each \(i\in[s-1]\). For matroids \(M\) and \(N\) on the same ground set, \(N\) is a quotient of \(M\) if \[\mathrm{rk}_N(Y)-\mathrm{rk}_N(X)\leq \mathrm{rk}_M(Y)-\mathrm{rk}_M(X)\quad \text{for all X\subseteq Y\subseteq E}.\] Various equivalent definitions of matroid quotient in terms of bases, circuits, and flats are known; see, e.g., [17], [33], and [15]. If \(\mathcal{B}_i\) denotes the base family of \(M_i\), then the associated family of flag bases is \[\mathcal{F}(\boldsymbol{M}) = \set{(B_1,\dots,B_s)| B_i\in \mathcal{B}_i \;(i=1,2,\dots,s),\;B_1\subsetneq B_2\subsetneq \cdots \subsetneq B_s}.\]

As with ordinary matroids, flag matroids admit a characterization via Gale order. To state it, we extend the Gale order from \(\binom{E}{k}\) to \(\mathcal{F}^{\boldsymbol{k}}_{E}\). For a ranking \(\pi\) over \(E\) and any two flags \(\boldsymbol{F}=(F_1,\dots,F_s), \boldsymbol{G}=(G_1,\dots,G_s)\in \mathcal{F}^{\boldsymbol{k}}_{E}\), we define \(\preceq_\pi^{\mathrm G}\) by \[\boldsymbol{F}\preceq_{\pi}^{\mathrm G} \boldsymbol{G} \quad\Longleftrightarrow\quad F_h\preceq_{\pi}^{\mathrm G} G_h \;\;(h=1,2,\dots,s).\]

Similarly to the case of matroids, a flag matroid is characterized by the existence of a minimum flag base with respect to Gale order [34]; a nonempty family \(\mathcal{F}\subseteq \mathcal{F}^{\boldsymbol{k}}_{E}\) is the family of flag bases of a flag matroid on \(E\) if and only if, for every ranking \(\pi\) over \(E\), the family \(\mathcal{F}\) has a unique \(\preceq_{\pi}^{\mathrm G}\)-minimum member.

For algorithmic purposes, we provide here a constructive proof of the “only if” direction.

3.3 Examples of Matroids and Flag Matroids↩︎

We present three classes of matroids relevant to constrained ranking and aggregation and identify sufficient conditions under which members of the same class are in a quotient relation.

The first example directly captures \(k\)-fairness; see [35] and [36].

A usual partition matroid is the case \(\ell_i=0~(i\in[g])\) and \(k=\sum_{i\in[g]} u_i\).

The \(k\)-fairness condition in Section 2 is captured by a generalized partition matroid: if we set \(\ell^*_i=\lfloor \alpha_i k \rfloor\) and \(u^*_i=\lceil \beta_i k \rceil\) for each \(i\in[g]\), then a ranking \(\pi\) over \(E\) is \((\boldsymbol{\alpha},\boldsymbol{\beta})\)-\(k\)-fair if and only if \(\mathsf{Top}_k(\pi)\in \mathcal{B}_{k,\boldsymbol{\ell}^*, \boldsymbol{u}^*}\), provided that this family is nonempty.

The next proposition gives a sufficient condition for quotient relations between generalized partition matroids, and hence for obtaining flag matroids. The proof is in Appendix 9.

Consequently, any sequence \(M_1,\dots,M_s\) such that each pair \((M_j,M_{j+1})\) satisfies Proposition [prop:quotient-partition] forms a flag matroid. In particular, block-\(k\)-fairness is a special case; as we formally prove in the appendix as Corollary 2, if we define a flag matroid \(\boldsymbol{M}=(M_1, \dots, M_s)\) and its rank \((h_1, \dots, h_s)\) appropriately, we have that a ranking \(\pi\) is \((\boldsymbol{\alpha},\boldsymbol{\beta})\)-block-\(k\)-fair if and only if \((\mathsf{Top}_{h_1}(\pi), \dots, \mathsf{Top}_{h_s}(\pi))\in \mathcal{F}(\boldsymbol{M})\).

We next give two more general examples.

One is a generalized transversal matroid, which is the size-\(k\) truncation of the generalized matroid in [37]. It models assignment-type feasibility constraints. For example, the top-\(k\) prefix of a consensus ranking may have to be assignable to eligible departments, tracks, or reserved positions under capacity or reserve requirements. A related reserve-graph formulation uses transversal matroids to encode eligibility for reserved positions [20]; our generalized version further allows lower and upper quotas for each position type.

When \(p_d=0\) and \(q_d=1\) for all \(d\in D\), this reduces to the size-\(k\) truncation of the usual transversal matroid.

We give a sufficient condition for two generalized transversal matroids defined from the same bipartite structure to have a quotient relation.

We postpone the proof of Proposition [prop:quotient-transversal] to Appendix 9 and describe only its main ingredient here. The proof is based on induction by a bipartite graph, an operation that constructs a new matroid from a given one. Brandenburg–Loho–Smith [17] showed that induction preserves quotient relations. Proposition [prop:quotient-transversal] then follows by applying Proposition [prop:quotient-partition] to suitable generalized partition matroids and then using induction.

A second example is what we call a generalized laminar matroid. It is the fixed-cardinality restriction of the laminar lower/upper-quota family, which is a generalized matroid [37]. Unlike the partition-based constraints, these constraints allow nested groups, so one can impose quotas simultaneously on broad groups and their subgroups. Similar hierarchical constraints have appeared in fairness-motivated committee selection and ranking. Bredereck et al. [21] study committee selection with label-wise cardinality constraints and explicitly discuss laminar label structures such as countries and continents; Gorantla et al. [22] consider laminar protected groups in fair ranking.

When \(g(L)=0\) for all \(L\in \mathcal{L}\), this reduces to a size-\(k\) truncation of the usual laminar matroid.

We give a sufficient condition for two generalized laminar matroids defined on the same laminar family to have a quotient relation.

We remark that, in contrast to the partition case, the condition in Proposition [prop:quotient-laminar] cannot in general be weakened to inequalities analogous to those in Proposition [prop:quotient-partition].

Other sources of flag matroids are also available. For partition matroids, i.e., partition constraints without lower quotas, the weaker condition \(u_i\leq u'_i~(i\in [g])\) suffices. Similar relaxations are possible in the transversal and laminar settings when lower quotas are absent. Another source comes from matroid union: if \(N_1, N_2, \dots, N_s\) are matroids on the same ground set and \(M_i\) is the matroid union of \(N_1, \dots, N_i\) for each \(i=1,\dots,s\), then \((M_1, M_2,\dots, M_s)\) forms a flag matroid (after removing repetitions of the same matroid if any).

4 Closest Ranking with Flag Matroid Constraints↩︎

We propose the following two problems as generalizations of Closest Fair Ranking (CFR) studied in [11], [13] and reviewed in Section 2. The first generalizes CFR with \(k\)-fairness.

The second problem below generalizes CFR with block-\(k\)-fairness.

Note that Matroid-CFR is a special case of Flag-Matroid-CFR with \(s=1\). However, we will treat this special case separately, since it is much easier than the case \(s\geq 2\).

We first provide a basic observation that can be used in both problems. Given an instance of Flag-Matroid-CFR as above, any ranking \(\sigma\) satisfying \(\mathsf{Top}_{k_i}(\sigma)\in \mathcal{B}_i~(i\in[s])\) is determined by the following two pieces of data: (1) a choice of a flag base \((B_1, B_2,\dots, B_s)\in \mathcal{F}(\boldsymbol{M})\) such that \(B_i=\mathsf{Top}_{k_i}(\sigma)~(i\in[s])\), and (2) an ordering of each of the parts \(B_i \setminus B_{i-1}\) for \(i\in[s+1]\), where for convenience we set \(B_0=\emptyset\) and \(B_{s+1}=E\).

For any flag base \(\boldsymbol{B}=(B_1, B_2, \dots, B_s)\) of \(\boldsymbol{M}\), which forms a chain by definition, we define a ranking \(\pi_{\boldsymbol{B}}\) on \(E\) as follows: the elements are ordered by concatenating \(B_1\), \(B_2 \setminus B_1\), \(B_3 \setminus B_2\), \(\dots\), \(B_s \setminus B_{s-1}\), and \(E \setminus B_s\); within each part, the elements are ordered according to the input ranking \(\pi\). See Figure 1.

We postpone the proof to Appendix 10 but it is summarized as follows. The constraints \(\mathsf{Top}_{k_i}(\sigma)=B_i~(i\in[s])\) fix the order of the blocks \(B_1\), \(B_2 \setminus B_1\), \(B_3 \setminus B_2\), \(\dots\), \(B_s \setminus B_{s-1}\), and \(E \setminus B_s\) in \(\sigma\). Hence, among the pairs counted in \(d_{\mathrm{KT}}(\sigma,\pi)\), those from different blocks contribute a constant independent of the internal ordering of each block. Therefore, it suffices to minimize the contribution of pairs within each block, which is achieved by ordering the elements of every block according to \(\pi\).

Therefore, once a flag base \(\boldsymbol{B}=(B_1,\dots,B_s)\in \mathcal{F}(\boldsymbol{M})\) is fixed, the ranking \(\sigma\) minimizing \(d_{\mathrm{KT}}(\sigma,\pi)\) is uniquely determined as \(\pi_{\boldsymbol{B}}\). Hence, Flag-Matroid-CFR reduces to the problem of finding a flag base \(\boldsymbol{B}\in \mathcal{F}(\boldsymbol{M})\) that minimizes \(d_{\mathrm{KT}}(\pi_{\boldsymbol{B}},\pi)\).

Single Matroid Case↩︎

We first apply Observation [obs:fixedbase] to the case \(s=1\), i.e., Matroid-CFR. For this special case, the objective function can be written explicitly.

The proof is given in Appendix 10, but the idea is simple. Starting from \(\pi\), consider obtaining \(\pi_B\) by moving the elements of \(B\) to the top \(k\) positions while preserving their relative order in \(\pi\). If \(e\in B\) is the \(h\)th highest element of \(B\) in \(\pi\), then it moves left by exactly \(\pi^{-1}(e)-h\) positions, creating one inversion at each step. Summing over all \(e\in B\) gives the formula.

Since \(-\frac{k(k+1)}{2}\) is a constant independent of the choice of \(B\), Lemma [lem:MatroidCFR] shows that Matroid-CFR reduces to the minimum-weight base problem with weights \(w(e)=\pi^{-1}(e)\). Then Proposition 1 immediately implies the following.

Difficulty with Multiple Matroids↩︎

By Proposition 2, for a flag matroid \(\boldsymbol{M}=(M_1, M_2,\dots, M_s)\), the unique \(\preceq_\pi^{\mathrm G}\)-minimum bases \(B_{i}^*\) of the matroids \(M_i\) form a chain \(B_1^*\subsetneq B_2^*\subsetneq \cdots \subsetneq B_s^*\), and hence give a flag base \(\boldsymbol{B}^*=(B^*_1,\dots, B^*_s)\). As a generalization of Theorem 4, we expect that \(\pi_{\boldsymbol{B}^*}\) gives the unique optimal solution to Flag-Matroid-CFR. This is indeed true, as we will show. However, the single-matroid proof does not extend directly.

We demonstrate that analyzing Flag-Matroid-CFR is not straightforward when \(s\geq 2\). Take any flag base \(\boldsymbol{B}=(B_1, B_2, \dots, B_s)\) and consider the corresponding ranking \(\pi_{\boldsymbol{B}}\), which arranges the blocks \(B_1, B_2\setminus B_1, \dots, B_s\setminus B_{s-1}\) and \(E\setminus B_s\) in this order, where within each block the elements are arranged in the order of \(\pi\). Let us write \(d_{\mathrm{KT}}(\pi_{\boldsymbol{B}}, \pi)\) in a way mimicking Lemma [lem:MatroidCFR]. One possible expression is then \[d_{\mathrm{KT}}(\pi_{\boldsymbol{B}}, \pi)=\sum_{e\in B_1}\pi^{-1}(e)~+\!\!\!\sum_{e\in B_2\setminus B_1}(\pi|_{E\setminus B_1})^{-1}(e)~+~\cdots ~+\!\!\!\sum_{e\in B_s\setminus B_{s-1}}(\pi|_{E\setminus B_{s-1}})^{-1}(e)~+ \text{constant}\] where the notation \((\pi|_X)^{-1}(e)\) represents the rank of \(e\) among \(X\subseteq E\). Here, the first term is simply the weight of \(B_1\) with respect to the weights \(w(e)=\pi^{-1}(e)\), but the weights for the \(i\)th term \((i\geq 2)\) are affected by the choice of \(B_{i-1}\). It is then possible that taking a non-optimal earlier base reduces the latter terms; for example, consider an instance where \(s=2\), \(\pi\) is the identity on \(E=\{1,2,3\}\), and \(\mathcal{B}_1=\{\{1\}, \{3\}\}\) and \(\mathcal{B}_2=\{\{1,3\}\}\). Then \(B_2\) must be \(\{1,3\}\). Choosing \(B_1=\{1\}\) minimizes the first term but then the second term is \(2\) as \((\pi|_{\{2,3\}})^{-1}(3)=2\), whereas choosing \(B_1=\{3\}\) makes the second term smaller (i.e., \(1\)) since \((\pi|_{\{1,2\}})^{-1}(1)=1\). Thus, we cannot divide the objective value into \(s\) separate linear optimization problems, and the optimality of each \(B_i\) with respect to weights \(\pi^{-1}\) does not simply imply the optimality of the whole objective value.

Indeed, if we represent the objective function using binary variables \(x_{ei}\) such that \(x_{ei}=1\Leftrightarrow e\in B_i\setminus B_{i-1}\) for each \(e\in E\) and \(i\in[s+1]\) (with \(B_0=\emptyset\) and \(B_{s+1}=E\)), then this natural formulation yields a quadratic objective function. For a pair of elements \(e,f\) with \(e\prec_\pi f\), its contribution to the objective function can be written as \(\sum_{i,j\in [s+1]: i<j} x_{fi}x_{ej}\). Summing over all pairs \(e\prec_\pi f\), we obtain a quadratic objective function.

Another possible strategy for proving the optimality of \(\pi_{\boldsymbol{B}^*}\) is to suppose, for contradiction, that an optimal solution \(\pi_{\boldsymbol{B}'}\) differs from \(\pi_{\boldsymbol{B}^*}\), and then use the matroid exchange property to modify \(\pi_{\boldsymbol{B}'}\) so as to obtain a solution with a strictly better objective value.³ However, the usual matroid exchange argument does not seem to extend directly, because to modify a flag base while preserving feasibility, we have to guarantee exchangeability with respect to all bases related to the exchanged elements, and such a property does not simply hold for a general flag base. Indeed, [14] shows that flag matroids do not satisfy the strong exchange property in general.

Analysis via Bruhat Order↩︎

As explained above, except in the case \(s=1\), it seems difficult to reduce Flag-Matroid-CFR to a known combinatorial optimization problem. Here, using the notion of the Bruhat order from the theory of Coxeter groups (in particular, the symmetric group), we show that we can establish the optimality of the greedy solution in a simple way.

Let us identify \(E\) as the set \([n]=\{1,2,\dots, n\}\). Then, the set of all rankings is nothing but the set \(S_n\) of permutations on \([n]\), i.e., the symmetric group. Assume without loss of generality that the input ranking \(\pi\) is the identity permutation \(\mathrm{id}\), i.e., \(\pi(i)=\mathrm{id}(i)=i\) for every \(i\in[n]\). For any permutation (ranking) \(\sigma\in S_n\), the Kendall tau distance \(d_{\mathrm{KT}}(\sigma, \mathrm{id})\) coincides with the inversion number of \(\sigma\), which is defined as \[\mathrm{inv}(\sigma)=|\set{(i,j)\in [n]\times[n]| i<j,~\sigma(i)>\sigma(j)}|.\] Thus, Flag-Matroid-CFR can be seen as the problem of finding \(\sigma\in S_n\) minimizing \(\mathrm{inv}(\sigma)\) subject to \((\mathsf{Top}_{k_1}(\sigma), \dots, \mathsf{Top}_{k_s}(\sigma))\in \mathcal{F}(\boldsymbol{M})\).

We recall the Bruhat order (also called the strong Bruhat order) on \(S_n\) following [30]. For the Bruhat order for general Coxeter groups, see [30].

Bruhat order is a partial order (i.e., a reflexive, antisymmetric, and transitive relation) on the elements of a Coxeter group. Here is a definition of Bruhat order specialized to \(S_n\), where we adopt a characterization given in [30] as a definition.

We write \(\sigma<^{\rm B} \tau\) if \(\sigma \leq^{\rm B} \tau\) and \(\sigma\neq \tau\). Observe that, by definition, when \(\sigma \vartriangleleft \tau\), we have \(\mathrm{inv}(\tau)=\mathrm{inv}(\sigma)+1\). More precisely, when \(i,j\) satisfy the stated properties, by swapping the positions of \(i\) and \(j\), the inversion status of pairs not involving \(i\) or \(j\) does not change. Among pairs involving \(i\) or \(j\), the only possible changes besides the pair \((i,j)\) occur for indices \(h\) with \(\sigma(i)<\sigma(h)<\sigma(j)\). However, by assumption there is no such \(h\) with \(i<h<j\); hence every such \(h\) satisfies \(h<i<j\) or \(i<j<h\), and its total contribution with \(i\) and \(j\) to the inversion number remains unchanged after the swap. Therefore, only the pair \((i,j)\) changes, from a noninversion to an inversion. As this observation implies, Bruhat order on \(S_n\) satisfies \[\sigma<^{\rm B} \tau~~~\Longrightarrow~~~ \mathrm{inv}(\sigma)<\mathrm{inv}(\tau).\]

Therefore, if we can compute \(\sigma^*\in S_n\) that is minimum with respect to the Bruhat order among all \(\sigma\in S_n\) satisfying \((\mathsf{Top}_{k_1}(\sigma), \dots, \mathsf{Top}_{k_s}(\sigma))\in \mathcal{F}(\boldsymbol{M})\), then \(\sigma^*\) is the optimal solution to Flag-Matroid-CFR. In fact, we can show this by using the following characterization of Bruhat order by Björner–Brenti [18] (also presented in [30]).

This can be used to identify the optimal solution of Flag-Matroid-CFR. Recall that, for a flag base \(\boldsymbol{B}=(B_1,\dots, B_s)\in \mathcal{F}(\boldsymbol{M})\), the ranking \(\pi_{\boldsymbol{B}}\) is defined by arranging \(B_1\), \(B_2 \setminus B_1\), \(B_3 \setminus B_2\), \(\dots\), \(B_s \setminus B_{s-1}\), and \(E \setminus B_s\) in this order, where the elements in each part are ordered according to \(\pi\).

This implies the tractability of Flag-Matroid-CFR.

We describe the construction of the optimal solution in algorithmic form in Algorithm 2.

For the correctness of the algorithm, a flag matroid structure, i.e., quotient relations between matroids, is critical. In Appendix 8, we demonstrate that if this condition is relaxed, even in a way that the greedy algorithm remains well defined, optimality is no longer guaranteed.

5 Approximation Consequences for Rank Aggregation↩︎

Using the exact algorithms for Matroid-CFR and Flag-Matroid-CFR from Section 4 as subroutines (in a generalized form for the former), we can extend the approximation frameworks in [13] to the following settings while preserving the approximation ratios.

The \((2+\varepsilon)\)-approximation for Matroid-FRA is obtained by replacing the colorful bi-partition subproblem in their framework with a matroidal analogue and then applying the PTAS by Kenyon-Mathieu and Schudy [9] to the two resulting parts. The \(2.881\)-approximation for Flag-Matroid-FRA follows from their generic black-box framework once Flag-Matroid-CFR is polynomial-time solvable. We defer the details to Appendix 11.

6 Hardness of Rank Aggregation with Few Voters↩︎

In the classical Kemeny consensus (i.e., rank aggregation without constraints), the complexity of the problem with a fixed number \(m\) of voters has been investigated, and the cases \(m=3\) and \(m=5\) remain open [1], [23], [24].

In this section, we show that Matroid-FRA with \(m\) voters is NP-hard for any constant \(m\geq 2\). Note that the case \(m=1\) coincides with Matroid-CFR and is thus already solved in Theorem 4. Indeed, to obtain the hardness result for all \(m\geq 2\), it is sufficient to show the hardness for the cases \(m=2\) and \(m=3\), since for any \(m'>3\), the problem with \(m'\) voters can be reduced to the problem with \(m'-2\) voters (see the proof of Corollary [cor:all95m]).

As suggested by the current complexity status of the unconstrained setting, odd numbers of voters are harder to handle. Indeed, proving Theorem [thm:three] requires an involved construction of three input rankings. Both proofs use only simple partition matroids. See Appendix 12 for the proofs and Figures 4 and 5 for illustrations of the reductions.

Acknowledgments↩︎

We thank Yuya Ryuzaki for helpful discussions at an early stage of this work. The second author was supported by JST ERATO Grant Number JPMJER2301, JST CRONOS Grant Number JPMJCS24K2, and JSPS KAKENHI Grant Number JP26K14706.

7 A Note on Exchange-Based Proofs for Block-Fairness↩︎

In [11], the authors give an exact algorithm for Closest Fair Ranking under block-\(k\)-fairness constraints. When specialized to this setting, our algorithm for Flag-Matroid-CFR produces the same ranking as theirs.

They establish optimality by an exchange argument, aiming to show that a ranking different from the algorithm’s output admits a feasible exchange of two elements that improves the objective value. However, to the best of our understanding, the exchange step as stated requires an additional justification: the proposed swap need not preserve all block-prefix constraints simultaneously. We explain the issue in [11], using the notation of the present paper.

The key point is that block-\(k\)-fairness is a simultaneous feasibility condition: By its definition, a block-\(k\)-fair ranking must satisfy the fairness constraint for every block-prefix of length at least \(k\). By contrast, the swap argument proved in their Theorem 3.2 concerns fairness for one fixed prefix length only. Thus, when Theorem 3.2 is invoked inside their Claim 3.8 to conclude that swapping two elements produces another block-\(k\)-fair ranking, this conclusion does not follow from Theorem 3.2 alone.

This issue can already be seen in a small example. Consider the groups \[G_1=\{a_1,a_2\},\qquad G_2=\{b_1,b_2\},\qquad G_3=\{c\}\] with block length \(b=2\) and \(k=2\), and let \[\alpha_1=\alpha_2=\alpha_3=0,\qquad \beta_1=\tfrac12,\qquad \beta_2=\beta_3=1.\] Then block-\(k\)-fairness requires that the top-\(2\) prefix may contain at most one element of \(G_1\), and the top-\(4\) prefix may contain at most two elements of \(G_1\). There are no other constraints, since \(\alpha_1=\alpha_2=\alpha_3=0\) and \(\beta_2=\beta_3=1\) impose nothing.

Now consider the input ranking \[\pi=(a_1,a_2,b_1,b_2,c).\] Then, the output of the algorithm in [11] (which coincides with our algorithm’s output) is \[\sigma=(a_1,b_1,a_2,b_2,c).\] Consider a block-\(k\)-fair ranking \[\pi^*=(a_1,c,b_1,b_2,a_2).\] This satisfies block-\(k\)-fairness and also preserves the intra-group orderings (i.e., the input ordering in each group). Since \(\mathsf{Top}_{4}(\sigma)\neq \mathsf{Top}_{4}(\pi^*)\), following the argument in [11], take the elements \(a_2\in \mathsf{Top}_{4}(\sigma)\setminus \mathsf{Top}_{4}(\pi^*)\) and \(c\in \mathsf{Top}_{4}(\pi^*)\setminus \mathsf{Top}_{4}(\sigma)\). The intended argument is that, by swapping \(a_2\) and \(c\) in \(\pi^*\), one obtains a block-\(k\)-fair ranking \(\pi^{**}\) that is closer to \(\pi\) than \(\pi^*\). As we have \(a_2\prec_{\pi} c\), swapping \(a_2\) and \(c\) indeed reduces the objective value. However, the resulting ranking \[\pi^{**}=(a_1,a_2,b_1,b_2,c)\] contains more than one element of \(G_1\) in its top-\(2\) prefix, violating block-\(k\)-fairness.

Therefore, the step in Claim 3.8 asserting that the exchanged ranking is still block-\(k\)-fair does not seem to follow as stated without an additional argument. The same concern also applies to Claim 3.9. Thus, the exchange-based proof of Theorem 3.4 appears to require an additional justification at this step.

Importantly, Claims 3.8 and 3.9 and Theorem 3.4 themselves are true; our proof based on Bruhat order establishes their correctness.

8 Failure of Greedy Approach without Quotient Relations↩︎

As a generalization of block-\(k\)-fairness, we consider flag matroid constraints on rankings. However, for a sequence of matroids, one can consider weaker conditions, and it is natural to ask to what extent the tractability of Flag-Matroid-CFR extends. We do not know a clear answer, but here we provide some observations.

Suppose that we have a sequence \((M_1, M_2,\dots, M_s)\) of matroids on the same ground set \(E\) with ranks \(k_1<k_2<\cdots <k_s\). Each matroid is given as \(M_i=(E, \mathcal{B}_i)\).

Note that, if we have no additional assumption at all, then even finding a feasible ranking is NP-hard when \(s\geq 3\). This follows easily from the fact that 3-matroid intersection is NP-hard.

We then consider imposing some assumptions on \((M_1,M_2,\dots, M_s)\) to obtain a reasonable class. As gradual restrictions, we can consider the following three settings:

1. The independent set families satisfy \(\mathcal{I}_1\subseteq \mathcal{I}_2\subseteq \cdots\subseteq \mathcal{I}_s\). This is equivalent to the condition that for every \(i\in[s-1]\) and \(B\in\mathcal{B}_i\), there exists \(B'\in \mathcal{B}_{i+1}\) with \(B\subseteq B'\).

2. The above condition holds, and in addition, for every \(i\in[s]\setminus \{1\}\) and \(B\in\mathcal{B}_i\), there exists \(B'\in \mathcal{B}_{i-1}\) with \(B'\subseteq B\).

3. \((M_1,M_2,\dots, M_s)\) forms a flag matroid.

Clearly, 2 implies 1. It is also not hard to see that 3 implies 2; a quotient relation implies \(\mathrm{rk}_{M_{i}}(X)-\mathrm{rk}_{M_{i}}(\emptyset)\leq \mathrm{rk}_{M_{i+1}}(X)-\mathrm{rk}_{M_{i+1}}(\emptyset)\) for every \(X\subseteq E\), which implies \(\mathcal{I}_i\subseteq \mathcal{I}_{i+1}\). In addition, for any \(B\in \mathcal{B}_i\), we have \(\mathrm{rk}_{M_{i-1}}(E)-\mathrm{rk}_{M_{i-1}}(B)\leq \mathrm{rk}_{M_{i}}(E)-\mathrm{rk}_{M_{i}}(B)=0\), which implies \(\mathrm{rk}_{M_{i-1}}(B)=\mathrm{rk}_{M_{i-1}}(E)\) and hence the existence of \(B'\in \mathcal{B}_{i-1}\) with \(B'\subseteq B\).

There are indeed gaps between any two of these three classes. An example satisfying 1 but violating 2 is given by \(\mathcal{B}_1=\{\{1,2\}\}\) and \(\mathcal{B}_2=\{\{1,2,3\}, \{1,2,4\},\{1,3,4\}\}\). An example of a matroid pair satisfying 2 but violating 3 is given in Figure 3.

Given an input ranking \(\pi\), consider the following two greedy algorithms.

1. Let \(B_0=\emptyset\) and for \(i=1,2,\dots, s\), do the following.

   • Let \(X\gets B_{i-1}\).

   • For each \(e\in E\setminus B_{i-1}\), in the ascending order of \(\pi\), if \(X\cup \{e\}\in \mathcal{I}_i\), then \(X\gets X\cup \{e\}\).

   • Set \(B_i\gets X\).

2. Let \(\boldsymbol{B}=(B_1, \dots, B_s)\) and output \(\pi_{\boldsymbol{B}}\) as defined in Section 4.

 

1. Let \(B_{s+1}= E\) and for \(i=s, s-1,\dots, 1\), do the following.

   • Let \(X\gets \emptyset\).

   • For each \(e\in B_{i+1}\), in the ascending order of \(\pi\), if \(X\cup \{e\}\in \mathcal{I}_i\), then \(X\gets X\cup \{e\}\).

   • Set \(B_i\gets X\).

2. Let \(\boldsymbol{B}=(B_1, \dots, B_s)\) and output \(\pi_{\boldsymbol{B}}\) as defined in Section 4.

Then the following hold.

• In setting 3, i.e., when the matroids form a flag matroid, both algorithms output the same ranking, and it is the unique optimal solution to Flag-Matroid-CFR.

• In setting 2, both algorithms always output feasible rankings, but it is possible that neither output is optimal. We demonstrate this below.

• In setting 1, the Forward Greedy Algorithm always outputs a feasible ranking, while the backward one may not.

We provide an example that satisfies the conditions in setting 2 and on which neither of the two greedy algorithms finds an optimal solution.

Consider a pair of matroids \(M_1\) and \(M_2\) on \(E=\{1,2,\dots, 12\}\), which are both partition matroids defined as in Figure 3. The smaller matroid \(M_1\) has rank \(6\) and is defined by the partition drawn in blue. The numbers written in blue show the upper quotas of those classes. The larger matroid \(M_2\) has rank \(8\), and its partition classes are given by the red dashed regions, whose upper quotas are also shown. This pair belongs to setting 2, while it does not fit setting 3, since \(\mathrm{rk}_{M_1}(\{1,2,5\})-\mathrm{rk}_{M_1}(\{1,2\})=1>0=\mathrm{rk}_{M_2}(\{1,2,5\})-\mathrm{rk}_{M_2}(\{1,2\})\).

Suppose that the input ranking \(\pi\) is the identity permutation.

We can observe that the output \(\sigma_{\rm f}\) of the forward greedy algorithm and the output \(\sigma_{\rm b}\) of the backward greedy algorithm are, respectively, \[\begin{align} \sigma_{\rm f}&= (1,4,5,7,9,10,6,12,2,3,8,11),\\ \sigma_{\rm b}&= (1,4,6,7,10,12,2,8,3,5,9,11). \end{align}\] The Kendall tau distances to \(\pi\) are \(d_{\mathrm{KT}}(\sigma_{\rm f},\pi)=21\) and \(d_{\mathrm{KT}}(\sigma_{\rm b},\pi)=21\). However, the feasible ranking \[\sigma^*\mathrel{\vcenter{:}}= (1,4,6,7,9,10,2,12,3,5,8,11)\] has smaller Kendall tau distance \(d_{\mathrm{KT}}(\sigma^*,\pi)=20\).

Thus, neither of the two greedy algorithms finds an optimal solution on this example.

9 Omitted Proofs from Section 3 (Quotient Relations)↩︎

In this section, we provide proofs omitted in Section 3.

9.1 Tools Used in the Proofs↩︎

In the proofs of Propositions [prop:quotient-partition] and [prop:quotient-laminar] (sufficient condition for generalized partition matroids or generalized laminar matroids to have a quotient relation), we use the following characterization of a matroid pair with quotient relation.

In the proof of Proposition [prop:quotient-transversal] (sufficient condition for generalized transversal matroids to have a quotient relation), we use an operation of matroid induction, which is defined as follows. Given a bipartite graph \(G=(U,V; F)\) and a matroid \(M_V=(V, \mathcal{B}_V)\), define \[\mathcal{B}_U\mathrel{\vcenter{:}}= \set{\partial X\cap U \mid X\subseteq F \text{ is a matching and } \partial X\cap V\in \mathcal{B}_V},\] where \(\partial X\subseteq U\cup V\) is the set of vertices covered by \(X\). If this \(\mathcal{B}_U\) is nonempty, then \(M_U=(U, \mathcal{B}_U)\) forms a matroid on \(U\) (see, e.g., [38], [39]). This operation is called an induction by the bipartite graph \(G\); here \(M_U\) is induced from \(M_V\).

It was shown by Brandenburg–Loho–Smith [17] that the induction operation preserves quotient relations. Although the original statement proves a more general result for M-convex sets and linking systems, we state only the special case needed for our present purpose.

9.2 Omitted Proofs↩︎

We provide omitted proofs from Section 3 in order.

10 Omitted Proofs from Section 4 (Matroid-CFR)↩︎

Here we provide a few proofs omitted from Section 4.

11 Omitted Proofs from Section 5 (Approximation for FRA)↩︎

In Section 5, we provide only the statements of our results on approximation algorithms for Matroid-FRA and Flag-Matroid-FRA. Here we provide their details.

11.1 Matroid-FRA Approximation↩︎

This part is devoted to the proof of the following theorem on Matroid-FRA (Matroid Feasible Rank Aggregation). See Section 5 for the definition of the problem.

For FRA with \(k\)-fairness criteria (i.e., a special case of Matroid-FRA with a generalized partition matroid), Chakraborty et al. [13] show that there exists a \((2+\varepsilon)\)-approximation algorithm for any constant \(\varepsilon>0\). Their algorithm consists of the following steps:

1. Find an appropriate bi-partition \(\{B, E\setminus B\}\) such that \(B\) has size \(k\) and satisfies \(k\)-fairness by solving the colorful bi-partition problem (described below in a generalized form).

2. Apply the known PTAS for rank aggregation (without constraints) by Kenyon-Mathieu and Schudy [9] to each of \((\pi_i|_{B})_{i\in [m]}\) and \((\pi_i|_{E\setminus B})_{i\in [m]}\) to obtain \(\sigma_B\) and \(\sigma_{E\setminus B}\).

3. Output a concatenation of \(\sigma_B\) and \(\sigma_{E\setminus B}\) as \(\sigma\).

To generalize their algorithm to Matroid-FRA, we consider solving the following generalized version of the colorful bi-partition subproblem. As in the original version, we describe the instance by a weighted tournament. In this paper, a weighted tournament is a directed graph \(T=(E,A)\) in which, for every pair of distinct vertices \(e,f\in E\), both arcs \((e,f)\) and \((f,e)\) belong to \(A\), together with a weight function \(c:A\to\mathbb{R}\).⁴ A weighted tournament arises from a collection of rankings as follows. Consider a weighted tournament with \(E\) being the set of candidates and, for each \(e,f\in E\), set the weight \(c(e,f)\) to be the fraction of voters preferring \(e\) to \(f\) among all voters. Then we see that the weights satisfy the following properties:

• Probability Constraints: \(c(e,f)+c(f,e)=1\) for any distinct \(e,f\in E\), and

• Triangle Inequality: \(c(e,g)\leq c(e,f)+c(f,g)\) for any distinct \(e,f,g\in E\).

The following problem is a matroidal generalization of the colorful bi-partition problem in [13]. For a weighted tournament \(T=(E,A)\) and any vertex subset \(S\subseteq E\), we define \(\mathrm{cost}(S)=\sum_{(e,s)\in A:\, s\in S,\, e\in E\setminus S}c(e,s)\). Also, for any vertex \(e\in E\), we define \(\delta^{-}(e)=\sum_{f\in E\setminus\{e\}} c(f,e)\).

By this lemma, we see that Matroid Bi-partition reduces to the minimum-weight base problem for matroids, which can be solved by the greedy algorithm with \(O(|E|)\) calls to the independence oracle.

We modify the algorithm by Chakraborty et al. [13] by replacing the subroutine solving colorful bi-partition with the one solving Matroid Bi-partition. Specifically, we construct a ranking \(\sigma^*\) in the following manner:

• Given an instance \(I=(\pi_1,\dots, \pi_m, M=(E,\mathcal{B}))\) of Matroid-FRA, define a weighted tournament \((T=(E, A), c)\) by setting \(c(e,f)=\frac{1}{m}|\set{j\in [m]\mid e\prec_{\pi_j} f}|\).

• Let \(B^*\) be the optimal solution to Matroid Bi-partition for the input \((T, c)\) and \(M\).

• Apply the known PTAS for rank aggregation (without constraints) by Kenyon-Mathieu and Schudy [9] to each of \((\pi_i|_{B^*})_{i\in [m]}\) and \((\pi_i|_{E\setminus B^*})_{i\in [m]}\) to obtain \(\sigma_{B^*}\) and \(\sigma_{E\setminus B^*}\).

• Output a concatenation of \(\sigma_{B^*}\) and \(\sigma_{E\setminus B^*}\) as \(\sigma^*\).

We reproduce the analysis of approximation ratio in [13] for completeness.

11.2 Flag-Matroid-FRA Approximation↩︎

In the previous subsection, we considered a matroidal generalization of FRA with \(k\)-fairness, i.e., only one prefix is required to satisfy the constraint. In this subsection, we consider the flag matroid analogue, which includes FRA with block-\(k\)-fairness as a special case.

We apply the generic framework by Chakraborty et al. [13]. They proved that, if there is an efficient procedure to solve the closest feasible ranking problem with some constraint, then we can obtain an efficient \(2.881\)-approximation algorithm for the rank aggregation problem with the same constraint. Since we have shown that Flag-Matroid-CFR is solvable in polynomial time, the framework applies directly to the flag matroid constraint, and we obtain the following.

12 Omitted Proofs from Section 6 (Hardness with Few Voters)↩︎

We provide proofs of the hardness results for Matroid-FRA with a constant number of voters. Specifically, we show NP-hardness for the cases of \(2\) voters and \(3\) voters, and then deduce hardness for all larger constant values of \(m\).

In the proofs, we use the terminology that \(\pi\) and \(\sigma\) are inconsistent on an unordered pair \(\{e,f\}\subseteq E\) if either \(e\prec_\pi f\) and \(e\succ_\sigma f\), or \(e\succ_\pi f\) and \(e\prec_\sigma f\).

To obtain the theorem, we show NP-completeness of the following decision version.

To obtain the theorem, we show NP-completeness of the following decision version.

References↩︎

---

1. Department of Mathematical and Computing Science, School of Computing, Institute of Science Tokyo, Tokyo 152-8552, Japan. Email: ando.s.373d@m.isct.ac.jp↩︎

2. Department of Mathematical and Computing Science, School of Computing, Institute of Science Tokyo, Tokyo 152-8552, Japan. Email: yokoi@comp.isct.ac.jp↩︎

3. A related exchange-based argument appears in the correctness proof of the algorithm for CFR with block-fairness [11]. To the best of our understanding, some additional justification is needed to ensure that the proposed swap preserves all block-prefix constraints; see Appendix 7 for details.↩︎

4. This terminology is used in some works on weighted rank aggregation. In graph theory, a tournament usually means an orientation of a complete graph.↩︎