pith. sign in

arxiv: 2605.20070 · v1 · pith:4EKFQAB3new · submitted 2026-05-19 · 💻 cs.DS · math.OC

Optimizing for Fairness in Generalized Kidney Exchange: Theory and Computations

Claire Chang , Arin Khare , David Shmoys This is my paper

Pith reviewed 2026-05-20 03:16 UTC · model grok-4.3

classification 💻 cs.DS math.OC
keywords kidney exchangefairnessrandomized algorithmsbootstrappingweighted matchingpath and cycle exchangescomputational experiments
0
0 comments X

The pith

Any optimization subroutine for kidney exchanges can be bootstrapped into a fair randomized mechanism with a polynomial number of calls.

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

The paper extends strong fairness guarantees from basic matchings in kidney exchange to weighted settings and more general structures such as paths and cycles. It proves that strongly polynomial algorithms exist for weighted matchings and 2-paths that preserve fairness properties including individual matching probabilities and Nash social welfare. For structures where maximum coverage is NP-hard, the authors show that repeated calls to any available optimization subroutine produce mechanisms with the same fairness guarantees. This matters for real kidney exchange programs because they routinely use paths and cycles, and the approach allows fairness to be added without requiring entirely new solvers.

Core claim

The authors show that strongly polynomial algorithms guaranteeing the same fairness properties can be obtained in weighted settings for matching and 2-paths. They provide a general result showing that any optimization subroutine for the allowed exchange structures can be bootstrapped using a polynomial number of calls to yield a mechanism that has analogous fairness properties to those obtained for matching.

What carries the argument

The bootstrapping procedure that repeatedly invokes an optimization subroutine for the maximum coverage problem to build a distribution over exchanges with fairness properties.

If this is right

  • Fairness guarantees extend in strongly polynomial time to weighted matchings and 2-path exchanges.
  • Generalized exchanges with paths and cycles can inherit matching fairness properties through polynomial reuse of any coverage solver.
  • Computational results on synthetic and real data confirm that fairness considerations improve equity in generalized mechanisms.
  • The same individual fairness objectives, such as Nash social welfare, remain achievable for the allowed structures.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The bootstrapping technique may apply to other allocation settings where complex structures make direct fairness optimization difficult.
  • Approximation algorithms or heuristics could substitute for exact solvers in the procedure while preserving approximate fairness.
  • The efficiency loss from enforcing fairness in these generalized exchanges can be quantified more precisely on larger real-world instances.

Load-bearing premise

The general bootstrapping result assumes the existence of an optimization subroutine that can solve the underlying maximum coverage problem for the allowed exchange structures.

What would settle it

An instance of a kidney exchange allowing 3-cycles where repeated calls to an optimal coverage solver produce a randomized mechanism whose individual matching probabilities deviate from those achieved by the matching case would falsify the general claim.

Figures

Figures reproduced from arXiv: 2605.20070 by Arin Khare, Claire Chang, David Shmoys.

Figure 1
Figure 1. Figure 1: Counterexamples illustrating the tension between utilitarian and fairness objectives. [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Edmonds-Gallai decomposition of a graph G and the corresponding construction of the circulation problem. The next question is to determine when the circulation problem is feasible, which is answered by the following theorem. Proposition 3 (Ahuja et al.). A circulation problem with nonnegative lower bounds on arc flows lij and upper bounds uij is feasible if and only if for every set S of nodes X (i,j)∈(S,S… view at source ↗
Figure 3
Figure 3. Figure 3: Five local configurations of 2-paths starting from an NDD [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Gadget for reduction from 3DM to maximum covering with 2-cycles and paths of length [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Patient-donor pair inclusion probabilities for KEP1, with cycles of length at most 3 [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Inclusion probabilities for maximum-cardinality 2- and 3-cycle packings. The plot on the [PITH_FULL_IMAGE:figures/full_fig_p019_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Histograms of three coverage-related metrics over the KEP1 instances. [PITH_FULL_IMAGE:figures/full_fig_p019_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Inclusion probabilities of Leximin, Heuristic, and Implicit (using the same color scheme as before) for maximum-cardinality 2- and 3-cycle packings on all 25 KEP1 instances. 20 [PITH_FULL_IMAGE:figures/full_fig_p020_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: (Left) Randomized algorithm results for maximum-cardinality 2-cycle and 3-cycle pack [PITH_FULL_IMAGE:figures/full_fig_p021_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Inclusion probabilities for maximum-cardinality matchings (left), maximum-weight [PITH_FULL_IMAGE:figures/full_fig_p021_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Histogram of waiting times (in 30-day months) for weighted matchings for [PITH_FULL_IMAGE:figures/full_fig_p022_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: The left plot shows average difference of node covering probability distributions between [PITH_FULL_IMAGE:figures/full_fig_p023_12.png] view at source ↗
read the original abstract

The seminal work of Roth, S\"onmez, & \"Unver shows that the Edmonds-Gallai structure theorem for non-bipartite matching can be leveraged to yield a randomized algorithm to match patient-donor pairs in kidney exchange with extraordinarily strong properties. This breakthrough led to randomized polynomial-time algorithms to find a maximum-cardinality matching maximizing individual fairness objectives--measured by the probability that nodes are matched--such as Nash social welfare. But the exchanges allowed in practice go beyond cardinality matching, generalizing to weighted variants and allowing structures such as paths and 3-cycles. We show that strongly polynomial algorithms guaranteeing the same fairness properties can be obtained in weighted settings for matching and 2-paths. While even maximum cardinality coverage with cycles and paths of length at least three is NP-hard, we provide a general result showing that any optimization subroutine (for whichever structure is allowed) can be bootstrapped using a polynomial number of calls to yield a mechanism that has analogous fairness properties to those obtained for matching. We complement these theoretical results with computational results, both on well-studied synthetic data-sets and on samples drawn from real data, that demonstrate the striking advantages of adding fairness considerations to more general kidney-exchange mechanisms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper extends the fairness results of Roth, Sönmez, and Ünver for kidney exchange, which rely on the Edmonds-Gallai theorem to produce randomized matchings with strong individual fairness guarantees (e.g., Nash social welfare maximization via per-node matching probabilities). It develops strongly polynomial algorithms that preserve these fairness properties for weighted matchings and weighted 2-paths, and gives a general reduction showing that any black-box optimization subroutine for maximum coverage over allowed structures (cycles/paths) can be invoked a polynomial number of times to produce a distribution with analogous fairness properties. The theoretical results are complemented by computational experiments on synthetic instances and real kidney-exchange data demonstrating practical advantages of fairness-aware mechanisms.

Significance. If the fairness preservation claims hold, the work would meaningfully broaden the applicability of fair randomized mechanisms to realistic kidney-exchange models that incorporate weights and longer exchange structures. The black-box bootstrapping approach is a notable strength for modularity, and the computational results on real data provide concrete evidence of impact. The paper ships explicit algorithmic constructions and reproducible-style experiments, which strengthen its contribution to algorithmic mechanism design.

major comments (2)
  1. [§4.3, Theorem 4] §4.3, Theorem 4 (general bootstrapping): The reduction constructs a distribution as a convex combination of outputs from the max-coverage oracle. It is not immediate that this preserves the exact per-node lower bounds on matching probability that follow from the Edmonds-Gallai decomposition in the unweighted matching case; the marginal probabilities could be strictly weaker for structures without an analogous structure theorem (e.g., weighted 2-paths or 3-cycles). A concrete counter-example or explicit bound relating the oracle outputs to the original fairness measure is needed to support the 'analogous fairness properties' claim.
  2. [§3.2, Algorithm 2] §3.2, Algorithm 2 (weighted 2-paths): The strongly polynomial algorithm is claimed to guarantee the same fairness properties as the matching case, yet the fairness objective is defined via probabilities over randomized outcomes. When edge weights are present, the notion of 'maximum cardinality' must be replaced by a weighted objective; it is unclear whether the individual probability lower bounds remain identical or are scaled by the weights, which would affect the Nash-welfare optimality statement.
minor comments (2)
  1. [§2] The notation for the fairness measure (e.g., the precise definition of the individual probability vector and its relation to Nash welfare) is introduced in §2 but reused without re-statement in later sections; a short reminder or reference to the equation number would improve readability.
  2. [Figure 3] Figure 3 (computational results on real data): The y-axis scale for fairness improvement is not labeled consistently with the synthetic-data plots in Figure 2; this makes direct comparison difficult.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. Below we respond point-by-point to the major comments and indicate the revisions we will make to clarify the fairness-preservation arguments.

read point-by-point responses

  1. Referee: [§4.3, Theorem 4] §4.3, Theorem 4 (general bootstrapping): The reduction constructs a distribution as a convex combination of outputs from the max-coverage oracle. It is not immediate that this preserves the exact per-node lower bounds on matching probability that follow from the Edmonds-Gallai decomposition in the unweighted matching case; the marginal probabilities could be strictly weaker for structures without an analogous structure theorem (e.g., weighted 2-paths or 3-cycles). A concrete counter-example or explicit bound relating the oracle outputs to the original fairness measure is needed to support the 'analogous fairness properties' claim.

    Authors: We appreciate the referee drawing attention to the precise relationship between the oracle outputs and the per-node marginals. The bootstrapping construction in Theorem 4 selects the convex combination so that the expected coverage for every node is at least the minimum probability guaranteed by the fairness objective in the base (matching) case; this holds because each oracle call is made on a suitably modified instance that encodes the fairness lower bounds via the coverage requirement. For structures lacking an Edmonds-Gallai-type theorem the term 'analogous' is intended to mean that the resulting distribution satisfies the same qualitative individual-fairness guarantees (every node has positive probability of being covered, and the distribution maximizes a fairness objective subject to those guarantees) rather than numerically identical bounds. To remove any ambiguity we will add an explicit lemma (and short proof) that derives a concrete lower bound on each marginal probability directly from the coverage value returned by the oracle. This lemma will be placed in the appendix and referenced from the statement of Theorem 4. revision: yes

  2. Referee: [§3.2, Algorithm 2] §3.2, Algorithm 2 (weighted 2-paths): The strongly polynomial algorithm is claimed to guarantee the same fairness properties as the matching case, yet the fairness objective is defined via probabilities over randomized outcomes. When edge weights are present, the notion of 'maximum cardinality' must be replaced by a weighted objective; it is unclear whether the individual probability lower bounds remain identical or are scaled by the weights, which would affect the Nash-welfare optimality statement.

    Authors: We agree that the interaction between edge weights and the probability bounds merits explicit clarification. In the proof of Algorithm 2 the fairness guarantee is defined solely on the indicator that a node is included in the chosen 2-path; the algorithm maintains an Edmonds-Gallai-style decomposition on the underlying graph and then randomizes uniformly over a polynomial-size set of maximum-weight 2-path covers. Because the randomization is performed after the maximum-weight structures have been identified, the per-node inclusion probabilities are independent of the particular weight values and coincide exactly with the bounds obtained in the unweighted matching case. Consequently the Nash social-welfare optimality statement continues to hold with respect to these (unscaled) probabilities. We will revise the paragraph following Algorithm 2 to state this invariance explicitly and add a one-sentence justification in the proof sketch. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation builds on external Edmonds-Gallai theorem via independent reduction

full rationale

The paper's central claims rest on the external Roth-Sönmez-Unver application of the Edmonds-Gallai structure theorem to obtain fairness bounds for matchings, then extend this via a general polynomial-time bootstrapping reduction that invokes any black-box max-coverage oracle for allowed structures (matching, 2-paths, or longer cycles/paths). This reduction is presented as a self-contained algorithmic construction that produces a distribution over oracle outputs; it does not redefine fairness measures in terms of the outputs themselves, fit parameters to target quantities, or rely on load-bearing self-citations. The abstract and claims treat the oracle as an independent subroutine whose existence is assumed without embedding the target fairness properties into its definition. No quoted step reduces the new fairness guarantees to a renaming, ansatz, or fitted input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based on the abstract alone, the central claims rest on standard results from matching theory (Edmonds-Gallai structure theorem) and the existence of an optimization oracle for the chosen exchange structures; no free parameters, ad-hoc axioms, or invented entities are visible.

axioms (2)
  • standard math Edmonds-Gallai structure theorem applies to the underlying non-bipartite matching graphs in kidney exchange
    Invoked in the abstract as the foundation for the randomized fairness algorithm from prior work.
  • domain assumption An optimization subroutine exists for the allowed exchange structures (matching, paths, cycles)
    The general bootstrapping result explicitly conditions on calling such a subroutine a polynomial number of times.

pith-pipeline@v0.9.0 · 5748 in / 1374 out tokens · 32608 ms · 2026-05-20T03:16:22.642558+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    Clearing algorithms for barter ex- change markets: Enabling nationwide kidney exchanges.ACM Transactions on Economics and Computation, 2007

    David J Abraham, Avrim Blum, and Tuomas Sandholm. Clearing algorithms for barter ex- change markets: Enabling nationwide kidney exchanges.ACM Transactions on Economics and Computation, 2007

    work page 2007

  2. [2]

    Hall’s theorem for hypergraphs.Journal of Graph Theory, 35(2):83–88, 2000

    Ron Aharoni and Penny Haxell. Hall’s theorem for hypergraphs.Journal of Graph Theory, 35(2):83–88, 2000

    work page 2000

  3. [3]

    Pearson, 1993

    Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin.Network Flows: Theory, Algo- rithms, and Applications. Pearson, 1993

    work page 1993

  4. [4]

    Topics in relaxation and ellipsoidal methods

    M Akg¨ ul. Topics in relaxation and ellipsoidal methods. 1983

    work page 1983

  5. [5]

    Roth, Tayfun S¨ onmez, and M

    Ross Anderson, Itai Ashlagi, David Gamarnik, Michael Rees, Alvin E. Roth, Tayfun S¨ onmez, and M. Utku ¨Unver. Kidney exchange and the alliance for paired donation: Operations research changes the way kidneys are transplanted.Interfaces, 45(1):26–42, February 2015

    work page 2015

  6. [6]

    Ross Anderson, Itai Ashlagi, David Gamarnik, and Alvin E. Roth. Finding long chains in kidney exchange using the traveling salesman problem.Proceedings of the National Academy of Sciences, 112(3):663–668, January 2015

    work page 2015

  7. [7]

    Private communication, 2025

    Itai Ashlagi. Private communication, 2025

    work page 2025

  8. [8]

    Individual rationality and participation in large scale, multi- hospital kidney exchange

    Itai Ashlagi and Alvin Roth. Individual rationality and participation in large scale, multi- hospital kidney exchange. InProceedings of the 12th ACM conference on Electronic commerce, EC ’11, page 321–322, New York, NY, USA, 2011

    work page 2011

  9. [9]

    Itai Ashlagi and Alvin E. Roth. Kidney exchange: An operations perspective.Management Science, 67(9):5455–5478, September 2021

    work page 2021

  10. [10]

    Kash, and Ariel D

    Itai Ashlagi, Felix Fischer, Ian A. Kash, and Ariel D. Procaccia. Mix and match: A strate- gyproof mechanism for multi-hospital kidney exchange.Games and Economic Behavior, 91: 284–296, May 2015

    work page 2015

  11. [11]

    Manlove, and Romeo Rizzi

    P’eter Bir´ o, David F. Manlove, and Romeo Rizzi. Maximum weight cycle packing in directed graphs, with application to kidney exchange programs.Discrete Mathematics, Algorithms and Applications, 01(04):499–517, December 2009

    work page 2009

  12. [12]

    Random matching under dichotomous preferences

    Anna Bogomolnaia and Herv’e Moulin. Random matching under dichotomous preferences. Econometrica, 72(1):257–279, 2004

    work page 2004

  13. [13]

    Brewster, Pavol Hell, Sarah H

    Richard C. Brewster, Pavol Hell, Sarah H. Pantel, Romeo Rizzi, and Anders Yeo. Packing paths in digraphs.Journal of Graph Theory, 44(2):81–94, 2003

    work page 2003

  14. [14]

    Fair integer programming under dichotomous and cardinal preferences.European Journal of Operational Research, 320 (3):465–478, February 2025

    Tom Demeulemeester, Dries Goossens, Ben Hermans, and Roel Leus. Fair integer programming under dichotomous and cardinal preferences.European Journal of Operational Research, 320 (3):465–478, February 2025. 24

    work page 2025

  15. [15]

    Dickerson, A

    J. Dickerson, A. Procaccia, and T. Sandholm. Price of fairness in kidney exchange.Trans- plantation, 98:815, July 2014

    work page 2014

  16. [16]

    A concept of egalitarianism under participation constraints

    Bhaskar Dutta and Debraj Ray. A concept of egalitarianism under participation constraints. Econometrica, 57(3):615–635, 1989

    work page 1989

  17. [17]

    Paths, trees, and flowers.Canadian Journal of Mathematics, 17:449–467, 1965

    Jack Edmonds. Paths, trees, and flowers.Canadian Journal of Mathematics, 17:449–467, 1965

    work page 1965

  18. [18]

    Individ- ual fairness in kidney exchange programs.Proceedings of the AAAI Conference on Artificial Intelligence, 35(1313):11496–11505, May 2021

    Golnoosh Farnadi, William St-Arnaud, Behrouz Babaki, and Margarida Carvalho. Individ- ual fairness in kidney exchange programs.Proceedings of the AAAI Conference on Artificial Intelligence, 35(1313):11496–11505, May 2021

    work page 2021

  19. [19]

    Procaccia

    Bailey Flanigan, Paul G¨ olz, Anupam Gupta, Brett Hennig, and Ariel D. Procaccia. Fair algorithms for selecting citizens’ assemblies.Nature, 596(7873):548–552, August 2021

    work page 2021

  20. [20]

    Fair-by-design matching.Data Mining and Knowledge Discovery, 34(5):1291–1335, September 2020

    David Garc´ ıa-Soriano and Francesco Bonchi. Fair-by-design matching.Data Mining and Knowledge Discovery, 34(5):1291–1335, September 2020

    work page 2020

  21. [21]

    Martin Gr¨ otschel, L´ aszl´ o Lov´ asz, and Alexander Schrijver.Geometric algorithms and combi- natorial optimization, volume 2. 2012

    work page 2012

  22. [22]

    Jan Karel Lenstra and David B. Shmoys. Elements of scheduling.https:// elementsofscheduling.nl, 2021

    work page 2021

  23. [23]

    Egalitarian pairwise kidney exchange: fast algorithms vialinear programming and parametric flow

    Jian Li, Yicheng Liu, Lingxiao Huang, and Pingzhong Tang. Egalitarian pairwise kidney exchange: fast algorithms vialinear programming and parametric flow. InProceedings of the 2014 international conference on Autonomous agents and multi-agent systems, AAMAS ’14, pages 445–452, Richland, SC, May 2014

    work page 2014

  24. [24]

    Elsevier, 1986

    Laszlo Lovasz and Michael Plummer.Matching Theory. Elsevier, 1986

    work page 1986

  25. [25]

    Balancing lexicographic fairness and a utilitarian ob- jective with application to kidney exchange.Proceedings of the AAAI Conference on Artificial Intelligence, 32(11), April 2018

    Duncan McElfresh and John Dickerson. Balancing lexicographic fairness and a utilitarian ob- jective with application to kidney exchange.Proceedings of the AAAI Conference on Artificial Intelligence, 32(11), April 2018

    work page 2018

  26. [26]

    OPTN policies.https://optn.transplant.hrsa.gov/media/eavh5bf3/optn_ policies.pdf, 2025

    OPTN. OPTN policies.https://optn.transplant.hrsa.gov/media/eavh5bf3/optn_ policies.pdf, 2025

    work page 2025

  27. [27]

    Plotkin, David B

    Serge A. Plotkin, David B. Shmoys, and ´Eva Tardos. Fast approximation algorithms for fractional packing and covering problems.Mathematics of Operations Research, 20(2):257– 301, 1995

    work page 1995

  28. [28]

    Roth, Tayfun S¨ onmez, and M

    Alvin E. Roth, Tayfun S¨ onmez, and M. Utku¨Unver. A kidney exchange clearinghouse in new england.American Economic Review, 95(2):376–380, May 2005

    work page 2005

  29. [29]

    Roth, Tayfun S¨ onmez, and M

    Alvin E. Roth, Tayfun S¨ onmez, and M. Utku ¨Unver. Pairwise kidney exchange.Journal of Economic Theory, 125(2):151–188, December 2005

    work page 2005

  30. [30]

    United Network for Organ Sharing.https://unos.org/, 2025

    UNOS. United Network for Organ Sharing.https://unos.org/, 2025. 25

    work page 2025