logo

HTML

Kóczy játékelmélet blogja

Tudomány, gazdaság, játékelmélet

Friss topikok

  • MAXVAL bircaman közíró: Én úgy tudom - a ballib médiákból - hogy a nem szavazók NEM szavazót jelentenek, hiszen pl. az ide... (2018.09.19. 05:36) Ki, hol és hogyan tartózkodik?
  • henceg new era: Brilliáns kifejtés, valóban. (2018.07.13. 11:59) Focielmélet
  • Neruo: "Magyarország egy konzervatív, keresztény ország." Ez egy nem túl alátámasztott kijelentés, de ok... (2018.05.16. 12:12) Megnézni a választókat
  • s: @maxval bircaman szeredőci szürke proletár: Faszért hallgatod? (2018.04.05. 15:24) Taktikai szavazás és egyensúly
  • chrisred: @/ms: Visszakanyarodtunk nagyjából ahhoz a verzióhoz, amit az elején állítottam, csak egy kicsit m... (2017.10.05. 05:36) Brutális burjánzás a Bundestagban

Közgazdasági Nobel díj 2012: Shapley és Roth

2012.10.15. 13:36 Kóczy László

roth-shapley.pngIdén is a játékelmélet vitte el a Nobel díjat! Shapley és Roth piactervezési és a stabil allokációk területén végzett munkásságukért kapták az elismerést. 

Kik is ők és mivel foglalkoztak? 

Az, hogy Shapley eddig nem kapott Nobel díjat, már kisebbfajta botrány. Olyan sokat tett a játékelmélet oly sok területéért, hogy nem volt szép dolog kihagyni a korábbi díjazottak közül. Mindenképp meg kell említeni a Shapley-értéket (Shapley, 1953), ami eredetileg nem csak azért volt simán "érték", mert a szerző a saját cikkében nem nevezi el saját magáról a bevezetett koncepciót, hanem, mert ez volt az első ilyen szemléletű megoldás. A Shapley-érték alkalmazása egyszerű játékokra, vagy más néven a Shapley-Shubik index a bonyolult súlyozott, minősített szavazási helyzetekben is megmutatja egy-egy döntéshozó befolyását, vagy hatalmát (Shapley-Shubik, 1954, magyarul l. Kóczy 2011, Kóczy-Pintér 2011)- éppen erről volt szó pénteken a QWERT Hatalom-estjén. Bár Shapley neve a Shapley-értékkel forrt össze, a másik hasonlóan népszerű megoldás, a mag kutatása terén is érdemeket szerzett, egyesek szerint a magot valójában ő találta ki, csak nem publikálta. Mindenesetre a mag nemürességét megfogalmazó Shapley-Bondareva tételt is ő bizonyította (Bondarevától függetlenül, Shapley, 1967). Mégis, Shapley most nem ezekért a dolgokért kapta az elismerést. 

Kereken 50 évvel ezelőtt publikálta David Gale-lel közösen az azóta Gale-Shapley algoritmusként is ismert késleltetett elfogadási algoritmust (Gale-Shapley, 1962), mely azóta számtalan felvételi rendszer, egyebek mellett a magyar középiskolai és egyetemi felvételi alapja lett. Az algoritmus titka, hogy stabil párosítást eredményez, azaz olyam módon kapcsolja össze a fiúkat a lányokkal, vagy a jelentkezőket az iskolákkal, hogy mindenki az elérhető legjobb partnert kapja. Ezzel Shapley egy teljesen új terület magját vetette el. Az már Roth érdeme, hogy ebből lett valami (Roth, 2008, magyarul l. Biró 2006, Kóczy 2009, 2010). Tíz évvel később felfedezte, hogy a kitűnően működő amerikai rezidensi felvételi egy, a GS algoritmussal ekvivalens módszeren alapszik (Roth, 1982, 1984). Tovább vizsgálva az algoritmust (Roth, 1985) matematikai magyarázatot talált bizonyos anomáliákra (Roth 1986), majd tevékenyen részt vett az algoritmus módosításában (Roth-Elliott, 1997, 1999), amikor a társadalmi változásoknak megfelelően (erősödő hallgatói mozgalmak, sok orvos-házaspár) az algoritmus is kisebb kiigazításra szorult. Roth munkássága eredménye, hogy több helyen az elméleti eredmények tükrében megváltoztatták a felvételi eljárásokat (Abdulkadiroğlu, Pathak, Roth, 2005; Abdulkadiroğlu, Pathak, Roth, Sönmez 2005).

Bár az egyetemi felvételi kimenetele egy jelentkező életét meghatározhatja, nem ez az algoritmus egyetlen alkalmazása. Már korábban beszámoltunk a vesecsere programokról, ahol a beteg és az élő donor közötti párosítás orvosi szempontok alapján történik (Roth, Sönmez, Ünver, 2007; Rees et al, 2009), de hogy ki kitől kap vesét, azt egy hasonló algoritmus segítségével határozzák meg sok országban. Sajnos kevés az élő donor Magyarországon, talán ezért sincs tudomásunk hasonló programról hazánkban. 

Végül meg kell említenünk, hogy a piactervezés nem merül ki a párosításokban. Ide tartoznak az aukciók és a hozzárendelési játékok is. Itt a két oldal összekapcsolása pénzmozgással is járhat. Évek óta ilyen módszerekkel értékesíti a Google a keresőszavakat és ezt a hirdetési platformját a televíziós társaságok rendelkezésére is bocsátotta. Egy ilyen tökéletesen automatizált rendszer lehetőséget ad arra, hogy minden hirdető pontosan az általa kívánatosnak ítélt időpontokban, egy számára elfogadható áron hirdessen, míg a hirdetési felület, például egy televíziós csatorna egyszerre tudja értékesíteni a teljes reklámidejét (igaz, időnként alacsonyabb áron) és élvezi a magas bevételt a frekventált idősávokban. 

Hivatkozások

Abdulkadiroğlu, Atila, Pathak, Parag, Roth, Alvin E. (2005) The New York City High School Match, American Economic Review 95 (2) 364-367.

Abdulkadiroğlu, Atila, Pathak, Parag, Roth, Alvin E., Sönmez, Tayfun (2005) The Boston Public School Match, American Economic Review 95 (2) 368-371.

Biró, P. (2006) Stabil párosítási modellek és ezeken alapuló központi párosító programok, Szigma 37 (3-4) 153-175.

Gale, D.- Shapley, LS. (1962) College Admissions and the Stability of Marriage, The American Mathematical Monthly 69 (1) 9-15.

Kóczy L. Á. (2009): Központi felvételi rendszerek. Taktikázás és stabilitás, Közgazdasági Szemle 56, 422-442.

Kóczy L. Á. (2010): A magyarországi felvételi rendszerek sajátosságai, Közgazdasági Szemle 57, 142-164.

Kóczy L. Á. (2011): Lisszaboni kilátások, Közgazdasági Szemle 58, 1045-1058.

Kóczy L. Á., Pintér M. P. (2011): Az ellenzék ereje - általánosított súlyozott szavazási játékok, Közgazdasági Szemle 58, 543-551.

Rees, Michael A. - Kopke, Jonathan E. - Pelletier, Ronald P. - Segev, Dorry L. - Rutter, Matthew E. - Fabrega, Alfredo J. - Rogers, Jeffrey - Pankewycz, Oleh G. - Hiller, Janet - Roth, Alvin E. - Sandholm, Tuomas - Ünver, M. Utku - Montgomery, Robert M. (2009) A Nonsimultaneous, Extended, Altruistic-Donor Chain. New England Journal of Medicine 360(11) 1096-1101.

Roth, Alvin E. (1982) The Economics of Matching: Stability and Incentives, Mathematics of Operations Research, 7 (4) 617-628.

Roth, Alvin E. (1984) The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory, Journal of Political Economy, 92 (6) 991-1016.

Roth, Alvin E. (1985) The college admissions problem is not equivalent to the marriage problem, Journal of Economic Theory, 36 (2) 277-288.

Roth, Alvin E. (1986) On the allocation of residents to rural hospitals: a general property of two-sided matching markets, Econometrica, 54 (2) 425-427.

Roth, Alvin E. (1991) A Natural Experiment in the Organization of Entry-Level Labor Markets: Regional Markets for New Physicians and Surgeons in the United Kingdom, American Economic Review, 81 (3) 414-440.

Roth, Alvin E. (2008) Deferred acceptance algorithms: history, theory, practice, and open questions, International Journal of Game Theory, 36 (3-4) 537-569.

Roth, Alvin E., Sotomayor Marilda (1990) Two-sided matching. A study in game-theroretic modeling and analysis. Cambridge University Press, Cambridge.

Roth, Alvin E., Peranson, Elliott (1997) The effects of the change in the NRMP matching algorithm, Journal of the American Medical Association 278 (9) 729-732.

Roth, Alvin E., Peranson, Elliott (1999) The Redesign of the Matching Market for American Physicians : Some Engineering Aspects of Economic Design, American Economic Review 99 (4) 748-780.

Roth, Alvin E. - Sönmez, Tayfun - Ünver, M. Utku (2004) Kidney Exchange. Quarterly Journal of Economics, 119 (2) 457-488.

Roth, Alvin E. - Sönmez, Tayfun - Ünver, M. Utku (2007) Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences. American Economic Review, 97, 3, June 2007, 828-851.

Shapley, LS (1953) A Value for n-Person Games. In: Kuhn, Harold W., Tucker, A.W. (eds.): Contributions to the Theory of Games, Princeton University Press. 

Shapley, LS (1967) On balanced Sets and Cores, Naval Research Logistics Quarterly 14 (4) 453-460.

Shapley, LS - Shubik, M (1954) A method for evaluating the distribution of power in a committee system. The American Political Science Review 48 (3) 787-792.

5 komment

Címkék: felvételi aukció nobel díj játékelmélet párosítás párosítások al roth lloyd s shapley

A bejegyzés trackback címe:

https://koczy.blog.hu/api/trackback/id/tr244849766

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

xylon 2012.10.15. 21:16:40

Szep munka. Van valahol egy rovidebb lista a jatekelmeleti alapmuvekrol, hogy az ember kiokositsa magat alap szinten?

Neruo 2012.10.15. 21:55:45

@xylon:

Egészen pontosan mi számít alapszintnek? Az alapművek meglehetősen technikai jellegűek. Viszonyításképpen a lényegében alapmű: books.google.fr/books/about/Theory_of_Games_and_Economic_Behavior_Co.html?id=_aIGYI-jGEcC&redir_esc=y

(de persze ezt már szinte senki nem olvassa...)

Áttekintésképpen tudom ajánlani:

www.matud.iif.hu/2009-05.pdf

Kóczy László · http://koczy.blog.hu 2012.10.15. 23:58:58

@xylon: A hivatkozott magyar nyelvű cikkek a szélesebb körű olvasóközönségnek íródtak, érdemes lehet ezekkel barátkozni.Ezek után jönnek a könyvek. Az Osborne-Rubinstein könyvek jók és ingyenesen letölthetők. books.osborne.economics.utoronto.ca/
Én mégis az Owen, vagy a Hans Peters féle Game Theory könyvből tanítok. Ebben a témában ajánlom Roth-Sotomayor könyvét, ami egyrészt tényleg az alapoktól kezdi, másrészt könnyen olvasható.

xylon 2012.10.16. 00:45:28

@Neruo: @Kóczy László: Koszonom mindkettotoknek. Megnezem eloszor ezeket.