Vés al contingut

Equilibri de Nash

De la Viquipèdia, l'enciclopèdia lliure

En la teoria de jocs, l'equilibri de Nash (per John Forbes Nash, qui el va proposar) és un concepte que fa referència a la solució d'un joc entre dos o més jugadors, en el qual se suposa que cada jugador coneix les estratègies d'equilibri dels altres jugadors, i cap jugador té res a guanyar si només canvia unilateralment la seva pròpia estratègia.[1]

Si cada jugador ha optat per una estratègia i cap jugador es pot beneficiar canviant la seva estratègia si els altres jugadors conserven la seva sense canvis, el conjunt d'opcions estratègiques i els guanys corresponents constitueixen un equilibri de Nash. La implicació pràctica i general és que quan els jugadors actuen també en els interessos del grup, llavors ells estan en millor situació que si actuessin en els seus interessos individuals per si sols.

Com que l'equilibri de Nash se centra en les preferències de cada individu, es poden produir resultats antiintuïtius. Pot haver-hi un equilibri de Nash en cas que si els jugadors poguessin coordinar-se, tots canviarien d'estratègia. El joc de la «caça del cérvol» és un exemple d'aquest fet.

En poques paraules, Amy i Phil es troben en equilibri de Nash si Amy pren la millor decisió que pot, tenint en compte la decisió de Phil, i Phil fa la millor decisió que pot, tenint en compte la decisió d'Amy. De la mateixa manera, un grup de jugadors es troben en equilibri de Nash si cada un fa la millor decisió que pot, tenint en compte les decisions dels altres. L'equilibri de Nash no significa necessàriament la millor recompensa per a tots els jugadors involucrats, i en molts casos, tots els jugadors poden millorar els seus beneficis si es poguessin posar-se d'acord sobre les diferents estratègies de l'equilibri de Nash: per exemple, les empreses que competeixen la formació d'un càrtel per tal d'augmentar els seus guanys.

El concepte d'equilibri de Nash no és original de John Forbes Nash, ja que Antoine-Augustin Cournot demostrà com trobar allò que avui en dia anomenem equilibri de Nash per a la competició de Cournot. Per tant, alguns autors es refereixen a aquest concepte com a equilibri de Cournot-Nash o equilibri de Nash-Cournot. Tot i així, fou Nash qui demostrà per primera vegada, a la seva tesi Non-cooperative games (1950) que han d'existir equilibris de Nash per a qualsevol joc finit amb qualsevol nombre de jugadors. Fins llavors, el resultat només s'havia demostrat per a jocs de suma nul·la per a dos jugadors, gràcies a John von Neumann i Oskar Morgenstern el 1947.[2]

Aplicacions

[modifica]

Els estudiosos de teoria de jocs utilitzen el concepte d'equilibri de Nash per analitzar el resultat de la interacció estratègica de diversos prenedors de decisions, proporcionant una forma de predir el que succeirà si diverses persones o institucions estan prenent decisions a la vegada, i si el resultat depèn de les decisions dels altres. La idea bàsica subjacent és que no podem predir el resultat de les decisions dels prenedors de decisions múltiples, si analitzem aquestes decisions de manera aïllada. En el seu lloc, hem de preguntar el que cada jugador hauria de fer, tenint en compte la presa de decisions dels altres.

L'equilibri de Nash s'ha utilitzat per analitzar les situacions hostils, com la guerra i la cursa armamentista[3] (vegeu dilema del presoner), i també com el conflicte pot ser mitigat per la interacció repetida (vegeu Estira-i-arronsa). També s'ha utilitzat per estudiar en quina mesura les persones amb preferències diferents poden cooperar (vegeu batalla dels sexes), i si van a córrer riscos per aconseguir un resultat cooperatiu (vegeu caça del cérvol). S'ha utilitzat per estudiar l'adopció d'estàndards tècnics, i també l'aparició del pànic bancari i la crisi monetària (vegeu joc de la coordinació). Altres aplicacions inclouen el flux de trànsit (vegeu principi de Wardrop), la forma d'organitzar subhastes (vegeu teoria de la subhasta), el resultat dels esforços desplegats per diverses parts en el procés de l'educació,[4] i àdhuc els penals en el futbol (vegeu joc de les monedes).[5]

Història

[modifica]

Una versió del concepte d'equilibri de Nash va ser utilitzat per primera vegada per Antoine Augustin Cournot en la seva teoria de l'oligopoli (1838). En la teoria de Cournot, les empreses trien la quantitat de sortida que han de produir per maximitzar el seu propi benefici. No obstant això, la millor sortida per a una empresa depèn dels resultats de les altres. Un equilibri de Cournot es produeix quan la producció de cada empresa maximitza els seus beneficis, donada la sortida de les altres empreses, la qual cosa és una estratègia pura d'equilibri de Nash.

En la moderna teoria de jocs el concepte d'equilibri de Nash està definit en termes d'estratègies barrejades, on els jugadors trien una distribució de probabilitat sobre les possibles accions. El concepte d'estratègia barrejada d'equilibri de Nash va ser introduït per John von Neumann i Oskar Morgenstern en el seu llibre de 1944 La Teoria de Jocs i el Comportament Econòmic. No obstant això, la seva anàlisi es limita al cas especial de jocs de suma zero. Van demostrar que un equilibri de Nash en estratègies mixtes existeix per a qualsevol joc de suma zero amb un conjunt finit d'accions. La contribució de John Forbes Nash, en l'article de 1951 Dels Jocs no Cooperatius va ser la definició d'una estratègia barrejada d'equilibri de Nash per a qualsevol joc amb un conjunt finit d'accions i demostrar que almenys ha d'existir un (estratègia barretjada) equilibri de Nash en un joc com aquests.

Definicions

[modifica]

Definició informal

[modifica]

Informalment, un conjunt d'estratègies és un equilibri de Nash si cap jugador pot fer res per canviar unilateralment la seva estratègia per obtenir un resultat millor. Per veure el que això significa, imagineu que a cada jugador se li han dit les estratègies que utilitzen els altres. Suposem llavors que cada jugador es pregunta a si mateix: "Conèguent les estratègies dels altres jugadors, i sabent que el tractament de les estratègies dels altres jugadors no canviaran, em puc beneficiar canviant la meva estratègia?"

Si qualsevol jugador pot respondre "Sí", llavors aquest conjunt d'estratègies no és un equilibri de Nash. Però si cada jugador prefereix no canviar (o li és indiferent canviar o no), llavors el conjunt d'estratègies és un equilibri de Nash. Per tant, cada estratègia en un equilibri de Nash és la millor resposta a totes les altres estratègies en aquest equilibri.[6]

L'equilibri de Nash a vegades pot semblar irracional des de la perspectiva d'una tercera persona. Això és degut al fet que l'equilibri de Nash no és l'òptim de Pareto.

L'equilibri de Nash també pot tenir conseqüències no racionals en els jocs seqüencials, ja que els jugadors poden "amenaçar" a l'altre amb maniobres no-racionals. Per a aquest tipus de jocs l'equilibri de Nash perfecte de subjocs pot ser més significatiu, com una eina d'anàlisi.

Definició formal

[modifica]

Per treure el màxim partit d'aquesta secció es recomana la lectura prèvia de l'article o articles:

  1. Teoria de jocs
  2. Estratègia (teoria de jocs)


Sigui (S, f) un joc, on S és el conjunt de perfils d'estratègia i f és el conjunt de perfils de beneficis. Sigui un perfil d'estratègia de tots els jugadors excepte per al jugador . Quan cada jugador escull les estratègies que conformen el perfil d'estratègia llavors el jugador obté el benefici . Cal notar que el benefici depèn del perfil d'estratègia escollit, és a dir, de l'estratègia escollida pel jugador així com de les estratègies escollides per tots els antres jugadors. Un perfil d'estratègia és un equilibri de Nash si cap desviació unilateral en l'estratègia de cap dels jugadors és profitosa, és a dir

Un joc pot tenir un equilibri de Nash d'estratègia pura o un equilibri de Nash en la seva extensió d'estratègia barrejada (en què s'escull una estratègia pura de forma estocàstica amb una freqüència determinada). Nash demostrà que, si es permeten estratègies mesclades, llavors tot joc de n jugadors en què tot jugador pot escollir entre un nombre finit d'estratègies admet, com a mínim un equilibri de Nash.

Quan la desigualtat anterior se subjecta estrictament (amb en lloc de ) per a tots els jugadors i totes les estratègies alternatives factibles, llavors l'equilibri es classifica com un equilibri de Nash estricte. Si per contra, per algun jugador, no és la igualtat exacta entre i alguna altra estratègia en el conjunt S, llavors l'equilibri es classifica com un equilibri feble de Nash.

Exemples

[modifica]

Joc de competició

[modifica]
Matriu de beneficis d'un joc de competició
Jugador 2 tria '0' Jugador 2 tria '1' Jugador 2 tria '2' Jugador 2 tria '3'
Jugador 1 tria '0' 0, 0 2, -2 2, -2 2, -2
Jugador 1 tria '1' -2, 2 1, 1 3, -1 3, -1
Jugador 1 tria '2' -2, 2 -1, 3 2, 2 4, 0
Jugador 1 tria '3' -2, 2 -1, 3 0, 4 3, 3

En una possible formulació d'un joc de benefici per a dos jugadors ambdós jugadors escullen simultàniament un nombre enter de 0 a 3; els dos jugadors guanyen un nombre de punts igual al menor dels dos nombres i, a més, si un jugador escull un nombre superior a l'altre, haurà de donar dos punts al seu contrincant. Aquest joc té un únic equilibri de Nash: que tots dos jugadors escullin el 0 (indicat en vermell a la matriu de beneficis). Qualsevol altra elecció d'estratègies es pot millorar si un dels jugadors baixa el seu nombre a una unitat per sota de l'escollit per l'altre jugador. En la taula de la dreta, per exemple, si els jugadors comencen a la casella de color verd, el jugador 1 es beneficiaria movent-se a la casella porpra escollint un nombre menor mentre que el jugador 2 ho faria movent-se a la casella blava escollint també un nombre menor.

Si el joc es modifica de forma que els dos jugadors guanyen la quantitat escollida si escullen el mateix nombre i en cas contrari no guanyen res, llavors hi ha quatre equilibris de Nash.

Joc de coordinació

[modifica]
Matriu de beneficis d'un joc de coordinació
El jugador 2 adopta l'estratègia 1 El jugador 2 adopta l'estratègia 2
El jugador 1 adopta l'estratègia 1 A, A B, C
El jugador 1 adopta l'estratègia 2 C, B D, D

El joc de coordinació és un joc simètric de dos jugadors i dues estratègies, amb la matriu de beneficis que es mostra al costat i en la qual els beneficis compleixen i . D'aquesta manera els jugadors han de cooperar en una de les dues estratègies per aconseguir un benefici elevat; si no cooperen obtindran un benefici menor.

Un exemple famós d'aquest tipus de joc és l'anomenat la caça del cérvol, en el joc de dos jugadors poden optar per caçar un cérvol o un conill, la primera estratègia proporciona més carn (4 unitats d'utilitat) que el segon (1 unitat d'utilitat). L'advertència és que el cérvol ha de ser caçat de forma cooperativa, de manera que si s'intenta per un jugador la caça del cérvol, mentre que l'altre caça el conill, que es produirà una falla en la caça (0 unitats d'utilitat), mentre que si tot-dos el cacen, es repartiran els resultats (2, 2). El joc per tant, presenta dos equilibris al (cérvol, cérvol) i (conill, conill) i per tant, l'estratègia òptima dels jugadors depèn de la seva expectativa respecte al que l'altre jugador pot fer. Si un caçador confia que l'altra anirà a la caça del cérvol, ha de caçar el cérvol, però si ell sospita que l'altre anirà a la caça del conill, ha de caçar el conill. Aquest joc va ser utilitzat com una analogia per a la cooperació social, ja que gran part del benefici augmenta en el cas de persones en societat depèn del fet que les persones cooperin i tinguin confiança implícitament entre elles per actuar d'una manera que correspongui amb la cooperació.

Un altre exemple d'un joc de coordinació és l'escenari on dues tecnologies estan disponibles per a dues empreses amb productes compatibles, i han de triar una estratègia per convertir-se en l'estàndard del mercat. Si les dues empreses estan d'acord en la tecnologia escollida, s'espera que les dues empreses tenguin vendes altes. Si les empreses no estan d'acord en la tecnologia estàndard de resultat, les vendes seran minses. Ambdues estratègies són equilibris de Nash del joc.

Conduir en una carretera, i haver de triar entre conduir per l'esquerra o per conduir per la dreta de la carretera, és també un joc de coordinació. Per exemple, amb 100 pagaments que vol dir que no xoc i 0 significa un xoc, el joc de coordinació pot ser definit amb la matriu de pagaments següent:

El joc de conduir
Conduir per l'esquerra Conduir per la dreta
Conduir per l'esquerra 100, 100 0, 0
Conduir per la dreta 0, 0 100, 100

En aquest cas hi ha dos equilibris de Nash en estratègies pures, quan tots dos opten per conduir o bé a l'esquerra o bé a la dreta. Si admetem les estratègies barrejades (en una estratègia pura és triat a l'atzar, sense perjudici d'alguna probabilitat fixa), llavors hi ha tres equilibris de Nash per al mateix cas: dos que hem vist en la forma d'estratègia pura, on les probabilitats són (0%, 100%) per al primer jugador, (0%, 100%) per al segon jugador, i (100%, 0%) per al primer jugador, (100%, 0%) per al segon jugador, respectivament. S'afegeix una altra on les probabilitats de cada jugador és (50%, 50%).

El dilema del presoner

[modifica]

(notau les diferències en l'orientació de la matriu de pagaments)

Exemple de matriu de pagaments
Coopera No coopera
Coopera 3, 3 0, 5
No coopera 5, 0 1, 1

El dilema del presoner té la mateixa matriu de pagaments, com es mostra en el joc de coordinació, però ara . Com que i , cada jugador millora la seva situació pel canvi d'estratègia # 1 a l'estratègia # 2 sense importar el que l'altre jugador decideixi. El dilema del presoner per tant, té un únic equilibri de Nash: ambdós jugadors trien l'estratègia # 2, "no coopera"). El que sempre ha fet d'aquest cas, un interessant estudi és el fet que (és a dir, "ambdós no cooperen" és globalment inferior a "tots dos segueixen sent lleials"). L'estratègia òptima a nivell global és inestable, no és un equilibri.

Trànsit en una xarxa

[modifica]
Exemple gràfic d'una xarxa. Els valors a les vores són el temps de viatge experimentat per un 'cotxe' viatjant per aquesta vora. és el nombre de cotxes que circulen a través d'aquesta vora.

Una aplicació d'equilibris de Nash es troba en la determinació del flux previst de trànsit en una xarxa. Considereu el gràfic de la dreta. Si assumim que hi ha x "cotxes" que viatgen des de la A a D, quina és la distribució esperada de trànsit a la xarxa?

Aquesta situació es pot modelar com un "joc" en què cada viatger té l'opció de 3 estratègies, en el qual cada estratègia és una ruta des de A a D (ja sigui , , o ). La "recompensa" de cada estratègia és el temps de recorregut de cada ruta. En el gràfic de la dreta, un automòbil que viatja a través d' triga un temps de , on és el nombre de cotxes que circulen a la vora . Per tant, els pagaments de qualsevol estratègia dependrà de les decisions dels altres jugadors, com és habitual. No obstant això, l'objectiu en aquest cas és reduir al mínim el temps de viatge, no maximitzar-ho. L'equilibri es produirà quan el temps en tots els camins sigui exactament el mateix. Quan això succeeix, cap conductor no té cap incentiu per canviar les rutes, ja que només pot augmentar al seu temps de viatge. Segons al gràfic de la dreta, si, per exemple, 100 cotxes viatgen de A a D, llavors l'equilibri es produeix quan 25 conductors viatgen a través d', de 50 van a través d', i 25 a través de ACD. Cada conductor té ara un temps total de viatge de 3,75.

Tingueu en compte que aquesta distribució no és, en realitat, socialment òptima. Si els 100 automòbils acorden que 50 viatjaran a través de i els altres 50 a través de , llavors el temps de viatge per a qualsevol cotxe únic realment seria 3,5 que és menor que 3,75. Aquest és també l'equilibri de Nash si la ruta entre B i C s'elimina, la qual cosa significa que l'addició d'una possible ruta addicional pot disminuir l'eficiència del sistema, un fenomen conegut com a Paradoxa de Braess.

Equilibris de Nash en una matriu de pagaments

[modifica]

Hi ha una manera numèrica fàcil d'identificar els equilibris de Nash en una matriu de pagaments. És especialment útil en jocs de dues persones, on els jugadors tenen més de dues estratègies. En aquest cas, l'anàlisi formal pot arribar a ser massa llarg. Aquesta regla no s'aplica al cas on poden ser interessants les estratègies mixtes (estocàstiques). La regla és la següent: si el primer nombre de guany, en la doble casella, és el màxim de la columna de la cel·la i si el segon nombre és el màxim de la fila de la cel·la - llavors la cel·la representa un equilibri de Nash.

Una matriu de pagaments - Equilibri de Nash en negreta
Opció A Opció B Opció C
Opció A 0, 0 25, 40 5, 10
Opció B 40, 25 0, 0 5, 15
Opció C 10, 5 15, 5 10, 10

Podem aplicar aquesta regla a una matriu de 3 × 3: Usant la regla, podem molt ràpidament (molt més ràpid que amb l'anàlisi formal) veure que les cel·les (B, A), (A, B), i (C, C) són equilibris de Nash. De fet, en el cas de la cel·la (B, A) 40 és el màxim de la primera columna i 25 és el màxim de la segona fila. (A, B) 25 és el màxim de la segona columna i 40 és el màxim de la primera fila. El mateix es pot dir de la cel·la (C, C). A les altres cel·les, ja sigui un o dos dels membres de la cel·la doble no són el màxim ni de les files ni de les columnes corresponents.

Dit això, la mecànica real per trobar cel·les d'equilibri és evident: trobar el màxim d'una columna i comprovar si el segon membre de la parella és el màxim de la fila. Si es compleixen aquestes condicions, la cel·la representa un equilibri de Nash. Reviseu totes les columnes d'aquesta manera per trobar totes les cel·les que són equilibris de Nash. Una matriu n × n pot tenir entre 0 i N × N equilibris de Nash d'estratègia pura.

Estabilitat

[modifica]

El concepte d'estabilitat, útil en l'anàlisi de molts tipus d'equilibris, també es pot aplicar als equilibris de Nash.

Un equilibri de Nash d'un joc d'estratègia barrejada és estable quan una petita variació (en concret, un canvi infinitesimal) en les probabilitats per un jugador porta a una situació en què es compleixen dues condicions:

  1. el jugador que no ha canviat no té una estratègia millor en les noves circumstàncies
  2. el jugador que ha canviat està ara jugant amb una estratègia estrictament pitjor.

Si aquests dos casos es compleixin simultàniament, a continuació, un jugador amb el petit canvi en la seva estratègia barretjada tornarà immediatament a l'equilibri de Nash. L'equilibri es diu que és estable. Si la primera condició no es compleix, l'equilibri és inestable. Si es dona una sola condició: llavors no és probable que hi hagi un nombre infinit d'estratègies òptimes per al jugador que ha canviat. John Nash va demostrar que aquesta última situació no podria produir-se en una varietat de jocs ben definits.

En el "joc de la conducció", que ja hem vist abans hi ha equilibris estables i inestables. Els equilibris amb estratègia barretjada amb probabilitats del 100% són estables. Si qualsevol dels jugadors canvia les seves probabilitats lleugerament, estarà alhora en desavantatge, i el seu oponent no tindrà cap raó per canviar la seva estratègia, al seu torn. L'equilibri (50%, 50%) és inestable. Si qualsevol dels jugadors canvia les seves probabilitats, llavors l'altre jugador té immediatament una millor estratègia, ja sigui en (0%, 100%) o (100%, 0%).

L'estabilitat és crucial en aplicacions pràctiques dels equilibris de Nash, ja que l'estratègia barrejada de cada jugador no és perfectament coneguda, i ha de ser inferida de la distribució estadística de les seves accions en el joc. En aquest cas els equilibris inestables són molt improbables a la pràctica, ja que qualsevol mínim canvi en les proporcions de cada estratègia que es pugui veure conduirà a un canvi en l'estratègia i la ruptura de l'equilibri.

L'equilibri de Nash defineix l'estabilitat només en termes de desviacions unilaterals. En els jocs cooperatius un concepte com aquest no és prou convincent. Un equilibri fort de Nash permet desviacions de cada coalició concebible.[7] Formalment, un equilibri fort de Nash és un equilibri de Nash en el qual cap coalició, prenent les accions dels seus complements com s'indica, pot de manera cooperativa desviar d'una manera que beneficiï a tots els seus membres.[8] No obstant això, el concepte fort de Nash es percep a vegades com a massa "fort" en què l'entorn permet la comunicació privada sense límits. De fet, l'equilibri fort de Nash ha de ser un òptim de Pareto. Com a resultat d'aquests requisits, l'equilibri fort de Nash és massa estrany per ser útil en moltes branques de la teoria de jocs. No obstant això, en els jocs com les eleccions amb molts més de jugadors que possibles resultats, pot ser més comú que un equilibri estable.

Un refinat equilibri de Nash es coneix com a equilibri a prova de coalicions de Nash (CPNE)[7] es produeix quan els jugadors no poden fer res millor, àdhuc si se'ls permet comunicar-se i fer un acord d'"autoaplicació" per desviar-se. Cada estratègia correlacionada recolzada en una dominància estricta iterada i en la frontera de Pareto és un CPNE.[9] A més, és possible per a un joc tenir un equilibri de Nash que sigui resistent contra coalicions de menys d'una mida especificada, k. El CPNE està relacionat amb la teoria del nucli.

Finalment, als anys vuitanta, construint amb gran profunditat en tals idees es van presentar com a concepte de solució els equilibris estables de Mertens. Els equilibris estables de Mertens satisfan tant la inducció cap endavant com la inducció cap enrere. En el context de la teoria de jocs els equilibris estables ara en general es refereixen a equilibris estables de Mertens.

Aparició

[modifica]

Si un joc té un únic equilibri de Nash i es juga entre els jugadors sota certes condicions, llavors el conjunt adoptarà l'estratègia de l'equilibri de Nash. Les condicions suficients per garantir que es juga segons l'equilibri de Nash són les següents:

  1. Tots els jugadors faran tot el possible per maximitzar el seu benefici esperat, com es descriu en el joc.
  2. Els jugadors no s'equivoquen en l'execució.
  3. Els jugadors tenen la intel·ligència suficient per deduir la solució.
  4. Els jugadors saben l'estratègia d'equilibri prevista de tots els altres jugadors.
  5. Els jugadors creuen que una desviació en la seva pròpia estratègia no provocarà desviacions dels altres jugadors.
  6. Hi ha un coneixement comú en el sentit que tots els jugadors satisfan aquestes condicions, incloent-hi aquesta. Per tant, no només cada jugador ha de saber que els altres jugadors satisfan les condicions, sinó també han de saber que tots ells saben que satisfan aquestes condicions, i coneixen que ells saben que ells les satisfan, i així successivament.

Quan les condicions no es compleixen

[modifica]

Exemples de problemes de teoria de jocs en què aquestes condicions no es compleixen:

  1. La primera condició no es compleix si el joc no descriu correctament les quantitats que un jugador vol maximitzar. En aquest cas no hi ha cap raó particular que dugui al jugador a adoptar una estratègia d'equilibri. Per exemple, el dilema del presoner no és un dilema si qualcun dels jugadors està feliç de ser empresonats indefinidament.
  2. Imperfecció intencional o accidental en l'execució. Per exemple, un ordinador capaç de joc lògic impecable davant d'un segon ordinador impecable produirà un equilibri. La introducció d'una imperfecció donarà lloc a una disrupció a través de la pèrdua del jugador que comet l'error, o per mitjà de la negació del criteri de coneixement comú que condueix a una possible victòria per al jugador. (Un exemple podria ser un jugador que de sobte posés el cotxe marxa enrere en el joc de la gallina, el que garanteix un escenari on ningú perd i ningú guanya).
  3. En molts casos, la tercera condició no es compleix perquè, tot i que l'equilibri ha d'existir, es desconeix a causa de la complexitat del joc, o, si se sap, potser no és conegut per tots els jugadors, com quan es juga el Tres en ratlla amb un nen petit que desesperadament vol guanyar (complint els altres criteris).
  4. El criteri de coneixement comú no es pot complir inclús si tots els jugadors, de fet, compleixen amb tots els altres criteris. Els jugadors que desconfien malament els uns dels altres poden adoptar racionalment contra-estratègies per al joc a l'espera de joc irracional dels seus oponents. Aquesta és una consideració important en el "joc de la gallina" o en una cursa armamentista, per exemple.

Quan es compleixen les condicions

[modifica]

A causa de les condicions limitades en què els equilibris de Nash poden observar de fet, rares vegades són tractats com una guia per al comportament del dia a dia, o s'observen en la pràctica en les negociacions humanes. No obstant això, els equilibris de Nash tenen poder explicatiu, com un concepte teòric en l'economia i la biologia evolutiva. El guany en l'economia és la utilitat (o, a vegades els diners), i en la biologia evolutiva la transmissió de gens, els dos són la línia de fons fonamental de la supervivència. Els investigadors que apliquen la teoria de jocs en aquests camps afirmen que les estratègies fallen a l'hora de maximitzar-los sigui quin sigui el motiu es competirà fora del mercat o del medi, al que s'atribueix la capacitat de provar totes les estratègies. Aquesta conclusió s'extreu de l'"estabilitat" de la teoria anterior.

Equilibri de Nash i les amenaces no creïbles

[modifica]
Il·lustracions àmplia i normal de manera que mostren la diferència entre el subjoc amb equilibri de Nash perfecte i altres equilibris de Nash. L'equilibri de color blau no és subjoc perfecte, perquè el segon jugador fa una amenaça no creïble a 2 (2) de ser cruel (U), La imatge utilitza K: amable (kindly), U: cruel (unkindly).

L'equilibri de Nash és un superconjunt de subjocs en un l'equilibri de Nash perfecte en. L'equilibri perfecte en subjocs juntament amb l'equilibri de Nash requereix que l'estratègia també sigui un equilibri de Nash en cada subjoc d'aquest joc. Això elimina totes les amenaces no creïbles, és a dir, estratègies que contenen jugades no racionals per tal de fer que el jugador contrari canviï d'estratègia.

La imatge de la dreta mostra un joc seqüencial simple que il·lustra el tema amb subjocs d'equilibris de Nash imperfectes. En aquest joc el jugador tria a l'esquerra (L) o dreta (R), que és seguit pel jugador 2 que és convidat a ser amable (K) o desagradable (U) amb el jugador 1, però, el segon jugador només pot guanyar sent desagradable si el jugador 1 va a l'esquerra. Si el jugador 1 va a la dreta el jugador racional 2 de fet seria amable amb ell en aquest subjoc. No obstant això, l'amenaça no creïble de ser desagradable a les 2 (2) segueix sent part de l'equilibri de Nash blau (L, (U, U)). Per tant, si es pot esperar un comportament racional per ambdues parts l'equilibri de Nash perfecte en subjocs pot ser un concepte de solució més significativa quan aquestes inconsistències dinàmiques sorgeixen.

Informàtica i equilibris de Nash

[modifica]

Si un jugador A té una estratègia dominant , llavors hi ha un equilibri de Nash en el qual A juga un . En el cas de dos jugadors A i B, hi ha un equilibri de Nash en el qual A juga un i B juga una millor resposta a . Si és una estratègia estrictament dominant, A juga en tots els equilibris de Nash. Si ambdós A i B tenen les estratègies estrictament dominants, hi ha un únic equilibri de Nash en què cada un juga la seva estratègia estrictament dominant.

En els jocs d'estratègia barrejada amb equilibris de Nash, la probabilitat d'un jugador de triar qualsevol estratègia particular pot ser calculada mitjançant l'assignació d'una variable a cada estratègia que representa una probabilitat fixa d'elecció d'aquesta estratègia. Perquè un jugador estigui disposat a canviar aleatòriament, el pagament esperat per a cada estratègia ha de ser el mateix. A més, la suma de les probabilitats per a cada estratègia d'un jugador en particular ha de ser 1. Això crea un sistema d'equacions a partir de la qual es poden deduir les probabilitats d'elecció de cada estratègia.[6]

Exemples

[modifica]
joc de les monedes
Jugador B juga H Jugador B juga T
Jugador A juga H −1, +1 +1, −1
Jugador A juga T +1, −1 −1, +1

En el joc de les monedes, el jugador A perd un punt davant B si A y B juguen la mateixa estratègia i guanya un punt de B si ambdós juguen diferents estratègies. Per calcular l'equilibri de Nash d'estratègia mixta, s'assigna a A la probabilitat p de jugar H i (1-p) de jugar T, i s'assigna a B la probabilitat q de jugar H i (1-q) de jugar T.

E[pagament per A jugant H] = (−1)q + (+1)(1−q) = 1−2q
E[pagament per A jugant T] = (+1)q + (−1)(1−q) = 2q−1
E[pagament per A jugant H] = E[pagament per A jugant T] ⇒ 1−2q = 2q−1 ⇒ q = 1/2
E[pagament per B jugant H] = (+1)p + (−1)(1−p) = 2p−1
E[pagament per B jugant T] = (−1)p + (+1)(1−p) = 1−2p
E[pagament per B jugant H] = E[pagament per B jugant T] ⇒ 2p−1 = 1−2p ⇒ p = 1/2

Així, una estratègia mixta d'equilibri de Nash en aquest joc és que cada jugador triï a l'atzar H o T, amb igual probabilitat.

Vegeu també

[modifica]

Referències

[modifica]
  1. Osborne, Martin J., and Ariel Rubinstein. A Course in Game Theory. Cambridge, MA: MIT, 1994. Print.
  2. Von Neumann, John; Morgenstern, Oskar; Rubinstein, Ariel. Theory of games and economic behavior (en anglès). Greenwood Publishing Group, 2007, p.xi. ISBN 0691130612. 
  3. Schelling, Thomas, The Strategy of Conflict, copyright 1960, 1980, Harvard University Press, ISBN 0674840313
  4. G. De Fraja, T. Oliveira, L. Zanchi (2010), 'Must Try Harder: Evaluating the Role of Effort in Educational Attainment'. "The Review of Economis and Statistics" 92:3. pp. 577-597
  5. P. Chiappori, S. Levitt, and T. Groseclose (2002), 'Testing Mixed-Strategy Equilibria When Players Are Heterogeneous: The Case of Penalty Kicks in Soccer'. American Economic Review 92, pp. 1138-51.
  6. 6,0 6,1 von Ahn, Luis. «Preliminaries of Game Theory». Arxivat de l'original el 2011-10-05. [Consulta: 7 novembre 2008].
  7. 7,0 7,1 B. D. Bernheim, B. Peleg, M. D. Whinston «Coalition-Proof Equilibria I. Concepts». Journal of Economic Theory, 42, 1, 1987, p. 1–12. DOI: 10.1016/0022-0531(87)90099-8.
  8. R. Aumann,. Acceptable points in general cooperative n-person games in "Contributions to the Theory of Games IV". Princeton Univ. Press, Princeton, N.J., 1959. 
  9. D. Moreno, J. Wooders «Coalition-Proof Equilibrium». Games and Economic Behavior, 17, 1, 1996, p. 80–112. DOI: 10.1006/game.1996.0095.

Bibliografia

[modifica]
Publicacions originals de Nash