CPS 196.2 Kidney exchanges (largely follows Abraham, Blum, Sandholm 2007 paper)Kidney transplantsAn imaginary kidney exchange with moneySelling kidneys is illegal!Kidney exchangeKidney exchange (3-cycle)Another exampleMore complex exampleSolving kidney exchange as maximum weighted bipartite matchingWhich solution is better?Long cycles are impracticalDifferent representationSlide 13Market clearing problemSlide 15Special case: k=2ComplexityAn integer programming formulationAnother integer programming formulation (turns out better)Program sizeAnother integer program (not in paper)Other applicationsCPS 196.2Kidney exchanges(largely follows Abraham, Blum, Sandholm 2007 paper)Vincent Conitzer [email protected] transplants•Kidneys filter waste from blood•Kidney failure results in death in months•Dialysis: regularly get blood filtered in hospital using external machine–Low quality of life•Preferred option: kidney transplant–Cadaver kidneys–Donation from live patient (better)•Must be compatible•Shortage of kidneys…An imaginary kidney exchange with moneypatient 1bids $7000“donor” 1asks $6000patient 2bids $8000donor 2asks $4000patient 3bids $9000donor 3asks $7000patient 4bids $6000donor 4asks $5000compatibilitiesSelling kidneys is illegal!•Large international black market–Desperate people on both ends…•What can we do legally?Kidney exchangepatient 1donor 1(patient 1’s friend)patient 2donor 2(patient 2’s friend)Kidney exchange (3-cycle)patient 1donor 1(patient 1’s friend)patient 2donor 2(patient 2’s friend)patient 3donor 3(patient 3’s friend)Another examplepatient 1donor 1(patient 1’s friend)patient 2donor 2(patient 2’s friend)patient 3donor 3(patient 3’s friend)patient 4donor 4(patient 4’s friend)More complex examplepatient 1donor 1(patient 1’s friend)patient 2donor 2(patient 2’s friend)patient 3donor 3(patient 3’s friend)patient 4donor 4(patient 4’s friend)Solving kidney exchange as maximum weighted bipartite matchingpatient 1donor 1(patient 1’s friend)patient 2donor 2(patient 2’s friend)patient 3donor 3(patient 3’s friend)patient 4donor 4(patient 4’s friend)111110000Which solution is better?patient 1donor 1(patient 1’s friend)patient 2donor 2(patient 2’s friend)patient 3donor 3(patient 3’s friend)patient 4donor 4(patient 4’s friend)Long cycles are impractical•All patients in a cycle must be operated on simultaneously–Otherwise donor can wait for friend to receive kidney, then back out–Contracts to donate an organ not binding•If last-minute test reveals incompatibility, whole thing falls apart•Require each cycle has length at most kDifferent representationpatient 1donor 1(patient 1’s friend)patient 2donor 2(patient 2’s friend)patient 3donor 3(patient 3’s friend)patient 4donor 4(patient 4’s friend)1234edge from i to j = patient i wants donor j’s kidneyDifferent representationpatient 1donor 1(patient 1’s friend)patient 2donor 2(patient 2’s friend)patient 3donor 3(patient 3’s friend)patient 4donor 4(patient 4’s friend)1234edge from i to j = patient i wants donor j’s kidneyMarket clearing problem•Try to cover as many vertices as possible with (vertex-)disjoint cycles of length at most k123412341234k=2k=3k=2,3Market clearing problem•Try to cover as many vertices as possible with (vertex-)disjoint cycles of length at most k1234567Special case: k=2•If edges go in both directions, replace by undirected edge•Remove other edges1 2 3 45•Maximum matching problem!Complexity•k = 2: in P by maximum matching•k = number of vertices (no constraint): in P by maximum weighted bipartite matching•k = 3, 4, 5, …: NP-hard!An integer programming formulation•For each edge from i to j, make a binary variable xij–1 if i gets j’s kidney, 0 otherwise•maximize Σijxij•subject to:•for every i: Σjxij = Σjxji –(number of kidneys received by i = number of kidneys given by i)•for every j: Σixij ≤ 1–(j gives at most 1 kidney)•for every path i1 i2 … ik ik+1 with i1 ≠ ik+1: Σ1≤j≤kxijij+1 ≤ k-1–(no path of length k that doesn’t end up where it started, hence no cycles greater than k)Another integer programming formulation(turns out better)•For each cycle c of length at most k, make a binary variable xc–1 if all edges on this cycle are used, 0 otherwise•maximize Σc|c|xc•subject to:•for every vertex i: Σc: i in cxc ≤ 1–(every vertex in at most one used cycle)Program size•Even for small k, number of paths/cycles is too large in reasonably large exchanges•Solution: generate constraints/variables on the fly during solving–Constraint/column generationAnother integer program (not in paper)•Say an “event” is a set of simultaneous operations•Denote events by t = 1, …, T (how big should T be?)•For each edge from i to j, for each t, make a binary variable xijt–1 if i gets j’s kidney in event t, 0 otherwise•maximize Σi,j,txijt•subject to:•for every i, t: Σjxijt = Σjxjit –(number of kidneys received by i in event t = number of kidneys given by i in event t)•for every j: Σi,txijt ≤ 1–(j gives at most 1 kidney overall)•for every t: Σi,jxijt ≤ k –(at most k operations per event)Other applications•Barter exchanges: agents want to swap items without paying money•Peerflix (DVDs)•Read It Swap It (books)•Intervac (holiday houses)•National odd shoe exchange–People with different foot