{"ID":6138153,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-11T08:45:50.451512195Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07153","arxiv_id":"2607.07153","title":"Ranking and Rank Aggregation with Matroid Prefix Constraints","abstract":"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\\ge 2$ of input rankings, even under partition matroid constraints.","short_abstract":"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 s...","url_abs":"https://arxiv.org/abs/2607.07153","url_pdf":"https://arxiv.org/pdf/2607.07153v1","authors":"[\"Seiei Ando\",\"Yu Yokoi\"]","published":"2026-07-08T08:47:23Z","proceeding":"cs.DM","tasks":"[\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}