1 gondolat. Nem bánt.
Eredeti szerző: jotunder
Tegnap Alvin Roth és Lloyd Shapley kapta meg a közgazdasági Nobel-díjat. Az ember elolvassa, hogy piactervezési és párosításelméleti munkásságukért kapták a díjat, és gondolom, tovább lapoz. Matolcsy György szokott a Heti Válaszban arról írni, hogy már megint olvasott valamit, és abból az következik, hogy a kormány gazdaságpolitikája helyes. Talán erről is fog írni valami hasonlót. No, én csak azt fogom leírni, hogy mi is ez a Gale-Shapley féle párosítási tétel, és Olvasó meg fogja érteni. Nem, ez nem használható annak kimutatására, hogy el kell menni a Milla tüntetésére, vagy hogy Orbán rablólovag. Ez most egy ilyen nap.
A kérdés: Van ezer férfi és ezer nő. Mindegyik férfi sorba rendezi a nőket aszerint, hogy mennyire tetszenek neki. A lista tetején áll a neve annak a nőnek, aki a legjobban tetszik neki, az alján pedig azé, aki a legkevésbé. Holtverseny nincs. Ugyanígy minden nőnek van egy listája az ezer férfiról. A feladat az, hogy úgy házasítsuk össze az ezer nőt az ezer férfival, hogy ne legyen olyan pár, akik nem egymással házasok, de jobban tetszenek egymásnak, mint a házastársuk. Tehát ne álljon elő olyan helyzet, hogy János felesége Margit, Béláé Irma, de Jánosnak jobban tetszik Irma Margitnál, és Irmának jobban tetszik János Bélánál. Gale és Shapley adott egy algoritmust arra, hogyan kell egy ilyen (stabil) házasító procedúrát végrehajtani.
Az algoritmus: Először is mind az ezer férfi házassági ajánlatot tesz annak a nőnek, aki a legjobban tetszik neki. Persze lehet, hogy lesz olyan nő, aki sok ajánlatot fog kapni, és lesz olyan, aki egyet sem. Azok a nők, akik ajánlatot kapnak, kiválasztják az ajánlatot tevő férfiak közül azt, aki nekik a legjobban tetszik. Ezzel a férfival eljegyzik egymást. Eljegyzésről van szó, nem házasságról. Azok a férfiak, akiket visszautasítottak, kihúzzák a lista tetejéről azt a nőt, aki visszautasította őket. Ezzel vége az algoritmus első lépésének.
A második lépésben a még eljegyzetlen férfiak házassági ajánlatot tesznek a listájuk tetején levő nőnek. Akkor is, ha az illető nőnek esetleg már van jegyese. Minden olyan nő, aki kapott ajánlatot, kiválasztja a számára legjobban tetsző férfit, és azzal jegyzi el magát. Itt most álljunk meg: elképzelhető, hogy egy már eljegyzett nő új házassági ajánlatot kap valakitől, aki jobban tetszik neki, mint a korábbi jegyese. Ilyenkor felbontja a régi eljegyzést, és az aktuális választékból legszimpatikusabb férfival jegyzi el magát. Az újabb eljegyzések után, az éppen eljegyzetlen férfiak kihúzzák a listájukról azt a nőt, aki elutasította őket (vagy közvetlenül, vagy a régebbi eljegyzés felbontásával). Ezzel vége az algoritmus második lépésének.
Az algoritmust addig ismétlik, amíg a listákon van kihúzatlan női név.
Miért lesz vége az algoritmusnak, miért nem kerülhetünk végtelen ciklusba? Nem, nem kerülhetünk végtelen ciklusba. Ez az algoritmus véges időben megáll. Ha egy lépésben egy férfit elutasítanak vagy egy eljegyzést felbontanak, legalább egy férfi ki fog húzni a listájáról egy nőt. Az összes férfi listáján együtt egymillió név szerepel, hiszen ezer lista van, mindegyiken ezer nővel. Legfeljebb egymillió lépés után egyszerűen nem marad kihúzható név.
Rendben, egyszer véget ér az algoritmus, de nem lehet-e, hogy egy férfi hoppon marad? Ha egy nőt egyszer kiválaszt egy férfi az algoritmus egy pontján, akkor az a nő az algoritmus végéig jegyes marad. Nem feltétlenül az első olyan férfival, aki eljegyezte, de valakivel. Ha egy férfinek nem jut nő, akkor bizony kell lennie olyan nőnek, akinek nem jut férfi. De azt a nőt egyszer a hoppon maradó férfi kihúzta a listáról. Ennek pedig az volt az oka, hogy ajánlatot tett neki. Tehát a nőnek volt ajánlata, így nem maradhatott a végén egyedül.
Tehát összeházasítottuk a férfiakat a nőkkel, de miért nem lehet, hogy János, Margit, Béla és Irma olyan házasságot köt a végén, amilyet ki akartunk zárni? Tegyük fel, hogy János a végén elveszi Margitot, annak ellenére, hogy Irma jobban tetszik neki. Akkor bizony volt egy olyan lépés, amelyben őt Irma elutasította. Amikor egy nő elutasít egy férfit, akkor már csak olyan férfi jegyezheti el, aki jobban tetszik neki, mint akit elutasított. Akkor viszont Irmát sohasem jegyezheti el Béla.
Ennyi.
<div class='sharedaddy sd-block sd-like jetpack-likes-widget-wrapper jetpack-likes-widget-unloaded' id='like-post-wrapper-192691293-16520706-6ae585a1a5b7e' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16520706&origin=www.orulunkvincent.hu&obj_id=192691293-16520706-6ae585a1a5b7e&n=1' data-name='like-post-frame-192691293-16520706-6ae585a1a5b7e' data-title='Like or Reblog'><h3 class="sd-title">Like this:</h3><div class='likes-widget-placeholder post-likes-widget-placeholder' style='height: 55px;'><span class='button'><span>Like</span></span> <span class="loading">Loading...</span></div><span class='sd-text-color'></span><a class='sd-link-color'></a></div>
Arra tudsz esetleg példát mondani, hogy ez milyen közgazdasági szituációban használható… Oké randivonalon igen, de a businessben?
@fromdtod: http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/popular-economicsciences2012.pdf
Asszem, ezt inkább reggel gondolom végig.
Egyébként Shapley-ék is hoztak hasonló gyakorlati példát? Mert a szövegből úgy tűnik, ez a sajátod.
Grat akkor.
@jotunder: köszi
Ez elég egyszerűnek tűnik. Mi ér ebben Nobel díjat?
Ezért Nobel díj jár? Majd minden nap hasonló vagy bonyolultabb problémákra kell algoritmusokat írnom 😀
@agresszív kismalac: így szokták elmagyarázni. stable marriage problemnek hívják.
@Szindbad: shapley rengeteg dolgot csinált, „for the theory of stable allocations and the practice of market design” ez a hivatalos indoklás.
egyébként ezt a tételt nem is egy „igazi” tudományos folyóiratban publikálták, hanem az American Mathematical Monthly-ban.
Késő van. Eszerint: „Ha egy nőt egyszer kiválaszt egy férfi az algoritmus egy pontján, akkor az a nő az algoritmus végéig eljegyezve marad” ez azt jelenti, hogy kapott ajánlat esetén választani kötelező? Mi több, egy (nur 1) kapott ajánlatot (összehasonlíthatóság híján) kötelező jegyességre váltani?
@ijontichy: igen, ha egy ajánlatot kap egy fordulóban, akkor azt kötelező jegyességre váltani. de ha a nő X jegyese, és a következő fordulóban kap Y-tól egy ajánlatot, akit jobban bír, mint X-t, akkor kicseréli X-et Y-ra.
a magyarázat igen szemléletes, és nem is nehezen érthető. amin elgondolkodtam -és a kommentekből látni, hogy más is 🙂 – az, hogy mi ennek az algoritmusnak a gyakorlati haszna.
bár, van egy olyan sejtésem, hogy a kereslet- kínálat optimalizásában használható.
mindig érdemes egy ilyen felállásban kinyilvánítani a valós preferenciákat, vagy van rá bármi kis esély, hogy valaki jobb helyzetbe kerüljön ha trükközik?
http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/popular-economicsciences2012.pdf
Gyakorlati felhasználás:
Kórház és rezidens orvosok, beültetésre váró vesék és vesére várakozók, főiskolára jelentkező tanulók és főiskolák.
Gale az algoritmust alkotta meg egyedül, majd Shapley megmondta hol lehet azt a gyakorlatban felhasználni.
Amíg a résztvevők nem változtatnak az eredeti preferenciáikon, addig hatalmas stabilitást hoz az ilyen módon párosított kereslet-kínálati rendszerekbe. De az élet változik és vele én is, így ma még ez a nő tetszett jobban, de lehet hogy holnap a szomszéd neje 🙂 Na erre – azaz a preferencia változásra – ez sem ad megoldást, hacsak nem mindig újra párosítunk amikor bárki változtat addigi preferenciáján vagy változnak a résztvevők – belép vagy kilép ebbe a párosító rendszerbe.
De összességében nagyon jó, mert a résztvevők konszenzusán alapuló stabilitást okoz!
Teccik nagyon! Jár a Nobel price érte!
Meg a Nobel prize is 🙂
@volker:
A preferencialisták elkészültekor már eldőltek a párosítások: az algoritmus ‘csak’ — determinisztikusan — meghatározza a párosításokat a preferencialisták tartalmának feldolgozásával. Természetesen ha más sorrend van egy (vagy több) preferencialistán, az megváltoztat(hat)ja a párosításokat… de mindig a ‘legjobb’ párosításokat adja meg a preferencialisták tartalmát figyelembe véve.
Tegyük fel hogy Béla összeállította az 1,000 elemű preferencialistáját és az algoritmus végrehajtása után a preferencialistájának 241. eleméhez lett hozzárendelve. Mondhatnánk azt hogy akkor a preferencialistájának első elemét kellett volna a 241. helyre raknia (mondjuk felcserélve a két listaelemet), és akkor az általa legpreferáltabb elemhez került volna hozzárendelésre. De ez nem így van: ehhez az is kellett volna hogy másik 999 férfi preferencialistáján is felcserélésre kerüljön az a két elem amelyik Béla ‘igazi’ listáján első ill. 241. helyen volt.
@volker: Pont azért jó a mechanizmus, mert nem érdemes „trükközni”. Cf 2007es közgazdasági Nobel.
@Szindbad: Egyrészt utólag minden szép tétel egyszerű, de azért attól vkinek még ki kellett találni, másrészt rengeteg más dolgot csináltak mindketten.
de mi köze ehhez Irmának meg a Bélának? fel is hívom, megkérdem tőlük.
@Jack Torrance: Akkor te rossz helyre születtél.:-)
Az algoritmus gyakorlati alkalmazását nyilván korlátozza, hogy a valóságban a „férfiak” nem tudják/akarják az összes „nőt” rangsorolni (és viszont), sőt, csak az első valahányat tartják elfogadhatónak, és ha abból nem jut nekik, akkor nem „házasodnak”. Praktikusan véges számú helyet jelölnek meg a felvételizők és a főiskolák is ponthatárt szabnak, de azért ilyen körülmények között is vannak jobb és rosszabb párosítások, amiket az intuitív módon kialakult gyakorlat valahogy csak megtalál.
Tényleg nem vette észre senki (itt), hogy ez a kritérium: „úgy házasítsuk össze az ezer nőt az ezer férfival, hogy ne legyen olyan pár, akik nem lesznek házasok, de jobban tetszenek egymásnak, mint a házastársuk.” nem ugyanazt jelenti, mint ez?: „Tehát, ne álljon elő olyan helyzet, hogy János házastársa Margit, Béla házastársa Irma, de Jánosnak jobban tetszik Irma Margitnál, és Irmának jobban tetszik János Bélánál.”
Bizony mondom, hogy ez az algoritmus nem tudja biztosítani ezt (a második) feltételt. Nagyon sok olyan János, és Irma lesz, akiknek jobban fog _tetszeni_ más, mint a házastársuk. És, természetesen nincs (és nem lesz) olyan algoritmus, amely azt a feladatot is meg tudja oldani, hogy mindenki a neki leginkább tetszővel párosodjon össze.
Viszont, ha ez utóbbi, szép, ám teljesen valóságidegen, idealista vágyálmot kivesszük belőle (a célok közül), akkor az algoritmusból egy rendkívül erős, és sok kompromisszumot megkövetelő eljárás marad (legalábbis a párválasztás terén). Gyakorlatilag (valószínűleg) senkinek sem az lesz a párja, aki a legjobban tetszik neki, hanem az, aki marad, vagyis akit ebben a versenyben meg tudott szerezni. Ez még mindig „igazságosabb”, célszerűbb, és optimálisabb megoldás, mint mondjuk a véletlenszerű kiválasztás, de attól fényévekre van, hogy mindenki a neki legjobban tetszőt kapja meg.
a dolog csak azért nem reális, mer ta valóságban a nö kezd ki a férfival, csak úgy csinálja, hogy a férfi azt higgye hogy ö volt a kezdeményezö.
van a problémának megoldása az arab világban is?
@ipartelep: Ízlelgesd az ‘egymásnak’ szót.
@spinat: Az algoritmus nyílvánvalóan fordított felállásban is működik.
…kecskére?
@ipartelep: Nincs olyan megoldás, amiben mindenki a neki legjobban tetszőt kapja meg. 2+2 szereplővel tudsz olyan példát csinálni, amiben ez lehetetlen. Szerelmi sokszögekkel a szépirodalom foglalkozik, nem a közgazdaságtan.
A párválasztás itt csak kontextus egy példához, hogy egyszerűbb legyen elmesélni a sztorit. Valójában senki nem gondolja, hogy a párválasztás ilyen algoritmusokkal történik vagy történjen. Azt se gondolja senki hogy mindenkinek preferenciarendezése van a releváns univerzumra, vagy hogy surlódásmentes a párválasztási piac, stb, stb.
JT vette a fáradtságot és elmesélt egy nagyon érdekes dolgot közérthetően, de ettől még a dolog érdekes, nem a mese. A mesébe nem érdemes nagyon belehelyezkedni.
egészen biztos, hogy a szerző közgazdászok okosabbak nálam, és valószínűleg a kommentelők, itteni szerzők zöme is, tehát nem okoskodni akarok, csak rámutatni, hogy szerintem ez megint ilyen „laborkörülmények között” működik csak, kint terepen (azaz IRL, ahogy mondani szokás) csak erős fenntartásokkal.
mivel a nők vagy a piac nem feltétlenül írható le kvantitatív jellemzőkkel. sőt, a nős példán elgondolkodva, saját magamból kiindulva még csak ordinális listát se igen lehet készíteni.
sőt ezek a rendszerek nagyon nem statikusak.
de ez nyilván nem a modell hibája. műfaji sajátosság, a közgáz ilyen. 🙂
de köszi, érdekes volt olvasni.
@tollaszerge: Jó, de mi itt az érdekes? Van itt egy 60 éves egyszerű algoritmus, ami ennyi idő alatt a kórház-doktor, meg az egyetem-tanuló konkrét felhasználási esetekeit bírta produkálni. Mi ér ebben Nobel díjat?
@Szindbad: A Nobel-díj honlapján van egy populáris és egy szakmai összefoglaló a díjazottak munkásságáról és eredményeiről. Te azt akarod játszani hogy ezeket nem olvasod el, hanem valaki foglalja neked össze röviden, lehetőleg elég röviden ahhoz hogy utána rákérdezhess hogy mi ér ebben Nobelt. Én nem akarom ezt játszani. Ha kedvem lenne funkcionális analfabétákat tutorálni (nincs), akkor valszeg találnék valami módját hogy fizessenek érte. Ingyen nem.
@tollaszerge: Igen, pontosan ezt szerettem volna játszani 🙂
A közgazdaságtan nagyon gyakran megkapja az áltudomány jelzőt, és nekem nincs annyi időm, hogy ezt leszedjem róla, gondoltam, hogy egy közgazdasági végzettségűnek kevésbé melós lenne.
@Szindbad:
Fordítsuk meg a dolgot: mivel Nobel-díjat kaptak érte ezért biztos ér valamit a dolog. Mivel nem értem ezért utánanézek.
Egyébként lehet meglepő dolgot mondok, de a Nobel-díj nem olyan mint a magyar közbeszerzés vagy a minisztériumi főosztályvezető-kiválasztás. Itt bárki aki egyáltalán esélyes rá komoly dolgot rakott le az asztalra.
@ipartelep: Nálad a pont! Szerintem ez egy roppant igazságtalan elosztás, mivel tényleg minden igénylö azt kapja ami marad, illetve nem kaphat jelentösen jobbat mint saját maga, a másik oldal pedig a számára legjobbat. Az algoritmus által tulajdonképpen mindenki kap a kritériumok szerinti párosítás alapján egy osztályzatot és azok a párok maradnak meg amelyek az igénylett oldalon a legjobb osztályzatot kapják. Ugyanakkor az igénylö oldal esetleg kimarad az igénylésböl mivel kötésben van, és egy késöbbi szakítás után már lehet, hogy csak a listája allján talál(kap) szabad lehetöséget. Pl. köznemes csak akkor kaphat hercegnöt, ha már az összes herceg elkelt, illetve, ha az összes nemeskislány talált egy herceget, neki már csak a parasztlány marad. Viszot tudnám ajánlani új választási rendszernek. Képviselök=Férfiak Választók=Nök 🙂
http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/advanced-economicsciences2012.pdf
@Szindbad: A jatekelmeletben nincs semmi altudomanyos, az 100% matematika.
@xylon: Aztat tudom én azt, de ha valaki amúgy is finoman szólva prekoncepciókkal rendelkezik a közgazdaságtan tudományát illetően, akkor esetleg felmerül benne, hogy ha egy ilyen egyszerű algoritmussal Nobel díjat lehet nyerni, akkor mégsem lehet valami komoly tudomány a közgazdaságtan.
@agresszív kismalac: nökkel kapcsolatban nem használnám a ” nyilvánvalóan” kifejezést.
és nem a kecskékre gondoltam hanem a többnejüségre 🙂
Amúgy lehetne boynolítani a problémát, ha a listára felvesszük az anyósokat is. De hát a közgazdaságtan mindig is a való élettöl távol álló problémákkal foglalkozott 🙂
@Szindbad: és ha még az advanced dolog is kevés lenne, itt van egy kicsit még komolyabb, megszórva matekkal:
doktori.math.bme.hu/Tezisek/biro_tezisfuzet.pdf
amúgy nyilván fel lehet turbózni ezer feltétellel, hogy ne legyen olyan egyszerű és mégis ez volt a kiinduló pont.
@tyder: Nekem ez nem a szakterületem, nekem ezt melós átnézni. Gondoltam hátha van valaki, aki közérthetően el tudja magyarázni, hogy miért értékes a közgazdasági Nobel díj.
@Szindbad: nem ezért kapta a Nobel díjat. vannak esetek, amikor valaki borzalmasan egyszerű, de rettenetesen fontos dologért kap Nobelt, pl. Nash egy kétoldalas bizonyításért. Arrow esetében az Arrow preferencia tétel súlya is elég nagy volt. Shapley a játékelméletben nagyon nagy név, sok mindent csinált.
@Szindbad: ha jól értem, itt nem az algoritmusért kaptak díjat, hanem annak közgazdasági vetülete, használhatósága, megfeleltetése vagy tudomisén, igazolása, kimutatása után, hogy ott is vannak olyan folyamatok, területek, ahol ez – az egyébként már ismert – algoritmus használható.
@Szindbad: ez azonban az illető egyéni szociális problémája.
@Szindbad: Ez a prekoncepcioval rendelkezo ugye te vagy?
A fenti cikk egy tudomanyos eredmeny egyszerusitett verziojanak popularis verziojanak zanzasitottja. Raadasul az 50es-60as evekbol Ertem hogy egyszerunek tunik de legyszives probald megerteni hogy ennel azert tobbrol van szo, ez csak az alapotlet (-nek a zanzaja).
Megegyszer a jatekelmelet NEM kozgazdasagtan.
BTW olvasd el xenuka cikket.
@xylon: Nem, nem én vagyok. Tényleg 🙂 Csak nem tudok neki semmi érdemit mondani.
@Lasombra: A fent vázolt algoritmus és az ahhoz kapcsolódó eredmények csak egy szelete a munkásságuknak, amiért a díjat kapták.
@xylon: A játékelmélet közgazdaságtan, már amennyire ezeknek a besorolásoknak értelme van.
@jotunder: Igen, igen, pontosan az érdekelne, hogy miért olyan nagy súlyú ez tétel. De ha senki, akkor utánanézek magam.
@tollaszerge:
akkor meg pláne.
köszi.
@Szindbad: de ha rájöttél, majd mondd el.
@Forgó morgó: „illetve nem kaphat jelentösen jobbat mint saját maga,”
Ezt hívja úgy a népi bölcsesség, hogy „zsák a foltját”. És ebből is látszik hogy a példa nem teljesen a valóságtól elrugaszkodott.
Szimmetrikus az algoritmus? Ugyanaz a megoldas jon ki, ha felcsereljuk a ferfi es noi szerpeket? (Merthogy nylivan nem egy megoldas van stabil hazasitasra.)
@értem: xenuka cikkeben eppen azt olvasni hogy a „kezdo” vagy „valaszto” elonyben van, es ott irja hogy a Nobel dij munkassag resze egy olyan modositas ami kezeli ezt.
@Szindbad: miért lenne önmagában nagy súlyú? ez egy gondolat, ami további gondolatokhoz vezetett. a scholar.google-on amúgy kétezer felett van a tétel idézettsége.