For the Kidney Exchange Problem (KEP), one has a barter exchange market represented by a digraph with vertices corresponding to either immunologically incompatible donor-acceptor pairs, non-directed donors, cadavers, or unpaired recipients, and directed edges corresponding to possible kidney exchanges. The objective is then to solve the associated clearing problem of finding an above threshold weight partition of the network into vertex-disjoint transplant cycles and/or paths. In this work – with a primary motivation being the broad applicability of the KEP model to barter exchange markets of indivisible goods – we conduct a theoretical investigation of the problem of uniformly, and in this sense “fairly”, sampling witnesses for a formalization of the KEP we denote KEP- \(\left( L_c,L_p,\varUpsilon \right) \) , where we have cycle and path vertex-wise length constraints \(L_c\) and \(L_p\) , respectively, and where we require that the sum of all edge weights in a partition is at least \(\varUpsilon \in \mathbb {N}_{0}\) . Here, for KEP- \(\left( \infty ,\infty ,0\right) \) , we provide an \(\mathcal {O} \left( 4^g \cdot n^4 \cdot m \right) \) time uniform sampling scheme (assuming access to an idealized coin flipping oracle) for networks on n vertices and m edges admitting bimodal embeddings (i.e., embeddings where each set of edges oriented away from a given vertex occur contiguously in a rotational ordering of edges incident to the vertex) on genus \(\le g\) surfaces, as well as a Fully Polynomial-time Almost Uniform Sampling (FPAUS) scheme for arbitrary genus digraphs. Subsequently, taking inspiration from recent rapid experimental advances in using boson sampling (respectively, Guassian boson sampling) to approximate the permanents (respectively, hafnians) of complex matrices, we reduce the uniform sampling problem for KEP- \(\left( L_c,L_p,\varUpsilon \right) \) to calculating permanents of hollow Hermitian \(\{-1,0,1\}\) matrices. However, we also moderate this latter finding by showing that no Fully Polynomial-time Randomized Approximation Scheme (FPRAS) for the permanent of such matrices unless \(NP = RP\) .

Fair Selection of Clearing Schemes for Kidney Exchange Markets

会议论文
发表日期：

2025年

查看全文

Robert D. Barish,
Tetsuo Shibuya

摘要

For the Kidney Exchange Problem (KEP), one has a barter exchange market represented by a digraph with vertices corresponding to either immunologically incompatible donor-acceptor pairs, non-directed donors, cadavers, or unpaired recipients, and directed edges corresponding to possible kidney exchanges. The objective is then to solve the associated clearing problem of finding an above threshold weight partition of the network into vertex-disjoint transplant cycles and/or paths. In this work – with a primary motivation being the broad applicability of the KEP model to barter exchange markets of indivisible goods – we conduct a theoretical investigation of the problem of uniformly, and in this sense “fairly”, sampling witnesses for a formalization of the KEP we denote KEP- \(\left( L_c,L_p,\varUpsilon \right) \) , where we have cycle and path vertex-wise length constraints \(L_c\) and \(L_p\) , respectively, and where we require that the sum of all edge weights in a partition is at least \(\varUpsilon \in \mathbb {N}_{0}\) . Here, for KEP- \(\left( \infty ,\infty ,0\right) \) , we provide an \(\mathcal {O} \left( 4^g \cdot n^4 \cdot m \right) \) time uniform sampling scheme (assuming access to an idealized coin flipping oracle) for networks on n vertices and m edges admitting bimodal embeddings (i.e., embeddings where each set of edges oriented away from a given vertex occur contiguously in a rotational ordering of edges incident to the vertex) on genus \(\le g\) surfaces, as well as a Fully Polynomial-time Almost Uniform Sampling (FPAUS) scheme for arbitrary genus digraphs. Subsequently, taking inspiration from recent rapid experimental advances in using boson sampling (respectively, Guassian boson sampling) to approximate the permanents (respectively, hafnians) of complex matrices, we reduce the uniform sampling problem for KEP- \(\left( L_c,L_p,\varUpsilon \right) \) to calculating permanents of hollow Hermitian \(\{-1,0,1\}\) matrices. However, we also moderate this latter finding by showing that no Fully Polynomial-time Randomized Approximation Scheme (FPRAS) for the permanent of such matrices unless \(NP = RP\) .