Vese csere program matematikai modellje Varga G´abor May 1, 2011
1
Bevezet´ es
¨ Alvin E. Roth, Tayfun S¨ onmez, M. Utku Unver Kidney Exchange c´ım˝ u cikke alapj´ an azzal foglalkoztam, hogy hogyan lehet k¨ ul¨onb¨oz˝o algoritmusok seg´ıts´eg´evel minn´el hat´ekonyabb´ a tenni a vese csere programot. Manaps´ag egy vesebetegnek, ha donor szervhez akar jutni k´et lehet˝os´ege van: vagy van egy hozz´atartoz´oja aki hajland´ o donor lenni ´es ha ´eppen kompatibilisak, akkor elv´egezhat˝o a transzplant´ aci´ o; vagy beker¨ ul a halott vese v´ar´olist´ara, ahol bizonytalan id˝o m´ ulva kap egy ves´et. A fent eml´ıtett cikk szerz˝oinek az u ´j´ıt´asa az, hogy az ´el˝odonorral rendelkez˝ o betegek eset´en nem csak a donor ´es kedvezm´enyezettje k¨oz¨ott hajthat´ o v´egre a transzplant´ aci´ o, hanem lehets´eges az, hogy a donor m´asnak adja a ves´ej´et, annak ´erdek´eben, hogy kedvezm´enyezettje jobb min˝os´eg˝ u (vagy magasabb fok´ u kompatibilit´ assal rendelkez˝o) ves´et kapjon. A szerz˝ ok a k¨ ovetkez˝ o elj´ ar´asokat vizsg´alt´ak: 1. Donor ´ es kedvezm´ enyezettje k¨ ozti transzplant´ aci´ o: Leggyakrabban alkalmazott elj´ ar´ as. ´ 2. P´ aros vese csere: Jelenleg az Egyes¨ ult Allamokban m˝ uk¨od˝o elj´ar´as, de nem el´eg hat´ekony, mivel csak k´et donor-beteg p´ar k¨ozt teszi lehet˝ov´e a szervek cser´ej´et. 3. RSD-SR algoritmus: H´atr´anya, hogy az elj´ar´asban r´esztvev˝oknek nem garant´ al legal´ abb olyan j´o ´allapotot, mint amilyennel eleve rendelkeznek. 4. TTC elj´ ar´ as: Az ´el˝ odonorral rendelkez˝o betegek k¨ozt Pareto-hat´ekonyan1 osztja el a ves´eket, de nem veszi figyelembe a halott v´ar´olista lehet˝os´eg´et, amivel tov´ abb n¨ ovelhet˝ o a hat´ekonys´ag. 5. YRM-IGYT elj´ ar´ as: Ez az algoritmus figyelembe veszi a halott v´ar´olista lehet˝ os´eg´et, viszont statikusan tudja csak kezelni a probl´em´at, azaz nem veszi figyelembe azt, hogy a halottb´ol sz´armaz´o szerv min˝os´ege ´es megjelen´es´enek id˝ opontja bizonytalan. 6. TTCC algoritmus: A vizsg´alt algoritmusok k¨oz¨ ul a legel˝ony¨osebb, u ´jj´ıt´as a TTC-hez k´epest az, hogy a beteg magas priorit´ast kap a halott v´ar´olist´an, ha donorja ves´et ad a v´ar´olist´an lev˝oknek, a cikk szerz˝oi ezt javasolj´ak gyakorlati megval´ os´ıt´ asra. (T¨obb v´altozata is l´etezik.) 1 Egy rendszer Pareto-hat´ ekony, ha a rendszerben nem hajthat´ o v´ egre olyan v´ altoztat´ as, hogy a szerepl˝ ok k¨ oz¨ ul legal´ ab egy j´ ol´ ete n˝ o´ es a t¨ obbiek´ e nem cs¨ okken.
1
Ebben a munk´ amban ezen algoritmusokat sz´am´ıtog´eppel implement´altam Mathematica nyelven.
2
Vese ´ at¨ ultet´ es jelent˝ os´ ege ´ es probl´ em´ ai
A vese transzplant´ asi´ o a leghat´ekonyabb kezel´ese a komoly vesemegbeteged´eseknek, hiszen transzplant´ aci´ o r´ev´en nagym´ert´ekben n˝o a beteg ´eletmin˝os´ege (egy ´at¨ ultetett vese ´elettartama ak´ ar 30 ´ev is lehet). Emellett az ´el˝odonor sz´am´ara a vese´at¨ ultet´es kock´ azata alacsony. Az Egyes¨ ult ´allamokban t¨obb, mint 55000 beteg v´ar vese transzplant´ aci´ ora, azonban a halottb´ol sz´armaz´o ves´ekb˝ol hi´any van ´evente k¨ or¨ ulberl¨ ul 3000-en halanak meg a halott v´ar´olist´an. Ez´ert lehet sz¨ uks´eg a lentebb ismertetett elj´ asokra, melyek r´ev´en mind az ´at¨ ultetett ves´ek sz´ama, mind a kompetibilit´ as foka nagy m´ert´ekben n¨ovelhet˝o. 2.0.1
Probl´ ema
Az ´ at¨ ultetett vese k´et forr´ asb´ ol sz´armazhat: 1. halottb´ ol ´es 2. ´el˝ o donorb´ ol. Jelenleg ha az ´el˝ odonor ves´eje biol´ogiai okokb´ol nem be¨ ultethet˝o, akkor vagy a halott vese v´ ar´ olist´ ara ker¨ ul, vagy p´aros vese csere elj´ar´as´at alkalmazz´ak. Azonban ez nem el´eg hat´ekony, mivel megfelel˝o algoritmussal n¨ovelhet˝o mind a be¨ ultetett ves´ek sz´ ama, mind a kompatibilit´as foka. 2.0.2
Kompatibilit´ asi t´ enyez˝ ok.
A f˝ o t´enyez˝ o, amely meghat´ arozza egy vese be¨ ultethet˝os´eg´et az a donor ´es a p´ aciens v´ercsoportja. N´egyf´ele f˝o v´ercsoport l´etezik: 0,A,B,AB. Az al´abbi t´ abl´ azat a v´ercsoport ´es a be¨ ultethet˝os´eg k¨oz¨otti kapcsolatot mutatja. Donor v´ercsoporja 0 A B AB
Kedvezm´enyezett lehets´eges v´ercsoportja 0,A,B,AB A,AB B,AB AB
Ugyancsak jelent˝ os t´enyez˝ o egy p´aciens sz´am´ara a saj´at szervezete ´es a donor szerv HLA antig´en beli k¨ ul¨ onbs´egei. A donor ´es a p´aciens HLA t´ıpus beli k¨ ul¨ onbs´egei cs¨ okkentik a be¨ ultetett vese ´elettartam´at. ´ o donorb´ol A be¨ ultetend˝ o vese vese harmadik f˝o tulajdons´aga a sz´armaz´asa. El˝ at¨ ´ ultetett vese ´elettertama ´ altal´aban nagyobb, mint a halottb´ol sz´armaz´o´e. Egy p´ aciens a fenti t´enyez˝ ok alapj´an hat´arozza meg a preferenci´ait a ves´ekr˝ol.
2
3
A vese csere programban alkalmazhat´ o algotitmusok
Az algoritmusokat el˝ osz¨ or az eredeti alkalmaz´asukban mutatjuk be, ezut´an megadjuk a vese csere programmal val´o anl´ogi´at. Ezut´an r´amutatunk az elj´ar´asok el˝ onyeire, esetleges hi´ anyoss´ agaira.
3.1
RSD-SR elj´ ar´ as, Koll´ egiumi f´ er˝ uhelyek kioszt´ asa
Az RSD-SR (random serial-dictatorship with squatting rights) algoritmust el˝osz¨or ´ koll´egiumi szob´ ak kioszt´ as´ ara haszn´alt´ak az Egyes¨ ult Allamokban. Adottak di´ akok, akik m´ ar elfoglaltak egy szob´at, amit v´eletlenszer˝ uen kiosztottak nekik ´es vannak olyanok, akiknek m´eg nincs szob´ajuk. Minden lak´o d¨ont, hogy r´eszt vesz-e a szob´ ak u ´jraelszot´ as´ aban, ha nem vesz r´eszt, akkor a jelenlegi szob´aj´at kapja meg, ezut´ an elj´ ar´ asban r´esztvev˝ok k¨oz¨ott l´etrehozunk egy v´eletlenszer˝ u sorrendet. Az els˝ o di´ ak megkapja az ´altala legjobba prefer´alt u ¨res szob´at, a m´ asodik a marad´ek szob´ ak k¨ oz¨ ul a neki legjobban tetsz˝ot ´es ´ıgy tov´abb. Az al´ abbi t´ abl´ azat az RSD-SR elj´ar´as ´es a vesecsre program t´enyez˝oi k¨ozti megfeleltet´est mutatja: RSD-SR elj´ ar´ asban szob´ ak szob´ aval rendelkez˝ o di´ akok szob´ aval nem rendelkez˝ o di´akok
Vesecsre programban ves´ek ´el˝o donorral rendelkez´o p´aciensek ´el˝o donorral nem rendelkez´o p´aciensek
A probl´ema az, hogy a mechanizmus nem el´eg hat´ekony, mert a m´ar szob´aval rendelkez˝ o r´esztvev˝ oknek nem garant´alja, hogy jobban prefer´alt szob´at kapnak a saj´ atjuk´en´ al.
3.2
TTC algoritmus, Lak´ aspiac
A TTC (top trading circles) algoritmus haszn´alata a lak´aspiacon mer¨ ult fel, a c´el Pareto-hat´ekonyan elosztani a tulajdonosok k¨ozt a h´azakat, u ´gy, hogy a piacon nincs p´enz. Adottak h´ azak ´es h´aztulajdonosok ´es minden tulajdonosnak van egy szigor´ u preferencia sorrendje a h´azakon. Az algoritmus sor´an minden l´ep´esben el˝ o´ all´ıtunk egy ir´ any´ıtott gr´ afot, melynek cs´ ucsai a h´azak ´es a tulajdonosok, ´eleit pedig u ´gy hat´ arozzuk meg, hogy minden h´azb´ol vezet egy ´el a tulajdonosa fel´e ´es minden tulajdonosb´ ol a sz´ am´ara legjobban tetsz˝o h´az fel´e. Ekkor a gr´afban, mivel v´eges, van egy k¨ or ami ment´en v´egrehajthat´ok a lak´asok cser´eje, ezut´an u ´jra megkonstru´ aljuk a gr´ afot u ´gy, hogy a sz´obanforg´o lak´asok ´es tulajdonosok nem vesznek r´eszt t¨ obb´e az elj´ar´asban ´es ´ıgy folytatjuk tov´abb, addig am´ıg minden tulajdonosnak nem lesz h´aza. Az al´ abbi t´ abl´ azat a TTC algoritmus ´es a vesecsre program t´enyez˝oi k¨ozti megfeleltet´est mutatja: TTC elj´ ar´ asban lak´ astulajdonosok lak´ asok
Vesecsre programban ´el˝ odonorral rendelkez˝o p´aciensek ´el˝o donorok
3
Az algoritmus kiz´ ar´ olag az ´el˝odonorall rendelkez˝o p´acienseket veszi figyelembe. A halott v´ ar´ olista lehet˝ os´eg´et is bev´eve az elj´ar´asba a hat´ekonys´ag tov´abb n¨ ovelhet˝ o. 3.2.1
Egy p´ elda a TTC algoritmus menet´ ere t8
h8
t7
h7
t6
t8
h6
h8
t7
h7
t6
h6
h9
t5
h9
t5
t9
h5
t9
h5
h10
t4
h10
t4
t10
h4
t10
h4
h1 t8
t1
h2
h8
1. l´ep´es t7 h7
t2
h3
h1
t3
t8
t1
h2
h8
2. l´ep´es t7 h7
t2
h3
t3
h10
t4
h10
t4
t10
h4
t10
h4
h1
h3
t1
h1
t3
3.l´ep´es
h3
t1
t3
4.l´ep´es
Az 1. l´ep´esben megkonstru´alunk egy i´any´ıtott p´aros gr´aftot, melynek egyik cs´ ucsai a tulajdonosok (t1 , t2 , · · · , t10 ) ´es a h´azaik (h1 , h2 , · · · , h10 ). Minden h´ azb´ ol vezet egy ´el a tulajdonosa fel´e ´es minden tulajdonosb´ol az ´altala legjobban prefer´ alt h´ az fel´e. 2. l´ep´esben megkeress¨ uk a k¨or¨oket a gr´afban: h2 → t2 → h6 → t6 → h9 → t9 → h2 ´es h5 → t5 → h5 . Ezen k¨or¨ok ment´en v´egrehajthat´ o a h´ azak cser´eje. Nyilv´anval´oan ´ıgy minden tr´esztvev˝o legal´abb olyan j´ ol j´ ar, mintha nem vett volna r´eszt az elj´ar´asbvan, hiszen ha saj´at h´az´at prefer´ alja a t¨ obbivel szemben, az a gr´afban egy hurok´elt jelent ´es akkor e ment´en hajt´ odik v´egre a csere. Az algoritmus az el˝obb meghat´arozott k¨or¨ok beli cs´ ucsok n´el¨ ul folytat˝ odik tov´ abb (3. l´ep´es). A 4. l´ep´esben azon h´aztulajdonosok, akik az ´eppen let¨ or¨ olt k¨ or¨ ok beli h´azakat prefer´alt´ak a preferenciasorrendj¨ uknek megfelel˝ o k¨ ovetkez˝ o h´ azra mutatnak.
3.3
YRMH-IGYT elj´ ar´ as
Az YRM-IGYT algoritmus (you reques my house-I get your turn) algoritmus az RSD-SA elj´ ar´ as hi´ anyoss´ againak megold´as´ara tal´alt´ak ki. N´eh´any di´aknak 4
van (nem biztos, hogy neki tetsz˝o) szob´aja, n´eh´anynak nincs. Minden di´aknak van egy preferenciasorrendet a szob´akon. V´eletlenszer˝ uen sorbarendezz¨ uk a di´ akokat, majd sorban a di´ akok rendre r´amutatnak a legjobban prefer´alt szob´ara. Ha a szoba u ¨res u ¨res, akkor a di´ak megkapja a szob´at ´es t¨obb´e sem a di´ak, sem a szoba nem szerepel az elj´ ar´ asban, ha foglalt, akkor a szoba lak´oja a sor elej´ere ker¨ ul ´es ´ıgy folytat´ odik az elj´ ar´as. Az elj´ar´as sor´an az al´abbi esetekben hajtjuk v´egre a szob´ ak cser´ej´et l1 , l2 , · · · , ln lak´ok k¨oz¨ott: • l1 l2 szob´ aj´ at, l2 l3 -´et · · · ,ln l1 -´et szeretn´e (k¨or ment´en) • l1 l2 szob´ aj´ at, l2 l3 -´et · · · ,ln egy u ¨res szob´at szerete (´ ut ment´en) Az al´ abbi t´ abl´ azat az YRMH-IGYT elj´ar´as ´es a vesecsre programban t´enyez˝oi k¨ ozti megfeletet´est mutatja. YRMH-IGYT elj´ ar´ asban lak´ assal rendelkez˝ o di´ akok m´ ar elfoglalt lak´ asok lak´ assal nem rendelkez˝ o di´akok el nem foglalt lak´ asok
Vesecsre programban ´el˝odonorral rendelkez˝o p´aciensek ´el˝o donorok v´ar´olist´as p´aciensek halottb´ol sz´armaz´o ves´ek
Ez az elj´ ar´ as pareto hat´ekonya osztja el a szob´akat a hallgat´ok k¨ozt. Viszont az anal´ ogia a k´et probl´ema k¨ ozt nem vesz figyelembe egy fontos k¨ ul¨onbs´eget, azt hogy az el nem foglalt lak´ asokkal szemben, a halottb´ol sz´armaz´o ves´ek min˝os´ege, el´erhet˝ os´eg´enek id˝ opontja nem pontosan meghat´arozott. Ez´ert az YRMH-IGYT elj´ ar´ as m´ odos´ıt´ asra szorul.
5
3.3.1 h3
Egy p´ elda az YRMH-IGYT elj´ ar´ asra: h6
h2
h5
h8
h1
h7
h4
sz1 sz2 sz3 sz4 sz5 sz6 sz7 sz8 h6
h2
sz1 sz2 sz3
1. l´ep´es h5 h8
h7
h4
sz5 sz6 sz7 sz8 3. l´ep´es h8 h1
sz2 sz3
h1
sz5
h7
h3
h6
h2
h5
h8
h6
h2
sz1 sz2 sz3
h4
sz2 sz3
5. l´ep´es
h7
h4
sz1 sz2 sz3 sz4 sz5 sz6 sz7 sz8 2. l´ep´es h5 h8
h1
h7
h4
sz5 sz6 sz7 sz8 4.l´ep´es h8 h1
sz7
h1
sz5
h7
h4
sz7
6. l´ep´es
Az 1. l´ep´esben megkunstru´aljuk a gr´afot, h1 , h2 , · · · , h8 a hallgat´okat jelenti, sz1 , sz2 , · · · , sz8 pedig a szob´akat. Egy hallgat´o ´es szoba k¨ozt fut ´el, ha a sz´ oban forg´ o hallgat´ onak m´ ar megkapta a szob´at (k´ek ´elek) ´es a hallgat´okat v´eletlenszer˝ uen sorbarendezz¨ uk. A 2. l´ep´esen a sorrend szerint els˝o hallgat´o, h3 a negyedik szob´ at szeretn´e, amit meg is kap, mivel ennek a szob´anak m´eg nincs tulajdonosa, ezut´ an m´ ar sem a hallgat´o, sem a szoba nem fog r´eszt venni az elj´ ar´ asban (3. l´ep´es). A 4. l´ep´esben egy u ´t alakult ki, mivel h6 a hatodik szob´ at szeretn´e, aminek m´ar van tulajdonososa (h5 ) ´es most ˝o kapja meg a jogot, hogy szob´ at v´ alasszon att´ol f¨ uggetlen¨ ul, hogy hol szerepel a sorrendben. Mindez addig folytat´ odott m´ıg valaki egy u ¨res szob´ara nem mutatott. A szob´ ak kioszt´ asa v´egrehajthat´o a h6 → sz6 → h5 → sz1 → h2 → sz8 u ´t ment´en. Az 5. l´ep´esben megint let¨or¨olj¨ uk az u ´jonnan szob´at kapott hallgat´ okat ´es szob´ aikat. A 6. l´ep´esben a 4. l´ep´eshez hasonl´oan a hallgat´ok tulajdonossal rendelkez˝ o szob´ akra mutatnak, viszont itt egy k¨or alakul ki. Ekkor a h8 → sz7 → h4 → sz3 → h8 k¨or ment´en hajthat´ok v´egre a sz´ob´ak cser´ei. Az elj´ ar´ as addig folytat´ odik, m´ıg minden hallgat´onak nincs szob´aja.
3.4
TTCC elj´ ar´ as
A TTCC algoritmus (top trading cicles and chains) a TTC tov´abbfejleszt´ese a a vese csere probl´em´ ara. Az algoritmus minden l´ep´esben el˝o´all´ıtunk egy G ir´ any´ıtott gr´ afot, melynek cs´ ucsai a p´aciensek (p1 , p2 , · · · , pn ), a donorok (v1 , v2 , · · · , vn ) ´es a halott v´ ar´olista lehet˝os´ege (w). Ha egy p´aciens a halott v´ ar´ olist´ at prefer´ alja, az azt jelenti, hogy a saj´at donor´anak ves´ej´e´ert cser´ebe ˝o 6
kap egy kedvezm´enyezett helyet a v´ar´olist´an. Minden donort´ol fut ´el a kedvezm´enyezettj´ehez ´es minden p´acienst˝ol az ´altala legjobban prefer´alt donorhoz, vagy a halott v´ ar´ olist´ ahoz. Ezut´an a k¨ovetkez˝o t¨ort´enik: • ha van ir´ any´ıtott k¨ or, akkor a k¨or ment´en v´egrehajthat´ok a transzplant´aci´ok, • ha nincs ir´ any´ıtott k¨ or, akkor minden pi pontb´ol indul u ´t w-be. Ekkor ezen utak (w-l´ ancok) valamelyike ment´en hajthat´ok v´egre a transzplant´aci´ok, u ´gy, hogy az u ´t v´eg´en lev˝o p´aciens donora beker¨ ul a halott v´ar´olist´ara. Az algoritmus addig fut, m´ıg minden p´aciensnek nincs donora, vagy egy kedvezm´enyezett helye a halott v´ ar´olist´an. 3.4.1
P´ eld´ ak a w-l´ ancok kiv´ alaszt´ as´ asnak szab´ aly´ ara
Az algoritmus sor´ an a halott v´ar´olist´aba vezet˝o utakat h´ıvjuk w-l´ancoknak. A w l´ ancok utols´ o p´ aciens´ehez tartoz´o donor ves´ej´et megtarthatjuk, ami azt jelenti, hogy az elj´ ar´ as k¨ ovetkez˝o l´ep´es´eben e donor ves´eje nem ker¨ ul be a halott v´ ar´ olist´ aba, hanem a m´eg ves´et nem kapott p´aciensek mutathatnak r´a. P´eld´ak w l´ ancok kiv´ alaszt´ as´ anak szab´aly´ara: • V´ alasszunk minim´ alis w-l´ancot ´es t´avol´ıtsuk el, vagy tartsuk meg. • V´ alasszunk a maxim´ alis w-l´ancot ´es t´avol´ıtsuk el, vagy tartsuk meg. • Adjunk meg priorit´ asi sorrendet a donor p´aciens p´arok k¨oz¨ott ´es v´alasszuk mindig azt a w-l´ ancot, amely a legmagasabb priorit´as´ u p´arral kezd˝odik, majd t´ avol´ıtsuk el, vagy tartsuk meg. • Adott meg prorit´ asi sorrend a p´arokon, (0-´as donorral magasabb), v´alasszuk a legnagyobb priorit´ as´ u p´arral kezd˝od˝o w-l´ancot ´es tartsuk meg, ha a donor 0-´ as, ellenkez˝ o esetben t´avol´ıtsuk el. A TTCC elj´ ar´ as miatt a v´ ar´olist´an lev˝o 0-´as v´ercsoportuak h´atr´anyba ker¨ ulhetnek, mivel nekik csak 0-´ as v´ercsoport´ u donor megfelel˝o ´es a TTCC elj´ar´as r´ev´en t¨ obb nem 0-´ as szerv ker¨ ul a halott v´ar´o list´ara, mint amennyi beker¨ ul oda. A legut´ obbi w l´ anc kiv´ alaszt´ asi szab´allyal kompenz´alaht´o a v´ar´olist´an lev˝o 0-´as v´ercsoport´ uak h´ atr´ anybaker¨ ul´ese, hiszen azon w-l´ancokat prefer´aljuk, ahonnan 0-´ as szerv ker¨ ul a v´ ar´ olist´ ara.
7
3.5
Egy p´ elda a TTCC elj´ ar´ asra p8
d8
p7
d7
p6
p8
d6
d8
p7
d7
p6
d6
d9
p5
d9
p5
p9
d5
p9
d5
p4
d10
d4
p10
w
d10 p10 d1
p1
p8
d8
p2
d2
d3
p3
1. l´ep´es p7 d7
w
p4 d4
d1
p1
p8
d8
p2
d2
d3
p3
2. l´ep´es p7 d7
d9
p5
d9
p5
p9
d5
p9
d5
w
w
p4
p4
d4 d1 p8
p1 d8
d3
d4
p3
d1
3. l´ep´es p7 d7
p1
d3
p3
4. l´ep´es
d9
p5
p9
d5 w
p4 d4
d1
p1
d3
p3
5. l´ep´es Az els˝ o l´ep´esben megkonstru´aljuk a G gr´afot: minden donort´ol vezet ´el a kedvezm´enyezettj´ehez ´es a p´ aciensekt˝ol az ´altaluk legjobban prefer´alt donorhoz, vagy a halott v´ ar´ olist´ ahoz (w). Ekkor kialakult egy k¨or (2. l´epl´es), d2 → p2 → d6 → p6 → d1 0 → p1 0 → d2 ment´en v´egrehajthat´ok a transzplant´aci´ok. 3. l´ep´esben kit¨ or¨ olj¨ uk a az el˝ obbi cs´ ucsokat , majd (4. l´ep´es) az ´erintett p´aciensek preferenciasorrendj¨ uknek megfelel˝oen v´altoztatj´ak a prefer´alt lehet˝osget (halott v´ arolista, vagy donor). Ezut´ an egy olyan gr´afot kaptunk, amely nem k¨or, ekkor
8
a leghosszabb w-be vezet˝ ou ´t ment´en, d7 → p7 → d1 → p1 → d3 → p3 → d4 → p4 → w ment´en hajthat´ ok v´egre a transzplant´aci´ok, azaz a hetes sz´am´ u donor ves´eje beker¨ ul a a halott v´ ar´ olist´ara, p4 pedig kap egy halottb´ol sz´armaz´o ves´et.
3.6
TTCC elj´ ar´ as taktik´ az´ asbiztoss´ aga ´ es Pareto hat´ ekonys´ aga
A TTCC elj´ ar´ as p´eld´ aul az al´ abbi esetekben Pareto-hat´ekony: • Legr¨ ovidebb w-l´ ancot v´ alasztjuk ´es megtartjuk azt. • Priorit´ asi sorrendet defini´alunk a p´arok felett ´es mindig a legmagasabb priorit´ as´ u p´ arral kezd˝ od˝ o w-l´ancot v´alasztjuk. A TTCC elj´ ar´ as taktik´ az´ asbiztos2 p´eld´aul az al´abbi esetekben: • V´ alasszunk minim´ alis w-l´ancot ´es t´avol´ıtsuk el • Adott priorit´ asi sorrend a p´arokon, v´alasszuk a legnagyobb priorit´as´ u p´ arral kezd˝ od˝ o w-l´ ancot ´es t´avol´ıtsuk el, vagy tartsuk meg. • Adott prorit´ asi sorrend a p´arokon, (0-´as donorral magasabb) v´alasszuk a legnagyobb priorit´ as´ u p´ arral kezd˝od˝o w-l´ancot ´es tartsuk meg, ha a donor 0-´ as, ellenkez˝ o esetben t´ avol´ıtsuk el.
4
Tov´ abbi feladatok
Tov´ abbiakban ´erdemes lenne felhaszn´alni a meg´ırt algoritmusokat egy szimul´aci´ohoz, amellyel a k¨ ovetkez˝ o szempontok szerint lehetne ¨osszehasonl´ıtani ezeket az elj´ar´asokat: 1. Pareto-hat´ekonys´ ag. 2. A ves´et kap´ ok ar´ anya az ´el˝odonorral rendelkez˝ok k¨oz¨ott. 3. Az ´ at¨ ultetett ves´ek kompatibilit´as´anak foka. 4. A halott v´ ar´ olist´ an lev˝ ok eset´en a k¨ ul¨onb¨oz˝o v´ercsoportal rendelkez˝ok v´ arakoz´ asi idej´enek megv´altoz´asa. 5. A halott v´ ar´ olist´ an lev˝ o egyes betegek esetleges h´atr´anybaker¨ ul´ese. 6. A halott v´ ar´ olist´ ar´ ol be¨ ultetett ves´ek kompatibilit´as´anak foka. 7. Milyen hat´ assal van a kimenetelre, az ha az algoritmus nem taktik´az´asbiztos. Emellett ki lehetne eg´esz´ıteni az algoritmusokat azzal, hogy egy p´aciensek nem csak egy donorja lehet, hanem t¨obb is, ekkor a k¨or keres˝o algoritmust m´ odos´ıtani kell (p´eld´ aul sz´eless´egi bej´ar´assal), hiszen kihaszn´altuk azt, hogy minden cs´ ucsnak pontosan egy akifoka.
5
Felhaszn´ alt irodalom • Wikipedia ¨ • Alvin E. Rot, Tayfun S¨ onmez, M. Utku Unver: KIDNEY EXCHANGE
2 Egy rendszert taktik´ az´ asbiztosnak nevez¨ unk, ha a rendszer szerepl˝ oinek nem ´ all ´ erdek¨ ukben, hogy hazudjanak, vagy eltitkolj´ ak a tudom´ asukban lev˝ o inform´ aci´ okat.
9
