Gry niekooperacyjne w postaci strategicznej.pdf

Rozdział1

Gryniekooperacyjnewpostaci

strategicznej

1.1Grydwuosoboweosumiezerowej

Wi¦kszo±¢teoriimatematycznychpowstaładoopisupewnychkonkretnychelementówrze-

czywisto±ciinieinaczejjestzteori¡gier.J¡stworzonodlaopisusytuacjikonﬂiktowychi

sposobówznichwychodzenia,b¡d¹przezwspółzawodnictwo,b¡d¹przezkooperacj¦.Oczy-

wi±ciewzało»eniutakateoriapowinnadawa¢odpowied¹napytanie:jakwdanejsytuacji

ludziepost¡pi¡–niestety,jakwka»dejteorii,teoriagiermaswojezało»enia,wktórelu-

dzie,głupi,niechc¡si¦wpasowa¢.Wniosekztegotaki,»eteoriagierniejestnajlepszym

narz¦dziemprzewidywaniaprzyszło±ci–dotegowci¡»najlepszajestszklanakula–mo»e

namnatomiastda¢odpowied¹napytanie,jakpowinnipost¡pi¢,je±libylibyracjonalni.I

odparusłównatemattego,jakopisa¢sytuacj¦konﬂiktu,oraztego,cob¦dziemyrozumie¢

podpoj¦ciemracjonalno±ci,zaczniemy.

Zastanowimysi¦nadtymnaprostymprzykładziesytuacji,wktórejmamydwóchpo-

dejmuj¡cychdecyzjeiichinteresys¡całkowicieprzeciwstawne,wi¦cniemamowyoja-

kiejkolwiekkooperacji,idzi¦kitemumo»nawmiar¦jasnowyekstrahowa¢istot¦tego,jakie

działaniemo»emyrozumie¢jakoracjonalne.Wi¦kszo±¢przykładów,któreb¦d¡si¦pojawia-

łynatymwykładzie,b¦dziejakim±uproszczeniemsytuacjiz»yciawzi¦tych,ewentualnie

b¦dzieopisywałojakie±zjawiskaekonomiczne–tyle»etambardzotrudnoosytuacje,w

którychinteresyposzczególnychstrons¡całkowicieprzeciwstawne–st¡dprzykładb¦dzie

zdziedziny„gierwojennych”,czyliwpraktycetakiejzabawyw»ołnierzykidladu»ych

chłopców.

Przykład: Rozwa»amynast¦puj¡c¡sytuacj¦:dwóchdowódcówarmiiprzeciwnychpa«stw

–AiBwalczyodwaforty(miasta)natereniepa«stwaA,ka»dymaprzytymdodyspozycji

podwaoddziały.Zadaniemka»degozdowódcówjestrozmieszczenieswoichoddziałów

wposzczególnychfortach(ewent.jakoatakuj¡cychposzczególneforty)–generałarmii

Awtensposób,»ebyjaknajwi¦cejfortówpozostałowr¦kachpa«stwaA,generałB–

tak,»ebyprzej¡¢jaknajwi¦cejfortów.Wiedz¡przytym,»earmiaposiadaj¡canadanym

odcinkuprzewa»aj¡c¡sił¦napewnobitw¦odanyfortwygra,aje±lisiłys¡równe,toz

prawdopodobie«stwem 1 2 wygrajeden,izprawdopodobie«stwem 1 2 drugi.Je±liodanyfort

nietoczysi¦walka,tozostajeonwewładaniupa«stwaA.Takabardzoprostagra.

Wnaturalnysposóbmo»emytoopisa¢tak,»ewypiszemywszystkiemo»liwedecyzje

jednegogracza,wszystkiemo»liwedecyzjedrugiego,iwtabelcezapiszemy,cosi¦wdanym

przypadkudzieje:

20 1102

20fort1zpr.0 . 5zdobytyprzezB,fort2zostajewA ... ...

11 ...

... ...

02 ...

... ...

2011 02

20 − 0 . 5 − 1 − 1

11 − 1 − 1 − 1

02 − 1 − 1 − 0 . 5

Iwtensposóbdostali±mynaturalnyopisgry–przypomocyzbiorówstrategiidost¦p-

nychposzczególnymgraczomorazmacierzytego,cowypłacadrugigraczpierwszemuw

zale»no±ciodtego,jakiestrategiestosuj¡.Ogólnie:

Deﬁnicja1.1 Gr¡dwuosobow¡osumiezerowejnazwiemytrójk¦( X,Y,u ),gdzie: X –

zbiórstrategiigracza1., Y –zbiórstrategiigracza2., u : X × Y ! R –ograniczonafunkcja

wypłaty.Grarozgrywanajestwnast¦puj¡cysposób:graczeniezale»nieodsiebiewybieraj¡

x 2 X oraz y 2 Y ,nast¦pniegracz2.płacigraczowi1.kwot¦ u ( x,y ).

Drugimproblemem,którypostawili±my,byłoto,cob¦dzieuwa»anezaracjonalnew

grze.Wró¢mydonaszegoprzykładuizastanówmysi¦,jakpost¡pi¡gracze,idlaczego?

20 11 02

! 20 − 0 . 5 − 1 − 1

lub 11 − 1 − 1 − 1

! 02 − 1 − 1 − 0 . 5

Drugigracz(generałB)wybieradrug¡kolumn¦,bowtedypowinienzdoby¢jedenfort

niezale»nieodtego,cozrobipierwszy(generałA).GenerałAnatomiastwybierzejedn¡z

mo»liwo±ciprzyktórychmo»eco±zyska¢,czyli1.lub3.wiersz.

Natejpodstawiemo»emyzapisa¢,»ezaracjonalneb¦dziemyuwa»a¢takiezachowania

jak:

1.Maksymalizowaniewłasnejwypłaty

2.Unikaniesytuacji,wktórychmo»emywi¦cejstraci¢,je±liprzeciwnikzagradlanas

niekorzystnie

3.Odrzucaniedecyzji,odktórychmamylepsze

Zgodnieztymizasadami(przynajmniejzdwomapierwszymi)gracz1.b¦dziesi¦starał

wybra¢tak¡strategi¦,»ebyzmaksymalizowa¢swoj¡wypłat¦przyzało»eniu,»eprzeciw-

nikb¦dziesi¦starałmujaknajbardziejzaszkodzi¢.Podobnie–gracz2.b¦dziewybierał

tak,»ebywypłaci¢graczowi1.jaknajmniej,zakładaj¡c,»etenb¦dziegrałwnajbardziej

dlasiebiekorzystnysposób.Patrz¡cnaprzykład,widzimy,»egraczewła±nietakrobi¡.

Spróbujmytoterazsformalizowa¢.

Terazcozinformacji,którezawarli±mywtabelcejestistotne-nacob¦d¡zwraca¢

uwag¦podejmuj¡cydecyzje?Nato,ilu»ołnierzypoległo,dostałosi¦doniewoli,który

oddziałwygrał,aktóryprzegrał–nie!Istotnyjesttylkoefektko«cowy,czylito,ilefortów

zdobyto,i(ewentualnie),czyefekt(pozytywny)operacjijestpewny,czytylkozpewnym

prawdopodobie«stwem.Wtakimraziepoodrzuceniunadmiarowejinformacjidostajemy

takiopisgry:

Deﬁnicja1.2 Warto±¢,któr¡gracz1.mo»esobiezapewni¢,nazywanawarto±ci¡doln¡

gry,jestrówna

y 2 Y u ( x,y ) .

Warto±¢najmniejszejstratyponiesionejprzezgracza2.,któr¡mo»esobiezapewni¢,nazy-

wanajestwarto±ci¡górn¡gryijestrówna

v =sup

x 2 X

inf

y 2 Y sup

x 2 X

u ( x,y ) .

Mo»naudowodni¢(imytopoka»emyna¢wiczeniach),»e v ¬ v .Wnaszymprzykładzie

mamyrówno±¢.Aleczyzawszejestrówno±¢?Nie.Np.wgrzez X = Y = { 1 , 2 } oraz

(

1 gdy x = y

− 1gdy x 6 = y , v = − 1,a v =1.

Czymsi¦zatemró»ni¡dwapodaneprzeznasprzykłady?Otó»wpierwszymznich

istniej¡takiestrategie x 2 X , y 2 Y ,»e u ( x ,y )=sup x 2 X u ( x,y )=inf y 2 Y u ( x ,y ).Z

tegowynika,»e

v =sup

x 2 X

y 2 Y u ( x,y ) inf

y 2 Y u ( x ,y )=sup

u ( x,y ) inf

y 2 Y sup

u ( x,y )= v.

x 2 X

Czyliwarto±¢górnajestrównawarto±cidolnej(iwdodatkurównawypłaciegracza1.,gdy

graczeu»ywaj¡strategii x i y ).

Deﬁnicja1.3 Je±li v = v ,tot¦wspóln¡warto±¢nazywamywarto±ci¡gryioznaczamy

przez v .Je±lidodatkowoistniej¡ x 2 X , y 2 Y ,takie»e u ( x ,y )=sup x 2 X u ( x,y )=

inf y 2 Y u ( x ,y ),mówimy,»estrategie x i y s¡optymalnedlagraczy1.i2.,lub»e( x ,y )

tworz¡punktsiodłowywgrze.

Uwaga1.1 Mówimyostrategiachoptymalnychposzczególnychgraczy,anietylkooopty-

malnejparzestrategii,bostrategieoptymalnedanegograczamo»nami¦dzysob¡wymienia¢

(tenfaktudowodnimysobiena¢wiczeniach).

Mamyzatempewn¡koncepcj¦rozwi¡zania,przynajmniejdlapewnejklasygierosu-

miezerowej.Niedlawszystkichjednak,achci¦liby±mymie¢jak¡±mo»liwo±¢rozwi¡zania

mo»liwiejaknajszerszejklasygier.Napewienpomysł,jaktozrobi¢,wpadłvonNeumann,

itemujegopomysłowipo±wi¦cimyreszt¦wykładu.Tensposóbb¦dzieskutecznytylkodla

gierzesko«czonymizbioramiakcjigraczy.Wypłatydlatakichgier(jakwprzykładzie)

mo»nazapisa¢przypomocymacierzy,st¡db¦dziemyjenazywa¢gramimacierzowymi.

Grymacierzoweosumiezerowej

X = { 1 , 2 ,...,m } –zbiórwierszymacierzy, Y = { 1 , 2 ,...,n } –zbiórkolumnmacierzy

Wypłat¦gracza1.zapisujemyprzypomocymacierzy m × n A =[ u ( i,j )], i 2 X , j 2 Y .

Rozszerzeniemieszanegrymacierzowejzdeﬁniowanejpowy»ej:

Zbioramistrategiigraczys¡ P ( X )i P ( Y )(gdzie P ( A )oznaczazbiórrozkładówprawdopo-

dobie«stwaono±nikuwzbiorze A ).Elementy µ 2 P ( X )oraz 2 P ( Y )b¦dziemynazywa¢

strategiamimieszanymigraczy(wodró»nieniuodelementów X i Y ,którenazywamystra-

tegiamiczystymi),awypłat¦deﬁniujemynast¦puj¡co:

u ( µ, )= X

u ( i,j ) µ i j ,

gdzie µ i toprawdopodobie«stwowylosowania i zrozkładu µ ,a j –prawdopodobie«stwo

wylosowania j z .

v =inf

u ( x,y )=

inf

Oczywi±ciepraktycznierozszerzeniemieszaneinterpretujesi¦wtensposób,»egracze,

zamiastwybra¢jedenwiersz(jedn¡kolumn¦)macierzy A ,wybieraj¡rozkładprawdopodo-

bie«stwa,zgodniezktórymlosuj¡tenwiersz(t¦kolumn¦),ajakowypłatygraczystosujemy

warto±¢oczekiwan¡zichwypłat.

Je±lizastosujemyrozszerzeniemieszane,prawdziweb¦dzienast¦puj¡cetwierdzenie:

Twierdzenie1.1 (vonNeumann,1928) Wka»dejgrzemacierzowejosumiezerowejist-

niejeparaoptymalnychstrategiimieszanychtzn.µ 2 P ( X ) , 2 P ( Y ) takie»e

u ( µ, ) ¬ u ( µ , ) ¬ u ( µ , ) 8 µ 2 P ( X ) , 2 P ( Y ) .

Dowodutegotwierdzenianieb¦d¦podawał,bowynikaztwierdzeniaNasha,któreudo-

wodnimyzatydzie«.

Wniosek1.1 Wstrategiachmieszanychka»dagramacierzowaposiadawarto±¢.

Uwaga1.2 To»e u ( µ, )= v nieoznacza,»e µ i s¡optymalne.Np.wgrzezmacierz¡

wypłat

A =

wybórpierwszejkolumnyidrugiegowierszaniejestoptymalny,awarto±¢gryjestrówna

u ( µ, )= P 1 i =1 P 1 j =1 u ( i, j ) µ i j .

Wtakiejgrze v = − 1,a v =1.

Obatefaktypokazujesi¦podobnie,wi¦cudowodni¦tylkopierwszy.We¹mydowolne µ 2

P ( X )oraz " > 0.Niech n " b¦dzietakie,»e P 1 i = n " +1 µ i < " .Okre±lmyterazstrategi¦gracza

2.jako µ = [ n " ].

u ( µ, µ )=

1 X

u ( i,n " ) µ i =

n " − 1 X

( − 1) µ i +

1 X

(1) µ i

i =1

i = n " +1

= −

1 X

µ i − µ n " +2

1 X

µ i < − 1+2 "

i =1

i = n " +1

Poniewa» " byłodowolne,dostajemy

2 P ( Y ) u ( µ, ) ¬− 1 ,

inf

aleskorodowolniebyłote»wybrane µ ,tomamy

sup

µ 2 P ( X )

2 P ( Y ) u ( µ, ) ¬− 1 .

inf

Oczywi±ciewrzeczywisto±cimamyrówno±¢,bowgrzeniemawypłatmniejszychni»-1.

Niestety,trickzrozszerzeniemmieszanymniedziałaju»dlagierzwi¦kszymizbiorami

akcjigraczy.Łatwoznale¹¢przykładgryzprzeliczalnymizbioramistrategiiczystych,dla

którejgranieposiadawarto±ciwstrategiachmieszanych.

Przykład: Niech X = Y = { 1 , 2 ,... } oraz u ( x,y )=sgn( x − y ).Rozwa»myrozszerzenie

mieszanetejgry: P ( X )= { µ : µ i 0 , P 1 i =1 µ i =1 } , P ( Y )= { : i 0 , P 1 i =1 i =1 } ,

1.2Gryosumieniezerowej

Naostatnimwykładziemówiłemograchopisuj¡cychsytuacj¦,gdymamydwóchgraczy,

którychinteresys¡całkowicieprzeciwstawne–tak¡sytuacj¦opisywałygrymacierzowe,czy

ogólniejgrydwuosoboweosumiezerowej.Dzisiajuogólniamytamtenmodel.Zaczniemy

odsytuacji,gdymamydwóchgraczy,którychinteresynies¡dokładnieprzeciwne.

Grydwumacierzowe

Niech X = { 1 , 2 ,...,m } –zbiórstrategii(czystych)gracza1., Y = { 1 , 2 ,...,n } –zbiór

strategii(czystych)gracza2.Niech A =[ a ij ] m × n –macierzwypłatgracza1., B =[ b ij ] m × n

–macierzwypłatgracza2.(Oczywi±cie,tewypłatys¡czystosubiektywne,imówi¡otym,

codanygraczmy±liodanejsytuacji,aniemusz¡oznacza¢jakich±konkretnychwypłat,

którejedenzgraczywypłacadrugiemu,lubkto±trzeci(PanBóg)wypłacagraczom).Jak

poprzednio,rozwa»amyodrazurozszerzeniemieszanetakiejgry,czylidowolnyrozkład

prawdopodobie«stwanazbiorze X , µ =( µ 1 ,...,µ m )jeststrategi¡mieszan¡gracza1;

rozkładprawdopodobie«stwanazbiorze Y , =( 1 ,..., n )–strategi¡mieszan¡gracza

2.,natomiastwypłatamiposzczególnychgraczys¡odpowiedniewarto±cioczekiwane:

u 1 ( µ, )= X

a ij µ i j u 2 ( µ, )= X

b ij µ i j .

Jakpami¦taj¡Pa«stwo,wgrachosumiezerowejoptymalnymzachowaniembyłowybra-

nieprzezgraczanajkorzystniejszejdlasiebiestrategiiprzyzało»eniu,»eprzeciwnikb¦dzie

grałnajgorzejdlanas.Tamuzasadnieniemtakiegozachowaniabyłoto,»einteresygraczy

byłydokładnieprzeciwne,iwiedzieli±my,»eprzeciwnikwybierzeto,codlanasnajbardziej

niekorzystne,dlatego»etobyłojednocze±nienajbardziejkorzystnedlaniego.Tutajnie

mamypowodu,»ebyoczekiwa¢,»eprzeciwnikb¦dziespecjalniedziałałnanasz¡niekorzy±¢

(niewszyscygraczes¡Polakami)–wi¦cnaturalnymjest,»eka»dyzgraczystarasi¦zmak-

symalizowa¢własn¡wypłat¦,przyzało»eniu,»einnite»staraj¡si¦zmaksymalizowa¢swoje

wypłaty.Autoremtakiejkoncepcjirozwi¡zaniajestJohnNash(st¡dnazwa).

Deﬁnicja1.4 Równowag¡wsensieNashawgrzedwumacierzowejnazwiemytak¡par¦

strategii µ 2 P ( X ), 2 P ( Y ),»e

u 1 ( µ , ) u 1 ( µ, ) 8 µ 2 P ( X )

u 2 ( µ , ) u 1 ( µ , ) 8 2 P ( Y ) ,

czylitak¡,»eodst¡pienieodrównowagiprzezpojedynczegograczaniejestdlaniegoopła-

calne.

Uwaga1.3 Oczywi±cie,je±li B = − A ,czyli u 1 = − u 2 ,równowag¡Nashasprowadzasi¦

dopunktusiodłowego.

RównowagawsensieNashawydajesi¦natylenaturalnymuogólnieniempunktusiodło-

wego,»epewniedu»acz¦±¢zPa«stwabyj¡wymy±liła,ia»narzucasi¦pytanie,dlaczego

vonNeumannjejniewymy±lił.Jednazmo»liwychodpowiedzijesttaka,»epewniewymy-

±lił,aleuznałtakierozwi¡zaniezawadliwe.Iterazpar¦słównatemattego,cowpoj¦ciu

NEniejestdoko«caudane.

Rozwa»mytakiprzykład:

Przykład: Mamydwojemał»onków,którzywła±niewysłalidziecidodziadkównawieczór,

iplanuj¡sp¦dzi¢razemwieczór,tylkozastanawiaj¡si¦jak.Kanonicznawersjatejhistoryjki

jesttaka,»ePanichcei±¢nabalet,Pannaboks(coprawdaniewieluznamfacetów,którzy

chcielibyi±¢naboks,ijeszczemniejkobiet,którechciałybynabalet,aleb¦d¦si¦trzymał

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: