A Learning-Based Framework for Fair and Scalable Solution Generation in Kidney Exchange Problems
Authors: William St-Arnaud
Margarida Carvalho
Golnoosh Farnadi
Venue: Accepted by TMLR ()

Abstract: Reinforcement learning and Generative Flow Networks, known as GFlowNets, present an exciting possibility for neural networks to model distributions across various data structures. In this paper, we broaden their applicability to data structures consisting of optimal solutions for a combinatorial problem. Concretely, we propose using Q-learning and various policy gradient methods, as well as GFlowNets to learn the distribution of optimal solutions for kidney exchange problems (KEPs). This could provide a useful tool for decision-making authorities, policymakers and clinicians, as it offers them multiple optimal or near-optimal solutions, and provides a complementary landscape to their traditional integer programming-based toolbox for promoting fairness and societal benefits. Our reinforcement learning-based framework trained on KEP instances provides an effective addition to computationally expensive exact approaches, notably mixed-integer programming. Our experiments thoroughly evaluate the quality of the solution sets sampled from the trained neural networks in terms of optimality, their scalability when dealing with real-sized KEP instances, and their capability to generate a diverse pool of solutions. We also cover the use of their efficient solution generation capabilities to improve fairness and simulate the evolution of the KEP pool in a dynamic setting. Our contribution is thus: 1) methodological, as it introduces a novel setting for reinforcement learning in addition to GFlowNets, 2) implementational, as it delves beyond the theory and details how to use conditional information, and 3) of practical significance, as it considers a specific combinatorial problem in the healthcare domain.

Published in Transactions on Machine Learning Research (04/2025)
A Learning-Based Framework for Fair and Scalable Solution Generation in Kidney Exchange Problems
William St-Arnaud
Université de Montréal
Mila
Margarida Carvalho
carvalho@iro. hww.:/oo@oiiommmmmrrll..oo
Université de Montréal Mila
Golnoosh Farnadi
farnadig@miid quebee
McGill University
Mila
Reviewed on OpenReview: https: // opwrreveew.eeee...oeeeeee net/ forum? IdzmQoF86Y
Abstract
Reinforcement learning and Generative Flow Networks, known as GFlowNets, present an exciting possibility for neural networks to model distributions across various data struc- tures. In this paper, we broaden their applicability to data structures consisting of opti- mal solutions for a combinatorial problem. Concretely, we propose using Q-learning and various policy gradient methods, as well GFlowNets to learn the distribution of opti- mal solutions for kidney exchange problems (KEPs). This could provide useful tool for decision-making authorilies, policymakers and clinicians, as il offers them multiple opti- mal or near-optimal solutions, and provides a complementary landscape to their traditional integer programming- based toolbox for promoting fairness and societal benefits. Our rein- forcement learning- baseed framework trained on KEP instances provides an effective addition to computationally expensive exact approaches, notably mixed-integer programming. Our experiments thoroughly evaluate the quality of the solution sets sampled from the trained neural networks in terms of optimality, their scalability when dealing with real-sized KEP instances, and their capability to generate diverse pool of solutions. We also cover the use of their efficient solution generation capabilities to improve fairness and simulate the evolution of the KEP pool in a dynamic setting. Our contribution is thus: 1) methodologi- cal, as it introduces a novel setting for reinforcement learning in addition to GFlowNets, 2) implementational, as it delves beyond the theory and details how to use conditional infor- mation, and 3) of practical significance, as considers specific combinatorial problem in the healtheare domain.
1 Introduction
Resource allocation problems ubiquitous in everyday lives they find various applications in sectors such business, engineering, robotics, and healthcare (Cormen et al., 2022 Bin-Obaid & Trafalis 2020 Munguía-López & Concc-Ortegg 2021h. Many of these problems take the form of combinatorial optimization problems due to the indivisibility of resources, which makes them hard to solve. One large class of such problems consists of matching problems. In the healthcare sector, kidney exchange problems (KEPs) are well-known matching problems involving patients needing a kidncy transplant and donors. The goal is find an exchange plan (defined in section D which determines the patients receiving transplant. The objective driving the search for exchange plan can vary but often involves the maximization of some

---

Published in Transactions on Machine Learning Research (04/2025)
objective function taking into account the number of matched patients (i.e., receiving a transplant) among other criteria.
Undoubtedly, KEPs correspond to an important subset of resource allocation problems in combinatorial optimization. In this context, we identify three key challenges. First, the exchange plans that are selected can sometimes fail for logistical reasons and due to donor or patient drop-off, e.g. a patient's 's health status renders them unable to perform surgery. Second, KEPs often have multiple optimal exchange plans, and relying exact solvers may not ensure all patients have fair chance of receiving transplant. Third, simulating KEPs in the long term is computationally expensive, notably, because each round of KEP corresponds to hard combinatorial problem. Because current KEPs use ad-hoc or empirically-based objectives to guide their matching policy, such exchange systems have yet to fully demonstrate the long-term impact of derived policies on the patient pool. For example, it has been observed in certain KEPs that there is an accumulation of certain subgroups of patients in the pool, based on bloodtype (Canadian Institute for Health Information 2016
Based on the first two aforementioned challenges, efficiently computing multiple exchange plans would em- power pecision-makers with the ability (i) to dispose of alternative exchange plans in situations of unexpected infeasibility, and (ti) to draw exchange plans at random according to a fixed policy and guarantee proba- bilities to patients of receiving a transplant, akin to live lotteries for citizens' assemblies (Flanigan et al. 2021p. With respect to the third challenge posed above, the efficient simulation of matching policies would (bii) afford decision-makers the ability to discover long-term policy impacts and mitigate potential negative effects. Because of the delicate nature of allocating kidneys to patients, the ultimate decision recision-making power lies in the hands of policy-makers and clinicians. They stand to gain greater ad adantagee from diverse array of exchange plans rather than relying on singular one.
Because KEPs are usually formulated as mixed-integer programs, distributions of solutions can be generated through column generation (St-Arnaud et al., 2023). For large kidney exchange pools, the mixed-integer formulation can become impractical to describe, and the time to compute one solution, not to mention a distribut of solutions, can be prohibitively large. To complement these approaches, reinforcement learning (RL) methods can learn policies that build exchange plans sequentially. The learned models can then be used to generate solutions. Because of the need to scale to large kidney exchange pools and to model long- term behaviour of policies dictating the selection of exchange plans, it is important to better understand the pros and cons of using learning-base based methods to derive KEP policies. In this work, we explore the possibility of efficiently generating multiple optimal or near-optimal solutions (exchange plans) by learning policies to generate exchange plans. This fits neatly into the framework of reinforcement learning through policy optimization methods. These include policy gradient, promiximal policy optimization (PPO), and Q-learning, By deriving the policy directly (and indirectly through Q values in Q-learning), the possibility of sampling multiple high-reward solutions arises. More recently, generative flow networks (GFlowNets). forming new class of algorithms to sample solutions proportional to some reward (much like PPO), have shown promising results (Bengio et al. 2023 2021). Our first contribution is the application of these learning- based methods to KEPs with the goal of using an extended set of solutions to form probability distributions over exchange plans. Second, to fit into the reinforcement learning and GFlowNet framework, we formalize the states, actions, trajectories, episodes and reward function that define the sampling distribution to be learned. Morcover, we condition on the input KEP graph as it allows us model a rich family of distributions from which we can sample. Third, we experimentally demonstrate the ability of our learning procedure to efficiently output good-quality (near-optimal) distributions by comparing against baselines, including the selection of an optimal solution. In addition, we analyze the capability of the learning phase to generalize from smaller KEP instances (i.e. training set) to larger instances (i.e. test set) when computing one or multiple exchange plans.
The promising experimental results validating the use of RL and GFlowNeets enable us to advance to our fourth contribution: showeasing the value of having an efficient sampler downstream of the training phase. To this end, (1) we provide effective sampling mechanism through which decision-makers can report individual matching probabilities to patients in the KEP pool, and (2) we describe the use of our approach
1 'Qur code will be made available upon publication.
2

---

Published in Transactions on Machine Learning Research (04/2025)
within the simulation of the evolution of the KEP pool over time. In (1), by using exchange plans generated through policy learning, we demonstrate how to improve individual fairness (TF) (i.e. more equal probability of receiving a transplant over patients) measures by computing a diverse set of (near-)optimal solutions. We compare against an optimal (but not scalable) exact mixed-integer programming approach. In (2), we use our efficient samplers and we show that their use in a dynamic simulation of the kidney exchange system allows to approximate the expected number of transplants over multiple matching rounds. These two experiments reflect how the work developed in this article can empower decision-makers to assess fairness thanks to the availability of multiple optimal solutions and to better understand the long-term impact of their choice of matching policy on patient welfare.
In section 2 of this article, we introduce key definitions and concepts relating to KEPs. We follow with a literature review of solution approaches and fairness for KEPs, machine learning in combinatorial optimiza- tion and reinforcement learning approaches for sampling solutions. In sections I| and we detail all the necessary concepts for learning-basee methods appliod to KEPs. Section
G contains the experimental setup we introduce research questions and we detail the results by providing a thorough analysis. Finally, section g contains our concluding remarks and we highlight future rescarch directions.
for our research questions. In sections i and g
2 Kidney exchange
With the purpose of addressing the scarcity of kidneys on deceased donor waiting lists, Rapaport (1966 put forward the notion of living donor exchanges. This led to what is now known as kidney exchange (Roth
et al. 2004). a barter market. that has been implemented in several countries, namely, in Europe Biró et al.
2021
Canada (Malik& & Cole 2014) and South Korea (Park et al., 2004).
In a kidney exchange system, incompatible patient-donor pairs are registered, forming a KEP pool. These pairs are then matched with other incompatible patient-donor pairs to exchange donors, resulting in com- patíble transplants to be performed. Matching between pairs can be done either pairwise involve multiple pairs part of a cycle. Additionally, non-directed donors can also register in the system, without being attached to a specific patient, and allow exchanges to initiate on them, thereby leading to chains. Indeed, a KEP can be naturally modeled as a graph G = (V, A); see Figure D In Figure | the set P of patient-donor pairs is represented by vertices and an arc (u, u) between vertices u and v corresponds to compatibility between the donor of pair u and the patient of pair v. The set. in Figure [ consists of non-directed donors, here the grey-coloured vertices. The vertex set of the graph is equal the disjoin union of P and N, i.e. PUN N with P n N = 0. Notice that there are no incoming ares to vertex eg. In this example, we can observe cycles involving vertices from P, e.g. (12, U7, u1), and chains starting in vertices from N and extended with vertices from P, e.g. (vg, U3, U2, U2, 1s) where (Us, U3, 02) is subchain that is also a valid chain. We use the general term erchange to refer to a cycle or chain. Consequently, solving a KEP entails determining an exchange plan, i.c., a set of disjoint exchanges (matchings) as only one kidney can be transplanted from a donor. In addition, for logistic reasons, the list of allowed exchange plans is limited to those including cycles and chains of below a predetermined length. This constraint is behind the complexity of solving KEPs, as they would otherwise be (antamount assignment problems. In Figure an exchange plan, where the maximum predetermined exchange length is three, takes the form of a subgraph of the original KEP graph (see subgraph on the right in the figure). The task of finding an exchange plan is usually approached through the use of solvers optimizing an objective, such as the maximization of the total number of transplants, the so-called utilitarian objective. Thus, in kidney exchange systems, at each predefined interval (e.g., every four months), a KEP is solved to find an exchange plan among the currently registered patients and donors that optimizes the objective function. This over-time sotting is referred as dynamic KEP in the remainder of the paper.
3 Literature review
Solving KEPs. In its most basic form, KEPs entail optimizing the utilitarian objective, which already NP-hard Abbrhhmm et al. 2007). The simplest mixed-integer program (MTP) to describe KEP is the
3

---

Published in Transactions on Machine Learning Research (04/2025)
Set of incompatible pairs ,,,,
P = {vi, U2, ................................
P2
Exchange plan
Set of non don-ddrected donors
N {
BY
14
Figure 1: On the left, example of KEP graph. On the right, example of feasible exchange plan for predetermined maximum exchange length of three.
cycle formulation Abraham et al., 2007 Roth et al. 2007). Other MIPs of a more compact size have been proposed, for example, by Constantino et al. (2013) and Dickerson et al. 2016 MIPs are widely used since they can be fed directly to off-the-shelf solvers. While the usual goal in KEPs is to identify single optimal exchange plan according to some pre-agreed objective, other works have proposed the determination of a probability distribution over exchange plans, accounting for fairness during selection. For instance, Farnadi )021) enumerate all optimal solutions for the utilitarian objective in order to generate probability distribution across them from which to sample exchange plans. This approach is better known as individual fairness, and it only scales for small instances with at most 50 pairs. Next, we discuss fairness for KEPs in more detail.
et al.
Fairness for KEPs. It was observed by Dickerson et al. (204 that solely maximizing the mumber of transplants in KEPs can result unfair treatment of specific patient groups that accumulate in the KEP pool over time (c.f. RQ4 in section 8. For this reason, there has been substantial research on group fairness approaches for selecting
exchange plan (e.g., Dickerson al. (014]); Dickerson & Sandholm (2014);
Gao 2019 Recent work has introduced a distinet fairness concept individual fairness- which focuses ensuring fairness at the level of individual patients rather than patient groups. This idea involves offering decision-makers multiple feasible solutions, moving away from the traditional focus on a single solution
returned by solvers (Farnadi et al.] 2021 St-Arnaud et al. 2023 Demeulemeester et al. 2025) St-Arnaud
et al. 2023) obtain probability distributions through the enumeration of solutions in the support of multi- objective KEPs composed of utilitarian and fairness components. The drawback of their methodology is that the choice of specific fairness objective predetermined before solving the optimization problem. This restricts the solution landscape to those that align with the chosen objective, potentially excluding other fair or efficient solutions that policy-makers might wish to explore.
Machine learning and combinatorial optimization. Across the literature on combinatorial optimiza- tion problems (which includes MIPs), a commonly found solution approach relevant to our work involves the use of machine learning models and architectures to return high quality solutions. This method belongs subtype of end-to-end constrained optimization known in the literature as predicting solutions (Kotary et al. 2021). Specifically, Lagrange multipliers have been used in learning objectives to enforce fcasibility of
constrained problems (Hopfeild & Tank 1985). while Detassis et al. (2021 introduced an iterative algorithm that uses combinatorial optimization solver to adjust solutions returned by neural network in order to maintain feasibility. Vinyals et al. (2015) introduced pointer networks to solve the travelling-saleenee (TSP) and convex-hull problems, but their method applies to instances where all permutations of a solution are feasible; this the case for KEP cycles, but not for chains. RI. methods such as the actor-critic framework have boen used to solve combinatorial optimization problems by relaxing the optimality criterion of generated solutions (Bello et al. 2016)). More recent advances in Velickovic et al. (2018) use graph attention networks with REINFORCE (Williams 1992) to improve upon previous results tasks such as TSPs.
A major driving factor behind this line of rescarch comes from the inherent difficulty in solving some large combinatorial optimization problems exactly; in some well-known cases, an approximate solution that is feasible is satisfying (e.g. chess, TSP), thus further justifying the use of learning- based methods. Moreover, when combinatorial optimization problems involve uncertainty, is typically intractable to solve a problem exactly and is then natural to use learning- methods. Other learning based methods are available,
such ML-auggented constrained oplimization and predicl-anddoplimizz (Kotary al., 2021 The former
4

---

Published in Transactions on Machine Learning Research (04/2025)
guide combinatorial solver during the solution phase, while the latter learns to predict a proxy model (objective and/or constraints) that is fed to combinatorial optimization solver, which returns a solution that is ideally close to target solution (Ferber et al.) 2020 Subin-Frankower the combinatorial formulation of the problem or the time to recover recover a solution is prohibitively large, these methods can fail. While predicting solutions has shown promise in cerlain tasks such as portfolio optimization and mixed-integer lincar programming (Wilder et al. 2019 Ferber et al. 20200, we observe that these learning- based methods, much like MIP, are most commonly used for selecting one solution, in contrast to our goal of producing a full distribution of solutions. The main difficulty with the aforementioned methods emerges out of the training procedure, but once model is learned, we can often get an efficient sampler that allows for fast solution generation. Based on this idea, we describe in the paragraph below how we seek to lake advantage of this polentially highly efficient solution generation to address fairness concerns raised earlier in relation to MIPs.
et al. 2024h. Much like MIP, if
Solution sampling in RL. In this article, we seek to investigate learning methods that can sample exchange plans efficiently. We are motivated by the need to find distributions of exchange plans exhibiting certain properties, as it is the general case for fair assignment problems involving the allocation of critical resources. Our work also driven by the fact that such mechanisms can allow the efficient simulation of multiple matching rounds (dynamic KEP). The key aspect that differentiates our line of inquiry from prior rescarch on KEPs is the learning aspect involved, where one is looking to learn distribution of optimal (or near-oplimal) solutions, according to a given objective. For this reason, we focus on policy gradient and flow- based methods (Suttnn et al. 1999: Bengio et al., 2023), and extend their application to the setting of kidney exchanges. These approaches are well suited for application on discrete structures such as graphs as it is possible to enforce constraints within the set of possible actions. In addition, GFlowNets offer in some cases an improvement over policy-gradient modh and Monte Carlo Markov chain (MCMC) sampling, because of their ability to model the reward directly and learn modes of the distribution. Algorithms derived from both policy gradient and generative flow networks have previously been successfully used in drug discovery (Bengio et al. 2021 Angermueller et al.) 2019h. The setting in drug discovery is similar to ours in the sense that it sooks to output samples that bear a particular graph structure (drug-like molecule). Yct, it is also diffcrent,
since the output in our problem is conditional on an initial KEP graph (see section 5 i.e. the action and state spaces are countably infinite (see section
4 Searning-based methods
We proceed to define the usual concepts of RL such as state, action and reward, in the setting of static KEPs. We will later see in section E the process by which we learn static KEP policies and how these policies are deployed over episodes consisting of multiple matching rounds with uncertainty over the arrival and departure of patient-donor pairs.
Preliminarics. As argued in the previous sections, learning-based methods (e.g. policy gradient and GFlowNets) seem to offer an adequate approach for learning probability distributions aimed to address fair assignment problems, namely, KEPs. In our application of learning methods to KEPs, we propose to sequentially build exchange plans by adding cycles and chains until a maximal exchange plan is reached. Thus, given a set of disjoint cycles and chains (hence a KEP subgraph, or exchange plan), the policy to be learned will assign probabilities to the remaining feasible (i.e., disjoint) cycles and chains. A cycle or chain selected by drawing from the constructed distribution. Note that Q-lcarning does not directly offer probability distribution, but we can recover one by making use of e-greedy selection mechanism. This approach involves either selecting uniformly at random between feasible cycle chain, choosing the one with the maximum value (i.c. maximum Q-value).
In the process of building an exchange plan, two scenarios are possible: the current exchange plan is complete (i.e., maximal) or not yet. In the case where it is not yet maximal, we augment it with additional cycles and chains. In the case where is maximal, the only available option is to select the exchange plan and proceed to the next matching round. Because of these two possible scenarios, we will define two types of states, internal and external states.
5

---

Published in Transactions on Machine Learning Research (04/2025)
Definition 4.1 (State). General states, denoted with the variable 8, will consist of a tuple (G, H), where G is KEP graph and H is an exchange plan, i.e. KEP subgraph of G consisting of disjoint cycles and chains. The set of parent and children of state s will be denoted using par(s) and child(s), respectively. An internal state s = (G, H) is a state such that for all s' E child(s), there exists H' such that s' = (G, H') and H is a subgraph of H'. An external state (G, H) is a state such that for all s' = (G', H)) E child(s), we have H' = 0. We denote the set of external states as X.
In the case of an internal state, an (internal) action (sce Definition 1.2 below) will correspond to cycles and chains that can be included lo augment the exchange plan in the internal state (i.e., its second component). Specifically, (internal) actions are ares between an internal state and a state s', such that s's exchange plan is a subgraph of s'ss exchange plan. When convenient, we will denote such ares as (s, s').)). In the case of an external state, an (external) action corresponds to the selection of the exchange plan Specifically, (external) actions are ares between two states and s', such that s's exchange plan is D. We can also think of internal states as part of the matching- building process in a specific matching round, while external states correspond to the end of a matching round.
matching.
matcchigg-uildding
Definition 4.2 (Action). A general action is arc (s) between two states. It is an internal action if = (G, H) and s' = H") implies that H is a subgraph of H², It is an external action if s' = (G', for some KEP graph G".
Definition 4.3 (Transition function). The transition function T is implicitly defined as (8, + s' with probability 1 for = ss, when s is an internal state. When s = (G, H) is an external state, we have a random variable Mc such that s' = (G', 0) ~ Mc. where G' is obtained through the graph G' after the arrival and departure of patient-donor pairs and non-directed donors in the pool using a Markovian process M.
The transition function corresponds to adding cycles and chains for internal states and transitioning to a new KEP graph after a matching round for external states.
Definition 4.4 (Reward). At each state, the reward for s= (G, H) and a ((G, H), (G', H²) is given as ((s,a) = = ((P())) for a maximal matching H' (see Definition 4.5h and 0 otherwise, where P(H') is the vertex
set of H' and it corresponds to the set of matched patients.
Using this representation of states and actions, it is possible to form a directed acyelic graph (DAG). We can compare the introduced definitions with Figure _ The DAG starts with an empty exchange plan and sequentially adds cycles or chains. The external actions are represented using the blue arrows. Because of space constraints we only include one external action, the end of the trajectory, in Figure ! Once a maximal exchange plan is encountered, transitions to a new KEP graph, modelled as a Markovian process M (see Simulator in section D for more details). The red box encloses matching round (see section for more details).
To suit the use of machine learning models, the states involved in our experiments are, in reality, computed from vertex embeddings of exchange plans. That is, given vertex embeddings (2,) in a vector space Rd we compute the averages [v( respectively
[V(H)) 1 E.V( x; and [((m)) =i=1 x; to obtain the embeddings of G and H,
g After the concatenation of these two vectors, we obtain the embedding of the state (G, H) (i.c. the state corresponding to the exchange plan H). This map from exchange plan (i.c. graph) to its corresponding stale will be denoted by a.
Definition 4.5 (Trajectory). A (complete) trajectory is a sequence T = -80 ,8....,8)) of states (here, n E N is an arbitrary length) that satisfies 8; child(s;-1) for i i= 1,...,m.. n. Whenever 8n X, we will refer to this (complete) trajectory as maximal trajectory, or maximal matching.
In simple words, trajectory corresponds to sequential selection of exchanges for various KEP graphs (see Figure 2 The set of complete trajectories is denoted T and the set of trajectories following from the state is denoted T.,
2To prevent confusion, we reserve the use of the term "graph" solely for KEP graphs. The notation V(G) and V(H) interpreted as the vertex sets of graphs G and H.
6

---

Published in Transactions on Machine Learning Research (04/2025)
Parameterization. Based the terminology introduced above, describe how to model probability distributions over states, partial and complete trajectories.
Definition 4.6 (Forward and backward flow). The forward flow, denoted Pp. is a function (s, + R such that equation 1 is satisfied, where 0 E R is a parameter vector. Similarly, the backward flow is function (s, 8'), 0 + R+ such that equation 2 is satisfied. By slightly abusing notation and dropping the dependence on 0, we can use equation B to extend forward and backward flows to complete trajectories
Σ
P=(s'|s,0)= =1
(1)
(cchild(s)
Pa(s|s' ,0) sEpar(s")
Σ
(2)
Pp(T] (0) = Z
II Pr(s: 81-1)
PB(T(Sp) = R(s,) a
II
P (ss
(3)
Definition 4.7 (Initial flow). The initial flow a function 8, + R4,, where 8 is an internal stale.
The parameters 0 that are involved Pp. PB and Z are often omitted for simplicity. For example, in equa- tion G we abuse notation and we drop the dependence of Pp, Pg and Z on the parameters unless necessary to disambiguale between two different. 0's. In order unily the notation belween RL and GelowNets, we make the identification in equation ! The reward R is a function of the external states E X and was
described in detail in Definition 4.4 (SCO caption of Figure 2.. We present the definition of the Q function, well as the detailed balance equation of the forward and backward probability transitions for GFlowNets 1.9 In equation
in equation G of Definition
4.9 we omit the dependency of R on the act since the end of an episode is an external state and thus, its action is trivial.
po(s'(s) = po(a | () Pp(s') 8),
(4)
Definition 4.8 (Q function). The Q function is a function s, + R4. We make use of the identification found in equation where we abuse notation a drop the dependence on the parameters.
Q(s (ss+s))= :(s===(ssa==--
(5)
Definition 4.9 (Trajectory balance). The trajectory balance equation for PF and P3 given a complete trajectory as follows:
Pr(T 80) = 2I[:= Pr(si | 8;-1) PB(T sn) R(s,) IT PB(s.-1 (s)
(6)
If O over all trajectories, the trajectory balance loss indicates that the networks Pp and P3 correspond to flow (see Bengio el al. 2023 By sampling set of trajectories, we oplimize an estimator for the true loss. With the introduction of various definitions and identifications between RL and GFlowNet notation in mind, we will see in the next section how to learn policies over sequences of matching rounds (i.e. episodes). Q-learning, policy gradient, PPO, and GFlowNets each lead to their own loss that will be optimized over batches of episodes using an exploratory policy.
5 Generating episodes
In order to generate data over which the learning based methods can fine-tune their parameters, we introduce Markovian process M that generates KEP pools.

---

Published in Transactions on Machine Learning Research (04/2025)
Definition 5.1. Let L N be arbitrary. An episode of L matching rounds consists of a sequence (Ti) of trajectories Ti starting in an internal state so, = (G,, 0) and terminating in an external state 8n; E X. We make use of the notations and sf for the artificial states corresponding to the start and final states of an episode. These are special purpose states that are neither internal nor external states, and that model the beginning and end of an episode. Furthermore, when the trajectories T for l...., are maximal, we call the episode static-matching episode.
Each trajectory forming an episode corresponds to matching round. The transition from trajectory r 7+11 (i.e. from Sn, to Su.+1) indicates the end of matching round and the start of new one. In our scenario, restrict episodes to static-matching episodes and the number of (maximal) trajectories contained in each episode to fixed number L. Each episode has finite length and corresponds to a sequence of maximal matchings. In Figure 2 we can observe part of a static-matching episode. The matching round is contained
inside the red box and we can see the previous and following internal states (G", H') and (G", 0), respectively. The choice of static-matching episodes is motivated by our goal to obtaín near-optimal policies for traditional KEPs over multiple matching rounds. Therefore, the exchange plan selected at round needs to affect the matching round time i I, while the decision needs be restricted to the current matching round. True dynamic KEP policies, where obtaín near-optimal solutions for non-myopic setting, are reserved for future work and various approaches would be conceivable; nevertheloss, learning- based approaches seem very well suited for this setting (see section 1 Using the notions introduced in section the policies learned over episodes are dependent on parameter 0. In the particular case of GFlowNets, the literature refers to this kind of learned GelowNets as conditional GFlowNets (Bengio ct al. 2023

---

Published in Transactions on Machine Learning Research (04/2025)
Subgraphs
#1, (G.fh)
Hj ((1), #2: us ((m, ez), (rz 152, (rs.
Hg (fr 18h ([ns. ma)) If" - (0.0)
P3
R(ag,) 4
(% 28 [0r ogl (ry. mi))
(G, H. U H6)
PV
%
mi (u-l(
F2
50,12
(G (1h Ha) U Hl,, II)
P2
= [G, 8
Legend
Selected in exchange plan
F2
Selected in exchange plan
New patient-donne pair
New
Internal action
External action / arrival of paizs
F2
Selected teajectory matching round
NDD matched and matched
F2
Figure 2: Example of matching round. We start from the initial state represented with a KEP graph with an empty matching. At every step, we add cycles and chains to the exchange plan (red modes/ares until we reach an external state (i.e. maximal matching). This external state transitions graph for the next matching round by following the markovian process M (blue curved arrow only one is depicted due to space constraints). The green path corresponds to the trajectory for this matching round, with multiple trajectories forming episodes.
new initial KEP

---

Published in Transactions on Machine Learning Research (04/2025)
Definition 5.2 (Exploratory policy). An exploratory policy is policy with full support over domain ((T))= (T)) ~ M, E )- An exploratory policy over static-matching episodes is called static-
matching exploratory policy.
In the domain of the exploratory policy are trajectories forming episodes (Ti) of length L. We can then evaluate the loss for our learning based methods. Specifically, the GFlowNet loss L for an episode is given by equation 7 Similarly, we can also obtain an estimate of the gradient for policy gradient in equation and for the PPO loss (clipped with = 0.2) in equation
The parameter 0 corresponds soek to minimize the loss L. In the case of GFlowNets, obtaín flow loss since, if the loss is over all episodes (or trajectories), we have flow-matching condition called the trajectory balance equation (Malkin et al. 2022). This implies that Z, Pp and Pn form a flow. In practice, this loss will not be 0 and we will also not sum over all trajectories since there would be too many to compute. We will have to resort to sampling a subset of trajectorics using x.
all the parameters of neural architecture. For equations 7 and we
((o)) I ( (86-1) 2
I(0)
Σ log (Tu
(7)
R(s,) [ PB (B 1 8is
(Tu)aam
Vo lolog Pr(Sse ( + s1c)
(8)
Pp(Sie
8ig 8ic-1,0)
L(0) = E (Tu)am
Σ min
Q( - 8ic),
Pris
8ix 1, Bold)
(9)
Pr(Si
18
clip
(81)-1:0ta)) -,,, 11 Q(1 + six)
Pr(Bir
6
Experimental setup
We aim to validate our approach with empirical evaluations by addressing five core research questions for- mulated to demonstrate the capabilities of learning-based methods to iteratively build variely of exchange plans for KEPs. To provide comprehensive answers to these research questions, we first outline the experi- mental setup and we describe the KEP instances simulator.
Methods. We first define the different suites of experiments that performed. We evaluate generative flow networks (GFlowNet), Q-learning, policy gradient (Policy (aalieGt) and proximal policy gradient (ProximalPolicy Gradient)) We specify that the Q function minimizes the squared difference between both sides of the Bellman equation as the temporal difference learning (TD learning) loss. It is common in the GFlowNets literature to compare with methods such as ProximalPolicyGraadd Gradicntt and PolicyGradient and we defer this rich body of literature for examples. We evaluate learning-based methods on datasets of episodes sampled using our simulator: we simulate graphs using a Markovian process described below. The resulting static-matching cpisodes will allow us to model the evolution of the KEP pool over time exchange plans are selected at various rounds, by more closely filting the true distribution of possible graphs encountered over the full horizon (I. matching rounds).
In order to determine the learning- based methods allow us to sample solutions that are close to optimal, we first need to compare the quality of our returned solutions against other methods that are not learning baased We devise two heuristics to construct exchange plans. We will refer to the process of selecting sequentially disjoint exchanges uniformly random to form solution RandUniform. The selection of disjoint
We abuse notation and denote each method's loss and parameters as and 8, respectively.
10

---

Published in Transactions on Machine Learning Research (04/2025)
exchanges using greedy process (i.e. largest first) will be referred to as RandGreedy (ties are broken uniformly at random). We also use an exact MIP solver (Gurobi 10.0.2) to compute optimal solution in a single step to which we refer as OptMIP. Our mixed-integer implementation follows the hybrid position- indexed edge formulation found in Dickerson et al. 2016). We note that OptMIP will always return one solution our experiments, in contrast. to other sampling-basel methods. Thus, the averages reported in Tables are rather single values for OptMIP. The basclines will serve to highlight the quality of the returned solutions and situate the effectiveness of the proposed learning approach.
Simulator. We simulate KEP graphs using Markovian process. The simulator that is used in our experiments is base on the work of [Saidman et al. (2006). Over multiple rounds of arrival, the number of incompatible pains entering the pool is drawn from a Poisson distribution. For each of these pairs, the blood type of the patient and donor are drawn according to pre-defined probabilities. Compatibility ares are then added between the newly introduced pairs and those already the pool, as well as between the newly introduced pairs themselves, following the ABO compatibility model (Dean 2005). For each of the new pairs, we randomly determine if the patient. is hard-lo-malech given by their calculated panel reactive antibody percentage (cPRA; high means hard-to-matehh (Tinckam et al.) 2015). Then, outgoing ares from each new pair are removed by drawing from a Bernoulli distribution with a parameter specified by the cPRA value. If the arrival rate at each round is À and we have N rounds, the expected number of vertices in the KEP pool at the end is AN. In our experiments, we did not simulate the arrival of non-directed donors to make the exposition simpler. Each graph (unless specified otherwise) in the distribution output by the simulator is obtained through N = 20 rounds with an arrival rate of A (i.e., the expected number of vertices is 100).
Generating episodes. For each obtained graph, we simulate 1000 episodes by picking actions at random and follow the Markovian process between matching round (N = 1, = 5). Thus, we obtain in total a dataset T' consisting 100, 000 vectors (LL) of trajectories т; forming episodes. We use conditional information (i.e. the initial graph at cach matching round) as part of the input to our models by computing graph embeddings using the starting graph al each matching round.
Model architecture. The architecture that is used consists of three main pipelines: learning embeddings, learning the initial flow Z (for GFlowNet) and learning the flow probabilitics Pp. The layers that are used for each pipeline are given in Table T in Appendix A
7 Computational results: evaluating the solution efficiency and quality of leasning-based methods
Using our simulator, we can evaluate the performance of our learning approaches static-matching episodes. This capability will allow us to model the evolution of the KEP pool over time as we follow the learned policy. Additional details regarding the architecture and other research questions can be found in Appendices and
7.1 Quality of generated solutions
RQ1: To what extent does the utilitarian value of solutions sampled from the learning methods align with those of the optimal solutions? To answer this question, we sample 1000 solutions for each instance using the tuned networks, as well as using the baselines. For example, when evaluating Get on a single instance, we sample 1000 solutions given the single initial KEP graph, while for multiple instances, we sample 1000 solutions for each KEP graph. Given a sampling mechanism, we compare the samples that generated and we select the best one (i... maximum utilitarian reward). The resulting samples should converge with probability 1 to their respective optimal value since each sampling mechanism has full support, provided the policy has full support. This is specifically the case for e-greedy policies.
We report the results from our experiment in Table where the approximation ratio is equal to the utilitarian methods do
value of a method's returned solution divided by the optimal value. While the learning- not recover solutions that are as good as OptMIP, we do see a significant improvement over the heuristics. We note that among the learning methods, GelowNet performs best. Further training of the networks,
11

---

Published in Transactions on Machine Learning Research (04/2025)
Instance size (AN 100)
Method
Single instance
Multiple instances
Best
Median
Worst
Best
Median
Worst
OptMIP
1.000 = 0.000
1.000 = 0.000
1.000 + 0.000
1.000 = 0.000
1.000 + 0.000
1.000 = 0.000
RandUniform
0.873 + 0.040
0.731 = 0.014
0.492 + 0.035
0.795 + 0.042
0.681 + 0.018
0.455 + 0.046
RandGreedy
0.877 + 0.035
0.779 = 0.030
0.589 + 0.021
0.821 + 0.037
0.740 + 0.072
0.492 + 0.011
PolicyGradient
0.919 = 0.058
0.826 = 0.016
0.775 0.026
0.838 + 0.067
0.748 + 0.054
0.684 = 0.292
ProximalPolicy
0.923 0.065
0.852 = 0.056
0.787 0.033
0.876 + 0.066
0.759 0.022
0.697 0.065
Q-lcarning
0.904 0.059
0.815 = 0.044
0.768 0.034
0.825 + 0.064
0.725 0.061
0.672 0.014
GFlowNeet
0.928 0.062
0.854 = 0.064
0.821 0.019
0.897 + 0.051
0.785 + 0.039
0.702 + 0.0457
Table 1: Average approximation ratio of learning-based methods against, baselines. For each instance, we report the best, median and worst values. We average these values over all instances.
along with adjustments the architecture and the optimal value, offering promising opportunities for enhancing method. Specifically, we envisage that training KEP instances with XN > 50 would help the performance when testing on larger KEP instances.
could potentially bring us even closer
7.2 Scaling to larger KEPs
RQ2: Is the gencralization capability of RL and flow learning applicable to KEP instances of diverse dimensions? In this experiment, we lest the capability RL and GFlowNets generalize larger graphs. Concretely, we train the neural networks on distribution of smaller graphs and then, we evaluate the quality of the returned solutions on graphs of larger sizes.
Instance size (AN)
Method
50
100
200
OptMIP
1.000 + 0.000
1.000 + 0.000
1.000 + 0.000
Raifori
0.829 + 0.045
0.795 + 0.045
0.631 + 0.064
RandGredy
0.841 + 0.044
0.821 + 0.034
0.706 + 0.066
Policy Gradient
0.015:
0.854 = 0.066
0.727 + 0.072
ProximalPolicy
0.933 0.056
0.862 0.062
0.742 + 0.066
Q-learning GFlowNet
0.885 = 0.065
0.829 0.056
0.716 + 0.072
0.936 + 0.058
0.872 + 0.057
0.782 + 0.077
Table 2: Average approximation ratio when training on instances of size (i.e. AN) 50 and testing against instances of size 50, 100, and 200.
The goal of this experiment is to show the ability of a model to extend beyond the size of the graphs on which it was trained. Since large graphs are currently hard to train because of the large number of possible actions involved at each step, a possibility is to train on smaller graph instances and deploy the network on larger KEP graphs to obtaín samples. We measure the quality of such samples on a network trained on instances with A. 50 (arrival of X = pairs each round in expectation; N 10 rounds). In Table we observe that when testing instances where the size of the initial KEP graphs is doubled, the learning- based methods still perform better than the heuristics. Inference sample 1000 exchange plans per graph within time of 15 minutes. The training time used was the same as in our prior experiments. While we do not report these values in Table 2 the approximation ratio of the best solution returned for larger graph sizes are surprisingly very similar to the ratios reported in Table ! (Multiple instances).
fast even larger graphs; were able to
RQ3: How efficient is the generation of exchange plans? In this experiment, we evaluate the ability of the learning approaches sample multiple exchange plans efficiently. We compute the time to sample
12

---

Published in Transactions on Machine Learning Research (04/2025)
single solution averaged over 1000 solutions for each method, except for OptMIP, where measure the time to return single solution. The results can be found in Table B
Instance size (AN) 200
Method
OptMIP
16.812 0.374
Randoniform
1.681 + 0.056
RandGreedy
0.889 + 0.034
PolicyGradices
1.702 + 0.075
ProximalPolicy
1.527 = 0.090
Q-learning
1.662 + 0.076
GFlowNett
1.627 + 0.016
Table 3: Aveage time (in seconds) to sample 1000 exchange plans OptMIP time is for one solution, while Dearning-based and heuristic methods take the average over 1000 sampled solutions.
We observe that the slowest method to compute a single solution is OptMIP. The other heuristics or learning-base based methods offer a more efficient method to obtain large number of solutions. It has to be said that the learning-based approaches require the training of neural networks. The time spent to retrieve solution is traded for the time spent learning the model. As the number and size of KEPs solved cach year is high and expected lo grow, the learning approach becomes viable, offering capabilities such as added flexibility in the choice of solution since we can generate many. It is also worth to mention that for larger KEP instances, OPT can often fail to return the optimal solution.
8 Computational results: evaluating the role of distributions in fairness and long-term policy behaviour
In this section, we will that learned policies result in efficient matching-generation mechanism that can be leveraged to generate distributions over exchange plans at each round. This ability combined with ideas from the fairness literature in KEPs will allow us to demonstrate the potential to mitigate the dis- proportionate probabilities of receiving a transplant over the set of patients in the pool. It will also allow us to better understand long-term impacts of KEP policics by directly modelling the evolution of the pool through the arrival and departure of patient-donor pairs.
8.1 Fairness in KEPs
RQ4: Does the efficient generation of exchange plans allow us to mitigate fairness issues in KEPs? In this experiment, we explore the extent to which learning approaches may improve fairness guarantces to patients by taking advantage of the fast exchange plan-sampling mechanism. Decision-makers can select solutions from large set of exchange plans, from which they can devise lottery policies that satisfy various fairness criteria. The access to multiple high-reward policies ensure that they can balance utilitarian and fairness aspects desired (sce section g for more in-depth discussion on this).
We choose to focus on the concept of individual fairness for KEPs Farnadii el al. 2021 We begin by computing the set p' of patients that can receive a transplant in the KEP. Using the subset Pl, we make use of a fairness measure referred to as the L, distance for individual fairness (Farnadi al., 2021).
Definition 8.1 (Feasible matchings). For a graph G = AV, we define the set of feasible matchings Xg as
Xa (H (G, e x
(10)
Definition 8.2 (Lp distance). Let G = AV be graph and P' CVV the subset of vertices that can be in al least one solution from Ng. The T.p-fairness of a probability distribution 8 over Xa is given by
Σ (5, 8)P, PEP
(11)
13

---

Published in Transactions on Machine Learning Research (04/2025)
where 6, := HHexalve 8(H), and 8 8= in selected exchange plan and 8 is the mean probability of being selected as part of an exchange plan for patients in P'. A probability distribution 8 is individually fair if it minimizes the Objective
Evepi 8y. The variable oe is the probability that vertex is
This L1 distance (here, p 1) is meastre of the dispersion of patients' chances of being selected: a lower value indicates more equally distributed chance of recciving a transplant, which is considered better. For each method, we sample 1000 maximal exchange plans and we compute the probability mass of the sampled exchange plans for two distributions: the uniform distribution and the distribution minimizing the L1 distance. Because of the similarity in performance demonstrated amongst the learning- baandd methods in the previous experiments, we only include results for GFlowNett as they offered the best performance. We categorize our results as GFlowNet w/ uniform and GFlowNett w/ IF. We compare against OptMII whose 4 score is computed from the distribution with single solution. We also include the method of St-Arnaud et al. (2023). referred to Enum w/IF, which consists of enumerating optimal solutions to KEPs using column generation procedure in order to minimize the L1 value. For the column generation procedure, we set a time limit of hour. We also added the bascline hcuristic RandGreedy to evaluate the methods to enhance fairness over a simple solution sampling process. In order to understand how individual fairness would scale, we also used different values of N (with the same A) generate 1000 instances for each additional AN combination. We report our results in Table g where we group results by the value of AN (i.c. the expected size of the instances in the generation process).
capacity of learning-basee
Instance size (AN)
Method
50
100
200
OptMIP
15.381 1.814
43.265 8.318
81.211
14.484
Enum w/ IF
10.532 1.489
25.423 3.991
61.306
8.153
GFlowNeet w/ uniform
11.794 + 1.130
34.467 + 4.651
63.597 + 9.426
GFlowNet w/ IF
10.701 = 1.280
26.981 + 3.823
62.049 + 8.005
RandGreedy
14.440 = 1.791
39.814 + 5.295
75.869 + 12.655
Table 4: Average individual fairness measures per instance size.
We observe that GFlowNets (and learning-based methods) improve measures of fairness when compared with OptMIP as they allow for a more varied subset of patients to be included in its distribution of solutions. Furthermore, the learning- based methods outperform the heuristic RandGreedy, indicating that these methods are helpful in improving individual fairness measures. The optimal values achievod by Enum w/ IF are very close to the ones offered by GFlowNet minimizing the Li with respect. to the sampled exchange plans (referred to as GelowNett w/ IF in Table D. In fact, making use of learning- methods reveals to be a promising approach they result in efficient samplers once trained that improve individual fairness for larger instances. We can even manage to generate a large number of solutions for instances of size AN = 500 and 1000, while it is not feasible for OptMIP or Enum w/ IF. In fact, for such large KEP graphs, we could not even manage to generate a single solution in the time limit. We note that individual fairness has been shown to suffer from technical issue when optimized in conjunction with a utilitarian (St-Arnaud et al. 2023) because empty exchange plans are optimal in terms of the fairness metric. This is, however, not the case in our experiments since we sample solutions that are maximal, i.c., they cannot be extended further. This experiment serves to highlight how the ability to generate large set of exchange plans can be used to mitigate fairness issues through lottery policies. In practice, decision-makers might wish to balance fairness and utilitarian approaches. The capacity to explore the space of lottery policies through the efficient generation of exchange plans provides fortile ground for the exploration of these ideas.
By generating multiple solutions through reinforcement and flow learning methods, we can sample among them and use the resulting patient probabilities to empower decksion-makers with vital information related to the structure of the KEP graph that would otherwise be missing. For example, in Figure 3 we observe how these probabilities are distributed. Note that with GFlowNet w/ IF, the probabilities are less unevenly distributed. It is then possible to identify patients that are "mathematically" hard-to-mate
5 For more context, see AtaAn et
2023
14

---

Published in Transactions on Machine Learning Research (04/2025)
0.0
GFlowNet w/ uniform
0.0
0.5
Ratio
0.3
0.0
0.6-0.8
0.4-0.6
Ranges of probability of inclasion
Figure 3: Distribution of patient transplant probabilities by ranges of probabilities. Values are averaged over all instances with AN 100.
according the KEP graph, as a complement clinical definitions involving their cPRA measure Dickerson
et al. 2014 Saidman et al. 2006).
Another conceivable method to jointly optimize the number of transplants and some fairness objective would be to make use of the conditioning nature of approach, where we condition on the weights over both objectives (see Jain et al. 2023) for an application to GFlowNets). These weights can later be changed to evaluate the effect on the space of solutions returned by the model, offering some added flexibility to decision- this work, we focus on the use of single objective because of the added level of complexity these conditional models entail. In the case of individual fairness and patient probabilities, multi-objectivee RL approaches and multi-objective GelowNets cannot provide any help as they functions of distributions of exchange plans.
8.2 Long-term policy behaviour
RQ5: Can efficient solution generation be used to evaluate the long-term impact of a selection policy? In this experiment, we deploy trained GFlowNet (on instances of size AN = 50) and we perform multiple matching rounds using it. Concretely, in each round, an exchange plan selected, the selected vertices are removed from the graph and the arrival of new pairs with their corresponding compatibility ares is simulated. We use the same arrival rate À and number of arrival rounds N for the incoming data. In total, we generate 1000 maatic-mtcching episodes corresponding to multiple matchings and changes in the pool. compare the use of GFlowNet in each round with the use of OptMIP. The computation
In Table times reported are with respect to the solution sampling time. Times to build the MIP (for OptMIP), to enumerate available actions and to obtain the tensors (for GFlowNet) are not reported as they are similar for both methods.
Foremost, we are interested in predicting the evolution of the KEP pool over multiple matching rounds, as using OptMIP is slow and, for large real-world sizes, impractical. For this purpose, we deploy a GFlowNet horizon of length 10 (i.e. 10 matching rounds). At each matching round, we select the maximum- sized exchange plan from the set sampled by the GFlowNet (1000 exchange plans for each matching round), Since the GelowNet approximates the true optimal distribution with respect to the utilitarian objective, the probability that the selected exchange plan is optimal goes to as the nunber of samples increases at each round.
We compare the cumulative number of transplants divided by the number of matching rounds against OptMIP. The averages were computed over 1000 trajectories, much as in the previous experiment. We refer the reader to Figure 4 for results. The efficient sampling mechanism offered by GFlowNets allow to
15

---

Published in Transactions on Machine Learning Research (04/2025)
Instance size XN
50
/ Matching rounds
2
5
10
OptMIP processing time (s)
43.862 + 5.057
118.639 + 13.517
189.771 + 29.428
15.219 + 0.393
38.910 + 1.990
81.629 + 6.240
GFlowNeet
40.580 = 7.291
101.431 = 12.674
144.615 = 29.630
processing time (s)
1.328 + 0.012
3.263 + 0.031
5.103 + 0.062
Instance size XN
100
Method/ /Matching rounds
2
5
10
OptMIP processing time (s)
71.006 = 9.874
168.305 + 19.171
292.203 + 36.743
35.604 + 1.17
93.791 + 7.29
199.603 + 17.709
GFlowNet
66.672 + 11.116
149.503 + 22.395
229.646 + 39.645
processing time (s)
3.336 + 0.018
8.965 + 0.046
18.385 + 0.091
Instance size XN
200
Method/Matenn Matching rounds
2
5
10
OptMIP processing time (s)
GelowNet
136.013 + 28.223
296.246 + 28.018
633.861 + 75.446
processing time (s)
3.910 + 0.045
10.704 + 0.147
23.731 + 0.284
Table 5: Average number of transplants for multiple matching rounds when training on instances of various sizes 50 and testing against instances of the same size. The average processing times reported are with respect sampling 1000 solutions. No instances were solved for OptMIP within the time limit for A.V 200.
OptMIP
GFlowNet
23-
Transplants
22
21
20
19.
2
Matching rounds
Figure 4: Average cumulative number of transplants after each round, divided by the number of rounds over instances of size AN 50.
approximately compute the expected number of transplants performed over multiple rounds of KEPs under a MPP framework. This allows us to model the evolution of the KEP pool under uncertainty over large instances, and Figure demonstrates that we can approximate the expected number of transplants achieved under GllowNet high precision. The repeated optimization for MIP proves too costly to evaluate over instances of size 200, shown in Table 3 (dashed lines), which serves underscore the effectiveness of our sampler in predieting the evolution of the KEP pool.
16

---

Published in Transactions on Machine Learning Research (04/2025)
9 Discussion, future directions, and broader impacts
In this work, we have demonstrated the ability of learning-based methods, complement exact MIP ap- proaches in KEPs. Our learned models, efficient samplers of near-optimal solutions, give two highly valuable outcomes. Firstly, are able to efficiently provide multiple high-quality solutions that can be used, for example, to promote fairness or to offer alternative solutions in the event of unexpected infeasi- bility (e.g. donor drop-off). Secondly, we can approximate the long-term impact of choosing a particular objective (matching policy) on the KEP pool. In the future, we can learn nou-static-matching (i.e. dynamic) policies over a longer horizon of simulated arrivals to approximate the optimal policy over multiple matching rounds, given an objective (e.g. utilitarian objective). Validating our approach with hierarchies of objectives and other real-world complexities in KEPs would be of interest. Of particular interest, thorough explo- ration of the space of lottery policies can offer mecision-makers the ability to explore policies that provide certain fairness guarantees while remaining efficient in terms of the expected mumber of transplants. The learning-baad based mechanism we present in this article can be used to efficiently generate multiple exchange plans that can be included in the support of these lottery policics, scaling to large kidney exchange pools. We envisage the extension of our conditional learning-based method to a family of objectives as in Jainn et al. (202)), in order to explore a large set fair policies as well as policies that balance utility and fairness. Our explorations need not be confined solely to KEPs. The applicability of learning- matching or combinatorial problems remains promising avenue for future study, Particularly in the context of policy-making, they have the potential to provide guidance on the combinatorial space of solutions and to help anticipate long-term impacts.
methods to other
With respect to the broader impacts that our work can have, we highlight the expanded applicability of learning-base methods to address combinatorial problems, with a specific emphasis on KEPs. Our findings showcase promising results in learning (near-Joptimal distributions that can guide policymakers and clini- cians, and offer patients supplementary information regarding solution selection and kidney allocation based their graph positions. This work represents an initial step towards acquiring deeper insights into novel approach for solution selection based on distributions of solutions and the approximation of long-term effects in problems that wield significant impact on individuals' lives. While our initial results are encouraging, the ethical, legal, and social consequences of our approach need in-depth consideration to ensure responsible implementation. In addition, our approach currently tailored to KEPs. Fxtending it to broader combi- natorial problems requires careful validation and adaptation. The real-world scenarios given their dynamic and multifaceted nature, specifically in health care, involve complexities that our approach may not fully capture. For instance, how patient preferences or health conditions evolve over time or how health-care poli- cios change. Finally, our evaluations rely on simulated data and as the approach evolves, obtaining diverse and comprehensive real-world datasets becomes crucial. However, we acknowledge the difficulty of accessing such datasets due to their sensitive nature.
10 Acknowledgements
This work was funded by the NSERC grant 2024-04051 and 2021-04378, Canada CIFAR AI Chair, and Google scholar award. This research was enabled in part by support provided by Calcul Québec (www. . calculquebec.co ca) and Compute Canada www.computecanada.cca
References
David J. Abraham, Avrim Blum, and Tuomas Sandholm. Clearing algorithms for barter exchange mar- kets: Enabling nationwide kidney exchanges. In Proceedings of the 8th ACM Conference on Electronic Commerce, EC '07, pp. 295-304, New York, NY, USA, 2007. ACM. ISBN 978-1-595933653-0. doi: 10.1145/1250910. 1250954. URL http://doi. acm. org/10. 10. 11 1015//125910...1 1250954
Christof Angermueller, David Dohan, David Belanger, Ramya Deshpande, Kevin Murphy, and Lucy Colwell. Model-based reinforcement learning for biological sequence design. In International conference on learning representations, 2019.
17

---

Canadian Institute for Health Information. High risk and high cost: Focus on opportunities to roduce hospitalizations of dialysis paticnts in Canada. httts:// www.chccccacccccceccccc www.ch.aaattteeerouueeeoo repott-coor- Published in Transactions on Machine Learning Research (04/2025)
Pierre-Cyril Frank-Frannkwski,, Yohann De Castro, Axel Parmentier, and Alessandro Rudi. Generalization bounds of surrogate policies for combinatorial optimization problems. arXiv preprinl orXin:2407.11 17200, 2024.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial opti- mization with reinforcement learning. arXiv preprint Xiw:1611.0994.. 2016.
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, 94:27381-27344 2021.
Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward Hu, Mo Tiwari, and Emmanuel Bengio. GFlowNet Foundations. The Journal of Machine Learning Research, 21(1):10006110000, 2023.
Hamoud S. Bin-Obaid and Theodore B. Trafalis. Fairness in resource allocation: Foundation and appli- cations. In Ilya Bychkov, Valery A. Kalyagin, Panos M. Pardalos, and Oleg Prokopyev (eds.), Network Algorithmss, Dala Mining, and Applications, pp. 3 3-18, Cham, 2020. Springer International Publishing. ISBN 978-3-030-37157-9.
Péter Biró, Joris Van de Klundert, David Manlove, William Pettersson, Tommy Andersson, Lisa Burnapp, Pavel Chromy, Pablo Delgado, Piotr Dworczak, Bernadette Haase, et al. Modelling and optimisation in European kidney exchange programmess. European Journal of Operational Research, 291 (2):444447-)))) 456, 2021.
web. 2016. 'Accessed: 2024-11-28".
Miguel Constantino, Xenia Klimentova, Ana Viana, and Abdur Rais. New insights on progremprggramming models for the kidney exchange problem. European Journal of Operational Research, (31(1):57 -6, 2013.
ISSN 0377-2217.
Thomas H. Cormen, Charles Eric Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algoritims. The MIT Press, Cambridge, Massachusett, fourth edition edition, 2022. ISBN 9780262046305..
Laura Dean. The ABO blood group. In Blood Groups and Red Cell Antigens. National Center for Biotech- nology Information (US), 2005.
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,, 2025. ISSN 0377-2217. doi: https://db..rrg/1..00////// 200200.0...00.22.0000000. URL https://www www. sciencedirect. ootp////aaaaeaarr../////////1110
Fabrizio Detassis, Michele Lombardi, and Michela Milano. Teaching the old dog new tricks: Supervised learning with constraints. In Proceedings of the AAAT Conference Artificial Intelligence, volume 35, pp. 3742 3749, 2021.
John P. Dickerson, Ariel D. Procaccia, and Tuomas Sandholm. Price of fairness in kidney exchange. In AAMAS, pp.
2014.
John P. Dickerson, David F. Manlove, Benjamin Plaut, Tuomas Sandholm, and James Trimble. Position- indexed formulations for kidney exchange. In Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16, pp. 25-42, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781 450339333. doi: 00.1145/29400166
URL
1ttp//0..14//29407.. 2940759
John Paul Dickerson and Tuomas Sandholm. Balancing efficioncy and fairness in dynamic kidney exchange. In AAAI Workshop: Modern Artificial Intelligence for Health Analytics, volume WS-14-08 of AAAI Work- shops. AAAI, 2014.
18

---

Published in Transactions on Machine Learning Research (04/2025)
Golnoosh Farnadi, William St-Arnaud, Behrouz Babaki, and Margarida Carvalho. Individual fairness in kidney exchange programs. Proceedings of the AAAT Conference on Arlificial Intelligence, 35(13):11496; 11505, May 2021. URL https://oja awa.aaaaiaa....... www.index...oiioooooooooo httgg///ee...pp/AAaaarriiieeeee phtp/AAt//artiill//veee////
Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as layer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1504-1511, 2020.
Bailey Flanigan, Paul Gölz, Anupam Gupta, Brett Hemnig, and Ariel D Procaccia. Fair algorithms for selecting citizens' assemblies. Nature, 596(7873):548-333 552, 2021.
Irena Gao. Fair matching in dynamic kidney exchange. orXiv preprint arXiv: 1056, 2019.
JJ Hopfeild and DW Tank. Neural computation of decision in optimization problems. Biological cybernelic, pp. 52 60, 1985.
Moksh Jain, Sharath Chandra Raparthy, Alex Hernandez-Garcia, Jarrid Rector-Brooks, Yoshua Bengio, San- tiago Miret, and Emmanuel Bengio. Multi-objective GFlowNets. In Proceedings of the 40th International Conference on Machine Learning, ICML 23. JMLR.org, 2023.
L. V. Kantorovich. Mathematical methods of organizing and planming production. Monagement Science, 6 (4):366-422 422, 1960. doi:
URL https://doi org/10. 1 ht.7//mss..uu 6.4.664436666 466
James Kotary, Ferdinando Fioretto, Pascal van Hentenryck, and Bryan Wilder. End-to-end constrained optimization learning: survey, 30th International Joint Conference on Artificial Intelligence, IJCAI 2021, pp. 4475 4482, International Joint Conferences on Artificial Intelligence, 2021.
Shafi Malik and Edward Cole. Foundations and principles of the canadian living donor paired exchange program. Conadian journal of kidney health and discase, 166), 2014.
Nikolay Malkin, Moksh Jain, Emmanuel Bengio, Chen Sun, and Yoshua Bengio. Trajectory balance: Im- proved credit assignment in gflownets. Advances in Neural Information Processing Systems, 35:5055-5967, 2022.
Aurora del Carmen López and José María Ponce-Ortege Fair allocation of potential COVID-19 vaccines using an optimization based strategy. Process Integration and Optimization for Sustainability, 5: 3-12, 2021.
K Park, JH Lee, KH Huh, SI Kim, and YS Kim. Exchange living-donor kidney transplantation: diminution of donor organ shortage. Transplantation proceedings, 36(10):2949 295, 2004.
FT Rapaport The case for living emotionally related international kidney donor exchange rogistry. Trans- plantation proceedings, 18(3) Suppl. 2):5-9, 9, June 1986. ISSN 0041-1345.
Alvin E Roth, Tayfun Sönmez, and M Utku Unver. Kidney exchange. The Quarlerly journal of economics, 119(2):457 488, 2004.
Alvin E. Roth, Tayfun Sönmez, and M. Utku Ünver. Efficient kidney exchange: Coincidence of wants in markets with compatibility-baat preferences. American Economic Review, (3):88828-85)) June 2007. doi: 2..125//ee.999 97.3.828. URL https: //tw://wwwww..o aeaweb. wwt..r//aaati.ees::11...... 1257 /aer http//eer.99...... 39.33.828
S. Saidman, A. Roth, T. Sonmez, U. Unver, and F. Delmonico. Increasing the opportunity of live kidney donation by matching for two- and three-way exchanges. Transplantation, 81(5): 782,, 2006.
William St-Arnaud, Margarida Carvalho, and Golnoosh Farnadi. Adaptation, comparison and practical implementation of fairness schemes in kidney exchange programs, 2023.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforeement learning with function approximation. Advances in neural information processing systems, 12, 1999.
19

---

Published in Transactions on Machine Learning Research (04/2025)
K. J. Tinckam, R. Liwski, D. Pochinco, M. Mousseau, A. Grattan, P. Nickerson, and P. Campbell. opra increases with dqa, dpa, and dpb unacceptable antigens in the canadian cpra calculator. Ameri- can Journal of Transplantation, 15(12):3194 3201, 2015. doi: http://bbb.org//0.111/a...... attps://onnineelbraay httpa//wwaaaaaaooo/oo//////////a
URL
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference Learving Represenlations, ICLR 2018, Vancowver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
URL httpp::/openreevie httpe//viwweee/ffuurruoe wttt:/orrumii
Oriol Vinyals, Mcire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-docisions pipeline: Decision-focused learning for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1658-1665, 2019.
Ronald Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8:229-255 256, 1992.
20


Reviews:
[{"review_id": "DYD1AzhNn6", "reviewer": "Reviewer_r3iH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- the usage of Gflownet seems appropriate in this scenario\n\nWeaknesses:\n- lack of clarity:\n  * In Figure 1, if N is the set of *non-directed* donors, why v_8 has a link with v_3 only?\n  * Providing an intuition of internal state and external state on top of the formal definition would help the reader\n  * The definition of the transition function is not clear. For a state (G, H), it should be explained how the next state are constructed.\n  * R(s_n) in (6) is not defined without an input action.\n  * Intuition about the Trajectory balance loss would also help, what is the motivation for using this loss?\n  * see requested changes\n\n- The experiments on fairness is not very convincing as you are comparing a method that do not optimize for fairness (OptMIP), with a method that do (GFlowNet followed by a selection according to fairness, GFlowNet w/ IF). \nIf GFlowNet w/ uniform do not explicitly optimize fairness, it's often the case in multi-objective optimization that when you are a bit worst on one objective you can be better on another.\nA cleaner experiment would present results displaying the Pareto front and include the performance of OptMIP if it would also optimize for fairness.\n\n- when it comes to KEP, it seems that obtaining slow optimal solutions is preferred over obtaining fast sub-optimal ones", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes to solve kidney exchange problems with GFlowNets by training it with RL or the trajectory balance loss.\nThe authors claim that their approach can complement traditional integer programming methods, enhance fairness, and provide a more efficient way to simulate the evolution of KEPs over time.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Figure 1 has notation or vocabulary issues. v is both used to denote a pair (as P is a set of incompatible pairs) and to denote single donor (v_8). It seems to me that P is the set of incompatible patients (not a set of pairs).\n\n- Please confirm what are the backbone networks used in Policy Gradient, PPO & Q-Learning? Notably for the Q network that seems to be used in every method.\n\n- The definition of the Q function (4.8) is not clear and not complete, are you maximizing a discounted sum of rewards?\nIf so, it looks like comparing algorithm that maximize \\sum r_t (policy gradient, Q-Learning & PPO) vs ones that maximize the final reward r_T (GFlowNet loss (7)) is not right. Please describe how is the Q function learned or estimated?\n\n- It looks like you are training in an offline RL scenario according to the Section 6. (Generating episodes). Therefore, why would you use online RL algorithms in this setup? Please clarify.\n\n- \"It is also worth to mention that for larger KEP instances, OptMIP can often fail to return the optimal solution.\" The claim is not supported by experiment results. Can you find large instances where the solution you obtain is better than OptMIP?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8HNfhDPC1v", "reviewer": "Reviewer_g4z3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGHTS:\n- To the best of my knowledge, applying learning-based methods to the kidney exchange problem is new. This is a relevant problem that is widely studied in the Operations Research and Economics literature, and traditional solution methods have been highly focused on Mixed Integer Programming (MIP) formulations.\n- The authors introduce the terminology that is required for the learning-based methods in an accessible way that is understandable for readers who have limited experience with learning-based methods.\n\nWEAKNESSES: \n\n-\tFirst, I believe that this is a setting where optimality of a solution is extremely important. For all evaluated instances with 200 pairs, for example, Table 2 illustrates that all heuristic methods (incl. learning-based) have an approximation ratio of less than +- 78%. For illustration, imagine the optimum would be 150 matches, for example. In that case, this would mean that adopting one of the discussed heuristics instead of an exact solution would result in 33 less transplantations! These are 33 patients that could have received a life-saving transplantation, but do not get one because of a choice not to focus on trying to find the best possible solution. The paper argues that MIP methods are not scalable. While it is true that computation times increase rapidly for larger instances, there is a large literature that proposes alternative MIP formulations for various kidney exchange variants. The paper: ‘On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches’ by Mak-Hau (2017), for example, illustrates that instances with up to 2000 pairs could be solved optimally, and since then, newer methods have been developed.\n\n-\tThe discussion on individual fairness is lacking in my opinion. First, only the criterion of L_1 fairness is considered, which is not a good measure to compare methods that find distributions over solutions of different quality. Imagine a solution in which no exchanges are executed. The average probability is zero, and the L_1-fairness is zero as well, obtaining a better score than all methods presented in the paper. It could be that the learning-based obtain a L_1-fairness score close to the optimal because they allow for worse solutions, while the optimal distribution only uses solutions that find an optimal number of exchanges. As the learning-based methods optimize over a different (larger) solution space, they could have well obtained a lower L_1-fairness score. To truly claim that the learning-based methods improve the individual fairness of the problem, they should be compared based on other individual fairness metrics (e.g., leximin, which maximizes the minimal selection probability, Nash product, L_2 norm…?). Additionally, a comparison with, for example, RandGreedy could be added to convince the reader that the learning-based methods outperform a very simple heuristic.\n\n-\tSecond, the improvement in individual fairness with respect to OPTMIP is not a merit of the learning-based methods, but is simply due to the fact that OPTMIP only returns a single solution. Papers such as Farnadi et al., 2021, St-Arnaud et al., 2023, and Demeulemeester et al., 2025 already observed that a distribution over multiple optimal solutions greatly outperforms selecting one optimal solution deterministically with respect to individual fairness. \n\n-\tIt is not stated to which MIP formulation the learning-based methods are compared to. The choice of the MIP formulation matters a lot for the time required to find a solution.\n\n-\tThe claim that finding distributions over optimal exchange plans using MILPs is not scalable is unfounded, in my opinion. On page 4 (top), it is claimed that this is only scalable for instances up to 50 instances. In Demeulemeester et al. (2025), for example, methods are introduced to find various distributions that do not rely on full enumeration of the optimal exchange plans. The solution times that are presented by them are around 1 second for some of the distributions for instances up to 70 pairs.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose learning-based methods for the kidney exchange problem, where the goal is to find reallocation cycles between incompatible patient-donor pairs. Their methods will in each episode focus on the static setting, in which the set of patient-donor pairs is fixed and given. Between different episodes, they model an arrival process in which new patient-donor pairs are added to the pool.\n\nThe authors perform a computational study to compare the performance of the learning-based methods with traditional solution methods for the kidney exchange problem, such as a MIP formulation and simple heuristics (e.g., greedy). While the solutions generated by the learning-based methods have no guarantee of optimality (where optimality is measured as the maximum number of transplants), the authors report on the quality of the generated solutions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the points in the section on weaknesses of the paper under the previous question.\n\nAdditional small comments:\n\n-\tP.3: kidney exchange is not only implemented in countries in Europe, as stated, but also widely used in the US and Canada, for example\n-\tP.3: To the best of my knowledge, it is common to say that an arc (u,v) means that the patient from pair v is compatible with the donor of pair u, and not the other way around as written in the paper. See, e.g., the paper ‘Novel integer programming models for the stable kidney exchange problem’ by Klimentova et al. (2022).\n-\tP.3, bottom section 2: maximum predetermineD exchange length.\n-\tP.4: “The drawback of their methodology is that fairness objectives are an input, effectively restricting the landscape of solutions made available to the policy-makers.” I don’t understand this comment. These papers aim to optimize individual fairness criteria (e.g., minimum selection probability) when allowing for all optimal exchange plans. In what sense do they restrict the solutions that are made available? \n-\tP.5 (middle): “[if the exchange plan is maximal, we can select it] … or we can augment it with additional cycles and chains.” How can we add additional cycles or chains when the exchange plan is already maximal?\n-\tP.5, Def. 4.3: sloppy math: T is a mapping so add : between T and (s,a). Later on in the paper, the notation for mappings is also different from convention. And what should be before =(s,s’)?\n-\tP.6: “Actions are represented by blue arrows”. There is only one blue arrow?\n-\tP.8: in Fig. 2, pair v_2 is included both in H_1 and in H_2? They can only be included in one cycle/chain, no?\n-\tP.9 (top): learning-based methods instead of leaning-based (also p. 13)\n-\tP.10: $\\tau_i$ instead of tau_i\n-\tP. 14: “Since the GFlowNet approximates the true optimal distribution, …” Optimal distribution with respect to what objective function? Will this be a distribution optimizing an individual fairness measure? Or do you refer to the number of matches in the matchings it finds?\n-\tRQ3: why should you compare to generating 1000 optimal solutions using OPTMIP, and not just to comparing one optimal solution? Because the 1000 sampled solutions using the proposed methods will at the first step be used to find the one with the maximum number of transplants, which is exactly what you obtain by solving the MIP formulation to optimality once. (Side question: will 1000 sampled solutions using your methods all be different? Because MIP will generate 1000 different solutions, which is more challenging than simply sampling 1000 times).\n\nLastly, the references have some missing information and lack consistency.:\n-\tGao (2019): add additional information (arxiv?)\n-\tSome references have doi (Abraham et al., 2007), others do not\n-\tDemeulemeester et al. (2024) no page numbers or issue number\n-\tBengio (2021a) is published", "broader_impact_concerns": "/", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nOG89AMUxC", "reviewer": "Reviewer_4Wqt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n* While applying learning-based methods to find approximate solutions for combinatorial problems is an existing line of research, this paper contributes by proposing an RL- and GFlowNets-based approach for KEPs—a combinatorial problem with real-world impact.\n\n* The paper is generally well organized. The problem setting is formulated clearly, and the visualizations provided with the concrete examples are helpful for understanding the sampling procedure of exchange plans in the proposed approach.\n\n* When selecting the highest-utility exchange plan out of 1000 plans generated, the proposed learning-based methods are shown to generate exchange plans that achieve about 90% of the optimal utilitarian reward achieved by the exact solver, outperforming heuristic-based baselines RandUniform and RandGreedy.\n\n* The learning-based methods, while requiring a training process before use, are able to generate exchange plans more efficiently with their learned policy than the exact MIP solver. This could be valuable for simulating multi-round KEPs and thus studying the evolution of KEP pools over a longer time horizon.\n\n* The demonstrated efficiency, coupled with the 90%-optimal best-sample reward, highlights the potential of the learning-based approach as a practical and faster approximate solver for KEPs.\n\n## Weaknesses\n\n* **Limitation of the comparison of solution quality:** In Section 7.1, the learning-based methods and the heuristic-based methods generate multiple (1000) exchange plans for a single KEP graph. However, only the best exchange plan with the highest utilitarian reward is compared across methods, while there is no comparison of the distribution of utilitarian rewards over all generated exchange plans. Furthermore, summary statistics such as average/median utilitarian rewards for each method are not included. One of the advantages of the learning-based approach, as argued in the paper, is its capability to compute a diverse set of (near-)optimal solutions. However, this is not well supported by the current results, as only the best solution generated is evaluated. Additionally, the utilitarian rewards of other generated exchange plans matter since all generated exchange plans are used as the support for the KEP policy in the discussion related to fairness improvements in Section 8.1.\n\n* **Limitation of the discussion on fairness improvements (Major):** Without evaluating the utilitarian rewards (number of transplants) achieved by different methods, the evaluation and discussion of individual fairness (IF) measures alone in Section 8.1 do not provide sufficient insights into the performances of the compared methods. For the baseline *Enum w/ IF*, the distribution of solutions has a support that only contains optimal solutions, therefore achieving the optimal utilitarian reward. In contrast, there is no evaluation of the utilitarian rewards achieved by the proposed learning-based methods *GFlowNet w/ uniform* and *GFlowNet w/ IF*. Comparing methods based solely on the IF metric is insufficient since they may lead to very different utilitarian rewards. A hypothetical policy (e.g., a uniformly random policy) could achieve a low IF measure while not being practically useful for KEPs if it results in very few transplants. Therefore, the claim that the learning-based approach improves fairness in KEPs requires additional evaluation of the corresponding utilitarian rewards.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Kidney exchange problems (KEPs), as a combinatorial problem, typically require computationally expensive methods such as mixed-integer program (MIP) solvers to solve for exact optimal solutions. As an alternative, this paper proposes a learning-based approach for KEPs: training a stochastic policy to generate exchange plans using algorithms such as reinforcement learning and generative flow networks (GFlowNets) over simulated KEPs, then sampling multiple exchange plans using the learned policy on new KEPs. The motivation of this approach is to find approximate solutions to KEPs using a method that can generate multiple exchange plans efficiently.\n\nThe paper explores a range of research questions through experiments on simulated KEPs. The experimental results show that the learning-based approach can provide exchange plans that achieve about 90% of the optimal utilitarian reward by selecting the best of the multiple exchange plans generated by the learned policy. This performance is higher than that achieved by heuristic-based baselines, RandUniform and RandGreedy. In addition, it is shown that the learning-based methods, after training, can generate exchange plans more efficiently than the exact solution solver based on MIP, which makes then more viable for simulating longer-term KEPs. The paper also discusses potential applications of the learning-based approach for fairness considerations in KEPs, based on its capability to generate multiple exchange plans.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Expand Section 7.1 to include additional measures of solution quality beyond the utilitarian reward achieved by the single best exchange plan generated. For example:\n  - The distribution of rewards over all generated plans.\n  - The mean/median utilitarian reward.\n  - The variation in the best-sample reward across different sample sizes. As the authors note in Section 7.1, all random methods, including the heuristic-based methods, can theoretically achieve near-optimal rewards if they have full support on all valid exchange plans and the sample size is sufficiently large. It would be interesting to evaluate how the best-sample reward of different methods changes with varying sample sizes.\n\n* In Section 8.1, the discussion of fairness improvements should be coupled with an evaluation of the utilitarian rewards achieved by different methods. This would provide a more complete picture for understanding the trade-offs between fairness and the utilitarian rewards (the number of transplants) achieved by each method.\n\n* Question: The caption of Table 3 states that it shows the average time to sample 1000 exchange plans. However, it is also mentioned that only one solution is generated for OptMIP. Does the time reported for OptMIP correspond to generating a single solution, while the times for other methods represent the total time required to generate 1000 solutions?", "broader_impact_concerns": "The broader impacts of the work have been discussed in the last section of the paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Some revision is needed to address the Claims and Evidence criterion.

One substantive way to address this, in the spirit of reviewer suggestions, would be to consider these various methods in the 2D space of efficiency vs fairness operating points and provide a method by which GFlowNets can be used to trace out a curve in this space rather than merely identifying two possible operating points.  For example, can the approach be used with a parameterized objective to choose a distribution to optimize a weighted combination of fairness and efficiency?  (This might also clarify the somewhat mysterious role played by the version with the uniform distribution which currently is not really discussed.  How should we think about it?  As an ablation?)

Alternatively, the TMLR guidelines identify another pathway to ensure the claims made in the paper are supported: “Another is simply for the authors to adjust (reduce) their claims.”  I believe it would be accurate to use language such as “suggests the potential of GFlowNets to be used to address fairness”, since I believe the results do show enough as is to demonstrate potential, although the efficiency of the new methods as is should still be reported in either Table 4 or some alternative form.  Suitable caveats and discussion of the research challenges for future work around implementing this would need to be added, for which comments and suggestions from reviewers should be incorporated.

Either approach would be adequate to satisfy the criteria, so I leave the choice to the authors.  The first would make for a stronger paper, but I recognize it requires some additional work.  I believe the second falls well within the expectations for a minor revision.
Decision: Accept (poster)