Nash likevekt - Nash equilibrium

I spillteori er Nash-likevekten , oppkalt etter matematikeren John Forbes Nash Jr. , den vanligste måten å definere løsningen på et ikke-samarbeidende spill som involverer to eller flere spillere. I en Nash -likevekt antas det at hver spiller kjenner likevektsstrategiene til de andre spillerne, og ingen spiller har noe å vinne ved å endre sin egen strategi. Prinsippet om Nash -likevekt går tilbake til Cournots tid , som brukte det på konkurrerende firmaer som valgte utganger.

Hvis hver spiller har valgt en strategi - en handlingsplan som velger sine egne handlinger basert på det som har skjedd så langt i spillet - og ingen spiller kan øke sin egen forventede gevinst ved å endre strategien mens de andre spillerne beholder sine uendret, så vil gjeldende sett med strategivalg utgjør en Nash -likevekt.

Hvis to spillere Alice og Bob velger strategier A og B, (A, B) er en Nash -likevekt hvis Alice ikke har noen annen strategi tilgjengelig som gjør det bedre enn A på å maksimere utbetalingen som svar på at Bob velger B, og Bob har ingen annen strategi tilgjengelig som gjør det bedre enn B for å maksimere utbetalingen som svar på at Alice valgte A. I et spill der Carol og Dan også er spillere, er (A, B, C, D) en Nash -likevekt hvis A er Alices beste svar på ( B, C, D), B er Bobs beste svar på (A, C, D), og så videre.

Nash viste at det er en Nash -likevekt for hvert endelig spill: se artikkelen om strategi videre .

applikasjoner

Spillteoretikere bruker Nash -likevekt til å analysere utfallet av det strategiske samspillet mellom flere beslutningstakere . I et strategisk samspill avhenger utfallet for hver beslutningstaker av beslutninger fra de andre så vel som deres egne. Den enkle innsikten som ligger til grunn for Nashs idé er at man ikke kan forutsi valgene til flere beslutningstakere hvis man analyserer disse beslutningene isolert. I stedet må man spørre hva hver spiller ville gjort med tanke på hva hun/han forventer at de andre skal gjøre. Nash -likevekt krever at valgene deres er konsistente: ingen spiller ønsker å angre beslutningen gitt hva de andre bestemmer.

Konseptet har blitt brukt til å analysere fiendtlige situasjoner som kriger og våpenkappløp (se fangenes dilemma ), og også hvordan konflikt kan dempes ved gjentatt interaksjon (se tit-for-tat ). Den har også blitt brukt til å studere i hvilken grad mennesker med forskjellige preferanser kan samarbeide (se kjønnskamp ), og om de vil ta risiko for å oppnå et samarbeidende utfall (se hjortjakt ). Den har blitt brukt til å studere vedtakelsen av tekniske standarder , og også forekomsten av bankkjøringer og valutakriser (se koordineringsspill ). Andre bruksområder inkluderer trafikkflyt (se Wardrops prinsipp ), hvordan man organiserer auksjoner (se auksjonsteori ), resultatet av innsatsen fra flere parter i utdanningsprosessen, forskriftslovgivning som miljøforskrifter (se allmenningens tragedie ), naturressurser ledelse, analysere strategier innen markedsføring, til og med straffespark i fotball (se matchende øre ), energisystemer, transportsystemer, evakueringsproblemer og trådløs kommunikasjon.

Historie

Nash likevekt er oppkalt etter amerikanske matematikeren John Forbes Nash jr . Den samme ideen ble brukt i en bestemt søknad i 1838 av Antoine Augustin Cournot i hans teori om oligopol . I Cournots teori velger hvert av flere firmaer hvor mye produksjon de skal produsere for å maksimere profitten. Den beste produksjonen for ett firma avhenger av utgangene til det andre. En Cournot-likevekt oppstår når hvert firmas produksjon maksimerer fortjenesten gitt produksjonen fra de andre selskapene, noe som er en ren Nash-likevekt. Cournot introduserte også begrepet beste responsdynamikk i sin analyse av stabiliteten i likevekt. Cournot brukte imidlertid ikke ideen i andre applikasjoner, eller definerte den generelt.

Det moderne konseptet om Nash -likevekt er i stedet definert i form av blandede strategier , hvor spillerne velger en sannsynlighetsfordeling fremfor mulige rene strategier (som kan sette 100% av sannsynligheten på en ren strategi; slike rene strategier er en delmengde av blandede strategier). Konseptet med en blandet strategi-likevekt ble introdusert av John von Neumann og Oskar Morgenstern i boken The Theory of Games and Economic Behavior fra 1944 , men analysen deres var begrenset til det spesielle tilfellet av nullsumsspill . De viste at en blandet strategi Nash-likevekt vil eksistere for ethvert nullsumspill med et begrenset sett med handlinger. Bidraget til Nash i hans artikkel "Non-Cooperative Games" fra 1951 var å definere en blandet strategi Nash-likevekt for ethvert spill med et begrenset sett med handlinger og bevise at minst én (blandet strategi) Nash-likevekt må eksistere i et slikt spill. Nøkkelen til Nashs evne til å bevise eksistens langt mer generelt enn von Neumann lå i hans definisjon av likevekt. I følge Nash, "er et likevektspunkt en n-tupel slik at hver spillers blandede strategi maksimerer utbetalingen hvis de andres strategier holdes faste. Dermed er hver spillers strategi optimal mot de andres." Å sette problemet i dette rammeverket tillot Nash å bruke Kakutani-punktpunktssetningen i papiret fra 1950 for å bevise eksistensen av likevekt. Hans papir fra 1951 brukte den enklere Brouwer-punktpunktssetningen til samme formål.

Spillteoretikere har oppdaget at Nash -likevekt under noen omstendigheter gir ugyldige spådommer eller ikke klarer å lage en unik spådom. De har foreslått mange løsningskonsepter ('forbedringer' av Nash -likevekt) designet for å utelukke usannsynlig Nash -likevekt. Et spesielt viktig spørsmål er at noen Nash -likevekt kan være basert på trusler som ikke er ' troverdige '. I 1965 foreslo Reinhard Selten delspill perfekt likevekt som en forfining som eliminerer likevekt som er avhengig av ikke-troverdige trusler . Andre utvidelser av Nash likevektskonseptet har tatt for seg hva som skjer hvis et spill gjentas , eller hva som skjer hvis et spill spilles i fravær av fullstendig informasjon . Imidlertid deler påfølgende forbedringer og utvidelser av Nash -likevekten den viktigste innsikten som Nashs konsept hviler på: likevekten er et sett med strategier slik at hver spillers strategi er optimal gitt de andres valg.

Definisjoner

Nash likevekt

En strategiprofil er et sett med strategier, en for hver spiller. Uformelt er en strategiprofil en Nash -likevekt hvis ingen spiller kan gjøre det bedre ved ensidig å endre strategien. For å se hva dette betyr, tenk deg at hver spiller blir fortalt strategiene til de andre. Anta at hver spiller spør seg selv: "Å kjenne strategiene til de andre spillerne, og behandle strategiene til de andre spillerne som steinlagt, kan jeg tjene på å endre strategien min?"

Hvis en spiller kunne svare "Ja", så er det settet med strategier ikke en Nash -likevekt. Men hvis hver spiller foretrekker å ikke bytte (eller er likegyldig mellom å bytte og ikke), så er strategiprofilen en Nash -likevekt. Dermed er hver strategi i en Nash -likevekt det beste svaret på de andre spillernes strategier i den likevekten.

Formelt, la være settet med alle mulige strategier for spiller , hvor . La oss være en strategiprofil, et sett bestående av en strategi for hver spiller, der den angir strategiene til alle spillerne unntatt . La oss være spillerens utbetaling som en funksjon av strategiene. Strategiprofilen er en Nash -likevekt hvis ${\ displaystyle S_ {i}}$${\ displaystyle i}$${\ displaystyle i = 1, \ ldots, N}$${\ displaystyle s^{*} = (s_ {i}^{*}, s _ {-i}^{*})}$${\ displaystyle s _ {-i}^{*}}$${\ displaystyle N-1}$${\ displaystyle i}$${\ displaystyle u_ {i} (s_ {i}, s _ {-i}^{*})}$${\ displaystyle s^{*}}$

${\ displaystyle u_ {i} (s_ {i}^{*}, s _ {-i}^{*}) \ geq u_ {i} (s_ {i}, s _ {-i}^{*}) \ ; \; {\ rm {for \; alle}} \; \; s_ {i} \ i S_ {i}}$

Et spill kan ha mer enn én Nash -likevekt. Selv om likevekten er unik, kan den være svak : en spiller kan være likegyldig blant flere strategier gitt de andre spillernes valg. Det er unikt og kalles en streng Nash -likevekt hvis ulikheten er streng, så en strategi er den unike beste responsen:

${\ displaystyle u_ {i} (s_ {i}^{*}, s _ {-i}^{*})> u_ {i} (s_ {i}, s _ {-i}^{*}) \; \; {\ rm {for \; alle}} \; \; s_ {i} \ i S_ {i}, s_ {i} \ neq s_ {i}^{*}}$

Vær oppmerksom på at strategisettet kan være forskjellig for forskjellige spillere, og elementene kan være en rekke matematiske objekter. Enklest kan en spiller velge mellom to strategier, f.eks Eller strategien sett kan være et begrenset sett av betingede strategier å svare på andre spillere, f.eks Eller kan det være en uendelig sett, et kontinuum eller grenseløs, for eksempel slik at en ikke-negativt reelt tall. Nashs eksistensbeviser antar et begrenset strategisett, men begrepet Nash -likevekt krever det ikke. ${\ displaystyle S_ {i}}$${\ displaystyle S_ {i} = \ {{\ text {Yes}}, {\ text {No}} \}.}$${\ displaystyle S_ {i} = \ {{\ text {Yes}} | p = {\ text {Low}}, {\ text {No}} | p = {\ text {High}} \}.}$${\ displaystyle S_ {i} = \ {{\ text {Price}} \}}$${\ displaystyle {\ text {Price}}}$

Nash-likevekten kan noen ganger virke ikke-rasjonell i et tredjepersonsperspektiv. Dette er fordi en Nash -likevekt ikke nødvendigvis er Pareto optimal .

Nash-likevekt kan også ha ikke-rasjonelle konsekvenser i sekvensielle spill fordi spillere kan "true" hverandre med trusler de faktisk ikke ville utføre. For slike spill kan underspillets perfekte Nash -likevekt være mer meningsfylt som et analyseverktøy.

Strenge/svake likevekt

Anta at i Nash -likevekten spør hver spiller seg selv: "Å kjenne strategiene til de andre spillerne, og behandle strategiene til de andre spillerne som satt i stein, ville jeg lide et tap ved å endre strategien min?"

Hvis hver spillers svar er "Ja", er likevekten klassifisert som en streng Nash -likevekt .

Hvis det i stedet for en spiller er eksakt likhet mellom strategien i Nash -likevekt og en annen strategi som gir nøyaktig samme utbetaling (dvs. denne spilleren er likegyldig mellom å bytte og ikke), så er likevekten klassifisert som en svak Nash -likevekt .

Et spill kan ha en ren-strategi eller en blandet-strategi Nash likevekt. (I sistnevnte velges en ren strategi stokastisk med en fast sannsynlighet ).

Nashs eksistenssetning

Nash beviste at hvis blandede strategier (hvor en spiller velger sannsynligheter for å bruke forskjellige rene strategier) er tillatt, så har hvert spill med et begrenset antall spillere hvor hver spiller kan velge mellom mange mange rene strategier minst én Nash -likevekt, noe som kan være en ren strategi for hver spiller eller kan være en sannsynlighetsfordeling over strategier for hver spiller.

Nash-likevekt trenger ikke eksistere hvis settet med valg er uendelig og ikke-kompakt. Et eksempel er et spill hvor to spillere samtidig navngir et tall og spilleren som navngir det større tallet vinner. Et annet eksempel er hvor hver av to spillere velger et reelt tall på strengt mindre enn 5 og vinneren er den som har det største tallet; ikke noe største tall som er strengt mindre enn 5 eksisterer (hvis tallet kunne være lik 5, ville Nash -likevekten få både spillere til å velge 5 og knytte spillet). Imidlertid eksisterer det en Nash -likevekt hvis settet med valg er kompakt med hver spillers gevinst kontinuerlig i strategiene til alle spillerne.

Eksempler

Koordinasjonsspill

Den samordning spillet er et klassisk to-player, to- strategispill, som vist i eksempelet payoff matrise til høyre. Det er to likeverdige likevekter, (A, A) med gevinst 4 for hver spiller og (B, B) med gevinst 2 for hver. Kombinasjonen (B, B) er en Nash -likevekt fordi hvis en av spillerne ensidig endrer sin strategi fra B til A, vil utbetalingen falle fra 2 til 1.

Et kjent eksempel på et koordineringsspill er hjortejakten . To spillere kan velge å jakte på en hjort eller en kanin, mens hjorten gir mer kjøtt (4 bruksenheter, 2 for hver spiller) enn kaninen (1 bruksenhet). Advarselen er at hjorten må jaktes i samarbeid, så hvis den ene spilleren prøver å jakte på hjorten, mens den andre jakter kaninen, vil hjortejegeren totalt mislykkes, for en gevinst på 0, mens kaninjegeren vil lykkes, for en gevinst på 1. Spillet har to likevekter, (hjort, hjort) og (kanin, kanin), fordi en spillers optimale strategi avhenger av hans forventning til hva den andre spilleren vil gjøre. Hvis den ene jegeren stoler på at den andre vil jakte hjorten, bør han jakte på hjorten; men hvis han tror at den andre vil jakte kaninen, vil han også jakte på kaninen. Dette spillet brukes som en analogi for sosialt samarbeid, siden mye av fordelen folk får i samfunnet er avhengig av at mennesker samarbeider og implisitt stoler på hverandre for å opptre på en måte som tilsvarer samarbeid.

Å kjøre på en vei mot en møtende bil, og måtte velge enten å svinge til venstre eller å svinge til høyre på veien, er også et koordinasjonsspill. For eksempel, med utbetalinger 10 som betyr ingen krasj og 0 som betyr et krasj, kan koordinasjonsspillet defineres med følgende utbetalingsmatrise:

I dette tilfellet er det to Nash-likevekt med ren strategi, når begge velger å enten kjøre til venstre eller til høyre. Hvis vi innrømmer blandede strategier (der en ren strategi velges tilfeldig, med forbehold om en viss sannsynlighet), så er det tre Nash-likevekter for samme sak: to vi har sett fra rent-strategiformen, der sannsynlighetene er (0 %, 100%) for spiller en, (0%, 100%) for spiller to; og (100%, 0%) for spiller én, henholdsvis (100%, 0%) for spiller to. Vi legger til en annen der sannsynligheten for hver spiller er (50%, 50%).

Nettverkstrafikk

Eksempel på nettverksgraf. Verdier på kantene er reisetiden som en 'bil' opplever langs den kanten. x er antall biler som kjører via den kanten.

En anvendelse av Nash -likevekt er å bestemme forventet trafikkflyt i et nettverk. Se på grafen til høyre. Hvis vi antar at det er x "biler" som reiser fra A til D, hva er den forventede fordelingen av trafikk i nettet?

Denne situasjonen kan modelleres som et "spill" hvor hver reisende har et valg mellom 3 strategier, hvor hver strategi er en rute fra A til D (en av ABD , ABCD eller ACD ). "Utbetalingen" av hver strategi er reisetiden for hver rute. I grafen til høyre opplever en bil som kjører via ABD reisetid på (1+ x /100) +2 , hvor x er antall biler som kjører på kant AB . Dermed avhenger utbetalinger for en gitt strategi av valgene til de andre spillerne, som vanlig. Imidlertid er målet i dette tilfellet å minimere reisetiden, ikke maksimere den. Likevekt vil oppstå når tiden på alle baner er nøyaktig den samme. Når det skjer, har ingen enkelt sjåfør noe insentiv til å bytte rute, siden det bare kan øke reisetiden. For grafen til høyre, hvis for eksempel 100 biler kjører fra A til D, vil likevekt oppstå når 25 sjåfører kjører via ABD , 50 via ABCD og 25 via ACD . Hver sjåfør har nå en total reisetid på 3,75 (for å se dette, vær oppmerksom på at totalt 75 biler tar AB -kanten, og på samme måte tar 75 biler CD -kanten).

Legg merke til at denne fordelingen faktisk ikke er sosialt optimal. Hvis de 100 bilene var enige om at 50 reiser via ABD og de andre 50 gjennom ACD , vil reisetiden for en enkelt bil faktisk være 3,5, noe som er mindre enn 3,75. Dette er også Nash -likevekten hvis banen mellom B og C fjernes, noe som betyr at å legge til en annen mulig rute kan redusere systemets effektivitet, et fenomen kjent som Braess paradoks .

Konkurransespill

Dette kan illustreres av et spill med to spillere der begge spillerne samtidig velger et helt tall fra 0 til 3 og de begge vinner det minste av de to tallene i poeng. I tillegg, hvis den ene spilleren velger et større tall enn den andre, må de gi fra seg to poeng til den andre.

Dette spillet har en unik Nash-likevekt i ren strategi: begge spillerne velger 0 (markert med rødt). Enhver annen strategi kan forbedres ved at en spiller bytter nummeret til ett mindre enn det til den andre spilleren. I tabellen ved siden av, hvis spillet begynner på den grønne ruten, er det i spiller 1 sin interesse å flytte til den lilla firkanten, og det er i spiller 2 sin interesse å flytte til den blå ruten. Selv om det ikke ville passe til definisjonen av et konkurransespill, hvis spillet er modifisert slik at de to spillerne vinner det navngitte beløpet hvis de begge velger samme nummer, og ellers vinner ingenting, så er det 4 Nash -likevekt: (0,0 ), (1,1), (2,2) og (3,3).

Nash likevekt i en utbetalingsmatrise

Det er en enkel numerisk måte å identifisere Nash -likevekt på en utbetalingsmatrise. Det er spesielt nyttig i to-personers spill der spillere har mer enn to strategier. I dette tilfellet kan formell analyse bli for lang. Denne regelen gjelder ikke for tilfeller der blandede (stokastiske) strategier er av interesse. Regelen går som følger: hvis det første utbetalingsnummeret, i utbetalingsparet i cellen, er maksimumet i kolonnen i cellen, og hvis det andre tallet er maksimumet i raden i cellen - så representerer cellen en Nash likevekt.

Vi kan bruke denne regelen på en 3 × 3 matrise:

Ved å bruke regelen kan vi veldig raskt (mye raskere enn ved formell analyse) se at Nash -likevektscellene er (B, A), (A, B) og (C, C). Faktisk, for celle (B, A) er 40 maksimumet for den første kolonnen og 25 er maksimumet for den andre raden. For (A, B) er 25 maksimum for den andre kolonnen og 40 er maksimum for den første raden. Samme for celle (C, C). For andre celler er ikke ett eller begge duplettmedlemmene maksimumet for de tilsvarende radene og kolonnene.

Når det er sagt, er den faktiske mekanikken for å finne likevektsceller åpenbar: finn maksimum for en kolonne og sjekk om det andre medlemmet i paret er maksimum på raden. Hvis disse betingelsene er oppfylt, representerer cellen en Nash -likevekt. Kontroller alle kolonnene på denne måten for å finne alle NE -celler. En N × N-matrise kan ha mellom 0 og N × N ren-strategi Nash-likevekt.

Stabilitet

Konseptet om stabilitet , nyttig i analysen av mange slags likevekt, kan også brukes på Nash -likevekt.

En Nash-likevekt for et blandet strategispill er stabil hvis en liten endring (spesielt en uendelig endring) i sannsynligheter for en spiller fører til en situasjon der to forhold holder:

1. spilleren som ikke endret seg har ingen bedre strategi i den nye situasjonen
2. spilleren som endret, spiller nå med en strengt dårligere strategi.

Hvis disse sakene begge blir oppfylt, vil en spiller med den lille endringen i sin blandede strategi umiddelbart gå tilbake til Nash -likevekten. Likevekten sies å være stabil. Hvis betingelse man ikke holder, er likevekten ustabil. Hvis bare betingelse man holder, er det sannsynligvis et uendelig antall optimale strategier for spilleren som endret seg.

I eksempelet "kjørespill" ovenfor er det både stabil og ustabil likevekt. Likevekten som involverer blandede strategier med 100% sannsynlighet er stabil. Hvis en av spillerne endrer sannsynligheten litt, vil de ha begge en ulempe, og motstanderen har ingen grunn til å endre strategien etter tur. Likevekten (50%, 50%) er ustabil. Hvis en av spillerne endrer sannsynligheten (som verken vil gavne eller skade forventningen til spilleren som gjorde endringen, hvis den andre spillerens blandede strategi fortsatt er (50%, 50%)), har den andre spilleren umiddelbart en bedre strategi på enten (0%, 100%) eller (100%, 0%).

Stabilitet er avgjørende i praktiske anvendelser av Nash -likevekt, siden den blandede strategien til hver spiller ikke er helt kjent, men må utledes av statistisk fordeling av handlingene deres i spillet. I dette tilfellet er det lite sannsynlig at det oppstår ustabil likevekt i praksis, siden enhver liten endring i proporsjonene til hver strategi vi ser vil føre til en endring i strategi og nedbrytning av likevekten.

Nash -likevekten definerer stabilitet bare når det gjelder ensidige avvik. I kooperative spill er et slikt konsept ikke overbevisende nok. Sterk Nash -likevekt tillater avvik fra alle tenkelige koalisjoner. Formelt sett er en sterk Nash -likevekt en Nash -likevekt der ingen koalisjoner, som tar handlingene fra komplementene som gitt, kan samarbeide avvikende på en måte som kommer alle medlemmene til gode. Imidlertid oppfattes det sterke Nash -konseptet noen ganger som for "sterkt" ved at miljøet gir mulighet for ubegrenset privat kommunikasjon. Faktisk må sterk Nash -likevekt være Pareto -effektiv . Som et resultat av disse kravene er sterk Nash for sjelden til å være nyttig i mange grener av spillteori. I spill som valg med mange flere spillere enn mulige utfall, kan det imidlertid være mer vanlig enn en stabil likevekt.

En raffinert Nash-likevekt kjent som koalisjonssikker Nash-likevekt (CPNE) oppstår når spillere ikke kan gjøre det bedre selv om de får lov til å kommunisere og inngå en "selvhåndhevende" avtale om å avvike. Hver korrelert strategi støttet av gjentatt streng dominans og på Pareto -grensen er en CPNE. Videre er det mulig for et spill å ha en Nash -likevekt som er motstandsdyktig mot koalisjoner mindre enn en spesifisert størrelse, k. CPNE er relatert til kjerneteorien .

Til slutt på åttitallet ble det bygd med stor dybde på slike ideer Mertens-stabil likevekt ble introdusert som et løsningskonsept . Mertens stabile likevektstilfredsstille både forover induksjon og bakover induksjon . I en spillteori sammenheng stabil likevekt nå vanligvis refererer til Mertens stabile likevekter.

Hendelse

Hvis et spill har en unik Nash -likevekt og spilles blant spillere under visse forhold, vil NE -strategisettet bli vedtatt. Tilstrekkelige forhold for å garantere at Nash -likevekten spilles er:

1. Spillerne vil alle gjøre sitt ytterste for å maksimere den forventede utbetalingen som beskrevet av spillet.
2. Spillerne er feilfrie i utførelsen.
3. Spillerne har tilstrekkelig intelligens til å utlede løsningen.
4. Spillerne kjenner den planlagte likevektsstrategien til alle de andre spillerne.
5. Spillerne tror at et avvik i deres egen strategi ikke vil forårsake avvik fra andre spillere.
6. Det er allment kjent at alle spillere oppfyller disse betingelsene, inkludert denne. Så ikke bare må hver spiller vite at de andre spillerne oppfyller betingelsene, men de må også vite at de alle vet at de møter dem, og vet at de vet at de vet at de møter dem, og så videre.

Der vilkårene ikke er oppfylt

Eksempler på spillteoriproblemer der disse betingelsene ikke er oppfylt:

1. Den første betingelsen er ikke oppfylt hvis spillet ikke korrekt beskriver mengdene en spiller ønsker å maksimere. I dette tilfellet er det ingen spesiell grunn for at spilleren skal vedta en likevektsstrategi. For eksempel er fangenes dilemma ikke et dilemma hvis en av spillerne er glad for å bli fengslet på ubestemt tid.
2. Bevisst eller utilsiktet ufullkommenhet i utførelsen. For eksempel vil en datamaskin som er i stand til feilfri logisk lek som vender mot en annen feilfri datamaskin, resultere i likevekt. Innføring av ufullkommenhet vil føre til dens avbrudd enten gjennom tap til spilleren som gjør feil, eller gjennom negasjonen av felles kunnskap kriterium fører til mulige seier for spilleren. (Et eksempel kan være at en spiller plutselig setter bilen i revers i kyllingspillet , og sikrer et no-loss no-win-scenario).
3. I mange tilfeller er den tredje betingelsen ikke oppfylt fordi, selv om likevekten må eksistere, er den ukjent på grunn av kompleksiteten i spillet, for eksempel i kinesisk sjakk . Eller, hvis det er kjent, er det kanskje ikke kjent for alle spillere, som når man spiller tic-tac-toe med et lite barn som desperat ønsker å vinne (oppfyller de andre kriteriene).
4. Kriteriet om felles kunnskap er kanskje ikke oppfylt selv om alle spillerne faktisk oppfyller alle de andre kriteriene. Spillere som feilaktig mistro hverandres rasjonalitet, kan vedta motstrategier for forventet irrasjonelt spill på motstandernes vegne. Dette er et stort hensyn i for eksempel " kylling " eller et våpenkappløp .

Der vilkårene er oppfylt

I sin doktorgrad avhandling, foreslo John Nash to tolkninger av hans likevektskonsept, med det formål å vise hvordan likevektspunkter kan kobles til observerbare fenomen.

(...) En tolkning er rasjonalistisk: hvis vi antar at spillerne er rasjonelle, kjenner hele strukturen i spillet, spilles spillet bare en gang, og det er bare en Nash -likevekt, så vil spillerne spille i henhold til den likevekten .

Denne ideen ble formalisert av Aumann, R. og A. Brandenburger, 1995, Epistemic Conditions for Nash Equilibrium , Econometrica, 63, 1161-1180 som tolket hver spillers blandede strategi som en formodning om oppførselen til andre spillere og har vist at hvis spillet og rasjonaliteten til spillerne er gjensidig kjent, og disse formodningene er kjent, da må formodningene være en Nash -likevekt (en vanlig forutgående antagelse er nødvendig for dette resultatet generelt, men ikke for to spillere. I dette tilfellet, formodningene trenger bare å være gjensidig kjent).

En annen tolkning, som Nash refererte til i masseaksjonstolkningen, er mindre krevende for spillerne:

[i] t er unødvendig å anta at deltakerne har full kunnskap om den totale strukturen i spillet, eller evnen og tilbøyeligheten til å gå gjennom komplekse resonnementsprosesser. Det som antas er at det er en populasjon av deltakere for hver posisjon i spillet, som vil bli spilt gjennom tid av deltakere trukket tilfeldig fra de forskjellige populasjonene. Hvis det er en stabil gjennomsnittsfrekvens som hver ren strategi brukes av gjennomsnittlig medlem av den aktuelle befolkningen, utgjør denne stabile gjennomsnittsfrekvensen en blandet strategi Nash -likevekt.

For et formelt resultat på denne måten, se Kuhn, H. og et al., 1996, "The Work of John Nash in Game Theory," Journal of Economic Theory , 69, 153–185.

På grunn av de begrensede forholdene der NE faktisk kan observeres, blir de sjelden behandlet som en guide til daglig oppførsel, eller observert i praksis i menneskelige forhandlinger. Som et teoretisk konsept i økonomi og evolusjonsbiologi har imidlertid NE en forklaringskraft. Utbetalingen i økonomi er nytte (eller noen ganger penger), og i evolusjonær biologi er gentransmisjon; begge er den grunnleggende bunnlinjen for overlevelse. Forskere som bruker spillteori på disse feltene hevder at strategier som ikke klarer å maksimere disse av en eller annen grunn vil bli konkurrert ut av markedet eller miljøet, som tilskrives evnen til å teste alle strategier. Denne konklusjonen er trukket fra " stabilitet " -teorien ovenfor. I disse situasjonene har antagelsen om at den observerte strategien faktisk er et NE ofte blitt bekreftet av forskning.

NE og ikke-troverdige trusler

Omfattende og normale formillustrasjoner som viser forskjellen mellom SPNE og andre NE. Den blå likevekten er ikke perfekt, fordi spiller to utgjør en ikke-troverdig trussel ved 2 (2) for å være uvennlig (U).

Nash -likevekten er et supersett av underspillets perfekte Nash -likevekt. Den perfekte likevekten i underspillet i tillegg til Nash -likevekten krever at strategien også er en Nash -likevekt i alle underspill i det spillet. Dette eliminerer alle ikke-troverdige trusler , det vil si strategier som inneholder ikke-rasjonelle trekk for å få motspilleren til å endre sin strategi.

Bildet til høyre viser et enkelt sekvensielt spill som illustrerer problemet med underspillet ufullkomne Nash -likevekt. I denne spilleren velger man venstre (L) eller høyre (R), som etterfølges av at spiller to blir oppfordret til å være snill (K) eller uvennlig (U) mot spiller en, men spiller to har bare å tjene på å være uvennlig hvis spiller en går til venstre. Hvis spiller en går rett, ville den rasjonelle spilleren to de facto være snill mot henne/ham i det underspillet. Imidlertid er den ikke-troverdige trusselen om å være uvennlig ved 2 (2) fortsatt en del av den blå (L, (U, U)) Nash-likevekten. Derfor, hvis rasjonell oppførsel kan forventes av begge parter, kan subgame -perfekt Nash -likevekt være et mer meningsfylt løsningskonsept når slike dynamiske inkonsekvenser oppstår.

Bevis på eksistens

Bevis ved bruk av Kakutani fastpunktssetning

Nashs originale bevis (i avhandlingen) brukte Brouwers fastpunktssetning (f.eks. Se en variant nedenfor). Vi gir et enklere bevis via Kakutani-punktpunktssetningen , etter Nashs papir fra 1950 (han gir David Gale observasjonen at en slik forenkling er mulig).

For å bevise eksistensen av en Nash -likevekt, la være den beste responsen til spiller i på strategiene til alle andre spillere. ${\ displaystyle r_ {i} (\ sigma _ {-i})}$

${\ displaystyle r_ {i} (\ sigma _ {-i}) = \ mathop {\ underset {\ sigma _ {i}} {\ operatorname {arg \, max}}} u_ {i} (\ sigma _ { i}, \ sigma _ {-i})}$

Her, hvor , er en blandet strategiprofil i settet med alle blandede strategier og er utbetalingsfunksjonen for spiller i. Definer en verdi som er satt til verdi slik at . Eksistensen av en Nash -likevekt tilsvarer å ha et fast punkt. ${\ displaystyle \ sigma \ in \ Sigma}$${\ displaystyle \ Sigma = \ Sigma _ {i} \ times \ Sigma _ {-i}}$${\ displaystyle u_ {i}}$ ${\ displaystyle r \ colon \ Sigma \ rightarrow 2^{\ Sigma}}$${\ displaystyle r = r_ {i} (\ sigma _ {-i}) \ ganger r _ {-i} (\ sigma _ {i})}}$${\ displaystyle r}$

Kakutanis fastpunktssetning garanterer eksistensen av et fast punkt hvis følgende fire betingelser er oppfylt.

1. ${\ displaystyle \ Sigma}$ er kompakt, konveks og ikke -fristende.
2. ${\ displaystyle r (\ sigma)}$ er nonempty.
3. ${\ displaystyle r (\ sigma)}$er øvre hemikontinuerlig
4. ${\ displaystyle r (\ sigma)}$ er konveks.

Tilstand 1. er tilfredsstilt fra det faktum at den er enkel og dermed kompakt. Konveksitet følger av spillernes evne til å blande strategier. er nonempty så lenge spillerne har strategier. ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$

Betingelse 2. og 3. er oppfylt ved hjelp av Berges maksimale teorem . Fordi er kontinuerlig og kompakt, er ikke-tom og øvre hemikontinuerlig . ${\ displaystyle u_ {i}}$${\ displaystyle r (\ sigma _ {i})}$

Betingelse 4. er tilfredsstilt som et resultat av blandede strategier. Anta , da . dvs. hvis to strategier maksimerer utbetalingen, vil en blanding mellom de to strategiene gi den samme utbetalingen. ${\ displaystyle \ sigma _ {i}, \ sigma '_ {i} \ in r (\ sigma _ {-i})}}$${\ displaystyle \ lambda \ sigma _ {i}+(1- \ lambda) \ sigma '_ {i} \ in r (\ sigma _ {-i})}}$

Derfor eksisterer det et fast punkt i og en Nash -likevekt. ${\ displaystyle r}$

Da Nash sa dette til John von Neumann i 1949, avviste von Neumann det berømt med ordene: "Det er trivielt, du vet. Det er bare et fastpunktssetning ." (Se Nasar, 1998, s. 94.)

Alternativt bevis ved å bruke Brouwer-punktpunktssetningen

Vi har et spill hvor antall spillere er og settet for spillerne. Alle handlingssettene er endelige. La oss angi settet med blandede strategier for spillerne. Endeligheten av s sikrer kompaktiteten til . ${\ displaystyle G = (N, A, u)}$${\ displaystyle N}$${\ displaystyle A = A_ {1} \ times \ cdots \ times A_ {N}}$${\ displaystyle A_ {i}}$${\ displaystyle \ Delta = \ Delta _ {1} \ times \ cdots \ times \ Delta _ {N}}$${\ displaystyle A_ {i}}$${\ displaystyle \ Delta}$

Vi kan nå definere forsterkningsfunksjonene. For en blandet strategi lar vi gevinsten for spiller i aksjon være ${\ displaystyle \ sigma \ in \ Delta}$${\ displaystyle i}$${\ displaystyle a \ i A_ {i}}$

${\ displaystyle {\ text {Gain}} _ {i} (\ sigma, a) = \ max \ {0, u_ {i} (a, \ sigma _ {-i})-u_ {i} (\ sigma _ {i}, \ sigma _ {-i}) \}.}$

Gevinstfunksjonen representerer fordelen en spiller får ved ensidig å endre strategien. Vi definerer nå hvor ${\ displaystyle g = (g_ {1}, \ dotsc, g_ {N})}$

${\ displaystyle g_ {i} (\ sigma) (a) = \ sigma _ {i} (a)+{\ text {Gain}} _ {i} (\ sigma, a)}$

for . Vi ser det ${\ displaystyle \ sigma \ in \ Delta, a \ i A_ {i}}$

${\ displaystyle \ sum _ {a \ i A_ {i}} g_ {i} (\ sigma) (a) = \ sum _ {a \ i A_ {i}} \ sigma _ {i} (a)+{ \ text {Gain}} _ {i} (\ sigma, a) = 1+\ sum _ {a \ i A_ {i}} {\ text {Gain}} _ {i} (\ sigma, a)> 0 .}$

Deretter definerer vi:

${\ displaystyle {\ begin {cases} f = (f_ {1}, \ cdots, f_ {N}): \ Delta \ to \ Delta \\ f_ {i} (\ sigma) (a) = {\ frac { g_ {i} (\ sigma) (a)} {\ sum _ {b \ i A_ {i}} g_ {i} (\ sigma) (b)}} og a \ i A_ {i} \ ende {saker} }}$

Det er lett å se at hver av dem er en gyldig blandet strategi . Det er også enkelt å kontrollere at hver av dem er en kontinuerlig funksjon av , og derfor er en kontinuerlig funksjon. Som tverrproduktet av et begrenset antall kompakte konvekse sett, er det også kompakt og konveks. Å bruke Brouwer -fastpunktsetningen til, og vi konkluderer med at det har et fast punkt i , kall det . Vi hevder det er en Nash -likevekt i . For dette formålet er det nok å vise det ${\ displaystyle f_ {i}}$${\ displaystyle \ Delta _ {i}}$${\ displaystyle f_ {i}}$${\ displaystyle \ sigma}$${\ displaystyle f}$${\ displaystyle \ Delta}$${\ displaystyle f}$${\ displaystyle \ Delta}$${\ displaystyle f}$${\ displaystyle \ Delta}$${\ displaystyle \ sigma ^{*}}$${\ displaystyle \ sigma ^{*}}$${\ displaystyle G}$

${\ displaystyle \ forall i \ in \ {1, \ cdots, N \}, \ forall a \ in A_ {i}: \ quad {\ text {Gain}} _ {i} (\ sigma ^{*}, a) = 0.}$

Dette sier ganske enkelt at hver spiller ikke får noen fordel ved å ensidig endre strategien sin, noe som er nøyaktig den nødvendige betingelsen for en Nash -likevekt.

Anta nå at gevinstene ikke alle er null. Derfor, og sånn . Legg merke til det da ${\ displaystyle \ finnes i \ i \ {1, \ cdots, N \},}$${\ displaystyle a \ i A_ {i}}$${\ displaystyle {\ text {Gain}} _ {i} (\ sigma ^{*}, a)> 0}$

${\ displaystyle \ sum _ {a \ i A_ {i}} g_ {i} (\ sigma ^{*}, a) = 1+\ sum _ {a \ i A_ {i}} {\ text {Gain} } _ {i} (\ sigma ^{*}, a)> 1.}$

Så la

${\ displaystyle C = \ sum _ {a \ i A_ {i}} g_ {i} (\ sigma ^{*}, a).}$

Vi skal også betegne som forsterkningsvektoren indeksert av handlinger i . Siden er det faste punktet vi har: ${\ displaystyle {\ text {Gain}} (i, \ cdot)}$${\ displaystyle A_ {i}}$${\ displaystyle \ sigma ^{*}}$

${\ displaystyle {\ begin {align} \ sigma ^{*} = f (\ sigma ^{*}) og \ Rightarrow \ sigma _ {i} ^{*} = f_ {i} (\ sigma ^{*} ) \\ & \ Rightarrow \ sigma _ {i} ^{*} = {\ frac {g_ {i} (\ sigma ^{*})} {\ sum _ {a \ i A_ {i}} g_ {i } (\ sigma ^{*}) (a)}} \\ [6pt] & \ Høyre pil \ sigma _ {i} ^{*} = {\ frac {1} {C}} \ venstre (\ sigma _ { i}^{*}+{\ text {Gain}} _ {i} (\ sigma^{*}, \ cdot) \ right) \\ [6pt] & \ Rightarrow C \ sigma _ {i}^{* } = \ sigma _ {i} ^{*}+{\ tekst {Gain}} _ {i} (\ sigma ^{*}, \ cdot) \\ & \ Høyre pil \ venstre (C-1 \ høyre) \ sigma _ {i}^{*} = {\ text {Gain}} _ {i} (\ sigma^{*}, \ cdot) \\ & \ Rightarrow \ sigma _ {i}^{*} = \ venstre ({\ frac {1} {C-1}} \ right) {\ text {Gain}} _ {i} (\ sigma ^{*}, \ cdot). \ end {align}}}$

Siden vi har det er en positiv skalering av vektoren . Nå hevder vi det ${\ displaystyle C> 1}$${\ displaystyle \ sigma _ {i}^{*}}$${\ displaystyle {\ text {Gain}} _ {i} (\ sigma ^{*}, \ cdot)}$

${\ displaystyle \ forall a \ i A_ {i}: \ quad \ sigma _ {i}^{*} (a) (u_ {i} (a_ {i}, \ sigma _ {-i}^{*} ) -u_ {i} (\ sigma _ {i}^{*}, \ sigma _ {-i}^{*})) = \ sigma _ {i}^{*} (a) {\ text {Gain }} _ {i} (\ sigma ^{*}, a)}$

For å se dette, merker vi først at hvis dette er sant per definisjon av forsterkningsfunksjonen. Anta det nå . Med våre tidligere uttalelser har vi det ${\ displaystyle {\ text {Gain}} _ {i} (\ sigma ^{*}, a)> 0}$${\ displaystyle {\ text {Gain}} _ {i} (\ sigma ^{*}, a) = 0}$

${\ displaystyle \ sigma _ {i} ^{*} (a) = \ left ({\ frac {1} {C-1}} \ right) {\ text {Gain}} _ {i} (\ sigma ^ {*}, a) = 0}$

og så er det venstre uttrykket null, noe som gir oss at hele uttrykket er etter behov. ${\ displaystyle 0}$

Så det har vi endelig

${\ displaystyle {\ begin {align} 0 & = u_ {i} (\ sigma _ {i}^{*}, \ sigma _ {-i}^{*})-u_ {i} (\ sigma _ {i }^{*}, \ sigma _ {-i}^{*}) \\ & = \ venstre (\ sum _ {a \ i A_ {i}} \ sigma _ {i}^{*} (a) u_ {i} (a_ {i}, \ sigma _ {-i}^{*}) \ høyre) -u_ {i} (\ sigma _ {i}^{*}, \ sigma _ {-i}^ {*}) \\ & = \ sum _ {a \ i A_ {i}} \ sigma _ {i}^{*} (a) (u_ {i} (a_ {i}, \ sigma _ {-i }^{*})-u_ {i} (\ sigma _ {i}^{*}, \ sigma _ {-i}^{*})) \\ & = \ sum _ {a \ i A_ {i }} \ sigma _ {i} ^{*} (a) {\ text {Gain}} _ {i} (\ sigma ^{*}, a) && {\ text {av de tidligere uttalelsene}} \\ & = \ sum _ {a \ i A_ {i}} \ venstre (C-1 \ høyre) \ sigma _ {i}^{*} (a)^{2}> 0 \ ende {justert}}}$

hvor den siste ulikheten følger siden er en ikke-null vektor. Men dette er en klar motsetning, så alle gevinstene må faktisk være null. Derfor er en Nash -likevekt etter behov. ${\ displaystyle \ sigma _ {i}^{*}}$${\ displaystyle \ sigma ^{*}}$${\ displaystyle G}$

Beregning av Nash -likevekt

Hvis en spiller A har en dominerende strategi , eksisterer det en Nash -likevekt der A spiller . Når det gjelder to spillere A og B, eksisterer det en Nash -likevekt der A spiller og B spiller den beste responsen på . Hvis er en strengt dominerende strategi, spiller A i alle Nash -likevekter. Hvis både A og B har strengt dominerende strategier, eksisterer det en unik Nash -likevekt der hver spiller sin strengt dominerende strategi. ${\ displaystyle s_ {A}}$${\ displaystyle s_ {A}}$${\ displaystyle s_ {A}}$${\ displaystyle s_ {A}}$${\ displaystyle s_ {A}}$${\ displaystyle s_ {A}}$

I spill med blandet strategi Nash-likevekt kan sannsynligheten for at en spiller velger en bestemt (så ren) strategi beregnes ved å tilordne en variabel til hver strategi som representerer en fast sannsynlighet for å velge den strategien. For at en spiller skal være villig til å randomisere, bør deres forventede gevinst for hver (ren) strategi være den samme. I tillegg bør summen av sannsynlighetene for hver strategi for en bestemt spiller være 1. Dette skaper et system av ligninger som sannsynligheten for å velge hver strategi kan utledes fra.

Eksempler

I matchende øre -spill mister spiller A et poeng til B hvis A og B spiller samme strategi og vinner et poeng fra B hvis de spiller forskjellige strategier. For å beregne den blandede strategien Nash-likevekt, tildeler A sannsynligheten p for å spille H og (1− p ) for å spille T, og tildel B sannsynligheten q for å spille H og (1− q ) for å spille T.

E [utbetaling for A som spiller H] = (−1) q + (+1) (1− q ) = 1−2 q

E [utbetaling for A som spiller T] = (+1) q + (−1) (1− q ) = 2 q −1

E [payoff for A som spiller H] = E [payoff for A som spiller T] ⇒ 1−2 q = 2 q −1 ⇒ q = 1/2

E [utbetaling for B som spiller H] = (+1) p + (−1) (1− p ) = 2 p −1

E [utbetaling for B som spiller T] = (−1) p + (+1) (1− p ) = 1−2 p

E [payoff for B som spiller H] = E [payoff for B som spiller T] ⇒ 2 p −1 = 1−2 p ⇒ p = 1/2

Således er en blandet strategi Nash-likevekt, i dette spillet, for hver spiller å tilfeldig velge H eller T med p = 1/2 og q = 1/2.

Ulikhet i likevektspunkter

I 1971 kom Robert Wilson med Oddness Theorem, som sier at "nesten alle" endelige spill har et begrenset og oddetall Nash -likevekt. I 1993 publiserte Harsanyi et alternativt bevis på resultatet. "Nesten alle" her betyr at ethvert spill med et uendelig eller jevnt antall likevekter er veldig spesielt i den forstand at hvis utbetalingene til og med ble litt tilfeldig forstyrret, med sannsynlighet en, ville det ha et oddetall likevekt i stedet.

Den innsatte dilemma , for eksempel, har en likevekt, mens den kampen mellom kjønnene har three-- to ren, og en blandet, og dette gjelder også om utbetalingene endres litt. Gratispengespillet er et eksempel på et "spesielt" spill med et like stort likevekt. I den må to spillere både stemme "ja" i stedet for "nei" for å få en belønning, og stemmene er samtidig. Det er to Nash-likevekt med ren strategi, (ja, ja) og (nei, nei), og ingen blandet strategi-likevekt, fordi strategien "ja" svakt dominerer "nei". "Ja" er så godt som "nei" uavhengig av den andre spillerens handling, men hvis det er noen sjanse, velger den andre spilleren "ja", så er "ja" det beste svaret. Under en liten tilfeldig forstyrrelse av utbetalingene er imidlertid sannsynligheten for at to utbetalinger forblir uavgjort, enten det er 0 eller et annet tall, forsvinnende liten, og spillet vil ha enten en eller tre likevekter i stedet.

Se også

Merknader

Referanser

Spillteori lærebøker

Originale Nash -papirer

Andre referanser

Eksterne linker

• "Nash teorem (i spillteori)" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Komplett bevis på eksistens av Nash Equilibria
• Forenklet skjema og relaterte resultater