Kezdőlap


Cím:	Egy csodálatos elmélet - a Nash-egyensúly
Szerző(k):	Radnai Márton
Füzet:	2002/szeptember, 326 - 332. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

¹
A magyar mozik nemrég játszották az ,,Egy csodálatos elme'' című amerikai játékfilmet, amely John F. Nash matematikus életéről szól, aki Harsányi Jánossal és Reinhard Selten-nel együtt 1994-ben elnyerte a közgazdasági Nobel-díjat. A nagy sikerű film azonban nem annyira Nash munkásságával, sokkal inkább betegségével foglalkozott, így kevés derült ki arról, miért is kapott Nash Nobel-díjat. E rövid cikkben ezt próbáljuk meg néhány egyszerű példán keresztül bemutatni.

Nem-kooperatív játékelmélet

Nash fő eredményét a nem kooperatív játékelmélet területén érte el, amely olyan stratégiai játékokkal (más néven: szituációkkal) foglalkozik, ahol a játékosokról (más néven: aktorokról) feltesszük, hogy nem kötnek megállapodásokat egymással, más szóval az egyes játékosokat, nem pedig csoportjaikat tesszük a vizsgálat tárgyává. Feltesszük továbbá, hogy minden játékos ismeri a saját maga és a többi játékos által választható lehetőségeket (más néven: stratégiákat), és az ezekhez a lehetőségekhez tartozó hasznosságokat (más néven: kifizetéseket). Emellett minden szereplő tudja mindezt, sőt azt is, hogy ezeknek az információknak a többi játékos is birtokában van.
A játékokat leggyakrabban úgynevezett normál (egyes irodalmakban: stratégiai) alakban írják fel, ahol egy táblázatban jelölik azt, hogy az egyes stratégiák választása mekkora hasznosságot eredményez az azt választó játékos számára. Vegyük például az alábbi klasszikus kétszemélyes játékot, melyet általában fogolydilemma néven emlegetnek: két betörőt, aki együtt követett el egy rablást elfognak, és külön-külön (egyidőben) vallatni kezdik őket. Mindkettőjüknek a következő alkut ajánlják: ha azt vallja, hogy a másik követte el a rablást, a másik börtönbe kerül, ő pedig pénzjutalmat kap. Ha mindketten a másikra vallanak, akkor mindketten börtönbe kerülnek és pénzjutalmat is kapnak, míg ha egyikük sem vall, mindketten szabadon maradnak, de pénzjutalomban nem részesülnek.
A játékot az alábbi táblázattal írhatjuk le (a két játékost nevezzük Sor-nak és Oszlop-nak.):

\begin{matrix} Oszlop \\ Nem vall & Vall \\ Sor & Nem vall & 3000 & 3000 & 0 & 4000 \\ Vall & 4000 & 0 & 1000 & 1000 \end{matrix}

Sor stratégiáit (vall, nem vall) a vízszintes sorok, míg Oszlop stratégiáit (vall, nem vall) a függőleges oszlopok mutatják. A táblázatban szereplő két szám közül az első Sor, míg a második Oszlop hasznosságait tartalmazza; ezek a számok úgy jöttek létre, hogy a szabadon bocsátáshoz 3000-et, a pénzjutalomhoz pedig 1000-et rendeltünk hozzá. A jobb felső cellát tehát így olvashatjuk: ha Sor nem vall, Oszlop viszont vall, akkor Sor számára nulla, míg Oszlop számára 4000 egység lesz a játék hasznossága.
Mi lehet ennek a játéknak a megoldása, vagyis milyen stratégiákat fognak választani a játékosok (akikről, ne felejtsük, feltettük, hogy csak a saját hasznosságukat maximalizálják)? Első látásra azt várnánk, hogy mindkettőjük számára az a legjobb választás, ha nem vallanak, hiszen így mindketten szabadok maradnak. Viszont ha Sor tudja, hogy Oszlop nem vall, akkor ő jobban jár, ha vall, mivel pénzjutalmat is kap. Sőt, akkor is jobban jár, ha Oszlop vall, hiszen akkor legalább a pénzjutalmat megkapja.
Ebben a játékban a ,,vall'' stratégia dominálja a ,,nem vall'' stratégiát, azaz a másik stratégiánál nagyobb hasznossághoz vezet ‐ bármit választ is a másik játékos. Ilyenkor azt mondjuk, hogy a játék ,,domináns egyensúllyal'' rendelkezik, amelyben mindkét játékos a másikra vall, börtönbe kerül, és elteszi a pénzjutalmat. Érdemes megjegyezni, hogy ez az eredmény független attól, hogy milyen pozitív számot rendelünk a pénzjutalomhoz, ill. a szabadon bocsátáshoz.
Formálisan: Egy kétszemélyes

J

játékot adottnak tekintünk, ha adottak a

Σ_{1}

Σ_{2}

stratégiahalmazok, valamint az ezeken értelmezett

H_{1} (σ_{1}, σ_{2})

H_{2} (σ_{1}, σ_{2})

hasznosságfüggvények, ahol a hasznosságfüggvény

i

-edik argumentuma az

i

-edik játékos által választott stratégia (

σ_{1} \in Σ_{1}

σ_{2} \in Σ_{2}

).
Ha létezik egy

(σ_{1}^{*}, σ_{2}^{*}) \in Σ_{1} \times Σ_{2}

stratégiapár, amelyre

\begin{matrix} H_{1} (σ_{1}^{*}, σ_{2}) \geq H_{1} (σ_{1}, σ_{2}) és H_{2} (σ_{1}, σ_{2}^{*}) \geq H_{2} (σ_{1}, σ_{2}) \end{matrix}

bármely

σ_{1} \in Σ_{1}

σ_{2} \in Σ_{2}

stratégiára, akkor azt mondjuk, hogy

(σ_{1}^{*}, σ_{2}^{*})

domináns egyensúly.
A kétszemélyes játékoknak megemlítjük néhány speciális osztályát: ilyenek a zérus összegű játékok, amelyekben a játékosok adott stratégiához tartozó hasznosságainak összege mindig nulla (

H_{1} (σ_{1}, σ_{2}) = - H_{2} (σ_{1}, σ_{2})

), és a szimmetrikus játékok, ahol a két játékos stratégiahalmaza megegyezik, és a fordított stratégiapárok a másik játékos számára azonos hasznosságokat eredményeznek (

H_{1} (σ_{1}, σ_{2}) = H_{2} (σ_{2}, σ_{1})

). A fogolydilemma szimmetrikus, de nem zérus összegű játék.

Nash-egyensúly

A fogolydilemmában volt domináns egyensúly, de a legtöbb játékban nincs. Mit tudunk mondani a játék kimeneteléről ezekben az esetekben?
Vegyük például a következő játékot, amelynek angol neve ,,battle of sexes'' (magyarra talán családi vitaként fordíthatnánk): Sor és Oszlop együtt járnak, és szombat esti programjukat tervezik. Sor rockkoncertre szeretne menni, Oszlop viszont otthon szeretne maradni, hogy tanuljon. Egyikük sem szeretné azonban a másik nélkül tölteni az estét. Ha a kedvenc időtöltéshez is és az együttléthez is 1-et rendelünk hozzá, akkor a játékot az alábbi táblázatban foglalhatjuk össze:

\begin{matrix} Oszlop \\ Koncert & Tanulás \\ Sor & Koncert & 2 & 1 & 1 & 1 \\ Tanulás & 0 & 0 & 1 & 2 \end{matrix}

A szimmetrikus, nem zérus összegű játékban a fogolydilemmához hasonlóan létezik domináns egyensúly: az, amikor Sor koncertre megy, Oszlop pedig otthon marad. Változtassuk meg azonban a játék feltételeit úgy, hogy az együttes programot ‐ bármelyik legyen is az ‐ a ,,kedvenc'' program elé helyezzük:

\begin{matrix} Oszlop \\ Koncert & Tanulás \\ Sor & Koncert & 2 & 1 & 0 & 0 \\ Tanulás & 0 & 0 & 1 & 2 \end{matrix}

Ez a játék továbbra is szimmetrikus, és persze nem zérus összegű. Ha a hasznosságokat alaposan szemügyre vesszük láthatjuk, hogy az eddigi esetektől eltérően egyik játékosnak sincs olyan stratégiája, amely jobb lenne a másiknál függetlenül attól, hogy mit választ a másik játékos. Ezért egyik stratégia sem dominálja a másikat, így domináns egyensúly sincs.
Mi lesz a megoldás? Ha Oszlop tanulni fog, Sornak is érdemesebb otthon maradnia. Ha viszont Sor otthon marad, Oszlopnak is érdemes tanulnia. Találtunk tehát egy olyan pontot, amely stabil: egyik játékosnak sem érdemes más stratégiát választania, kilépnie az egyensúlyi pontból. Az ilyen egyensúlyt nevezzük Nash-egyensúlynak.
Formálisan: ha létezik egy

(σ_{1}^{*}, σ_{2}^{*}) \in Σ_{1} \times Σ_{2}

stratégiapár, amelyre

\begin{matrix} H_{1} (σ_{1}^{*}, σ_{2}^{*}) \geq H_{1} (σ_{1}, σ_{2}^{*}) \end{matrix}

bármely

σ_{1} \in Σ_{1}

stratégiára, és

\begin{matrix} H_{2} (σ_{1}^{*}, σ_{2}^{*}) \geq H_{2} (σ_{1}^{*}, σ_{2}) \end{matrix}

bármely

σ_{2} \in Σ_{2}

stratégiára, akkor

(σ_{1}^{*}, σ_{2}^{*})

Nash-egyensúly.
Az egyensúlyt nemcsak kétszemélyes, hanem

n

-személyes játékokra is definiálhatjuk. Hasonlóan a korábbiakhoz egy

n

-személyes

J

játékot adottnak tekintünk, ha adottak a

Σ_{1}, ..., Σ_{i}, ..., Σ_{n}

stratégiahalmazok (

i = 1, ..., n

), valamint az ezeken értelmezett

H_{1} (σ_{1}, ..., σ_{n}), ..., H_{i} (σ_{1}, ..., σ_{n}), ..., H_{n} (σ_{1}, ..., σ_{n})

hasznosságfüggvények (

σ_{i} \in Σ_{i})

.
Ha létezik

(σ_{1}^{*}, ..., σ_{n}^{*})

stratégiapont, amely mellett minden

i = 1, ..., n

szereplőre igaz az, hogy

H_{i} (σ_{1}^{*}, ..., σ_{i}^{*}, ...,, σ_{n}^{*}) \geq H_{i} (σ_{1}^{*}, ..., σ_{i - 1}^{*}, σ_{i}, σ_{i + 1}^{*}, ..., σ_{n}^{*})

bármely

σ_{i} \in Σ_{i}

stratégiára, a pontot Nash-egyensúlynak nevezzük.
Míg a domináns egyensúllyal az volt a probléma, hogy a legtöbb játékban nem létezik, a Nash-egyensúly esetén az is gond, hogy nem feltétlenül egyértelmű. A fenti játékban ugyanis könnyen mutathatunk még egy ilyen pontot: ha mindkét játékos koncertre megy.

Kevert stratégiák

A fenti játékokat tovább lehet bővíteni az úgynevezett kevert stratégiák bevezetésével, amelyek az egyes játékosok stratégiahalmazait bővítik a stratégiák

p_{i}

eloszlásvektorokkal ,,súlyozott'' változataival (

\sum_{j = 1}^{S_{i}} p_{i}^{j} = 1

p_{i}^{j} \geq 0

, ahol

S_{i}

i

-edik játékos stratégiáinak száma a bővítés előtt). Mivel bővítettük a stratégiák halmazát, az azon értelmezett kifizetésfüggvények halmazát is bővítenünk kell: a kevert stratégiákhoz tartozó kifizetések a kifizetésfüggvény eredeti értékeinek a

p_{i}

eloszlásvektorral súlyozott várható értékei lesznek.
A két stratégiás esetben tehát az egyik játékosnak egy kevert stratégiája az, ha

p

valószínűséggel az egyik, (

1 - p

) valószínűséggel pedig a másik stratégiát választja. A gyakorlatban ez például azt jelentheti, hogy ha egy adott játékot egy pillanatban többször is lejátszanak,

p

gyakorisággal az egyiket, míg (

1 - p

) gyakorisággal a másikat választja a játékos. Az eddig tárgyalt stratégiákat (amelyek esetén

p = 1

) ezentúl tiszta stratégiáknak nevezzük.
Vegyük például a pénzfeldobós játékot, ahol a két játékos egyszerre dob fel egy-egy pénzérmét és megállapodnak, hogy ha azonos oldalra esnek az egyikük nyer, ellenkező esetben viszont a másik. Ezt a játékot az alábbi táblázattal jellemezhetjük (Sor nyer, ha azonosak az oldalak):

\begin{matrix} Oszlop \\ Fej & Írás \\ Sor & Fej & 1 & - 1 & - 1 & 1 \\ Írás & - 1 & 1 & 1 & - 1 \end{matrix}

A fenti játék zérus összegű. Akárcsak a családi vitának, a pénzfeldobós játéknak sincs domináns egyensúlya. Sőt, a tiszta stratégiák halmazán még Nash-egyensúlya sincs ‐ ezt könnyen ellenőrizhetjük a négy eset végiggondolásával: valamelyik játékosnak mindig érdemes stratégiát váltania, ha feltételezi, hogy a másik játékos nem vált stratégiát. ,,Stratégiát váltani'' itt persze annyit jelent, hogy a másik oldalára esik az érme.
A

p = \frac{1}{2}

kevert stratégia azonban mindkét játékos számára Nash-egyensúly, hiszen ennek a stratégiának a kifizetése a másik játékos bármilyen választása esetén nulla ‐ így ez a stratégia a kölcsönösen legjobb választás mindkettőjük számára.
Nash többek között bebizonyította, hogy ha véges számú játékost és véges számú tiszta stratégiát feltételezünk, akkor létezik Nash-egyensúly a játékban. Az egyensúlyban azonban lehet, hogy kevert stratégiát játszanak a játékosok ‐ előbbi példánkban is ez volt a helyzet.

Egy érdekes alkalmazás

Nemrég ,,Gesztiméter'' címmel egy televíziós vetélkedőt láthattunk az egyik kereskedelmi televízión, amelynek címe műsorvezetőjének, Geszti Péternek nevére utalt (a játék internetes oldala még elérhető a www.gesztimeter.hu címen). A játékban olyan kérdéseket tettek fel, melyekre kétféle választ lehetett adni (például: ki írta az Aida című operát: Verdi vagy Puccini?). A játékosoknak azonban nem azt kellett kitalálni, hogy melyik a helyes válasz, hanem kétféle játék volt: az egyikben azok nyertek, akik arra tippeltek, amit többen választottak, a másikban viszont azok, akik arra tippeltek, amit kevesebben választottak. (A játékosok száma páratlan volt, ezért döntetlen nem alakulhatott ki.)
Most és a következőkben feltesszük, hogy minden játékos tudja, hogy az Aidá-t Verdi írta. Mi lehet az egyensúlyi stratégia az egyes esetekben? Írjuk fel először a többségi játékot három játékosra. Szokásos felírásunkat most nem alkalmazhatjuk, ezért felsoroljuk az összes esetet, és ahhoz rendeljük a hasznosságokat (J1, J2, J3 jelöli a három játékos stratégiáját, H1, H2 és H3 pedig a hozzájuk tartozó hasznosságokat):

\begin{matrix} J1 & J2 & J3 & H1 & H2 & H3 \\ Verdi & Verdi & Verdi & 1 & 1 & 1 \\ Verdi & Verdi & Puccini & 1 & 1 & 0 \\ Verdi & Puccini & Verdi & 1 & 0 & 1 \\ Verdi & Puccini & Puccini & 0 & 1 & 1 \\ Puccini & Verdi & Verdi & 0 & 1 & 1 \\ Puccini & Verdi & Puccini & 1 & 0 & 1 \\ Puccini & Puccini & Verdi & 1 & 1 & 0 \\ Puccini & Puccini & Puccini & 1 & 1 & 1 \end{matrix}

Megállapíthatjuk, hogy nincs domináns stratégia. Nash-egyensúly azonban kettő is van a tiszta stratégiák halmazán: ha mindhárman Verdi-t, vagy ha mindhárman Puccini-t választanak. Ellenőrizzük először a váratlan Puccini választást: ha bármely két játékos Puccini-t választ, a harmadiknak nem érdemes Verdi-t választania, hiszen kisebbségbe kerül. Ugyanez igaz a jobban várt három Verdire is ‐ ha bármely két játékos Verdi-t választ, a harmadiknak nem érdemes Puccinit választania, hiszen kisebbségbe kerül.
Matematikai problémákra nem mindig jellemző az, hogy a megoldás helyességét a valóságban is ellenőrizhetjük ─ itt a televíziós játék miatt lehetőséget kaptunk erre. A játékok során szinte mindig az az egyensúlyi pont alakult ki, ahol mindenki az igaz választ tippelte (esetünkben a három Verdi). A játékosok számára a két egyensúlyi pont közötti választásban mégis szerepet játszott az is, hogy mi a válasz a kérdésre (eddig ezt az információt nem használtuk).
Mi a helyzet a fordított játék esetében, ahol a kisebbséghez tartozók nyertek? Esetükben is felírjuk az egyes stratégiahármasokhoz tartozó hasznosságokat:

\begin{matrix} J1 & J2 & J3 & H1 & H2 & H3 \\ Verdi & Verdi & Verdi & 0 & 0 & 0 \\ Verdi & Verdi & Puccini & 0 & 0 & 1 \\ Verdi & Puccini & Verdi & 0 & 1 & 0 \\ Verdi & Puccini & Puccini & 1 & 0 & 0 \\ Puccini & Verdi & Verdi & 1 & 0 & 0 \\ Puccini & Verdi & Puccini & 0 & 1 & 0 \\ Puccini & Puccini & Verdi & 0 & 0 & 1 \\ Puccini & Puccini & Puccini & 0 & 0 & 0 \end{matrix}

Ebben a játékban sincs domináns egyensúly. Viszont hat Nash-egyensúly is van: amelyben ketten az egyikre, egy valaki pedig a másikra tippel. A kisebbségre tippelőnek nyilván nem érdemes másra tippelnie, hiszen nyertesből vesztessé válna. A többséghez tartozó tippelő pedig hiába áll át a kisebbséghez, azt többséggé változtatja, ezért ismét csak nem tud győztessé válni.
A televíziós játékok során ez az eredmény be is következett: a kérdéstől függetlenül szinte mindig közel fele-fele arányban voltak az egyik és a másik válaszra tippelők.
Ha a problémát általánosítjuk, és a játékosok számát

2 k + 1

-re növeljük, a többségi játékban továbbra is két Nash-egyensúly marad, amikor mindenki ugyanarra tippel. A kisebbségi játékban minden olyan eset Nash-egyensúly, ahol

k

játékos az egyikre,

k + 1

játékos pedig a másik válaszra tippel, azaz az egyensúlyok száma igen nagy,

\frac{(2 k + 1)!}{k! (k + 1)!}

Ajánlott irodalom

Akik a témában mélyebben szeretnének elmélyülni, azoknak javaslom Szép Jenő ‐ Forgó Ferenc: Bevezetés a játékelméletbe, Közgazdasági és Jogi Könyvkiadó (1974) című könyvét. A játékelmélet oktatásához hasznos Filep László: Játékelmélet, Tankönyvkiadó (1985), Radnainé Szendrei Julianna: A játék matematikája, Tankönyvkiadó (1976) vagy Eső Péter ‐ Rátfai Attila ‐ Világi Balázs: Nem-kooperatív játékelmélet, BKE (1992) műve. A közgazdasági alkalmazások iránt érdeklődőknek pedig érdemes tanulmányozniuk Martin J. Osborne ‐ Ariel Rubinstein: A Course in Game Theory, MIT press (1996) és Jean Tirole: Theory of Industrial Organizations, MIT press (1988) című könyveit.

Radnai Márton

¹Köszönetet mondok szüleimnek és Váradi Balázsnak, akik értékes megjegyzéseivel és javaslataival segítették munkámat.