M´atrixj´at´ekok tiszta nyeregponttal ´lda. K´et j´at´ekos – Alad´ar ´es Bendeg´ 1. Pe uz – rendelkeznek egy-egy tetra´ederrel, melyek lapjaira rendre az 1, 2, 3, 4 sz´amokat ´ırt´ak. Egy megadott jelre egyszerre felmutatj´ak egym´asnak a n´aluk lev˝o tetra´eder valamelyik lapj´at. Ha Alad´ar i-t (i = 1, 2, 3, 4), Bendeg´ uz pedig j-t (j = 1, 2, 3, 4) mutat, akkor az al´abbi t´abl´azat i-edik sor´anak j-edik eleme megmutatja, hogy kinek mennyi p´enzt kell fizetnie a m´asiknak. Ha p´eld´aul Alad´ar 3at mutat, Bendeg´ uz pedig 2-t, akkor a t´abl´azat harmadik sor´anak m´asodik eleme (−2) szerint Alad´ar fizet Bendeg´ uznak k´et forintot. A t´abl´azat teh´at Alad´ar lehets´eges nyeres´egeit vagy vesztes´egeit tartalmazza, ha a megfelel˝o elem pozit´ıv akkor Alad´ar kap p´enzt Bendeg´ uzt´ol, ha negat´ıv, akkor ˝o fizet Bendeg´ uznak. A k´erd´es az, hogy a j´at´ekosok milyen taktik´aval j´atssz´ak a j´at´ekot, ha feltessz¨ uk, hogy sok partit szeretn´enek lebonyol´ıtani. ´Ime a fizet´esi t´abl´azat, melyet egy 4 × 4-es A = [aij ] m´atrixk´ent is felfoghatunk. Bendeg´ uz
Alad´ar
1 2 3 4
1 2 1 3 −3
2 3 4 −4 −1 6 −1 3 2 −2 1 0 −1 4 0
Alad´ar arra t¨orekszik, hogy az egyes esetekben a sz´am´ara legrosszabb eset a lehet˝o legjobb legyen. Ez´ert megn´ezi, hogy az egyes alternat´ıv´akn´al – nevezz¨ uk ezeket strat´egi´aknak – mekkora a t´abl´azat megfelel˝o sor´aban a legkisebb ´ert´ek, ´es u ´gy pr´ob´al j´atszani, hogy ez min´el nagyobb legyen. Teh´at a fizet´esi m´atrix sorminimumainak maximum´at keresi meg. Jelen esetben max{−4, −1, −2, −3} = −1 = a22 . Bendeg´ uz hasonl´oan gondolkodik, a legrosszabb eseteket szeretn´e elker¨ ulni. Mivel a t´abl´azat Alad´ar szemsz¨og´eb˝ol k´esz¨ ult, ez´ert ˝o a m´atrix sormaximumainak minimum´at keresi meg, amely most min{3, −1, 4, 6} = −1 = a22 . K¨onny˝ u l´atni, hogy mindk´et j´at´ekos abban ´erdekelt, hogy ´alland´oan a 2-t tartalmaz´o lapot mutassa fel. Ugyanis ha ett˝ol elt´erne valamelyik¨ uk, akkor nem j´arna jobban, mert a22 = −1 a sor´aban minim´alis, oszlop´aban pedig maxim´alis. Eszerint a fenti j´at´ekot le sem kell j´atszani, mert mindig ugyanazt fogj´ak l´epni a j´at´ekosok, ´es ´ıgy j´at´ekonk´ent Alad´ar 1 forintot vesz´ıtene (amely az ˝o szempontj´ab´ol −1 forintk´ent jelenik meg). A a v´alasztott strat´egi´ak sorsz´amaib´ol k´epzett (2, 2) p´art tiszta nyeregpontnak fogjuk h´ıvni, m´ıg a22 = −1 a j´at´ek ´ert´eke. 2 Tekints¨ unk most ´altal´anosan egy k × n-es A = [aij ] (i = 1, . . . , k; j = 1, . . . , n) fizet´esi m´atrixot. K´et j´at´ekos k¨oz¨ ul az els˝o a k sor, a m´asodik n oszlop k¨oz¨ ul v´alaszthat. A v´alasztottak alapj´an az A m´atrixb´ol – amely az els˝o j´at´ekos szempontj´ab´ol k´esz¨ ult – kikeresik, hogy kinek mennyit kell fizetni a m´asiknak. Ilym´odon A egy´ertelm˝ uen meghat´arozza a j´at´ekot. ´ . Az A = [aij ] m´atrixszal megadott m´atrixj´at´ekn´al az (i0 , j0 ) p´art tiszta 2. Defin´ıcio nyeregpontnak h´ıvjuk, ha ai0 j0 a sor´aban minim´alis ´es oszlop´aban maxim´alis, azaz aij0 ≤ ai0 j0 ≤ ai0 ,j
∀i, j
(i = 1, . . . , k; j = 1, . . . , n).
Ekkor v = ai0 j0 a j´at´ek ´ert´eke. ♦ 1
Amennyiben egy m´atrixj´at´eknak van tiszta nyeregpontja, akkor a j´at´ek megold´as´anak az (i0 , j0 , v) h´armast tekintj¨ uk. A k¨ovetkez˝o k´et t´etel k¨oz¨ ul az els˝o egy elj´ar´ast ad tiszta nyeregpont l´etez´es´enek eld¨ont´es´ere, tov´abb´a annak megkeres´es´ere. A m´asodik t¨obb tiszta nyeregpont eset´en azok felcser´elhet˝os´eg´et mondja ki. 3. T´ etel. Az A = [aij ] m´atrixj´ at´eknak az (i0 , j0 ) p´ar akkor ´es csak akkor tiszta nyeregpontja, ha max min{aij } = ai0 j0 = min max{aij }. i
j
j
i
4. T´ etel. Ha egy A = [aij ] m´atrixszal megadott j´at´eknak t¨obb tiszta nyeregpontja van akkor azok ekvivalensek egym´ assal. ´lda. 5. Pe
A = [aij ] =
3 −2 3 −5
4 0 5 2
5 3 4 1 −5 1 4 3 5 3 2 0
Ebben a j´at´ekban maxi minj {aij } = 3 = minj maxi {aij }, de a tiszta nyeregpont n´egy (egym´assal egyen´ert´ek˝ u) helyen is el˝ofordul: 3 = a11 = a14 = a31 = a34 . Most az els˝o j´at´ekos kedv´ere v´alaszthat az els˝o ´es harmadik strat´egi´ak k¨oz¨ ul. Hasonl´oan a m´asodik j´at´ekos szabadon cser´elgethet az els˝o ´es negyedik strat´egi´ai k¨oz¨ott. 2
2
M´atrixj´at´ekok ´altal´anos vizsg´alata Tekints¨ uk most egy k × n-es A = [aij ] =
a11 a12 a21 a22 .. .. . . ak1 ak2
. . . a1n . . . a2n .. .. . . . . . akn
m´atrixszal adott m´atrixj´at´ekot, ´es tegy¨ uk fel, hogy a j´at´ekosoknak nincs tiszta strat´egi´ajuk (teh´at maxi minj {aij } 6= minj maxi {aij }). Ebben az esetben egyik f´el sem fog ragaszkodni egy konkr´et strat´egi´ahoz, hiszen a m´asik f´el azt kiismerve a j´at´ekban kedvez˝obb helyzetbe ker¨ ulhet. Ugyanez a helyzet akkor is, ha valamelyik j´at´ekos el˝ore meghat´arozott m´odon cser´elgeti a v´alaszt´asait, hiszen egy id˝o ut´an a m´asik j´at´ekos r´aj¨ohet a szab´alyszer˝ us´egre, ´es az inform´aci´ot a saj´at jav´ara haszn´alhatja fel. A legjobb amit tehetnek, hogy v´eletlenszer˝ uen v´alasztanak az alternat´ıv´ak k¨oz¨ ul, teh´at keverik a strat´egi´akat. Ekkor viszont az a k´erd´es mer¨ ul fel, hogy az egyes v´alaszt´asi lehet˝os´egekhez mekkora val´osz´ın˝ us´egeket rendeljenek hozz´a, m´ask´eppen fogalmazva, milyenek legyenek a val´osz´ın˝ us´eg-eloszl´asok. Jel¨olje a p ¯ = [p1 , p2 , . . . , pk ]> vektor azt, hogy az els˝o j´at´ekos a m´atrix els˝o, m´asodik, P stb. k-adik sor´at rendre p1 , p2 , stb. pk val´osz´ın˝ us´eggel v´alasztja, ahol ki=1 pi = 1. HaP sonl´oan a q ¯ = [q1 , q2 , . . . , qn ]> ( kj=1 qj = 1) vektor a m´asodik j´at´ekos alternat´ıv´aihoz tartoz´o val´osz´ın˝ us´eg-eloszl´ast mutatja. Ekkor az els˝o j´at´ekos nyerem´eny´enek v´arhat´o ´ert´eke az E(¯ p, q ¯) =
k X n X
aij pi qj = p ¯ > A¯ q
i=1 j=1
kifejez´essel sz´amolhat´o. Ebb˝ol adott p ¯, q ¯ vektorok eset´en r¨ogt¨on eld¨onthet˝o, hogy kinek el˝ony¨os a j´at´ekot ´ıgy j´atszani. Nyilv´anval´o, hogy a h´atr´anyos helyzetben lev˝o f´el v´altoztatni szeretne. De vajon siker¨ ulhet-e neki? Most azt vizsg´aljuk meg, hogyan kell a kevert strat´egi´akat megv´alasztani a j´et´ekosoknak, hogy a lehet˝o legjobban j´arjanak a j´at´ek sor´an. Egyens´ ulyi helyzet akkor alakul ki, ha a szemben´all´o feleknek van olyan p ¯ 0 ill. q ¯0 kevert strat´egi´ajuk, melyekre b´armely p ¯ ´es q ¯ mellett E(¯ p, q ¯0 ) ≤ E(¯ p0 , q ¯0 ) ≤ E(¯ p0 , q ¯)
(1)
teljes¨ ul. ´ . A (¯ 6. Defin´ıcio p0 , q ¯0 ) vektorp´ar az A m´atrixj´at´ek nyeregpontja, ha b´armely p ¯ ´es q ¯ eloszl´asra E(¯ p, q ¯0 ) ≤ E(¯ p0 , q ¯0 ) ≤ E(¯ p0 , q ¯). Ekkor v = E(¯ p0 , q ¯0 ) a j´at´ek ´ert´eke. ♦ at´eknak van nyereg7. T´ etel. (J´at´ekelm´elet alapt´etele, Neumann J´anos) Minden m´atrixj´ pontja. Meg kell jegyezn¨ unk, hogy t¨obb nyeregpont eset´en azok egym´assal egyen´ert´ek˝ uek, ugyanazt a v ´ert´eket szolg´altatj´ak. Tov´abb´a k¨onnyen l´athat´o, hogy a tiszta strat´egia a kevert strat´egia olyan speci´alis esete, mikor a val´osz´ın˝ us´eg-eloszl´asban egy val´osz´ın˝ us´eg 1 lesz, a t¨obbi pedig 0. A f˝o k´erd´es a tov´abbiakban az, hogyan lehet megkeresni a nyeregpontot? 3
M´atrixj´at´ekok vizsg´alata speci´alis esetekben I. ESET 8. T´ etel. Ha egy A = [aij ] ∈ IRk×n m´atrix minden sor´aban ugyanaz az S sz´ am az elemek osszege, tov´abb´ ¨ a ugyanaz az O sz´ am az egy oszlopban lev˝o elemek ¨osszege, akkor ·
1 1 1 p ¯0 = , , . . . , k k k tov´ abb´ a
¸>
´lda. Az 9. Pe
1 1 1 q ¯0 = , ,..., n n n
,
Pk
i=1
v=
·
Pn
j=1
aij
k·n
=
¸>
,
S O = . n k
2 1 4 1 A = 2 4 4 −2 ∈ IR3×4 2 1 −2 7 m´atrixszal adott j´at´ek eset´en minden sorban az elemek ¨osszege S = 8, ´es minden oszlopban az elemek ¨osszege O = 6. Az el˝oz˝o t´etel szerint a j´at´ekosok egyenletesen osztj´ak sz´et az egys´egnyi val´osz´ın˝ us´eget az alternat´ıv´aik k¨oz¨ott: ·
1 1 1 p ¯0 = , , 3 3 3
¸>
·
1 1 1 1 q ¯0 = , , , 4 4 4 4
,
¸>
.
A j´at´ek az els˝o j´at´ekos sz´am´ara kedvez˝o, mert a j´at´ek v=2=
8 6 = 4 3
´ert´eke pozit´ıv. 2 Vannak olyan m´atrixj´at´ekok, amelyekn´el a felt´etelek ellen˝orz´ese pillanatok alatt megt¨ort´enhet. Ezekben az esetekben a j´at´ek vizsg´alat´at leggyorsabban az el˝oz˝o t´etellel lehet v´egrehajtani. Tekints¨ unk k´et ilyen p´eld´at. ´lda. Legyenek x ´es y tetsz˝oleges val´os sz´amok. Ha 10. Pe "
A=
x y y x
#
∈ IR2×2
akkor S = O = x + y, ´es mindk´et j´at´ekosnak 1/2 - 1/2 val´osz´ın˝ us´eggel kell v´alasztania az egyes lehet˝os´egeit. A j´at´ek ´ert´eke v = (x + y)/2. 2 ´lda. B´armely a, b, c val´os sz´amok eset´en az 11. Pe
a b c 3×3 A= c a b ∈ IR b c a m´atrixszal megadott j´at´ekra S = O = a + b + c, teh´at az egyes strat´egi´akra rendre 1/3 val´osz´ın˝ us´eg jut. A j´at´ek ´ert´eke v = (a + b + c)/3. 2 4
II. ESET (2 × 2-es j´at´ekok) Legyen most
"
A=
a11 a12 a21 a22
#
egy tiszta nyeregponttal nem rendelkez˝o m´atrixj´at´ek. Mivel mindk´et j´at´ekosnak k´et v´alaszt´asi lehet˝os´ege van, ´ıgy a strat´egi´aik p ¯ = [p1 , p2 ]> = [p, 1−p]> illetve q ¯ = [q1 , q2 ]> = [q, 1 − q]> alakban ´ırhat´ok, ahol 0 ≤ p , q ≤ 1. Teh´at a j´at´ek megold´as´ahoz elegend˝o p, q ´es v meghat´aroz´asa. 12. T´ etel. Ha egy 2 × 2-es A m´atrixj´ at´eknak nincs tiszta nyeregpontja akkor A = a11 − a12 − a21 + a22 6= 0. at´eknak nincs tiszta nyeregpontja akkor 13. T´ etel. Ha egy 2 × 2-es A m´atrixj´ p=
a22 − a21 , A
q=
a22 − a12 , A
´lda. Az 14. Pe
"
A=
2 −3 −3 4
v=
a11 a22 − a21 a12 . A
#
m´atrixj´at´eknak nincs tiszta nyeregpontja. Mivel A = 2 − (−3) − (−3) + 4 = 12, ez´ert p = 7/12, q = 7/12 ´es v = −1/12. 2 Az el˝oz˝o t´etel haszn´alata n´elk¨ ul is k¨onnyen meghat´arozhat´ok a p, q ´es v ´ert´ekek. Erre k´et m´odszer is aj´anlkozik. Az els˝ot algebrai m´odszernek h´ıvjuk ´es l´enyeg´eben az el˝oz˝o t´etel bizony´ıt´as´anak l´ep´eseit sz´amoljuk v´egig az adott m´atrix eset´en. A m´asodik elj´ar´ast geometriai m´odszernek nevezz¨ uk, mert az E(¯ p0 , q ¯0 ) = E(p0 , q0 ) v´arhat´o ´ert´ekre vonatkoz´o (1) egyenl˝otlens´egeket haszn´alja p = 0 ´es p = 1 illetve q = 0 ´es q = 1 eset´en. ´lda. L´asd 2 × 2-es m´atrixj´at´ekokra vonatkoz´o mintafeladat. 2 15. Pe Mivel a mintap´eld´aban nincs le´ırva az egyenl˝otlens´egek pontos sz´armaztat´asa, ez´ert itt tessz¨ uk ezt meg. Legyen teh´at A = [aij ] ∈ IR2×2 . Ekkor tetsz˝oleges p ´es q val´osz´ın˝ us´egek eset´en E(p, q) = a11 pq + a12 p(1 − q) + a21 (1 − p)q + a22 (1 − p)(1 − q). (1) alapj´an az al´abbi egyenl˝otlens´egrendszerek ´ırhat´ok fel.
E(1, q0 ) = a11 q0 + a12 (1 − q0 ) ≤ v E(0, q0 ) = a21 q0 + a22 (1 − q0 ) ≤ v v −→ min ´es
E(p0 , 1) = a11 p0 + a21 (1 − p0 ) ≥ v E(p0 , 0) = a12 p0 + a22 (1 − p0 ) ≥ v v −→ max
A k´et egyenl˝otlens´egrendszert rendezve ´es k¨ ul¨on-k¨ ul¨on grafikusan megoldva egyszer˝ uen juthatunk el az optim´alis strat´egi´ak ´es a j´at´ek ´ert´ek´enek meghat´aroz´as´ahoz.
5
III. ESET (2 × n-es vagy k × 2-es j´at´ekok) Ezen speci´alis t´ıpusn´al ¨otv¨oz˝odik az el˝oz˝o esetn´el megismert grafikus ´es algebrai megold´as. El˝osz¨or – a geometriai m´odszert felhaszn´alva – meghat´arozzuk a k´et v´alaszt´asi lehet˝os´eggel rendelkez˝o j´at´ekos kevert strat´egi´aj´at. A 2×2-es j´at´ek megold´as´at´ol ez abban k¨ ul¨onb¨ozik, hogy a megfelel˝o egyenl˝otlens´eg-rendszer kett˝on´el t¨obb egyenl˝otlens´eget tartalmaz. A m´asodik l´ep´esben – az els˝o l´ep´es eredm´eny´et is felhaszn´alva – algebrai u ´ton kisz´amoljuk a m´asik j´at´ekos kevert strat´egi´aj´at. ´lda. L´asd 2 × 5-¨os m´atrixj´at´ekra vonatkoz´o mintafeladatot. 2 16. Pe
6
M´atrixj´at´ekok megold´as szimplex m´odszerrel Tekints¨ uk most ism´et a k × n-es A = [aij ] =
a11 a12 a21 a22 .. .. . . ak1 ak2
. . . a1n . . . a2n .. .. . . . . . akn
m´atrixszal megadott j´at´ekot. Most egy univerz´alis m´odszert ismertet¨ unk a j´at´ekosok optim´alis strat´egi´ainak meghat´aroz´as´ara. A m´odszer akkor is m˝ uk¨odik, ha tiszta strat´egia van, de az´ert annak krit´erium´at ´erdemes el˝osz¨or a sorminimumokkal ´es az oszlopmaximumokkal tesztelni, mert a felt´etel teljes¨ ul´ese eset´en gyorsabban jutunk megold´ashoz, mint az ´altal´anos elj´ar´assal. A megold´as l´ep´eseit pontokba szedve fogalmazzuk meg. 1. Ha az A m´atrix elemei k¨oz¨ott van negat´ıv ´ert´ek, akkor v´alasszunk egy (lehet˝oleg kicsi) pozit´ıv c sz´amot u ´gy, hogy az A m´atrix minden elem´ehez c-t adva, a kapott A1 m´atrix minden eleme nemnegat´ıv legyen. 2. A szimplex m´odszert alkalmazva megoldjuk az A1 x ¯ ≤ x ¯ ≥ > ¯ 1 x ¯ −→
¯ 1 ¯ 0 max
¯ 1 ¯ 0 min
A> ¯ ≥ 1y y ¯ ≥ > ¯ 1 y ¯ −→
,
prim´al-du´al feladatp´art. 3. A prim´al programoz´asi feladat ´es du´alis´anak megold´as´aban legyen a k¨oz¨os maxim´alis ill. minim´alis ´ert´ek v˜. Az els˝o j´at´ekos optim´alis strat´egi´aj´ara p ¯ > = [p1 , . . . , pk ] =
·
¸
·
¸
1 > 1 y1 yk ·y ¯ = · [y1 , . . . , yk ] = ,... v˜ v˜ v˜ v˜
teljes¨ ul, m´ıg a m´asodik j´at´ekos optim´alis strat´egi´aja q ¯> = [q1 , . . . , qn ] =
1 > 1 x1 xn ·x ¯ = · [x1 , . . . , xn ] = ,... v˜ v˜ v˜ v˜
alapj´an sz´amolhat´o. Teh´at az els˝o j´at´ekos optim´alis strat´egi´aj´ara a du´alis feladat megold´as´ab´ol, a m´asodik j´at´ekos optim´alis starat´egi´aj´ara a prim´al feladat´eb´ol k¨ovetkeztethet¨ unk. Az eredeti A m´atrixj´at´ek ´ert´eke v=
1 − c. v˜
´lda. L´asd a m´atrixj´at´ekok szimplex m´odszerrel val´o elemz´es´ere vonatkoz´o mintafe17. Pe ladatot. 2
7
