Algojáték 3. gyakorlat megoldókulcs
Javaslat
A megoldásokat ne nézd meg rögtön, előbb szánj egy kis időt az önálló gondolkodásra és az ötletelésre! A problémamegoldás képessége olyan mint egy izom: mindenkiben fejleszthető. Ezek a feladatok pontosan ebben segítenek. Ha teljesen elakadnál, ott a hint.1. feladat
Fogolydilemma: Egy súlyos bűntény kapcsán letartóztat két gyanúsítottat a rendőrség. A vádemeléshez nincs elegendő bizonyíték, ezért elkülönítik őket egymástól és mindkettejüknek ugyanazt az ajánlatot teszik. Ha vallomást tesznek, miközben a társuk hallgat, akkor szabadon engedik őket, a társuk pedig 10 év börtönt kap. Ha mindketten vallanak, akkor fejenként 6 évet kapnak. Ha mindketten hallgatnak, akkor egy kisebb bűntényért fejenként 6 hónapot kapnak.
a) Adjuk meg ennek a stratégiai játéknak a nyereségmátrixát!
b) Határozzuk meg a tiszta Nash-egyensúlyokat a játékban.
c) Határozzuk meg a Pareto-optimális stratégiaválasztásokat a játékban.
Hint
A nyereségmátrix sorai felelnek meg az egyik, az oszlopai a másik játékos stratégiaválasztásainak. A cellákba $(a,b)$ párokat írunk, ahol $a$ a sorjátékos, $b$ az oszlopjátékos kifizetése az adott stratégiaválasztásra.
A tiszta Nash-egyensúlyok megkereséséhez az egyes játékosok legjobb válaszait csillagozzuk meg a másik játékos adott stratégiájával szemben. Amelyik cellába mindkét játékos tett csillagot, az tiszta Nash-egyensúly.
A Pareto-optimális stratégiaválasztások megkereséséhez minden cellapárt megnézünk, hogy az egyik Pareto-dominálja-e a másikat. Pareto-optimális minden amit nem Pareto-dominál senki.
Megoldás
A nyereségmátrix a következő.
| B vall | B tagad | |
| A vall | (-6*, -6*) | (0*, -10) |
| A tagad | (-10, 0*) | (-0.5, -0.5) |
Tiszta Nash-egyensúly kereséséhez mindkét játékos megvizsgálja a saját kifizetéseit. A sorjátékos minden oszlopban megjelöli $*$-al a maximális értéket tartalmazó cellá(ka)t. Az oszlopjátékos ugyanezt teszi a sorokban. Tiszta Nash-egyensúly minden olyan cella, amit mindketten megjelöltek.
Gondoljuk meg ez miért igaz: Ha egy olyan cellában vagyunk, amit valaki nem jelölt meg, akkor az a játékos a saját döntésének megváltoztatásával el tudna jutni egy másik, általa megjelölt cellába, amivel javíthatna a saját kifizetésén.
A fenti mátrixban látható $*$-ozás alapján az (A vall, B vall) az egyetlen tiszta Nash-egyensúly a játékban.
Pareto-optimális stratégiaválasztás minden olyan, amit nem Pareto-dominál másik. Összesen $6$ cellapárt kell megvizsgálni, egyedül az (A vall, B vall) stratégiaválasztást Pareto-dominálja az (A tagad, B tagad), hiszen minden játékos legalább ugyanolyan jól jár és van olyan aki jobban jár az (A tagad, B tagad) esetben. Tehát Pareto-optimálisak az (A tagad, B tagad), az (A vall, B tagad) és az (A tagad, B vall).
2. feladat
Egy kétszemélyes, zéróösszegű játékban a sorjátékos kifizetéseit az alábbi $A$ mátrix adja meg. Ennek az $i$. sor, $j$. oszlopbeli $a_{i,j}$ cellája azt a kifizetést jelöli, amelyet a sorjátékos kap, ha ő a saját $i$. stratégiáját, az oszlopjátékos pedig a saját $j$. stratégiáját választja.
$$A=\begin{pmatrix} 5 & 4 & 1 & 0\\ 4 & 3 & 2 & -1\\ 0 & -1 & 4 & 3\\ 1 & -2 & 1 & 2 \end{pmatrix}$$a) Végezzük el a mátrixon az iterált szigorú eliminálást!
b) Van-e tiszta Nash-egyensúly az eliminálás után kapott játékban? És az eredetiben?
Hint
Egy adott sor/oszlop szigorú eliminálásához kell egy másik sort/oszlopot találni, amiben a sor/oszlop-játékos kifizetései minden cellában szigorúan nagyobbak.
A fenti mátrix a sorjátékos kifizetéseit tartalmazza, tehát vagy észben tartjuk, hogy az oszlopjátékos kifizetései ennek a $(-1)$-szeresei (azaz pont a nagyobbik oszlopot kell mindig törölni) vagy csak felírjuk azokat is külön.
Megoldás
A szigorú elimináláshoz bőven elég az eredeti $A$ mátrixot használni, pusztán arra kell figyelni hogy oszlopok esetében a kisebb számok a dominálók. Annak, akinek ez még nehezen követhető álljon itt a teljes nyereségmátrix.
| o1 | o2 | o3 | o4 | |
| s1 | (5, -5) | (4, -4) | (1, -1) | (0, 0) |
| s2 | (4, -4) | (3, -3) | (2, -2) | (-1, 1) |
| s3 | (0, 0) | (-1, 1) | (4, -4) | (3, -3) |
| s4 | (1, -1) | (-2, 2) | (1, -1) | (2, -2) |
Az $o2$ stratégia erősen dominálja az $o1$-et:
| o2 | o3 | o4 | |
| s1 | (4, -4) | (1, -1) | (0, 0) |
| s2 | (3, -3) | (2, -2) | (-1, 1) |
| s3 | (-1, 1) | (4, -4) | (3, -3) |
| s4 | (-2, 2) | (1, -1) | (2, -2) |
Az $s3$ stratégia erősen dominálja az $s4$-et.
| o2 | o3 | o4 | |
| s1 | (4, -4) | (1, -1) | (0, 0) |
| s2 | (3, -3) | (2, -2) | (-1, 1) |
| s3 | (-1, 1) | (4, -4) | (3, -3) |
Az $o4$ stratégia erősen dominálja az $o3$-mat.
| o2 | o4 | |
| s1 | (4, -4) | (0, 0) |
| s2 | (3, -3) | (-1, 1) |
| s3 | (-1, 1) | (3, -3) |
Az $s1$ stratégia erősen dominálja az $s2$-t.
| o2 | o4 | |
| s1 | (4, -4) | (0, 0) |
| s3 | (-1, 1) | (3, -3) |
Más erős dominancia nincs. Megcsillagozzuk az egyes játékosok legjobb válaszát a másik játékos adott stratégiájára.
| o2 | o4 | |
| s1 | (4*, -4) | (0, 0*) |
| s3 | (-1, 1*) | (3*, -3) |
Mivel nincs olyan cella, amelyre mindkét játékos tett volna csillagot, ezért nincs tiszta Nash-egyensúly a játékban.
Mivel az erős dominálás nem változtat a tiszta Nash-egyensúlyok halmazán (nem tűnik el meglévő, nem jön létre új), ezért az eredeti játékban sem lehetett tiszta Nash-egyensúly.
3. feladat
Tószennyezés: Egy tó köré épült három gyár dönt arról, hogy szennyezzék vagy tisztítsák-e a tó vizét a következő évben. A vizet szennyezni ingyenes, a tisztítás azonban 1 egységnyi pénzbe kerül. Továbbá, ha legalább két gyár szennyez, akkor a tó vize súlyosan elszennyeződik, és minden gyárnak külön-külön 3 egységnyi pénzbüntetést kell fizetnie.
a) Határozzuk meg a tiszta Nash-egyensúlyokat a játékban.
b) Határozzuk meg a Pareto-optimális stratégiaválasztásokat a játékban.
Hint
Itt most egy $(2 \times 2 \times 2)$-es táblázatot kell felírni. Praktikusan például két darab $(2 \times 2)$-es mátrixot lehet felírni, amiből az egyik a harmadik gyár szennyez stratégiájához, a másik pedig a tisztít stratégiájához tartozik.
Megoldás
| szennyez | tisztít | |
| szennyez | (-3*, -3*, -3*) | (-3, -4, -3) |
| tisztít | (-4, -3, -3) | (-1*, -1*, 0*) |
| szennyez | tisztít | |
| szennyez | (-3, -3, -4) | (0*, -1*, -1*) |
| tisztít | (-1*, 0*, -1*) | (-1, -1, -1) |
A tiszta Nash-egyensúlyok meghatározásához minden játékos megcsillagozza a legjobb válaszait és amire mindenki tett csillagot az tiszta Nash-egyensúly. Ezek pontosan azok a stratégiaválasztások, ahol mindenki szennyez, illetve ahol az egyik gyár szennyez, a másik kettő pedig tisztít.
Azok a cellák lesznek Pareto-optimálisak, ahol valaki szennyez és a másik kettő tisztít. Ezek bármelyike Pareto-dominálja azokat a cellákat, ahol legalább ketten szennyeznek, illetve azt is ahol mindhárman tisztítanak. Más Pareto-dominancia pedig nincs.
4. feladat
Mutassunk példát olyan legalább 2x2-es stratégiai játékra, melynek a nyereségmátrixában minden kifizetés-vektor különböző, de az iterált laza eliminálás után akármelyik stratégiaválasztás megmaradhat benne egyetlenként.
Hint
Ha valaki, például a sorjátékos kifizetései minden oszlopban azonosak akkor a laza eliminálás során mi történhet?
Megoldás
Legyenek a sorjátékos kifizetései azonosak minden oszlopban és az oszlopjátékos kifizetései azonosak minden sorban. Ekkor az iterált laza eliminálás bármely sort, illetve oszlopot eliminálhatja a másikkal.
| bal | jobb | |
| fel | (1, 1) | (2, 1) |
| le | (1, 2) | (2, 2) |
5. feladat
Választás: Egy választáson két jelölt indul, $A$ és $B$, a választók száma pedig $n \in \mathbb{N}_+$. Minden választónak 2 pontot ér, ha az ő támogatottja nyer, $-2$ pontot ér, ha a támogatottja veszít, és 0 pontot ér, ha a választás döntetlennel zárul. Ezen felül minden választónak 1 pontjába kerül elmenni szavazni.
a) Határozzuk meg a tiszta Nash-egyensúlyokat, ha $n=2$ választó van, és közülük az egyik $A$-t, a másik pedig $B$-t támogatja.
Megoldás
Az egyetlen tiszta Nash-egyensúly az, amikor mindenki elmegy választani.
| elmegy | nem megy el | |
| elmegy | (-1*, -1*) | (1*, -2) |
| nem megy el | (-2, 1*) | (0, 0) |
b) Határozzuk meg a tiszta Nash-egyensúlyokat, ha $n=3$ választó van, és közülük ketten $A$-t támogatják, a harmadik pedig $B$-t.
Megoldás
Legyen $a_1$ és $a_2$ az $A$-t támogató szavazók, $b$ pedig a $B$-t támogató.
| $a_2$ elmegy szavazni | $a_2$ otthon marad | |
| $a_1$ elmegy szavazni | (1*, 1*, -3) | (-1*, 0, -1*) |
| $a_1$ otthon marad | (0, -1*, -1*) | (-2, -2, 1*) |
| $a_2$ elmegy szavazni | $a_2$ otthon marad | |
| $a_1$ elmegy szavazni | (1, 1, -2*) | (1*, 2*, -2) |
| $a_1$ otthon marad | (2*, 1*, -2) | (0, 0, 0) |
6. feladat
Két diák csoportmunkában házi feladatot ír. A leadás előtti napon mindkét diák egyénileg választ: elmegy a házi feladaton dolgozni a könyvtárba, vagy inkább bulizni megy a barátokkal.
- Ha legalább az egyikük dolgozik, akkor a feladat hibátlanul elkészül ami mindkettőjüknek fejenként $10$ pontnyi örömet szerez. Ha egyikük sem dolgozik, akkor a feladat nem készül el és ezért mindketten fejenként $-2$ pontot kapnak.
- Ezen felül az egyedül végzett munka $-7$ pontot ér az erőfeszítés miatt, a közös munka mindkettőjüknek fejenként $-2$ pontba kerül.
- A bulizásért kapott pontot egy $p \in \mathbb{R}$ paraméter határozza meg.
Hint
A nyereségmátrix celláiban most lesz egy $p$ paraméter. Minden cellapárra meg kell nézni, hogy a $p$ értékétől függően dominálhatja-e az egyik a másikat.
Megoldás
| HF | buli | |
| HF | (8, 8) | (3, p+10) |
| buli | (p+10, 3) | (p-2, p-2) |
Ha $p \lt -2$, akkor a (HF, HF) az egyetlen Pareto-optimális stratégiaválasztás. Ha $-2 \le p \lt 10$, akkor a (buli, buli) kivételével minden stratégiaválasztás Pareto-optimális. Ha $p=10$, akkor minden stratégiaválasztás Pareto-optimális. Ha $p > 10$, akkor a (HF, HF) kivételével minden stratégiaválasztás Pareto-optimális.
7. feladat
Mutassuk meg, hogy bármely $A$ és $B$ nyereségmátrixszal adott kétszemélyes stratégiai játékhoz megadható egy olyan $C$ nyereségmátrixú kétszemélyes stratégiai játék, amiből az $A$, illetve a $B$ nyereségmátrixú játékok bármelyike megkapható laza eliminálások ismételt alkalmazásával.
Hint
A 4. feladat ötletéből érdemes kiindulni.
Megoldás
Sor- illetve oszlopduplikálással elérhető, hogy $A$ és $B$ mérete megegyezzen. Legyen $A_1$, illetve $B_1$ a sorjátékoshoz tartozó nyereségek mátrixa, és legyen $A_2$, illetve $B_2$ az oszlopjátékoshoz tartozó nyereségek mátrixa. Vagyis $A = (A_1, A_2)$ és $B=(B_1, B_2)$. Legyen $$C = \left( \begin{array}{cc} (A_1, A_2) & (B_1, A_2) \\ (A_1, B_2) & (B_1, B_2) \\ \end{array} \right)$$
Ebben a mátrixban a négy sarok bármelyike megkapható laza eliminálásokkal, hiszen a sorjátékos szemszögéből a mátrix felső és alsó fele ugyanaz, az oszlopjátékos szemszögéből pedig a bal és a jobb fele.
8. feladat
Tegyük fel, hogy a Tószennyezés játékban a 3. gyár tudja a másik két gyárról, hogy azok egymástól függetlenül $p$ valószínűséggel döntenek úgy, hogy tisztítják a tó vizét. Határozzuk meg minden $p \in [0,1]$ értékre, hogy ekkor milyen döntéssel jár jobban a 3. gyár.
(Pöttyös feladat, azzal a megjegyzéssel, hogy azért, mert ezen a héten még nem tanultuk a kevert Nash-egyensúlyokat.)9. feladat
Határozzuk meg a Választás játékban tetszőleges $n = 2k$ esetén a tiszta Nash-egyensúlyokat, ha $k$ darab választó az $A$-t, a maradék $k$ darab pedig a $B$-t támogatja.
(Pöttyös feladat.)10. feladat
Közlegelők tragédiája: Egy falu melletti legelőn tíz gazda legelteti egy-egy tehenét. Kezdetben mindegyik tehén jóllakik és napi 10 liter tejet ad. Mindegyik gazdának van elég pénze, hogy vegyen egy új tehenet és azt is kihajtsa a legelőre. Mindegyik gazda eldöntheti, hogy megteszi-e ezt vagy sem. Minnél több tehén van a legelőn, annál kevesebb tejet adnak fejenként: ha a tehenek száma $k \in \{10, 11, \dots, 20\}$, akkor mindegyik tehén napi $(20-k)$ liter tejet ad. Egy gazda kifizetése megegyezik a birtokában lévő tehén vagy tehenek napi össztermelésével.
a) Határozzuk meg a tiszta Nash-egyensúlyokat a játékban.
b) Határozzuk meg a Pareto-optimális stratégiaválasztásokat a játékban.
(Pöttyös feladat.)