skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


This content will become publicly available on February 11, 2026

Title: Partitioned matching games for international kidney exchange
Abstract We introduce partitioned matching games as a suitable model for international kidney exchange programmes, where in each round the total number of available kidney transplants needs to be distributed amongst the participating countries in a “fair” way. A partitioned matching game (N, v) is defined on a graph$$G=(V,E)$$ G = ( V , E ) with an edge weightingwand a partition$$V=V_1 \cup \dots \cup V_n$$ V = V 1 V n . The player set is$$N = \{ 1, \dots , n\}$$ N = { 1 , , n } , and player$$p \in N$$ p N owns the vertices in$$V_p$$ V p . The valuev(S) of a coalition $$S \subseteq N$$ S N is the maximum weight of a matching in the subgraph ofGinduced by the vertices owned by the players in S. If$$|V_p|=1$$ | V p | = 1 for all$$p\in N$$ p N , then we obtain the classical matching game. Let$$c=\max \{|V_p| \; |\; 1\le p\le n\}$$ c = max { | V p | | 1 p n } be the width of (N, v). We prove that checking core non-emptiness is polynomial-time solvable if$$c\le 2$$ c 2 but co--hard if$$c\le 3$$ c 3 . We do this via pinpointing a relationship with the known class ofb-matching games and completing the complexity classification on testing core non-emptiness forb-matching games. With respect to our application, we prove a number of complexity results on choosing, out of possibly many optimal solutions, one that leads to a kidney transplant distribution that is as close as possible to some prescribed fair distribution.  more » « less
Award ID(s):
1928930
PAR ID:
10600011
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
Springer Nature
Date Published:
Journal Name:
Mathematical Programming
ISSN:
0025-5610
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Given$$g \in \mathbb N \cup \{0, \infty \}$$ g N { 0 , } , let$$\Sigma _g$$ Σ g denote the closed surface of genusgwith a Cantor set removed, if$$g<\infty $$ g < ; or the blooming Cantor tree, when$$g= \infty $$ g = . We construct a family$$\mathfrak B(H)$$ B ( H ) of subgroups of$${{\,\textrm{Map}\,}}(\Sigma _g)$$ Map ( Σ g ) whose elements preserve ablock decompositionof$$\Sigma _g$$ Σ g , andeventually like actlike an element ofH, whereHis a prescribed subgroup of the mapping class group of the block. The group$$\mathfrak B(H)$$ B ( H ) surjects onto an appropriate symmetric Thompson group of Farley–Hughes; in particular, it answers positively. Our main result asserts that$$\mathfrak B(H)$$ B ( H ) is of type$$F_n$$ F n if and only ifHis. As a consequence, for every$$g\in \mathbb N \cup \{0, \infty \}$$ g N { 0 , } and every$$n\ge 1$$ n 1 , we construct a subgroup$$G <{{\,\textrm{Map}\,}}(\Sigma _g)$$ G < Map ( Σ g ) that is of type$$F_n$$ F n but not of type$$F_{n+1}$$ F n + 1 , and which contains the mapping class group of every compact surface of genus$$\le g$$ g and with non-empty boundary. 
    more » « less
  2. Abstract We define the half-volume spectrum$$\{{\tilde{\omega }_p\}_{p\in \mathbb {N}}}$$ { ω ~ p } p N of a closed manifold$$(M^{n+1},g)$$ ( M n + 1 , g ) . This is analogous to the usual volume spectrum ofM, except that we restrict top-sweepouts whose slices each enclose half the volume ofM. We prove that the Weyl law continues to hold for the half-volume spectrum. We define an analogous half-volume spectrum$$\tilde{c}(p)$$ c ~ ( p ) in the phase transition setting. Moreover, for$$3 \le n+1 \le 7$$ 3 n + 1 7 , we use the Allen–Cahn min-max theory to show that each$$\tilde{c}(p)$$ c ~ ( p ) is achieved by a constant mean curvature surface enclosing half the volume ofMplus a (possibly empty) collection of minimal surfaces with even multiplicities. 
    more » « less
  3. Abstract Let$$(h_I)$$ ( h I ) denote the standard Haar system on [0, 1], indexed by$$I\in \mathcal {D}$$ I D , the set of dyadic intervals and$$h_I\otimes h_J$$ h I h J denote the tensor product$$(s,t)\mapsto h_I(s) h_J(t)$$ ( s , t ) h I ( s ) h J ( t ) ,$$I,J\in \mathcal {D}$$ I , J D . We consider a class of two-parameter function spaces which are completions of the linear span$$\mathcal {V}(\delta ^2)$$ V ( δ 2 ) of$$h_I\otimes h_J$$ h I h J ,$$I,J\in \mathcal {D}$$ I , J D . This class contains all the spaces of the formX(Y), whereXandYare either the Lebesgue spaces$$L^p[0,1]$$ L p [ 0 , 1 ] or the Hardy spaces$$H^p[0,1]$$ H p [ 0 , 1 ] ,$$1\le p < \infty $$ 1 p < . We say that$$D:X(Y)\rightarrow X(Y)$$ D : X ( Y ) X ( Y ) is a Haar multiplier if$$D(h_I\otimes h_J) = d_{I,J} h_I\otimes h_J$$ D ( h I h J ) = d I , J h I h J , where$$d_{I,J}\in \mathbb {R}$$ d I , J R , and ask which more elementary operators factor throughD. A decisive role is played by theCapon projection$$\mathcal {C}:\mathcal {V}(\delta ^2)\rightarrow \mathcal {V}(\delta ^2)$$ C : V ( δ 2 ) V ( δ 2 ) given by$$\mathcal {C} h_I\otimes h_J = h_I\otimes h_J$$ C h I h J = h I h J if$$|I|\le |J|$$ | I | | J | , and$$\mathcal {C} h_I\otimes h_J = 0$$ C h I h J = 0 if$$|I| > |J|$$ | I | > | J | , as our main result highlights: Given any bounded Haar multiplier$$D:X(Y)\rightarrow X(Y)$$ D : X ( Y ) X ( Y ) , there exist$$\lambda ,\mu \in \mathbb {R}$$ λ , μ R such that$$\begin{aligned} \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C})\text { approximately 1-projectionally factors through }D, \end{aligned}$$ λ C + μ ( Id - C ) approximately 1-projectionally factors through D , i.e., for all$$\eta > 0$$ η > 0 , there exist bounded operatorsA, Bso thatABis the identity operator$${{\,\textrm{Id}\,}}$$ Id ,$$\Vert A\Vert \cdot \Vert B\Vert = 1$$ A · B = 1 and$$\Vert \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C}) - ADB\Vert < \eta $$ λ C + μ ( Id - C ) - A D B < η . Additionally, if$$\mathcal {C}$$ C is unbounded onX(Y), then$$\lambda = \mu $$ λ = μ and then$${{\,\textrm{Id}\,}}$$ Id either factors throughDor$${{\,\textrm{Id}\,}}-D$$ Id - D
    more » « less
  4. Abstract We study holomorphic mapsFfrom a smooth Levi non-degenerate real hypersurface$$ M_{\ell }\subset {\mathbb {C}}^n $$ M C n into a hyperquadric$$ {\mathbb {H}}_{\ell '}^N $$ H N with signatures$$ \ell \le (n-1)/2 $$ ( n - 1 ) / 2 and$$ \ell '\le (N-1)/2,$$ ( N - 1 ) / 2 , respectively. Assuming that$$ N - n < n - 1,$$ N - n < n - 1 , we prove that if$$ \ell = \ell ',$$ = , thenFis either CR transversal to$$ {\mathbb {H}}_{\ell }^N $$ H N at every point of$$ M_{\ell },$$ M , or it maps a neighborhood of$$ M_{\ell } $$ M in$$ {\mathbb {C}}^n $$ C n into$$ {\mathbb {H}}_{\ell }^N.$$ H N . Furthermore, in the case where$$ \ell ' > \ell ,$$ > , we show that ifFis not CR transversal at$$0\in M_\ell ,$$ 0 M , then it must be transversally flat. The latter is best possible. 
    more » « less
  5. Abstract LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$ [ 0 , 1 ] k where$$k \ge 2$$ k 2 . According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour)$$x_1, x_2, \ldots , x_n$$ x 1 , x 2 , , x n through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ i = 1 n | x i - x i + 1 | k 1 / k c k , where$$|x-y|$$ | x - y | is the Euclidean distance betweenxandy, and$$c_k$$ c k is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$ x n + 1 x 1 . From the other direction, for every$$k \ge 2$$ k 2 and$$n \ge 2$$ n 2 , there existnpoints in$$[0,1]^k$$ [ 0 , 1 ] k , such that their shortest tour satisfies$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$ i = 1 n | x i - x i + 1 | k 1 / k = 2 1 / k · k . For the plane, the best constant is$$c_2=2$$ c 2 = 2 and this is the only exact value known. Bollobás and Meir showed that one can take$$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ c k = 9 2 3 1 / k · k for every$$k \ge 3$$ k 3 and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$ c k = 2 1 / k · k , for every$$k \ge 2$$ k 2 . Here we significantly improve the upper bound and show that one can take$$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ c k = 3 5 2 3 1 / k · k or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$ c k = 2.91 k ( 1 + o k ( 1 ) ) . Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$ c 3 2 7 / 6 , which disproves the conjecture for$$k=3$$ k = 3 . Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed. 
    more » « less