2026/07/08 by Seiei Ando, Yu Yokoi · 1 voice
Computer Science · #cs.DM #cs.DS
We study ranking and rank aggregation under the Kendall tau distance, subject to matroid or flag matroid constraints on prefixes of the output ranking. In the matroid case, the top-k prefix is required to form a base of a matroid; in the flag matroid case, several prescribed prefixes are required to form bases of a sequence of matroids linked by quotient relations. This framework contains the previously studied notions of k-fairness and block-fairness as special cases, and also captures more general hierarchical and assignment-type lower- and upper-quota constraints. We provide a polynomial-time algorithm for finding, given a single input ranking, a closest feasible ranking under flag matroid prefix constraints. The algorithm is a natural greedy procedure, and its optimality is proved via a Bruhat order argument on the symmetric group. As a consequence, existing approximation frameworks for fair rank aggregation carry over to the matroidal setting. We also prove that rank aggregation with matroid constraints is NP-hard for every fixed number m≥ 2 of input rankings, even under partition matroid constraints.