Написано от: CB Garcia и WI Zangwill

Преподаватели по наука за управление в училището за бизнес на щанда (и двамата пенсионери)

Ревизиран август 18, 2018 от (Garcia и Zangwill [8, 9]).

Ключови думи: Теория на игрите, дилема на затворника, байесовска, субективна вероятност

абстрактен: Фон Нойман и Моргенстерн (VNM), използвайки очакваната полезна хипотеза, предоставиха фундаменталната формулировка на проблема с теорията на игрите. До този момент обаче тази формулировка беше трудна за разрешаване без налагане на допълнителни предположения. Неш трябваше да приеме, че играчите са отделени, така че вероятността играч А да предприеме действие не зависи от вероятността играч Б да предприеме действие. В този документ елиминираме предположенията на Nash, включително предположението, че стратегиите на играчите са общоизвестни, и създаваме модел, който е напълно еквивалентен на общия проблем с VNM. Нашата лесно разрешима формулировка елиминира някои от присъщите затруднения с подхода на Наш, които често дават противоречиви и противодействащи резултати, например, за дилемата на затворника, играта на пилетата, парадокса на Нюкомб, ловът на елен и много други игри. Например, отпадайки предположението за взаимна независимост на Наш в дилемата на затворника, нашият модел демонстрира, че играчите са в състояние да постигнат превъзходни изплащания и за да постигнат това, не е необходимо да играят съвместно или да общуват, а просто да прилагат теоремата на Байес, в стила на (Harsanyi [10]; Kadane и Larkey [11]). Нашият подход разделя вероятното пространство на две полупространства или региони, чийто относителен размер зависи от изплащанията. Сега не е необходимо да се преценява точно вероятността, а само да се определи в кой регион се намира. Това дава значителни предимства, тъй като, ако един регион е значително по-голям от другия, това веднага дава съществено разбиране за това как се играе играта. Нашето общо решение, което не е свързано, да речем по смисъла на Aumann [1], съдържа равновесията на Наш като конкретни решения. За разлика от описателните решения на Nash, нашето решение е предписваща двойка чисти стратегии за рационални очаквания, което дава нова основа за теорията на игрите. Ние разширяваме подхода си към общите M-Person игри, както илюстрираме в играта рок-хартия-ножици и проблема с препълването на лентата.

Обобщение на резултатите.

Сега обобщаваме някои резултати въз основа на детайлите и изричните изплащания, предоставени по-долу. Вярваме, че тези резултати показват стойността на нашия подход за преподаване и изследване, тъй като резултатите често представят нови решения.

Координационна игра: Предположението на Наш за независимост пропуска превъзходния байесовски подход, който възприемаме. За изплащанията, предоставени по-долу, играйте първата стратегия, ако смятате, че вероятността на противника да играе първата си стратегия е най-малко 1 / 3, иначе играйте втората стратегия. Наш не дава представа за това кога да приложим коя стратегия. Освен това, ако изплащанията се променят, подходът ни предоставя преразгледани вероятности. Битка на половете: Две страни се различават по това къде трябва да отидат, но не им е позволено да общуват. И двете страни получават добро изплащане, ако и двете отидат на един и същ избор, тъй като поне двамата са заедно. Дадена страна ще получи бонус, ако и двамата отидат по избор на тази страна. Нито едно от тях не се получава добре, ако отидат на различни места. Като се имат предвид изплатените суми, представени по-долу, играчът A трябва да играе желаната от него стратегия, ако вярва, че другият играч също ще избере желания избор на A с вероятност поне 33%. За разлика от това, Nash предоставя три равновесия, без каквато и да е представа кои да играят, когато и без анализ на вероятностите. Съвпадение на стотинки: Двама играчи, четни и нечетни, разкриват едновременно стотинка. Ако стотинките съвпадат, Дори пази и двете стотинки; в противен случай Од пази и двете стотинки. Уникалното равновесие на Наш за тази игра с нулева сума е и двамата играчи да играят на случаен принцип. Като се имат предвид изплащанията по-долу, Even трябва да играе глави, ако смята, че Odd ще играе глави с вероятност поне 50%. От друга страна, Odd трябва да играе глави, ако смята, че Even ще играе глави с вероятност най-много 50%. Игра с пиле: Две коли се ускоряват една към друга и са на път да имат катастрофа. Неш предлага едната кола да се завие, а другата да тръгне направо, но предлага малък поглед върху това, който трябва да се завърти. Предвид изплащанията по-долу, подходът ни предлага да се отклоните, ако вярвате, че противникът ще се отклони с вероятност най-много 90%, в противен случай вървете направо. Забележете тук, че и двамата играчи, които завъртат (или и двамата вървят направо), не са равновесие на Неш, но и двамата играчи, които се завъртат (или и двамата вървят направо) в очакването, че опонентът ще тръгне направо (или отклонява се) е сценарий на равновесие. Освен това, ако изплащанията са променени, подходът ни предоставя актуализирани вероятности. Състезание по оръжие: всяка страна първоначално складира оръжия, за да не бъде атакувана. Както е показано по-долу, намаляващата възвръщаемост на оръжията за складиране се материализира, което отваря възможност за мирен договор. Наш не определя възможността за мирния договор. Лов на елен: ловува елен, ако вярвате, че противникът ще ловува елен с вероятност поне 50%, в противен случай ловува зайци. (Чистите равновесии на Наш са както за лов на еленци, така и за двама за лов на зайци). Проблемът на Нюкомб: ако проблемът на Нюкомб се постави като дилема на затворника, до решението на проблема на Нюкомб може да се стигне по два начина: като некооперативното равновесие на Наш, използвайки принципа на доминиране, или като съвместно решение, използвайки очакваната хипотеза за полезност. Игра рок-хартия-ножица: Равновесието на Наш е да играете на 3-матрица на случаен принцип. Това, което изглежда нова стратегия за тази древна игра, е да играете рок, ако вярвате, че опонентът ви ще играе на хартия с вероятност най-много 33% и ножици с вероятност поне 33%; да играете на хартия, ако вярвате, че опонентът ви ще играе ножица с вероятност най-много 33% и рок с вероятност най-малко 33%; друго да играе ножица. (Нашият подход може да ви помогне, ако кажете, че имате данни за предишните пиеси на играта на опонента ви.) В играта за препълване на барове има приятели 3 A, B и C: Всеки, който отиде сам в бара, не получава нищо - ако остане вкъщи е по-добър избор. Ако двама приятели отидат в бара, това е най-добрият вариант. Ако и трите отидат, щангата изхвърля и трите. Равновесията на Наш са всички да останат у дома или всички да играят първата си стратегия с вероятност равна на 33%. Но ако имате някаква представа за приятелите си и можете да прецените байесовските вероятности за тяхното поведение, нашата стратегия може да помогне.

Ние също така разширяваме подхода си към играта на M-person и получаваме подобна информация. Например, ние показваме цялостното решение за общи игри на 2-лице и общи игри на 3 лица x 2 стратегии.

Хипотезата на очакваната полезност.

В играта с 2-Person, нека играчите A и B да имат 2 стратегии: A1 или A2 за играч A и B1 или B2 за играч B.

Основата на очакваната теория на полезността е теоремата за полезността на фон Нойман - Моргенстерн (фон Нойман и Моргенстерн [20]): нека Aij и Bij са изплащанията съответно на играчите A и B, ако играч A играе Ai и играч B играе Bj, за i , j = 1 или 2. Хипотезата на очакваната полезност гласи, че играчите A и B трябва да увеличат максимално очакваните си изплащания1:

където pA (Ai и Bj) е вероятността на играча A, че A играе Ai, а B играе Bj, и подобно на играча B.

Условни вероятности[1].

За нашия подход ние спад Предположението на Неш, че вероятностите на играчите са взаимно независими. Това позволява нашият проблем (1) да бъде по-общ и да получим повече решения, които удовлетворяват очакваната хипотеза за полезност.

Нека EP (A | Ai) и EP (B | Bj) са очакваните изплащания[2],[3] на A и B съответно, като се има предвид, че A играе Ai и B играе Bj, за i, j = 1, 2:

Нека започнем с доказване на елементарна „байесова” теорема за игрите което демонстрира еквивалентността на нашия подход към формулировката на VNM:

Теорема 1[5]. Проблемите (3) по-долу са еквивалентни на проблеми (1)[6]:

Доказателство. По теорема на Байес,

След това,

Максимумът[7] от горното уравнение е pA (A1) = 1 (т.е. стратегия за игра A1), ако EP (A | A1) ≥ EP (A | A2), или pA (A1) = 0 (т.е. стратегия за възпроизвеждане A2), ако EP ( A | A1) EP (A | A2). Следователно (3) важи за играч А. Подобен аргумент има за играч BQED

VNM региони.

Определете VNM регионите A1 и A2 да бъдат изпъкналите политопи:

Както е показано по-долу, A трябва да играе стратегия A1, ако очаква B да бъде в регион A1. В противен случай A трябва да играе A2. Равновесната линия

разделя вероятностното пространство в двата региона и предоставя визуално полезно средство за анализ на ситуацията[8].

Значение на регионите: Двата региона са важни на практика, тъй като сега не е необходимо да се преценява точно вероятността, а само да се определи в кой от двата региона се намира. Често ще се види, че предишната вероятност вероятно е в един регион и идентифицирането на този регион е достатъчна информация, за да подскаже подходящата игра на играта. Да предположим например, че регионът A1 е значително по-голям от другия, така че е много вероятно вероятността да бъде в този регион A1. Това предоставя убедителна информация, че играч A вероятно ще играе A1.

Аналогично за B:

VNM регионите зависят от предишните вероятностни разпределения на играчите, често просто наричани приори (Jaynes [13]; Harsanyi [10]; Kadane и Larkey [11]), които са израз на вярванията на играчите за разпределението на вероятността на противника им. [9]

Следствие 2. Като се има предвид (3), A играе стратегия A1, ако и само ако очаква играч B да бъде в VNM регион A1. Друго, A играе стратегия A2. По същия начин, B играе стратегия B1, ако и само ако очаква играч A да бъде в VNM регион B1. Друго, B играе стратегия B2.

Доказателство. EP (A | A1) ≥ EP (A | A2), ако и само ако A11 pA (B1 | A1) + A12 pA (B2 | A1) ≥ A21 pA (B1 | A2) + A22 pA (B2 | A2), ако и само ако (A11 - A12) pA (B1 | A1) + (A21 - A22) pA (B2 | A2) + A12 - A21 ≥ 0.

По същия начин, EP (B | B1) ≥ EP (B | B2), ако и само ако B11 pB (A1 | B1) + B21 pB (A2 | B1) ≥ B12 pB (A1 | B2)

+ B22 pB (A2 | B2), ако и само ако (B11 - B21) pB (A1 | B1) + (B12 - B22) pB (A2 | B2) + B21 - B12 ≥ 0. QED

От теорема 1 и следствие 2, за точки в регионите (5) и (7), се спазва очакваната хипотеза за полезност, т.е. VNM регионите определят общото решение на играта 2-Person[10].

Равновесие на Наш

Ако вероятностите на играчите са взаимно независими, VNM регионите опростяват до:

Предложение 3. Да предположим, че равновесието на Наш (p (A1), p (B1)) е в VNM регион Ai и VNM регион Bj съответно, за някои i, j = 1, 2. След това, играч А ще играе стратегия Ai, а играч B ще играе стратегия

Bj.

Доказателство. Проблемът за равновесието на Наш е проблем (1), където pA (Ai и Bj) = pB (Ai и Bj) = p (Ai) p (Bj), или проблем (3), където pA (Bj | Ai) = p (Bj ) и pB (Ai | Bj) = p (Ai), за i, j = 1, 2. По този начин, следствието 2 има право, където VNM регионите са дефинирани от (8), за pA (B1) = p (B1) и pB (A1) = p (A1). QED

Спомнете си, че равновесните уравнения

отделете VNM регионите, като по този начин дадете общото решение на всяка игра. Същите тези уравнения на равновесие, където pB (A1) = p (A1) и pA (B1) = p (B1), дават смесеното равновесие на Nash, както показваме в таблицата по-долу.

Предложение 4. Като се има предвид всяка игра A = [[A11, A12], [A21, A22]] и B = [[B11, B12], [B21, B22]], равновесията на Nash за играта се изчисляват от приложимия ред на таблица 112.

Доказателство. Забележете, че (i, j) е чисто равновесие на Неш, ако и само ако sgn (2i - 1) * (A11 - A21)> 0 и sgn (2j - 1) * (B11 - B12)> 0, за i, j = 0, 1. Използвайки този факт, за всеки ред в Таблица 1 изброяваме всички двойки (i, j), които са чиста равновесие на Наш.

И накрая, за двойката (a, b), дефинирана от (9), е смесено равновесие на Наш, трябва само да покажем, че 0 <a <1 и 0 <b <1. Но имайте предвид, че за редовете 6, 7, 10 и 11 от таблица 1, числителят и знаменателят на a, 1 - a, b или 1 - b са и двете положителни или и двете отрицателни; следователно a, 1 - a, b, 1 - b са всички по-големи от 0. QED

Пример за итерационно господство[13].

Нека A = [[2, 2], [3, 1]] и B = [[0, 1], [0, 2]]. „Play A1 & B2“ е равновесието на Неш.

Предложение 5. Като се имат предвид A = [[2, 2], [3, 1]] и B = [[0, 1], [0, 2]], тогава играч A ще играе A1 и играч B ще играе B2.

Доказателство. VNM регион A1 е: pA (B2 | A2) ≥ 1 / 2, а VNM регион B2 е: pB (A2 | B2) ≥ -1. Следователно, играч B ще играе B2. Играч A също знае, че това е така, следователно pA (B2 | A2) = 1. Тъй като pA (B2 | A2) = 1 е точка в VNM регион A1, играч A играе A1. QED

Пример за координация.

Нека A = B = [[2, 0], [0, 1]]. Има 3 Nash равновесни точки: „възпроизвеждане на A1 & B1“, „възпроизвеждане на A2 & B2“ и „възпроизвеждане на A1 (или B1) с вероятност 1 / 3“. VNM регион A1 е: 2pA (B1 | A1) ≥ pA (B2 | A2) и VNM регион B1 е: 2pB (A1 | B1) ≥ pB (A2 | B2). Анализирайки визуално тези VNM региони, A и B вероятно ще избират стратегии съответно A1 и B1.

Предложение 6. Като се има предвид A = B = [[2, 0], [0, 1]], ако вероятностите на играчите са взаимно независими, тогава играйте първата стратегия, ако смятате, че вероятността на противника да играе първата си стратегия е най-малко 1 / 3, иначе играйте втората стратегия.

Доказателство. VNM регион A1 е: pA (B1) ≥ 1 / 3 и VNM регион B1 е: pB (A1) ≥ 1 / 3. QED

Пример за битка на половете.

Нека A = [[3, 1], [1, 2]] и B = [[2, 1], [1, 3]]. Има равновесни точки на 3 Nash: „възпроизвеждане на A1 & B1“, „възпроизвеждане на A2 & B2“ и „възпроизвеждане на A1 с вероятност 2 / 3, възпроизвеждане на B1 с вероятност 1 / 3“. VNM регион A1 е: 2pA (B1 | A1) ≥ pA (B2 | A2) и VNM регион B1 е: pB (A1 | B1) ≥ 2pB (A2 | B2). A по-скоро ще избере A1, а B по-скоро B2.

Предложение 7. Дадени A = [[3, 1], [1, 2]] и B = [[2, 1], [1, 3]], ако вероятностите на играчите са взаимно независими, тогава: играйте A1, ако pA (B1 ) ≥ 1 / 3, иначе играйте A2; възпроизвеждане на B1, ако pB (A1) ≥ 2 / 3, иначе играе B2.

Доказателство. Областта VNM A1 е: pA (B1) ≥ 1 / 3 и VNM регион B1 е: pB (A1) ≥ 2 / 3. QED

Пример за съвпадение на пари.

Нека A = [[1, -1], [-1, 1]] и B = [[-1, 1], [1, -1]]. Тази игра с нулева сума има смесено равновесие на Наш: „играйте A1 с вероятност 1 / 2, играйте B1 с вероятност 1 / 2“.

Предложение 8. Дадени A = [[1, -1], [-1, 1]] и B = [[-1, 1], [1, -1]], ако вероятностите на играчите са взаимно независими, тогава: играйте A1 ако pA (B1) ≥ 1 / 2, иначе играйте A2; пусни B1, ако pB (A1) 1 / 2, иначе играе B2[14].

Доказателство. Регионът на VNM A1 е: pA (B1) ≥ 1 / 2 и VNM регион B1 е: pB (A1) 1 / 2. QED

Пример за игра с пиле (Sugden [19]).

Нека A = [[0, -1], [1, -10]] и B = [[0, 1], [-1, -10]]. Равновесията на Неш са „възпроизвеждане A1 (отклонение) и B2 (отидете направо)“, „възпроизвеждане на A2 (отидете направо) & B1 (поклона)“ и „възпроизвеждане на A1 (B1) с вероятност 0.9“.

Предложение 9. В играта с пилета, ако вероятностите на играчите са взаимно независими, тогава: swerve, ако вярвате, че противникът ще се отклони с вероятност най-много 90%, иначе вървете направо.

Доказателство. Областта VNM A1 е: pA (B1) + 11pA (B2) ≥ 2, или pA (B1) ≤ 9 / 10. По същия начин VNM регионът B1 е: pB (A1) ≤ 9 / 10. QED

Обърнете внимание, че ако опонентът ви проявява прекалено голям ентусиазъм (поне 90%), за да се обърнете, тогава трябва да продължите направо.

Предпочитан сценарий: Играчите са по-склонни да се отклонят, отколкото да тръгнат право.

Пиле сценарий: Да предположим, pA (B1) = pB (A1) = 0. И двамата играчи очакват другият играч да тръгне право. И двете ще се отклонят.

Катастрофен сценарий: Да предположим, pA (B1) = pB (A1) = 1. И двамата играчи очакват другият играч да се отклони. И двете ще тръгнат направо[15].

Сценарий за равновесие на Наш: Да предположим, pA (B1) = 1 - pB (A1), и pB (A1) = 0 или 1. Играчът, който очаква другият играч да тръгне направо, ще се отклони, а играчът, който очаква другият играч да се отклони, ще отиде направо.

Пример за надпревара с оръжие

В предложение 9, нека A = [[0, -x], [1, -10x]], B = [[0, 1], [-y, -10y]], за x, y ≥ 0. Нека A1 или B1 да „търсят мир“, а A2 или B2 да бъдат „ядрена атака“. Стойностите x и y означават запасите от оръжие съответно на B и A.

Страна A търси мир, ако вероятността страната B атаки е по-голяма от 1 / (9x + 1); в противен случай А атаки. Кривата на вероятността pA (B1) = 1 / (9x + 1) спада бързо, например, pA (B1) = 1 / 2 при x = 1 / 9, но скоро драстично се изравнява: B трябва бързо да се складира първоначално, но като кривата изравнява, ще има малка полза за B за складиране на оръжия.

И подобно на страната Б.

В обобщение, всяка страна първоначално складира оръжия, за да не бъде атакувана. Но бързо намаляващата възвръщаемост на складовите оръжия се материализира, отваряйки възможност за търсене на мирен договор.

Като илюстрация, помислете за изчисления на 2018 глобален ядрен запас[16] от Таблица 2.

Въз основа на изплащанията по-горе и таблица 2, една разумна Северна Корея трябва да търси мирен договор със САЩ и Русия.

Skyrms [16]).

Нека A = [[4, 1], [3, 2]] и B = [[4, 3], [1, 2]]. Равновесията на Наш са „игра A1 (Stag) & B1 (Stag)“, „play A2 (Hare) & B2 (Hare)“ и „play A1 (B1) с вероятност 0.5“.

Предложение 10. При лов на естакади, ако вероятностите на играчите са взаимно независими, тогава: ловувайте естакада, ако вярвате, че противникът ще ловува елен с вероятност от поне 50%, в противен случай ще ловува зайци.

Доказателство. Областта VNM A1 е: 3pA (B1) + pA (B2) ≥ 2, или pA (B1) ≥ 1 / 2. По същия начин VNM регионът B1 е: pB (A1) ≥ 1 / 2. QED

Дилема на затворника[17].

Нека A12 <A22 <A11 <A21 и нека B равно на транспонирането на A. Тъй като A11 <A21 и A12 <A22, използването на принципа на доминиране води до равновесие на Неш, а именно некооперативното решение "играе A2 (дефект) и B2 (дефект) ”. Но тъй като A22 <A11, A и B са по-добри, ако и двамата играят на съвместното решение „играят A1 (тишина) и B1 (мълчание)“.

Предложение 11. В дилемата на затворника, ако вероятностите на играчите са взаимно независими, тогава играчите играят некооперативно[18].

Доказателство. Помислете от лявата страна на VNM регион A1:

(A11 - A12 - A21 + A22) стрA(B1) + A12 - A22.

Ако A11 - A12 - A21 + A22 ≤ 0, тогава (A11 - A12 - A21 + A22) pA(B1) + A12 - A22 ≤ A12 - A22 <0. От друга страна, ако A11 - A12 - A21 + A22> 0, тогава (A11 - A12 - A21 + A22) pA(B1) + A12 - A22 ≤ (A11 - A12 - A21 + A22) + A12 - A22 = A11 - A21 <0. По този начин, за всеки предишен играч A, VNM регион A1 е нулевият набор, следователно трябва да играе стратегия 2.

По същия начин, играч B трябва да играе на стратегия 2. QED

Предложението 11 ясно показва, че приемането на независимост ни ограничава до несъдействащото решение.

Пример за дилема на класическия затворник.

В дилемата на класическия затворник, A = [[-1, -3], [0, -2]] и B = [[-1, 0], [-3, -2]].

Предложение 12. В дилемата на класическия затворник, ако приорите на играчите са: pA (B1 | A1) + pA (B2 | A2) ≥ 3 / 2, pB (A1 | B1) + pB (A2 | B2), тогава X играчите ще играят съвместно решение3.

Доказателство. Областта VNM A1 е: pA (B1 | A1) + pA (B2 | A2) ≥ 3 / 2, а VNM регионът B1 е: pB (A1 | B1) + pB (A2 | X2 | X3 | X2 | Следователно, за дадените приори, играчите А и Б трябва да играят кооперативното решение. QED

В Proposition 12 обърнете внимание на високата лента, необходима за игра на кооперативното решение. Играчите предпочитат да изиграят несъдействащото решение.

Инстанция, в която подходът на Наш не успява да разгледа възможността за игра на стратегията за сътрудничество.

Помислете за дилемата на затворника, когато A11 - A12 = A21 - A22, A21 = A11 + m и A22 = A11 - M, където m> 0 е малък и M> 0 е много голям. Например, A = [[100, -3], [101, -2]]. Спомнете си от Proposition 11, че ако вероятностите на играчите са взаимно независими, тогава играчите ще играят не-кооперативно.

Очевидно би било глупаво играчите да не обмислят дори играта на стратегия 1, тъй като ако един играч играе 2, вероятността другият играч също да играе 2 би довел до значителна загуба, така че защо да рискувате. Ясно е, че подходът на Наш не успява да обмисли възпроизвеждането на кооперативното решение, дори когато това е очевидното решение - много важен момент, например, дискусиите за сривовете на пазара в общите модели на икономическо равновесие.

От друга страна, както следващото предложение показва, отпадайки поемането на независимостта, подходът ни ще играе решение за сътрудничество, а не решение за сътрудничество.

Черната линия е линията на безразличие към дилемата на класическия затворник. По-вероятно е даден играч да играе на стратегия 2 поради малко вероятната вероятност да бъде в региона за стратегия за игра

1.

Зелената линия е линията на безразличие за този случай на дилемата на затворника: pA (B1 | A1) + pA (B2 | A2) = 1 + m / (M + m). Тук размерът на вероятностния регион за стратегия 1 е почти този за стратегията 2. Нашият подход съветва играчите да разгледат стратегията за игра 1.

Предложение 13. Предвид дилемата на затворника, където A11 - A12 = A21 - A22, A21 = A11 + m и A22 = A11 - M, където m> 0 е малък и M> 0 е много голям, играчите A и B ще играят съвместното решение20.

  • Следователно играчите няма да играят на кооперативното решение.
  • В момента, за да се постигне решение за сътрудничество, се добавят предположения, например, ограничена рационалност, непълна информация (Aumann и Maschler [2]; Acevedo и Krueger [4]; Дейли Предвид очакваните съвместни вероятности на A pA (Ai и Bj), A заключава, че pA (A1 и B1) трябва да е близо до 1.Това е, защото A и B вероятно играят на стратегия 1, където изплащанията им са доста високи и само m единици по-малко от максималните.

Следователно, pA (B1 | A1) = pA (A1 и B1) / pA (A1) също трябва да е близо до 1.

A също заключава, че pA (A2 и B2) pA (A2 и B1), тъй като B е по-вероятно да играе на стратегия 2, ако A играе стратегия 2. Следователно pA (B2 | A2) = pA (A2 и B2) / (pA (A2 и B1) + pA (A2 и B2)) 1 / 2. A, с помощта на фиг. 1, заключава, че B е достатъчно във VNM регион A1. По подобен начин B ще играе на стратегия 1. QED

Парадоксът на Нюкомб като версия на дилемата на затворника.

В известния парадокс на Newcomb (Wolpert и Benford [21]) има предсказател B, играч A и поле X. Играчът A получава избор да вземе полето X или полето X плюс $ 1,000. Преди A да направи своя избор, B прогнозира какво ще направи A, а прогнозите на B са почти сигурни. Ако B прогнозира, че A ще вземе само поле X, тогава B поставя $ 1,000,000 в поле X. В този случай, тъй като кутията има $ 1,000,000 в нея, A ще получи $ 1,000,000 или $ 1,001,000 в зависимост от това дали A избира поле X или X плюс $ 1,000. От друга страна, ако B прогнозира, че A ще вземе поле X плюс $ 1,000, тогава B не поставя нищо в поле X. В този случай, в зависимост от избора си, A или получава $ 1,000, или нищо.

Парадоксът на Newcomb е, че два съвършено рационални анализа дават противоречиви отговори на проблема с оптимизацията на играча А: при очакваната хипотеза за полезност играчът A трябва да вземе само поле X, тъй като очакваното изплащане на X ще е много по-голямо. От друга страна, според принципа на доминиране, играч A трябва да вземе поле X плюс $ 1,000.

Парадоксът се разбира най-добре от пасаж в (Wolpert and Benford [21]): „… Newcomb каза, че той просто ще вземе X; защо да се борим с богоподобно същество? Нозик каза: „На почти всички е напълно ясно и очевидно какво трябва да се направи. Трудността е, че тези хора изглежда се разделят почти равномерно по проблема, като голям брой смятат, че противниковата половина просто е глупава. “…”.

Волперт и Бенфорд разрешават парадокса, като показват, че проблемът на Newcomb всъщност представлява две различни игри с различни вероятностни резултати.

В този раздел ще разрешим парадокса, като поставим проблема на Нюкомб като дилема на затворника. По този начин решението на проблема на Newcomb може да се намери по два начина: като несъдействащо решение (вземете поле X плюс $ 1,000), използвайки принципа на доминиране, или като решение за сътрудничество (вземете само поле X), използвайки очакваното хипотеза за полезност.

Да предположим, че има богат благодетел, който обещава да финансира матрица на изплащане за предсказател B, като се получи следната игра: A = [[$ 1,000,000, 0], [$ 1,001,000, $ 1,000]] и B = [[$ 1,000,000, $ 1,001,000 ], [0, $ 1,000]].

Ако B прогнозира правилно, B получава това, което играчът получава. Но ако B прогнозира погрешно, B получава $ 1,001,000 минус това, което A получава21.

От Proposition 13, играчите A и B ще играят съвместно в тази игра.

Ако като Nash, играчът решава проблема, използвайки принципа на доминиране, така прави и прогнозата. Както прогнозаторът, така и играчът ще бъдат при несъдействащото решение: вземете X плюс $ 1,000. Ако играчът реши проблема с помощта на очакваната хипотеза за полезност, това прави и предсказателят, и прогнозата, и играчът ще бъдат при съвместното решение: вземете само X. И в двата случая прогнозата на прогнозата е

и Садовски [6]) или са описани нови методи, например, тит-за-тат, корелирано равновесие (Axelrod [3]; Aumann [1]).

21 Обърнете внимание, че поставяйки проблема на Newcomb като проблем на PD, на прогнозата се дава личен стимул, който отсъства в проблема на Newcomb.

сигурен. Тъй като от Proposition 13, играчите няма да играят несъдействащото решение, ние сме съгласни с Newcomb, че сътрудничеството е очевидната стратегия.

Забележка на фиг. 1 обаче регионът за сътрудничество е незначително по-малък от този за несъдействието. Тогава не е изненадващо за нас, ако хората се разделят равномерно по коя стратегия да предприемат.

Обобщение на дилемата на затворника пред М-Лицата.

За да разберем по-добре как решението на Наш може да разруши общите модели на икономическо равновесие, нека да обобщим дилемата на затворника пред M-Persons, като всеки играч има стратегии на 2, за M 2.

Нека опишем играта M-Person чрез двоични дървета.

Фиг. 2 е изплащането на дилемата на затворника за играч А. Дървото (2, 1) е двоичното дърво с играч B (играч 2) като родител и играч A (играч 1) като дете. За да получите изплащането за играч B, просто превключете ролите на родител и дете на Tree (1, 2). Спомнете си, че за дилемата на затворника A12 <A22 <A11 <A21.

На следващо място, да предположим, че Tree (M - 1, M - 2,…, 2, 1) обозначава изплащането на играча A за игра (M - 1) -Person, за M 3. Конструирайте дървото на изплащане на играч A (M, M - 1,…, 2, 1) за игра с M-Person, като оставите дървото на играча A (M - 1, M - 2,…, 2, 1) да бъде под дърветата и на двете клонове на родителя играч М.

Цифровите стойности на изплащането в дясното под дърво се приемат различни от тези в лявото подподно дърво, стига връзката A12 <A22 <A11 <A21 да се поддържа навсякъде в дървото.

И накрая, като се има предвид Tree (M, M - 1,…, 2, 1) за играч A, създайте дърво (1, M, M - 1,…, 3, 2) за играч B (играч 2), като направите 1 най-високия родител; Дърво (1, 2, M, M - 1,…, 4, 3) за играч 3, като направи 2 вторият най-висок родител,…, Дърво (1, 2, 3,…, M - 2, M, M - 1 ) за играч M - 1 като направи M - 2 третото най-ниско дете, Дърво (1, 2, 3,…, M - 1, M) за играч M, като направи M - 1 второто най-ниско дете.

С това завършваме описанието на изплащанията на играчите за дилемата на дилемата на M-Person, като всеки играч има 2 стратегии.

Теорема 14. За дилемата на затворника M-Person, M 2, използвайки принципа на доминиране, решението на Nash е играчите да играят на стратегия 2.

Доказателство. Вече знаем, че теоремата важи за M = 2. Да приемем чрез индукция, че теоремата важи за M - 1, за M 3. Нека покажем, че теоремата важи за М.

Като се има предвид дърво (M, M - 1,…, 2, 1) за играч A, припомнете си, че по конструкция, под-дърветата в лявата и дясната клона са с формата на дърво (M - 1, M - 2,…, 2 , 1) за играч 1, дърво (M, M - 1,…, 2) за играч 2, дърво (2, M, M - 1,…, 4, 3) за играч 3,…, дърво (2,… , M - 2, M, M - 1) за играч M - 1. Тези под дървета са идентични за играчите 1, 2,…, M - 1, с изключение на етикетирането на възлите на родителите. Имайте предвид, че стратегията на всеки играч 2 доминира над стратегията си 1 при всякакви условия. Чрез индукция, използвайки принципа на доминиране, играчите 1 до M - 1 ще играят стратегия 2.

Следователно, като се има предвид Tree (1, 2,…, M - 1, M) за играч M, ако M играе 1, изплащането за играч M е b (вторият най-десен възел на дървото), докато ако M играе 2, изплащането за играч M е A22 (най-десния възел на дървото). По принципа на доминиране, тъй като A12 <A22, играч M също ще играе на стратегия 2. QED

Сега нека предположим, че всяко изплащане от тип A11 е много по-голямо от всяко изплащане от типа A22; и че A21 = A11 + m, където изплащанията A11 и A21 са в съседни възли.

Ясно е, че подходът на Nash не обмисля да играе на кооперативното решение „игра стратегия 1“, дори когато това е очевидното решение.

Следвайки индуктивния аргумент на Теорема 14, можем също да заключим, че тъй като под дърветата в лявата и дясната клона са с формата на Дърво (M - 1, M - 2,…, 2, 1) за играч 1, Tree ( M - 1, M - 2,…, 2) за играч 2, дърво (2, M, M - 1,…, 4, 3) за играч 3,…, Tree (2,…, M - 2, M, M - 1) за играч M - 1, чрез индукция, използвайки очакваната хипотеза за полезност, играчите 1 до M - 1 ще играят стратегия 1, където изплащането е от типа A11.

Следователно, като се има предвид Tree (1, 2, ..., M - 1, M) за играч M, ако M играе 1, изплащането за играч M е a (най-левият възел на дървото), докато ако M играе 2, изплащането за играч M е A21 = A11 + m (вторият най-ляв възел на дървото). Тъй като A11 <A21, играчът M може да се изкуши да играе на стратегия 2. Но защо рискувате да играете стратегия 2 за m единици повече от A11, когато това може да доведе до изплащане от типа A22, изплащане значително по-малко от A11?

Съгласно очакваната хипотеза за полезност, играчът M също трябва да играе на стратегия 1.

Общи игри за M-лице.

И накрая, обобщаваме Theorem 1 за общи игри с M лица.

Нека има M играчи, където всеки играч има никакви възможни стратегии за всеки i = 1, 2, ..., M. Предвид вектора на стратегията (j1, j2, ..., jM), нека изплащането на играча е Aij1j2 ... JM, Нека xi е смесена стратегия за играч i, т.е. стратегия xi къде Σj xij = 1, xij 0, всички j, и x = (xi, xi) обозначават стратегиите на всички играчи. Проблемът на Наш е:

където EP (i | xi) е очакваното изплащане на играча i, дадено xi и където сумирането е над всички jk и всички k.

Стратегия x * е равновесие на Неш, ако xi * е решение на проблема на играча i по-горе, като се има предвид xi *.

За нашия подход нека пиj1, j2, ..., JM бъде очакваната вероятност на играча i, че играч k играе jk, за всички jk и всички k. Теорията на очакваната полезност на Von Neumann-Morgenstern казва, че целта на играча i е да увеличи максимално очакваното си изплащане:

където сумирането е над всички jk и всички k.

Определяне

където -i играе j-i означава, че играч k играе jk и където сумирането е над всички jk, за всички k i.

Теорема 15. Проблемите (13) по-долу са еквивалентни на проблеми (11):

Доказателство., По дефиниция,

където сумирането е над всички rk, за всеки k i.

Знаменателят на (14) е вероятността pi (i играе ji). Следователно,

Тъй като Σ pi (играя ji) = 1 и pi (играя ji) 0 за всички ji, следва, че играчът играе стратегия [arg maxji EP (i | i play ji)]. QED

Метод за намиране на най-добрата стратегия за играч i е следният: За всяка двойка стратегии за играч i, да речем стратегия r и стратегия s, изчислете локуса на точките, при които очакваните изплащания, условни за играча, който играе или r или s, са равни , Това определя повърхността на безразличие, която разделя пространството на условната вероятност на 2 VNM области. Един VNM регион е обозначен като r, защото стратегията на избор е r, а другият VNM регион е обозначен s, защото стратегията на избор е s.

След изчисленията по-горе, всеки VNM регион ще бъде маркиран толкова пъти, колкото има различни двойки стратегии. За всеки даден VNM регион, вземете всеки два от множеството етикети и елиминирайте един от тях въз основа на повърхността на безразличие, създадена от тази двойка етикети. Процесът завършва, когато всеки VNM регион има само един етикет.

Общи игри на 2 лице.

Нека играч A има стратегии Ai, i = 1, 2, ... n1 и играч B имат стратегии Bj, j = 1, 2, ... n2. Да приемем, че вероятностите на играчите са взаимно независими. Проблемът (13) е:

Следователно VNM регионите се дефинират от изпъкнали политопи:

Както може да се забележи в (16), намирането на решението, зададено на обща игра на човек с 2, е ясно. Например, помислете за над две хиляди години игра Rock-Paper-Scissors, където е равновесието на Наш: играйте всяка стратегия с 33% вероятност:

Стратегия A1 или B1 (скала) губи от стратегията A2 или B2 (хартия) губи от стратегията A3 или B3 (ножици) губи да се скали.

За играч А, като цяло имаме, където 0 рА (Bj) 1,

което се свежда до

И подобно на играча Б.

Новата стратегия за тази древна игра изглежда е: играйте рок, ако вярвате, че опонентът ви ще играе на хартия с вероятност най-много 33% и ножици с вероятност най-малко 33%; играйте на хартия, ако вярвате, че опонентът ви ще играе ножица с вероятност най-много 33% и скала с вероятност поне 33%; друго играе ножица22.

Игри за 3 лице, където всеки човек има 2 стратегии.

Нека приложим теорема 15 за намиране на решението, зададено в игра с лице на 3, където всеки играч A, B и C има стратегии 2 съответно Ai, Bi, Ci, за i = 1, 2.

Да приемем, че вероятностите на играчите са взаимно независими. За играч А уравнението (13) е

и подобно за играчи B и C. Използвайки Theorem 15, решението се определя от:

Нека използваме по-горе за играта Bar-crowding[21]:

Ако играчът е у дома, изплащането му е 1; ако играчът е сам на бара, изплащането му е 0; ако играчът е на бара с друг човек, изплащането му е 2; друго, изплащането му е -1.

Имаме: A111 - A211 = -2, A112 - A212 = A121 - A221 = 1, A122 - A222 = -1, следователно VNM регион A1 е областта -3pA (BXXUMUM)) (PXXUMUM)) (C1) - 1 ≥ 2, или еквивалентно региона[22] pA (B1) ≥ (1 - 2pA (C1)) / (2 - 3pA (C1)). По същия начин, VNM регион B1 е регионът pB (A1) ≥ (1 - 2pB (C1)) / (2 - 3pB (C1)) и VNM регион C1 е регионът pC (B1) ≥ (1X) - X (2X) / (1 - 2pC (A3)). Равновесията на Наш са p (A) = p (B) = p (C) = 1 и p (A) = p (B) = p (C) = 1 / 1.

Потвърждение.

Бихме искали да благодарим на Ал Рот и Тод Дейвис за безценните им съвети и насоки при подготовката на настоящия документ.

Бележки под линия

[1] За простота правим общоприетото предположение, че полезността е линейна функция на изплащането (Starmer [18]). Следователно, максимизиране на очакваната полезност е същото като увеличаване на очакваното изплащане.

[2] Нашият байесовски подход за игри се различава от предишния байесовски труд (например Acevedo и Krueger [4]; Aumann [1]; Дейли и Садовски [6]; McKelvey и Palfrey [12]; Quattrone и Tversky [15]) в това, за разлика от другите подходи, нашите подвързани условни вероятности недвусмислено спрямо очакваната хипотеза за полезност, която нашето решение винаги удовлетворява.

[3] Критик заявява, че "рационалните играчи не трябва и не трябва да обмислят условни вероятности ... Представете си агент, който знае, че вероятността за дъжд е p. Вашето „решение“ изглежда е, че агентът трябва да вземе чадър със себе си, ако вали, и да остави чадъра, ако не вали “.
Теорема 1 показва, че бившата критика е неоправдана. По отношение на последната критика, нека EP (агент | донесе чадър) = p, и EP (агент | не носи чадър) = 1 - p. Тогава нашето решение би било: да внесем чадър, ако p ≥ 1 / 2; не носете чадър, ако p ≤ 1 / 2.

[4] Условните вероятности на (2) не нарушават принципа в Спон [17]: „Всеки адекватен модел на количествено решение не трябва да съдържа изрично или косвено някакви субективни вероятности за действия ...“ Условните вероятности на играча са субективни вероятности за противниците стратегии, а не за собствените си стратегии.

[5] Тази теорема ще бъде обобщена до една за M-person игри.

[6] Няма сигнали между плейърите.

[7] Независимите променливи pA (B1 | A1) и pA (B2 | A2) се приемат в задачата за максимализация, опростяване, което избягва проблема с безкрайната регресия (подобно на предположението на Неш, че p (B1) е даден за играч А във формулировката на проблема му за максимализация).

[8] Неравенството (5) е (откритото) решение на проблема (1) по същия начин, по който квадратичната формула е решението на общо квадратно уравнение.

[9] Приорите на играча могат да зависят от частично наблюдавани случайни събития, като например времето. За използването на приори в игри с непълна информация, играна от играчите на Bayes, моля, вижте (Harsanyi [10]).

[10] Това общо решение съдържа равновесията на Наш като конкретни решения. За разлика от описателните Nash решения, нашето решение е двойка предписателни рационални очаквания, чисти стратегии. Освен това, ако по грешка играчът A е в VNM регион A1 и играе A2, следствието 2 заявява, че играчът A ще получи по-ниско очаквано изплащане.

[11] Интересно е да се отбележи, че при смесено равновесие на Nash, стратегията на играча зависи от познаването на функцията за изплащане на другия играч.

[12] Нулевите знаци се игнорират в таблицата, тъй като тези случаи са изродени: играчът не може да избира между двете си стратегии. Също така е интересно да се отбележи, че всяко равновесие на Наш се появява в точно четири реда.

[13] Следващите примери за 3 са адаптирани от (Davies [7]) по начин, който може да служи като педагогическа техника за студентите по теория на игрите. Таблица 1 може да се използва за бързо намиране на равновесието на Наш за всички примери за игра на 2 човек, описани тук.

[14] Действията на A не влияят на избора на действия на B. Това е така, защото вярванията на А са некорелирани с вярванията на Б. От друга страна, ако вярванията са свързани, тогава вероятностите на двамата играчи трябва да са равни на 50%, в противен случай, ако кажем, че вероятностите на играчите са и двете> 50%, А знае, че B ще играе на стратегия 2 (опашки), следователно играе стратегия 1 (heads) не може да бъде правилно предписание за A. Ако кажем, A вероятността е> 50% и B вероятността е <50%, B знае, че A ще играе глави, следователно играещите глави не могат да бъдат правилно предписание за А. и т.н. Следователно уникалното решение е равновесието на Наш: играйте на случаен принцип и за двете.

[15] Обърнете внимание, че pA (B1) = pB (A1) = 0 или 1 е сценарий на равновесие: и двамата играчи се завъртат (или и двамата отиват направо), ако и двамата играчи очакват другият играч да върви право (или да завърти). За разлика от тях, p (A1) = p (B1) = 0 или 1 не може да бъде равновесие на Неш: ако B върви направо (или отклонява се), A ще се завърти (или тръгне направо).

[16] Източници: Асоциация за контрол на оръжията, Федерация на американските учени, Международна група за делими материали, Министерство на отбраната на САЩ, Държавен департамент на САЩ и Международен институт за изследване на мира в Стокхолм.

[17] От оригиналната книга на Flood and Dresher са публикувани хиляди статии по въпроса. Търсенето на „Дилема на затворника“ от Google Учен дава резултати от 104,000 към това писане. Моля, посъветвайте се (Kuhn [14]).

[18] Следователно играчите няма да играят на решението за сътрудничество.

[19] Ако опонентът ви играе неслучайно, вашият предимник може да бъде повлиян от предишните игра на опонента ви в тази игра.

[20] Формулата може да бъде разширена до M-лица, за M> 3.

[21] Тази игра е базирана на проблема с лентата El Farol (Arthur [5]).

[22] Локусът на безразличието е квадратична крива, преминаваща през точките (pA (C1), pA (B1)) = (0.5, 0), (0.33, 0.33), (0, 0.5).

Препратки

[1] Aumann RJ (1974) Субективност и корелация в рандомизирани стратегии. Списание за математическа икономика 1: 67-96

[2] Aumann RJ, Maschler M (1995) Повтарящи се игри с непълна информация. MIT Press, Кеймбридж Лондон

[3] Axelrod R (1984) Еволюцията на сътрудничеството. Основни книги

[4] Acevedo M, Krueger JI (2005) Доказателно разсъждение в дилемата на затворника. Американското списание за психология 118: 431-457

[5] Arthur WB (1994) Индуктивна обосновка и ограничена рационалност. Американски икономически преглед 84: 406-411

[6] Daley B, Sadowski P (2017) Магическо мислене: Резултат от представителството. Теоретична икономика 12: 909-956 24 Тази игра се основава на проблема с барове El Farol (Arthur [5]). 25 Локусът на безразличието е квадратична крива, преминаваща през точките (pA (C1), pA (B1)) = (0.5, 0), (0.33, 0.33), (0, 0.5).

[7] Davies T (2004) Теория на полезността и теорията на игрите. Бележки за лекцията

[8] Garcia CB, Zangwill WI (2017) Нов подход към войната или мира. Работен документ

[9] Garcia CB, Zangwill WI (2018) Доминиране, Очаквана полезност и дилемата на затворника. Работен документ

[10] Harsanyi J (1967) Игри с непълна информация, играна от „Bayesian” Играчи I - III. J. Science Science 14 (3): 159-182

[11] Kadane JB, Larkey PD (1982) Субективна вероятност и теорията на игрите. Наука за управление 28 (2): 113-120

[12] McKelvey RD, Palfrey TR (1995) Quantal Response Equilibria for Normal Form Games. Игри и икономическо поведение 10: 6-38

[13] Jaynes ET (1968) Предварителни вероятности. IEEE транзакции за системна наука и кибернетика 4 (3): 227-241

[14] Дилема на затворника Kuhn S (2017). Станфордската енциклопедия на философията

[15] Quattrone GA, Tversky A (1984) Причинно-следствена диагностична ситуация: върху самозаблудата и върху илюзията на избирателя. Списание за личностна и социална психология 46: 237-248

[16] Skyrms B (2004) Ловът на елен и еволюцията на социалната структура. Cambridge University Press, Cambridge

[17] Spohn W (1977) Където Люси и Кранц наистина обобщават модела на решение на Savage. Erkenntnis 11: 113-134

[18] Starmer C (2000) Развитие в теорията на непредвидената полезност: търсенето на описателна теория за избор с риск. Списание за икономическа литература 38: 332-382

[19] Sugden R (2005) Икономиката на правата, сътрудничеството и благосъстоянието. Palgrave MacMillan, издание 2: 132

[20] Von Neumann J, Morgenstern O (1953) Теория на игрите и икономическото поведение. Princeton University Press, Ню Джърси

[21] Wolpert DH, Benford G (2011) Урокът на парадокса на Newcomb. Синтез 190: 1637-164