Algojáték 5. 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
Az alábbi mátrixok az oszlopjátékos nyereségeit írják le egy-egy 0-összegű stratégiai játékban.
a) Írjuk fel az oszlopjátékos maximin stratégiáit leíró lineáris programozási feladatot.
b) Írjuk fel a sorjátékos maximin stratégiáit leíró lineáris programozási feladatot.
c) Határozzuk meg a játékosok maximin stratégiáit.
(i)
$\begin{pmatrix} 1 & 3 \\ 4 & 2 \end{pmatrix}$Hint
Az oszlopjátékos maximin stratégiáját úgy kapjuk, hogy maximalizáljuk a garantált várható nyereségét, vagy más néven a biztonsági szintjét ($\alpha$). Legyenek $x_1, x_2$ változók, amik az oszlopjátékos kevert stratégiájának az eloszlását leírják. Egyrészt ki kell kényszeríteni, hogy ez valóban eloszlás legyen, másrészt minden sorhoz tartozik egy feltétel: az adott sor ellen játszva legalább $\alpha$ várható nyereséget kell kapnia. Ekkor bárhogyan is keveri a sorjátékos a stratégiáját, az oszlopjátékos nyeresége nem tud az $\alpha$ alá menni.
A sorjátékos maximin stratégiáját úgy kapjuk, hogy minimalizáljuk a garantált várható veszteségét, vagyis a biztonsági szintjének a $(-1)$-szeresét ($\beta$). Legyenek $y_1, y_2$ változók, amik a sorjátékos kevert stratégiájának az eloszlását leírják. Egyrészt ki kell kényszeríteni, hogy ez valóban eloszlás legyen, másrészt minden oszlophoz tartozik egy feltétel: az adott oszlop ellen játszva legfeljebb $\beta$ várható veszteséget szenvedhet el. Ekkor bárhogyan is keveri az oszlopjátékos a stratégiáját, a sorjátékos vesztesége nem tud a $\beta$ fölé menni.
A Neumann-tételből következik, hogy a kétszemélyes zéróösszegű játékokban a maximin stratégiák pontosan a kevert Nash-egyensúlyoknak felelnek meg, hiszen mindkét játékos a saját garantált nyereségét önerőből garantálni tudja. Mivel zéróösszegű a játék, bármely más kevert stratégiaválasztásban az egyik játékos rosszul fog járni a saját maximin stratégiája által garantált értékhez képest, tehát megéri neki a maximinre váltani. Ha pedig mindketten maximint játszanak, akkor hiába vált valaki, ha a maradó játékos továbbra is maximint játszik akkor a maradó játékos értéke továbbra is garantálva van, a zéróösszegűség miatt pedig ez azt jelenti hogy a váltó játékos csak ugyanolyan jól vagy rosszabbul járhat.
Kevert Nash-egyensúlyt pedig 2x2-es játékban már nagyon jól tudunk a geometriai módszerrel számolni.
Megoldás
a) Oszlopjátékos lineáris programozási feladata:
Egyrészt kikényszerítjük, hogy az $x_1, x_2$ valóban eloszlás: $$x_1, x_2 \geq 0$$ és $$x_1+x_2 = 1$$.
Továbbá a sorjátékos minden sorára kikényszerítjük, hogy ha ő azt a sort játssza, az oszlopjátékos garantált várható nyeresége nem mehet az $\alpha$ biztonsági szint alá: $$x_1 + 3x_2 \geq \alpha$$ és $$4x_1 + 2x_2 \geq \alpha$$. Ezzel a sorjátékos bármely kevert stratégiájára is garantáltuk az oszlopjátékosnak az $\alpha$ várható nyereséget.
Végezetül a célfüggvény az $\alpha$ érték maximalizálása.
Összesítve: $$\begin{array}{rl} \max & \alpha \\ \text{feltéve:} & x_1 + 3x_2 \geq \alpha \\ & 4x_1 + 2x_2 \geq \alpha \\ & x_1 + x_2 = 1 \\ & x_1, x_2 \geq 0 \end{array}$$
b) Sorjátékos lineáris programozási feladata:
Egyrészt kikényszerítjük, hogy az $y_1, y_2$ valóban eloszlás: $$y_1, y_2 \geq 0$$ és $$y_1+y_2 = 1$$.
Továbbá az oszlopjátékos minden oszlopára kikényszerítjük, hogy ha ő azt az oszlopot játssza, a sorjátékos garantált várható vesztesége nem mehet a $\beta$ (biztonsági szint $(-1)$-szerese) fölé: $$y_1 + 4y_2 \leq \beta$$ és $$3y_1 + 2y_2 \leq \beta$$. Ezzel az oszlopjátékos bármely kevert stratégiájára is garantáltuk a sorjátékosnak a $\beta$ várható veszteséget.
Végezetül a célfüggvény a $\beta$ érték minimalizálása.
Összesítve: $$\begin{array}{rl} \min & \beta \\ \text{feltéve:} & y_1 + 4y_2 \leq \beta \\ & 3y_1 + 2y_2 \leq \beta \\ & y_1 + y_2 = 1 \\ & y_1, y_2 \geq 0 \end{array}$$
c) Maximin stratégiák meghatározása:
Mivel 0-összegű játékról van szó, a Neumann-tétel szerint a maximin stratégiák pontosan a kevert Nash-egyensúlyoknak felelnek meg. Használjuk a geometriai módszert a kevert Nash-egyensúlyok meghatározására. Fontos, hogy a fenti mátrix most az oszlopjátékos nyereségeit tartalmazza!
A piros és kék vonalak metszéspontja adja a kevert Nash-egyensúlyt. Ez jelen esetben a $(p,q) = (\frac{1}{2}, \frac{1}{4})$.
Tehát:
- Az oszlopjátékos maximin stratégiája: $\underline{x} = (\frac{1}{4}, \frac{3}{4})^{\top}$
- A sorjátékos maximin stratégiája: $\underline{y} = (\frac{1}{2}, \frac{1}{2})$
Ellenőrzés:
(Ez már nem kell a teljes értékű megoldáshoz, pusztán a Neumann-tétel működésének szemléltetésére tettük ide.)
Nyilván ezek eloszlások, ezt nem kell külön ellenőrizni.
Behelyettesítünk az oszlopjátékosnál: $$x_1+3x_2 = \frac{1}{4} + 3\cdot\frac{3}{4} = \frac{10}{4} = 2,5 \geq \alpha$$, $$4x_1 + 2x_2 = 4\cdot\frac{1}{4} + 2\frac{3}{4} = \frac{10}{4} = 2,5 \geq \alpha$$.
Tehát az az $\alpha$, ami minden kényszert kielégít és emellett maximális az $\alpha = 2,5$. (Figyelem, a kényszerekből nem feltétlen fognak ugyanazok a számok kipottyanni felső korlátként, erre később látunk példát!)
Behelyettesítünk a sorjátékosnál: $$y_1+4y_2 = \frac{1}{2} + 4\cdot\frac{1}{3} = \frac{5}{2} = 2,5 \leq \beta$$, $$3y_1 + 2y_2 = 3 \cdot \frac{1}{2} + 2 \cdot \frac{1}{2} = \frac{5}{2} = 2,5 \leq \beta$$.
Tehát az a $\beta$, ami minden kényszert kielégít és emellett minimális a $\beta = 2,5$.
Látható, hogy valóban $\alpha = \beta$, azaz ezek tényleg maximin stratégiák.(ii)
$\begin{pmatrix} 2 & 3 & 1 & 5 \\ 4 & 1 & 6 & 0 \end{pmatrix}$Hint
a), b): Az LP feladatokat az eredeti mátrixon írjuk fel, hiszen azt bárhány változóra fel lehet.
c): Iterált szigorú eliminálásokkal csináljuk 2x2-es mátrixot a feladatból, amire már alkalmazható a geometriai módszer.
Megoldás
a) és b) LP feladatok:
Oszlopjátékos LP-je:
$\begin{array}{rl} \max & \alpha \\ \text{feltéve:} & 2x_1 + 3x_2 + x_3 + 5x_4 \geq \alpha \\ & 4x_1 + x_2 + 6x_3 + 0x_4 \geq \alpha \\ & x_1 + x_2 + x_3 + x_4 = 1 \\ & x_1, x_2, x_3, x_4 \geq 0 \end{array}$Sorjátékos LP:
$\begin{array}{rl} \min & \beta \\ \text{feltéve:} & 2y_1 + 4y_2 \leq \beta \\ & 3y_1 + y_2 \leq \beta \\ & y_1 + 6y_2 \leq \beta \\ & 5y_1 + 0y_2 \leq \beta \\ & y_1 + y_2 = 1 \\ & y_1, y_2 \geq 0 \end{array}$c) Maximin stratégiák:
Szigorú eliminálás:
Kezdetben a mátrix:| $o_1$ | $o_2$ | $o_3$ | $o_4$ | |
| $s_1$ | 2 | 3 | 1 | 5 |
| $s_2$ | 4 | 1 | 6 | 0 |
Az $o_1$ stratégiát például a $\frac{7}{10}\chi_{o_3} + \frac{3}{10}\chi_{o_4}$-el, az $o_2$ stratégiát pedig például az $\frac{1}{3}\chi_{o_3} + \frac{2}{3}\chi_{o_4}$-el eliminálhatjuk.
| $o_3$ | $o_4$ | |
| $s_1$ | 1 | 5 |
| $s_2$ | 6 | 0 |
A piros és kék vonalak metszéspontja adja a kevert Nash-egyensúlyt. Ez jelen esetben a $(p,q) = (\frac{3}{5}, \frac{1}{2})$.
Tehát:
- Az oszlopjátékos maximin stratégiája: $\underline{x} = (0, 0, \frac{1}{2}, \frac{1}{2})^{\top}$
- A sorjátékos maximin stratégiája: $\underline{y} = (\frac{3}{5}, \frac{2}{5})$
Ellenőrzés:
(Ez már nem kell a teljes értékű megoldáshoz, pusztán a Neumann-tétel működésének szemléltetésére tettük ide.)
Nyilván ezek eloszlások, ezt nem kell külön ellenőrizni.
Behelyettesítünk az oszlopjátékosnál: $$2x_1 + 3x_2 + x_3 + 5x_4 = 0 + 0 + \frac{1}{2} + \frac{5}{2} = 3 \geq \alpha$$, $$4x_1 + x_2 + 6x_3 + 0x_4 = 0 + 0 + 3 + 0 = 3 \geq \alpha$$.
Tehát az az $\alpha$, ami minden kényszert kielégít és emellett maximális az $\alpha = 3$.
Behelyettesítünk a sorjátékosnál: $$2y_1 + 4y_2 = 2 \cdot \frac{3}{5} + 4 \cdot \frac{2}{5} = \frac{6}{5} + \frac{8}{5} = \frac{14}{5} = 2,8 \leq \beta$$, $$3y_1 + y_2 = 3 \cdot \frac{3}{5} + \frac{2}{5} = \frac{11}{5} = 2,2 \leq \beta$$, $$y_1 + 6y_2 = \frac{3}{5} + 6 \cdot \frac{2}{5} = \frac{15}{5} = 3 \leq \beta$$, $$5y_1 + 0y_2 = 5 \cdot \frac{3}{5} = 3 \leq \beta$$.
Tehát az a $\beta$, ami minden kényszert kielégít és emellett minimális a $\beta = 3$.
Látható, hogy valóban $\alpha = \beta$, azaz ezek tényleg maximin stratégiák.
(iii)
$\begin{pmatrix} 5 & 0 \\ 2 & 3 \\ 1 & 4 \\ 4 & 0 \\ 4 & -1 \end{pmatrix}$Megoldás
a) és b) LP feladatok:
Oszlopjátékos LP-je:
$$\begin{array}{rl} \max & \alpha \\ \text{feltéve:} & 5x_1 + 0x_2 \geq \alpha \\ & 2x_1 + 3x_2 \geq \alpha \\ & x_1 + 4x_2 \geq \alpha \\ & 4x_1 + 0x_2 \geq \alpha \\ & 4x_1 - x_2 \geq \alpha \\ & x_1 + x_2 = 1 \\ & x_1, x_2 \geq 0 \end{array}$$Sorjátékos LP:
$$\begin{array}{rl} \min & \beta \\ \text{feltéve:} & 5y_1 + 2y_2 + y_3 + 4y_4 + 4y_5 \leq \beta \\ & 0y_1 + 3y_2 + 4y_3 + 0y_4 - y_5 \leq \beta \\ & y_1 + y_2 + y_3 + y_4 + y_5 = 1 \\ & y_1, y_2, y_3, y_4, y_5 \geq 0 \end{array}$$c) Maximin stratégiák:
Szigorú eliminálás:
Kezdetben a mátrix:| $o_1$ | $o_2$ | |
| $s_1$ | 5 | 0 |
| $s_2$ | 2 | 3 |
| $s_3$ | 1 | 4 |
| $s_4$ | 4 | 0 |
| $s_5$ | 4 | -1 |
Az $s_1$ stratégiát például az $s_5$-el, az $s_2$ stratégiát például a $\frac{3}{4}\chi_{s_3} + \frac{1}{4}\chi_{s_5}$-el, az $s_4$-et pedig például az $\frac{1}{10}\chi_{s_3} + \frac{9}{10}\chi_{s_5}$-el eliminálhatjuk.
| $o_1$ | $o_2$ | |
| $s_3$ | 1 | 4 |
| $s_5$ | 4 | -1 |
A piros és kék vonalak metszéspontja adja a kevert Nash-egyensúlyt. Ez jelen esetben a $(p,q) = (\frac{5}{8}, \frac{5}{8})$.
Tehát:
- Az oszlopjátékos maximin stratégiája: $\underline{x} = (\frac{5}{8}, \frac{3}{8})^{\top}$
- A sorjátékos maximin stratégiája: $\underline{y} = (0, 0, \frac{5}{8}, 0, \frac{3}{8})$
Ellenőrzés:
(Ez már nem kell a teljes értékű megoldáshoz, pusztán a Neumann-tétel működésének szemléltetésére tettük ide.)
Nyilván ezek eloszlások, ezt nem kell külön ellenőrizni.
Behelyettesítünk az oszlopjátékosnál: $$5x_1 + 0x_2 = 5 \cdot \frac{5}{8} + 0 = \frac{25}{8} = 3,125 \geq \alpha$$, $$2x_1 + 3x_2 = 2 \cdot \frac{5}{8} + 3 \cdot \frac{3}{8} = \frac{10}{8} + \frac{9}{8} = \frac{19}{8} = 2,375 \geq \alpha$$, $$x_1 + 4x_2 = \frac{5}{8} + 4 \cdot \frac{3}{8} = \frac{5}{8} + \frac{12}{8} = \frac{17}{8} = 2,125 \geq \alpha$$, $$4x_1 + 0x_2 = 4 \cdot \frac{5}{8} = \frac{20}{8} = 2,5 \geq \alpha$$, $$4x_1 - x_2 = 4 \cdot \frac{5}{8} - \frac{3}{8} = \frac{20}{8} - \frac{3}{8} = \frac{17}{8} = 2,125 \geq \alpha$$.
Tehát az az $\alpha$, ami minden kényszert kielégít és emellett maximális az $\alpha = 2,125$.
Behelyettesítünk a sorjátékosnál: $$5y_1 + 2y_2 + y_3 + 4y_4 + 4y_5 = 0 + 0 + \frac{5}{8} + 0 + 4 \cdot \frac{3}{8} = \frac{5}{8} + \frac{12}{8} = \frac{17}{8} = 2,125 \leq \beta$$, $$0y_1 + 3y_2 + 4y_3 + 0y_4 - y_5 = 0 + 0 + 4 \cdot \frac{5}{8} + 0 - \frac{3}{8} = \frac{20}{8} - \frac{3}{8} = \frac{17}{8} = 2,125 \leq \beta$$.
Tehát az a $\beta$, ami minden kényszert kielégít és emellett minimális a $\beta = 2,125$.
Látható, hogy valóban $\alpha = \beta$, azaz ezek tényleg maximin stratégiák.
2. feladat
Alább látható egy kétszemélyes, 0-összegű stratégiai játék oszlopjátékosra vonatkozó nyereségmátrixa. Mutassuk meg, hogy az $\underline{x} = (7/8, 0, 1/8)^{\top}$ az oszlopjátékos, és az $\underline{y} = (1/4, 3/4, 0)$ a sorjátékos egy maximin stratégiája.
$$\begin{pmatrix} 3 & 7 & 27 \\ 7 & 5 & -1 \\ 6 & \pi & 8 \end{pmatrix}$$Hint
Ha felírjuk az oszlop- és sorjátékos maximin LP-jeit, behelyettesítjuk a megadott kevert stratégiákat és az jön ki, hogy $\alpha = \beta$, akkor azok a Neumann-tétel értelmében maximin stratégiák kell, hogy legyenek.
Megoldás
Oszlopjátékos LP-je:
$$\begin{array}{rl} \max & \alpha \\ \text{feltéve:} & 3x_1 + 7x_2 + 27x_3 \geq \alpha \\ & 7x_1 + 5x_2 - x_3 \geq \alpha \\ & 6x_1 + \pi x_2 + 8x_3 \geq \alpha \\ & x_1 + x_2 + x_3 = 1 \\ & x_1, x_2, x_3 \geq 0 \end{array}$$Sorjátékos LP:
$$\begin{array}{rl} \min & \beta \\ \text{feltéve:} & 3y_1 + 7y_2 + 6y_3 \leq \beta \\ & 7y_1 + 5y_2 + \pi y_3 \leq \beta \\ & 27y_1 - y_2 + 8y_3 \leq \beta \\ & y_1 + y_2 + y_3 = 1 \\ & y_1, y_2, y_3 \geq 0 \end{array}$$A megadott kevert stratégiák behelyettesítése:
Oszlopjátékosra: $\underline{x}=\big(\tfrac{7}{8},0,\tfrac{1}{8}\big)^{\top}$. $$ \begin{aligned} &3x_1+7x_2+27x_3 = 3\cdot\tfrac{7}{8}+7\cdot0+27\cdot\tfrac{1}{8} = \tfrac{21}{8}+\tfrac{27}{8}=\tfrac{48}{8}=6 \ge \alpha\\ &7x_1+5x_2-x_3 = 7\cdot\tfrac{7}{8}+5\cdot0-\tfrac{1}{8} = \tfrac{49}{8}-\tfrac{1}{8}=\tfrac{48}{8}=6 \ge \alpha\\ &6x_1+\pi x_2+8x_3 = 6\cdot\tfrac{7}{8}+\pi\cdot0+8\cdot\tfrac{1}{8} = \tfrac{42}{8}+1=\tfrac{50}{8}=\tfrac{25}{4}\ge \alpha \end{aligned} $$ Tehát az az $\alpha$, ami minden kényszert kielégít és emellett maximális az $\alpha=6$.
Sorjátékosra: $\underline{y}=\big(\tfrac{1}{4},\tfrac{3}{4},0\big)$. $$ \begin{aligned} &3y_1+7y_2+6y_3 = 3\cdot\tfrac{1}{4}+7\cdot\tfrac{3}{4}+6\cdot0 = \tfrac{3}{4}+\tfrac{21}{4}=\tfrac{24}{4}=6 \le \beta\\ &7y_1+5y_2+\pi y_3 = 7\cdot\tfrac{1}{4}+5\cdot\tfrac{3}{4}+\pi\cdot0 = \tfrac{7}{4}+\tfrac{15}{4}=\tfrac{22}{4}=\tfrac{11}{2}\le \beta\\ &27y_1-1y_2+8y_3 = 27\cdot\tfrac{1}{4}-\cdot\tfrac{3}{4}+8\cdot0 = \tfrac{27-3}{4}=\tfrac{24}{4}=6 \le \beta \end{aligned} $$ Tehát az a $\beta$, ami minden kényszert kielégít és emellett minimális a $\beta=6$.
Mivel $\alpha=\beta=6$, tehát a megadott $\underline{x}$ és $\underline{y}$ valóban maximin stratégiák.
3. feladat
Határozzuk meg az alábbi csődproblémákban az arányos, az egyenletes nyereségű, az egyenletes veszteségű, illetve a sorban állásás szétosztást. A sorban állásás szétosztáshoz legyen 1,2,3,4 a sorrend.
(i) $E=30$ és $(d_1, d_2, d_3, d_4) = (5, 6, 19, 20)$
Hint
Az arányos esetében a követelések arányában kerül elosztásra a vagyon.
Az egyenletes nyereség esetében például lehet úgy gondolkozni, hogy megpróbáljuk egyenlően szétosztani, de ha valaki ezzel többet kapna, mint amennyit ő kért, akkor visszavesszük tőle a többletet, ő távozik és azt a maradék játékosok között osztjuk egyenletesen.
Az egyenletes veszteséghez lehet például úgy gondolkozni, hogy $5+6+19+20=50$ az összkövetelés, vagyis $20$ veszteséget kell egyenletesen szétosztani. Ezt megtehetjük az előbbihez hasonló módon, speciálisan amikor valaki többet vesztene mint amennyit követelt, akkor 0-val távozik és a többiek között osztjuk a maradék veszteséget egyenletesen.
A sorban állásos szétosztásnál egymás után szolgáljuk ki a hitelezőket, mindenkinek megpróbáljuk a teljes követelését kifizetni, amíg a vagyonból erre tellik. A legutolsónak kiszolgált hitelező a maradék vagyont kapja, ami lehet hogy kevesebb mint amit ő szeretett volna.
Megoldás
Arányos szétosztásAz összkövetelés $5+6+19+20=50$. Az arányos szétosztás $(\frac{5}{50} \cdot 30, \frac{6}{50} \cdot 30, \frac{19}{50} \cdot 30, \frac{20}{50} \cdot 30) = (3; 3,6; 11,4; 12)$.
Egyenletes nyereségHa mindenki ugyanannyit kapna, akkor $\frac{50}{4} = 17,5$ lenne mindenki kifizetése. Tehát $d_1$ és $d_2$ teljesen ki lesz elégítve. A maradék $30-5-6=19$ vagyont, ha $d_3$ és $d_4$ között osztjuk egyenletesen, akkor fejenként $9,5$-öt kapnak, ami kevesebb mint a követelésük. Tehát az egyenletes nyereség szerinti szétosztás $(5;6;9,5;9,5)$.
Egyenletes veszteségÖsszesen $50-30=20$ veszteséget szeretnénk kiosztani. Ha mindenki ugyanannyit veszít, az fejenként $\frac{20}{4}=5$ veszteség. Mindenki legalább ennyit követel, tehát ezzel kész vagyunk. Az egyenletes veszteség szerinti szétosztás $(5-5, 6-5, 19-5, 20-5) = (0, 1, 14, 15)$.
Sorban állásos szétosztásElőször a $d_1=5$ lesz teljesen kiszolgálva, ekkor marad még $25$ vagyon. Majd a $d_2=6$ lesz tejesen kiszolgálva, ekkor marad még $19$ vagyon. Végül $d_3=19$ lesz teljesen kiszolgálva. A negyedik hitelezőnek nem maradt semmi. $(5,6,19,0)$.
(ii) $E=40$ és $(d_1, d_2, d_3, d_4) = (8, 11, 16, 45)$
Megoldás
Arányos szétosztásAz összkövetelés $8+11+16+45=80$. Az arányos szétosztás $(\frac{8}{80} \cdot 40, \frac{11}{80} \cdot 40, \frac{16}{80} \cdot 40, \frac{45}{80} \cdot 40) = (4; 5,5; 8; 22,5)$.
Egyenletes nyereségHa mindenki ugyanannyit kapna, akkor $\frac{40}{4} = 10$ lenne mindenki kifizetése. Tehát $d_1$ teljesen ki lesz elégítve. A maradék $40-8=32$ vagyont, ha $d_2$, $d_3$ és $d_4$ között osztjuk egyenletesen, akkor fejenként $\frac{32}{3}$-ot kapnak, ami kevesebb mint a követelésük. Tehát az egyenletes nyereség szerinti szétosztás $(8; \frac{32}{3}; \frac{32}{3}; \frac{32}{3})$.
Egyenletes veszteségÖsszesen $80-40=40$ veszteséget szeretnénk kiosztani. Ha mindenki ugyanannyit veszít, az fejenként $\frac{40}{4}=10$ veszteség. $d_1$ ennél kevesebbet követel, ezért ő $8$-at veszít és távozik. A maradék $32$ veszteséget a maradék három hitelező között egyenletesen osztva fejenként $\frac{32}{3}$ veszteség adódik. Mindannyian legalább ennyit követelnek, tehát az egyenletes veszteség szerinti szétosztás $(8-8, 11-\frac{32}{3}, 16-\frac{32}{3}, 45-\frac{32}{3}) = (0, \frac{1}{3}, \frac{16}{3}, \frac{103}{3})$.
Sorban állásos szétosztásElőször a $d_1=8$ lesz teljesen kiszolgálva, ekkor marad még $32$ vagyon. Majd a $d_2=11$ lesz tejesen kiszolgálva, ekkor marad még $21$ vagyon. Majd a $d_3=16$ lesz teljesen kiszolgálva, ekkor marad még $5$ vagyon. A negyedik hitelező ezt az $5$ maradékot kapja. $(8,11,16,5)$.
4. feladat
Vegyük a $d_1=6$ és $d_2=10$ követeléseket. Rajzoljuk fel ezen követelések mellett az $E_1= 16-\varepsilon$, $E_2=10$, $E_3=6$ vagyonokhoz tartozó csődjátékok kelmeszabály-illusztrációját, illetve az ezeknek megfelelő közlekedőedényeket, a bennük lévő vízszintekkel együtt.
Megoldás
Kelmeszabály-illusztráció:
Közlekedőedények:
Interaktív widget 1
Interaktív widget 2
Interaktív widget 3
Gondoljuk végig, hogy az esetek közötti átmenet hogyan néz ki a kelmeszabály-illusztráción és a közlekedőedények szerint. Látható, hogy a kettő ugyanazt a szétosztást eredményezi.
5. feladat
Határozzuk meg az alábbi csődproblémákban a kelmeszabály szerinti szétosztást.
a) $E=100$ és $(d_1, d_2) = (100, 200)$
b) $E=100$ és $(d_1, d_2) = (50, 70)$
c) $E=20$ és $(d_1, d_2) = (4, 18)$
d) $E=20$ és $(d_1, d_2) = (9, 12)$
6. feladat
Határozzuk meg az alábbi csődproblémákban a kelmeszabály-konzisztens szétosztást.
a) $E=50$ és $(d_1, d_2, d_3, d_4) = (10, 20, 40, 50)$
b) $E=80$ és $(d_1, d_2, d_3, d_4) = (20, 30, 40, 50)$
7. feladat
Konstruáljunk közlekedőedény-rendszert az arányos, az egyenletes nyereségű, az egyenletes veszteségű és a sorban állásás szétosztásokra.
Hint
Használhatunk más szélességű, magasságú közlekedőedényeket. Tehetjük őket a padlóra, lelógathatjuk őket a plafonról. Több edényt is tehetünk egymás alá/fölé. Összeköthetjük őket másképp.
Megoldás
- Az arányos szétosztáshoz minden követeléshez egy közlekedőedényt rendelünk, melynek a szélessége felel meg a követelés nagyságának és egységnyi a magassága. Ezeket az edényeket a padlóra helyezzük és alul kötjük őket össze. Így a víz a szélességek arányában oszlik meg, éppen az arányos szétosztásnak megfelelően.
- Az egyenletes nyereséghez minden követeléshez egy közlekedőedényt rendelünk, melynek a magassága felel meg a követelés nagyságának és egységnyi a szélessége. Ezeket a padlóra tesszük és alul kötjük őket össze. Így a vízszint egyenletesen oszlik el a követelések erejéig.
- Az egyenletes veszteséghez minden követeléshez egy közlekedőedényt rendelünk, melynek a magassága felel meg a követelés nagyságának és egységnyi a szélessége. Ezeket a plafonról lógatjuk le és alul kötjük őket össze. Így az edényekben lévő levegő szintje egyenletesen oszlik el a követelések erejéig.
- A sorban állásos szétosztáshoz minden követeléshez egy közlekedőedényt rendelünk, melynek a magassága felel meg a követelés nagyságának és egységnyi a szélessége. Ezeket sorba kötjük, vagyis egymás fölé helyezzük őket, és a közvetlenül egymás alatt lévő edényeket úgy kapcsoljuk össze, hogy az aalsó edény tetejét a fölötte lévő edény aljával kötjük össze. A sorban elöl álló edény kerül alulra és a legutolsó felülre. Így az edények pont a megadott sorrend szerint töltődnek fel, a követelésük erejéig.
8. feladat
Piros- és Kékország egymással háborúzik. A csata két színtéren zajlik: egy pirosországi és egy kékországi csatatéren. A Piros Királynak 3, a Kék Királynak 4 serege van. Mindkét király egymástól függetlenül egyidőben eldönti, hogy melyik csatatérre hány sereget küld, és a két csatát egyszerre vívják meg. Ha ugyanannyi piros és kék sereg sorakozik fel egy csatatéren, akkor a seregek visszavonulnak és ennek a csatának az eredménye döntetlen. Ha valamelyik király több sereget küld az egyik csatatérre, akkor ott ő nyeri csatát és foglyul ejti a másik király összes odaküldött seregét: a megnyert csatáért 20 Ft-ot nyer a másik királytól, valamint minden foglyul ejtett seregért további 10 Ft váltságdíjat is kap tőle.
a) Legyen a Piros Király az oszlopjátékos! Írjuk fel a nyereségmátrixát.
b) Írjuk fel az oszlopjátékos maximin stratégiáit leíró lineáris programozási feladatot.
c) Írjuk fel a sorjátékos maximin stratégiáit leíró lineáris programozási feladatot.
d) A Piros Király azt tervezi, hogy rendre $(9/68, 23/68, 28/68, 8/68)$ valószínűségekkel küld $0, 1, 2, 3$ sereget a pirosországi csatatérre, a Kék Király pedig $(5/12, 0, 2/12, 0, 5/12)$ valószínűséggel küld $0, 1, 2, 3, 4$ sereget ugyanide. Mutassuk meg, hogy ezzel mindketten egy maximin stratégiát választottak.
Hint
A nyereségmátrix $(5 \times 4)$-es méretű lesz, kitöltve a feladat utasítása szerint. Az oszlop- és sorjátékos LP programjait felírjuk, a megadott kevert stratégiákat behelyettesítjük, a kipottyanó $\alpha$ és $\beta$ értékekről kiderül hogy egyenlők, ezzel a Neumann-tétel értelmében ezek valóban maximin stratégiák.
Megoldás
a) Oszlopjátékos nyereségmátrixa (Kék = sorjátékos, Piros = oszlopjátékos):
| (K,P) | (0,3) | (1,2) | (2,1) | (3,0) |
| (0,4) | -50 | -20 | -10 | 0 |
| (1,3) | -20 | -40 | 0 | 10 |
| (2,2) | 20 | -30 | -30 | 20 |
| (3,1) | 10 | 0 | -40 | -20 |
| (4,0) | 0 | -10 | -20 | -50 |
b) Oszlopjátékos (Piros) maximin LP-je:
Legyen $x_1,\dots,x_4$ az oszlopjátékos kevert stratégiája az oszlopokra. Ekkor
$$ \begin{array}{rl} \max & \alpha \\ \text{feltéve:} & -50x_1 -20x_2 -10x_3 + 0x_4 \ge \alpha \\ & -20x_1 -40x_2 + 0x_3 + 10x_4 \ge \alpha \\ & 20x_1 -30x_2 -30x_3 + 20x_4 \ge \alpha \\ & 10x_1 + 0x_2 -40x_3 -20x_4 \ge \alpha \\ & 0x_1 -10x_2 -20x_3 -50x_4 \ge \alpha \\ & x_1+x_2+x_3+x_4 = 1 \\ & x_1,x_2,x_3,x_4 \ge 0 \end{array} $$
c) Sorjátékos (Kék) maximin LP-je:
Legyen $y_1,\dots,y_5$ a sorjátékos kevert stratégiája a sorokra. Ekkor
$$ \begin{array}{rl} \min & \beta \\ \text{feltéve:} & -50y_1 -20y_2 +20y_3 +10y_4 +0y_5 \le \beta \\ & -20y_1 -40y_2 -30y_3 +0y_4 -10y_5 \le \beta \\ & -10y_1 +0y_2 -30y_3 -40y_4 -20y_5 \le \beta \\ & 0y_1 +10y_2 +20y_3 -20y_4 -50y_5 \le \beta \\ & y_1+y_2+y_3+y_4+y_5 = 1 \\ & y_1,y_2,y_3,y_4,y_5 \ge 0 \end{array} $$
d) A megadott stratégiák ellenőrzése:
Behelyettesítünk $\underline{x}=\big(\tfrac{9}{68},\tfrac{23}{68},\tfrac{28}{68},\tfrac{8}{68}\big)^{\top}$ az oszlopjátékos (Piros) LP-jébe: $$ \begin{aligned} &(0,4):\; -50\cdot\tfrac{9}{68}-20\cdot\tfrac{23}{68}-10\cdot\tfrac{28}{68}+0\cdot\tfrac{8}{68}=-17,5 \ge \alpha\\ &(1,3):\; -20\cdot\tfrac{9}{68}-40\cdot\tfrac{23}{68}+0\cdot\tfrac{28}{68}+10\cdot\tfrac{8}{68}=-15 \ge \alpha\\ &(2,2):\; 20\cdot\tfrac{9}{68}-30\cdot\tfrac{23}{68}-30\cdot\tfrac{28}{68}+20\cdot\tfrac{8}{68}=-17,5 \ge \alpha\\ &(3,1):\; 10\cdot\tfrac{9}{68}+0\cdot\tfrac{23}{68}-40\cdot\tfrac{28}{68}-20\cdot\tfrac{8}{68}=-17,5 \ge \alpha\\ &(4,0):\; 0\cdot\tfrac{9}{68}-10\cdot\tfrac{23}{68}-20\cdot\tfrac{28}{68}-50\cdot\tfrac{8}{68}=-17,5 \ge \alpha \end{aligned} $$
Tehát az az $\alpha$, ami minden kényszert kielégít és emellett maximális az $\alpha=-17,5$.
Behelyettesítünk $\underline{y}=\big(\tfrac{5}{12},0,\tfrac{2}{12},0,\tfrac{5}{12}\big)$ a sorjátékos (Kék) LP-jébe
$$ \begin{aligned} &(0,3):\; -50\cdot\tfrac{5}{12}-20\cdot0+20\cdot\tfrac{2}{12}+10\cdot0+0\cdot\tfrac{5}{12}=-17,5 \le \beta \\ &(1,2):\; -20\cdot\tfrac{5}{12}-40\cdot0-30\cdot\tfrac{2}{12}+0\cdot0-10\cdot\tfrac{5}{12}=-17,5 \le \beta \\ &(2,1):\; -10\cdot\tfrac{5}{12}+0\cdot0-30\cdot\tfrac{2}{12}-40\cdot0-20\cdot\tfrac{5}{12}=-17,5 \le \beta \\ &(3,0):\; 0\cdot\tfrac{5}{12}+10\cdot0+20\cdot\tfrac{2}{12}-20\cdot0-50\cdot\tfrac{5}{12}=-17,5 \le \beta \end{aligned} $$Tehát az a $\beta$, ami minden kényszert kielégít és emellett minimális a $\beta=-17,5$.
Tehát mivel $\alpha=\beta=-17,5~$ vagyis a megadott $\underline{x}$ és $\underline{y}$ valóban maximin stratégiák.
9. feladat
Mutassuk meg, hogy a kelmeszabály monoton, azaz egyetlen hitelező jussa sem csökkenhet a kelmeszabály szerinti szétosztás esetén, ha a követelése vagy a szétosztandó vagyon növekszik.
Hint
Képzeljük el mi történik ha több vizet töltünk a közlekedőedényekbe vagy ha valakinek nagyobb edényeket adunk.
Megoldás
A vagyon növekedése a hidraulikus közlekedőedényeknél annak felel meg, hogy több vizet töltünk ugyanabba a rendszerbe. Világos, hogy ilyenkor a vízszint minden edényben vagy ugyanott marad vagy növekedni fog.
A fizika törvényei szerint a rendszerben mindig egyetlen, globális vízszint alakul ki, amely minden hitelezőhöz tartozó részben azonos (és előfordulhat, hogy ez a vékony összekötő szakaszra esik). Ha valaki követelése növekszik, akkor neki nagyobb edényeket adunk, miközben a többiek edényeinek a mérete és az össz kitöltött vízmennyiség nem változik. Ilyenkor a globális vízszint vagy csökken vagy nem változik a rendszerben. Mivel a többiek edényeinek a mérete nem változott, ezért ebből következik, hogy a többiek részesedése szintén vagy csökken vagy nem változik. De az össz kitöltött vízmennyiség ugyanaz, ez csak úgy lehetséges ha a változott követelésű hitelező vízmennyisége vagy növekedett vagy nem változott.
10. feladat
Egy kétszemélyes, 0-összegű stratégiai játékban az oszlopjátékos nyereségmátrixa egy "bűvös négyzet", azaz egy olyan ($n \times n$)-es mátrix, melynek minden sorában, illetve minden oszlopában az elemek összege ugyanaz a szám: legyen ez az összeg $k$. Mutassuk meg, hogy az oszlopjátékos biztonsági szintje $k/n$.
Hint
Próbálkozzunk a csupa $\frac{1}{n}$-t tartalmazó kevert stratégiákkal.
Megoldás
Tekintsük az $$\underline{x} = (\frac{1}{n},\ \ldots, \frac{1}{n})^\top$$ és $$\underline{y} = (\frac{1}{n},\ \ldots, \frac{1}{n})$$ kevert stratégiákat.
Legyen az oszlopjátékos nyereségmátrixa az $A$ mátrix! Ekkor az oszlopjátékos maximin LP-je a $$\sum_{j=1}^{n} a_{i,j} x_j \geq \alpha$$ kényszereket írja fel minden $i$-re.
Mivel $x_j = \frac{1}{n}$ minden $j$-re, ezért ez éppen $$\frac{1}{n} \sum_{j=1}^{n} a_{i,j} \geq \alpha$$.
$\sum_{j=1}^{n} a_{i,j} = k$ a feladat feltétele szerint, tehát $$\frac{k}{n} \geq \alpha$$.
Vagyis $\alpha = \frac{k}{n}$.
A sorokra hasonló érveléssel belátható, hogy $\beta = \frac{k}{n}$. Mivel $\alpha = \beta$, ezért ezek valóban maximin stratégiák, tehát az oszlopjátékos biztonsági szintje valóban $\frac{k}{n}$.11. feladat
Egy $S$ szétosztási szabály duálisán azt az $S^*$ szétosztási szabályt értjük, melyet úgy kapunk, hogy az összveszteséget az $S$ szabály szerint osztjuk szét. Egy $S$ szétosztási szabály önduális, ha $S=S^*$.
a) Az $S$ szétosztási szabályt megvalósító közlekedőedény-rendszer ismeretében hogyan tudjuk meghatározni az $S^*$-ot megvalósító közlekedőedény-rendszert?
Hint
A 7. feladatban láttunk példát az egyenletes nyereség és az egyenletes veszteség szerinti szétosztásnak megfelelő közlekedőedény-rendszerre. Ezek a szabályok éppen egymás duálisai. Hogy viszonyul egymáshoz a két szabály közlekedőedény-rendszerének a képe?
Megoldás
A vízszintes tengely mentén tükrözzük az edényrendszert, de továbbra is alulról töltjük azokat az edényeket, amelyeket nem egy másik edényen keresztül látunk el.
Gondoljuk meg, hogy ez miért jó: Az egyes hitelezők vesztesége megfelel az edényeikben lévő levegő térfogatának. Ha lefényképezzük a rendszert, majd a képet fejjel lefelé fordítjuk, és a levegőt kékre, a vizet pedig fehérre színezzük, akkor egy olyan elrendezést kapunk, amely a fizika törvényeivel is összhangban van: ha éppen ennyi vizet töltenénk a rendszerbe, pontosan így nézne ki az egyensúlyi állapot.
b) Hogyan néz ki egy önduális szétosztási szabályt megvalósító közlekedőedény-rendszer?
Hint
Az a) feladat megoldása a hint. :)
Megoldás
Szimmetrikus a vízszintes tengelyre, ilyenkor a tükrözés után önmagát kapjuk. Ilyen például a kelmeszabály-konzisztens szétosztást megvalósító Kaminski-féle közlekedőedény-rendszer.
12. feladat
Vegyük azt a kétszemélyes, 0-összegű $(2^n \times 2^n)$-es stratégiai játékot, ahol a játékosok a $\{0,1, \dots 2^n-1\}$ számok közül választanak egyet, az oszlopjátékos kifizetése pedig a mondott számok nim-összege. Határozzuk meg az oszlopjátékos biztonsági szintjét!
(Pöttyös feladat.)
13. feladat
Adjunk (egy hagyományos számítógépen futtatható) algoritmust, amely a $d_1, \dots, d_n$ követelések polinomidejű előfeldolgozása után egy adott $E$ vagyonhoz $O(\log n)$ időben meghatározza a kelmeszabály-konzisztens szétosztásban szereplő maximális kifizetésértéket.
(Pöttyös feladat.)