Skrevet af: CB Garcia og WI Zangwill

Professorer i ledelsesvidenskab ved Booth School of Business (begge pensioneret)

Revideret august 18, 2018 fra (Garcia og Zangwill [8, 9]).

nøgleord: Spilteori, fangerens dilemma, bayesiske, subjektive sandsynligheder

Abstrakt: Von Neumann og Morgenstern (VNM) leverede den forventede nyttighedshypotese den grundlæggende formulering af spilteoriproblemet. Op til dette punkt havde denne formulering imidlertid været vanskelig at løse uden at pålægge yderligere antagelser. Nash måtte antage, at spillerne blev afkoblet, så sandsynligheden for, at spiller A griber ind, var uafhængig af sandsynligheden for, at spiller B griber ind. I dette papir eliminerer vi Nash's antagelser, herunder en antagelse om, at spillernes strategier er almindelig viden, og foreslår en model, der fuldt ud svarer til det generelle VNM-problem. Vores let opløselige formulering eliminerer nogle af de iboende vanskeligheder med Nash-fremgangsmåden, der ofte frembragte modstridende og modsætningsfulde resultater, fx til fangerens dilemma, kyllingespil, Newcombs paradoks, hjortjagt og mange andre spil. For eksempel ved at droppe Nashs gensidige uafhængighedsantagelse i fangens dilemma demonstrerer vores model, at spillerne er i stand til at opnå overlegne gevinster, og for at opnå det, behøver de ikke at spille samarbejdsmæssigt eller kommunikere, men kun anvende Bayes sætning, i stil med (Harsanyi [10]; Kadane og Larkey [11]). Vores tilgang deler sandsynlighedsrummet i to halve mellemrum eller regioner, hvis relative størrelse afhænger af udbetalingen. Man behøver nu ikke at estimere sandsynligheden præcist, men kun bestemme, hvilken region det er i. Dette giver betydelige fordele, hvis dette, hvis det ene område er betydeligt større end det andet, dette straks giver betydelig indsigt i, hvordan man spiller spillet. Vores generelle løsning, som ikke er korreleret, siger i betydningen Aumann [1], indeholder Nash-ligevægterne som særlige løsninger. I modsætning til de beskrivende Nash-løsninger er vores løsning et forskriftsmæssigt par rationelle forventninger til rene strategier, der giver et nyt fundament for spilteori. Vi udvider vores tilgang til generelle M-Person-spil, som vi illustrerer i rock-paper-saks-spillet og bar-trængsel-problemet.

Resumé af resultater.

Vi opsummerer nu nogle resultater baseret på detaljerne og eksplicitte udbetalinger, der er angivet nedenfor. Vi mener, at disse resultater viser værdien af ​​vores tilgang til undervisning og forskning, da resultaterne ofte præsenterer nye løsninger.

Koordinationsspil: The Nash assumption of independence misses the superior Bayesian approach we take. For the payoffs provided below, play the first strategy if you believe that the opponent’s probability of playing its first strategy is at least 1 / 3, else play the second strategy. Nash provides no insights about when to apply which strategy. Also, if the payoffs are changed, our approach provides revised probabilities. Battle of the sexes: Two parties differ on where they should go, but are not allowed to communicate. Both parties obtain a good payoff if they both go to the same choice, since at least they are both together. A given party will get a bonus if they both go to that party’s choice. Neither gets a good payoff if they go different places. Given the payoffs presented below, player A should play its desired strategy if it believes the other player will also select A’s desired choice with probability of at least 33%. In contrast, Nash provides three equilibria without any insight into which to play when and no analysis of the probabilities. Matching pennies: Two players, Even and Odd, simultaneously reveal a penny. If the pennies match, Even keeps both pennies; otherwise Odd keeps both pennies. The unique Nash equilibrium for this zero-sum game is for both players to play randomly. Given the payoffs below, Even should play heads if it believes that Odd will play heads with probability of at least 50%. On the other hand, Odd should play heads if it believes that Even will play heads with probability of at most 50%. Chicken game: Two cars are speeding towards each other and about to have a head-on crash. Nash suggests one car should swerve and the other go straight, but offers little insight into which should swerve. Given the payoffs below, our approach suggests you swerve if you believe that the opponent will swerve with probability of at most 90%, else go straight. Observe here that both players swerving (or both going straight) is not a Nash equilibrium but that both players swerving (or both going straight) in the expectation that the opponent will go straight (or swerve) is an equilibrium scenario. Also, if the payoffs are changed, our approach provides updated probabilities. Arms Race: each country initially stockpiles arms lest it be attacked. But as demonstrated below, diminishing returns on stockpiling arms materialize, opening an opportunity for a peace treaty. Nash does not identify the opportunity for the peace treaty. Stag hunt: hunt stag if you believe that the opponent will hunt stag with probability at least 50%, else hunt hare. (The pure Nash equilibria are for both to hunt stag, or for both to hunt hare). Newcomb’s problem: if Newcomb’s problem is posed as a prisoner’s dilemma, the solution to Newcomb’s problem can be arrived at in two ways: as the non-cooperative Nash equilibrium using the dominance principle, or as a cooperative solution using the expected utility hypothesis. Rock-paper-scissors game: The Nash equilibrium is for you to play a 3-sided die randomly. What appears to be a new strategy for this ancient game is for you to play rock if you believe that your opponent will play paper with probability of at most 33% and scissors with probability of at least 33%; to play paper if you believe that your opponent will play scissors with probability of at most 33% and rock with probability of at least 33%; else to play scissors. (Our approach can help you if say, you have data on your opponent’s previous plays of the game.) Bar-crowding game has 3 friends A, B, and C: Anyone who goes to the bar alone gets nothing – staying home is a better choice. If two friends go to the bar, that is the best option. If all three go, the bar throws all three out. The Nash equilibria are for all to stay home, or for all to play their first strategy with probability equal to 33%. But if you have any insight into your friends and can estimate the Bayesian probabilities of their behavior, our strategy can help.

Vi udvider også vores tilgang til M-person-spillet og får lignende indsigt. For eksempel viser vi den komplette løsning til generelle 2-personers spil og generelle 3 personer x 2 strategispil.

Den forventede værktøjshypotese.

I et 2-person-spil, lad spillerne A og B have 2-strategier: A1 eller A2 for spiller A, og B1 eller B2 for spiller B.

Grundlaget for forventet brugsteori er von Neumann - Morgenstern nyttesætning (von Neumann og Morgenstern [20]): lad Aij og Bij være udbetalingen til henholdsvis spillerne A og B, hvis spiller A spiller Ai og spiller B spiller Bj, for i , j = 1 eller 2. Den forventede nyttehypotese siger, at spillerne A og B skal maksimere deres forventede udbetalinger1:

hvor pA (Ai og Bj) er spiller A's sandsynlighed for, at A spiller Ai og B spiller Bj, og på lignende måde for spiller B.

Betingede sandsynligheder[1].

For vores tilgang, vi drop Nash antager, at spillernes sandsynligheder er gensidigt uafhængige. Dette giver vores problem (1) mulighed for at være mere generelle og få flere løsninger, der tilfredsstiller den forventede nyttehypotese.

Lad EP (A | Ai) og EP (B | Bj) være de forventede udbetalinger[2],[3] af henholdsvis A og B, da A spiller Ai og B spiller Bj, for i, j = 1, 2:

Lad os begynde med at bevise en elementær ”Bayesisk” teorem om spil hvilket demonstrerer ækvivalensen af ​​vores tilgang til VNM-formuleringen:

Sætning 1[5]. Problemer (3) nedenfor svarer til problemer (1)[6]:

Bevis. Ved Bayes 'sætning,

Derefter

Det maksimale[7] af ovennævnte ligning er pA (A1) = 1 (dvs. play strategi A1) hvis EP (A | A1) ≥ EP (A | A2), eller pA (A1) = 0 (dvs. play strategi A2) hvis EP ( A | A1) EP (A | A2). Derfor gælder (3) for spiller A. Et lignende argument gælder for spiller BQED

VNM-regioner.

Definer VNM-regionerne A1 og A2 til at være de konvekse polytoper:

Som vist nedenfor skal A spille strategi A1, hvis den forventer, at B er i region A1. Ellers skal A spille A2. Ligevægtslinjen

adskiller sandsynlighedsrummet i de to regioner og tilvejebringer et visuelt nyttigt middel til at analysere situationen[8].

Regionernes betydning: De to regioner er praktisk vigtige, da man nu ikke behøver at estimere sandsynligheden præcist, men kun bestemme, hvilken af ​​de to regioner det er i. Ofte vil det ses, at den forudgående sandsynlighed sandsynligvis vil være i en region , og identifikation af den region er tilstrækkelig information til at antyde, at spillet er passende. Antag f.eks. At region A1 er betydeligt større end den anden, så sandsynligheden er ganske sandsynligvis i regionen A1. Dette giver overbevisende oplysninger om, at spiller A sandsynligvis vil spille A1.

Analogt for B:

VNM-regionerne er afhængige af spillernes forudgående sandsynlighedsfordelinger, ofte blot kaldet de forudgående (Jaynes [13]; Harsanyi [10]; Kadane og Larkey [11]), som er spillernes udtryk for tro på sandsynlighedsfordelingen af deres modstander. [9]

Korollar 2. Givet (3) spiller A strategi A1, hvis og kun hvis den forventer, at spiller B er i VNM-region A1. Ellers A spiller strategi A2. Tilsvarende spiller B strategi B1, hvis og kun hvis den forventer, at spiller A er i VNM-region B1. Ellers B spiller strategi B2.

Bevis. EP (A | A1) ≥ EP (A | A2) hvis og kun hvis A11 pA (B1 | A1) + A12 pA (B2 | A1) ≥ A21 pA (B1 | A2) + A22 pA (B2 | A2) hvis og kun hvis (A11 - A12) pA (B1 | A1) + (A21 - A22) pA (B2 | A2) + A12 - A21 ≥ 0.

Tilsvarende EP (B | B1) ≥ EP (B | B2) hvis og kun hvis B11 pB (A1 | B1) + B21 pB (A2 | B1) ≥ B12 pB (A1 | B2)

+ B22 pB (A2 | B2) hvis og kun hvis (B11 - B21) pB (A1 | B1) + (B12 - B22) pB (A2 | B2) + B21 - B12 ≥ 0. QED

Fra sætning 1 og Corollary 2, for punkter i regionerne (5) og (7), gælder den forventede nyttehypotese, dvs. VNM-regionerne definerer den generelle løsning til 2-Person-spillet[10].

Nash-ligevægt.

Hvis spillernes sandsynligheder er gensidigt uafhængige, forenkler VNM-regionerne til:

Forslag 3. Antag, at en Nash-ligevægt (p (A1), p (B1)) er i henholdsvis VNM-region Ai og VNM-region Bj, for nogle i, j = 1, 2. Herefter spiller spiller A strategi Ai og spiller B spiller strategi

Bj.

Bevis. Nash's ligevægtsproblem er problem (1), hvor pA (Ai og Bj) = pB (Ai og Bj) = p (Ai) p (Bj), eller problem (3), hvor pA (Bj | Ai) = p (Bj ) og pB (Ai | Bj) = p (Ai), for i, j = 1, 2. Således holder Corollary 2, hvor VNM-regioner er defineret af (8), for pA (B1) = p (B1) og pB (A1) = p (A1). QED

Husk, at ligevægtsligningerne

adskiller VNM-regionerne og giver derved den generelle løsning til ethvert spil. Disse samme ligevægtsligninger, hvor pB (A1) = p (A1) og pA (B1) = p (B1), giver den blandede Nash-ligevægt11, som vi viser i nedenstående tabel.

Forslag 4. Givet ethvert spil A = [[A11, A12], [A21, A22]] og B = [[B11, B12], [B21, B22]], Nash-ligevægten for spillet beregnes ud fra den relevante række i tabel 112.

Bevis. Bemærk, at (i, j) er en ren Nash-ligevægt, hvis og kun hvis sgn (2i - 1) * (A11 - A21)> 0 og sgn (2j - 1) * (B11 - B12)> 0, for i, j = 0, 1. Ved hjælp af denne kendsgerning lister vi alle par (i, j) for hver række i tabel 1, der er rene Nash-ligevægte.

Endelig, for at paret (a, b) defineret af (9) skal være en blandet Nash-ligevægt, behøver vi kun at vise, at 0 <a <1 og 0 <b <1. Men bemærk at for rækkerne 6, 7, 10 og 11 i tabel 1 er tælleren og nævneren for a, 1 - a, b eller 1 - b begge positive eller begge negative; derfor er a, 1 - a, b, 1 - b alle større end 0. QED

Iterated Dominance-eksempel[13].

Lad A = [[2, 2], [3, 1]] og B = [[0, 1], [0, 2]]. “Spil A1 & B2” er Nash-ligevægten.

Forslag 5. Givet A = [[2, 2], [3, 1]] og B = [[0, 1], [0, 2]], derefter spiller spiller A spiller A1 og spiller B spiller B2.

Bevis. VNM-region A1 er: pA (B2 | A2) ≥ 1 / 2, og VNM-region B2 er: pB (A2 | B2) ≥ -1. Derfor spiller spiller B B2. Spiller A ved også, at dette er tilfældet, hvorfor pA (B2 | A2) = 1. Da pA (B2 | A2) = 1 er et punkt i VNM-region A1, spiller spiller A A1. QED

Koordinationseksempel.

Lad A = B = [[2, 0], [0, 1]]. Der er 3 Nash-ligevægtspunkter: “play A1 & B1”, “play A2 & B2” og “play A1 (eller B1) med sandsynlighed 1 / 3”. VNM-region A1 er: 2pA (B1 | A1) ≥ pA (B2 | A2) og VNM-region B1 er: 2pB (A1 | B1) ≥ pB (A2 | B2). Ved at analysere disse VNM-regioner visuelt vil A og B sandsynligvis vælge strategierne henholdsvis A1 og B1.

Forslag 6. Givet A = B = [[2, 0], [0, 1]], hvis spillernes sandsynligheder er gensidigt uafhængige, så spill den første strategi, hvis du mener, at modstanderens sandsynlighed for at spille sin første strategi er mindst 1 / 3, ellers spiller den anden strategi.

Bevis. VNM-region A1 er: pA (B1) ≥ 1 / 3 og VNM-region B1 er: pB (A1) ≥ 1 / 3. QED

Battle of the Sexes Eksempel.

Lad A = [[3, 1], [1, 2]] og B = [[2, 1], [1, 3]]. Der er 3 Nash-ligevægtspunkter: “play A1 & B1”, “play A2 & B2” og “play A1 med sandsynlighed 2 / 3, play B1 med sandsynlighed 1 / 3”. VNM-region A1 er: 2pA (B1 | A1) ≥ pA (B2 | A2) og VNM-region B1 er: pB (A1 | B1) ≥ 2pB (A2 | B2). A vil hellere vælge A1 og B vil hellere vælge B2.

Forslag 7. Givet A = [[3, 1], [1, 2]] og B = [[2, 1], [1, 3]], hvis spillernes sandsynligheder er gensidigt uafhængige, så: spill A1 hvis pA (B1 ) ≥ 1 / 3, ellers spill A2; afspil B1, hvis pB (A1) ≥ 2 / 3, ellers afspil B2.

Bevis. VNM-regionen A1 er: pA (B1) ≥ 1 / 3 og VNM-regionen B1 er: pB (A1) ≥ 2 / 3. QED

Matchende øreeksempel.

Lad A = [[1, -1], [-1, 1]] og B = [[-1, 1], [1, -1]]. Dette nul-sum-spil har en blandet Nash-ligevægt: "spil A1 med sandsynlighed 1 / 2, spil B1 med sandsynligheden 1 / 2".

Forslag 8. Givet A = [[1, -1], [-1, 1]] og B = [[-1, 1], [1, -1]], hvis spillernes sandsynligheder er gensidigt uafhængige, så: spill A1 Hvis pA (B1) ≥ 1 / 2, skal du ellers spille A2; afspil B1 hvis pB (A1) 1 / 2, ellers spiller B2[14].

Bevis. VNM-regionen A1 er: pA (B1) ≥ 1 / 2 og VNM-regionen B1 er: pB (A1) 1 / 2. QED

Eksempel på kyllingespil (Sugden [19]).

Lad A = [[0, -1], [1, -10]] og B = [[0, 1], [-1, -10]]. Nash-ligevægterne er “play A1 (swerve) & B2 (go straight)”, “play A2 (go straight) & B1 (swerve)” og “play A1 (B1) med sandsynlighed 0.9”.

Forslag 9. Hvis spillernes sandsynligheder er gensidigt uafhængige i kyllingespelet, så: sving, hvis du tror, ​​at modstanderen vil svæve med sandsynligheden for højst 90%, gå ellers lige.

Bevis. VNM-regionen A1 er: pA (B1) + 11pA (B2) ≥ 2, eller pA (B1) ≤ 9 / 10. Tilsvarende er VNM-regionen B1: pB (A1) ≤ 9 / 10. QED

Vær opmærksom på, at hvis din modstander viser for meget entusiasme (mindst 90%) til at svæve, så burde du gå lige.

Foretrukket scenario: Det er sandsynligt, at spillerne svinger end at gå lige.

Kylling-scenarie: Antag pA (B1) = pB (A1) = 0. Begge spillere forventer, at den anden spiller går lige. Begge vil svinge.

Katastrofescenarie: Antag, at pA (B1) = pB (A1) = 1. Begge spillere forventer, at den anden spiller svinger. Begge vil gå lige[15].

Nash ligevægtscenario: Antag pA (B1) = 1 - pB (A1) og pB (A1) = 0 eller 1. Den spiller, der forventer, at den anden spiller skal gå lige, vil svæve, og den spiller, der forventer, at den anden spiller vil svinge, vil gå lige.

Eksempel på våbenløb.

I forslag 9, lad A = [[0, -x], [1, -10x]], B = [[0, 1], [-y, -10y]], for x, y ≥ 0. Lad A1 eller B1 være "søge fred" og A2 eller B2 være "atomangreb". Værdierne x og y betegner våbenlageret af henholdsvis B og A.

Land A søger fred, hvis sandsynligheden for, at land B angriber, er større end 1 / (9x + 1); ellers angriber A. Sandsynlighedskurven pA (B1) = 1 / (9x + 1) falder hurtigt, fx pA (B1) = 1 / 2 ved x = 1 / 9, men snart flattes dramatisk ud: B skal hurtigt lagres oprindeligt, men som kurven plader, der vil være lille fordel for B for at lagre arme.

Og på lignende måde for land B.

Sammenfattende lagrer hvert land oprindeligt våben, for ikke at blive angrebet. Men hurtigt aftagende afkast på lagring af våben materialiseres, hvilket åbner en mulighed for at søge en fredsaftale.

Som illustration skal du overveje den estimerede 2018 globale atomlager[16] i tabel 2.

Baseret på udbetalingerne ovenfor og tabel 2, burde et rationelt Nordkorea søge en fredsaftale med De Forenede Stater og Rusland.

Skyrms [16]).

Lad A = [[4, 1], [3, 2]] og B = [[4, 3], [1, 2]]. Nash-ligevægterne er “play A1 (Stag) & B1 (Stag)”, “play A2 (Hare) & B2 (Hare)” og “play A1 (B1) med sandsynlighed 0.5”.

Forslag 10. Hvis spillerens sandsynligheder er gensidigt uafhængige i hjortjagt, skal du: jage hjort, hvis du tror, ​​at modstanderen vil jage hjort med sandsynlighed for mindst 50%, jagt hare.

Bevis. VNM-regionen A1 er: 3pA (B1) + pA (B2) ≥ 2 eller pA (B1) ≥ 1 / 2. Tilsvarende er VNM-regionen B1: pB (A1) ≥ 1 / 2. QED

Fangerens dilemma[17].

Lad A12 <A22 <A11 <A21, og lad B være lig med transponering af A. Da A11 <A21 og A12 <A22, giver brugen af ​​dominansprincippet Nash-ligevægten, nemlig den ikke-kooperative løsning “spiller A2 (defekt) og B2 (defekt) ”. Men da A22 <A11, A og B er bedre stillet, hvis de begge spiller den kooperative løsning “play A1 (stilhed) og B1 (stilhed)”.

Forslag 11. I fangens dilemma, hvis spillernes sandsynligheder er gensidigt uafhængige, spiller spillerne ikke-samarbejdsvilligt[18].

Bevis. Overvej venstre side af VNM-regionen A1:

(A11 - A12 - A21 + A22) sA(B1) + A12 - A22.

Hvis A11 - A12 - A21 + A22 ≤ 0, så (A11 - A12 - A21 + A22) pA(B1) + A12 - A22 ≤ A12 - A22 <0. På den anden side, hvis A11 - A12 - A21 + A22> 0, så (A11 - A12 - A21 + A22) pA(B1) + A12 - A22 ≤ (A11 - A12 - A21 + A22) + A12 - A22 = A11 - A21 <0. For enhver foregående for spiller A er VNM-regionen A1 således nul-sæt, og derfor skal det spille strategi 2.

Tilsvarende skal spiller B spille strategi 2. QED

Forslag 11 viser tydeligt, at antagelsen om uafhængighed begrænser os til den ikke-samarbejdsvillige løsning.

Eksempel på klassisk fangerens dilemma.

I den klassiske fanges dilemma er A = [[-1, -3], [0, -2]] og B = [[-1, 0], [-3, -2]].

Forslag 12. I den klassiske fanges dilemma, hvis spillernes forudgående er: pA (B1 | A1) + pA (B2 | A2) ≥ 3 / 2, pB (A1 | B1) + pB (A2 | B2) ≥ 3 / XUM spillerne spiller den kooperative løsning2.

Bevis. VNM-regionen A1 er: pA (B1 | A1) + pA (B2 | A2) ≥ 3 / 2, og VNM-regionen B1 er: pB (A1 | B1) + pB (A2 | 2) Derfor skal spillerne A og B for de givne forudgående spillere spille den kooperative løsning. QED

I forslag 12 skal du bemærke den høje bjælke, der kræves for at spille den kooperative løsning. Spillerne vil hellere vælge at spille den ikke-samarbejdsvillige løsning.

Et tilfælde, hvor Nash-metoden ikke overvejer at spille samarbejdsstrategien.

Overvej fangerens dilemma, hvor A11 - A12 = A21 - A22, A21 = A11 + m og A22 = A11 - M, hvor m> 0 er lille og M> 0 er meget stor. For eksempel A = [[100, -3], [101, -2]]. Husk fra Proposition 11, at hvis spillernes sandsynligheder er gensidigt uafhængige, så vil spillerne spille ikke-samarbejdsvilligt.

Det er klart, det ville være tåbeligt for spillerne at ikke engang overveje at spille strategi 1, da hvis en spiller spiller 2, vil chancen for, at den anden spiller også spiller 2, give et betydeligt tab, så hvorfor risikere det. Det er klart, at Nash-metoden ikke overvejer at spille den kooperative løsning, selv når det er den åbenlyse løsning at spille - et meget vigtigt punkt i sagen, diskussioner om markedsfordeling i generelle økonomiske ligevægtsmodeller.

På den anden side, som det næste forslag viser, ved at droppe antagelsen om uafhængighed, vil vores tilgang spille den kooperative løsning snarere end den ikke-kooperative løsning.

Den sorte linje er ligegyldighedslinjen for den klassiske fanges dilemma. En spiller er mere tilbøjelige til at spille strategi 2 på grund af den usandsynlige sandsynlighed for at være i regionen for at spille strategi

1.

Den grønne linje er ligegyldighedslinjen for denne forekomst af fangerens dilemma: pA (B1 | A1) + pA (B2 | A2) = 1 + m / (M + m). Her er størrelsen på sandsynlighedsregionen for strategi 1 næsten størrelsen for strategi 2. Vores tilgang tilråder spillerne at overveje at spille strategi 1.

Forslag 13. Givet en fanges dilemma, hvor A11 - A12 = A21 - A22, A21 = A11 + m og A22 = A11 - M, hvor m> 0 er lille, og M> 0 er meget stor, spillerne A og B spiller den kooperative løsning20.

  • Derfor vil spillerne ikke spille den ikke-samarbejdsvillige løsning.
  • For at nå den kooperative løsning tilføjes antagelser, for eksempel afgrænset rationalitet, ufuldstændig information (Aumann og Maschler [2]; Acevedo og Krueger [4]; Daley given A's forventede fælles sandsynligheder pA (Ai og Bj), A konkluderer, at pA (A1 og B1) skal være i nærheden af ​​1.Det skyldes, at A og B sandsynligvis spiller strategi 1, hvor deres udbetalinger er ret høje og kun m-enheder er mindre end maksimal.

Derfor skal pA (B1 | A1) = pA (A1 og B1) / pA (A1) også være i nærheden af ​​1.

A konkluderer også, at pA (A2 og B2) pA (A2 og B1), da B er mere sandsynligt for at spille strategi 2, hvis A spiller strategi 2. Derfor pA (B2 | A2) = pA (A2 og B2) / (pA (A2 og B1) + pA (A2 og B2)) 1 / 2. A konkluderer under anvendelse af fig. 1, at B er tilstrækkeligt inden for VNM-området A1. Tilsvarende vil B spille strategi 1. QED

Newcombs paradoks som en version af fangerens dilemma.

I den berømte Newcombs paradoks (Wolpert og Benford [21]) er der en prediktor B, en spiller A og en boks X. Spilleren A får valget mellem at tage boksen X eller boksen X plus $ 1,000. Før A vælger, forudsiger B, hvad A vil gøre, og B's forudsigelser er næsten sikre. Hvis B forudsiger, at A kun tager felt X, sætter B $ 1,000,000 i boks X. I dette tilfælde, da boksen har en $ 1,000,000 i, modtager A $ 1,000,000 eller $ 1,001,000 afhængigt af om A vælger boks X eller X plus $ 1,000. På den anden side, hvis B forudsiger, at A vil tage boks X plus $ 1,000, placerer B intet i boks X. I dette tilfælde, afhængigt af dets valg, modtager A enten $ 1,000 eller intet.

Newcombs paradoks er, at to perfekt rationelle analyser giver modstridende svar på spiller A's optimeringsproblem: Under den forventede nyttehypotese bør spiller A kun tage boks X, da den forventede gevinst ved at tage X er meget højere. På den anden side, under dominansprincippet, skal spiller A tage boks X plus $ 1,000.

Paradokset forstås bedst ved en passage i (Wolpert og Benford [21]): “… Newcomb sagde, at han bare ville tage X; hvorfor kæmpe for et gudlignende væsen? Nozick sagde imidlertid: 'For næsten alle er det helt klart og tydeligt, hvad der skal gøres. Problemet er, at disse mennesker ser ud til at dele sig næsten jævnt på problemet, idet store tal tror, ​​at den modsatte halvdel bare er fjollet. '… ”.

Wolpert og Benford løser paradokset ved at vise, at Newcombs problem faktisk repræsenterer to forskellige spil med forskellige sandsynlige resultater.

I dette afsnit vil vi løse paradokset ved at stille Newcombs problem som en fanges dilemma. Dermed kan løsningen på Newcombs problem nås på to måder: som den ikke-kooperative løsning (tag boks X plus $ 1,000) ved hjælp af dominansprincippet, eller som den kooperative løsning (tage kun boks X) ved hjælp af det forventede nyttehypotese.

Antag, at der er en rig velgørenhed, der lover at finansiere en udbetalingsmatrix til prediktor B, der giver følgende spil: A = [[$ 1,000,000, 0], [$ 1,001,000, $ 1,000]] og B = [[$ 1,000,000, $ 1,001,000 ], [0, $ 1,000]].

Hvis B forudsiger korrekt, får B, hvad spiller A får. Men hvis B forudsiger forkert, får B $ 1,001,000 minus hvad A får21.

Fra Proposition 13 spiller spillerne A og B kooperativt i dette spil.

Hvis spilleren som Nash, løser problemet ved hjælp af dominansprincippet, gør prediktoren det også. Både prediktor og spiller vil være på den ikke-samarbejdsvillige løsning: tage X plus $ 1,000. Hvis afspilleren løser problemet ved hjælp af den forventede nyttehypotese, gør prediktoren det også, og både prediktor og spiller vil være i samarbejdsløsningen: tage kun X. I begge tilfælde er prediktorens forudsigelse

og Sadowski [6]) eller nye metoder er beskrevet, fx tit-for-tat, korrelerede ligevægter (Axelrod [3]; Aumann [1]).

21 Bemærk, at ved at stille Newcombs problem som et PD-problem får prediktoren et personligt incitament, der er fraværende i Newcombs problem.

bestemte. Da spillere ikke vil spille den ikke-samarbejdsvillige løsning fra Proposition 13, er vi enige med Newcomb om, at samarbejde er den åbenlyse strategi at tage.

Bemærk i fig. 1, men området for samarbejde er imidlertid ubetydelig mindre end for ikke-samarbejde. Det er os ikke overraskende, hvis folk deler jævnt på hvilken strategi de skal tage.

En generalisering af fangerens dilemma til M-personer.

For bedre at forstå, hvordan Nash-løsningen kan nedbrydes i generelle økonomiske ligevægtsmodeller, lad os generalisere fangerens dilemma til M-Personer, hvor hver spiller har 2-strategier, for M 2.

Lad os beskrive M-Person-spillet via binære træer.

Fig. 2 er fangens dilemma-udbetaling for spiller A. Træ (2, 1) er det binære træ med spiller B (spiller 2) som forælder, og spiller A (spiller 1) som barn. For at opnå udbetalingen for spiller B skal du blot skifte roller som forælder og barn til Tree (1, 2). Husk, at det for fangens dilemma er A12 <A22 <A11 <A21.

Antag derefter, at Tree (M - 1, M - 2,…, 2, 1) betegner spiller A's gevinst for et (M - 1) -Person-spil, for M 3. Konstruer spiller A's payoff-træ (M, M - 1, ..., 2, 1) til et M-Person-spil ved at lade spiller A's Tree (M - 1, M - 2, ..., 2, 1) være undertræerne på begge grene af forælder spiller M.

De numeriske værdier for udbetalingen på det højre undertræ antages forskellige fra dem på det venstre undertræ, så længe forholdet A12 <A22 <A11 <A21 opretholdes overalt i træet.

Endelig, givet træ (M, M - 1, ..., 2, 1) til spiller A, opret træ (1, M, M - 1, ..., 3, 2) til spiller B (spiller 2) ved at gøre 1 til det højeste forælder; Træ (1, 2, M, M - 1,…, 4, 3) til spiller 3 ved at gøre 2 til den næsthøjeste overordnede,…, Tree (1, 2, 3,…, M - 2, M, M - 1 ) for spiller M - 1 ved at gøre M - 2 til det tredje laveste barn, Tree (1, 2, 3,…, M - 1, M) til spiller M ved at gøre M - 1 til det næst laveste barn.

Dette afslutter beskrivelsen af ​​spillernes udbetaling for et M-Person fanger-dilemma-spil, hvor hver spiller har 2-strategier.

Sætning 14. For M-Person fangerens dilemma, M 2, ved hjælp af dominansprincippet, er Nash-løsningen for spillerne at spille strategi 2.

Bevis. Vi ved allerede, at teoremet gælder for M = 2. Antag ved induktion, at teoremet gælder for M - 1, for M 3. Lad os vise, at teoremet gælder for M.

Givet træ (M, M - 1,…, 2, 1) for spiller A, husk at under konstruktion er undertræerne på venstre og højre gren af ​​formen træ (M - 1, M - 2,…, 2 , 1) til spiller 1, Træ (M, M - 1,…, 2) til spiller 2, Træ (2, M, M - 1,…, 4, 3) til spiller 3,…, Træ (2,… , M - 2, M, M - 1) til spiller M - 1. Disse undertræer er identiske for spillere 1, 2, ..., M - 1, bortset fra mærkning på forældrenes knudepunkter. Bemærk, at hver spillers strategi 2 dominerer sin strategi 1 under enhver betingelse. Ved induktion ved hjælp af dominansprincippet spiller spillerne 1 til M - 1 strategi 2.

Derfor, givet træ (1, 2, ..., M - 1, M) for spiller M, hvis M spiller 1, er udbetalingen for spiller M b (træets anden højeste knude), hvorimod hvis M spiller 2, er udbetalingen for spiller M for spiller M er A22 (træets højeste knude). Efter dominansprincippet, da A12 <A22, spiller spiller M også strategi 2. QED

Antag nu, at enhver udbetaling af typen A11 er meget større end enhver udbetaling af typen A22; og at A21 = A11 + m, hvor udbetalinger A11 og A21 er i tilstødende noder.

Det er klart, Nash-metoden undlader at overveje at spille den kooperative løsning “play strategi 1”, selv når det er den åbenlyse løsning at spille.

Efter det induktive argument fra sætning 14, kan vi også konkludere, at da undertræerne på venstre og højre gren er af formen Træ (M - 1, M - 2, ..., 2, 1) for spiller 1, Træ ( M - 1, M - 2,…, 2) til afspiller 2, træ (2, M, M - 1,…, 4, 3) til spiller 3,…, træ (2,…, M - 2, M, M - 1) for spiller M - 1 ved induktion ved brug af den forventede utility-hypotese spiller spillerne 1 til M - 1 strategi 1, hvor udbetalingen er af typen A11.

Derfor, givet træ (1, 2, ..., M - 1, M) for spiller M, hvis M spiller 1, er udbetalingen for spiller M en (træets mest venstre knude), mens hvis M spiller 2, er udbetalingen for spilleren M spiller M er A21 = A11 + m (den anden venstre knude på træet). Siden A11 <A21 kan spiller M blive fristet til at spille strategi 2. Men hvorfor risikere at spille strategi 2 for m enheder mere end A11, når det kan føre til en udbetaling af typen A22, en udbetaling, der er væsentlig mindre end A11?

Ved den forventede nyttehypotese skal spiller M også spille strategi 1.

Generelle M-person spil.

Endelig generaliserer vi sætning 1 til generelle M-personers spil.

Lad der være M-spillere, hvor hver spiller i har ingen mulige strategier for hver i = 1, 2, ..., M. Givet strategievectoren (j1, j2, ..., jM), lad udbetalingen til spilleren være Aij1j2 ... Jm. Lad xi være en blandet strategi for spiller i, dvs. en strategi xi hvor Σj xij = 1, xij 0, alle j, og lad x = (xi, xi) betegne alle spillers strategier. Nash's problem er:

hvor EP (i | xi) er den forventede udbetaling til spiller jeg har givet xi, og hvor sammenlægningen er over alle jk og alle k.

En strategi x * er en Nash-ligevægt, hvis xi * er en løsning på spiller i's problem ovenfor, givet xi *.

For vores tilgang, lad pij1, j2, ..., JM være spiller I er forventet sandsynlighed for, at spiller k spiller jk, for alle jk og alle k. Von Neumann – Morgenstern forventet nytte-teori siger, at spiller i's mål er at maksimere sin forventede udbetaling:

hvor summationen er over alt jk og alle k.

Definere

hvor -jeg spiller j-i betyder, at spiller k spiller jk, og hvor summationen er over alt jk, for alle k i.

Sætning 15. Problemer (13) nedenfor svarer til problemer (11):

Bevis.. Per definition,

hvor summationen er over alle rk, for enhver k i.

Nævneren til (14) er sandsynligheden pi (i spiller ji). derfor

Siden Σ pi (jeg spiller ji) = 1 og pi (jeg spiller ji) 0 for alle ji, det følger, at spiller i spiller strategi [arg maxji EP (i | i spiller ji)]. QED

En metode til at finde den bedste strategi for spiller i er som følger: For ethvert par strategier for spiller i, siger strategi r og strategi, skal du beregne locus for point, hvor jeg er forventede udbetalinger betinget af, at spiller, jeg spiller enten r eller s, er ens . Dette definerer en ligegyldighedsoverflade, der deler det betingede sandsynlighedsrum i 2 VNM-regioner. Én VNM-region er mærket r, fordi den valgte strategi er r, og den anden VNM-region er mærket s, fordi den valgte strategi er s.

Efter beregningerne ovenfor vil hver VNM-region være mærket så mange gange, som der er forskellige par strategier. For enhver given VNM-region skal du tage en hvilken som helst to af de flere etiketter og fjerne en af ​​dem baseret på ligegyldighedsoverfladen, der er skabt af dette par etiketter. Processen slutter, når hver VNM-region kun har én etiket.

Generelle 2-personers spil.

Lad spiller A have strategier Ai, i = 1, 2, ... n1 og player B har strategier Bj, j = 1, 2, ... n2. Antag, at spillernes sandsynligheder er gensidigt uafhængige. Problem (13) er:

Derfor er VNM-regionerne defineret af konvekse polytoper:

Som det kan observeres i (16), er det let at finde løsningen sat til et generelt 2-personespil. Overvej for eksempel det over to tusind år gamle Rock-Paper-Scissors-spil, hvor Nash-ligevægten er: spil enhver strategi med 33% sandsynlighed:

Strategi A1 eller B1 (rock) taber til strategi A2 eller B2 (papir) taber til strategi A3 eller B3 (saks) taber til rock.

For spiller A har vi generelt, hvor 0 pA (Bj) 1,

som reducerer til

Og på lignende måde for spiller B.

Hvad der ser ud til at være en ny strategi for dette gamle spil er: spille rock, hvis du tror, ​​at din modstander vil spille papir med en sandsynlighed på højst 33% og en saks med en sandsynlighed på mindst 33%; spille papir, hvis du tror, ​​at din modstander vil spille saks med sandsynlighed for højst 33% og rock med sandsynlighed for mindst 33%; ellers spiller saks22.

3-personers spil, hvor hver person har 2-strategier.

Lad os anvende sætning 15 til at finde den løsning, der er sat til et 3-person-spil, hvor hver spiller A, B og C har 2-strategier Ai, Bi, Ci, for i = 1, 2.

Antag, at spillernes sandsynligheder er gensidigt uafhængige. For spiller A er ligningen (13)

og på lignende måde for spillere B og C. Ved hjælp af sætning 15 defineres løsningen af:

Lad os bruge ovenstående til Bar-trængsel-spillet[21]:

Hvis spilleren er hjemme, er dens udbetaling 1; hvis spilleren er alene i baren, er dens udbetaling 0; hvis spilleren er i baren med en anden person, er dens udbetaling 2; Ellers er dens udbetaling -1.

Vi har: A111 - A211 = -2, A112 - A212 = A121 - A221 = 1, A122 - A222 = -1, derfor er VNM region A1 regionen -3pA (B1 X) (C1) - 2 ≥ 1, eller tilsvarende regionen[22] pA (B1) ≥ (1 - 2pA (C1)) / (2 - 3pA (C1)). Tilsvarende er VNM-regionen B1 regionen pB (A1) ≥ (1 - 2pB (C1)) / (2 - 3pB (C1)) og VNM region C1 er regionen pC (B1) ≥ (1) X / (2 - 1pC (A2)). Nash-ligevægten er p (A) = p (B) = p (C) = 3 og p (A) = p (B) = p (C) = 1 / 1.

Anerkendelse.

Vi vil gerne takke Al Roth og Todd Davies for deres uvurderlige råd og vejledning i forberedelsen af ​​dette papir.

Fodnoter

[1] For enkelheds skyld antager vi den fælles antagelse, at værktøjet er en lineær funktion af udbetalingen (Starmer [18]). Derfor er maksimering af forventet nytteværdi det samme som at maksimere forventet udbetaling.

[2] Vores Bayesiske tilgang til spil adskiller sig fra tidligere Bayesian-arbejde (for eksempel Acevedo og Krueger [4]; Aumann [1]; Daley og Sadowski [6]; McKelvey og Palfrey [12]; Quattrone og Tversky [15]) ved, at i modsætning til de andre tilgange, ændrer vores tilgang betingede sandsynligheder utvetydigt til den forventede nyttehypotese, som vores løsning altid tilfredsstiller.

[3] En kritiker siger, at "rationelle spillere ikke og bør ikke overveje betingede sandsynligheder ... Forestil dig en agent, der ved, at sandsynligheden for regn er p. Din 'løsning' ser ud til at være, at agenten skal tage en paraply med sig, hvis det regner og forlade paraplyen, hvis det ikke regner ”.
Sætning 1 viser, at den tidligere kritik er uberettiget. Med hensyn til sidstnævnte kritik, lad EP (agent | bringe en paraply) = p, og EP (agent | medbringe ikke en paraply) = 1 - p. Vores løsning ville så være: at bringe en paraply, hvis p ≥ 1 / 2; medbring ikke en paraply, hvis p ≤ 1 / 2.

[4] De betingede sandsynligheder for (2) overtræder ikke princippet i Spohn [17]: ”Enhver passende kvantitativ beslutningsmodel må ikke eksplicit eller implicit indeholde nogen subjektive sandsynligheder for handlinger…” En spillers betingede sandsynligheder er subjektive sandsynligheder for modstanderens strategier, ikke for sine egne strategier.

[5] Dette teorem vil blive generaliseret til et for M-personers spil.

[6] Der er ingen signalering mellem spillerne.

[7] De uafhængige variabler pA (B1 | A1) og pA (B2 | A2) antages givet i maksimeringsproblemet, en forenkling, der undgår problemet med uendelig regress (svarer til Nashs antagelse om, at p (B1) er givet for spilleren A i formuleringen af ​​hans maksimeringsproblem).

[8] Inequality (5) er den (opdagede) løsning på problemet (1) på samme måde som den kvadratiske formel er løsningen på en generel kvadratisk ligning.

[9] Spillerens forudgående kan være afhængig af delvist observerbare tilfældige begivenheder, såsom vejret. For brug af tidligere i spil med ufuldstændige oplysninger, der spilles af Bayesianske spillere, henvises til (Harsanyi [10]).

[10] Denne generelle opløsning indeholder Nash-ligevægten som særlige opløsninger. I modsætning til de beskrivende Nash-løsninger er vores løsning et par foreskrivende rationelle forventninger rene strategier. Hvis spiller A der ved en fejl er i VNM-regionen A1 og spiller A2, siger Corollary 2, at spiller A vil få en lavere forventet udbetaling.

[11] Det er interessant at bemærke, at ved en blandet Nash-ligevægt er en spillers strategi afhængig af at kende den anden spillers udbetalingsfunktion.

[12] Nulskilte ignoreres i tabellen, da disse tilfælde er degenererede: en spiller kan ikke vælge mellem sine to strategier. Det er også interessant at bemærke, at hver Nash-ligevægt vises i nøjagtigt fire rækker.

[13] De næste 3-eksempler er tilpasset fra (Davies [7]) på en måde, der kan tjene som en pædagogisk teknik for studerende i spilteori. Tabel 1 kan bruges til hurtigt at finde Nash-ligevægten for alle de heri beskrevne 2-personspileksempler.

[14] A's handlinger påvirker ikke B's valg af handlinger. Dette skyldes, at A's overbevisning ikke er korreleret med B's overbevisning. På den anden side, hvis tro er korreleret, skal begge spillers sandsynligheder være lige 50%, ellers, hvis man siger, at spillernes sandsynligheder er begge> 50%, A ved, at B vil spille strategi 2 (haler), og dermed spille strategi 1 (hoveder) kan ikke være en korrekt recept for A. Hvis det er sagt, A's sandsynlighed er> 50% og B's sandsynlighed er <50%, B ved, at A vil spille hoveder, og derfor kan det at spille hoveder ikke være en korrekt recept for A. osv. unik løsning er derfor Nash-ligevægten: leg tilfældigt for begge.

[15] Bemærk, at pA (B1) = pB (A1) = 0 eller 1 er et ligevægtscenarie: begge spillere svinger (eller begge går lige), hvis begge spillere forventer, at den anden spiller skal gå lige (eller svinge). I modsætning hertil kan p (A1) = p (B1) = 0 eller 1 ikke være en Nash-ligevægt: Hvis B går lige (eller svinger), vil A svinge (eller gå lige).

[16] Kilder: Arms Control Association, Federation of American Scientists, International Panel on Fissile Materials, US Department of Defense, US State State Department og Stockholm International Peace Research Institute.

[17] Siden Flood og Dreshers originale papir, er tusinder af artikler blevet offentliggjort om det. En Google Scholars søgning efter “fangerens dilemma” giver 104,000-resultater fra dette tidspunkt. Confer (Kuhn [14]).

[18] Derfor spillerne ikke spiller den kooperative løsning.

[19] Hvis din modstander spiller ikke tilfældigt, kan din foregående blive påvirket af din modstanders tidligere afspilninger af dette spil.

[20] Formlen kan udvides til M-personer til M> 3.

[21] Dette spil er baseret på El Farol-barproblemet (Arthur [5]).

[22] Likegyldighedsstedet er en kvadratisk kurve, der passerer gennem punkterne (pA (C1), pA (B1)) = (0.5, 0), (0.33, 0.33), (0, 0.5).

Referencer

[1] Aumann RJ (1974) Subjektivitet og korrelation i tilfældige strategier. Journal of Mathematical Economics 1: 67-96

[2] Aumann RJ, Maschler M (1995) gentagne spil med ufuldstændig information. MIT Press, Cambridge London

[3] Axelrod R (1984) Udviklingen af ​​samarbejde. Grundlæggende bøger

[4] Acevedo M, Krueger JI (2005) Bevidst begrundelse i fangens dilemma. American Journal of Psychology 118: 431-457

[5] Arthur WB (1994) induktiv begrundelse og bundet rationalitet. American Economic Review 84: 406-411

[6] Daley B, Sadowski P (2017) Magisk tænkning: Et repræsentationsresultat. Teoretisk økonomi 12: 909-956 24 Dette spil er baseret på El Farol-barproblemet (Arthur [5]). 25 Lokaliteten af ​​ligegyldighed er en kvadratisk kurve, der passerer gennem punkterne (pA (C1), pA (B1)) = (0.5, 0), (0.33, 0.33), (0, 0.5).

[7] Davies T (2004) værktøjsteori og spilteori. Forelæsningsnotater

[8] Garcia CB, Zangwill WI (2017) En ny tilgang til krig eller fred. Arbejdspapir

[9] Garcia CB, Zangwill WI (2018) dominans, forventet værktøj og fangerens dilemma. Arbejdspapir

[10] Harsanyi J (1967) spil med ufuldstændig information spillet af “Bayesian” spillere I - III. J. Management Science 14 (3): 159-182

[11] Kadane JB, Larkey PD (1982) Subjektiv sandsynlighed og teorien om spil. Management Science 28 (2): 113-120

[12] McKelvey RD, Palfrey TR (1995) Quantal Response Equilibria for Normal Form Games. Spil og økonomisk opførsel 10: 6-38

[13] Jaynes ET (1968) Forudgående sandsynligheder. IEEE-transaktioner med systemvidenskab og cybernetik 4 (3): 227-241

[14] Kuhn S (2017) Fangerens dilemma. The Stanford Encyclopedia of Philosophy

[15] Quattrone GA, Tversky A (1984) Årsagsmæssig versus diagnosticeringsbetingelser: På selvbedrag og på vælgerens illusion. Journal of Personality and Social Psychology 46: 237-248

[16] Skyrms B (2004) Hjortjag og udviklingen af ​​social struktur. Cambridge University Press, Cambridge

[17] Spohn W (1977) Hvor Luce og Krantz virkelig generaliserer Savages beslutningsmodel. Erkenntnis 11: 113-134

[18] Starmer C (2000) Udviklingen i ikke-forventet nyttensteori: jagt på en beskrivende teori om valg under risiko. Journal of Economic Literature 38: 332-382

[19] Sugden R (2005) The Economics of Rights, Cooperation and Welfare. Palgrave MacMillan, 2-udgave: 132

[20] Von Neumann J, Morgenstern O (1953) Teori om spil og økonomisk adfærd. Princeton University Press, New Jersey

[21] Wolpert DH, Benford G (2011) Lektionen i Newcombs paradoks. Syntese 190: 1637-164