Pith. sign in

REVIEW 7 minor 57 references

Ranking and Rank Aggregation with Matroid Prefix Constraints

T0 review · 0 major / 7 minor · reviewed 2026-07-09 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Greedy algorithm solves constrained ranking via Bruhat order

desk verdict Clean greedy algorithm for flag-matroid ranking with a sharp hardness dichotomy — worth a serious referee. read the letter →

arxiv 2607.07153 v1 pith:4KQGUQOP submitted 2026-07-08 cs.DM cs.DS

Seiei Ando , Yu Yokoi This is my paper · ORCID
classification cs.DMcs.DS
keywords matroidconstraintsrankingaggregationrankflagprefixunder
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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).

What carries the argument

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).

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 7 minor

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.

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

minor comments (7)
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.'

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found; derivation is self-contained

full rationale

The paper's central algorithmic result — that the greedy algorithm outputs the Bruhat-minimum feasible ranking for Flag-Matroid-CFR — is derived from first principles without circular dependencies. The derivation chain is: (1) Observation 12 reduces the problem to finding an optimal flag base B, since for any fixed flag base, π_B minimizes d_KT by a straightforward inversion-counting argument (proof in Appendix D). (2) Proposition 4 uses the matroid quotient property to show greedy outputs form a chain and constitute the unique Gale-minimum flag base; this is proved directly via the rank function definition of quotient. (3) Theorem 17 applies the tableau criterion (Theorem 16, cited from Björner–Brenti [5], an external reference) to show π_{B*} ≤_B π_D: the key step is that D_R(π_{B*}) ⊆ {k_1,...,k_s} because within-block elements are in increasing order, and the condition b_{i,h} ≤ d_{i,h} is exactly the Gale order condition B* ⪯^G_π D, which holds by definition of B*. No step reduces to its own input by construction. The approximation results (Theorems 19, 20) extend prior frameworks [15] but use the newly proven CFR solvability as a black-box subroutine — legitimate non-circular extension. The NP-hardness reductions (Theorems 34, 36) reduce from standard NP-complete problems (3DM, X3C). The self-citations to [9] (Brandenburg–Loho–Smith) for induction preserving quotients and to [38] (Yokoi, second author) for generalized polymatroid structures are auxiliary tools, not load-bearing for the main theorem. The paper is self-contained against external mathematical benchmarks.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper relies entirely on standard mathematical results from matroid theory, Coxeter group theory, and combinatorial optimization. No new axioms, free parameters, or invented entities are introduced. The algorithmic framework uses the standard independence oracle model.

assumptions (5)
  • standard math Gale's theorem: a family B ⊆ (E choose k) is a matroid base family iff for every ranking π, B has a unique Gale-minimum member.
    Invoked in Section 3.1 to characterize matroids and justify the greedy algorithm for minimum-weight bases.
  • standard math Flag matroid Gale order characterization: a nonempty family F ⊆ F^k_E is a flag matroid base family iff for every ranking π, F has a unique Gale-minimum member.
    Invoked in Section 3.2, referencing Borovik-Gelfand-Stone [7]. Used to establish that greedy outputs form the minimum flag base.
  • standard math Björner-Brenti tableau criterion for Bruhat order on S_n.
    Invoked as Theorem 16 to prove that the greedy output π_{B*} is Bruhat-minimal among feasible rankings, establishing optimality.
  • domain assumption Independence oracle model for matroids.
    Stated in Section 3.1: 'we assume access to an independence oracle, following the usual convention.' Used for complexity analysis of the greedy algorithm.
  • standard math Kendall tau distance equals inversion number when input ranking is the identity.
    Used in Section 4 to connect the ranking problem to the Bruhat order on permutations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Ranking and Rank Aggregation with Matroid Prefix Constraints." pith.science (2026). https://pith.science/paper/4KQGUQOP

@misc{pith2026260707153,
  author       = {Pith},
  title        = {Pith review of: Ranking and Rank Aggregation with Matroid Prefix Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4KQGUQOP}},
  note         = {Machine review of arXiv:2607.07153}
}
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.

Figures

Figures reproduced from arXiv: 2607.07153 by the authors.

Figure 1
Figure 1. A construction of πB for a ranking π and a flag base B = (B1, B2, . . . , Bs). In each block, elements are arranged according to π. Observation 12 (⋆). For a ranking π : [n] → E and any flag base B = (B1, B2, . . . , Bs), among rankings σ satisfying Topki (σ) = Bi (i ∈ [s]), the one minimizing dKT(σ, π) is πB. We postpone the proof to Appendix D but it is summarized as follows. The constraints Topki (σ) = Bi (i ∈ [s… view at source ↗
Figure 2
Figure 2. An example on which the greedy approach does not work. Blue regions indicate the partition [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. Illustration of the reduction from 3DM to Matroid-FRA with two voters. The left figure shows [PITH_FULL_IMAGE:figures/full_fig_p028_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

57 extracted references · 57 canonical work pages

  1. [1]

    Aggregating inconsistent information: Ranking and clustering.Journal of the ACM, 55(5):23:1–23:27, 2008.doi:10.1145/ 1411509.1411513

    Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering.Journal of the ACM, 55(5):23:1–23:27, 2008.doi:10.1145/ 1411509.1411513

    work page arXiv 2008

  2. [2]

    doi:10.1016/j.jcss.2019.04.005

    GeorgBachmeier, FelixBrandt, ChristianGeist, PaulHarrenstein, KeyvanKardel, Dominik Peters, and Hans Georg Seedig.k-majority digraphs and the hardness of voting with a constant number of voters.Journal of Computer and System Sciences, 105:130–157, 2019. doi:10.1016/j.jcss.2019.04.005

    work page doi:10.1016/j.jcss.2019.04.005 2019

  3. [3]

    Bartholdi, III, Craig A

    John J. Bartholdi, III, Craig A. Tovey, and Michael A. Trick. Voting schemes for which it can be difficult to tell who won the election.Social Choice and Welfare, 6(2):157–165, 1989. doi:10.1007/BF00303169

    work page doi:10.1007/bf00303169 1989

  4. [4]

    Fellows, Jiong Guo, Rolf Niedermeier, and Frances A

    Nadja Betzler, Michael R. Fellows, Jiong Guo, Rolf Niedermeier, and Frances A. Rosamond. Fixed-parameter algorithms for Kemeny rankings.Theoretical Computer Science, 410:4554– 4570, 2009.doi:10.1016/j.tcs.2009.08.033

    work page doi:10.1016/j.tcs.2009.08.033 2009

  5. [5]

    An improved tableau criterion for Bruhat order.The Electronic Journal of Combinatorics, 3(1):R22, 1996.doi:10.37236/1246

    Anders Björner and Francesco Brenti. An improved tableau criterion for Bruhat order.The Electronic Journal of Combinatorics, 3(1):R22, 1996.doi:10.37236/1246

    work page doi:10.37236/1246 1996

  6. [6]

    Springer, 2005.doi:10.1007/3-540-27596-7

    Anders Björner and Francesco Brenti.Combinatorics of Coxeter Groups, volume 231 of Graduate Texts in Mathematics. Springer, 2005.doi:10.1007/3-540-27596-7

    work page doi:10.1007/3-540-27596-7 2005

  7. [7]

    Borovik, Israel M

    Alexandre V. Borovik, Israel M. Gelfand, and David A. Stone. On the topology of the combinatorial flag varieties.Discrete & Computational Geometry, 27(2):195–214, 2002. doi:10.1007/s00454-001-0061-8

    work page doi:10.1007/s00454-001-0061-8 2002

  8. [8]

    Borovik, Israel M

    Alexandre V. Borovik, Israel M. Gelfand, and Neil White.Coxeter Matroids, volume 216 ofProgress in Mathematics. Birkhäuser Boston, Boston, MA, 2003.doi:10.1007/ 978-1-4612-2066-4

    work page 2003

Show all 57 references
  1. [9]

    Quotients of M-convex sets and M-convex functions.Combinatorial Theory, 6(1), 2026.doi:10.5070/C66165701

    Marie-Charlotte Brandenburg, Georg Loho, and Ben Smith. Quotients of M-convex sets and M-convex functions.Combinatorial Theory, 6(1), 2026.doi:10.5070/C66165701

    2026 doi

  2. [10]

    Multiwinner elections with diversity constraints

    Robert Bredereck, Piotr Faliszewski, Ayumi Igarashi, Martin Lackner, and Piotr Skowron. Multiwinner elections with diversity constraints. InProceedings of the 32nd AAAI Con- ference on Artificial Intelligence (AAAI 2018), pages 933–940. AAAI Press, 2018. URL: https://ojs.aaai....

    2018

  3. [11]

    Richard A. Brualdi. Induced matroids.Proceedings of the American Mathematical Society, 29(2):213–221, 1971.doi:10.2307/2038115

    1971 doi

  4. [12]

    Constructions

    Thomas Brylawski. Constructions. In Neil White, editor,Theory of Matroids, volume 26 ofEncyclopedia of Mathematics and its Applications, pages 127–223. Cambridge University Press, Cambridge, 1986.doi:10.1017/CBO9780511629563.010

    1986 doi

  5. [13]

    Flag matroids: algebra and geometry

    Amanda Cameron, Rodica Dinu, Mateusz Michałek, and Tim Seynnaeve. Flag matroids: algebra and geometry. InInteractions with Lattice Polytopes, pages 73–114. Springer Inter- national Publishing, Cham, 2022.doi:10.1007/978-3-030-98327-7_4. 14

    2022 doi

  6. [14]

    Elisa Celis, Damian Straszak, and Nisheeth K

    L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. Ranking with fairness constraints. In45th International Colloquium on Automata, Languages, and Pro- gramming (ICALP 2018), volume 107 ofLeibniz International Proceedings in Infor- matics (LIPIcs), pages 28:1–28:15. Schl...

    2018

  7. [15]

    2018.28,doi:10.4230/LIPIcs.ICALP.2018.28

    URL:https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP. 2018.28,doi:10.4230/LIPIcs.ICALP.2018.28

    2018 doi

  8. [16]

    Improved rank aggregation under fairness constraint

    Diptarka Chakraborty, Himika Das, Sanjana Dey, and Alvin Hong Yao Yan. Improved rank aggregation under fairness constraint. InProceedings of the 34th International Joint Confer- ence on Artificial Intelligence (IJCAI 2025), pages 330–338. International Joint Conferences on Art...

    2025 doi

  9. [17]

    Fair rank aggregation

    Diptarka Chakraborty, Syamantak Das, Arindam Khan, and Aditya Subramanian. Fair rank aggregation. InAdvances in Neural Information Processing Systems (NeurIPS 2022), volume 35, pages 23965–23978, 2022. Conference version in NeurIPS 2022; arXiv version cited in the main text. U...

    2022 arXiv

  10. [18]

    A natural family of flag matroids.SIAM Journal on Discrete Mathematics, 21(1):130–140, 2007.doi:10.1137/050627873

    Anna de Mier. A natural family of flag matroids.SIAM Journal on Discrete Mathematics, 21(1):130–140, 2007.doi:10.1137/050627873

    2007 doi

  11. [19]

    Bumin Yenmez

    Battal Doğan, Kenzo Imamura, and M. Bumin Yenmez. Market design with deferred acceptance: A recipe for characterizations.Journal of Economic Theory, 228:106057, 2025. doi:10.1016/j.jet.2025.106057

    2025 doi

  12. [20]

    Rank aggregation methods for the Web

    Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar. Rank aggregation methods for the Web. InProceedings of the 10th International Conference on World Wide Web (WWW 2001), pages 613–622. ACM, 2001.doi:10.1145/371920.372165

    2001 doi

  13. [21]

    Kemeny consensus complexity

    Zack Fitzsimmons and Edith Hemaspaandra. Kemeny consensus complexity. InProceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), pages 196–202. International Joint Conferences on Artificial Intelligence Organization, 2021. Main Track.doi:...

    2021 doi

  14. [22]

    Oxford University Press, Oxford, 2011

    András Frank.Connections in Combinatorial Optimization, volume 38 ofOxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2011

    2011

  15. [23]

    Optimal assignments in an ordered set: An application of matroid theory.Jour- nal of Combinatorial Theory, 4(2):176–180, 1968.doi:10.1016/S0021-9800(68)80039-0

    David Gale. Optimal assignments in an ordered set: An application of matroid theory.Jour- nal of Combinatorial Theory, 4(2):176–180, 1968.doi:10.1016/S0021-9800(68)80039-0

    1968 doi

  16. [24]

    Garey and David S

    Michael R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco, 1979. URL: https://dl.acm.org/doi/10.5555/578533,doi:10.5555/578533

    1979 doi

  17. [25]

    Sampling individually-fair rankings that are always group fair

    Sruthi Gorantla, Anay Mehrotra, Amit Deshpande, and Anand Louis. Sampling individually-fair rankings that are always group fair. InProceedings of the 2023 AAAI/ACM Conference on AI, Ethics, and Society (AIES ’23), pages 205–216. Association for Com- puting Machinery, 2023.doi:...

    2023 doi

  18. [26]

    The complexity of Kemeny elec- tions.Theoretical Computer Science, 349:382–391, 2005.doi:10.1016/j.tcs.2005.08

    Edith Hemaspaandra, Holger Spakowski, and Jörg Vogel. The complexity of Kemeny elec- tions.Theoretical Computer Science, 349:382–391, 2005.doi:10.1016/j.tcs.2005.08. 031. 15

    2005 doi

  19. [27]

    Packing of mixed hyperarborescences with flexible roots via matroid intersection.The Electronic Journal of Combinatorics, 28(3):P3.29, 2021.doi: 10.37236/10105

    Florian Hörsch and Zoltán Szigeti. Packing of mixed hyperarborescences with flexible roots via matroid intersection.The Electronic Journal of Combinatorics, 28(3):P3.29, 2021.doi: 10.37236/10105

    2021 doi

  20. [28]

    Flag matroids with coefficients.Advances in Mathe- matics, 436:109396, 2024.doi:10.1016/j.aim.2023.109396

    Manoel Jarra and Oliver Lorscheid. Flag matroids with coefficients.Advances in Mathe- matics, 436:109396, 2024.doi:10.1016/j.aim.2023.109396

    2024 doi

  21. [29]

    Richard M. Karp. Reducibility among combinatorial problems. InComplexity of Com- puter Computations, pages 85–103. Plenum Press, New York, 1972.doi:10.1007/ 978-1-4684-2001-2_9

    1972

  22. [30]

    John G. Kemeny. Mathematics without numbers.Daedalus, 88(4):577–591, 1959

    1959

  23. [31]

    How to rank with few errors

    Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors. InProceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), pages 95–103. ACM, 2007.doi:10.1145/1250790.1250806

    2007 doi

  24. [32]

    On weakly and strongly popular rankings

    Sonja Kraiczy, Ágnes Cseh, and David Manlove. On weakly and strongly popular rankings. Discrete Applied Mathematics, 340:134–152, 2023.doi:10.1016/j.dam.2023.06.041

    2023 doi

  25. [33]

    Oxford University Press, 2nd edition, 2011.doi:10.1093/ acprof:oso/9780198566946.001.0001

    James Oxley.Matroid Theory. Oxford University Press, 2nd edition, 2011.doi:10.1093/ acprof:oso/9780198566946.001.0001

    2011

  26. [34]

    Independence spaces and combinatorial problems.Proceedings of the London Mathematical Society, s3-19(1):17–30, 1969.doi:10.1112/plms/s3-19.1.17

    Hazel Perfect. Independence spaces and combinatorial problems.Proceedings of the London Mathematical Society, s3-19(1):17–30, 1969.doi:10.1112/plms/s3-19.1.17

    1969 doi

  27. [35]

    Springer, 2003

    Alexander Schrijver.Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003

    2003

  28. [36]

    A framework for the greedy algorithm.Discrete Applied Mathematics, 121(1–3):247–260, 2002.doi:10.1016/S0166-218X(01)00362-6

    Andrew Vince. A framework for the greedy algorithm.Discrete Applied Mathematics, 121(1–3):247–260, 2002.doi:10.1016/S0166-218X(01)00362-6

    2002 doi

  29. [37]

    A survey on rank aggre- gation

    Siyi Wang, Qi Deng, Shiwei Feng, Hong Zhang, and Chao Liang. A survey on rank aggre- gation. InProceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI 2024), pages 8281–8289. International Joint Conferences on Artificial Intelligence Organizati...

    2024 doi

  30. [38]

    Rank aggregation with proportionate fairness

    Dong Wei, Md Mouinul Islam, Baruch Schieber, and Senjuti Basu Roy. Rank aggregation with proportionate fairness. InProceedings of the 2022 International Conference on Man- agement of Data (SIGMOD 2022), pages 262–275. ACM, 2022.doi:10.1145/3514221. 3517865

    2022 doi

  31. [39]

    A generalized polymatroid approach to stable matchings with lower quotas

    Yu Yokoi. A generalized polymatroid approach to stable matchings with lower quotas. Mathematics of Operations Research, 42(1):238–255, 2017.doi:10.1287/moor.2016.0802

    2017 doi

  32. [40]

    Peyton Young and Arthur Levenglick

    H. Peyton Young and Arthur Levenglick. A consistent extension of Condorcet’s election principle.SIAM Journal on Applied Mathematics, 35(2):285–300, 1978.doi:10.1137/ 0135023

    1978

  33. [41]

    Condorcet’s theory of voting.American Political Science Review, 82(4):1231–1244, 1988.doi:10.2307/1961757

    Hobart Peyton Young. Condorcet’s theory of voting.American Political Science Review, 82(4):1231–1244, 1988.doi:10.2307/1961757

    1988 doi

  34. [42]

    Fa*ir: A fair top-k ranking algorithm

    Meike Zehlike, Francesco Bonchi, Carlos Castillo, Sara Hajian, Mohamed Megahed, and Ricardo Baeza-Yates. Fa*ir: A fair top-k ranking algorithm. InProceedings of the 26th ACM International Conference on Information and Knowledge Management (CIKM 2017), pages 1569–1578. ACM, 201...

    2017 doi

  35. [43]

    This is equivalent to the condition that for everyi∈[s−1]andB∈ B i, there existsB′ ∈ B i+1 withB⊆B ′

    The independent set families satisfyI1 ⊆ I 2 ⊆ · · · ⊆ I s. This is equivalent to the condition that for everyi∈[s−1]andB∈ B i, there existsB′ ∈ B i+1 withB⊆B ′

  36. [44]

    3.(M 1, M2,

    The above condition holds, and in addition, for everyi∈[s]\ {1}andB∈ B i, there exists B′ ∈ B i−1 withB ′ ⊆B. 3.(M 1, M2, . . . , Ms)forms a flag matroid. Clearly, 2 implies 1. It is also not hard to see that 3 implies 2; a quotient relation implies rkMi(X)−rk Mi(∅)≤rk Mi+1(X)...

  37. [45]

    , s, do the following

    LetB 0 =∅and fori= 1,2, . . . , s, do the following. •LetX←B i−1. •For eache∈E\B i−1, in the ascending order ofπ, ifX∪ {e} ∈ Ii, thenX←X∪ {e}. •SetB i ←X

  38. [46]

    , Bs)and outputπ B as defined in Section 4

    LetB= (B 1, . . . , Bs)and outputπ B as defined in Section 4. Backward Greedy Algorithm

  39. [47]

    ,1, do the following

    LetB s+1 =Eand fori=s, s−1, . . . ,1, do the following. •LetX← ∅. •For eache∈B i+1, in the ascending order ofπ, ifX∪ {e} ∈ I i, thenX←X∪ {e}. •SetB i ←X

  40. [48]

    , Bs)and outputπ B as defined in Section 4

    LetB= (B 1, . . . , Bs)and outputπ B as defined in Section 4. Then the following hold. 18 •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 algorit...

  41. [49]

    Indeed, we can impose these assumptions without loss of generality

    IfL∈ Lis not a leaf, thenLis partitioned into its children. Indeed, we can impose these assumptions without loss of generality. If the originalLdoes not satisfy the first condition, then we can addEtoLand setg(E) =f(E) =kandg ′(E) =f ′(E) = k′. If the second condition is not s...

  42. [50]

    Find an appropriate bi-partition{B, E\B}such thatBhas sizekand satisfiesk-fairness by solving thecolorful bi-partition problem(described below in a generalized form)

  43. [51]

    Apply the known PTAS for rank aggregation (without constraints) by Kenyon-Mathieu and Schudy [30] to each of(πi|B)i∈[m] and(π i|E\B)i∈[m] to obtainσ B andσ E\B

  44. [52]

    To generalize their algorithm to Matroid-FRA, we consider solving the following generalized version of the colorful bi-partition subproblem

    Output a concatenation ofσB andσ E\B asσ. 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 aweighted tournament. In this paper, a...

  45. [53]

    We always haveHα(σ)≥4·n 2 α

  46. [54]

    The equality holds if and only if, for every triple(e, f, g)∈Jα0K×Jα1K×Jα2K, the elements e, f, gare ordered inσin this order or in a cyclic shift of this order

  47. [55]

    Proof.Note that each pair{e, f} ∈ P α consists of elements taken from two distinct sets among Jα0K,Jα1K, andJα2K, each of which has sizen α

    If the equality holds, then for any positive integerℓ, one of the following must hold: •Jα0KorJα1KorJα2Kis completely contained inTop ℓ(σ), or •Jα0KorJα1KorJα2Kis disjoint fromTop ℓ(σ). Proof.Note that each pair{e, f} ∈ P α consists of elements taken from two distinct sets amo...

  48. [56]

    For eachα∈ {0,1,2} d, letˆσα be the trivial ranking on the singleton{α}

  49. [57]

    First, partition the setJαKinto the following subsets: E1 =Jα0K∩B X , F 1 =Jα1K∩B X , G 1 =Jα2K∩B X , E2 =Jα0K\B X , F 2 =Jα1K\B X , G 2 =Jα2K\B X

    For eachα∈ {0,1,2} <d, we defineˆσα usingˆσα0,ˆσα1, andˆσα2 as follows. First, partition the setJαKinto the following subsets: E1 =Jα0K∩B X , F 1 =Jα1K∩B X , G 1 =Jα2K∩B X , E2 =Jα0K\B X , F 2 =Jα1K\B X , G 2 =Jα2K\B X . By the definition ofBX and the setE mand, at least one o...

Pith tools

Reviewed July 9, 2026 · model on record in the stance chip above.