Algojáték 8. 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
Határozzunk meg a felső körcsere algoritmus segítségével az $1, 2, 3, 4(, 5)$ lakások egy-egy újraosztását, ha a tulajdonosok preferenciasorrendje a következő.
a)
$1\colon~(3, 2, 4, 1)$
$2\colon~(4, 1, 2, 3)$
$3\colon~(1, 4, 3, 2)$
$4\colon~(3, 2, 1, 4)$
Hint
A felső körcsere (Top Trading Cycle, TTC) algoritmus a következőképpen működik: A lakástulajdonosok rámutatnak a számukra legszimpatikusabb még a piacon lévő lakás tulajdonosára. A kialakuló körök egymás között cserélnek és távoznak a piacról. A többiek ismétlik ezt, amíg mindenki nem távozik.
Megoldás
1. kör:
A tulajdonosok rámutatnak a nekik legszimpatikusabb lakásra:
$1\colon~(\boxed{3}, 2, 4, 1)$
$2\colon~(\boxed{4}, 1, 2, 3)$
$3\colon~(\boxed{1}, 4, 3, 2)$
$4\colon~(\boxed{3}, 2, 1, 4)$
Egy kialakuló kör van, $1$ és $3$, ők cserélnek, elhagyják a piacot.
$2\colon~(4, \cancel{1}, 2, \cancel{3})$
$4\colon~(\cancel{3}, 2, \cancel{1}, 4)$
2. kör:
A tulajdonosok rámutatnak a nekik legszimpatikusabb lakásra:
$2\colon~(\boxed{4}, 2)$
$4\colon~(\boxed{2}, 4)$
$2$ és $4$ cserélnek, elhagyják a piacot. Ezzel vége az algoritmusnak.
Az újraosztás:
$1 \leftarrow 3$
$2 \leftarrow 4$
$3 \leftarrow 1$
$4 \leftarrow 2$
b)
$1\colon~(5, 2, 1, 3, 4)$
$2\colon~(5, 4, 3, 1, 2)$
$3\colon~(4, 2, 3, 5, 1)$
$4\colon~(2, 1, 5, 3, 4)$
$5\colon~(2, 4, 1, 5, 3)$
Megoldás
1. kör:
A tulajdonosok rámutatnak a nekik legszimpatikusabb lakásra:
$1\colon~(\boxed{5}, 2, 1, 3, 4)$
$2\colon~(\boxed{5}, 4, 3, 1, 2)$
$3\colon~(\boxed{4}, 2, 3, 5, 1)$
$4\colon~(\boxed{2}, 1, 5, 3, 4)$
$5\colon~(\boxed{2}, 4, 1, 5, 3)$
Egy kialakuló kör van, $2$ és $5$, ők cserélnek, elhagyják a piacot.
$1\colon~(\cancel{5}, \cancel{2}, 1, 3, 4)$
$3\colon~(4, \cancel{2}, 3, \cancel{5}, 1)$
$4\colon~(\cancel{2}, 1, \cancel{5}, 3, 4)$
2. kör:
A tulajdonosok rámutatnak a nekik legszimpatikusabb lakásra:
$1\colon~(\boxed{1}, 3, 4)$
$3\colon~(\boxed{4}, 3, 1)$
$4\colon~(\boxed{1}, 3, 4)$
Egy kialakuló kör (hurokél) van, az $1$-es a saját lakásával távozik.
$3\colon~(4, 3, \cancel{1})$
$4\colon~(\cancel{1}, 3, 4)$
3. kör:
A tulajdonosok rámutatnak a nekik legszimpatikusabb lakásra:
$3\colon~(\boxed{4}, 3)$
$4\colon~(\boxed{3}, 4)$
Egy kialakuló kör van, $3$ és $4$, ők cserélnek, elhagyják a piacot. Ezzel vége az algoritmusnak.
Az újraosztás:
$1 \leftarrow 1$
$2 \leftarrow 5$
$3 \leftarrow 4$
$4 \leftarrow 3$
$5 \leftarrow 2$
c)
$1\colon~(2, 5, 3, 1, 4)$
$2\colon~(3, 1, 5, 4, 2)$
$3\colon~(1, 2, 3, 4, 5)$
$4\colon~(1, 3, 5, 4, 2)$
$5\colon~(4, 1, 3, 2, 5)$
Megoldás
1. kör:
A tulajdonosok rámutatnak a nekik legszimpatikusabb lakásra:
$1\colon~(\boxed{2}, 5, 3, 1, 4)$
$2\colon~(\boxed{3}, 1, 5, 4, 2)$
$3\colon~(\boxed{1}, 2, 3, 4, 5)$
$4\colon~(\boxed{1}, 3, 5, 4, 2)$
$5\colon~(\boxed{4}, 1, 3, 2, 5)$
Egy kialakuló kör van, $1,2$ és $3$, ők cserélnek, elhagyják a piacot.
$4\colon~(\cancel{1}, \cancel{3}, 5, 4, \cancel{2})$
$5\colon~(4, \cancel{1}, \cancel{3}, \cancel{2}, 5)$
2. kör:
A tulajdonosok rámutatnak a nekik legszimpatikusabb lakásra:
$4\colon~(\boxed{5}, 4)$
$5\colon~(\boxed{4}, 5)$
Egy kialakuló kör van, $4$ és $5$, ők cserélnek, elhagyják a piacot. Az algoritmus véget ért.
Az újraosztás:
$1 \leftarrow 2$
$2 \leftarrow 3$
$3 \leftarrow 1$
$4 \leftarrow 5$
$5 \leftarrow 4$
2. feladat
Határozzunk meg az 1. feladatban minden újraosztási feladathoz egy-egy jó lakáspiaci egyensúlyi árazást.
Hint
Lakáspiaci egyensúly: Minden lakáshoz hozzárendelek egy (pozitív) valós számot (árat) úgy, hogy ha minden tulajdonosnak adok annyi pénzt, amennyit a saját lakása ér, majd mindenkit megkérek hogy mutasson rá a neki legszimpatikusabb lakásra aminek az árát ki tudná fizetni, akkor minden lakásra pontosan egyvalaki mutatott rá (vagyis ez meghatároz egy újraosztást).
Jó stratégia például ha az alapján árazunk, hogy hanyadik körben hagyta el az adott tulajdonos a TTC algoritmust. Minnél korábban hagyta el, annál nagyobb árat rendelünk a lakásához, akik pedig egymás között cseréltek, azoknak azonos árúnak kell lennie a lakásuknak.
Egészen konkrétan, ha $n$ tulajdonos van és valamelyik tulajdonos a $k$. körben hagyta el a TTC-t, akkor például $n-k+1$ pozitív és a feltételnek megfelelő ár, de bármi más értelmes választás is jó.
Megoldás
Az a) feladatban $1$ és $3$ az 1. körben távoztak, árazzuk az ő lakásukat $2$-re, $2$ és $4$ a 2. körben távoztak, árazzuk az ő lakásukat $1$-re.
Ekkor ha zölddel jelöljük mindenkinél azokat a lakásokat, amiket ki tud fizetni, majd ezek közül az elsőket kiválasztjuk, akkor egy újraosztást fogunk kapni (minden lakásra pontosan egy ember mutat rá). Tehát ez egy lakáspiaci egyensúlyi árazás.
a)
$1\colon~(\boxed{\textcolor{green}{3}}, \textcolor{green}{2}, \textcolor{green}{4}, \textcolor{green}{1})$
$2\colon~(\boxed{\textcolor{green}{4}}, \textcolor{red}{1}, \textcolor{green}{2}, \textcolor{red}{3})$
$3\colon~(\boxed{\textcolor{green}{1}}, \textcolor{green}{4}, \textcolor{green}{3}, \textcolor{green}{2})$
$4\colon~(\textcolor{red}{3}, \boxed{\textcolor{green}{2}}, \textcolor{red}{1}, \textcolor{green}{4})$
A b) feladatban $2$ és $5$ az 1. körben távoztak, árazzuk az ő lakásukat $3$-ra, $1$ a 2. körben távozott, árazzuk az ő lakását $2$-re, $3$ és $4$ pedig a 3. körben távoztak, árazzuk az ő lakásukat $1$-re.
Hasonlóan itt is, egyensúlyi árazást kaptunk.
b)
$1\colon~(\textcolor{red}{5}, \textcolor{red}{2}, \boxed{\textcolor{green}{1}}, \textcolor{green}{3}, \textcolor{green}{4})$
$2\colon~(\boxed{\textcolor{green}{5}}, \textcolor{green}{4}, \textcolor{green}{3}, \textcolor{green}{1}, \textcolor{green}{2})$
$3\colon~(\boxed{\textcolor{green}{4}}, \textcolor{red}{2}, \textcolor{green}{3}, \textcolor{red}{5}, \textcolor{red}{1})$
$4\colon~(\textcolor{red}{2}, \textcolor{red}{1}, \textcolor{red}{5}, \boxed{\textcolor{green}{3}}, \textcolor{green}{4})$
$5\colon~(\boxed{\textcolor{green}{2}}, \textcolor{green}{4}, \textcolor{green}{1}, \textcolor{green}{5}, \textcolor{green}{3})$
A c) feladatban, $1$, $2$ és $3$ az 1. körben távoztak, árazzuk az ő lakásukat $2$-re, $4$ és $5$ pedig a 2. körben távoztak, árazzuk az ő lakásukat $1$-re.
Hasonlóan itt is, egyensúlyi árazást kaptunk.
c)
$1\colon~(\boxed{\textcolor{green}{2}},\textcolor{green}{5},\textcolor{green}{3},\textcolor{green}{1},\textcolor{green}{4})$
$2\colon~(\boxed{\textcolor{green}{3}},\textcolor{green}{1},\textcolor{green}{5},\textcolor{green}{4},\textcolor{green}{2})$
$3\colon~(\boxed{\textcolor{green}{1}},\textcolor{green}{2},\textcolor{green}{3},\textcolor{green}{4},\textcolor{green}{5})$
$4\colon~(\textcolor{red}{1},\textcolor{red}{3},\boxed{\textcolor{green}{5}},\textcolor{green}{4},\textcolor{red}{2})$
$5\colon~(\boxed{\textcolor{green}{4}},\textcolor{red}{1},\textcolor{red}{3},\textcolor{red}{2},\textcolor{green}{5})$
3. feladat
Mutassuk meg, hogy a felső körcsere algoritmus kimenete Pareto-optimális.
Hint
Tanultuk, hogy a TTC erős magbeli újraosztást szolgáltat.
Megoldás
Az erős magbeli újraosztás olyan, hogy nem létezik hozzá gyengén blokkoló koalíció. A gyengén blokkoló koalíció olyan, hogy benne mindenki legalább olyan jól jár mint az újraosztásban és van aki szigorúan jobban jár.
Ha a TTC kimenete nem lenne Pareto-optimális, akkor lenne olyan újraosztás ami Pareto-dominálná. A Pareto-domináló újraosztásban mindenki legalább olyan jól jár mint az eredetiben és van aki szigorúan jobban jár. Tehát ebben az esetben az összes játékos együtt gyengén blokkoló koalíciót alkotna a TTC kimenete felett.
4. feladat
Mutassunk példát olyan preferencia profilra, amelyre nézve tetszőleges árazás egyensúlyi árazás lesz!
Hint
Akkor lesz egyensúlyi az árazás, ha az első megfizethető lakás mindenkinél különböző. Hogyan lehet ezt nagyon könnyen biztosítani?
Megoldás
Vegyünk egy olyan preferenciaprofilt, ahol mindenkinél a saját lakása van első helyen.
5. feladat
Adott egy újraosztási probléma, ahol a tulajdonosok több lakással is rendelkezhetnek. Minden tulajdonosnak szigorú preferenciasorrendje van az összes lakás fölött, beleértve a sajátjait is. Csak olyan újraosztások megengedettek, ahol minden tulajdonos ugyanannyi lakást kap, mint amennyivel eredetileg rendelkezett. Tegyük fel, hogy egy $k$ db lakással rendelkező tulajdonos eredeti lakásai a preferenciasorrendben az $i_1 \prec i_2 \prec \ldots \prec i_k$ helyeket foglalják el, az újraosztás után kapott lakásai pedig a $j_1 \prec j_2 \prec \ldots \prec j_k$ helyeken állnak. Azt mondjuk, hogy ez a tulajdonos legalább olyan jól járt az újraosztással, ha $i_1 \preceq j_1$, $i_2 \preceq j_2$, $\ldots$, $i_k \preceq j_k$ és szigorúan jobban járt ha az ezek közül legalább egy szigorú. Adjunk hatékony algoritmust egy erős magbeli újraosztás megtalálására.
Hint
Klónozzuk a tulajdonosokat.
Megoldás
Minden tulajdonos készítsen magáról annyi klónt, ahány lakása van, mindegyik klónnak legyen ugyanaz a preferenciasorrendje mint az eredeti tulajnak volt és kapjon meg pontosan egy lakást a tulajtól. Futtassuk le a TTC algoritmust a klónok lakáspiacán. A klónok adják vissza a megszerzett lakásokat a hozzájuk tartozó tulajnak.
Azt állítjuk, hogy az így kapott újraosztás a tulajok felett erős magbeli.
Tegyük fel indirekt, hogy nem az: ekkor van ezt gyengén blokkoló koalíció a tulajdonosok lakáspiacán. Képezzünk ebből a TTC outputját gyengén blokkoló koalíciót a klónok lakáspiacára a következőképpen:
Ha a koalícióban egy tulaj a $b_1 \prec \dots \prec b_k$ lakásokat kapná, a módosított TTC-ben pedig a $j_1 \prec \dots \prec j_k$ lakásokat kapta, akkor az, hogy a koalíció blokkol a tulajdonosok lakáspiacán azt jelenti, hogy $j_1 \preceq b_1$, $j_2 \preceq b_2$, $\dots$, $j_k \preceq b_k$ teljesülnek és van olyan tulaj a koalícióban akire legalább az egyik szigorúan teljesül.
Adjuk tehát oda a $j_1$-et elhozó klónnak a $b_1$ lakást, a $j_2$-t elhozó klónnak a $b_2$ lakást, és így tovább. Ekkor a koalícióban lévő tulajok klónjai szintén gyengén blokkoló koalíciót alkotnak a klónok lakáspiacán a TTC outputja felett, ami ellentmondás.
6. feladat
Tekintsük az újraosztási feladat azon általánosítását, amelyben minden lakástulajdonos egy lakással rendelkezik, de bizonyos lakások ugyanabban a társasházban találhatók, és az ilyen lakások teljesen egyenlőek minden tulajdonos preferenciarendezésében, az azonos lakásokat leszámítva viszont szigorúak a preferenciarendezések. Adjunk hatékony algoritmust egy olyan újraelosztás megtalálására, amit nem blokkol olyan koalíció, amiben mindenki szigorúan jobban járna mint az újraosztásban.
Hint
Képezzünk szigorú preferenciasorrendeket úgy, hogy mindenki sorsolással dönt a számára egyforma lakások sorrendjéről.
Megoldás
Képezzünk szigorú preferenciasorrendeket úgy, hogy mindenki sorsolással dönt a számára egyforma lakások sorrendjéről. Futtassuk ezen preferenciasorrendek mellett a TTC-t.
Tegyük fel indirekt, hogy a kapott újaosztásra az eredeti preferenciasorrendek mellett van olyan koalíció, aminek minden tagja szigorúan jobban járna. Ez viszont a képzett szigorú preferenciasorrendek felett is igaz lesz ugyanerre a koalícióra, tehát a TTC outputját is gyengén (sőt erősen is) blokkolja a koalíció, ami ellentmondás.
7. feladat
Ingatlanisztánban minden lakosnak pontosan egy lakása van. Misi gyakornokként dolgozik a Lakásár Egyensúlyi Bizottságnál (LEB), amelynek feladata a lakásárak egyensúlyának fenntartása. Év végén minden tulajdonos levelet küld a LEB-nek, benne saját preferenciasorrendjével Ingatlanisztán összes lakásáról. Misi ezek alapján egész nap dolgozott, hogy kiszámítsa az egyensúlyi lakásárakat, majd az eredményt feljegyezte minden levél aljára. Ám éjszaka egy gonosz borítéklopó manó betört, és ellopta az összes borítékot, rajta a feladóval és a címével, a borítékok tartalmát hátrahagyva! Így Misi másnap rájött, hogy nem tudja, melyik preferencialista és ár kihez tartozik. Főnöke, Tamás, hamarosan megérkezik ellenőrizni a munkát. Segíts Misinek egy hatékony algoritmust találni, amellyel eldöntheti, melyik tulajdonosnak melyik árat kell visszaküldenie (a preferenciasorrendet nem kell visszaküldeni).
(Pöttyös feladat.)