Ysgrifennwyd gan: CB Garcia a WI Zangwill

Athrawon Gwyddoniaeth Rheolaeth yn Ysgol Fusnes Booth (y ddau wedi ymddeol)

Awst 18, 2018 diwygiedig o (Garcia a Zangwill [8, 9]).

allweddeiriauTheory theori gêm, cyfyng-gyngor carcharor, baeaidd, tebygolrwydd goddrychol

Crynodeb: Darparodd Von Neumann a Morgenstern (VNM), gan ddefnyddio'r rhagdybiaeth cyfleustodau disgwyliedig, ffurf sylfaenol y broblem theori gêm. Hyd at y pwynt hwn, fodd bynnag, roedd y fformiwleiddiad hwnnw wedi bod yn anodd ei ddatrys heb orfodi rhagdybiaethau ychwanegol. Roedd yn rhaid i Nash dybio bod y chwaraewyr yn cael eu datgysylltu fel bod y tebygolrwydd y bydd chwaraewr A yn gweithredu yn annibynnol ar y tebygolrwydd y bydd chwaraewr B yn gweithredu. Yn y papur hwn rydym yn dileu rhagdybiaethau Nash, gan gynnwys rhagdybiaeth bod strategaethau chwaraewyr yn wybodaeth gyffredin, ac yn gwthio model sy'n gwbl gyfwerth â'r broblem VNM gyffredinol. Mae ein ffurfiad hawdd ei ddatrys yn dileu rhai o'r anawsterau cynhenid ​​gyda dull Nash, a oedd yn aml yn cynhyrchu canlyniadau gwrthgyferbyniol a gwrthgyferbyniol, ee, i gyfyng-gyngor y carcharor, y gêm ieir, paradocs Newcomb, yr helfa carw a llawer o gemau eraill. Er enghraifft, trwy ollwng rhagdybiaeth annibyniaeth Nash yn y cyfyng-gyngor, mae ein model yn dangos bod y chwaraewyr yn gallu cyflawni cyflogau uwch, ac i gyflawni hynny, nid oes angen iddynt chwarae ar y cyd na chyfathrebu, ond dim ond cymhwyso theorem Bayes, yn null (Harsanyi [10]; Kadane a Larkey [11]). Mae ein dull yn rhannu'r gofod tebygolrwydd yn ddau hanner gofod neu ranbarth, y mae eu maint cymharol yn dibynnu ar y taliadau. Nawr, nid oes angen i un amcangyfrif y tebygolrwydd yn union, ond dim ond penderfynu ym mha ranbarth y mae. Mae hyn yn darparu manteision sylweddol oherwydd, os yw un rhanbarth gryn dipyn yn fwy na'r llall, mae hyn yn rhoi mewnwelediad sylweddol ar unwaith i sut i chwarae'r gêm. Mae ein datrysiad cyffredinol, nad yw'n gysylltiedig, dywed yn ystyr Aumann [1], yn cynnwys ecwilibria Nash fel datrysiadau penodol. Mewn cyferbyniad â'r atebion disgrifiadol Nash, mae ein datrysiad yn bâr rhagnodol o strategaethau pur disgwyliadau rhesymegol, gan esgor ar sylfaen newydd ar gyfer theori gêm. Rydym yn ymestyn ein hagwedd at gemau M-Person cyffredinol, fel y dangoswn yn y gêm siswrn papur-roc a'r broblem gorlenwi bar.

Crynodeb o'r Canlyniadau.

Rydym nawr yn crynhoi rhai canlyniadau, yn seiliedig ar y manylion a'r ad-daliadau penodol a ddarperir isod. Credwn fod y canlyniadau hyn yn dangos gwerth ein dull ar gyfer addysgu ac ymchwil gan fod y canlyniadau yn aml yn cyflwyno atebion newydd.

Gêm gydlynu: 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.

Rydym hefyd yn ymestyn ein hagwedd at y gêm M-person ac yn cael mewnwelediadau tebyg. Er enghraifft, rydym yn dangos yr ateb cyflawn ar gyfer gemau 2-person cyffredinol a phersonau cyffredinol 3 x gemau strategaethau 2.

Y Rhagdybiaeth Cyfleustodau Disgwyliedig.

Mewn gêm 2-Person, gadewch i chwaraewyr A a B gael strategaethau 2: A1 neu A2 ar gyfer chwaraewr A, a B1 neu B2 ar gyfer chwaraewr B.

Y sylfaen ar gyfer theori cyfleustodau disgwyliedig yw theorem cyfleustodau von Neumann - Morgenstern (von Neumann a Morgenstern [20]): gadewch i Aij a Bij fod yn daliadau talu i chwaraewyr A a B yn y drefn honno os yw chwaraewr A yn chwarae rhan Ai a chwaraewr B yn chwarae Bj, ar gyfer i , j = 1 neu 2. Mae'r rhagdybiaeth cyfleustodau disgwyliedig yn nodi bod yn rhaid i chwaraewyr A a B wneud y mwyaf o'u cyflogau disgwyliedig1:

lle mae pA (Ai a Bj) yn debygolrwydd chwaraewr A bod A yn chwarae Ai a B yn chwarae Bj, ac yn yr un modd ar gyfer chwaraewr B.

Tebygolrwydd Amodol[1].

Ar gyfer ein hymagwedd, rydym ni gollwng Rhagdybiaeth Nash fod tebygolrwydd chwaraewyr yn annibynnol ar ei gilydd. Mae hyn yn caniatáu i'n problem (1) fod yn fwy cyffredinol a chael mwy o atebion sy'n bodloni'r rhagdybiaeth cyfleustodau disgwyliedig.

Gadewch i EP (A | Ai) ac EP (B | Bj) fod y taliadau disgwyliedig[2],[3] o A a B yn y drefn honno o gofio bod A yn chwarae Ai a B yn chwarae Bj, ar gyfer i, j = 1, 2:

Gadewch inni ddechrau trwy brofi theorem elfennol gemau “Bayesaidd” sy'n dangos cywerthedd ein hymagwedd at lunio VNM:

Theorem 1[5]. Mae'r problemau (3) isod yn gyfwerth â phroblemau (1)[6]:

Prawf. Yn ôl theorem Bayes,

Yna,

Yr uchafswm[7] o'r hafaliad uchod yw pA (A1) = 1 (h.y., strategaeth chwarae A1) os yw EP (A | A1) ≥ EP (A | A2), neu pA (A1) = 0 (h.y., strategaeth chwarae A2) os EP ( A | A1) EP (A | A2). Felly, mae (3) yn dal ar gyfer chwaraewr A. Mae dadl debyg yn bodoli dros chwaraewr BQED

Rhanbarthau VNM.

Diffiniwch y rhanbarthau VNM A1 ac A2 i fod y polytopau convex:

Fel y dangosir isod, dylai A chwarae strategaeth A1 os yw'n disgwyl i B fod yn rhanbarth A1. Fel arall, dylai A chwarae A2. Y llinell ecwilibriwm

yn gwahanu'r gofod tebygolrwydd i'r ddau ranbarth ac yn darparu dull gweledol ddefnyddiol o ddadansoddi'r sefyllfa[8].

Pwysigrwydd y Rhanbarthau: Mae'r ddau ranbarth yn bwysig yn ymarferol, oherwydd nawr nid oes angen i un amcangyfrif y tebygolrwydd yn union, ond dim ond penderfynu pa un o ddau ranbarth y mae ynddo. Yn aml, gwelir bod y tebygolrwydd blaenorol yn debygol o fod mewn un rhanbarth , ac mae adnabod y rhanbarth hwnnw yn wybodaeth ddigonol i awgrymu chwarae priodol y gêm. Er enghraifft, mae'n debyg bod rhanbarth A1 gryn dipyn yn fwy na'r llall, felly mae'r tebygolrwydd yn eithaf tebygol o fod yn y rhanbarth hwnnw A1. Mae hyn yn darparu gwybodaeth gymhellol y bydd chwaraewr A yn debygol o chwarae A1.

Yn analog ar gyfer B:

Mae'r rhanbarthau VNM yn ddibynnol ar ddosbarthiadau tebygolrwydd blaenorol y chwaraewyr, a elwir yn aml yn arweinwyr (Jaynes [13]; Harsanyi [10]; Kadane a Larkey [11]), sef mynegiant credoau chwaraewyr ynghylch dosbarthiad tebygolrwydd eu gwrthwynebydd. [9]

Canlyneb 2. O ystyried (3), mae A yn chwarae strategaeth A1 os a dim ond os yw'n disgwyl i chwaraewr B fod yn rhanbarth VNM A1. Mae Else, A yn chwarae strategaeth A2. Yn yr un modd, mae B yn chwarae strategaeth B1 os a dim ond os yw'n disgwyl i chwaraewr A fod yn rhanbarth VNM B1. Mae Else, B yn chwarae strategaeth B2.

Prawf. EP (A | A1) ≥ EP (A | A2) os a dim ond os A11 pA (B1 | A1) + A12 pA (B2 | A1) ≥ A21 pA (B1 | A2) + A22 pA (B2 | A2) os a dim ond os (A11 - A12) pA (B1 | A1) + (A21 - A22) pA (B2 | A2) + A12 - A21 ≥ 0.

Yn yr un modd, EP (B | B1) ≥ EP (B | B2) os a dim ond os B11 pB (A1 | B1) + B21 pB (A2 | B1) ≥ B12 pB (A1 | B2)

+ B22 pB (A2 | B2) os a dim ond os (B11 - B21) pB (A1 | B1) + (B12 - B22) pB (A2 | B2) + B21 - B12 ≥ 0. QED

O Theorem 1 a Corollary 2, ar gyfer pwyntiau yn y rhanbarthau (5) a (7), mae'r rhagdybiaeth cyfleustodau disgwyliedig yn dal, hy, mae'r rhanbarthau VNM yn diffinio'r datrysiad cyffredinol i'r gêm 2-Person[10].

Ecwilibriwm Nash.

Os yw tebygolrwydd y chwaraewyr yn annibynnol ar ei gilydd, mae'r rhanbarthau VNM yn symleiddio i:

Cynnig 3. Tybiwch fod ecwilibriwm Nash (p (A1), p (B1)) yn rhanbarth VNM rhanbarth Ai a VNM Bj yn y drefn honno, ar gyfer rhai i, j = 1, 2. Yna, bydd chwaraewr A yn chwarae strategaeth Ai a bydd chwaraewr B yn chwarae strategaeth

Bj.

Prawf. Problem ecwilibriwm Nash yw problem (1), lle mae pA (Ai a Bj) = pB (Ai a Bj) = p (Ai) p (Bj), neu broblem (3), lle mae pA (Bj | Ai) = p (Bj ) a pB (Ai | Bj) = p (Ai), ar gyfer i, j = 1, 2. Felly, mae Corollary 2 yn dal, lle mae rhanbarthau VNM wedi'u diffinio gan (8), ar gyfer pA (B1) = p (B1) a pB (A1) = p (A1). QED

Dwyn i gof bod yr hafaliadau ecwilibriwm

gwahanwch y rhanbarthau VNM, a thrwy hynny ildio'r datrysiad cyffredinol i unrhyw gêm. Mae'r un hafaliadau ecwilibriwm hyn, lle mae pB (A1) = p (A1) a pA (B1) = p (B1), yn cynhyrchu'r Nash equilibrium11 cymysg, fel y dangoswn yn y tabl isod.

Cynnig 4. O ystyried unrhyw gêm A = [[A11, A12], [A21, A22]] a B = [[B11, B12], [B21, B22]], cyfrifir ecwilibria Nash ar gyfer y gêm o'r rhes berthnasol yn Nhabl 112.

Prawf. Sylwch fod (i, j) yn gydbwysedd Nash pur os a dim ond os sgn (2i - 1) * (A11 - A21)> 0 a sgn (2j - 1) * (B11 - B12)> 0, ar gyfer i, j = 0, 1. Gan ddefnyddio'r ffaith hon, ar gyfer pob rhes yn Nhabl 1, rydym yn rhestru'r holl barau (i, j) sy'n ecwilibria Nash pur.

Yn olaf, er mwyn i'r pâr (a, b) a ddiffinnir gan (9) fod yn gydbwysedd Nash cymysg, nid oes ond angen i ni ddangos bod 0 <a <1 a 0 <b <1. Ond nodwch, ar gyfer rhesi 6, 7, 10 a 11 yn Nhabl 1, bod rhifiadur ac enwadur a, 1 - a, b neu 1 - b yn gadarnhaol neu'r ddau yn negyddol; felly mae a, 1 - a, b, 1 - b i gyd yn fwy na 0. QED

Enghraifft Dominiwn Iterated[13].

Gadewch i A = [[2, 2], [3, 1]] a B = [[0, 1], [0, 2]]. “Chwarae A1 & B2” yw ecwilibriwm Nash.

Cynnig 5. O ystyried A = [[2, 2], [3, 1]] a B = [[0, 1], [0, 2]], Yna bydd chwaraewr A yn chwarae A1 a bydd chwaraewr B yn chwarae B2.

Prawf. Rhanbarth VNM A1 yw: pA (B2 | A2) ≥ 1 / 2, a rhanbarth VNM B2 yw: pB (A2 | B2) ≥ -1. Felly, bydd chwaraewr B yn chwarae B2. Mae Chwaraewr A hefyd yn gwybod bod hyn yn wir, felly pA (B2 | A2) = 1. Gan fod pA (B2 | A2) = 1 yn bwynt yn rhanbarth VNM A1, mae chwaraewr A yn chwarae A1. QED

Enghraifft Cydlynu.

Gadewch A = B = [[2, 0], [0, 1]]. Mae yna bwyntiau ecwilibriwm 3 Nash: “chwarae A1 & B1”, “chwarae A2 & B2”, a “chwarae A1 (neu B1) gyda thebygolrwydd 1 / 3”. Rhanbarth VNM A1 yw: 2pA (B1 | A1) ≥ pA (B2 | A2) a rhanbarth VNM B1 yw: 2pB (A1 | B1) ≥ pB (A2 | B2). Trwy ddadansoddi'r rhanbarthau VNM hyn yn weledol, mae'n debyg y bydd A a B yn dewis strategaethau A1 a B1 yn y drefn honno.

Cynnig 6. O ystyried A = B = [[2, 0], [0, 1]], os yw tebygolrwydd y chwaraewyr yn annibynnol ar ei gilydd, yna chwaraewch y strategaeth gyntaf os ydych chi'n credu bod tebygolrwydd y gwrthwynebydd o chwarae ei strategaeth gyntaf o leiaf 1 / 3, arall chwarae'r ail strategaeth.

Prawf. Rhanbarth VNM A1 yw: pA (B1) ≥ 1 / 3 a rhanbarth VNM B1 yw: pB (A1) ≥ 1 / 3. QED

Enghraifft Brwydr y Rhywiau.

Gadewch i A = [[3, 1], [1, 2]] a B = [[2, 1], [1, 3]]. Mae yna bwyntiau ecwilibriwm 3 Nash: “chwarae A1 & B1”, “chwarae A2 & B2”, a “chwarae A1 gyda thebygolrwydd 2 / 3, chwarae B1 gyda thebygolrwydd 1 / 3”. Rhanbarth VNM A1 yw: 2pA (B1 | A1) ≥ pA (B2 | A2) a rhanbarth VNM B1 yw: pB (A1 | B1) ≥ 2pB (A2 | B2). Byddai'n well gan A ddewis A1 a byddai'n well gan B ddewis B2.

Cynnig 7. O ystyried A = [[3, 1], [1, 2]] a B = [[2, 1], [1, 3]], os yw tebygolrwydd y chwaraewyr yn annibynnol ar ei gilydd, yna: chwarae A1 os yw pA (B1 ) ≥ 1 / 3, arall chwarae A2; chwarae B1 os pB (A1) ≥ 2 / 3, arall chwarae B2.

Prawf. Rhanbarth VNM A1 yw: pA (B1) ≥ 1 / 3 a rhanbarth VNM B1 yw: pB (A1) ≥ 2 / 3. QED

Enghraifft o Geiniogau Paru.

Gadewch i A = [[1, -1], [-1, 1]] a B = [[-1, 1], [1, -1]]. Mae gan y gêm sero-swm hon gydbwysedd Nash cymysg: “chwaraewch A1 gyda thebygolrwydd 1 / 2, chwarae B1 gyda thebygolrwydd 1 / 2”.

Cynnig 8. O ystyried A = [[1, -1], [-1, 1]] a B = [[-1, 1], [1, -1]], os yw tebygolrwydd y chwaraewyr yn annibynnol ar ei gilydd, yna: chwarae A1 os pA (B1) ≥ 1 / 2, arall chwarae A2; chwarae B1 os pB (A1) 1 / 2, arall chwarae B2[14].

Prawf. Rhanbarth VNM A1 yw: pA (B1) ≥ 1 / 2 a rhanbarth VNM B1 yw: pB (A1) 1 / 2. QED

Enghraifft Gêm Cyw Iâr (Sugden [19]).

Gadewch i A = [[0, -1], [1, -10]] a B = [[0, 1], [-1, -10]]. Y ecwilibria Nash yw “chwarae A1 (gwyro) a B2 (ewch yn syth)”, “chwarae A2 (ewch yn syth) a B1 (gwyro)” a “chwarae A1 (B1) gyda thebygolrwydd 0.9”.

Cynnig 9. Yn y gêm cyw iâr, os yw tebygolrwydd y chwaraewyr yn annibynnol ar ei gilydd, yna: gwyro os ydych chi'n credu y bydd y gwrthwynebydd yn gwyro gyda thebygolrwydd o 90% ar y mwyaf, ewch yn syth.

Prawf. Rhanbarth VNM A1 yw: pA (B1) + 11pA (B2) ≥ 2, neu pA (B1) ≤ 9 / 10. Yn yr un modd, rhanbarth VNM B1 yw: pB (A1) ≤ 9 / 10. QED

Sylwch, os yw'ch gwrthwynebydd yn dangos gormod o frwdfrydedd (o leiaf 90%) i wyro, yna dylech fynd yn syth.

Y senario a ffefrir: Mae'r chwaraewyr yn fwy tebygol o wyro na mynd yn syth.

Senario cyw iâr: Tybiwch pA (B1) = pB (A1) = 0. Mae'r ddau chwaraewr yn disgwyl i'r chwaraewr arall fynd yn syth. Bydd y ddau yn gwyro.

Senario trychineb: Tybiwch pA (B1) = pB (A1) = 1. Mae'r ddau chwaraewr yn disgwyl i'r chwaraewr arall wyro. Bydd y ddau yn mynd yn syth[15].

Senario ecwilibria Nash: Tybiwch pA (B1) = 1 - pB (A1), a pB (A1) = 0 neu 1. Bydd y chwaraewr sy'n disgwyl i'r chwaraewr arall fynd yn syth yn gwyro, a bydd y chwaraewr sy'n disgwyl i'r chwaraewr arall wyro yn mynd yn syth.

Enghraifft Ras Arfau.

Yn Cynnig 9, gadewch A = [[0, -x], [1, -10x]], B = [[0, 1], [-y, -10y]], ar gyfer x, y ≥ 0. Gadewch i A1 neu B1 fod yn “ceisio heddwch” ac A2 neu B2 yn “ymosodiad niwclear”. Mae'r gwerthoedd x ac y yn dynodi pentwr stoc breichiau B ac A yn y drefn honno.

Mae Gwlad A yn ceisio heddwch os yw'r tebygolrwydd y bydd gwlad B yn ymosod yn fwy na 1 / (9x + 1); fel arall A yn ymosod. Mae'r gromlin debygolrwydd pA (B1) = 1 / (9x + 1) yn gostwng yn gyflym, ee, pA (B1) = 1 / 2 yn x = 1 / 9, ond yn fuan yn gwastatáu'n ddramatig: rhaid i B bentyrru'n gyflym i ddechrau, ond wrth i'r gromlin yn gwastatáu, ni fydd fawr o fudd i B am freichiau pentyrru.

Ac yn yr un modd ar gyfer gwlad B.

I grynhoi, mae pob gwlad yn pentyrru breichiau i ddechrau rhag ymosod arni. Ond mae enillion sy'n lleihau'n gyflym ar freichiau pentyrru stoc yn dod i'r fei, gan agor cyfle i geisio cytundeb heddwch.

Fel enghraifft, ystyriwch y pentwr stoc niwclear byd-eang amcangyfrifedig 2018[16] o Dabl 2.

Yn seiliedig ar y taliadau uchod a Thabl 2, dylai Gogledd Corea rhesymol geisio cytundeb heddwch gyda'r Unol Daleithiau a Rwsia.

Skyrms [16]).

Gadewch i A = [[4, 1], [3, 2]] a B = [[4, 3], [1, 2]]. Y ecwilibria Nash yw “chwarae A1 (Stag) a B1 (Stag)”, “chwarae A2 (Ysgyfarnog) a B2 (Ysgyfarnog)” a “chwarae A1 (B1) gyda thebygolrwydd 0.5”.

Cynnig 10. Yn yr helfa carw, os yw tebygolrwydd y chwaraewyr yn annibynnol ar ei gilydd, yna: hela carw os ydych chi'n credu y bydd y gwrthwynebydd yn hela carw gyda thebygolrwydd o 50% o leiaf, fel arall yn hela ysgyfarnog.

Prawf. Rhanbarth VNM A1 yw: 3pA (B1) + pA (B2) ≥ 2, neu pA (B1) ≥ 1 / 2. Yn yr un modd, rhanbarth VNM B1 yw: pB (A1) ≥ 1 / 2. QED

Dilema'r Carcharor[17].

Gadewch i A12 <A22 <A11 <A21, a gadewch i B hafal trawsosod A. Ers A11 <A21 ac A12 <A22, mae defnyddio'r egwyddor goruchafiaeth yn esgor ar gydbwysedd Nash, sef yr ateb anweithredol “chwarae A2 (nam) a B2 (nam) ”. Ond gan fod A22 <A11, A a B yn well eu byd os yw'r ddau ohonyn nhw'n chwarae'r datrysiad cydweithredol “chwarae A1 (distawrwydd) a B1 (distawrwydd)”.

Cynnig 11. Yng nghyfyng-gyngor y carcharor, os yw tebygolrwydd y chwaraewyr yn annibynnol ar ei gilydd, yna mae chwaraewyr yn chwarae'n anweithredol[18].

Prawf. Ystyriwch ochr chwith rhanbarth VNM A1:

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

Os yw A11 - A12 - A21 + A22 ≤ 0, yna (A11 - A12 - A21 + A22) tA(B1) + A12 - A22 ≤ A12 - A22 <0. Ar y llaw arall, os yw A11 - A12 - A21 + A22> 0, yna (A11 - A12 - A21 + A22) tA(B1) + A12 - A22 ≤ (A11 - A12 - A21 + A22) + A12 - A22 = A11 - A21 <0. Felly, ar gyfer unrhyw chwaraewr blaenorol ar gyfer chwaraewr A, rhanbarth VNM A1 yw'r set null, felly mae'n rhaid iddo chwarae strategaeth 2.

Yn yr un modd, rhaid i chwaraewr B chwarae strategaeth 2. QED

Mae Cynnig 11 yn dangos yn glir bod y dybiaeth o annibyniaeth yn ein cyfyngu i'r datrysiad anweithredol.

Enghraifft o Gyfyng-gyngor Carcharorion Clasurol.

Yn nghyfyng-gyngor clasurol y carcharor, A = [[-1, -3], [0, -2]] a B = [[-1, 0], [-3, -2]].

Cynnig 12. Yng nghyfyng-gyngor y carcharor clasurol, os yw arweinwyr y chwaraewyr yn: pA (B1 | A1) + pA (B2 | A2) ≥ 3 / 2, pB (A1 | B1) + pB (A2 | B2) ≥ 3 / X bydd y chwaraewyr yn chwarae'r datrysiad cydweithredol2.

Prawf. Rhanbarth VNM A1 yw: pA (B1 | A1) + pA (B2 | A2) ≥ 3 / 2, a rhanbarth VNM B1 yw: pB (A1 | B1) + pB (A2 | B2 | Felly, ar gyfer yr arweinwyr a roddir, rhaid i chwaraewyr A a B chwarae'r datrysiad cydweithredol. QED

Yn Proposition 12, nodwch y bar uchel sy'n ofynnol ar gyfer chwarae'r datrysiad cydweithredol. Byddai'n well gan y chwaraewyr ddewis chwarae'r datrysiad anweithredol.

Digwyddiad lle nad yw Dull Nash yn Methu Ystyried Chwarae'r Strategaeth Gydweithredol.

Ystyriwch gyfyng-gyngor y carcharor lle mae A11 - A12 = A21 - A22, A21 = A11 + m ac A22 = A11 - M, lle mae m> 0 yn fach a M> 0 yn fawr iawn. Er enghraifft, A = [[100, -3], [101, -2]]. Dwyn i gof o Proposition 11, os yw tebygolrwydd y chwaraewyr yn annibynnol ar ei gilydd, yna bydd chwaraewyr yn chwarae'n anweithredol.

Yn amlwg, byddai'n ffôl i'r chwaraewyr beidio â hyd yn oed ystyried chwarae strategaeth 1 oherwydd pe bai chwaraewr yn chwarae 2, byddai'r siawns y bydd y chwaraewr arall hefyd yn chwarae 2 yn cynhyrchu colled sylweddol, felly pam ei fentro. Yn amlwg, mae dull Nash yn methu ag ystyried chwarae'r datrysiad cydweithredol hyd yn oed pan mai hwn yw'r ateb amlwg i'w chwarae - pwynt pwysig iawn, dyweder, trafodaethau am ddadansoddiadau yn y farchnad mewn modelau ecwilibriwm economaidd cyffredinol.

Ar y llaw arall, fel y dengys y cynnig nesaf, trwy ollwng y rhagdybiaeth o annibyniaeth, bydd ein dull yn chwarae'r datrysiad cydweithredol yn hytrach na'r datrysiad anweithredol.

Y llinell ddu yw'r llinell ddifaterwch ar gyfer cyfyng-gyngor y carcharor clasurol. Mae chwaraewr yn fwy tebygol o chwarae strategaeth 2 oherwydd y tebygolrwydd annhebygol o fod yn y rhanbarth ar gyfer strategaeth chwarae

1.

Y llinell werdd yw'r llinell ddifaterwch ar gyfer yr achos hwn o gyfyng-gyngor y carcharor: pA (B1 | A1) + pA (B2 | A2) = 1 + m / (M + m). Yma, mae maint y rhanbarth tebygolrwydd ar gyfer strategaeth 1 bron yn un ar gyfer strategaeth 2. Ein dull yw cynghori'r chwaraewyr i ystyried chwarae strategaeth 1.

Cynnig 13. O ystyried cyfyng-gyngor carcharor lle mae A11 - A12 = A21 - A22, A21 = A11 + m ac A22 = A11 - M, lle mae m> 0 yn fach a M> 0 yn fawr iawn, bydd chwaraewyr A a B yn chwarae'r datrysiad cydweithredol20.

  • Felly, ni fydd chwaraewyr yn chwarae'r datrysiad anweithredol.
  • Ar hyn o bryd, i gyrraedd yr ateb cydweithredol, ychwanegir rhagdybiaethau, ee rhesymoledd wedi'i ffinio, gwybodaeth anghyflawn (Aumann a Maschler [2]; Acevedo a Krueger [4]; Daley O ystyried tebygolrwyddau cyd-ddisgwyliedig disgwyliedig A pA (Ai a Bj), mae A yn dod i'r casgliad bod Rhaid i pA (A1 a B1) fod yn agos at 1. Mae hynny oherwydd bod A a B yn debygol o chwarae strategaeth 1, lle mae eu cyflogau yn eithaf uchel a dim ond m unedau yn llai na'r mwyafswm.

Felly, rhaid i pA (B1 | A1) = pA (A1 a B1) / pA (A1) hefyd fod yn agos at 1.

Mae A hefyd yn dod i'r casgliad bod pA (A2 a B2) pA (A2 a B1) gan fod B yn debycach i chwarae strategaeth 2 os yw A yn chwarae strategaeth 2. Felly pA (B2 | A2) = pA (A2 a B2) / (pA (A2 a B1) + pA (A2 a B2)) 1 / 2. Daw A i'r casgliad, gan ddefnyddio Ffig. 1, fod B yn ddigonol y tu mewn i ranbarth VNM A1. Yn yr un modd, bydd B yn chwarae strategaeth 1. QED

Paradocs Newcomb fel Fersiwn o Gyfyng-gyngor y Carcharor.

Ym mharadocs enwog Newcomb (Wolpert a Benford [21]), mae rhagfynegydd B, chwaraewr A a blwch X. Rhoddir dewis i'r chwaraewr A gymryd y blwch X neu'r blwch X ynghyd â $ 1,000. Cyn i A wneud ei ddetholiad, mae B yn rhagweld beth fydd A yn ei wneud, ac mae rhagfynegiadau B bron yn sicr. Os yw B yn rhagweld y bydd A yn cymryd blwch X yn unig, yna mae B yn rhoi $ 1,000,000 ym mlwch X. Yn yr achos hwn, gan fod gan y blwch $ 1,000,000 ynddo, bydd A yn derbyn $ 1,000,000 neu $ 1,001,000 yn dibynnu a yw A yn dewis blwch X neu X ynghyd â $ 1,000. Ar y llaw arall, os yw B yn rhagweld y bydd A yn cymryd blwch X ynghyd â $ 1,000, yna nid yw B yn gosod dim ym mlwch X. Yn yr achos hwn, yn dibynnu ar ei ddewis, mae A naill ai'n derbyn $ 1,000 neu ddim byd.

Paradocs Newcomb yw bod dau ddadansoddiad cwbl resymol yn rhoi atebion gwrthgyferbyniol i broblem optimeiddio chwaraewr A: o dan y rhagdybiaeth cyfleustodau disgwyliedig, dylai chwaraewr A gymryd blwch X yn unig, gan fod y tâl disgwyliedig o gymryd X yn llawer uwch. Ar y llaw arall, o dan yr egwyddor goruchafiaeth, dylai chwaraewr A gymryd blwch X ynghyd â $ 1,000.

Y ffordd orau o ddeall y paradocs yw darn yn (Wolpert a Benford [21]): “… dywedodd Newcomb y byddai’n cymryd X yn unig; pam ymladd bod yn debyg i Dduw? Fodd bynnag, dywedodd Nozick, 'I bron pawb, mae'n hollol glir ac amlwg beth ddylid ei wneud. Yr anhawster yw ei bod yn ymddangos bod y bobl hyn yn rhannu bron yn gyfartal ar y broblem, gyda niferoedd mawr yn meddwl mai dim ond bod yn wirion yw'r hanner gwrthwynebol. '… ”.

Mae Wolpert a Benford yn datrys y paradocs trwy ddangos bod problem Newcomb mewn gwirionedd yn cynrychioli dwy gêm wahanol gyda chanlyniadau tebygolrwydd gwahanol.

Yn yr adran hon, byddwn yn datrys y paradocs trwy osod problem Newcomb fel cyfyng-gyngor carcharor. Wrth wneud hynny, gellir dod o hyd i'r ateb i broblem Newcomb mewn dwy ffordd: fel yr ateb anweithredol (cymerwch flwch X ynghyd â $ 1,000) gan ddefnyddio'r egwyddor goruchafiaeth, neu fel yr ateb cydweithredol (cymerwch flwch X yn unig) gan ddefnyddio'r disgwyliedig rhagdybiaeth cyfleustodau.

Tybiwch fod yna gymwynaswr cyfoethog sy'n addo ariannu matrics talu ar gyfer rhagfynegydd B, gan ildio'r gêm ganlynol: A = [[$ 1,000,000, 0], [$ 1,001,000, $ 1,000]] a B = [[$ 1,000,000, $ 1,001,000 ], [0, $ 1,000]].

Os yw B yn darogan yn gywir, mae B yn cael yr hyn y mae chwaraewr A yn ei gael. Ond os yw B yn darogan yn anghywir, mae B yn cael $ 1,001,000 heb yr hyn y mae A yn ei gael21.

O Proposition 13, bydd chwaraewyr A a B yn chwarae ar y cyd yn y gêm hon.

Os fel Nash, mae'r chwaraewr yn datrys y broblem gan ddefnyddio'r egwyddor goruchafiaeth, felly hefyd y rhagfynegydd. Bydd y rhagfynegydd a'r chwaraewr yn y datrysiad anweithredol: cymerwch X ynghyd â $ 1,000. Os yw'r chwaraewr yn datrys y broblem gan ddefnyddio'r rhagdybiaeth cyfleustodau disgwyliedig, felly hefyd y rhagfynegydd, a bydd y rhagfynegydd a'r chwaraewr yn yr ateb cydweithredol: cymerwch X yn unig. Yn y naill achos neu'r llall, rhagfynegiad y rhagfynegydd yw

a disgrifir Sadowski [6]) neu ddulliau newydd, ee tit-for-tat, ecwilibria cydberthynol (Axelrod [3]; Aumann [1]).

21 Sylwch, trwy osod problem Newcomb fel problem PD, bod y rhagfynegydd yn cael cymhelliant personol sy'n absennol yn broblem Newcomb.

sicr. Ers o Proposition 13, ni fydd chwaraewyr yn chwarae'r datrysiad anweithredol, rydym yn cytuno â Newcomb mai cydweithredu yw'r strategaeth amlwg i'w chymryd.

Sylwch yn Ffig. 1, fodd bynnag, mae'r rhanbarth ar gyfer cydweithredu yn esgeulus yn llai na'r rhanbarth ar gyfer peidio â chydweithredu. Yna nid yw'n syndod i ni os yw pobl yn rhannu'n gyfartal ar ba strategaeth i'w chymryd.

Cyffredinoliad o Gyfyng-gyngor y Carcharor i M-Bobl.

Er mwyn deall yn well sut y gallai datrysiad Nash ddadelfennu mewn modelau ecwilibriwm economaidd cyffredinol, gadewch inni gyffredinoli cyfyng-gyngor y carcharor i M-Persons, gyda phob chwaraewr â strategaethau 2, ar gyfer M 2.

Gadewch inni ddisgrifio'r gêm M-Person trwy goed deuaidd.

Ffig. 2 yw ad-daliad cyfyng-gyngor y carcharor ar gyfer chwaraewr A. Tree (2, 1) yw'r goeden ddeuaidd gyda chwaraewr B (chwaraewr 2) fel rhiant, a chwaraewr A (chwaraewr 1) yn blentyn. I gael y tâl ar gyfer chwaraewr B, dim ond newid rolau rhiant a phlentyn i Tree (1, 2). Dwyn i gof hynny ar gyfer cyfyng-gyngor y carcharor, A12 <A22 <A11 <A21.

Nesaf, mae'n debyg bod Tree (M - 1, M - 2,…, 2, 1) yn dynodi ad-daliad chwaraewr A ar gyfer gêm (M - 1) -Person, ar gyfer M 3. Llunio Coeden ad-dalu chwaraewr A (M, M - 1,…, 2, 1) ar gyfer gêm M-Person trwy adael i Goeden chwaraewr A (M - 1, M - 2,…, 2, 1) fod yr is-goed ar y ddau canghennau rhiant-chwaraewr M.

Tybir bod gwerthoedd rhifiadol y payoff ar yr is-goeden dde yn wahanol i'r rhai ar yr is-goeden chwith, cyhyd â bod y berthynas A12 <A22 <A11 <A21 yn cael ei chynnal ym mhobman yn y goeden.

Yn olaf, o ystyried Tree (M, M - 1,…, 2, 1) ar gyfer chwaraewr A, crëwch Tree (1, M, M - 1,…, 3, 2) ar gyfer chwaraewr B (chwaraewr 2) trwy wneud 1 yr uchaf rhiant; Coeden (1, 2, M, M - 1,…, 4, 3) ar gyfer chwaraewr 3 trwy wneud 2 yr ail riant uchaf,…, Tree (1, 2, 3,…, M - 2, M, M - 1 ) ar gyfer chwaraewr M - 1 trwy wneud M - 2 y trydydd plentyn isaf, Tree (1, 2, 3,…, M - 1, M) ar gyfer chwaraewr M trwy wneud M - 1 yr ail blentyn isaf.

Mae hyn yn cwblhau'r disgrifiad o daliadau talu chwaraewyr ar gyfer gêm cyfyng-gyngor carcharor M-Person, gyda strategaethau 2 ar bob chwaraewr.

Theorem 14. Ar gyfer cyfyng-gyngor carcharor M-Person, M. 2, gan ddefnyddio'r egwyddor goruchafiaeth, datrysiad Nash yw i'r chwaraewyr chwarae strategaeth 2.

Prawf. Rydym eisoes yn gwybod bod y theorem yn dal ar gyfer M = 2. Tybiwch trwy anwythiad bod y theorem yn dal ar gyfer M - 1, ar gyfer M. 3. Gadewch inni ddangos bod y theorem yn dal am M.

O ystyried Coeden (M, M - 1,…, 2, 1) ar gyfer chwaraewr A, cofiwch, wrth adeiladu, fod yr is-goed ar y canghennau chwith a dde o'r ffurf Tree (M - 1, M - 2,…, 2 , 1) ar gyfer chwaraewr 1, Tree (M, M - 1,…, 2) ar gyfer chwaraewr 2, Tree (2, M, M - 1,…, 4, 3) ar gyfer chwaraewr 3,…, Tree (2,… , M - 2, M, M - 1) ar gyfer chwaraewr M - 1. Mae'r is-goed hyn yn union yr un fath ar gyfer chwaraewyr 1, 2,…, M - 1, heblaw am y labelu ar nodau'r rhieni. Sylwch fod strategaeth 2 pob chwaraewr yn dominyddu ei strategaeth 1 o dan unrhyw amod. Trwy sefydlu, gan ddefnyddio'r egwyddor goruchafiaeth, bydd chwaraewyr 1 i M - 1 yn chwarae strategaeth 2.

Felly, o ystyried Tree (1, 2,…, M - 1, M) ar gyfer chwaraewr M, os yw M yn chwarae 1, y tâl ar gyfer chwaraewr M yw b (ail nod mwyaf cywir y goeden) ond os yw M yn chwarae 2, y payoff ar gyfer chwaraewr M yw A22 (nod mwyaf cywir y goeden). Yn ôl yr egwyddor goruchafiaeth, ers A12 <A22, bydd chwaraewr M hefyd yn chwarae strategaeth 2. QED

Nawr mae'n debyg bod unrhyw ad-daliad o'r math A11 yn llawer mwy nag unrhyw ad-daliad o'r math A22; a bod A21 = A11 + m, lle mae ad-daliadau A11 ac A21 mewn nodau cyfagos.

Yn amlwg, mae dull Nash yn methu ag ystyried chwarae'r datrysiad cydweithredol “strategaeth chwarae 1” hyd yn oed pan mai dyna'r ateb amlwg i'w chwarae.

Yn dilyn dadl anwythol Theorem 14, gallwn hefyd ddod i'r casgliad, gan fod yr is-goed ar y canghennau chwith a dde o'r ffurf Tree (M - 1, M - 2,…, 2, 1) ar gyfer chwaraewr 1, Tree ( M - 1, M - 2,…, 2) ar gyfer chwaraewr 2, Tree (2, M, M - 1,…, 4, 3) ar gyfer chwaraewr 3,…, Tree (2,…, M - 2, M, M - 1) ar gyfer chwaraewr M - 1, trwy anwythiad, gan ddefnyddio'r rhagdybiaeth cyfleustodau disgwyliedig, bydd chwaraewyr 1 i M - 1 yn chwarae strategaeth 1 lle mae'r tâl o'r math A11.

Felly, o ystyried Tree (1, 2,…, M - 1, M) ar gyfer chwaraewr M, os yw M yn chwarae 1, y tâl ar gyfer chwaraewr M yw (nod mwyaf chwith y goeden) ond os yw M yn chwarae 2, y tâl ar gyfer chwaraewr M yw A21 = A11 + m (ail nod mwyaf chwith y goeden). Ers A11 <A21, gellir temtio chwaraewr M i chwarae strategaeth 2. Ond pam mentro chwarae strategaeth 2 ar gyfer m unedau yn fwy nag A11, pan allai arwain at ad-daliad o'r math A22, ad-daliad sy'n sylweddol is nag A11?

Yn ôl y rhagdybiaeth cyfleustodau disgwyliedig, rhaid i chwaraewr M hefyd chwarae strategaeth 1.

Gemau Cyffredinol M-person.

Yn olaf, rydym yn cyffredinoli Theorem 1 ar gyfer gemau M-person cyffredinol.

Gadewch fod chwaraewyr M, lle mae gan bob chwaraewr ni strategaethau posibl ar gyfer pob i = 1, 2,…, M. O ystyried fector y strategaeth (j1, j2,…, jM), gadewch i'r tâl i chwaraewr fod yn Aij1j2… jM. Gadewch i xi fod yn strategaeth gymysg ar gyfer chwaraewr i, hy, strategaeth xi lle Σj xij = 1, xij Mae 0, pob j, a gadewch i x = (xi, xi) ddynodi strategaethau pob chwaraewr. Problem Nash yw:

lle EP (i | xi) yw'r ad-daliad disgwyliedig i chwaraewr i a roddir xi a lle mae'r crynhoad dros bob jk a phob k.

Mae strategaeth x * yn gydbwysedd Nash os yw xi * yn ddatrysiad i broblem chwaraewr i uchod, o ystyried xi *.

Ar gyfer ein hymagwedd, gadewch pij1, j2,…, jM fod yn debygolrwydd disgwyliedig chwaraewr i fod chwaraewr k yn chwarae jk, ar gyfer pob jk a phob k. Mae theori cyfleustodau disgwyliedig Von Neumann-Morgenstern yn dweud mai nod chwaraewr i yw cynyddu ei gyflog disgwyliedig i'r eithaf:

lle mae'r crynhoad dros bob jk a phob k.

Diffiniwch

lle -i yn chwarae j-i yn golygu bod chwaraewr k yn chwarae jk a lle mae'r crynhoad dros bob jk, i bawb k i.

Theorem 15. Mae'r problemau (13) isod yn gyfwerth â phroblemau (11):

Prawf.. Trwy ddiffiniad,

lle mae'r crynhoad dros bob rk, ar gyfer unrhyw k i.

Enwadur (14) yw'r tebygolrwydd pi (i chwarae ji). Felly,

Ers Σ pi (dwi'n chwarae ji) = 1 a pi (i yn chwarae ji) 0 i bawb ji, mae'n dilyn bod chwaraewr i yn chwarae strategaeth [arg maxji EP (i | i yn chwarae ji)]. QED

Mae dull ar gyfer dod o hyd i'r strategaeth orau ar gyfer chwaraewr i fel a ganlyn: Ar gyfer unrhyw bâr o strategaethau ar gyfer chwaraewr i, dywedwch strategaeth r a strategaeth s, cyfrifwch locws y pwyntiau lle mae taliadau disgwyliedig disgwyliedig yn amodol ar chwaraewr i chwarae naill ai r neu s yn gyfartal . Mae hyn yn diffinio arwyneb difaterwch sy'n rhannu'r gofod tebygolrwydd amodol yn rhanbarthau 2 VNM. Mae un rhanbarth VNM wedi'i labelu r oherwydd bod y strategaeth o ddewis yn r, ac mae'r rhanbarth VNM arall wedi'i labelu s oherwydd bod y strategaeth o ddewis yn s.

Ar ôl y cyfrifiadau uchod, bydd pob rhanbarth VNM wedi cael ei labelu gymaint o weithiau ag y mae parau penodol o strategaethau. Ar gyfer unrhyw ranbarth VNM penodol, cymerwch unrhyw ddau o'r labeli lluosog a dileu un ohonynt yn seiliedig ar yr arwyneb difaterwch a grëwyd gan y pâr hwn o labeli. Daw'r broses i ben pan mai dim ond un label sydd gan bob rhanbarth VNM.

Gemau Cyffredinol 2-person.

Gadewch i chwaraewr A gael strategaethau Ai, i = 1, 2,… mae gan n1 a chwaraewr B strategaethau Bj, j = 1, 2,… n2. Tybiwch fod tebygolrwydd y chwaraewyr yn annibynnol ar ei gilydd. Problem (13) yw:

Felly, mae'r rhanbarthau VNM wedi'u diffinio gan polytopau convex:

Fel y gwelir yn (16), mae dod o hyd i'r ateb wedi'i osod i gêm gyffredinol 2-person yn syml. Er enghraifft, ystyriwch y gêm Rock-Paper-Scissors dros ddwy fil o flynyddoedd oed, lle mae ecwilibriwm Nash: chwarae unrhyw strategaeth gyda thebygolrwydd 33%:

Mae strategaeth A1 neu B1 (craig) yn colli i strategaeth A2 neu B2 (papur) yn colli i strategaeth A3 neu B3 (siswrn) yn colli i graig.

Ar gyfer chwaraewr A, yn gyffredinol mae gennym ni, lle 0 pA (Bj) 1,

sy'n lleihau i

Ac yn yr un modd i chwaraewr B.

Yr hyn sy'n ymddangos yn strategaeth newydd ar gyfer y gêm hynafol hon yw: chwarae roc os ydych chi'n credu y bydd eich gwrthwynebydd yn chwarae papur gyda thebygolrwydd o 33% ar y mwyaf a siswrn gyda thebygolrwydd o 33% o leiaf; papur chwarae os ydych chi'n credu y bydd eich gwrthwynebydd yn chwarae siswrn gyda thebygolrwydd o 33% ar y mwyaf ac yn siglo gyda thebygolrwydd o 33% o leiaf; arall chwarae siswrn22.

Gemau 3-person Lle Mae gan Bob Unig Strategaethau 2.

Gadewch inni gymhwyso Theorem 15 ar gyfer dod o hyd i'r datrysiad wedi'i osod i gêm 3-person, lle mae gan bob chwaraewr A, B, a C strategaethau 2 Ai, Bi, Ci, ar gyfer i = 1, 2 yn y drefn honno.

Tybiwch fod tebygolrwydd y chwaraewyr yn annibynnol ar ei gilydd. Ar gyfer chwaraewr A, hafaliad (13) yw

ac yn yr un modd ar gyfer chwaraewyr B a C. Gan ddefnyddio Theorem 15, diffinnir yr ateb gan:

Gadewch i ni ddefnyddio'r uchod ar gyfer y gêm gorlenwi Bar[21]:

Os yw'r chwaraewr gartref, ei daliad yw 1; os yw'r chwaraewr ar ei ben ei hun wrth y bar, ei daliad yw 0; os yw'r chwaraewr wrth y bar gyda pherson arall, ei daliad yw 2; arall, ei gyflog yw -1.

Mae gennym ni: A111 - A211 = -2, A112 - A212 = A121 - A221 = 1, A122 - A222 = -1, felly rhanbarth VNM A1 yw'r rhanbarth -3pA (B1XXXXXXX (C1) - 2 ≥ 1, neu yn yr un modd y rhanbarth[22] pA (B1) ≥ (1 - 2pA (C1)) / (2 - 3pA (C1)). Yn yr un modd, rhanbarth VNM B1 yw'r rhanbarth pB (A1) ≥ (1 - 2pB (C1)) / (2 - 3pB (C1)) a rhanbarth VNM C1 yw'r rhanbarth pC (B1) ≥ (1 - 2) / (1 - 2pC (A3)). Y ecwilibria Nash yw p (A) = p (B) = p (C) = 1 a p (A) = p (B) = p (C) = 1 / 1.

Cydnabyddiaeth.

Hoffem ddiolch i Al Roth a Todd Davies am eu cyngor a'u harweiniad amhrisiadwy wrth baratoi'r papur hwn.

Troednodiadau

[1] Er symlrwydd, rydym yn cymryd yn ganiataol bod swyddogaeth yn swyddogaeth linellol y payoff (Starmer [18]). Felly, mae sicrhau'r cyfleustodau disgwyliedig mwyaf yr un peth â sicrhau'r tâl disgwyliedig mwyaf posibl.

[2] Mae ein dull Bayesaidd ar gyfer gemau yn wahanol i waith blaenorol Bayesaidd (er enghraifft, Acevedo a Krueger [4]; Aumann [1]; Daley a Sadowski [6]; McKelvey a Palfrey [12]; Quattrone a Tversky [15]) yn hynny o beth, yn wahanol i'r dulliau eraill, mae ein dull yn clymu tebygolrwyddau amodol yn ddigamsyniol â'r rhagdybiaeth cyfleustodau disgwyliedig, y mae ein datrysiad bob amser yn ei fodloni.

[3] Mae beirniad yn nodi “nid yw ac ni ddylai chwaraewyr rhesymegol ystyried tebygolrwyddau amodol ... Dychmygwch asiant sy'n gwybod bod tebygolrwydd glaw yn t. Ymddengys mai eich 'datrysiad' yw y dylai'r asiant fynd ag ymbarél gydag ef os yw'n bwrw glaw a gadael yr ymbarél os nad yw'n bwrw glaw ”.
Mae Theorem 1 yn dangos bod y feirniadaeth flaenorol yn ddiangen. O ran y feirniadaeth olaf, gadewch i EP (asiant | ddod ag ymbarél) = p, ac EP (asiant | peidiwch â dod ag ymbarél) = 1 - t. Ein datrysiad wedyn fyddai: dod ag ymbarél os yw p ≥ 1 / 2; peidiwch â dod ag ymbarél os yw p ≤ 1 / 2.

[4] Nid yw tebygolrwyddau amodol (2) yn torri'r egwyddor yn Spohn [17]: “Rhaid i unrhyw fodel penderfyniad meintiol digonol beidio â chynnwys unrhyw debygolrwydd goddrychol am weithredoedd yn benodol nac yn ymhlyg ...” Mae tebygolrwyddau amodol chwaraewr yn debygolrwydd goddrychol ar gyfer gwrthwynebwyr. strategaethau, nid ar gyfer ei strategaethau ei hun.

[5] Bydd y theorem hon yn cael ei gyffredinoli i un ar gyfer gemau M-person.

[6] Nid oes unrhyw signalau rhwng y chwaraewyr.

[7] Tybir bod y newidynnau annibynnol pA (B1 | A1) a pA (B2 | A2) yn cael eu rhoi yn y broblem uchafu, symleiddio sy'n osgoi problem atchweliad anfeidrol (tebyg i dybiaeth Nash bod p (B1) yn cael ei roi ar gyfer chwaraewr A wrth lunio ei broblem uchafu).

[8] Anghydraddoldeb (5) yw'r datrysiad (a ddarganfuwyd) i'r broblem (1) yn yr un modd â'r fformiwla gwadratig yw'r datrysiad i hafaliad cwadratig cyffredinol.

[9] Efallai y bydd arweinwyr y chwaraewr yn dibynnu ar ddigwyddiadau ar hap y gellir eu gweld yn rhannol, fel y tywydd. Ar gyfer defnyddio priors mewn gemau gyda gwybodaeth anghyflawn a chwaraeir gan chwaraewyr Bayesaidd, cyfeiriwch at (Harsanyi [10]).

[10] Mae'r datrysiad cyffredinol hwn yn cynnwys ecwilibria Nash fel datrysiadau penodol. Mewn cyferbyniad â'r atebion disgrifiadol Nash, mae ein datrysiad yn bâr o strategaethau pur rhagnodol-ddisgwyliadau rhesymol. Ar ben hynny, os yw chwaraewr A yn rhanbarth VNM A1 ac yn chwarae A2, mae Corollary 2 yn nodi y bydd chwaraewr A yn cael ad-daliad disgwyliedig is.

[11] Mae'n ddiddorol nodi, mewn ecwilibriwm cymysg Nash, bod strategaeth chwaraewr yn dibynnu ar wybod swyddogaeth ad-daliad y chwaraewr arall.

[12] Anwybyddir dim arwyddion yn y tabl, gan fod yr achosion hyn yn dirywio: ni all chwaraewr ddewis rhwng ei ddwy strategaeth. Hefyd, mae'n ddiddorol nodi bod pob ecwilibriwm Nash yn ymddangos mewn pedair rhes yn union.

[13] Mae'r enghreifftiau 3 nesaf wedi'u haddasu o (Davies [7]) mewn modd a allai fod yn dechneg addysgeg i fyfyrwyr mewn theori gêm. Gellir defnyddio Tabl 1 i ddod o hyd i ecwilibria Nash yn gyflym ar gyfer yr holl enghreifftiau gêm 2-person a ddisgrifir yma.

[14] Nid yw gweithredoedd A yn effeithio ar ddewis B o gamau gweithredu. Mae hyn oherwydd bod credoau A heb eu cysylltu â chredoau B. Ar y llaw arall, os oes cydberthynas rhwng credoau, yna mae'n rhaid i debygolrwydd y ddau chwaraewr fod yn hafal i 50%, fel arall, os dywedwch fod tebygolrwydd y chwaraewyr ill dau> 50%, mae A yn gwybod y bydd B yn chwarae strategaeth 2 (cynffonau), ac felly'n chwarae strategaeth 1 ni all (pennau) fod yn bresgripsiwn cywir ar gyfer A. Os dywedwch, tebygolrwydd A yw> 50% a thebygolrwydd B yw <50%, mae B yn gwybod y bydd A yn chwarae pennau, felly ni all pennau chwarae fod yn bresgripsiwn cywir ar gyfer A. Etc. datrysiad unigryw felly yw ecwilibriwm Nash: chwarae ar hap i'r ddau.

[15] Sylwch fod pA (B1) = pB (A1) = 0 neu 1 yn senario ecwilibriwm: mae'r ddau chwaraewr yn gwyro (neu'r ddau yn mynd yn syth) os yw'r ddau chwaraewr yn disgwyl i'r chwaraewr arall fynd yn syth (neu wyro). Mewn cyferbyniad, ni all p (A1) = p (B1) = 0 neu 1 fod yn gydbwysedd Nash: os aiff B yn syth (neu wyro), bydd A yn gwyro (neu'n mynd yn syth).

[16] Ffynonellau: Cymdeithas Rheoli Arfau, Ffederasiwn Gwyddonwyr America, Panel Rhyngwladol ar Ddeunyddiau Ymneilltuol, Adran Amddiffyn yr UD, Adran Wladwriaeth yr UD a Sefydliad Ymchwil Heddwch Rhyngwladol Stockholm.

[17] Ers papur gwreiddiol Flood a Dresher, mae miloedd o erthyglau wedi'u cyhoeddi yn ei gylch. Mae chwiliad Google Scholar am “gyfyng-gyngor carcharor” yn esgor ar ganlyniadau 104,000 o'r ysgrifen hon. Rhowch (Kuhn [14]).

[18] Felly, ni fydd chwaraewyr yn chwarae'r datrysiad cydweithredol.

[19] Os yw'ch gwrthwynebydd yn chwarae ar hap, mae'n bosibl y bydd dramâu blaenorol eich gwrthwynebydd o'r gêm hon yn dylanwadu ar eich blaen.

[20] Gellir ymestyn y fformiwla i M-bersonau, ar gyfer M> 3.

[21] Mae'r gêm hon yn seiliedig ar broblem bar El Farol (Arthur [5]).

[22] Mae locws difaterwch yn gromlin gwadratig sy'n pasio trwy'r pwyntiau (pA (C1), pA (B1)) = (0.5, 0), (0.33, 0.33), (0, 0.5).

cyfeiriadau

[1] Aumann RJ (1974) Goddrychedd a Chydberthynas mewn Strategaethau ar Hap. Cyfnodolyn Economeg Mathemategol 1: 67-96

[2] Aumann RJ, Maschler M (1995) Gemau Ailadroddwyd gyda Gwybodaeth Anghyflawn. MIT Press, Caergrawnt Llundain

[3] Axelrod R (1984) Esblygiad Cydweithrediad. Llyfrau Sylfaenol

[4] Acevedo M, Krueger JI (2005) Rhesymu Tystiolaethol yn Gyfyng-gyngor y Carcharor. The American Journal of Psychology 118: 431-457

[5] Arthur WB (1994) Rhesymu Cynhenid ​​a Rhesymoldeb Ffiniol. Adolygiad Economaidd America 84: 406-411

[6] Daley B, Sadowski P (2017) Meddwl Hudol: Canlyniad Cynrychiolaeth. Economeg Ddamcaniaethol 12: 909-956 24 Mae'r gêm hon yn seiliedig ar broblem bar El Farol (Arthur [5]). 25 Mae locws difaterwch yn gromlin gwadratig sy'n mynd trwy'r pwyntiau (pA (C1), pA (B1)) = (0.5, 0), (0.33, 0.33), (0, 0.5).

[7] Theori Cyfleustodau a Theori Gêm Davies T (2004). Nodiadau Darlith

[8] Garcia CB, Zangwill WI (2017) Ymagwedd Newydd at Ryfel neu Heddwch. Papur gwaith

[9] Garcia CB, Zangwill WI (2018) Dominance, Utility Utility a Dilema'r Carcharor. Papur gwaith

[10] Gemau Harsanyi J (1967) Gyda Gwybodaeth Anghyflawn wedi'i Chwarae gan Chwaraewyr “Bayesaidd” I - III. J. Gwyddoniaeth Rheolaeth 14 (3): 159-182

[11] Kadane JB, Tebygolrwydd Goddrychol Larkey PD (1982) a Theori Gemau. Gwyddoniaeth Rheolaeth 28 (2): 113-120

[12] McKelvey RD, Palfrey TR (1995) Ecwilibria Ymateb Meintiol ar gyfer Gemau Ffurf Arferol. Gemau ac Ymddygiad Economaidd 10: 6-38

[13] Tebygolrwydd Blaenorol Jaynes ET (1968). Trafodion IEEE ar Wyddoniaeth Systemau a Seiberneteg 4 (3): 227-241

[14] Kuhn S (2017) Dilema'r Carcharor. Gwyddoniadur Athroniaeth Stanford

[15] Quattrone GA, Tversky A (1984) Achosion Diagnostig Achosol: Ar Hunan-dwyll ac ar Dwyll y Pleidiwr. Cyfnodolyn Personoliaeth a Seicoleg Gymdeithasol 46: 237-248

[16] Skyrms B (2004) Helfa'r Stag ac Esblygiad Strwythur Cymdeithasol. Gwasg Prifysgol Caergrawnt, Caergrawnt

[17] Spohn W (1977) Lle mae Luce a Krantz yn Gwireddu Model Penderfyniad Savage mewn gwirionedd. Erkenntnis 11: 113-134

[18] Starmer C (2000) Datblygiadau mewn theori cyfleustodau na ddisgwylir: yr helfa am theori ddisgrifiadol o ddewis o dan risg. Cyfnodolyn Llenyddiaeth Economaidd 38: 332-382

[19] Sugden R (2005) Economeg Hawliau, Cydweithrediad a Lles. Palgrave MacMillan, rhifyn 2: 132

[20] Von Neumann J, Morgenstern O (1953) Theori Gemau ac Ymddygiad Economaidd. Gwasg Prifysgol Princeton, New Jersey

[21] Wolpert DH, Benford G (2011) Gwers Paradocs Newcomb. Synthese 190: 1637-164