In teoria jocurilor, nu exista o cale clara catre echilibru

141

In 1950, John Nash – matematicianul prezentat ulterior in cartea si filmul „O minte frumoasa” – a scris o lucrare de doua pagini care a transformat teoria economiei. Ideea sa cruciala, dar extrem de simpla, a fost ca orice joc competitional are o notiune de echilibru: o colectie de strategii, una pentru fiecare jucator, astfel incat niciun jucator nu poate castiga mai mult trecand unilateral la o strategie diferita.

Conceptul de echilibru al lui Nash, care i-a obtinut premiul Nobel in economie in 1994, ofera un cadru unificat pentru intelegerea comportamentului strategic nu numai in economie, ci si in psihologie, biologie evolutiva si o serie de alte domenii. Influenta sa asupra teoriei economice „este comparabila cu cea a descoperirii dublei helixuri ADN in stiintele biologice”, a scris Roger Myerson de la Universitatea din Chicago, un alt nobel in economie.

Cand jucatorii se afla in echilibru, nimeni nu are un motiv sa se rataceasca. Dar cum ajung jucatorii la echilibru in primul rand? Spre deosebire de, sa zicem, o minge rostogolindu-se in jos si venind sa se odihneasca pe o vale, nu exista forte evidente care sa ghideze jucatorii spre un echilibru Nash.

„A fost intotdeauna un sporn in partea microeconomistilor”, a spus Tim Roughgarden, un informatician teoretic la Universitatea Stanford. „Foloseste aceste concepte de echilibru si le analizeaza ca si cum oamenii vor fi in echilibru, dar nu exista intotdeauna o explicatie satisfacatoare a motivului pentru care oamenii vor fi in echilibru Nash, in schimb nu vor face fata doar unuia”.

Daca oamenii joaca un joc o singura data, este adesea nejustificat sa va asteptati sa gaseasca un echilibru. Acest lucru este in special in cazul in care – asa cum este obisnuit in lumea reala – fiecare jucator nu stie decat cat valoreaza ea insasi rezultatele diferite ale jocului si nu cat de mult o fac colegii sai. Dar daca oamenii pot juca in mod repetat, poate ca ar putea invata din primele runde si s-ar putea orienta rapid catre un echilibru. Totusi, incercarile de a gasi metode de invatare eficiente au devenit intotdeauna uscate.

„Economistii au propus mecanisme pentru cum poti converge [rapid] la echilibru”, a spus Aviad Rubinstein, care termina un doctorat in informatica teoretica la Universitatea din California, Berkeley. Dar pentru fiecare astfel de mecanism, a spus el, „exista jocuri simple pe care le puteti construi acolo unde nu functioneaza.”

Acum, Rubinstein si Yakov Babichenko, matematician la Institutul Tehnologic-Israel din Haifa, au explicat de ce. Intr-o lucrare postata online in septembrie anul trecut, ei au dovedit ca nicio metoda de adaptare a strategiilor ca raspuns la jocurile anterioare – indiferent cat de comuna, creativa sau inteligenta – nu va converge eficient pana la un echilibru aproximativ Nash pentru fiecare joc posibil. Este „un rezultat negativ foarte maturat”, a spus Roughgarden.

Economistii folosesc adesea analizele de echilibru Nash pentru a justifica reformele economice propuse, a spus Myerson. Dar noul rezultat spune ca economistii nu pot presupune ca jucatorii de jocuri vor ajunge la un echilibru Nash, decat daca pot justifica ceea ce este special pentru jocul respectiv. „Daca incercati sa va dati seama daca jocul dvs. va gasi cu usurinta un echilibru”, a spus Noam Nisan, un informatician de la Universitatea Evreiasca, „trebuie sa oferiti argumentul pentru care ar fi”.

Jocuri Multiplayer

In unele jocuri simple, este usor de remarcat echilibrul Nash. De exemplu, daca prefer mancarea chineza si preferi italianul, dar preferinta noastra cea mai puternica este sa luam masa impreuna, doua echilibre evidente sunt pentru amandoi sa mergem la restaurantul chinezesc sau amandoi sa mergem la restaurantul italian. Chiar daca incepem sa ne cunoastem doar propriile preferinte si nu ne putem comunica strategiile inainte de joc, nu va trece prea multe runde de conexiuni ratate si mese solitare inainte sa ne intelegem pe deplin preferintele celuilalt si, speram, sa ne gasim drumul. la unul sau altul echilibru.

Dar imaginati-va daca planurile de cina implica 100 de oameni, fiecare dintre ei a decis preferinte cu care altii ar dori sa ia masa si nimeni nu stie preferintele altcuiva. Nash a dovedit in 1950 ca chiar si jocuri mari, complicate ca acesta, au intotdeauna un echilibru (cel putin daca conceptul de strategie este largit pentru a permite alegeri aleatorii, cum ar fi alegerea restaurantului chinez cu 60% procente). Dar Nash – care a murit intr-un accident de masina in 2015 – nu a dat nicio reteta despre cum sa calculeze un astfel de echilibru.

Prin scufundarea in neplacutul dovezii lui Nash, Babichenko si Rubinstein au reusit sa arate ca, in general, nu exista o metoda garantata pentru jucatori sa gaseasca chiar si un echilibru aproximativ Nash, decat daca isi spun reciproc practic totul despre preferintele respective. Si pe masura ce numarul jucatorilor dintr-un joc creste, timpul necesar pentru toata aceasta comunicare devine rapid prohibitiv.

De exemplu, in jocul cu 100 de jucatori, exista 2100 de moduri in care jocul ar putea juca si, prin urmare, 2100 de preferinte pe care fiecare jucator trebuie sa le imparta. Prin comparatie, numarul de secunde care au trecut de la Big Bang este de aproximativ 259.

Acest blocaj de comunicare inseamna ca orice metoda posibila de adaptare a strategiilor de la runda la runda nu va reusi sa ghideze jucatorii in mod eficient catre un echilibru Nash pentru cel putin unele jocuri complexe (cum ar fi un joc de 100 de jucatori cu preferinte complicate). La urma urmei, in fiecare runda, jucatorii invata doar cateva informatii noi unul despre celalalt: cat de fericiti sunt cu aranjamentul de cina unic care a fost jucat. Asadar, va dura ordinul de 2100 de runde inainte sa stie totul despre valorile celuilalt (pana la care, probabil, restaurantele chinezesti si italiene vor fi iesit din afaceri).

„Daca acest lucru va dura mai mult decat varsta universului”, a spus Sergiu Hart, un teoretician al jocurilor de la Universitatea Evreiasca din Ierusalim, „este complet inutil, desigur.”

Poate parea firesc, aproape evident, faptul ca jucatorii vor trebui uneori sa stie totul despre valorile celuilalt pentru a gasi un echilibru Nash. Noua lucrare arata, insa, ca aceasta aceeasi limitare este valabila chiar daca jucatorii sunt dispusi sa faca un echilibru aproximativ Nash – o constatare importanta cand vine vorba de aplicatii din lumea reala, in care un rezultat apropiat de un echilibru Nash este adesea destul de bine.

Rezultatul lui Babichenko si Rubinstein nu implica faptul ca toate, sau chiar majoritatea, vor fi supuse acestei limitari – doar ca unele jocuri vor. Multe dintre jocurile pe care economistii le folosesc pentru a modela lumea reala au o structura suplimentara care reduce mult cantitatea de informatii pe care trebuie sa le comunice fiecare jucator. De exemplu, in cazul in care 100 de noi sunt fiecare alegand dintre cele doua rute pentru naveta de dimineata, probabil ca nu -mi pasa care jucatorii merg pe fiecare ruta – va intereseaza doar cat de multe du – te. Aceasta inseamna ca colectia dvs. de preferinte va avea un grad ridicat de simetrie si puteti transmite in intregime intr-un cuplu de propozitii bine alese in loc de 2100 dintre ele.

Economistii ar putea folosi astfel de argumente pentru a justifica de ce echilibrul Nash ar putea fi atins pentru anumite jocuri. Dar noul rezultat implica faptul ca astfel de justificari trebuie facute de la caz la caz; nu exista niciun argument criminal care sa acopere toate jocurile tot timpul.

Ba mai mult, chiar daca multe jocuri care au evoluat impreuna cu civilizatia pot fi adaptate la astfel de simplificari, era Internetului da nastere la tot felul de noi jocuri cu multi jucatori, de la site-uri de intalnire pana la tranzactionarea de stocuri online. „In acest moment, nu avem evolutia lenta a umanitatii care ne conduce doar spre jocuri unde este usor sa gasim un echilibru”, a spus Nisan. „Proiectam noi jocuri si, daca presupunem ca vom obtine un echilibru, de multe ori vom gresi.”

In viata reala, oamenii nu joaca adesea jocuri la echilibru, lucru pe care economistii il constientizeaza cu multa atentie, a spus Andrew McLennan, economist la Universitatea Queensland din Brisbane, Australia. Dar, a spus el, „economia nu are nicio structura teoretica pentru a intreba cat de precisa poate fi o economie”. Rezultatele teoretice de informatica precum cele noi de la Babichenko si Rubinstein „ar trebui sa fie o inspiratie pentru a aborda problema intr-un mod formal”, a spus el.

Insa cele doua domenii au mentalitati foarte diferite, ceea ce poate impiedica comunicarea interdisciplinara: Economistii tind sa caute modele simple care sa surprinda esenta unei interactiuni complexe, in timp ce informaticienii teoreticieni sunt adesea mai interesati sa inteleaga ce se intampla pe masura ce modelele cresc din ce in ce mai complexe. “Mi-as dori ca colegii mei din economie sa fie mai constienti, mai interesati de ceea ce face informatica”, a spus McLennan.

Un consilier de incredere

Noua lucrare traseaza o linie de impartire stralucitoare intre echilibrul Nash si un alt concept de echilibru mai general, care a ajuns la importanta la 24 de ani de la lucrarea lui Nash. „Echilibrul corelat” – propus in 1974 de Robert Aumann, un alt nobilist in economie – prezinta un scenariu in care jucatorii de jocuri primesc fiecare sfat de la un mediator de incredere (sau „dispozitiv corelat”) despre ce strategie sa joace. Sfaturile mediatorului formeaza un echilibru corelat daca niciun jucator nu are un stimulent sa se abata de la sfaturile primite, daca considera ca ceilalti jucatori urmeaza fiecare sfatul lor.

La inceput, acest lucru ar putea suna ca o constructie arcana, dar de fapt folosim echilibrul corelat tot timpul – ori de cate ori, de exemplu, lasam o moneda sa decida daca vom merge pentru chinezi sau italieni, sau permitem un semafor sa dicteze. care dintre noi va trece mai intai printr-o intersectie.

In aceste doua exemple, fiecare jucator stie exact ce sfaturi ii ofera „mediatorului” celuilalt jucator, iar sfaturile mediatorului ii ajuta in esenta pe jucatori sa coordoneze ce echilibru Nash vor juca.

Dar cand jucatorii nu stiu exact ce sfaturi primesc ceilalti – doar modul in care diferitele tipuri de sfaturi sunt corelate intre ele – Aumann a aratat ca setul de echilibre corelate poate contine mai mult decat simple combinatii de echilibre Nash: poate include forme de joc care nu sunt deloc echilibrul Nash, dar care uneori au ca rezultat un rezultat social mai pozitiv decat oricare dintre echilibrele Nash. De exemplu, in unele jocuri in care cooperarea ar oferi un profit total mai mare pentru jucatori decat sa actioneze egoist, mediatorul poate uneori indemna jucatorii sa coopereze, retinand doar ce sfaturi ii ofera celorlalti jucatori. Aceasta constatare, a spus Myerson, a fost „un surub din senin”.

Si chiar daca un mediator poate da sfaturi diferite, setul de echilibre corelate ale unui joc, care este reprezentat de o colectie de ecuatii liniare si inegalitati, este mai abordabil din punct de vedere matematic decat setul de echilibre Nash. “Acest alt mod de a gandi despre asta, matematica este cu atat mai frumoasa”, a spus Myerson.

In timp ce Myerson a numit viziunea lui Nash asupra teoriei jocurilor „unul dintre avansurile intelectuale deosebite ale secolului XX”, el vede echilibrul corelat ca poate un concept si mai natural decat echilibrul Nash. El a sustinut in mai multe randuri ca „daca exista viata inteligenta pe alte planete, in majoritatea lor ar fi descoperit echilibrul corelat inainte de echilibrul Nash.”

Cand vine vorba de runde repetate de joc, multe dintre cele mai naturale moduri prin care jucatorii ar putea alege sa isi adapteze strategiile converg, intr-un anumit sens, la echilibrul corelat. Luam, de exemplu, abordari de „minimizare a regretului”, in care inainte de fiecare runda, jucatorii cresc probabilitatea de a utiliza o strategie data daca regreta ca nu au mai jucat-o in trecut. Minimizarea regretului este o metoda „care are o asemanare cu viata reala – acordand atentie la ceea ce a functionat bine in trecut, combinat cu experimentarea ocazionala”, a spus Roughgarden.

Pentru multe abordari care sa reduca regretul, cercetatorii au aratat ca jocul va conveni rapid la un echilibru corelat in urmatorul sens surprinzator: dupa ce s-au jucat probabil 100 de runde, istoricul jocului va arata in esenta la fel ca si cum un mediator i-ar fi sfatuit pe jucatori. tot acest timp. Este ca si cum „dispozitivul [corelat] ar fi fost intr-un fel implicit gasit, prin interactiune”, a declarat Constantinos Daskalakis, un informatician teoretic al Institutului de Tehnologie din Massachusetts.

Pe masura ce jocul continua, jucatorii nu vor ramane neaparat la acelasi echilibru corelat – dupa 1.000 de runde, de exemplu, s-ar putea sa fi derivat intr-un nou echilibru, astfel incat acum istoria lor de 1.000 de jocuri arata ca si cum ar fi fost ghidata de un alt mediator decat inainte. Procesul este o reminiscenta a ceea ce se intampla in viata reala, a spus Roughgarden, in timp ce normele sociale despre care trebuie sa se joace echilibrul evolueaza treptat.

In tipurile de jocuri complexe pentru care echilibrul Nash este greu de atins, echilibrul corelat este „concurenta conducatoare naturala” pentru un concept de solutie de inlocuire, a spus Nisan.

Faptul ca umanitatea a venit cu ideea echilibrului Nash inainte de echilibrul corelat poate fi doar un accident al istoriei, a spus Myerson. „Oamenii cred ca ideile care au evoluat mai devreme sunt cele mai fundamentale”, a spus el, dar in acest caz, „cine sa spuna ce este o idee mai fundamentala?”

Cu toate acestea, rezultatele referitoare la convergenta rapida nu implica faptul ca nici o runda individuala a jocului se joaca la un echilibru corelat – doar ca istoria pe termen lung a jocului este. Acest lucru inseamna, a subliniat Rubinstein, ca abordarile de minimizare a regretului nu sunt intotdeauna o alegere ideala pentru jucatorii rationali intr-o etapa data. Aceasta lasa intrebarea „Ce vor face jucatorii rationali?” fara raspuns definitiv.

Aceasta intrebare „a fost explorata inca de dinainte de a ma naste”, a spus Rubinstein, in varsta de 30 de ani. – Dar inca este inceputul.

In teoria jocurilor, nu exista o cale clara catre echilibru

Jocuri Multiplayer

Un consilier de incredere

Populare

Afacere proprie, angajat la stat sau angajat la privat? Pro &...

Cum alegi cel mai bun brad de Crăciun?

Afla cum iti poti lansa o mica afacere folosind un spatiu...

Top 10 cele mai supraevaluate filme din toate timpurile

10 regizori care au facut un film de groaza si au...

10 documentare care au schimbat perceptia publicului

Top 10 interviuri controversate cu celebritati din toate timpurile

Top 10 cele mai memorabile momente ale premiilor Oscar

Cum se schimba viata atunci cand intri in cercurile sociale ale...

10 povesti ciudate din lumea rap pe care sa le cunosti