Algojáték 10. 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

Ketten játszanak két kupac kaviccsal. Az egyik kupacban $n_1$, a másikban $n_2$ darab kavics van, $n_1, n_2 \in \mathbb{N}_+$. A soron következő játékos vagy elvesz az egyik, általa választott kupacból valamennyi, de legalább egy darab kavicsot, vagy pedig mind a két kupacból elvesz ugyanannyi, de legalább egy darab kavicsot. Az a játékos veszít, aki nem tud lépni. Határozzuk meg minden $n_1, n_2 \in \{ 1, 2, \ldots, 6 \}$ esetén az $(n_1, n_2)$ állás Grundy-számát.

Hint

Készítsünk egy táblázatot, melyen sorai az egyik, oszlopai a másik kupac kavicsszámát jelölik. Vegyünk fel sort, illetve oszlopot a $0$ kavicsos kupachoz is! Számoljuk ki a Grundy-számozást a $mex$-es képlet alapján: minden cella átlósan, oszlopban és sorban látja a kisebb méretű kupacokat.

Az átlóban látás miatt a Sprague-Grundy tétel nem érvényes erre a feladatra.

Megoldás
$n_1$ \ $n_2$ 0 1 2 3 4 5 6
0 0 1 2 3 4 5 6
1 1 2 0 4 5 3 7
2 2 0 1 5 3 4 8
3 3 4 5 6 2 0 1
4 4 5 3 2 7 6 9
5 5 3 4 0 6 8 10
6 6 7 8 1 9 10 3

2. feladat

Három hitelező osztozik egy 100-nagyságú vagyonon. A hitelezők összkövetelése 200. Tudjuk, hogy a hitelezők $x_1 = 10$, $x_2 = 30$, illetve $x_3 = 60$ fabatkát kaptak. Előfordulhatott-e ez

  1. az arányos,
  2. a sorban állásos,
  3. az egyenletes nyereség,
  4. az egyenletes veszteség,
  5. a kelmeszabály-konzisztens

szétosztási szabályok szerinti szétosztás esetén? Amelyik esetben igen, ott határozzuk meg a hitelezők követeléseinek összes lehetséges értékét.

Megoldás

Arányos esetben a kifizetések aránya a követelések arányával egyezik meg. Ha az összkövetelés $200$ volt (ami éppen a vagyon kétszerese) akkor ez csak úgy lehet, ha $d_1=2 \cdot x_1 = 20$, $d_2=2 \cdot x_2 = 60$, $d_3=2 \cdot x_3 = 120$.

Sorban állásos esetben, mivel $x_3$ is kapott valamit, ezért $x_1$ és $x_2$ biztosan a teljes követelésüket kapták. Ezzel $d_1=x_1=10$, $d_2=x_2=30$. Az összkövetelés $200$, tehát a kimaradó $d_3=200-d_1-d_2=160$ volt.

Egyenletes nyereség esetében a maximális kifizetés $x_3=60$ volt, mindenki aki ennél kevesebbet kapott, tehát $x_1$ és $x_2$ is a teljes követelését meg kellett, hogy kapja. Ezzel $d_1=x_1=10$, $d_2=x_2=30$. Az összkövetelés $200$, tehát a kimaradó $d_3=200-d_1-d_2=160$ volt.

Egyenletes veszteség esetében aki nem nullát kapott, az egyforma veszteséget szenvedett el. Az összveszteség $200-100=100$, ezért fejenként $\frac{100}{3}$ volt a veszteségük. Ezzel a követeléseik $d_1=x_1+\frac{100}{3} = \frac{130}{3}$, $d_2=x_2+\frac{100}{3} = \frac{190}{3}$, $d_1=x_1+\frac{100}{3} = \frac{280}{3}$.

Kelmeszabály-konzisztens esetben a közlekedőedény-rendszerben lévő edények mérete a kérdés. Észrevehetjük, hogy a kifizetések éppen az összkövetelés felét adják. Ilyen esetben a közlekedőedény-rendszerben a vízszint éppen félúton lesz, azaz az alsó edények teljesen tele vannak, a felső edények pedig teljesen üresek. Tehát mindenki a követelése felét kapta, azaz $d_1=2 \cdot x_1 = 20$, $d_2=2 \cdot x_2 = 60$, $d_3=2 \cdot x_3 = 120$.

3. feladat

Öt játékos, $A$, $B$, $C$, $D$ és $E$ licitál két tárgyra $s$-re és $t$-re. Minden játékos legfeljebb egy tárgyat kaphat. A beérkezett liciteket az alábbi táblázat mutatja.

$s$ $t$
$A$ 5 5
$B$ 4 2
$C$ 2 4
$D$ 2 0
$E$ 0 2

a) Határozzuk meg, hogy a Clarke-szabályos Vickrey-Clarke-Groves-mechanizmussal történő árverezés során kik lesznek a nyertesek, mit fognak ők kapni és mennyit kell fizetniük ezért?

Hint

A VCG szerint az az alternatíva nyer, ami maximalizálja az össztársadalmi hasznosságot. Ehhez egy maximális súlyú párosítást keresünk.

A Clarke-szabály szerint az $i$. játékos által fizetett összeg a következőképp számolódik:

Látható, hogy $i$ jelenlétében a többiek biztos nem járhatnak jobban, legfeljebb csak rosszabbul, hiszen $i$ elhappolhat előlük egy jó alternatívát. Ezért a Clarke-szabály azt mondja, hogy $i$ fizesse ki azt a kárt, amit az ő jelenléte okozott a többieknek, vagyis a két imént meghatározott érték különbségét.

Megoldás

1. lépés: Az optimális allokáció meghatározása.

Két tárgyat kell kiosztanunk öt játékos között úgy, hogy minden játékos legfeljebb egy tárgyat kaphat. Ránézésre látszik, hogy a maximális elérhető összhaszon $9$, ezt két allokáció is el tudja érni: $$A \gets s,\quad C \gets t \quad \text{vagy} \quad A \gets t,\quad B \gets s$$ Ilyenkor tetszőlegeset választhatunk, válasszuk például az elsőt. $$A \gets s,\quad C \gets t$$ Ez $A$-nak $5$-öt, $C$-nek pedig $4$-et ér.

2. lépés: Clarke-szabály szerinti fizetések.

$A$ játékos fizetése

Ha $A$ nincs, akkor a többiek ($B$, $C$, $D$, $E$) közül keressük a maximális párosítást. A legjobb: $B \gets s$, $C \gets t$, ahol az összhaszon $4 + 4 = 8$. $A$ jelenlétében a többiek ($C$) $4$-et kapnak, ezért $A$ fizetése $$p_A = 8 - 4 = 4.$$

$C$ játékos fizetése

Ha $C$ nincs, akkor a többiek ($A$, $B$, $D$, $E$) közül keressük a maximális párosítást. A legjobb: $A \gets t$, $B \gets s$, ahol az összhaszon $5 + 4 = 9$. $C$ jelenlétében a többiek ($A$) $5$-öt kapnak, ezért $C$ fizetése $$p_C = 9 - 5 = 4.$$

Mindenki más $0$-át fizet, hiszen akár jelen vannak, akár nem, a többiek ugyanannyit tudnak elérni.

Végső válasz.

b) Mi lesz a válasz akkor, ha két példány is rendelkezésre áll az $s$ tárgyból?

Megoldás

1. lépés: Az optimális allokáció meghatározása.

Ebben az esetben az $5+4+4$ a legnagyobb elérhető összhaszon, amit a következő allokáció ér el: $$A \gets s,\quad B \gets s \quad C \gets t$$ Ez $A$-nak $5$-öt, $B$-nek $4$-et, $C$-nek pedig szintén $4$-et ér.

2. lépés: Clarke-szabály szerinti fizetések.

$A$ játékos fizetése

Ha $A$ nincs, akkor a többiek ($B$, $C$, $D$, $E$) közül keressük a maximális párosítást. Egy legjobb: $B \gets s$, $C \gets t$, $D \gets s$ ahol az összhaszon $4 + 4 + 2 = 10$. $A$ jelenlétében a többiek ($B$ és $C$) $4+4=8$-at kapnak, ezért $A$ fizetése $$p_A = 10 - 8 = 2.$$

$B$ játékos fizetése

Ha $B$ nincs, akkor a többiek ($A$, $C$, $D$, $E$) közül keressük a maximális párosítást. Egy legjobb: $A \gets s$, $C \gets t$, $D \gets s$, ahol az összhaszon $5 + 4 + 2 = 11$. $B$ jelenlétében a többiek ($A$ és $C$) $5+4=9$-et kapnak, ezért $B$ fizetése $$p_B = 11 - 9 = 2.$$

$C$ játékos fizetése

Ha $C$ nincs, akkor a többiek ($A$, $B$, $D$, $E$) közül keressük a maximális párosítást. Egy legjobb: $A \gets s$, $B \gets s$, $E \gets t$, ahol az összhaszon $5 + 4 + 2 = 11$. $C$ jelenlétében a többiek ($A$ és $B$) $5+4=9$-et kapnak, ezért $C$ fizetése $$p_C = 11 - 9 = 2.$$

Mindenki más $0$-át fizet, hiszen akár jelen vannak, akár nem, a többiek ugyanannyit tudnak elérni.

Végső válasz.

4. feladat

Három játékos osztozik arányosan a $[0,1)$ intervallumon a Fink-eljárás segítségével. A játékosok a sorszámuk szerinti növekvő sorrendben érkeztek, és minden vágás műveletnél a lehető legbalrább vágtak. Tudjuk, hogy az első játékos értékelő eloszlásfüggvénye $f_1(x) = x$ és hogy ő az eljárás végén egy $[a,b) \cup [c,d)$ alakú részt kapott, ahol $0 \le a < b < c < d \le 1$. Határozzuk meg $a$, $b$, $c$ és $d$ összes lehetséges értékét.

Hint

Az első körben az első játékos a $[0, \frac{1}{2})$ és $[\frac{1}{2}, 1)$ intervallumokat ajánlja fel a másodiknak, aki ezek közül egyet elvisz. Minek kell történnie a harmadik körben, hogy $[a,b) \cup [c,d)$ alakú részt kapjon az első?

Megoldás

Az első körben az első játékos a $[0, \frac{1}{2})$ és $[\frac{1}{2}, 1)$ intervallumokat ajánlja fel a másodiknak, aki ezek közül egyet elvisz. A harmadik körben ezeket három egyenlő hosszúságú részre fogja osztani, amiből a harmadiknak a középsőt kell elvinnie, hogy $[a,b) \cup [c,d)$ alakú legyen a maradék.

Tehát két eset van: $[0, \frac{1}{6})$ és $[\frac{2}{6}, \frac{1}{2})$, illetve $[\frac{1}{2}, \frac{4}{6})$ és $[\frac{5}{6}, 1)$.

Azaz $a=0, b=\frac{1}{6}, c=\frac{2}{6}, d=\frac{1}{2}$ vagy $a=\frac{1}{2}, b=\frac{4}{6}, c=\frac{5}{6}, d=1$.

5. feladat

Egy tengeralattjáró egy ($3 \times 3$)-as rács két oldalszomszédos mezőjén áll. Egy bombázó repülőgépről, ahonnan nem látszik a víz alatti jármű, bombát dobnak a kilenc mező valamelyikére. Ha a bombázó eltalálja a tengeralattjárót, akkor 1 pontot kap, a tengeralattjáró viszont ekkor 1 pontot veszít, ha azonban a bombázó nem találja el a tengeralattjárót, akkor a tengeralattjáró kap 1 pontot, a bombázó pedig veszít 1 pontot. Határozzuk meg a játékosok egy-egy tetszőleges maximin stratégiáját.

Hint

Használjuk ki a tábla szimmetriáit, készítsünk egy kisebb nyereségmátrixot ami leírja a játékot!

Megoldás

Számozzuk meg a négyzetrács mezőit a következőképpen.

123
456
789

Tegyük fel, hogy valamilyen maximin stratégiában a bombázó a következő valószínűségekkel választja az egyes mezőket.

$p_1$$p_2$$p_3$
$p_4$$p_5$$p_6$
$p_7$$p_8$$p_9$

Azt állítjuk, hogy ekkor a függőleges tengelyre tükrözött eloszlás is maximin stratégia lesz.

$p_3$$p_2$$p_1$
$p_6$$p_5$$p_4$
$p_9$$p_8$$p_7$

Ez azért van így, mert a maximin stratégia olyan, hogy az ellenség bármely kevert stratégiájával szemben garantálja az $\alpha$ biztonsági szintet, az ellenség lehetséges kevert stratégiái (vagyis hogy hol helyezkedik el a tengeralattjáró) pedig szintén szimmetrikusak, a főátlóra tükrözéssel egy másik lehetséges kevert stratégiát kapunk.

A maximin stratégiák lineáris kombinációja is maximin stratégia (megfelelően skálázva, hogy eloszlás legyen), tehát vehetem a két fenti eloszlás cellánkénti átlagát.

$\frac{p_1 + p_3}{2}$$p_2$$\frac{p_1+p_3}{2}$
$\frac{p_4+p_6}{2}$$p_5$$\frac{p_4+p_6}{2}$
$\frac{p_7+p_9}{2}$$p_8$$\frac{p_7+p_9}{2}$

Mint látható, a tábla függőleges tengelyre vett szimmetriája miatt létezik olyan maximin stratégia ami szintén szimmetrikus a függőleges tengelyre.

A másik tengelyre tükrözés után azt kapjuk, hogy a bombázónak létezik olyan maximin stratégiája, amelyben valamilyen $q_1$ valószínűséggel dob középre (az 5-ös mezőre), $q_2$ valószínűségekkel élre (a 2, 4, 6, 8 mezőkre) és $q_3$ valószínűségekkel sarokba (az 1, 3, 7, 9 mezőkre).

Hasonló gondolatmenettel (90 fokos forgatási szimmetriával) az is belátható, hogy a tengeralattjárónak létezik olyan maximin stratégiája, amelyben valamilyen $r_1$ valószínűségekkel lesz az $\{ 2, 5 \}$, $\{ 4, 5 \}$, $\{ 6, 5 \}$, $\{ 8, 5 \}$ mezőkön és $r_2$ valószínűségekkel az $\{ 1, 2 \}$, $\{ 1, 4 \}$, $\{ 2, 3 \}$, $\{ 3, 6 \}$, $\{ 4, 7 \}$, $\{ 6, 9 \}$, $\{ 7, 8 \}$, $\{ 8, 9 \}$ mezőkön.

Ezzel pedig a nyereségmátrix a következő alakra hozható.

$$ \begin{array}{r|ccc} & 5 & \text{2, 4, 6, 8} & \text{1, 3, 7, 9} \\ \hline \{2,5\},\,\{4,5\},\,\{6,5\},\,\{8,5\} & a_{11} & a_{12} & a_{13} \\ \text{maradék} & a_{21} & a_{22} & a_{23} \end{array} \text{,} $$

Ahol egy cellán belül mindkét játékos egyenletes eloszlással választ a hozzá tartozó sor és oszlop stratégiái közül, a cella értéke pedig az így kapott várható nyereség lesz.

Vagyis $$a_{11} = -1 \text{,}$$ $$a_{12} = \frac{1}{4} \cdot (-1) + \frac{3}{4} \cdot 1 = \frac{1}{2} \text{,}$$ $$a_{13} = 1 \text{,}$$ $$a_{21} = 1 \text{,}$$ $$a_{22} = \frac{1}{4} \cdot (-1) + \frac{3}{4} \cdot 1 = \frac{1}{2} \text{,}$$ $$a_{23} = \frac{1}{4} \cdot (-1) + \frac{3}{4} \cdot 1 = \frac{1}{2} \text{,}$$ azaz a nyereségmátrix $$\left( \begin{array}{ccc} -1 & 1/2 & 1 \\ 1 & 1/2 & 1/2 \end{array} \right) \text{.}$$

Tudjuk, hogy elég egy kevert Nash-egyensúlyt meghatározni, márpedig a második sor második eleme egy tiszta Nash-egyensúly.

Vagyis a sorjátékos egy maximin stratégiája az, ha $\frac{1}{8}$ valószínűséggel rejtőzik el az $\{ 1, 2 \}$, $\{ 1, 4 \}$, $\{ 2, 3 \}$, $\{ 3, 6 \}$, $\{ 4, 7 \}$, $\{ 6, 9 \}$, $\{ 7, 8 \}$, $\{ 8, 9 \}$ mezők mindegyikén. Az oszlopjátékos egy maximin stratégiája pedig az, ha $\frac{1}{4}$ valószínűséggel lő a 2, 4, 6, 8 mezők mindegyikére.

6. feladat

A táblára felírtunk egy pozitív egész számot. Két játékos felváltva lép. A soron következő játékos átírja a táblán lévő $n$ számot ($n-1$)-re vagy $\lfloor n/2 \rfloor$-re. Az a játékos veszít, aki az 1-et írja fel. Határozzuk meg az $n$ függvényében, hogy kinek van nyerő stratégiája.

(Pöttyös feladat.)

7. feladat

Közeledik a vizsgaidőszak a Bűbájtudományi és Mágiaelméleti Egyetemen. A Bevezetés a Számmisztikába 1 tantárgyból a félév során minden mágiatanonc különböző pontszámot szerzett. Főmágus Tamás a szóbeli vizsgára $n$ tanonchoz $n$ vizsgáztatót rendelt ki, akiket egy stabil párosítás szerint szeretne összerendelni. A vizsgáztatók egyetértésben a magasabb pontszámú tanoncok vizsgáztatását preferálják, a tanoncoknak viszont egyéni rangsoruk van a vizsgáztatókról, amit előzetesen leadtak. (Mindkét oldal rangsorai teljesek.) A tanoncok maximális kiszolgálása érdekében Főmágus Tamás elrendelte, hogy a vizsga megkezdése előtt módosítási kérelmeket nyújthatnak be: megneveznek két vizsgáztatót és kérik, hogy azok cseréljenek helyet a saját preferencialistájukban. Tamás a kérések kiszolgálásával Mágus Misit bízta meg: Misi előző nap este polinomiális időben feldolgozhatja a leadott listákat, a helyszínen viszont minden beérkező kérés után $O(n \log n)$ lépés megtételével ki kell hirdetnie egy új, az aktuális preferenciáknak megfelelő stabil párosítást. A tanoncok tetszőlegesen sok kérést intézhetnek Misihez. Segíts Misinek megoldani a feladatát!

(Pöttyös feladat.)