Joko-teoria matematikaren atal bat da, zeinak dituen aldaketak aztertzen dituen. Hainbat arlotan aplikatzen da joko-teoria: ekonomian eta politikan esate baterako (baita afarien ordainketan ere). Artikulu honetan garraio-sareetan ere aplikatzen dela ikusiko dugu.
Garraio-sareak errepidez osaturiko sareak dira. Bertan, zenbait ibilgailu ibiltzen dira: kotxeak, furgonetak, kamioiak, motorrak, autobusak eta abar. Gainera, garraiobide bakoitzak erabakiak hartu ahal ditu errepidean; alegia, ibilgailu batek aurreko ibilgailua aurreratu ahal du edo errepidearen alde berean jarraitu ahal du. Hortaz, joko-teoria erabiliz, ikertu daiteke zein izango den garraiobide-sarearen egoera.
Oro har, garraio-sareetan ibilgailuen erabakiak denboraren arabera hartzen dira, hau da, ibilgailuek erabakiak hartzen dituzte bi lekuren arteko bidea (lantokitik etxera, esate baterako) ahalik eta lasterren egiteko. Artikulu honetan, jatorrizko tokiari A puntua deituko diogu eta xede lekuari B puntua. Horrela, pentsatuko dugu garraio-sareko elementu guztiak (kotxeak, kamioak, etab.) biderik lasterrena aukeratuz A puntutik B puntura joango direla.
Artikulu honetan aztertuko dugun eredu matematikoari Pigou-ren adibidea deitzen zaio. Bertan, A puntutik B puntura 10 kotxe mugituko dira eta, horretarako, bi bide posible daudela pentsatuko da (1 bidea eta 2 bidea izango dira). Horiek horrela, 1 bidea 2 bidea baino okerragoa da; zehazki, kotxe batek 1 bidea zeharkatzeko denbora segundo batekoa da; aldiz, 2 bidea zeharkatzeko, p segundo, non p 2 bidea aukeratutako kotxe kopuruaren proportzioa baita. Hau da, zazpi kotxe 1 bidetik joanez gero (eta, ondorioz, hiru kotxe 2 bidetik), 2 bidea hartzen duen kotxe bakoitzak 3/10 segundo behar du A puntutik B puntura joateko. Horrela, auto guztiek jatorritik xedera joateko behar duten denbora honakoa da: 7*1+3*3/10=79/10 segundo.
Aurreko guztia kontuan hartuz, honako galdera egin diezaiokegu geure buruari: zein izango da kotxeen banaketa egokiena auto guztiek A puntutik B puntura joateko behar duten denbora minimizatzeko? Problema honen ebazpena erraza da (ebazpenaren frogapena, berriz, ez hain erraza): autoak berdinki banatzen dira bideetan, hots, bost kotxek 1 bidea hartzen dute eta beste bost kotxek 2 bidea. Egoera honetan, auto guztiek jatorritik xedera joateko behar duten denbora hau izango da: 5*1+5*5/10=75/10 segundo.
Orain, joko-teoriaren ikuspuntutik aztertuko dugu problema hau. Horrela, kotxe bakoitzak 1 bidea edo 2 bidea aukeratu ahal du A puntutik B puntura lehenbailehen ailegatzeko. Horrela, joko matematiko bat eratu daiteke egoera honetan, non Nash-en orekak deskribatzen duen zein izango den kotxeen banaketa. Alegia, Nashen orekak esaten du zein bide aukeratuko duen auto bakoitzak haren bidaia-denbora minimizatzeko. Beraz, 1 bideko bidaia-denbora 1 segundo denez eta 2 bidekoa p segundo (p txikiago edo berdin bat izanik, proportzio bat delako), kotxe guztiek 2 bidea aukeratuko dute. Egoera honetan, auto guztiek jatorritik xedera joateko behar duten denbora ondokoa izango da: 0*1+10*1=10 segundo. Eta ohartu 10 segundo 75/10 segundo baino gehiago dela. Horrek esan nahi du Nashen orekan ageri den egoera ez dela kotxe guztien bidai-denbora minimizatzen duen banaketa; edo beste modu batean esanda, Nashen oreka ez dela kotxe-banaketa optimoa.
Adibide honen bidez ondorioztatu daiteke, beraz, erabaki berekoien ondorioz lortutako egoera ez dela zertan optimoa izan. Fenomeno hau ezaguna da joko-teoriaren arloan. Izan ere, joko-teorian esaten da Nashen oreka eraginkorra dela egoera optimoarekin bat egiten badu. Hortaz, Pigou-ren adibidearen kasuan, esan daiteke Nashen oreka ez dela eraginkorra.
Nash-en orekaren eraginkortasuna aztertzeko, anarkiaren kostua deituriko kontzeptua erabiltzen da joko-teorian. Kasu orokorrean, anarkiaren kostuak adierazten du zein den Nashen orekaren galera egoera optimoaren aldean; alegia, definitzen da Nashen orekan lortutako errendimendua eta errendimendu optimoaren zatiketa bezala (Pigou-ren adibidearen kasuan, errendimendua kotxe guztien bidai-denbora izango da). Definizio horri erreparatuz, anarkiaren kostuaren balioa bat da Nashen oreka eraginkorra denean eta, bestela, bat baino handiagoa da.
Pigou-ren adibidera bueltatuta, lortutako emaitzak kontuan hartuz, kasu honetan anarkiaren kostua honakoa da: 10/(75/10)=4/3. Beraz, esan daiteke Nashen orekaren ondorioz ageri den galera ez dela oso handia adibide honetan. [1] eta [2] artikuluetan Pigou-ren adibideko eredua orokortzen dute eta, haien emaitzen arabera, edozein garraio-sareren anarkiaren kostua beti 4/3 da, baldin eta ibilgailu batek bide bakoitza zeharkatzeko behar duen denbora x-ren funtzio lineala bada, x izanik ibilgailuen banaketa bideetan.
Erreferentzia bibliografikoak:
- Roughgarden, Tim eta Tardos, Éva (2002). How bad is selfish routing? J. ACM, 49 (2), 236–259. DOI:10.1145/506147.506153
- Roughgarden, Tim eta Tardos, Éva (2004). Bounding the inefficiency of equilibria in nonatomic congestion games. Games and Economic Behavior, 47 (2), 389-403. DOI:10.1016/j.geb.2003.06.004
Egileaz:
Josu Doncel Matematikan doktorea da eta UPV/EHUko Matematika Saileko irakaslea.