Summary and Contributions: This paper studies a kidney exchange problem. Kidney exchanges can be represented by a directed graph. Each edge is considered as one potential kidney exchange, and the goal is to choose a subset of edges (i.e., a matching policy), which maximizes the expected number of successful exchanges. The key element in the model is the ability of the decision-maker to perform a pre-screening (i.e., query) before constructing a matching. After a query, a binary label is assigned to each queried edge: Accepted or Rejected. If the label of a queried edge is “rejected,” it will not be selected in matching phase. On the other hand, an edge with “accepted” label may or may not be selected by matching policy. We should keep in mind an “accepted” label does not guarantee a successful exchange. The main contribution of this paper is developing an algorithm for selecting query edges. Finding optimal pre-match queries is an NP-hard problem. However, this paper suggests two algorithms (MCTS and Greedy) to find a suboptimal pre-match query.
Strengths: 1. The first contribution is the model itself. This model considers the possibility of performing pre-screening before constructing a matching. A queried edge can be labeled as accepted or rejected. However, an edge with "accepted" label does not guarantee a successful exchange. This proposed kidney exchange model with pre-screening is new. 2. Finding the optimal query is an NP-hard problem. However, this paper proposes an algorithm to find a suboptimal query strategy that helps the decision-maker construct better matching. Based on table 1, the proposed algorithm finds the optimal query for at least 90 of the 100 graphs.
Weaknesses: I have the following concerns about the paper: 1. This paper introduces an algorithm to find a suboptimal query strategy, and it does not provide an algorithm to find the optimal matching. For finding the best query strategy, we need to know the optimal matching policy as a function of the query edges. This paper assumes that after selecting a specific query, the optimal matching and the maximum utility are available to the decision-maker. More precisely, this paper assumes that $V^S(q)$ is available to the decision-maker. However, we need to find the optimal matching policy for evaluating $V^S(q)$. Finding the optimal matching is much more difficult and important problem. Of course, after evaluating $V^S(q)$, we can search through possible queries to find a (sub)optimal query. Even if the decision-maker does not want to perform pre-screening, he has to find the optimal matching, and this paper does not provide an algorithm for that. 2. The experiment is unfair. Just consider the definition of $\Delta^{max}$. $\Delta^{max}$ tells us how much improvement the proposed algorithm can make as compared to a scenario without query. Of course, a scenario with a query can achieve higher utility and outperform a matching without pre-screening/query. Therefore, figure 2 is not informative. I found the left part of Table 1 very informative, though. It shows that the Greedy algorithm can find the optimal query in 90 graphs out of 100 graphs. It implies that the Greedy algorithm is a powerful method. 3. There is no complexity analysis of the proposed algorithms. That would be great if the authors provide the run time of the proposed algorithms. To find an optimal query, we have to find the optimal matching associated with each query. Therefore, I feel finding a (sub)optimal query would be very expensive. By the right part of table 1, a random query can improve the objective function of the problem (1) by 50% as compared to a scenario without query. Given the fact that choosing a random query does not have any computational cost, a random query may be a better choice as compared to the Greedy or MCTS algorithm. 4. This paper compares its results with [10]. Since [10] considers a different model, the authors should mention how the algorithm of [10] can solve optimization problem (1). 5. Since [15] does not use a query to find the optimal matching, it is not fair to compare MCTS/Greedy algorithm with the algorithm of [15]. UPDATE: The authors have addressed my concecerns with the experiment section. Moreover, even though their proposed algorithms are simple and are commonly used in the literature, they show that they work on real data and in kidney exchange problem. Therefore, I would like to increase the score.
Correctness: Claims.propositions are correct. As I mentioned in the previous part, this paper proposes an algorithm to find the optimal query. However, it does not provide an algorithm to find the optimal matching. To find the optimal query, we need to know the optimal matching and maximum utility/objective function for any given query. Any query, gives us a rejection vector $r$ and the rejection vector affects the optimal matching strategies $M^{max}(r)$ and $M^{FA}(r)$. Therefore, finding an algorithm for an optimal query without having an algorithm to find $M^{max}(r)$ or $M^{FA}(r)$ does not seem right.
Clarity: Yes, it is. It was easy to read and understand the model, main idea and emprical methodology.
Relation to Prior Work: Yes, it is. As I mentioned before, the model itself is new and makes the paper different from existing literature.
Reproducibility: Yes
Additional Feedback: That would be intresting if the authros try to find an algorithm which finds the optimal matching given a specific query. Then, the algorithm can be used in proposed MCTS or Greedy algorithm to find the best query.
Summary and Contributions: This paper points out the unrealistic assumption of prior work in the kidney exchange problem and proposes a multi-stage optimization problem with both the pre- and post-match phases. The authors also demonstrate that this problem set is a mathematically challenging combinatorial problem, and propose a greedy heuristic and Monte Carlo tree search method to solve this problem. Finally, through synthetic data and real data, they experimentally confirm that their pre-screening has a significant effect on performance.
Strengths: The authors suggest a new research direction in the kidney exchange problem and show that the problem they propose is theoretically and empirically meaningful. Also, since their problem setting considers the structure of the actual kidney exchange at the application level, this paper seems to be a good initial study for those who study this field.
Weaknesses: (1) Even considering this is an initial study through a new problem formulation, the algorithmic contribution proposed in the paper is insufficient. They experimentally show that the simple greedy method and the Monte Carlo tree search method are effective in this NP-hard problem, but there is no mathematical discussion with this claim regarding the characteristics of the data. Alternatively, suggesting an algorithm modification that considers the characteristics of the problem can also be a way for algorithmic contributions (2) If simple greedy or Monte Cralot tree search in the kidney exchange problem ensures sufficient performance, formulating this problem as an edge query problem does not seem to be of much value. The problem of estimating the probability distribution or graph assuming given in this problem seems more realistic and important.
Correctness: The claims and methods are clear and correct
Clarity: (1) The abstract part is too long. The detailed explanations at the beginning of the abstract seem to need to be reduced. (2) In 4.1 and 4.2, it is inconvenient to read because the experimental setting and the experimental result are mixed within one paragraph. (3) Multistage and multi-stage are used interchangeably.
Relation to Prior Work: This paper introduces a sufficient level of prior work, and the authors compare their contributions with existing research well.
Reproducibility: Yes
Additional Feedback:
Summary and Contributions: This paper proposed the policy-constrained edge query model for kidney exchange problem, where a decision-maker selects a set of potential edges to pre-screen and then constructs a final packing using a fixed algorithm. This model generalizes existing models in the literature, as edge failure probabilities depend on whether or not the edge is pre-screened. The authors proved that the edge query problem is non-monotonic and non-submodular in the set of queried edges when the decision-maker uses a max-weight packing policy. Experiments are conducted on both simulated and real exchange data from the United Network for Organ Sharing (UNOS), showing that the proposed methods substantially outperform prior approaches.
Strengths: This paper considers the problem of kidney exchange, which is a practical real-world problem. The results of the experiments showing the performance of the algorithm are encouraging and the contribution has significant broader impact. Besides formulating the problem, the authors also prove the important properties (non-monotonic and non-submodular) of the problem and proposed baseline solutions with experiments, ensuring the soundness of the claims. The problem definition, proofs of propositions and algorithm description in section 2, 3 and appendix are written in a detailed and clear way. The writing of this paper is friendly to readers who are not familiar with the field.
Weaknesses: The proposed solutions to the problem (Monte Carlo Tree Search and the Single Stage Greedy Algorithm) have been used in other applications. The authors are encouraged to clarify special tweaks of these algorithms to make them work on the specific application.
Correctness: Yes.
Clarity: The writing of this paper is very clear and friendly to readers who are not familiar with the field. In section 2, the problem definition and proofs of propositions are provided, with detailed definitions and explanations of important concepts (matching policy, single or multi-stage setting, etc). Proofs of important properties are provided. In section 3, the algorithm description is provided in a detailed and clear way. The abstract and introduction of this paper are brief and clear, giving a good overview of the main idea.
Relation to Prior Work: The relation to prior work is provided clearly in the introduction section. Existing matching algorithms aiming to mitigate transplant failures usually require modifying fielded matching algorithms, which in many cases would require changing the law or policy. Pre-screening potential transplants can avoid failures without modifying the matching algorithm, but it is costly as it requires scarce time and resources. To overcome these problems, the multistage stochastic optimization problem formulation is proposed.
Reproducibility: Yes
Additional Feedback: