{"id":"76419bfb-5ae6-492e-815c-a5f8da2faf07","arxiv_id":"2607.07153","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"A greedy algorithm optimally solves closest-ranking under flag matroid prefix constraints (via Bruhat order), and matroid-constrained rank aggregation is NP-hard for any fixed number of voters ≥ 2.","lead":"This paper gives a polynomial-time greedy algorithm to find the closest ranking satisfying matroid-based prefix constraints, and proves rank aggregation becomes NP-hard with just two voters under these constraints. It matters because it unifies and generalizes fair-ranking constraints under a matroidal framework with clean algorithmic and complexity results.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified","rationale":"I traced the full proof chain from Observation 12 through Proposition 4 to Theorem 17 and found no logical gaps. The tableau criterion is applied correctly: the descent set of π_{B*} is contained in {k_1,...,k_s}, the Gale-minimality of B* provides exactly the needed inequalities, and strict Bruhat order follows from distinctness. The hardness reductions were verified step-by-step, including the cyclic-order contradiction in Claim 37.3. The reader's weakest assumption about quotient relations is not an unaddressed vulnerability — the paper explicitly demonstrates its necessity via counterexample in Appendix B. The verdict of ACCEPT with HIGH confidence is appropriate; no adjustment needed.","tokens_in":35499,"tokens_out":4546,"duration_ms":221577,"concrete_test":"Independently verify Theorem 17 by brute force on small instances: enumerate all permutations σ ∈ S_n for n ≤ 8, all flag matroids of small rank on [n] (e.g., flag matroids arising from generalized partition matroids with 2–3 groups), compute inv(σ) for all feasible σ, and confirm that the greedy output π_{B*} achieves the minimum. If any instance shows a mismatch, the Bruhat order argument has a gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim — that the greedy algorithm outputs the Bruhat-minimum feasible ranking for Flag-Matroid-CFR — rests on a clean chain of arguments that I traced end-to-end without finding a gap. (1) Observation 12 correctly reduces the problem to finding the optimal flag base B, since for any fixed flag base, π_B minimizes d_KT among rankings with those prefix sets. (2) Proposition 4 correctly uses the quotient property to show greedy outputs form a chain and constitute the unique Gale-minimum flag base B*. (3) Theorem 17 applies the tableau criterion (Theorem 16) correctly: D_R(π_{B*}) ⊆ {k_1,...,k_s} because within-block elements are in increasing order; the condition b_{i,h} ≤ d_{i,h} for all h ∈ {k_1,...,k_s} and i ∈ [h] is exactly the Gale order condition B* ⪯^G_π D, which holds by definition of B*; since D_R(π_{B*}) ⊆ {k_1,...,k_s}, the tableau criterion gives π_{B*} ≤_B π_D, and strictness follows from D ≠ B*. The hardness proofs (Theorems 34, 36) were also checked: Claim 35's lower bound for m=2 and Claim 37's third statement (the forcing argument via cyclic order contradictions) are both correct. The reader's identified weakest assumption — that quotient relations are necessary for optimality — is explicitly acknowledged and demonstrated with a counterexample in Appendix B, so it is not an unaddressed risk but a known and handled limitation.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"This paper studies 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 must form a base of a matroid; in the flag matroid case, several prescribed prefixes must form bases of a sequence of matroids linked by quotient relations. This framework generalizes previously studied k-fairness and block-fairness notions and also captures hierarchical and assignment-type lower/upper-quota constraints. The main algorithmic contribution is a polynomial-time greedy algorithm for Flag-Matroid-CFR (finding a closest feasible ranking to a single input ranking under flag matroid prefix constraints). The optimality proof uses the Bruhat order on the symmetric group via the tableau criterion of Björner–Brenti. As a consequence, existing approximation frameworks for fair rank aggregation extend to the matroidal setting, yielding a (2+ε)-approximation for Matroid-FRA and a 2.881-approximation for Flag-Matroid-FRA. The paper also proves that Matroid-FRA is NP-hard for every fixed number m≥2 of voters, even under partition matroid constraints, establishing a sharp dichotomy with the tractable m=1 case.","tokens_in":36179,"tokens_out":1394,"duration_ms":197093,"significance":"The paper makes a clean and well-motivated contribution at the intersection of combinatorial optimization, social choice, and matroid theory. The main positive result — that Flag-Matroid-CFR is solvable by a greedy algorithm whose optimality is proved via the Bruhat order — is elegant and non-obvious. The proof chain is rigorous: Observation 12 reduces the problem to finding the optimal flag base; Proposition 4 uses the quotient property to show greedy outputs form a chain constituting the unique Gale-minimum flag base; and Theorem 17 applies the tableau criterion correctly to establish Bruhat-minimality. The framework is genuinely broader than prior fairness models, and the explicit construction of flag matroids from partitions, transversal structures, and laminar families (Section 3.3, Propositions 6, 8, 10) demonstrates practical relevance. The hardness results for fixed m≥2 are a valuable complement, showing that the constrained setting is strictly harder than unconstrained Kemeny aggregation for small m. The counterexample in Appendix B, showing that quotient relations are necessary for greedy optimality, is a thoughtful addition that clarifies the boundary of tractability. No","major_comments":[],"minor_comments":[{"comment":"Section 4, 'Difficulty with Multiple Matroids': The discussion of why the single-matroid proof does not extend is valuable, but the quadratic objective formulation is described only informally. A brief explicit display of the IP formulation (even in the appendix) would improve readability and allow readers to verify the claim that no direct reduction to a known polynomial-time problem exists.","section":null},{"comment":"Section 3.1: The paper states that a matroid is 'mainly' represented via its base family but that algorithmic access uses an independence oracle. For the generalized transversal matroid (Example 7) and generalized laminar matroid (Example 9), Remark 11 notes that the oracle can be implemented via network flow. It would help to state the oracle complexity more explicitly for these classes, since the greedy algorithm's polynomial-time guarantee depends on the oracle.","section":null},{"comment":"Algorithm 1 (Section 4): The algorithm description is clear, but the running time analysis is not stated explicitly. Since the greedy algorithm makes O(n) oracle calls per matroid and there are s matroids, the total is O(ns) oracle calls plus the cost of constructing the output ranking. Stating this explicitly would strengthen the algorithmic contribution.","section":null},{"comment":"Section 5 / Appendix E: The approximation results are presented somewhat tersely in the main text with details deferred to Appendix E. The (2+ε)-approximation for Matroid-FRA (Theorem 19) involves a non-trivial generalization of the colorful bi-partition problem to a matroidal setting (the Matroid Bi-partition problem in Appendix E.1). A brief mention of this generalization in the main text would give readers a better sense of what is involved beyond a black-box application of prior frameworks.","section":null},{"comment":"Theorem 36 (Appendix F, m=3 hardness): The reduction from X3C is intricate and the use of ternary strings {0,1,2}^d as the ground set is clever. The construction of the three rankings via lexicographic orders from cyclically shifted underlying orders is well-motivated. However, the role of the parameter d = h+2 (where 2^h = q) could be stated more prominently, as it controls the recursive structure. A sentence summarizing the high-level strategy of the reduction before diving into the technical details would aid the reader.","section":null},{"comment":"References: The citation [9] (Brandenburg–Loho–Smith) is listed with publication year 2026, which appears to be a future date. This may be a typo or a reference to an forthcoming publication; please verify and update with final publication details.","section":null},{"comment":"Typo in Section 4 ('Difficulty with Multiple Matroids'): The phrase 'a non-optimal earlier base reduces the latter terms' should perhaps read 'a non-optimal earlier base may reduce the latter terms' for precision. Also, in the same paragraph, 'the base family' is used where 'a base' might be intended in the phrase 'Choosing B_1 = {1} minimizes the first term.'","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is mathematically sound and the central claims are well-supported. The Bruhat order argument is the key technical innovation and it is executed correctly. The hardness proofs for m=2 and m=3 are both non-trivial; the m=3 proof in particular is quite involved and the authors should be commended for the construction. I checked the proof of Theorem 17 end-to-end and found no gaps: the application of the tableau criterion is correct, the key observation that D_R(π_{B*}) ⊆ {k_1,...,k_s} follows from the within-block increasing order, and the Gale order condition is exactly what is needed. The minor comments are all presentation-level and do not affect correctness. The paper fits well within the scope of a discrete mathematics journal."},"author_rebuttal":null,"desk_editor":{"model":"glm-5.2","letter":"The main thing to know: this paper gives an exact polynomial-time greedy algorithm for finding the closest feasible ranking under flag matroid prefix constraints, with the optimality proof going through the Bruhat order on the symmetric group. That is a genuinely new technique for this problem class, and it works. The companion result — NP-hardness of matroid-constrained rank aggregation for every fixed number of voters m≥2, even for partition matroids — is also clean and gives a sharp dichotomy against the m=1 tractability case.","headline":"Clean greedy algorithm for flag-matroid ranking with a sharp hardness dichotomy — worth a serious referee.","tokens_in":36251,"tokens_out":170,"would_cite":true,"duration_ms":87152,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Greedy algorithm solves constrained ranking via Bruhat order","keywords":[],"falsifier":"A concrete counterexample in Appendix B with two partition matroids that do not satisfy the quotient relation: on this instance, both the forward and backward greedy algorithms produce rankings with Kendall tau distance 21 from the input, while a feasible ranking achieving distance 20 exists.","tokens_in":35788,"feed_emoji":"🏅","tokens_out":837,"duration_ms":198670,"temperature":0.7,"pith_summary":"The paper studies a generalization of fair ranking where the top-k prefix of an output ranking must form a base of a matroid, or where several prefix lengths must simultaneously form bases of a sequence of matroids linked by quotient relations (a flag matroid). This framework subsumes previously studied k-fairness and block-fairness notions and extends to hierarchical and assignment-type quota constraints. The central result is that, given a single input ranking, the closest feasible ranking under flag matroid prefix constraints can be found in polynomial time by a greedy algorithm: compute the unique Gale-minimum flag base and output the ranking that places each block of that base in order, with elements within each block arranged as in the input. The proof of optimality uses the tableau criterion for the Bruhat order on the symmetric group, showing the greedy output is the Bruhat-minimum among all feasible rankings. The paper also proves that the rank aggregation version with matroid constraints is NP-hard for every fixed number of voters m >= 2, even for partition matroids, establishing a sharp dichotomy between the single-voter case (tractable) and all multi-voter cases (hard).","feed_headline":"Greedy algorithm solves constrained ranking via Bruhat order","feed_subtitle":"Flag matroid constraints on ranking prefixes are tractable for one voter but NP-hard for two or more, with optimality proved through Bruhat-","key_machinery":"The Bruhat order on the symmetric group, the tableau criterion of Bjorner-Brenti, Gale order on matroid bases, and flag matroids (sequences of matroids linked by quotient relations).","core_discovery":"The greedy algorithm that computes the Gale-minimum base for each matroid in a flag matroid, then concatenates the resulting blocks in order, produces the unique optimal solution to the closest feasible ranking problem under flag matroid prefix constraints. The proof works by identifying rankings with permutations, noting that Kendall tau distance to the identity equals the inversion number, and then showing via the Bjorner-Brenti tableau criterion for the Bruhat order that the greedy output is the Bruhat-minimum feasible ranking. Since Bruhat-minimality implies inversion-number-minimality, the greedy output is optimal. This approach works because the quotient relations between consecutive m","pith_inferences":[],"forward_implications":["Existing approximation frameworks for fair rank aggregation carry over: a (2+epsilon)-approximation for matroid-constrained aggregation and a 2.881-approximation for flag-matroid-constrained aggregation follow from the exact closest-ranking algorithm as a subroutine.","The NP-hardness for every fixed m >= 2, even for partition matroids, contrasts sharply with the unconstrained Kemeny problem where m=2 is tractable and the status of m=3 and m=5 remains open.","The framework captures hierarchical quota constraints via generalized laminar matroids and assignment-type constraints via generalized transversal matroids, broadening applicability beyond simple group-based fairness.","The counterexample in Appendix B shows that if the quotient relations between matroids are dropped, the greedy algorithm can fail to find an optimal solution, pinpointing the quotient property as essential for tractability."],"fun_headline_variants":["Greedy algorithm finds closest feasible ranking under matroid constraints","One ranking is tractable under flag matroids; two or more rankings is NP-hard","Bruhat order proof shows greedy is optimal for constrained ranking","Matroid constraints generalize fairness in ranking with polynomial-time solution"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The optimality of the greedy algorithm depends on the matroid quotient relations between consecutive matroids in the flag matroid. Without these quotient relations, the greedy outputs may not even form a valid chain of bases, and the Bruhat-order argument breaks down; the paper gives a concrete counterexample showing suboptimal greedy behavior when quotient relations are absent.","fun_headline_variants_meta":{"raw":{"variants":["Greedy algorithm finds closest feasible ranking under matroid constraints","One ranking is tractable under flag matroids; two or more rankings is NP-hard","Bruhat order proof shows greedy is optimal for constrained ranking","Matroid constraints generalize fairness in ranking with polynomial-time solution"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":621,"prompt_tokens":549,"completion_tokens":72,"prompt_tokens_details":null},"tokens_in":549,"tokens_out":72,"duration_ms":41098,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-09T18:44:38.089528+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"A concrete counterexample in Appendix B with two partition matroids that do not satisfy the quotient relation: on this instance, both the forward and backward greedy algorithms produce rankings with Kendall tau distance 21 from the input, while a feasible ranking achieving distance 20 exists.","supporting_citations":[],"review_version":1}