CS Paper Radar

Kidney Exchange with Dual Donors

Ioannis Caragiannis, Tomasz Filip Gawron, Kristoffer Arnsfelt Hansen, Yuchen Zhang

cs.GT ·submitted 2026-10-30 09:17 UTC · v1

Abstract

Kidney exchange programs enable patients with incompatible living donors to receive transplants by exchanging donors with other patient-donor pairs. Existing models typically assume either that each patient enrolls with a single donor, or that at most one of a patient's multiple alternative donors is selected to donate. In practice, however, a patient may have access to multiple willing but incompatible donors who are all prepared to donate simultaneously if doing so enables the patient to receive a kidney. We study a dual-donor kidney exchange model, in which a patient may enroll with up to two proxy donors and the exchange is allowed to utilize both, provided the patient receives a compatible transplant. This paradigm allows a patient to participate in an exchange cycle via one donor while their second donor initiates a donation chain---unlocking additional transplants without relying on altruistic donors. We formulate the resulting combinatorial optimization problems under realistic cycle and chain constraints, showing that utilizing both donors introduces sharp computational challenges compared to standard exchange, and we design new approximation algorithms with provable guarantees. We also study strategic manipulation when patients hide a donor, establishing the limits of deterministic mechanisms and showing how randomization achieves truthfulness with near-optimal welfare. Finally, our experiments on realistic synthetic graphs demonstrate that using both donors yields substantial gains in total transplants over selecting at most one---even when only a small fraction of patients enroll with two donors.

Closest papers

Nearest neighbours by meaning across the whole index.

Capacity Modification for Matching with Couples: An Integer Programming and Computational Study

cs.GT ·2026-10-23 ·Zexiao Wu, Genjiu Xu, Péter Biró
similarity 0.60
Abstract · 31 pages, 4 figures

We study capacity modification in the Hospitals/Residents problem with Couples, in which hospital capacities and a stable matching are jointly determined. Exact and Cutoff integer programming formulations are developed for the resulting problem. We assume that, for each couple, either both members are matched or neither is. For arbitrary strict preferences, every instance admits a stable matching after changing each hospital capacity by at most two. Total capacity increases by at most one, and this bound is tight. Under sub-responsive and sub-complete couple preferences, a stable matching exists after adding at most one position to each hospital. The total number of additions is at most the number of couples, and this bound is also tight. Computational experiments show that Exact formulations are modestly faster at fixed capacities, whereas Cutoff formulations perform substantially better in the minimum repair experiments and attain higher completion rates in markets with up to 30,000 doctors. Across 96,000 synthetic and reconstructed markets, small capacity changes restore existence whenever no stable matching exists at the original capacities.

0.25

Dynamic Pooling and Regional Participation in Deceased-Donor Organ Allocation

cs.GT econ.TH ·2026-09-16 ·Genta Okada
unusual similarity 0.58
Abstract · 47 pages, 3 figures

Moving from geographically fragmented to pooled waiting lists in deceased-donor organ transplantation can improve efficiency, but it raises concerns about regional fairness and participation incentives. This paper studies Pareto gains from such transitions in a multi-class queueing model with impatient agents, perishable items, and a tractable homogeneous compatibility friction. In contrast to standard approaches that emphasize static match quality or overlook regional incentives in dynamic contexts, this analysis identifies dynamic risk pooling as the primary source of Pareto improvements for regions. Pooling reduces organ waste resulting from stochastic supply-demand fluctuations, temporal mismatches, and random compatibility outcomes. Although this dynamic surplus theoretically enables Pareto improvements, a purely utilitarian policy that treats all patients equally across regions often fails to achieve these improvements when regions are asymmetric. In these situations, utilitarian redistribution removes an excessive number of organs from high-supply regions and violates their participation constraints. To address this conflict, it is demonstrated that the set of achievable utilities can be represented by mixtures of static priority index policies. Building on this structure, the Constrained Pareto Frontier Search (CPFS) is proposed as a polynomial-time procedure that computes an approximately optimal allocation policy with arbitrarily small participation-constraint violations. The results indicate that, by adjusting priority indices to ensure redistribution remains within the gains from pooled supply, demand, and compatibility risk, policymakers can achieve global efficiency while maintaining local participation incentives.

0.29

When Should AI Decide, Defer, and Deviate? Responsible Automation for Deceased Donor Kidney Allocation

cs.AI ·2026-10-28 ·Madeleine Pollack, Thomas Daillak, Mehmet Toner, Korkut Uygun, Heidi Yeh +1 more
unusual similarity 0.56
Abstract

We ask when an AI trained on historical decisions should be allowed to recommend decisions, defer to human experts, or in other cases, flag concerning patterns in data and deviate from past practice. This can be challenging because past decisions record what was done rather than what should have been done, and where data is sparse, a model's predictions may be too uncertain to act on. We provide a framework for addressing this problem using a case study in deceased-donor kidney allocation. Nearly 30% of kidneys recovered from deceased donors in the United States are never transplanted, largely because they are hard to place through the standard waitlist sequence. One can use AI to flag kidneys at risk of delayed or failed placement for out-of-sequence (OOS) allocation, but this comes at the cost of bypassing candidates higher on the waitlist. Thus, OOS allocation should only be used when the organ is demonstrably at high risk of discard on the standard sequence. Using Organ Procurement and Transplantation Network match-run data from 2016-2019 and 2023-2025 (excluding COVID-19-disrupted years), we build the Arbitrator framework, which combines various interpretable models and acts only when the uncertainty in their predictions cannot change the preferred action. Our Arbitrator resolves 93.5% of organ placement decisions using explicit medical criteria learned from data, and defers the remaining 6.5% to a human or a more complex model. We show that the Arbitrator correctly identifies 70.1% of historically discarded low-KDPI kidneys as OOS candidates, projecting that up to 43.9% of historically discarded kidneys could be flagged for expedited placement and potentially transplanted. We then exploit the interpretability of the Arbitrator to create an agentic audit comparing the learned rules to published clinical literature in order to flag decision-making patterns that are contentious.

0.33

Decentralized LLM Workflows via Sequential Auctions

cs.GT cs.AIcs.MA ·2026-10-15 ·Ian Gemp, Shubhendu Trivedi, Adam Fisch, Fantine Huot, Michael Kaisers +5 more
similarity 0.54
Abstract · 28 pages

We present a scalable framework for solving multi-step tasks through a decentralized market of self-interested agents. Prior theoretical work demonstrated that agents organized through sequential auctions can converge to a globally optimal policy in a Markov decision process (MDP), but relied on the restrictive assumption of the existence of perfect clones as a model of perfect competition. In reality, exact clones drive agent profit to zero, violating the natural risk-reward incentives of participants. Conversely, we empirically demonstrate that the opposite extreme, absence of competition, also leads to market failure and value extraction collapse. Between these two extremes, we investigate how heterogeneous agents can survive in markets that span the critical middle ground of imperfect competition. To be profitable, agents learn to strategically shade bids to secure positive individual profit margins, while still ensuring that the marketplace functions effectively enough so that collaborative tasks posed by market consumers can still be solved. We formulate and evaluate four bidding algorithms (Mirror Descent, Thompson Sampling, Bayes-Optimal, and PPO) across three auction protocols (1st-Price, 2nd-Price, and Credit-Conserving Vickrey). Across a diverse set of domains, we demonstrate that imperfect competition successfully sustains necessary agent profit margins while maintaining high task success rates at low costs.

0.28

Fairness and Non-wastefulness in Matching with Siblings and Initial Enrollments: Compatibility and Complexity

cs.GT ·2026-10-01 ·Haris Aziz, Gergely Csáji, Zhaohong Sun, Makoto Yokoo
similarity 0.52
Abstract

We study a two-sided matching problem between families and daycare centers in which a family may have multiple children with joint preferences, and some children may already be enrolled in daycare centers while seeking transfers. Our model combines and generalizes two well-studied matching frameworks: matching with couples and school choice with initial enrollments. The interaction between joint family preferences and initial enrollments creates fundamental challenges for the existence of desirable outcomes and the design of computationally efficient algorithms. Since stable matchings need not exist, we decompose stability into individual rationality, fairness, and non-wastefulness, and study the trade-off between fairness and non-wastefulness from two complementary directions. To preserve non-wastefulness, we first consider master-list-based approaches and show that they are insufficient in the presence of initial enrollments. We then introduce \emph{resettlement}, which protects displaced families by allowing them to return to their initial assignments, and develop a greedy improvement algorithm that establishes the existence of matchings satisfying non-wastefulness together with resettlement-based fairness. To preserve fairness, we first examine a generalized cutoff approach and then develop a fairness-preserving non-wasteful algorithm that guarantees fairness together with a relaxed notion of non-wastefulness. We further characterize the computational complexity of these solution concepts. While several fairness notions can be verified in polynomial time, deciding whether a non-wasteful matching satisfying them exists is NP-complete. Resettlement restores universal existence, but computing resettlement-based outcomes is PLS-hard, and verifying the stronger dominance-based fairness notion is coNP-complete.

0.18

Improved Combinatorial Auctions with and without Samples

cs.GT cs.DS ·2026-10-13 ·Aviad Rubinstein, Sahil Singla
similarity 0.51
Abstract · Abstract shortened to fit arXiv constraints

We give new mechanisms for combinatorial auctions in the offline, secretary, and prophet-with-samples models. Specifically, we obtain the following guarantees for social welfare maximization with $m$ items and $n$ XOS buyers: * In the prophet-with-samples version, buyers arrive in adversarial order and draw their values from independent distributions. We give a universally truthful, polynomial-time $(2+\eps)$-approximation mechanism using $O(\log\!\log m)$ samples from each distribution. The approximation factor is tight even for a single item and without the incentive constraints, due to the classic prophet inequality. Compared to the previous state-of-the-art with the same guarantees [Dütting--Kesselheim--Lucier--Reiffenhäuser--Singla (FOCS 2024)], our running time is exponentially faster, and our sample complexity is doubly-exponentially lower, resolving two explicit open problems by Dütting et al. * Using the same techniques, we also obtain improved mechanisms in the secretary and offline versions, where the values are worst-case, and buyers are processed in either random order (secretary) or without any timing restrictions (offline). After a long line of works, the state of the art in both models is an $O((\log\!\log m)^2)$-approximation due to [Assadi--Kesselheim--Singla (SODA 2021)], who explicitly ask whether it can be improved to $O(\log\!\log m)$. We indeed obtain an $O(\log\!\log m)$-approximate universally truthful mechanism for the secretary and offline models.

0.08

Revisiting EFX and fPO Allocations for Binary Chores

cs.GT ·2026-09-12 ·Zehan Lin, Xiaowei Wu, Shengwei Zhou
similarity 0.51
Abstract · 28 pages, no figure

We study fair and efficient allocations of indivisible chores under binary additive costs, with a focus on unequal entitlements and best-of-both-worlds guarantees. While binary valuations have been extensively studied for goods, their chore counterpart remains much less understood. A notable exception is due to Tao et al. (TCS 2025), who established that EFX and fPO are compatible for binary chores with equal entitlements. We revisit binary chores under unequal entitlements and establish the computation of allocations that satisfy WEFX and fPO. Our key technical contribution is a new lexicographic potential function tailored to chores: any allocation minimizing this potential ensures both WEFX and fPO. This potential further guides a polynomial-time local-search algorithm for computing allocations with such fairness and efficiency guarantees. For best-of-both-worlds guarantees, we show that unequal entitlements create a sharp obstruction: even with two agents and identical binary additive costs, no lottery can simultaneously satisfy ex-ante WEF and ex-post WEF1. In contrast, for equal entitlements, we construct in polynomial time a lottery that is ex-ante EF and fPO, while every realization is both EFX and fPO.

0.41

Envy-free Allocations with Individual Payments

cs.GT cs.DS ·2026-10-07 ·Robert Bredereck, Eva Deltl, Tanmay Inamdar, Pallavi Jain, Pranjal Pandey
survey similarity 0.51
Abstract

When an envy-free allocation of indivisible goods does not exist, monetary transfers can restore envy-freeness. Existing work on fair division with subsidies, however, typically assumes that these payments are provided by an external source, an assumption that may be unrealistic in many applications. We address this limitation by allowing only monetary transfers between agents, with each agent's payments constrained by their individual budget. We show that while it is polynomial-time tractable to determine whether a given allocation can be made envy-free by payments under individual budgets, the general problem of computing such an allocation from scratch is NP-hard, even when agents have relatively large budgets. Motivated by this intractability, we conduct a parameterized complexity analysis, establishing fixed-parameter tractability with respect to the number of goods or to the joint parameter number of agents and good types, and we provide efficient algorithms in several special cases. For explicitly listed items, our type-based algorithm answers the envy-freeness part of an open question of T. T. Nguyen and J. Rothe, "Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey."

0.15