Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
J´at´ekelm´elet 3-4. el˝oad´as Sziklai Bal´azs ELTEcon
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
1
2
Egyetemi felv´eteli P´aros´ıt´asi probl´ema Gale-Shapley algoritmus ´ Ujraeloszt´ asi probl´ema H´azallok´aci´os probl´ema N´epszer˝ u eloszt´asok
3
Vesecsere program
4
Stabil szobat´ars probl´ema
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
H´azas´ıt´asi probl´ema I.
H´azas´ıt´asi probl´ema Adott n f´erfi ´es n n˝o, akiket ¨ ossze kell h´azas´ıtani. Minden f´erfi ´es n˝o fel´all´ıtott egy rangsort a m´asik nembeliekr˝ ol. C´el egy olyan teljes p´aros´ıt´as l´etrehoz´asa, amely mindenkinek megfelel.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
H´azas´ıt´asi probl´ema II. Defin´ıci´o A f´erfiak halmaz´at jel¨olje M, a n˝ ok´et W , egy adott p´aros´ıt´ast pedig a µ bet˝ u. Egy (m, w ) p´art (m ∈ M, w ∈ W ) blokkol´ o p´ arnak 0 nevez¨ unk, ha az m p´arja a µ p´aros´ıt´asban w , a w p´arja pedig m0 ´es mindketten prefer´alj´ak egym´ast a jelenlegi p´arjukhoz k´epest. Egy p´aros´ıt´ast stabilnak nevez¨ unk, ha nem l´etezik blokkol´o p´ar. Tov´abbi jel¨ol´esek Legyen a ∈ M ∪ W egy tetsz˝ oleges n˝ o, vagy f´erfi. Az a szem´ely m´asik nemen vett rendez´es´et ≺a -val jel¨ olj¨ uk, a p´arj´at pedig µ(a)-val.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
A Gale-Shapley algoritmus K´esleltetett elfogad´asi algoritmus (l´anyk´er˝ o v´altozat) 1
Minden fi´ u megk´eri a preferencialist´aj´an szerepl˝o els˝o l´any kez´et.
2
A l´anyok az ˝oket felk´er˝ o fi´ uk k¨ oz¨ ul a legjobban tetsz˝onek azt mondj´ak ’tal´an’ a t¨ obbit elutas´ıtj´ak.
3
Azok a fi´ uk, akiket elutas´ıtottak megk´erik a list´ajukon szerepl˝o m´asodik l´any kez´et.
4
Ha egy l´any a m´asodik k¨ orben jobb aj´anlatot kapott, akkor elk¨ uldi az eddig talonban tartott fi´ ut ´es az u ´jnak mondja azt, hogy tal´an.
5
A m´asodik k¨orben elutas´ıtott fi´ uk tov´abb folytatj´ak a l´anyk´er´est... Az algoritmus le´all, ha m´ar minden fi´ u meg´allapodott. A l´anyok ekkor elk¨ otelezik magukat. Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
H´azas´ıt´asi probl´ema III.
T´etel [Gale, Shapley 1962] Tetsz˝oleges G = (M, W , E ) p´aros gr´afban l´etezik stabil p´aros´ıt´as. Ha |M| = |W | = n, ´es E a teljes p´aros gr´af, akkor l´etezik teljes, vagyis n m´eret˝ u stabil p´aros´ıt´as. Bizony´ıt´as A l´anyk´er˝o algoritmussal.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
Feladat Feladat Alkalmazzuk a Gale-Shapley k´esleltetett elfogad´asi algoritmus´at!
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
H´azas´ıt´asi probl´ema IV.
T´etel Legyen ν ´es µ k´et stabil p´aros´ıt´as. Ha az a ∈ M ∪ W szem´elynek a ν-ben nem jutott p´ar, akkor µ-ben sem fog jutni.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
Feladat
N´ ev Anna Bea Csilla D´ori
Preferenciasorrend G H G F E H G H E F H G
N´ ev Endre Ferenc G´abor Henrik
Preferenciasorrend D A B C D C A B D C B A B A C
Feladat Alkalmazzuk a l´anyk´er˝ o algoritmust, majd a ford´ıtottj´at a leg´enyk´er˝o algoritmust! Mit vesz¨ unk ´eszre?
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
Feladat
L´anyk´er´es eredm´enye N´ ev Anna Bea Csilla D´ori
Preferenciasorrend G H G F E H G H E F H G
Sziklai Bal´ azs
N´ ev Endre Ferenc G´abor Henrik
Preferenciasorrend D A B C D C A B D C B A B A C
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
Feladat
Leg´enyk´er´es eredm´enye N´ ev Anna Bea Csilla D´ori
Preferenciasorrend G H G F E H G H E F H G
Sziklai Bal´ azs
N´ ev Endre Ferenc G´abor Henrik
Preferenciasorrend D A B C D C A B D C B A B A C
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
H´azas´ıt´asi probl´ema V.
Defin´ıci´o Azt mondjuk, hogy a µ p´aros´ıt´as a fi´ uk szempontj´ ab´ ol domin´ alja a ν p´aros´ıt´ast, ha minden m ∈ M fi´ ura µ(m) m ν(m). Egy µ stabil p´aros´ıt´as fi´ uoptim´alis, ha a fi´ uk szempontj´abol domin´al minden m´as ν stabil p´aros´ıt´ast. T´etel A l´anyk´er˝o algoritmus fi´ uoptim´alis stabil p´aros´ıt´ast ad, a leg´enyk´er˝o algoritmus pedig l´anyoptim´alisat.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
H´azas´ıt´asi probl´ema VI.
Defin´ıci´o Egy mechanizmust taktik´ az´ asbiztosnak mondunk, ha taktikailag nem manipul´alhat´o, azaz mindenkinek meg´eri az igazi preferenci´ait k¨oz¨olni (megint m´ask´eppen: az igazmond´as domin´ans strat´egia). T´etel A l´anyk´er˝o algoritmus a fi´ uk szempontj´ab´ ol taktik´az´asbiztos.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
H´azas´ıt´asi probl´ema v´altozatok
A probl´ema v´altozatai Z´ar´ojelben a felmer¨ ul˝o nehezs´egek. Egyetemi felv´eteli (kapacit´asok, k¨ oz¨ os kv´ ot´ak) Rezidens felv´eteli (p´arok egy¨ uttes jelentkez´ese) Nem szigor´ u preferencialist´ak (t¨ obb stabilit´asfogalom) Nem teljes preferencialist´ak (maxim´alis p´aros´ıt´as megkeres´ese)
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
Rezidens felv´eteli
A probl´ema le´ır´asa A rezidensek k´orh´azakhoz val´ o beoszt´asa a Gale-Shapley algoritmus szerint t¨ort´enik. Fiatal h´azasoknak gondot okoz, ha egym´ast´ol t´avol kapnak ´all´ast. Ez´ert felmer¨ ult az ig´eny, hogy p´arok k¨oz¨os jelentkez´eseket adhassanak le. Sajnos amint a k¨ovetkez˝o p´elda mutatja, ekkor m´ar nem felt´etleln¨ ul l´etezik stabil p´aros´ıt´as ´es m´ar a k´erd´esnek az eld¨ ont´ese is NP-teljes.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
P´ aros´ıt´ asi probl´ ema Gale-Shapley algoritmus
P´elda
´ Jelentkez˝ok: Eva Al´ız ´es Bob 1. hely Queens (Queens, Memorial) 2. hely Memorial ´ Queens sorrendje: Al´ız, Eva ´ Memorial sorrendje: Eva, Bob
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
H´ azallok´ aci´ os probl´ ema N´ epszer˝ u eloszt´ asok
H´azallok´aci´o I.
H´azallok´aci´os probl´ema Adott n egy´en, akiknek mind van egy vagyont´argya, mondjuk egy h´aza. Nem mindenki el´egedett a saj´atj´aval, sz´ıvesen elcser´eln´e, ha jobbat kapna helyette. Mindenkinek van egy teljes preferenciarendez´ese a h´azakr´ ol. A c´el a h´azaknak egy olyan u ´jraoszt´asa, amely mindenkinek a megel´eged´es´ere szolg´al.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
H´ azallok´ aci´ os probl´ ema N´ epszer˝ u eloszt´ asok
H´azallok´aci´o II.
Jel¨ol´esek A h´aztulajdonosok halmaz´at jel¨ olje N. Egy u ´jraeloszt´as nem m´as, mint a h´azaknak egy permut´aci´ oja. Az eloszt´asok halmaz´at jel¨olje A egy konkr´et eloszt´ast pedig a. Minden eloszt´asr´ol feltessz¨ uk, hogy ai 6= aj , ha i 6= j, minden i, j ∈ N-re, azaz egy h´azat csak egy ember kap meg. Az viszont lehets´eges, hogy ai = i, azaz az i. h´aztulajdonos az u ´jraoszt´as sor´an a saj´at h´az´at kapta meg. Minden S ⊆ N koal´ıci´ ora, jel¨ olje A(S) azon eloszt´asok halmaz´at, amelyekn´el S tagjai egym´as k¨ oz¨ ott cser´eltek h´azat, azaz A(S) = {h ∈ A| hi ∈ S, ∀i ∈ S}.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
H´ azallok´ aci´ os probl´ ema N´ epszer˝ u eloszt´ asok
H´azallok´aci´o III.
Defin´ıci´o Egy adott a eloszt´asra n´ezve S blokkol´ o koal´ıci´ o, ha l´etezik olyan h ∈ A(S) eloszt´as, amellyel S tagjai legal´abb olyan j´ol j´arnak mint a-val ´es legal´abb egy S-beli szigor´ uan jobban j´ar. Jelent´ese: Ha S kil´epne az eloszt´asb´ ol, akkor az S-beliek maguk k¨oz¨ott el tudn´ak osztani a h´azakat u ´gy, hogy mindenki jobban j´arna, ez´ert az a eloszt´as nem stabil. Azon eloszt´asok halmaz´at, amelyekre n´ezve nem l´etezik blokkol´ o koal´ıci´ o, az u ´jraeloszt´asi feladat magj´ anak nevezz¨ uk.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
H´ azallok´ aci´ os probl´ ema N´ epszer˝ u eloszt´ asok
Fels˝o k¨orcsere algoritmus (TTC) Top trading cycles ´ azoljuk az N halmazt egy n cs´ 1 Abr´ ucs´ u gr´affal. 2
H´ uzzunk be ir´any´ıtott ´eleket i ´es j cs´ ucsok k¨ oz¨ott, ha az i-edik egy´en preferenciarendez´es´eben a j. h´az van legel¨ol.
3
Ekkor egy olyan gr´afot kapunk, amelyben minden cs´ ucs kifoka 1. Az ilyen gr´afokban van legal´abb egy ir´any´ıtott k¨or.
4
Az ir´any´ıtott k¨or(¨ ok) ment´en cser´elj¨ uk ki a h´azakat. Mindenki azt a h´azat kapja meg, amelybe az ir´any´ıtott ´el mutat.
5
Jel¨olje N1 azoknak a tulajdonosoknak a halmaz´at, akik h´azat cser´eltek. Iter´aljuk az itt le´ırt elj´ar´ast az N − N1 halmazon, u ´gy hogy az N1 -beli h´azakat minden preferenciarendez´esb˝ol t¨or¨olj¨ uk. Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
H´ azallok´ aci´ os probl´ ema N´ epszer˝ u eloszt´ asok
H´azallok´aci´o IV.
T´etel [Shapley, Scarf, Gale 1974] Az u ´jraeloszt´asi feladat magja pontosan egy eloszt´asb´ol´all, abb´ol, amelyet a fels˝o k¨orcsere algoritmus szolg´altat. T´etel [Roth 1982] A fels˝o k¨orcsere algoritmus taktik´az´asbiztos.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
H´ azallok´ aci´ os probl´ ema N´ epszer˝ u eloszt´ asok
N´epszer˝u eloszt´asok
Defin´ıci´o A h´azak egy a u ´jraeloszt´as´at n´ epszer˝ unek mondjuk, ha nincs olyan a0 eloszt´as, amelyet t¨obb tulajdonos r´eszes´ıt el˝ onyben mint a-t. N´epszer˝ u eloszt´as nem felt´etlen¨ ul l´etezik, l´asd pl. az al´abbi p´eld´at: 1: 2: 3:
h1 h1 h1
Sziklai Bal´ azs
h2 h2 h2
h3 h3 h3
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
H´ azallok´ aci´ os probl´ ema N´ epszer˝ u eloszt´ asok
Feladat
Tal´aljunk k´et k¨ ul¨onb¨oz˝ o m´eret˝ u n´epszer˝ u eloszt´ast! 1: 2: 3: 4: 5: 6:
h1 h2 h3 h1 h2 h3
Sziklai Bal´ azs
h4 h5 h4
h6
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Vesecsere program I.
Veseel´egtelens´eg kezel´ese Dial´ızis Transzplant´aci´o A csal´adon bel¨ uli szerv´at¨ ultet´es sokszor lehetetlen a v´ercsoport, vagy a sz¨ovett´ıpus k¨ ul¨ onb¨ oz˝ os´ege miatt. A balesetben elhunyt szem´elyekt˝ol sz´armaz´o szerv kev´es ⇒ sok´eves v´ar´ olista.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Vesecsere program II.
Megold´as A donorok ´es betegek megfelel˝ o p´aros´ıt´as´aval, a ves´eket sz´o szerint k¨orbeadva, mindenki j´ ol j´ar. Az elj´ar´as azonban sz´amos k´erd´est felvet: Jogi szab´alyoz´as (pl. ¨ onk´entess´eg k´erd´ese) Donorok n´evtelens´ege A m˝ ut´eteknek egyszerre kell lezajlania, nehogy az egyik donor k¨ozben meggondolja mag´at.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Vesecsere program III.
A cser´ek hossza Hosszabb cser´ek t¨obb ´eletet mentenek meg, de a kock´azat is sokkal nagyobb. A donorok n´evtelens´ege miatt a m˝ ut´etekre sokszor nem is egy v´arosban ker¨ ul sor (sz´all´ıt´asi ´es szervez´esi neh´ezs´egek). Az els˝o hatos (!) cser´et 2008 ´aprilis´aban hajtott´ak v´egre az ´ Egyes¨ ult Allamokban. M´ashol pl. Angli´aban azonban maximum h´armas cser´eket engednek meg.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Vesecsere program IV.
Tov´abbi szempontok ¨ entes vesedonorok hossz´ Onk´ u domin´ oszer˝ u cser´eket tudnak elind´ıtani. K´orh´azak sokszor visszatartj´ak a ’legkompatibilisebb’ betegeiket. Ez megoldhat´o u ´gy, hogy a k´ orh´azakat ´erdekeltt´e tessz¨ uk a cser´eben, vagy t¨orv´enyi szab´alyoz´as u ´tj´an (az Egyes¨ ult Kir´alys´agban pl. k¨ otelez˝ o r´eszt venni a programban).
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Stabil szobat´ars probl´ema
A probl´ema le´ır´asa A koll´egiumba szeretn´enk 2n sz´am´ u di´akot bek¨ olt¨ oztetni. Egy szob´aban ketten f´ernek el. Minden di´aknak van egy szigor´ u preferenciasorrendje arr´ ol, hogy kivel szeretne ¨ osszek¨olt¨ozni. K´er´es lehets´eges-e a di´akokat stabil m´ odon p´aros´ıtani? Megjegyz´es A probl´ema annyiban t´er el a stabil h´azas´ıt´ast´ ol, hogy nem p´aros, hanem teljes g´arfon dolgozunk.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Stabil szobat´ars probl´ema
Ahogy a k¨ovetkez˝o p´elda mutatja ebben az esetben m´ar nem biztos, hogy l´etezik stabil p´aros´ıt´as! Egy´en 1: 2: 3: 4:
Sziklai Bal´ azs
Preferencia 2 3 4 3 1 4 1 2 4 tetsz˝ oleges
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
A TEX megalkot´oja
Donald Knuth (1938- )
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa Els˝o f´azis Ha x aj´anlatot kap egy y szem´elyt˝ ol a) elutas´ıtja, ha egy ´altala jobban kedvelt egy´en aj´anlat´at ˝ orzi, b) k¨ ul¨onben megtartja, ´es ezzel egyid˝oben elutas´ıtja a kor´abban esetleg neki tett (rosszabb) aj´anlatot. Az egy´enek a preferencialist´ajukon l´ev˝ o sorrendben aj´anlatot tesznek a t¨obbieknek. Ha valaki ideiglenesen elfogadja az aj´anlatukat meg´allnak. Ha b´armikor visszautas´ıt´ast kapnak folytatj´ak az aj´anlattev´est, am´ıg a preferencialist´ajuk v´eg´ere nem ´ernek. Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa
P´elda az els˝ o f´azisra: Egy´en 1: 2: 3: 4: 5: 6:
4 6 4 2 4 5
Sziklai Bal´ azs
Preferencia 6 2 5 3 5 1 5 1 6 6 5 1 2 3 6 1 4 2
3 4 2 3 1 3
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa P´elda az els˝ o f´azisra: Egy´en 1: 2: 3: 4: 5: 6:
4 6 4 2 4 5
Preferencia 6 2 5 3 5 1 5 1 6 6 5 1 2 3 6 1 4 2
3 4 2 3 1 3
– 1-es aj´anlatot tesz a 4-esnek, 4-es meg˝ orzi ´es a j¨ov˝oben elutas´ıt minden enn´el rosszabb aj´anlatot.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa P´elda az els˝ o f´azisra: Egy´en 1: 2: 3: 4: 5: 6:
4 6 4 2 4 5
Preferencia 6 2 5 3 5 1 5 1 6 6 5 1 2 3 6 1 4 2
3 4 2 3 1 3
– 2-es aj´anlatot tesz a 6-osnak, 6-os meg˝ orzi ´es a j¨ov˝oben elutas´ıt minden enn´el rosszabb aj´anlatot.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa P´elda az els˝ o f´azisra: Egy´en 1: 2: 3: 4: 5: 6:
4 6 4 2 4 5
Preferencia 6 2 5 3 5 1 5 1 6 6 5 1 2 3 6 1 4 2
3 4 2 3 1 3
– 3-as aj´anlatot tesz a 4-esnek, 4-es elutas´ıtja, hiszen m´ar van jobb aj´anlata.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa P´elda az els˝ o f´azisra: Egy´en 1: 2: 3: 4: 5: 6:
4 6 4 2 4 5
Preferencia 6 2 5 3 5 1 5 1 6 6 5 1 2 3 6 1 4 2
3 4 2 3 1 3
– 3-as aj´anlatot tesz az 5-¨ osnek, 5-¨ os meg˝ orzi ´es a j¨ov˝oben elutas´ıt minden enn´el rosszabb aj´anlatot.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa P´elda az els˝ o f´azisra: Egy´en 1: 2: 3: 4: 5: 6:
4 6 4 2 4 5
Preferencia 6 2 5 3 5 1 5 1 6 6 5 1 2 3 6 1 4 2
3 4 2 3 1 3
– 4-es aj´anlatot tesz a 2-esnek, 2-es meg˝ orzi ´es a j¨ov˝oben elutas´ıt minden enn´el rosszabb aj´anlatot.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa P´elda az els˝ o f´azisra: Egy´en 1: 2: 3: 4: 5: 6:
4 6 4 2 4 5
Preferencia 6 2 5 3 5 1 5 1 6 6 5 1 2 3 6 1 4 2
3 4 2 3 1 3
– 5-¨os aj´anlatot tesz a 4-esnek, 4-es meg˝ orzi ´es elutas´ıtja kor´abbi (enn´el rosszabb) aj´anlat´at.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa P´elda az els˝ o f´azisra: Egy´en 1: 2: 3: 4: 5: 6:
4 6 4 2 4 5
Preferencia 6 2 5 3 5 1 5 1 6 6 5 1 2 3 6 1 4 2
3 4 2 3 1 3
– 1-es aj´anlatot tesz a 6-osnek, 6-es meg˝ orzi ´es a j¨ov˝oben elutas´ıt minden enn´el rosszabb aj´anlatot.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa P´elda az els˝ o f´azisra: Egy´en 1: 2: 3: 4: 5: 6:
4 6 4 2 4 5
Preferencia 6 2 5 3 5 1 5 1 6 6 5 1 2 3 6 1 4 2
3 4 2 3 1 3
– 2-es aj´anlatot tesz a 3-asnek, 3-as meg˝ orzi ´es a j¨ov˝oben elutas´ıt minden enn´el rosszabb aj´anlatot.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa P´elda az els˝ o f´azisra: Egy´en 1: 2: 3: 4: 5: 6:
4 6 4 2 4 5
Preferencia 6 2 5 3 5 1 5 1 6 6 5 1 2 3 6 1 4 2
3 4 2 3 1 3
– 6-os aj´anlatot tesz az 5-¨ osnek, 5-¨ os elutas´ıtja, hiszen m´ar van jobb aj´anlata.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa P´elda az els˝ o f´azisra: Egy´en 1: 2: 3: 4: 5: 6:
4 6 4 2 4 5
Preferencia 6 2 5 3 5 1 5 1 6 6 5 1 2 3 6 1 4 2
3 4 2 3 1 3
– 6-os aj´anlatot tesz az 1-esnek, 1-es meg˝ orzi ´es a j¨ov˝oben elutas´ıt minden enn´el rosszabb aj´anlatot.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa
Els˝o f´azis Az els˝o f´azis k´etf´elek´eppen ´erhet v´eget: ha minden ember kapott valakit˝ ol aj´anlatot, vagy ha egy egy´ent mindenki elutas´ıt. A m´asodik esetben nem l´etezik stabil p´aros´ıt´as (mi´ert?). Lemma Ha az algoritmus sor´an y elutas´ıtja x-et, akkor x ´es y nem ´allhatnak p´arban egyetlen stabil p´aros´ıt´asban sem.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa
K¨ovetkezm´enyek Ha az algoritmus sor´an x aj´anlatot tesz y -nak, akkor egy stabil p´aros´ıt´asban x-nek nem lehet jobb partnere y -n´al, y -nak nem lehet rosszabb partnere x-n´el. K¨ovetkezm´enyek Ha az els˝o f´azis v´eg´en van valaki, akit mindenki m´as elutas´ıtott, akkor nem l´etezik stabil p´aros´ıt´as.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa
K¨ovetkezm´enyek Ha az els˝o f´azis u ´gy fejez˝ odik be, hogy mindenki o˝riz valakit˝ol aj´anlatot, akkor preferencialist´akat egyszer˝ us´ıteni lehet. Ha y ´eppen x aj´anlat´at ˝orzi, akkor y list´aj´ar´ ol potenci´alis partnerei k¨oz¨ ul t¨or¨olhet˝oek azok, akiket x-n´el kev´esb´e kedvel, vagy akik ˝oriznek egy aj´anlatot olyasvalakit˝ ol, akit y -n´al jobban kedvelnek.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa
K¨ovetkezm´enyek Ha a fentieket v´egrehajtjuk, akkor y els˝o lesz x list´aj´an, x pedig utols´ o y -´en. ´altal´anoss´agban, ha a szerepel b list´aj´an, akkor b is szerepel a-´en. Lemma Ha az egyszer˝ us´ıt´es ut´an minden lista csak egy szem´elyt tartalmaz, akkor egy stabil p´aros´ıt´ast kaptunk.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa
Az egyszer˝ us´ıt´es ut´an: Egy´en 1: 2: 3: 4: 5: 6:
Sziklai Bal´ azs
Preferencia 6 3 5 4 5 2 2 5 4 2 3 1
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa
Legyen a1 , . . . , ar a di´akoknak egy csoportja, amelyre igaz a k¨ ovetkez˝ o Egy´en a1 a2 .. . ar
Preferencia b1 b2 . . . b2 b3 . . . .. .. . . br
Sziklai Bal´ azs
b1
...
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa
T´etel Legyen a1 , . . . , ar a fenti felt´eteleknek eleget tev˝ o di´akcsoport. Ekkor b´armely stabil p´aros´ıt´as eset´en ai ´es bi vagy minden i-re partnerek, vagy egyikre sem. ha l´etezik olyan p´aros´ıt´as, amelyben ai ´es bi partnerek minden i-re, akkor olyan is l´etezik, amelyikben nem.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa
M´asodik f´azis A t´etel k¨ovetkezm´enyek´epp, ha l´etezik stabil p´aros´ıt´as, akkor olyan stabil p´aros´ıt´as is van, amelyben bi minden i-re elutas´ıtja ai -t. Ekkor ai aj´anlatot tesz bi+1 -nek ´es bi+1 list´aj´ar´ ol t¨or¨olhet¨ unk minden ai -n´el rosszabb jelentkez˝ ot. Ezzel egy id˝ oben bi+1 -et is t¨or¨olhetj¨ uk ezeknek a jelentkez˝ oknek a list´aj´ar´ ol. A m´asodik f´azist addig ism´etelj¨ uk, am´ıg minden di´ak list´aj´an csak egy szem´ely nem szerepel. Ekkor stabil p´aros´ıt´ashoz jutottunk. Ha valamelyik di´ak preferencialist´aja ki¨ ur¨ ul, akkor nem l´etezik stabil p´aros´ıt´as.
Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa
A m´asodik f´azisban a 2-es elutas´ıtja a 4-est, az 5-¨os pedig a 3-ast. Egy´en 1: 2: 3: 4: 5: 6:
Sziklai Bal´ azs
Preferencia 6 3 5 4 5 2 2 5 4 2 3 1
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Irving algoritmusa
´Igy kialakulnak a v´egs˝ o p´aros´ıt´asok: 1–6, 2–3, 4–5. Egy´en 1: 2: 3: 4: 5: 6:
Sziklai Bal´ azs
Preferencia 6 3 5 4 5 2 2 5 4 2 3 1
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Feladat
L´etezik-e stabil p´aros´ıt´as az al´abbi p´eld´aban? Egy´en 1: 2: 3: 4: 5: 6:
2 3 1 5 6 4
Sziklai Bal´ azs
Preferencia 6 4 3 5 1 6 6 2 5 2 3 6 1 3 4 2 5 1
5 4 4 1 2 3
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
Egyetemi felv´ eteli ´ Ujraeloszt´ asi probl´ ema Vesecsere program Stabil szobat´ ars probl´ ema
Tan t´etele T´etel Stabil f´el-p´aros´ıt´as mindig l´etezik. N´ezz¨ uk meg u ´jra a kiindul´ o p´eld´ankat! Egy´en A: B: C: D:
Preferencia B C D C A D A B D tetsz˝ oleges
Anna, Bea, Cettina ´es D´ ori teniszpartnert keres egy ´or´ara. Tudjuk, hogy stabil p´aros´ıt´as nem l´etezik. Ugyanakkor ha Anna, Bea ´es Cetti f´el-f´el ´or´at j´atszanak egym´assal, D´ orit pedig kihagyj´ak, akkor stabil f´el-p´aros´ıt´ast kapunk! Sziklai Bal´ azs
J´ at´ ekelm´ elet 3-4. el˝ oad´ as
