Napsali: CB Garcia a WI Zangwill

Profesoři managementu na Booth School of Business (oba v důchodu)

Upraveno srpna 18, 2018 z (Garcia a Zangwill [8, 9]).

Klíčová slovaTheory teorie her, dilema vězně, bayesovský, subjektivní pravděpodobnosti

Abstraktní: Von Neumann a Morgenstern (VNM), využívající očekávanou hypotézu užitečnosti, poskytli základní formulaci problému teorie her. Až do této chvíle však bylo obtížné tuto formulaci vyřešit, aniž by to vyžadovalo další předpoklady. Nash musel předpokládat, že hráči byli odděleni, takže pravděpodobnost, že hráč A podnikne akci, je nezávislá na pravděpodobnosti, že hráč B podnikne akci. V tomto článku eliminujeme Nashovy předpoklady, včetně předpokladu, že hráčské strategie jsou běžnými znalostmi, a navrhujeme model, který je plně ekvivalentní obecnému problému VNM. Naše snadno řešitelná formulace eliminuje některé vlastní potíže s přístupem Nash, které často vedly k protichůdným a kontraintuitivním výsledkům, např. K dilematu vězně, kuřecím hrám, Newcombovu paradoxu, lovu jelenů a mnoha dalších her. Například tím, že upustíme od Nashova předpokladu vzájemné nezávislosti v dilematu vězně, náš model prokazuje, že hráči jsou schopni dosáhnout vyšších odměn, a dosáhnout toho, že nemusí hrát společně, ani komunikovat, ale pouze aplikovat Bayesovu teorém, ve stylu (Harsanyi [10]; Kadane a Larkey [11]). Náš přístup rozděluje pravděpodobnostní prostor na dva poloprostory nebo regiony, jejichž relativní velikost závisí na výnosech. Nyní není třeba přesně odhadnout pravděpodobnost, ale pouze určit, v jaké oblasti se nachází. To poskytuje významné výhody, protože pokud je jedna oblast podstatně větší než druhá, okamžitě se získá podstatný přehled o tom, jak hrát hru. Naše obecné řešení, které nesouvisí, řekněme ve smyslu Aumanna [1], obsahuje Nashovy rovnováhy jako konkrétní řešení. Na rozdíl od popisných řešení Nash, naše řešení je předepisující pár racionálně očekávaných čistých strategií, který dává nový základ pro teorii her. Rozšiřujeme náš přístup k obecným hrám M-Person, jak dokládáme ve hře nůžky na rockový papír a problém s vytlačením baru.

Shrnutí výsledků.

Nyní shrneme některé výsledky na základě podrobností a explicitních výplat uvedených níže. Věříme, že tyto výsledky ukazují hodnotu našeho přístupu k výuce a výzkumu, protože výsledky často přinášejí nová řešení.

Koordinační hra: 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.

Rozšiřujeme také náš přístup ke hře M-person a získáváme podobné poznatky. Představujeme například kompletní řešení pro obecné hry 2-osoba a obecné hry 3 x 2.

Očekávaná hypotéza užitečnosti.

Ve hře 2-Person nechte hráče A a B mít strategie 2: A1 nebo A2 pro hráče A a B1 nebo B2 pro hráče B.

Základem očekávané teorie užitku je von Neumann - Morgensternova věta o užitku (von Neumann a Morgenstern [20]): nechť Aij a Bij jsou výplaty hráčům A a B, pokud hráč A hraje Ai a hráč B hraje Bj, pro i , j = 1 nebo 2. Očekávaná hypotéza užitku uvádí, že hráči A a B musí maximalizovat své očekávané výplaty1:

kde pA (Ai a Bj) je pravděpodobnost hráče A, že A hraje Ai a B hraje Bj, a podobně pro hráče B.

Podmíněné pravděpodobnosti[1].

Pro náš přístup jsme pokles Nashův předpoklad, že pravděpodobnosti hráčů jsou vzájemně nezávislé. To umožňuje, aby byl náš problém (1) obecnější a získal více řešení, která uspokojí očekávanou hypotézu užitku.

Nechť EP (A | Ai) a EP (B | Bj) jsou očekávanými výplatami[2],[3] z A a B, vzhledem k tomu, že A hraje Ai a B hraje Bj, pro i, j = 1, 2:

Začněme tím, že dokážeme elementární „Bayesovská“ věta o hrách což demonstruje rovnocennost našeho přístupu k formulaci VNM:

Věta 1[5]. Problémy (3) níže jsou ekvivalentní problémům (1)[6]:

Důkaz. Podle Bayesovy věty

Poté,

Maximální[7] výše uvedené rovnice je pA (A1) = 1 (tj. herní strategie A1), pokud EP (A | A1) ≥ EP (A | A2), nebo pA (A1) = 0 (tj. herní strategie A2), pokud EP ( A | A1) EP (A | A2). (3) tedy platí pro hráče A. Podobný argument platí pro hráče BQED

Regiony VNM.

Definujte oblasti VNM A1 a A2 jako konvexní polytopy:

Jak je ukázáno níže, A by měla hrát strategii A1, pokud očekává, že B bude v oblasti A1. Jinak by A měl hrát A2. Rovnovážná čára

rozděluje pravděpodobnostní prostor do dvou oblastí a poskytuje vizuálně užitečné prostředky pro analýzu situace[8].

Význam regionů: Tyto dva regiony jsou prakticky důležité, protože nyní není nutné přesně odhadnout pravděpodobnost, ale pouze určit, ve kterém ze dvou regionů se nachází. Často se uvidí, že předchozí pravděpodobnost bude pravděpodobně v jednom regionu a identifikace této oblasti jsou dostatečné informace, které by naznačovaly vhodné hraní hry. Předpokládejme například, že oblast A1 je podstatně větší než druhá, takže pravděpodobnost je v této oblasti A1 docela pravděpodobně. To poskytuje přesvědčivé informace, že hráč A bude pravděpodobně hrát A1.

Analogicky pro B:

Oblasti VNM jsou závislé na předchozích pravděpodobnostních distribucích hráčů, často jednoduše nazývaných precedenty (Jaynes [13]; Harsanyi [10]; Kadane a Larkey [11]), což jsou názory hráčů na přesvědčení o distribuci pravděpodobnosti jejich soupeř. [9]

Důsledek 2. Vzhledem k (3), A hraje strategii A1 tehdy a pouze tehdy, pokud očekává, že hráč B bude v oblasti VNM A1. Jinak A hraje strategii A2. Podobně B hraje strategii B1 pouze tehdy, pokud očekává, že hráč A bude v oblasti VNM B1. Jinak, B hraje strategii B2.

Důkaz. EP (A | A1) ≥ EP (A | A2) pouze tehdy, pokud A11 pA (B1 | A1) + A12 pA (B2 | A1) ≥ A21 pA (B1 | A2) + A22 pA (B2 | A2) pouze tehdy, pokud (A11 - A12) pA (B1 | A1) + (A21 - A22) pA (B2 | A2) + A12 - A21 ≥ 0.

Podobně EP (B | B1) ≥ EP (B | B2) pouze tehdy, pokud B11 pB (A1 | B1) + B21 pB (A2 | B1) ≥ B12 pB (A1 | B2)

+ B22 pB (A2 | B2) pouze tehdy, pokud (B11 - B21) pB (A1 | B1) + (B12 - B22) pB (A2 | B2) + B21 - B12 ≥ 0. QED

Z vět Theorem 1 a Corollary 2 pro body v regionech (5) a (7) platí očekávaná hypotéza užitečnosti, tj. Regiony VNM definují obecné řešení hry 2-Person[10].

Nashova rovnováha.

Pokud jsou pravděpodobnosti hráčů vzájemně nezávislé, regiony VNM zjednodušují:

Návrh 3. Předpokládejme, že Nashova rovnováha (p (A1), p (B1)) je ve VNM oblasti Ai a VNM oblasti Bj, pro některé i, j = 1, 2. Poté hráč A bude hrát strategii Ai a hráč B bude hrát strategii

Bj.

Důkaz. Nashův rovnovážný problém je problém (1), kde pA (Ai a Bj) = pB (Ai a Bj) = p (Ai) p (Bj) nebo problém (3), kde pA (Bj | Ai) = p (Bj ) a pB (Ai | Bj) = p (Ai) pro i, j = 1, 2. Corollary 2 tedy platí, kde jsou oblasti VNM definovány pomocí (8), pro pA (B1) = p (B1) a pB (A1) = p (A1). QED

Připomeňme si, že rovnovážné rovnice

oddělte oblasti VNM, čímž získáte obecné řešení pro jakoukoli hru. Stejné rovnovážné rovnice, kde pB (A1) = p (A1) a pA (B1) = p (B1), získají smíšenou Nashovu rovnováhu11, jak je ukázáno v tabulce níže.

Návrh 4. Vzhledem k jakékoli hře A = [[A11, A12], [A21, A22]] a B = [[B11, B12], [B21, B22]], Nashovy rovnováhy pro hru se počítají z příslušného řádku tabulky 112.

Důkaz. Všimněte si, že (i, j) je čistá Nashova rovnováha pouze tehdy, pokud sgn (2i - 1) * (A11 - A21)> 0 a sgn (2j - 1) * (B11 - B12)> 0, pro i, j = 0, 1. S použitím této skutečnosti uvedeme pro každý řádek v tabulce 1 všechny páry (i, j), které jsou čistými Nashovými rovnováhami.

Nakonec, aby dvojice (a, b) definovaná (9) byla smíšená Nashova rovnováha, potřebujeme pouze ukázat, že 0 <a <1 a 0 <b <1. Ale všimněte si, že pro řádky 6, 7, 10 a 11 v tabulce 1 jsou čitatel a jmenovatel a, 1 - a, b nebo 1 - b kladné nebo oba záporné; proto a, 1 - a, b, 1 - b jsou všechny větší než 0. QED

Příklad opakované dominance[13].

Nechť A = [[2, 2], [3, 1]] a B = [[0, 1], [0, 2]]. „Play A1 & B2“ je Nashova rovnováha.

Návrh 5. Při A = [[2, 2], [3, 1]] a B = [[0, 1], [0, 2]], pak hráč A bude hrát A1 a hráč B bude hrát B2.

Důkaz. VNM oblast A1 je: pA (B2 | A2) ≥ 1 / 2 a VNM oblast B2 je: pB (A2 | B2) ≥ -1. Hráč B tedy bude hrát B2. Hráč A také ví, že tomu tak je, a proto pA (B2 | A2) = 1. Protože pA (B2 | A2) = 1 je bod v oblasti VNM A1, hráč A hraje A1. QED

Příklad koordinace.

Nechť A = B = [[2, 0], [0, 1]]. Existují rovnovážné body 3 Nash: „play A1 & B1“, „play A2 & B2“ a „play A1 (nebo B1) s pravděpodobností 1 / 3“. VNM oblast A1 je: 2pA (B1 | A1) ≥ pA (B2 | A2) a VNM oblast B1 je: 2pB (A1 | B1) ≥ pB (A2 | B2). Při vizuální analýze těchto oblastí VNM si A a B pravděpodobně zvolí strategie A1 a B1.

Návrh 6. Vzhledem k tomu, že A = B = [[2, 0], [0, 1]], jsou-li pravděpodobnosti hráčů vzájemně nezávislé, zahrajte první strategii, pokud se domníváte, že pravděpodobnost soupeře hrát svou první strategii je alespoň 1 / 3, jinak hrajte druhou strategii.

Důkaz. VNM oblast A1 je: pA (B1) ≥ 1 / 3 a VNM oblast B1 je: pB (A1) ≥ 1 / 3. QED

Příklad bitvy pohlaví.

Nechť A = [[3, 1], [1, 2]] a B = [[2, 1], [1, 3]]. Existují rovnovážné body 3 Nash: „play A1 & B1“, „play A2 & B2“ a „play A1 s pravděpodobností 2 / 3, hraní B1 s pravděpodobností 1 / 3“. VNM oblast A1 je: 2pA (B1 | A1) ≥ pA (B2 | A2) a VNM oblast B1 je: pB (A1 | B1) ≥ 2pB (A2 | B2). Raději si vybere A1 a B raději vybere B2.

Návrh 7. A = [[3, 1], [1, 2]] a B = [[2, 1], [1, 3]], pokud jsou pravděpodobnosti hráčů vzájemně nezávislé, pak: hrajte A1, pokud pA (B1) ) ≥ 1 / 3, jinak hrát A2; hrát B1, pokud pB (A1) ≥ 2 / 3, jinak hrát B2.

Důkaz. VNM oblast A1 je: pA (B1) ≥ 1 / 3 a VNM oblast B1 je: pB (A1) ≥ 2 / 3. QED

Příklad odpovídajících pencí.

Nechť A = [[1, -1], [-1, 1]] a B = [[-1, 1], [1, -1]]. Tato hra s nulovým součtem má smíšenou Nashovu rovnováhu: „hrajte A1 s pravděpodobností 1 / 2, hrajte B1 s pravděpodobností 1 / 2“.

Návrh 8. Vzhledem k A = [[1, -1], [-1, 1]] a B = [[-1, 1], [1, -1]], pokud jsou pravděpodobnosti hráčů vzájemně nezávislé, pak: hrajte A1 pokud pA (B1) ≥ 1 / 2, hrajte A2; hrát B1, pokud pB (A1) 1 / 2, jinak hrát B2[14].

Důkaz. VNM oblast A1 je: pA (B1) ≥ 1 / 2 a VNM oblast B1 je: pB (A1) 1 / 2. QED

Příklad kuřecí hry (Sugden [19]).

Nechť A = [[0, -1], [1, -10]] a B = [[0, 1], [-1, -10]]. Nashovy rovnováhy jsou „play A1 (swerve) & B2 (go straight)“, „play A2 (go straight) & B1 (swerve)“) a „play A1 (B1) with pravděpodobnost 0.9“.

Návrh 9. Pokud je pravděpodobnost hráčů ve hře kuře vzájemně nezávislá, pak: zatočte, pokud si myslíte, že se soupeř bude potýkat s pravděpodobností nejvýše 90%, jinak jdou rovně.

Důkaz. VNM oblast A1 je: pA (B1) + 11pA (B2) ≥ 2 nebo pA (B1) ≤ 9 / 10. Podobně oblast VNM B1 je: pB (A1) <9 / 10. QED

Všimněte si, že pokud váš soupeř projevuje příliš velké nadšení (alespoň 90%), než aby se mu zatočilo, měli byste jít rovně.

Upřednostňovaný scénář: Hráči se budou více snažit, než se vyrovnat.

Kuřecí scénář: Předpokládejme, že pA (B1) = pB (A1) = 0. Oba hráči očekávají, že druhý hráč půjde rovně. Oba se zamotají.

Katastrofální scénář: Předpokládejme, že pA (B1) = pB (A1) = 1. Oba hráči očekávají, že se druhý hráč otočí. Oba půjdou rovně[15].

Nashova rovnovážná situace: Předpokládejme pA (B1) = 1 - pB (A1) a pB (A1) = 0 nebo 1. Hráč, který očekává, že druhý hráč půjde rovně, se otočí, a hráč, který očekává, že se druhý hráč otočí, půjde rovně.

Příklad závodu se zbraněmi.

V Propozici 9 nechť A = [[0, -x], [1, -10x]], B = [[0, 1], [-y, -10y]] pro x, y ≥ 0. Nechť A1 nebo B1 bude „hledat mír“ a A2 nebo B2 bude „jaderný útok“. Hodnoty x a y označují zásobu zbraní B a A.

Země A usiluje o mír, pokud je pravděpodobnost, že útoky země B budou větší než 1 / (9x + 1); jinak útoky. Křivka pravděpodobnosti pA (B1) = 1 / (9x + 1) rychle klesá, např. PA (B1) = 1 / 2 v x = 1 / 9, ale brzy se dramaticky zplodí: B se musí na začátku rychle skladovat, ale jako křivka zplošťuje, bude mít B jen malý přínos pro skladování zbraní.

A podobně pro zemi B.

Stručně řečeno, každá země původně skladovala zbraně, aby nebyla napadena. Rychle se snižující návratnost zásob zbraní se však projevuje, což otevírá příležitost k hledání mírové smlouvy.

Pro ilustraci zvažte odhadovanou globální zásobu jaderné energie 2018[16] tabulky 2.

Na základě výše uvedených výplat a tabulky 2 by racionální Severní Korea měla usilovat o mírovou dohodu se Spojenými státy a Ruskem.

Skyrms [16]).

Nechť A = [[4, 1], [3, 2]] a B = [[4, 3], [1, 2]]. Nashovy rovnováhy jsou „play A1 (Stag) a B1 (Stag)“, „play A2 (Hare) a B2 (Hare)“ a „play A1 (B1) s pravděpodobností 0.5“.

Návrh 10. Pokud jsou pravděpodobnosti hráčů vzájemně nezávislé, pak v lovu jelenů: lovte jelena, pokud si myslíte, že soupeř bude lovit jelena s pravděpodobností alespoň 50%, jinak loví zajíc.

Důkaz. Oblast VNM A1 je: 3pA (B1) + pA (B2) ≥ 2 nebo pA (B1) ≥ 1 / 2. Podobně oblast VNM B1 je: pB (A1) ≥ 1 / 2. QED

Vězňovo dilema[17].

Nechť A12 <A22 <A11 <A21, a nechť B se rovná transpozici A. Od A11 <A21 a A12 <A22 přináší princip dominance Nashovu rovnováhu, jmenovitě nespolupracující řešení “hrát A2 (defekt) a B2 (vada) “. Ale protože A22 <A11, A a B jsou lepší, pokud oba hrají kooperativní řešení „hrají A1 (ticho) a B1 (ticho)“.

Návrh 11. Pokud je pravděpodobnost hráčů v dilematu vězně vzájemně nezávislá, pak hráči hrají nespolupracovně[18].

Důkaz. Zvažte levou stranu oblasti VNM A1:

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

Pokud A11 - A12 - A21 + A22 ≤ 0, pak (A11 - A12 - A21 + A22) pA(B1) + A12 - A22 ≤ A12 - A22 <0. Na druhou stranu, pokud A11 - A12 - A21 + A22> 0, pak (A11 - A12 - A21 + A22) pA(B1) + A12 - A22 ≤ (A11 - A12 - A21 + A22) + A12 - A22 = A11 - A21 <0. Tedy pro hráče A, VNM region A1 je nulová sada, proto musí hrát strategii 2.

Podobně musí hráč B hrát strategii 2. QED

Propozice 11 jasně ukazuje, že předpoklad nezávislosti nás omezuje na nespolupracující řešení.

Příklad klasického vězeňského dilema.

V dilematu klasického vězně A = [[-1, -3], [0, -2]] a B = [[-1, 0], [-3, -2]].

Návrh 12. V dilematu klasického vězně, pokud jsou předešlé hráče: pA (B1 | A1) + pA (B2 | A2) ≥ 3 / 2, pB (A1 | B1) ≥ 2 / 2 / 3 / 2 / 19 / XNUMX hráči budou hrát kooperativní řešeníXNUMX.

Důkaz. Oblast VNM A1 je: pA (B1 | A1) + pA (B2 | A2) ≥ 3 / 2 a oblast VNM B1 je: pB (A1 | B1) + pB (A2 | XXUM) ≥ XXUMX Z tohoto důvodu musí hráči A a B hrát kooperativní řešení. QED

V Proposition 12 si všimněte vysoké lišty potřebné pro hraní kooperativního řešení. Hráči by se raději rozhodli hrát nespolupracující řešení.

Příklad, kdy přístup Nash neuvažuje o hraní strategie spolupráce.

Zvažte dilema vězně, kde A11 - A12 = A21 - A22, A21 = A11 + ma A22 = A11 - M, kde m> 0 je malý a M> 0 je velmi velký. Například A = [[100, -3], [101, -2]]. Připomeňme si z Propozice 11, že pokud jsou pravděpodobnosti hráčů vzájemně nezávislé, budou hráči hrát nespolupracovně.

Je zjevné, že by bylo hloupé, kdyby hráči ani neuvažovali o hraní strategie 1, protože pokud hráč hraje 2, šance, že druhý hráč také hraje 2, by způsobila významnou ztrátu, tak proč by to riskovali. Je zřejmé, že přístup Nash nezohledňuje hraní na kooperativním řešení, i když je to zřejmé řešení - velmi důležitý bod, například diskuse o rozpadech trhu v obecných modelech ekonomické rovnováhy.

Na druhou stranu, jak ukazuje další návrh, upustíme-li od předpokladu nezávislosti, náš přístup bude hrát spíše kooperativní řešení než nespolupracující řešení.

Černá čára je lhostejná linie pro dilema klasické vězně. Hráč s větší pravděpodobností bude hrát strategii 2, protože je nepravděpodobné, že bude v regionu hrát strategii

1.

Zelená čára je lhostejná čára pro tento případ dilematu vězně: pA (B1 | A1) + pA (B2 | A2) = 1 + m / (M + m). Zde je velikost oblasti pravděpodobnosti pro strategii 1 téměř taková jako pro strategii 2. Náš přístup doporučuje hráčům zvážit strategii hraní 1.

Návrh 13. Dané dilema vězně, kde A11 - A12 = A21 - A22, A21 = A11 + ma A22 = A11 - M, kde m> 0 je malý a M> 0 je velmi velký, hráči A a B budou hrát kooperativní řešení20.

  • Hráči tedy nebudou hrát nespolupracující řešení.
  • V současné době se k dosažení kooperativního řešení přidávají předpoklady, např. Omezená racionalita, neúplné informace (Aumann a Maschler [2]; Acevedo a Krueger [4]; Daley Vzhledem k očekávaným společným pravděpodobnostem pA (Ai a Bj)) A dochází k závěru, že pA (A1 a B1) musí být blízko 1. Je to proto, že A a B pravděpodobně budou hrát strategii 1, kde jejich výplaty jsou poměrně vysoké a pouze m jednotky menší než maximální.

Proto musí být pA (B1 | A1) = pA (A1 a B1) / pA (A1) také blízko 1.

A také dochází k závěru, že pA (A2 a B2) pA (A2 a B1), protože B je vhodnější hrát strategii 2, pokud A hraje strategii 2. Proto pA (B2 | A2) = pA (A2 a B2) / (pA (A2 a B1) + pA (A2 a B2)) 1 / 2. A na základě obr. 1 dochází k závěru, že B je dostatečně uvnitř VNM oblasti A1. Podobně bude B hrát strategii 1. QED

Newcombův paradox jako verze vězeňského dilema.

V proslulém Newcombově paradoxu (Wolpert a Benford [21]) existuje prediktor B, hráč A a box X. Hráč A má možnost vybrat box X nebo box X plus $ 1,000. Než A provede svůj výběr, B předpovídá, co A udělá, a B předpovědi jsou téměř jisté. Pokud B předpovídá, že A vezme pouze kolonku X, pak B vloží do kolonky X $ 1,000,000. V tomto případě, protože v krabici je $ 1,000,000, bude A dostávat $ 1,000,000 nebo $ 1,001,000 v závislosti na tom, zda A vybere kolonku X nebo X plus $ 1,000. Na druhé straně, pokud B předpovídá, že A vezme box X plus $ 1,000, pak B nevloží nic do kolonky X. V tomto případě, v závislosti na svém výběru, A buď obdrží $ 1,000, nebo nic.

Newcombův paradox spočívá v tom, že dvě dokonale racionální analýzy dávají protichůdné odpovědi na optimalizační problém hráče A: podle očekávané užitkové hypotézy by měl hráč A vzít pouze box X, protože očekávaná návratnost přijetí X je mnohem vyšší. Na druhé straně by měl hráč A podle zásady dominance vzít box X plus $ 1,000.

Paradox je nejlépe pochopitelný průchodem v (Wolpert a Benford [21]): „… Newcomb řekl, že vezme jen X; proč bojovat s Bohem podobnou bytostí? Nozick však řekl: „Téměř každému je naprosto jasné a jasné, co by se mělo dělat. Obtížnost spočívá v tom, že tito lidé se problémem téměř rovnoměrně dělí, přičemž velké množství lidí si myslí, že protivník je jen hloupý. “…“.

Wolpert a Benford řeší paradox tím, že ukazují, že Newcombův problém ve skutečnosti představuje dvě různé hry s různými pravděpodobnostními výsledky.

V této části vyřešíme paradox tím, že představíme Newcombův problém jako dilema vězně. Přitom lze řešení problému společnosti Newcomb dosáhnout dvěma způsoby: jako nespolupracující řešení (vezměte box X plus $ 1,000) pomocí principu dominance, nebo jako kooperativní řešení (vezměte pouze box X) pomocí očekávaného hypotéza užitečnosti.

Předpokládejme, že existuje bohatý dobrodruh, který slibuje, že bude financovat matici výplaty pro prediktor B, což přinese následující hru: A = [[$ 1,000,000, 0], [$ 1,001,000, $ 1,000]] a B = [[$ 1,000,000, $ 1,001,000] ], [0, $ 1,000]].

Pokud B předpovídá správně, B dostane to, co dostane hráč A. Ale pokud B předpovídá špatně, B dostane $ 1,001,000 mínus to, co dostane AXXX.

Od Proposition 13 budou hráči A a B hrát v této hře kooperativní.

Pokud je to jako Nash, hráč řeší problém pomocí principu dominance, stejně jako prediktor. Prediktor i hráč budou na nespolupracujícím řešení: vezměte X plus $ 1,000. Pokud hráč vyřeší problém pomocí očekávané užitkové hypotézy, stejně tak prediktor a prediktor i hráč budou v kooperativním řešení: vezměte pouze X. V obou případech je predikce prediktora

a Sadowski [6]) nebo jsou popsány nové metody, např. tit-for-tat, korelované rovnováhy (Axelrod [3]; Aumann [1]).

21 Všimněte si, že tím, že představuje problém Newcomb jako problém PD, prediktor dostane osobní pobídku, která v problému Newcomb chybí.

určitý. Protože hráči z Proposition 13 nebudou hrát nespolupracující řešení, souhlasíme s Newcomb, že spolupráce je zřejmá strategie, kterou je třeba přijmout.

Všimněte si však na obr. 1, region spolupráce je však zanedbatelně menší než region nespolupráce. Není tedy překvapivé, když se lidé rovnoměrně rozdělí, jakou strategii mají přijmout.

Zobecnění vězeňského dilematu na osoby M.

Abychom lépe porozuměli tomu, jak by se řešení Nash mohlo rozpadnout v modelech všeobecné ekonomické rovnováhy, zobecmeme dilema vězně na M-osoby, přičemž každý hráč má strategie 2, pro M 2.

Popíšme hru M-Person prostřednictvím binárních stromů.

Obr. 2 je výplata dilematu vězně pro hráče A. Strom (2, 1) je binární strom s hráčem B (hráč 2) jako rodič a hráč A (hráč 1) jako dítě. Pro získání výplaty pro hráče B jednoduše přepněte role rodiče a dítěte na Strom (1, 2). Připomeňme, že pro vězeňské dilema je A12 <A22 <A11 <A21.

Dále předpokládejme, že Tree (M - 1, M - 2,…, 2, 1) označuje výplatu hráče A za hru (M - 1) -Person, pro M 3. Postavte strom pro výplatu hráče A (M, M - 1,…, 2, 1) pro hru M-Person tím, že necháte strom hráče A (M - 1, M - 2,…, 2, 1) být pod stromy na obou větve mateřského hráče M.

Číselné hodnoty výplaty v pravém pod stromě se předpokládají odlišné od hodnot v levém pod stromě, pokud je vztah A12 <A22 <A11 <A21 zachován všude ve stromu.

Nakonec, vzhledem k stromu (M, M - 1,…, 2, 1) pro hráče A, vytvořte strom (1, M, M - 1,…, 3, 2) pro hráče B (hráč 2) tak, že 1 bude nejvyšší rodič; Strom (1, 2, M, M - 1,…, 4, 3) pro hráče 3 tím, že se 2 stane druhým nejvyšším rodičem,…, Strom (1, 2, 3,…, M - 2, M, M - 1 ) pro hráče M - 1 vytvořením M - 2 třetího nejnižšího dítěte, strom (1, 2, 3, ..., M - 1, M) pro hráče M tím, že z M - 1 učiní druhé nejnižší dítě.

Tím je dokončen popis výplat hráčů za dilematovou hru vězně M-Person, přičemž každý hráč má strategie 2.

Věta 14. Za dilema vězně M. 2, s využitím principu dominance, řešení Nash je pro hráče, aby hráli strategii 2.

Důkaz. Už víme, že věta platí pro M = 2. Předpokládejte indukcí, že věta platí pro M - 1, pro M 3. Ukážme, že věta platí pro M.

Daný strom (M, M - 1,…, 2, 1) pro hráče A, vzpomeňte si, že konstrukcí jsou dílčí stromy na levé a pravé větvi ve tvaru Strom (M - 1, M - 2,…, 2 , 1) pro hráče 1, Tree (M, M - 1,…, 2) pro hráče 2, Tree (2, M, M - 1, ..., 4, 3) pro hráče 3,…, Tree (2,… , M - 2, M, M - 1) pro hráče M - 1. Tyto sub stromy jsou stejné pro hráče 1, 2,…, M - 1, s výjimkou označení na rodičovských uzlech. Všimněte si, že strategie každého hráče 2 dominuje jeho strategii 1 za jakýchkoli podmínek. Indukcí na principu dominance budou hráči 1 až M - 1 hrát strategii 2.

Proto vzhledem k stromu (1, 2,…, M - 1, M) pro hráče M, pokud M hraje 1, je výplata pro hráče M b (druhý pravý uzel stromu), zatímco pokud M hraje 2, výplata pro hráče M je A22 (pravý uzel stromu). Podle principu dominance, protože A12 <A22, bude hráč M hrát také strategii 2. QED

Nyní předpokládejme, že jakákoli výplata typu A11 je mnohem větší než jakákoli výplata typu A22; a že A21 = A11 + m, kde výplaty A11 a A21 jsou v sousedních uzlech.

Je zřejmé, že přístup Nash nezohledňuje hraní na kooperativní řešení „strategie hry 1“, i když je zřejmé, že hrát.

Na základě induktivního argumentu Theorem 14 můžeme také dojít k závěru, že vzhledem k tomu, že dílčí stromy na levé a pravé větvi mají tvar Strom (M - 1, M - 2,…, 2, 1) pro hráče 1, Tree ( M - 1, M - 2,…, 2) pro hráče 2, Tree (2, M, M - 1,…, 4, 3) pro hráče 3,…, Tree (2,…, M - 2, M, M - 1) pro hráče M - 1 indukcí, s využitím očekávané užitkové hypotézy, budou hráči 1 až M - 1 hrát strategii 1, kde je výplata typu A11.

Proto vzhledem k stromu (1, 2,…, M - 1, M) pro hráče M, pokud M hraje 1, je výplata pro hráče M (levý uzel stromu), zatímco pokud M hraje 2, výplata pro hráč M je A21 = A11 + m (druhý levý uzel stromu). Protože A11 <A21, hráč M může být v pokušení hrát strategii 2. Ale proč riskovat strategii hraní 2 pro m jednotky více než A11, když by to mohlo vést k výplatě typu A22, výplata výrazně nižší než A11?

Očekávanou hypotézou užitku musí hráč M také hrát strategii 1.

Obecné hry M-person.

Nakonec zobecňujeme Theorem 1 pro obecné hry M-person.

Nechť jsou M hráči, kde každý hráč i má ni možné strategie pro každý i = 1, 2,…, M. Vzhledem k vektoru strategie (j1, j2,…, jM), nechte výplatu hráči i Aij1j2 ... jM. Nechť xi je smíšená strategie pro hráče i, tj. Strategie xi where Σj xij = 1, xij 0, všichni j, a nechť x = (xi, xi) označují strategie všech hráčů. Nashův problém je:

kde EP (i | xi) je očekávaná návratnost pro hráče, kterému jsem dal xi a kde součet je nad všemi jk a všemi k.

Strategie x * je Nashova rovnováha, pokud xi * je řešením výše uvedeného problému hráče i, vzhledem k xi *.

Pro náš přístup, ať pij1, j2,…, jM být hráčem jsem očekávaná pravděpodobnost, že hráč k hraje jk, pro všechny jk a všechny k. Teorie předpokládané Von Neumann-Morgensternové říká, že cílem hráče i je maximalizovat jeho očekávanou návratnost:

kde součet je nad všemi jk a všemi k.

Definovat

kde -i hraje j-i znamená, že hráč k hraje jk a kde součet je nad všemi jk, pro všechny k i.

Věta 15. Problémy (13) níže jsou ekvivalentní problémům (11):

Důkaz.. Podle definice,

kde součet je nad všemi rk, pro všechny k i.

Jmenovatelem (14) je pravděpodobnost pi (hraji ji). Proto,

Od Σ pi (hraju ji) = 1 a pi (hraji ji) 0 pro všechny ji, to znamená, že hráč hraje strategii [arg maxji EP (i | i hraje ji)]. QED

Metoda pro nalezení nejlepší strategie pro hráče i je následující: Pro jakoukoli dvojici strategií pro hráče i, řekněme strategie r a strategie s, spočítejte lokus bodů, ve kterých jsou očekávané výplaty podmíněné tím, že hráč hrající buď r nebo s, jsou stejné . Toto definuje lhostejný povrch, který rozděluje podmíněný pravděpodobnostní prostor na 2 VNM oblasti. Jedna oblast VNM je označena r, protože zvolená strategie je r, a druhá oblast VNM je označena jako s, protože zvolená strategie je s.

Po výše uvedených výpočtech bude každá oblast VNM označena tolikrát, kolik různých strategií existuje. Pro kteroukoli danou oblast VNM vezměte libovolné dvě z více štítků a jednu z nich odstraňte na základě indiferenčního povrchu vytvořeného touto dvojicí štítků. Proces končí, když má každá oblast VNM pouze jeden štítek.

Obecné hry 2.

Nechte hráče A mít strategie Ai, i = 1, 2,… n1 a hráč B mají strategie Bj, j = 1, 2,… n2. Předpokládejme, že pravděpodobnosti hráčů jsou vzájemně nezávislé. Problém (13) je:

Oblasti VNM jsou tedy definovány konvexními polytopy:

Jak lze pozorovat v (16), nalezení řešení nastaveného na obecnou hru pro 2 je jednoduché. Zvažte například více než dva tisíce let starou hru Rock-Paper-Scissors, kde je Nashova rovnováha: hrát jakoukoli strategii s pravděpodobností 33%:

Strategie A1 nebo B1 (rock) ztrácí na strategii A2 nebo B2 (papír) ztrácí na strategii A3 nebo B3 (nůžky) ztrácí na rock.

Pro hráče A máme obecně, kde 0 pA (Bj) 1,

což se snižuje na

A podobně pro hráče B.

Zdá se, že nová strategie této starověké hry je: zahrajte si rock, pokud si myslíte, že váš soupeř bude hrát papír s pravděpodobností nejvýše 33% a nůžky s pravděpodobností alespoň 33%; hrát papír, pokud si myslíte, že váš soupeř bude hrát nůžky s pravděpodobností maximálně 33% a rock s pravděpodobností alespoň 33%; jinak hrají nůžky22.

Hry 3-osoba, kde má každý člověk strategie 2.

Použijeme Theorem 15 pro nalezení řešení nastaveného na hru 3-osoba, kde každý hráč A, B a C má 2 strategie Ai, Bi, Ci, pro i = 1, 2.

Předpokládejme, že pravděpodobnosti hráčů jsou vzájemně nezávislé. Pro hráče A je rovnice (13) rovna

a podobně pro hráče B a C. Pomocí věty 15 je řešení definováno:

Použijme výše uvedené pro hru Bar-crowding[21]:

Pokud je hráč doma, jeho výplata je 1; pokud je hráč na baru sám, jeho výplata je 0; pokud je hráč u baru s jinou osobou, jeho výplata je 2; jinak, jeho výplata je -1.

Máme: A111 - A211 = -2, A112 - A212 = A121 - A221 = 1, A122 - A222 = -1, tedy VNM region A1 je region -3pA (B1) (B1) (B2) (B1) (C2) - 1 ≥ 1 nebo ekvivalentní oblast[22] pA (B1) ≥ (1 - 2pA (C1)) / (2 - 3pA (C1)). Podobně oblast VNM B1 je oblast pB (A1) ≥ (1 - 2pB (C1)) / (2 - 3pB (C1)) a oblast VNM C1 je oblast pC (B1) ≥ (1 - 2) / (1 - 2pC (A3)). Nashovy rovnováhy jsou p (A) = p (B) = p (C) = 1 a p (A) = p (B) = p (C) = 1 / 1.

Potvrzení.

Rádi bychom poděkovali Al Rothovi a Toddovi Daviesovi za jejich cenné rady a pokyny při přípravě tohoto dokumentu.

Poznámky pod čarou

[1] Pro jednoduchost vycházíme ze společného předpokladu, že užitečnost je lineární funkcí výplaty (Starmer [18]). Maximalizace očekávané užitečnosti je tedy stejná jako maximalizace očekávané návratnosti.

[2] Náš Bayesovský přístup k hrám se liší od předchozích Bayesovských prací (například Acevedo a Krueger [4]; Aumann [1]; Daley a Sadowski [6]; McKelvey a Palfrey [12]; Quattrone a Tversky [15]) v tom, na rozdíl od jiných přístupů, náš přístup utěšuje podmíněné pravděpodobnosti jednoznačně na očekávanou hypotézu užitečnosti, kterou naše řešení vždy splňuje.

[3] Kritik uvádí, že „racionální hráči neberou a neměli by zvažovat podmíněné pravděpodobnosti… Představte si agenta, který ví, že pravděpodobnost deště je s. Zdá se, že vaše „řešení“ je, že agent by si měl vzít deštník, pokud prší, a nechat deštník, pokud neprší “.
Věta 1 ukazuje, že dřívější kritika je neopodstatněná. S ohledem na tuto kritiku nechte EP (agent | přinést deštník) = p a EP (agent | nepřinést deštník) = 1 - p. Naše řešení by pak bylo: přinést deštník, pokud p ≥ 1 / 2; nepřineste deštník, pokud p ≤ 1 / 2.

[4] Podmíněné pravděpodobnosti (2) neporušují princip ve Spohn [17]: „Jakýkoli vhodný kvantitativní kvantitativní rozhodovací model nesmí výslovně ani implicitně obsahovat žádné subjektivní pravděpodobnosti pro činy ...“ Podmíněné pravděpodobnosti hráče jsou subjektivní pravděpodobností pro soupeřovy strategie, nikoli pro své vlastní strategie.

[5] Tato věta bude zobecněna na jednu pro hry M-person.

[6] Mezi hráči není signalizace.

[7] Nezávislé proměnné pA (B1 | A1) a pA (B2 | A2) se předpokládají v problému maximalizace, zjednodušení, které se vyhne problému nekonečného regrese (podobné Nashovu předpokladu, že p (B1) je uveden pro hráče A ve formulaci jeho problému maximalizace).

[8] Nerovnost (5) je (objevené) řešení problému (1) stejným způsobem, že kvadratický vzorec je řešením obecné kvadratické rovnice.

[9] Priority hráče mohou záviset na částečně pozorovatelných náhodných událostech, jako je počasí. Informace o použití turnajů ve hrách s neúplnými informacemi, které hrají bayesovští hráči, viz (Harsanyi [10]).

[10] Toto obecné řešení obsahuje Nashovy rovnováhy jako konkrétní řešení. Na rozdíl od popisných řešení Nash je naše řešení dvojicí předepsaných racionálních očekávání čistých strategií. Navíc, pokud se omylem hráč A nachází v oblasti VNM A1 a hraje A2, Corollary 2 uvádí, že hráč A získá nižší očekávanou návratnost.

[11] Je zajímavé poznamenat, že při smíšené rovnováze Nash závisí strategie hráče na znalosti funkce výplaty druhého hráče.

[12] V tabulce jsou ignorovány nulové značky, protože tyto případy jsou degenerované: hráč si nemůže vybrat mezi dvěma strategiemi. Je také zajímavé poznamenat, že každá Nashova rovnováha se objevuje ve čtyřech řádcích.

[13] Další příklady 3 jsou adaptovány od (Davies [7]) způsobem, který by mohl sloužit jako pedagogická technika pro studenty v teorii her. Tabulka 1 může být použita k rychlému nalezení Nashových rovnováh pro všechny zde uvedené příklady her 2-osoba.

[14] Akce A nemají vliv na výběr akcí B. Je tomu tak proto, že víry A nejsou ve vztahu k vírám B. Na druhé straně, pokud jsou přesvědčení vzájemně korelovány, pak se pravděpodobnost obou hráčů musí rovnat 50%, jinak, pokud řekneme, že pravděpodobnosti hráčů jsou obě> 50%, A ví, že B bude hrát strategii 2 (ocasy), proto hraje strategii 1 (hlavy) nemohou být správným předpisem pro A. Pokud řekněme, pravděpodobnost A je> 50% a pravděpodobnost B je <50%, B ví, že A bude hrát hlavy, a proto nemůže hrát správný předpis pro A. atd. Unikátním řešením je tedy Nashova rovnováha: hrajte náhodně pro oba.

[15] Všimněte si, že pA (B1) = pB (A1) = 0 nebo 1 je scénář rovnováhy: oba hráči se zatočí (nebo oba jdou rovně), pokud oba hráči očekávají, že se druhý hráč vyrovná (nebo zatočí). Naproti tomu p (A1) = p (B1) = 0 nebo 1 nemůže být Nashova rovnováha: pokud B jde rovně (nebo se otáčí), A se otočí (nebo jde rovně).

[16] Zdroje: Asociace pro kontrolu zbraní, Federace amerických vědců, Mezinárodní panel pro štěpné materiály, Ministerstvo obrany USA, Ministerstvo zahraničí USA a Stockholmský mezinárodní institut pro výzkum míru.

[17] Od původního příspěvku Flood a Dresher byly publikovány tisíce článků. Hledání „dilematu vězně“ ve službě Scholar Google přináší od tohoto psaní výsledky 104,000u. Prosím, udělejte (Kuhn [14]).

[18] Hráči tedy nebudou hrát kooperativní řešení.

[19] Pokud váš soupeř hraje náhodně, vaše předchozí hra může být ovlivněna předchozími soupeřovými hrami této hry.

[20] Vzorec lze rozšířit na M-osoby, pro M> 3.

[21] Tato hra je založena na problému El Farol bar (Arthur [5]).

[22] Místem lhostejnosti je kvadratická křivka procházející body (pA (C1), pA (B1)) = (0.5, 0), (0.33, 0.33), (0, 0.5).

Reference

[1] Aumann RJ (1974) Subjektivita a korelace v randomizovaných strategiích. Journal of Mathematical Economics 1: 67-96

[2] Aumann RJ, Maschler M (1995) Opakované hry s neúplnými informacemi. MIT Press, Cambridge Londýn

[3] Axelrod R (1984) Vývoj spolupráce. Základní knihy

[4] Acevedo M, Krueger JI (2005) Důkazní odůvodnění v dilematu vězně. The American Journal of Psychology 118: 431-457

[5] Arthur WB (1994) Induktivní uvažování a ohraničená racionalita. American Economic Review 84: 406-411

[6] Daley B, Sadowski P (2017) Magické myšlení: Výsledek reprezentace. Teoretická ekonomie 12: 909-956 24 Tato hra je založena na problému El Farol bar (Arthur [5]). 25 Místem lhostejnosti je kvadratická křivka procházející body (pA (C1), pA (B1)) = (0.5, 0), (0.33, 0.33), (0, 0.5).

[7] Davies T (2004) Utility Teorie a Teorie her. Poznámky k výuce

[8] Garcia CB, Zangwill WI (2017) Nový přístup k válce nebo míru. Pracovní papír

[9] Garcia CB, Zangwill WI (2018) Dominance, Očekávaná utilita a Vězeňské dilema. Pracovní papír

[10] Harsanyi J (1967) Hry s neúplnými informacemi, které hrají hráči „Bayesian“ I - III. J. Management Science 14 (3): 159-182

[11] Kadane JB, Larkey PD (1982) Subjektivní pravděpodobnost a teorie her. Management Science 28 (2): 113-120

[12] McKelvey RD, Palfrey TR (1995) Rovnováhy kvantové odezvy pro hry s normálními formami. Hry a ekonomické chování 10: 6-38

[13] Jaynes ET (1968) Předchozí pravděpodobnosti. Transakce IEEE ve vědě o systémech a kybernetice 4 (3): 227-241

[14] Kuhn S (2017) vězeňské dilema. Stanfordská encyklopedie filozofie

[15] Quattrone GA, Tversky A (1984) Kauzální versus diagnostické případy: Na sebeklam a na iluzi voliče. Žurnál osobnosti a sociální psychologie 46: 237-248

[16] Skyrms B (2004) Stag Hunt a vývoj sociální struktury. Cambridge University Press, Cambridge

[17] Spohn W (1977), kde Luce a Krantz skutečně zobecňují Savageův rozhodovací model. Erkenntnis 11: 113-134

[18] Starmer C (2000) Vývoj v neočekávané teorii užitečnosti: honba za popisnou teorií volby v riziku. Journal of Economic Literature 38: 332-382

[19] Sugden R (2005) Ekonomika práv, spolupráce a sociální péče. Palgrave MacMillan, edice 2: 132

[20] Von Neumann J, Morgenstern O (1953) Teorie her a ekonomického chování. Princeton University Press, New Jersey

[21] Wolpert DH, Benford G (2011) Lekce Newcombova paradoxu. Synthese 190: 1637-164