Partitioned matching games for international kidney exchange
提出分区匹配博弈模型，用于国际肾脏交换中公平分配移植数量，并证明当每个国家拥有的顶点数不超过2时，核心非空性可多项式时间求解，不超过3时则为co-NP难。
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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>=</mml:mo> <mml:mo>(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> with an edge weighting w and a partition $$V=V_1 \cup \dots \cup V_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>V</mml:mi> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>V</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>∪</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>∪</mml:mo> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:math> . The player set is $$N = \{ 1, \dots , n\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>=</mml:mo> <mml:mo>{</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> , and player $$p \in N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> owns the vertices in $$V_p$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>p</mml:mi> </mml:msub> </mml:math> . The value v ( S ) of a coalition $$S \subseteq N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> is the maximum weight of a matching in the subgraph of G induced by the vertices owned by the players in S . If $$|V_p|=1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mo>|</mml:mo> </mml:mrow> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>p</mml:mi> </mml:msub> <mml:mrow> <mml:mo>|</mml:mo> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mrow> </mml:math> for all $$p\in N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> , then we obtain the classical matching game. Let $$c=\max \{|V_p| \; |\; 1\le p\le n\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mo>=</mml:mo> <mml:mo>max</mml:mo> <mml:mo>{</mml:mo> <mml:mo>|</mml:mo> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>p</mml:mi> </mml:msub> <mml:mo>|</mml:mo> <mml:mspace/> <mml:mo>|</mml:mo> <mml:mspace/> <mml:mn>1</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>p</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>n</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> be the width of ( N , v ). We prove that checking core non-emptiness is polynomial-time solvable if $$c\le 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mo>≤</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> but co--hard if $$c\le 3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mo>≤</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> . We do this via pinpointing a