Če še ne poznaš matričnih iger, ki so osnova za bimatrične, si lahko nekaj o njih prebereš tukaj.

Bimatrične igre v formatu .pdf

Poleg matričnih iger z vsoto nič poznamo še matrične igre, katerih vsota ni enaka nič.

1. Splošne matrične igre v strateški obliki

Splošna matrična igra je podana z dvema množicama X in Y čistih strategij igralcev in z dvema realnima funkcijama u₁(x,y) in u₂(x,y), definiranih na X×Y, ki predstavljata plačili za oba igralca. Če prvi (I) izbere x ∈ X in drugi (II) izbere y ∈ Y, potem I dobi u₁(x,y) in II dobi u₂(x,y).

Končno matrično igro lahko predstavimo z matriko urejenih parov, poimenujemo jo bimatrika. Prva komponenta para predstavlja plačilo igralca I, druga komponenta pa predstavlja plačilo igralca II. Matrika ima toliko vrstic, kot ima igralec I čistih strategij in toliko stolpcev, kot ima igralec II čistih strategij. Npr. bimatrika:

(1)	( ) (1,4) (2,0) (-1,1) (0,0) (3,1) (5,3) (3,-2) (4,4) (0,5) (-2,3) (4,1) (2,2)

predstavlja igro, v kateri ima igralec I tri čiste strategije (vrstice) in igralec II štiri čiste strategije (stolpci). če igralec I izbere vrstico 3 in igralec II stolpec 2, potem igralec I dobi -2 (torej izgubi 2) in igralec II dobi 3.

Eden od načinov, kako opišemo končno matrično igro, je s parom matrik. Če m in n predstavlja število čistih strategij dveh igralcev, lahko igro predstavimo z dvema m×n matrikama A in B. Interpretiramo tako: če igralec I izbere vrstico i in igralec II izbere stolpec j, potem I dobi a_ij in II dobi b_ij, kjer sta a_ij in b_ij elementa v i-ti vrstici in j-tem stolpcu matrik A oz. B. Upoštevati je treba, da B predstavlja zmage igralca II in ne izgube, kot je to v primeru za matrične igre z vsoto nič. Igra bimatrike (1) je predstavljena kot (A,B), kjer:

(2)

A =

( ) 1 2 -1 0 3 5 3 4 0 -2 4 2

in

B =

( ) 4 0 1 0 1 3 -2 4 5 3 1 2

Torej, matrična igra ima vsoto nič, če in samo če velja: B = -A.

2. Pregled

Analiza matričnih iger je bolj zapletena za splošne matrične igre, kot pa za igre z vsoto nič. Ko vsota plačil ni več enaka nič (ali konstantna), maksimiziranje plačila enega igralca ni več enako minimiziranju plačila drugega. Izrek o minimaksu ne ustreza bimatričnim igram. Igralec ne more več računati na to, da bo igral optimalno, če bo gledal samo na svojo matriko in delal v nasprotju z najslabšim primerom. Logično je, da mora upoštevati nasprotnikovo matriko in sklepati, katero strategijo bo verjetno uporabil. Tudi drugi igralec mora delati na tak način. Primer za splošne matrične igre torej zahteva drugačen koncept rešitev.

Teorija je v splošnem razdeljena na dve veji, nekooperativno teorijo in kooperativno teorijo. V nekooperativni teoriji imamo dve možnosti: ali se igralci ne pogovarjajo, predno se odločijo, ali če se pogovarjajo, se ne smejo dogovarjati o strategijah. Glaven koncept nekooperativnih rešitev je strateško ravnovesje (razloženo kasneje). V kooperativni teoriji se tekmovalci lahko dogovarjajo, predno se odločijo. Lahko se dogovorijo, da bodo uporabili določene strategije, vendar je tak dogovor lahko narejen pod prisilo (eden prisili drugega, kakšno strategijo naj uporabi).

3. Varen nivo

Enega od konceptov za matrične igre z vsoto nič lahko prenesemo na splošne matrične igre in ta koncept se v splošnih matričnih igrah zelo uporablja. To je varen nivo ali znesek, ki ga lahko vsak igralec v povprečju zagotovo dobi. V bimatrični igri z m×n matrikama A in B lahko igralec I v povprečju zagotovo dobi vsaj:

(3)	vI = maxpminj∑i=1mpiaij = Val(A)

To imenujemo varen nivo igralca I. (To je po definiciji najmanjša vrednost od A, kar je po izreku o minimaksu tudi največja vrednost A. Torej lahko pišemo v_I = Val(A)). Igralec I lahko doseže to plačilo, brez da bi se oziral na matriko igralca II. Strategija p, ki doseže maksimum v (3), se imenuje maxmin strategija za igralca I.

Na isti način dobimo varen nivo igralca II, to je:

(4)	vII = maxqmini∑j=1nbijqj = Val(BT)

Torej lahko igralec II zagotovo dobi v povprečju ta znesek. Strategija q, ki doseže maksimum v (4), se imenuje maxmin strategija za igralca II (v_II je vrednost od B^T, to pa zato, ker je Val(B) definirana kot vrednost igre, kjer komponente predstavljajo zmage (dobitke) tistega, ki ima vrstice in izgube tistega, ki ima stolpce). Pojasnimo na primeru:

(	(2,0)	(1,3)	)	oziroma	A =	(	2	1	)	in	B =	(	0	3	)
	(0,1)	(3,2)					0	3					1	2

Iz matrike A vidimo, da je za igralca I maxmin strategija ( ³/₄ , ¹/₄ ) in njegov varen nivo je v_I = ( ³/₂ ). Pri matriki B vidimo, da je drugi stolpec večji od prvega (to so spet dobički igralca II; radi bi maksimizirali). Za igralca II velja: v_II = 2 po maxmin strategiji (stolpec 2). To je vrednost od B^T, medtem ko je Val(B) = 1.

Če oba igralca uporabljata maxmin strategijo, potem igralec I dobi samo v_I, medtem ko igralec II dobi ³/₄⋅3 + ¹/₄⋅2 = ¹¹/₄. To je ugodno za igralca II. Toda če igralec I pogleda matriko B, lahko vidi, da bo igralec II zelo verjetno izbral stolpec 2, ker je stolpec 2 večji od stolpca 1. Potem igralec I dobi 3, kar je večje od v_I in igralec II dobi v_II = 2.

Plačilo (3,2) iz druge vrstice in drugega stolpca je bolj stabilno. Če vsak igralec verjame, da bo nasprotnik izbral drugo strategijo, potem bo vsak izbral drugo strategijo. To je eno glavnih stališč teorije nekooperativne igre, kjer se tak strateški par imenuje strateško ravnovesje.

4. Nekooperativne igre

Splošne matrične igre in igre za n igralcev, kjer je n > 2, je težje analizirati in interpretirati kot igre z vsoto nič. "Optimalnost" tu ne obstaja. V nekooperativni teoriji se smatra, da igralci ne morejo očitno sodelovati, da bi dobili višje dobitke. Če je dovoljena komunikacija, potem ne morejo delati povezanih dogovorov. Možno nadomestilo za "rešitev" igre najdemo v strateškem ravnovesju.

Strateško ravnovesje. Končna igra n igralcev v strateški obliki je dana z n nepraznimi množicami X₁, X₂, …, X_n in z n realnimi funkcijami u₁, u₂, …, u_n, ki so definirane na X₁×X₂×…×X_n. Množica X_i predstavlja množico čistih strategij igralca i in u_i(x₁, x₂, …, x_n) predstavlja plačila igralcu i, ko so x₁, x₂, …, x_n izbire čistih strategij igralcev, kjer x_j ∈ X_j za j = 1, 2, …, n.

Definicija: Vektor čistih strategij x₁, x₂, …, x_n, kjer x_i ∈ X_i za i = 1, 2, …, n, se imenuje čisto strateško ravnovesje (PSE - pure strategic equilibrium), če za vse i = 1, 2, …, n in za vse x ∈ X_i velja:

(5)	ui(x1, …, xi-1, xi, xi+1, …, xn) ≥ ui(x1, …, xi-1, x, xi+1, …, xn)

Neenakost (5) torej pove, da če ostali igralci izberejo njihove strategije, potem je najboljše za igralca i, da uporabi x_i. Takšna čista strategija za igralca i se imenuje najboljši odgovor strategijam drugih igralcev. Ideja strateškega ravnovesja je lahko takšna: določena izbira strategije igralca postane PSE, če vsak igralec uporablja najboljši "odgovor" na strategijo drugega igralca. Kot primer poglejmo primer dveh igralcev:

(a)	(	(3,3)	(0,0)	)	(b)	(	(3,3)	(4,3)	)
		(0,0)	(5,5)				(3,4)	(5,5)

V primeru (a) je matrika na mestu [1,1] strateško ravnovesje s plačilom (3,3). Če vsak verjame, da bo nasprotnik izbral prvo strategijo, tudi sam ne bo hotel zamenjati svoje strategije. Na mestu [2,2] imamo prav tako strateško ravnovesje. Ker je tu plačilo (5,5), je obema igralcema ljubše to ravnovesje. Pri (b) je [1,1] po definiciji ravnovesje. Noben igralec ne more zmagati, če zamenja strategijo. Po drugi strani pa noben igralec ne bo prizadet, če zamenja in če oba zamenjata, bosta oba na boljšem. Zato je ravnovesje [1,1] bolj nestabilno.

Primer (a) je iz igre, v kateri igralca dobita isto izplačilo, toda se ne smeta pogovarjati. Če bi se lahko pogovarjala, bi se dogovorila za tako igro, ki da maksimalno izplačilo obema.

Če se igralci v nekooperativni igri lahko pogovarjajo in dosežejo neke neformalne dogovore, lahko pričakujemo, da bo strateško ravnovesje. Vsak igralec maksimizira svoj dobiček glede na strategijo, ki naj bi jo uporabil nasprotnik.

Definicijo razširimo tako, da je igralcem dovoljeno, da uporabijo mešane strategije. Označimo množico možnosti po k točkah s P_k:

(6)	Pk = {p = (p1, …, pk): pi ≥ 0 za i = 1, …, k in ∑i=1kpi = 1}

Naj m_i označuje število čistih strategij za igralca i, tako da ima množica X_i m_i elementov. Potem je množica mešanih strategij igralca i: P_mi. Označimo jo z X^*_i, torej X^*_i = P_mi.

Označimo sedaj množico elementov X_i s prvimi m_i naravnimi števili, torej: X_i = {1, 2, …, m_i}. Predpostavimo, da za i = 1, 2, …, n igralec i uporabi p_i = (p_i1, p_i2, …, p_imi) ∈ X^*_i. Potem je povprečno izplačilo za igralca j:

(7)	gj(p1, …, pn) = ∑i1=1m1…∑in=1mnp1i1…pninuj(i1, …, in)

Iz tega sledi analogna definicija ravnovesja, ki uporablja mešane strategije:

Definicija: Vektor mešanih strategij (p₁, p₂, …, p_n), kjer p_i ∈ X^*_i za i = 1, 2, …, n, se imenuje strateško ravnovesje (SE - strategic equilibrium), če za vse i = 1, 2, …, n in za vse p ∈ X^*_i velja:

(8)	gi(p1, …, pi-1, pi, pi+1, …, pn) ≥ gi(p1, …, pi-1, p, pi+1, …, pn)

Katerakoli mešana strategija p_i, ki zadošča neenakosti (8), je najboljši odgovor igralca i na mešane strategije ostalih igralcev. Določena izbira mešanih strategij igralcev je strateško ravnovesje, če in samo če vsak igralec uporablja najboljši odgovor na strategije drugih igralcev. Noben igralec ne more zmagati, če samo on spreminja strategijo. Čisto strateško ravnovesje (PSE) je poseben primer strateškega ravnovesja (SE).

Ta koncept najboljšega odgovora predstavlja praktičen način igranja igre: Glede na to, katere različne čiste strategije bo tvoj nasprotnik po tvojem mnenju igral, izberi najboljši odgovor nanje. To je primer Bayesovega poskusa, kako se odločati. Seveda je v igri to lahko nevaren postopek, saj je lahko nasprotnik boljši v tem načinu ugibanja.

Prvo vprašanje, ki se je pojavilo, je bilo: "Ali vedno obstaja strateško ravnovesje?". To vprašanje je leta 1951 rešil John Nash v naslednjem izreku, ki je posplošitev von Neumanovega izreka o minimaksu. Zaradi tega dosežka se strateško ravnovesje imenuje tudi Nashevo ravnovesje.

Izrek: Vsaka končna igra n igralcev v strateški obliki ima vsaj eno strateško ravnovesje.

Ena od težav nekooperativne teorije je ta, da obstaja več ravnovesij, ki dajo različne vektorje dobitkov. Druga težava je, da čeprav obstaja edinstveno strateško ravnovesje, se ne smatra kot primerna rešitev ali predviden rezultat.

Torej na kratko: Nashevo ravnovesje je v teoriji iger niz strategij za igralce, kjer nobeden izmed njih ne more izboljšati svojega položaja oz. poplačila s strategijo, ki jo ponuja drugi igralec.

5. Primer: Zapornikova dilema

Zapornikova dilema je v teoriji iger igra z neničelno vsoto, v kateri nastopata dva igralca, zapornika.

Policija je aretirala dva človeka A in B, ki sta osumljena, da sta skupaj zagrešila rop (zločin) in ju zaprla v ločeni celici. Ni jima dovoljeno, da bi komunicirala drug z drugim. Dejansko sta zločin tudi zagrešila, policija pa tega ne more dokazati. Policija ima dovolj podatkov za 6-mesečno kazen (posedovanje orožja, manjši prekrški), želi pa dokončno zaključiti primer s priznanjem, ki bi vsaj enega za dalj časa poslalo v ječo, vendar bi moral vsaj eden priznati. Oba vesta naslednje:

• Lahko ali priznaš, da si storil zločin, ali pa ne priznaš.
• Če eden od vaju prizna, drugi pa ne, potem je tisti, ki je priznal, izpuščen; tisti, ki pa ni priznal, bo šel v ječo za 10 let.
• Če oba priznata, potem bosta oba šla v ječo za dve leti.
• Če nobeden od vaju ne prizna, potem imamo dovolj podatkov, da dobita oba po 6 mesecev.

Kaj naj storita? Ali se splača izdati drugega?

	B molči	B izda
A molči	(0.5, 0.5)	(10, 0)
A izda	(0, 10)	(2, 2)

Vsak želi čim bolj zmanjšati svojo kazen. S stališča posameznika se je bolje izdati, ker je kazen manjša, ne glede na odločitev drugega. Ker pa je tako najbrž razmišljal tudi drugi igralec, se zgodi, da drug drugega obtožita, za kar dobita 2 leti zapora, če pa bi molčala, bi dobila le pol leta. Za oba skupaj bi bilo najugodneje, če bi se dogovorila in molčala, vendar je to lahko tudi nevarno, če kateri od zapornikov ne drži besede in spregovori.

Poizkusi se v igri zapornikova dilema proti računalniku:

Drugi zapornik se je že odločil, ali te bo izdal ali ne. Odloči se še ti: Bom izdal        Ne bom izdal Oba sta molčala, zato dobita vsak po 6 mesecev zapora! Drug zapornik te je izdal, zato bo on izpuščen, ti pa boš odsedel 10 let! Drug zapornik je molčal, zato boš ti izpuščen, on pa bo odsedel 10 let! Oba sta se izdala, zato dobita vsak po 2 leti zapora! Za tiste, ki tega ne bi opazili: ko se odločiš za eno izmed možnosti (Bom izdal, Ne bom izdal), ne dobiš vedno za isto možnost enakega odgovora, saj je odgovor odvisen tudi od drugega "zapornika" (računalnika), kako se odloči on (te bo izdal ali ne). Poskusi in videl boš, da odgovor ni vedno enak!

Naloži si igro zapornikova dilema!

6. Vprašanja za samopreverjanje

Podana je bimatrika:

( ) (-1,1) (0,2) (0,2) (2,1) (1,-1) (0,0) (0,0) (1,1) (1,2)

Izračunaj varen nivo v_I za igralca I, varen nivo v_II za igralca II in maxmin strategiji za oba igralca! Poišči še čimveč strateških ravnovesij!

Poglej rešitev Skrij rešitev

7. Povezave na dopolnilne vsebine na spletu:

http://roso.epfl.ch/fukuda/lect/polyex_handout/expoly4b.pdf

http://dissertations.ub.rug.nl/faculties/non-rug/1993/a.p.jurg/

http://www.stanford.edu/class/msande316/slides/050404.pdf

http://web.mit.edu/jnt/www/Papers/J021-88-strat-elim.pdf

http://www.everything2.com/title/bimatrix%2520game

http://www.math.ucla.edu/~tom/Game_Theory/Contents.html

8. Vir

http://www.math.ucla.edu/~tom/Game_Theory/bimat.pdf

Definicija: Matrično igro definiramo tako:

A ∈ ℜ ^m×n

je matrika igre. Če prvi igralec izbere vrstico i in drugi igralec izbere stolpec j, potem je element a_ij vrednost, ki jo dobi prvi igralec od drugega (če je vrednost negativna (npr. -3), to pomeni, da mora prvi igralec drugemu dati toliko (v tem primeru mu mora dati 3)).

Primer: Igra móra (morra)

Igro igrata dva igralca. Vsak skrije enega ali dva kovanca in na glas skuša uganiti, koliko je skril nasprotnik. Če eden ugane, dobi od drugega toliko kovancev, kot sta jih skrila skupaj. Če pa uganeta oba ali nobeden, je neodločeno. Možne poteze so:

	[1 1]	[2 1]	[1 2]	[2 2]
[1 1]	0	-3	2	0
[2 1]	3	0	0	-4
[1 2]	-2	0	0	3
[2 2]	0	4	-3	0

Pri tem [] pomeni: [koliko skrije, koliko ugiba].

Definicija: Igra je simetrična, če velja: A = -A^T.

Koliko si lahko prvi igralec zagotovi pri vsaki igri?

A := max1≤i≤mmin1≤j≤naij

Tu A pomeni neko konstanto, ne matrike A!!!

Koliko si lahko drugi igralec zagotovi pri vsaki igri?

B := min1≤j≤nmax1≤i≤maij

Velja: A ≤ B

Dokaz:	aij ≤ maxiaij
	minjaij ≤ minjmaxiaij
	maximinjaij ≤ minjmaxiaij

Definicija: A = B: sedlo matrike.

Dominiranost:
    1. igralec: Če je i-ta vrstica po komponentah večja ali enaka od j-te vrstice, potem obstaja optimalna strategija prvega igralca, ki ne uporablja j-te vrstice.
    2. igralec: Če je i-ti stolpec po komponentah manjši ali enak od j-tega stolpca, potem obstaja optimalna strategija drugega igralca, ki ne uporablja j-tega stolpca.

Poglejmo si sedaj lastnosti igre za prvega igralca (za drugega je analogno):

Želimo čim večji pričakovani dobiček v dolgem zaporedju iger:

    Mešane verjetnostne strategije:
            vektor x ∈ ℜ ^m (za prvega igralca)
            stohastični vektor: x ≥ 0; ∑x_i = 1
            Z verjetnostjo x_i izberemo vrstico i.

    Pričakovani dobiček pri uporabi strategije x:
            Naj bodo y₁, …, y_n relativne frekvence, s katerimi je v zaporedju iger stolpce izbiral nasprotnik.
            Pričakovani dobiček je x^TAy.
            Prvi igralec dobi v povprečju vsaj

d(x) := min_yx^TAy, (y je stohastični vektor)

Želimo max_xd(x) (strategija, ki doseže ta maksimum, je optimalna strategija).

Trditev: Za vsako mešano strategijo x ima 2. igralec čisto strategijo, ki mu v povprečju zagotavlja najmanjšo možno izgubo, tj.

d(x) = minyxTAy = min1≤j≤n∑i=1maijxi = min1≤j≤nxTAy(j)

kjer y^(j) pomeni vektor [0 … 0 1 0 … 0], kjer je 1 na j-tem mestu.

Dokaz:	Naj bo t := min1≤j≤nxTAy(j)
	Vemo: d(x) ≤ t, treba pa je videti: d(x) ≥ t!
	Treba je pokazati, da je x stohastični vektor, torej: xTAy ≥ t za ∀y:
	xTAy = yTATx = ∑j=1nyj(ATx)j = ∑j=1nyj(∑i=1maijxi) ≥ t∑j=1nyj = t       KONEC DOKAZA
	Pri tem smo upoštevali: yj ≥ 0, ∑i=1maijxi ≥ t in t∑j=1nyj = 1.

Sedaj iščemo:	maxxd(x) = maxxminj∑i=1maijxi
	p.p. (pri pogoju) ∑i=1mxi = 1
	xi ≥ 0, i = 1, …, m

Vpeljemo novo spremenljivko w:

max w
p.p.	w ≤ ∑i=1maijxi, j = 1, …, n
	∑i=1mxi = 1, x ≥ 0

Ti dve nalogi sta enakovredni optimizacijski nalogi!

Dokaz:	(⇒) Rešimo prvo nalogo. Dobimo x. Definiramo w kot min… Dobimo dopustno rešitev za drugo nalogo, vrednosti kriterijskih funkcij se ujemata.
	(⇐) Vzamemo optimalno rešitev druge naloge. Potem v pogojih za w velja vsaj en enačaj (sicer ni optimalno) (*). x je dopusten tudi za prvo nalogo, vrednost kriterijske funkcije je na (*) enaka.

Opomba: Linearni program ima vedno optimalno rešitev (dopustne rešitve obstajajo, je omejen).

Zgled: w* = 0, x* = [0, ²/₅ , ³/₅ , 0]^T

Analogno dobimo lastnosti igre za drugega igralca:

Trditev: d'(y) = max_xx^TAy = max_1≤i≤mx^(i)TAy
kjer x^(i)T pomeni vektor [0 … 0 1 0 … 0]^T, kjer je 1 na i-tem mestu.

Nova spremenljivka je z:

min z
p.p.	z ≥ ∑j=1naijyj, i = 1, …, m
	∑j=1nyj = 1, y ≥ 0

To je optimalna strategija za drugega igralca.

Trditev: Linearni program za optimalno strategijo za 2. igralca je dual linearnega programa za optimalno strategijo za 1. igralca.

Torej: w* = z* je vrednost igre.
Pomeni: w* … koliko prvi dobi, z* … koliko drugi izgubi.
Če w* = z* = 0 ⇒ poštena igra.

Izrek:(o minimaksu) Za vsako matriko A ∈ ℜ ^m×n obstajata stohastična vektorja x ∈ ℜ ^m in y ∈ ℜ ⁿ, za katera velja: min_yx^TAy = max_xx^TAy, pri čemer min/max teče po vseh stohastičnih vektorjih y oz. x.

(x in y obstajata (sta določena), x in y sta poljubna)

Vir:

Martin Juvan. Predavanja iz Kombinatorične optimizacije. Fakulteta za matematiko in fiziko, Ljubljana, šolsko leto 2006/2007.