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-6ae57b92c877e' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16520706&origin=www.orulunkvincent.hu&obj_id=192691293-16520706-6ae57b92c877e&n=1' data-name='like-post-frame-192691293-16520706-6ae57b92c877e' 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>
@xylon: Nem egészen. Rájöttek, hogy a diákok nem azt a kórházat választják, amelyikhez kellene, hanem rosszabbat, hogy jobb relatív teljesítményt mutathassanak fel. (Ahelyett, hogy a legjobb kórházban Dr.House legjobb segédje legyen, egy rosszabb kórházat választ ahol ö lehet Dr. House) Ezzel viszont megzavarja az elosztást és a legjobb kórház nem a legjobb diákot kapja. Az új algoritmus kiküszöböli az ilyetén szándékosan rosszabb választásokat, hogy mégiscsak a kórház járjon jól. 😉
Gondolatok/kerdesek:
1. Lehet hogy hülye kerdes (reg foglalkoztam ilyesmivel…), de: Szimmetrikus-e az algoritmus a ferfiak es nök tekinteteben a vegeredmenyt tekintve? Tehat ha aggregaljuk az 1000 ferfi es 1000 nö boldogsagat (pl aszerint hogy listajan hanyadik nö/ferfi jött vegül össze) akkor elterö eredmeny születik ha megfordul az algoritmusban a nö-ferfi szerep? Egyaltalan a leirt peremfeltetel megenged többfele parositast?
2. A jatekelmelet jo dolog, ugyanakkor meg mindig a közgazdasagtan operacionalizalo/algoritmizalo/pozitivista vonulatahoz tartozik, ennyiben kar hogy ide jött a dij. Biztos lehetett volna olyan mühelyeket talalni ahol valami magyarazatfelen dolgoznak arra, hogy jelenleg mi törtenik a vilagban, es igy hangyanyival relevansabb mint a parositgatos jatekok. Persze meg mindig jobb mintha valami rettenetesen forradalmi 561-ik egyensulyelmelet kapta volna a dijat.
3. @Szindbad: a közgazdasagtan szvsz olyan mint a teologia. Egy összefoglalo nev zart es irreflexiv hiedelemrendszereknek, melyek egymassal a vilagon semmiben nem ertenek egyet; mindemellett lenyegeben irrelavansak es mindenkeppen alkalmatlanok a valosag leirasara, plane elörejelzesere. (Es mindez nem zarja ki hogy nagyon nagy elmek nagyon nagyot alkossanak egy-egy ilyen burokban.)
4. @tollaszerge: a jatekelmelet nem közgazdasagtan. Akkor valik azza amikor megvizsgaljuk balrol-jobbrol, teoretikusan es empirikusan hogy a jatekelmeleti eredmeny hol mennyiben egyezik valos folyamatokkal; amennyiben nem, ott miert es mennyire nem stb. Addig ”csak” matematika.
P.S. az hogy faszaganyosan összeparositjuk a jelentkezöt az iskolaval, az nem közgazdasagi felhasznalas.
@tollaszerge:
nem inkább az elméleti közgazdaságtan matematika?:)
@Ellenpontok:
nem lehet hogy te az elméleti közgazdaságtant összetéveszted más diszciplínákkal, mint pl. gazdaságtörténet,gazdaság-szociológia pszichológia-filozófia stb.?
@Vortumnus: Egyes ágai használnak (elég sok) matematikát, de nem tudom mennyire érdekesek egy matematikusnak. Szerintem akkor lesz egy matematikai eszközöket használó terület matematika, ha az eredmények túlmutatnak azon a célproblémán, amihez szükség volt rájuk. Nekem az a benyomásom hogy a matematikusokat általában nem annyira izgatják a micro theory eredmények. A közgazdászokat inkább.
SZVSZ amúgy a kérdésnek (matematika-e …?) nincs túl nagy jelentősége, nem is annyira érdekes. A díjazott eredmény, na az érdekes, sokkal jobb azon gondolkozni.
@Ellenpontok: A területet mindenki (közgazdászok és a témát ismerő nem-közgazdászok) közgazdaságtanhoz sorolja, beleértve a közgazdasági Nobel-bizottságot. Te persze gondolhatod hogy nem közgazdaságtan, akkor az lesz hogy egy csekély jelentőségű kérdésben lesz egy érdekes álláspontod.
@Vortumnus: inkabb arrol van szo hogy a közgazdasagtan teveszti össze sajat magat egyes termeszettudomanyokkal. Az altalad felsoroltak közül pl a pszichologianak vagy a szociologianak összehasonlithatatlanul nagyobb igenye van eredmenyeinek a verifikalasara, valosaggal valo összevetesere mint a közgazdasagtannak.
@tollaszerge: matematikus forrasaim szerint meg a durvabb modellek is eleg kezdetleges matematikat hasznalnak.
Hogy mi a csekely jelentösegü es mi nem, az nyilvan szubjektiv. Nekem erdekes kerdes hogy hol kezdödik a közgazdasagtan es hol vegzödik a matematika.
@Ellenpontok: arxiv.org/pdf/1210.3164.pdf
tessék, itt van egy friss cikk. quant.
@Ellenpontok: A közgazdaságtan magát inkább társadalomtudománynak tekinti. Hogy a pszichológiának és a szociológiának milyen igénye van eredményei igazolására, azt nem tudom, de a közgazdaságtan első sorban arról szól, hogy a létező világ összefüggéseit próbálja leírni, ami az emberi tényező miatt jelentős bizonytalanságot hordoz. Magyarán egyre közelebb kerülhetünk az igazsághoz, de az hajlamos odébb ugrani, illetve egyáltalán nem egy kézzel fogható tényező.
@jotunder: ez most mi mellett vagy mi ellen szol?
@tommybravo: A közgazdaságtan jelenleg úgy működik, hogy modelleket alkot, amiket összevet az adatokkal. Ez egy elég összetett folyamat, vannak cikkek amik csak modellekről szólnak, vannak amik csak adatokról, de a kettő össze szokott érni.
Erről persze nem mindenki tud, miért is tudna, ha egyszer nem foglalkozik közgazdaságtannal. Valamiért mégis nagy az igény közgazdaságtannal halvány kapcsolatba sem kerülő emberekben, hogy átfogó állításokat tegyenek arról mit és mit nem csinál a közgazdaságtan, esetleg összehasonlítsák egyéb diszciplínákkal, vagy bónuszként köpködjék egy kicsit. Ez a jelenség számomra érthetetlen.
@tollaszerge: Talán félreérthetően fogalmaztam, de hasonlóan gondolom, mint ahogy te is írtad („jelentős bizonytalanságot hordoz” vs. „össze SZOKOTT érni”). A bizonytalanság a közgazdaságtanban nem egy negatív tényező, amennyiben lehet vele kalkulálni, és a tudomány egyes ágai – gondolom – pont ezzel foglalkoznak, illetve a legtöbbnek része a bizonytalanság figyelembe vétele. Ezt a megközelítést (a bizonytalanság nem a modell halála, hanem az egyik szempontja) nehéz átvennie sok jogásznak, műszaki végzettségűnek vagy akár biológusnak (a sor folytatható).
@tollaszerge. „közgazdaságtannal halvány kapcsolatba sem kerülő emberekben„
– ez kedves 🙂 csak nem megsertettelek valamivel?
„vannak cikkek amik csak modellekről szólnak, vannak amik csak adatokról, de a kettő össze szokott érni.“ De meg mennyire, az adatok összernek a klasszikus, neoklasszikus, keynesianus es neokeynesianus, monetarista es osztrak iskolara epülö modellek mindegyikevel, hogyne. Nagyobb feritel mint az eredeti.
Nem latszol tudni arrol, hogy a közgazdasagtan matematizalasa es önceluva valasa mar a kezdetektöl jelentös kritikakat valtott ki (nezd meg Keynes mit mondott erröl), es hogy ez az utobbi idöben csak erösödött (egy pelda a sokbol a keves jegyzett magyar közgazdasz egyiketöl: epa.oszk.hu/00000/00017/00147/pdf/01csaba23.pdf).
Kornai maga meselte Douglas North-ot köszöntö elöadasan hogy egyszer egy közgazdasagi gondolatat matematikai formalizalas nelkül küldte el amerikai folyoiratoknak akik visszadobtak azt; kesöbb egy diakja kepletekbe szedte, ugy megjelenhetett. Es ha mar North, aki ugyancsak Nobel-dijas (!!), nezd meg az ö nezeteit is az ügyben.
Eközben a matematizalt, elmeleti közgazdasagtan prediktiv ereje mar a mostani valsag elött is eleg gyenge volt, az utobbi evekben pedig kb összeomlott. Mondj egyetlen iskolat/embert/modellt aki helyesen latta volna elöre a 2009-es realgazdasagi összeomlas merteket ES a visszapattanaset (nyilvan a permabear-ek es permabull-ok eltalaltak az egyik felet).
De azt hiszem legjobb befejeznem itt. Nem kellemes szamomra a hangvetel amit hasznalsz, es velhetöen az egesz vita a többseg szamara rettenetesen erdektelen.
@Ellenpontok: A kozgazdasagtan matematikai megkozeliteset foleg
azok kritizaljak akik rosszak matekbol 🙂
@tollaszerge:
úgy gondolják, hogy az elméleti( matematikai:) ) közgazdaságtan fősodra egy olyan gondolkodásmód egyik megnyilvánulásának tekinthető, mely segít megalapozni és fenntartani egy nemkívánatos globális rendet. (hogy miért nem kívánatos, arról persze megoszlanak a vélemények, pl. szélbal, széljobb vagy éppen az átlagos nacionalista eltérő kritikákat fogalmaznak meg)
Az Ellenpontok által linkelt dolgozatból:
epa.oszk.hu/00000/00017/00147/pdf/01csaba23.pdf
A gazdaságpolitika elemzése – az elméleti tanszékek fanyalgása ellenére – sosem veszített gyakorlati jelentõségébõl egyetlen országban sem (a legkevésbé az ortodoxiát egyetemein leghevesebben képviselõ Egyesült Államokban). Ahogy annak idején David Ricardo a védõvámok elleni köztéri harcban szülte meg a komparatív elõnyök elvét, a közgazdaságtan egyik leginkább idõtálló (és a közvéleményben máig kevéssé felfogott) felismerését, úgy Ed Prescott Nobel-díja átvétele alkalmából tartott elõadásában szemléltette, hogy a gazdaságpolitikai elemzés sosem tûnt el a színrõl (Prescott [2008]). Itt nyilván nem arról van szó, hogy a demokráciában elkerülhetetlen laikus közbeszéddel keverjük össze a valóság folyamatainak elemzését. Sokkal inkább arról, hogy a társadalmat joggal foglalkoztató, megoldatlan kérdéshalmazban, legyen szó nyugdíjreformról vagy a világhálón folyó kereskedelemrõl, adózásról vagy szegénységcsökkentésrõl, nemigen tudunk hatásos megoldásokat találni a fõáramban kimunkált elemzési eszköztár és ismeretanyag hasznosítása nélkül. Másfelõl a gazdaságelméleti felismerések alkalmazásának peremfeltételei között pótolhatatlan a jogalkotás, a közigazgatás, a társadalmi csoportok mûködési szabályosságai, a politikatudomány és a nemzetközi viszonyok hatásának elemzése, a maga komplexitásában. Ezek bizony éppen azok az elemek, amelyektõl a technicista ortodoxia eleve elvonatkoztat.
Ahogy látom a hozzászólásokban inkább az algoritmus határait feszegetjük, de akit érdekel, ajánlom figyelmébe egyik előadásomat, amiben a GS algoritmust magyaráztam – középiskolásoknak. A végén kitérek pár érdekes és tanulságos következményre, amiket már Roth igazolt. http://www.academia.edu/2038996/Egyetemi_felveteli_…_es_a_matek_ami_mogotte_van_College_admissions…_and_the_maths_behind_it_
@ipartelep: @agresszív kismalac: Eltévedtetek. Nem az „egymásnak” szót kellene ízlelgetnie ipartelepnek az első verzióban, hanem az „és” szót a másdikban. Igen, lesz sok olyan János, akinek jobban tetszik egy másik nő, és lesz sok ilyen Irma is. De hogy Jánosnak Irma ÉS Irmának János, olyan nem lesz. Ettől stabil: János és Irma együtt már meglépnének egymással, fölrugnák a rendszert, de én hiába írok levelet Szíjjártó Petinek, hogy jöjjön el velem, hogy ha ő az Orbánnal akar maradni.
„A monogámia a férfiak közmegegyezése, hogy minden férfinak jusson nő.”
@xenuka:
Preferenciák időbeli változása:
Gyanítom (mivel nem ismerem), hogy az ilyen algoritmusoknak az igazi haszna is ott mutatkozik meg, ha statisztikai (ill. valószínűségszámítási) módszerekkel együttesen alkalmazzák.
A mai világban, főleg, ha valami internet-alapú témáról van szó – rengeteg adatot lehet gyűjteni mindenféléről.
Ez alapján az érintett témákban a preferenciák megállapítása szerintem ritkán csak egyszeri, legtöbbször inkább valamiféle folyamatos mintavétel eredménye.
Ezzel párhuzamban a párosítások is valószínűleg rendszeresen ismétlődnek, így az eredmények szintén statisztikai alapokon értékelhetőek. Így az időbeli változásokat jobban tudják kezelni.
@Szindbad: nézd, vannak friss tudományágak, amelyekben fél délutános gondolatmenetek csúcsnak számítanak. pl. én láttam a kilencvenes évek elején az informatikában a neurális hálókat. hoztak egy cikket, hogy egy nagy koponya kigondolt valamit, lefuttatta egy pár sejtes hálón, és az jött ki neki, hogy jó. na én leprogramoztam és lefuttattam egy tízszer akkora hálón, és kijött, hogy nem jó. aztán megnéztem, utánaszámoltam, és a faszi egy O(nlog(n))-es függvényt lecserélt egy O(n^2)-esre, csak kevés sejtnél ez nem volt érdekes, a konstans viszont kisebb volt, ezért tűnt kis hálón jobbnak. de senki nem számolt utána, senki nem ellenőrizte, hanem lehozták, mint a nagy koponya újítását egy tudományos lapban.
igen, a játékelmélet ennyit produkál(t 50 éve), és ez nóvum ott. függvényanalízisben már nehezebb lenne ilyenekkel messzire jutni.