Lemke-Hauson algoritam

je algoritam za računanje Nešovog ekvilibrijuma dvomatrične igre. Tvrdi se da je ovo "najbolji poznati kombinatorni algoritam za pronalaženje Nešovog ekvilibrijuma".

Algoritam Ulaz algoritma je igra dva igrača, G. G je predstavljena matricama igara A i B, dimenzija m × n, koje sadrže dobiti igrača 1 i 2 respektivno, koji imaju m i n čistih strategija respektivno. Od sada pa nadalje pretpostavljamo da su sve dobiti pozitivne (jer se skaliranjem svaka igra može transformisati u strateški ekvivalentnu igru sa pozitivnim dobitima).

G ima dva odgovarajuća politopa (zvani politopi najboljeg odziva) P1 i P2, u m dimenzija i n dimenzija respektivno, definisana na sledeći način:

P1 je iz Rm; neka {x1,...,xm} predstavlja koordinate. P1 je definisano sa m nejednakosti xi ≥ 0, za sve i ∈ {1,...,m}, i dodatnih n nejednakosti B1,jx1+...+Bm,jxm ≤ 1, za sve j ∈ {1,...,n}.

P2 je iz Rn; neka {xm+1,...,xm+n} predstavlja koordinate. P2 je definisano sa n nejednakosti xm+i ≥ 0, za sve i ∈ {1,...,n}, i dodatnih m nejednakosti Ai,1xm+1+...+Ai,nxm+n ≤ 1, za sve i ∈ {1,...,m}.

P1 predstavlja skup nenormalizovanih raspodela verovatnoće za m čistih strategija igrača 1, tako da je očekivana dobit igrača 2 najviše 1. Prvih m uslova ograničava verovatnoće na nenegativne vrednosti, a drugih n uslova ograničava očekivanu dobit svake od n čistih strategija igrača 2 na najviše 1. P2 ima slično značenje, pri čemu su uloge igrača obrnute.

Svako teme P1 je povezano sa skupom oznaka iz skupa {1,...,m + n} na sledeći način. Za i ∈ {1, ..., m}, teme v dobija oznaku i ako je xi = 0 u temenu v. Za j ∈ {1, ..., n}, teme v dobija oznaku m + j ako je B1,jx1 + ... + Bm,jxm = 1. Pod pretpostavkom da je P1 nedegenerisano, svako teme je vezano za m pljosni P1 i ima m oznaka. Primetimo da izvor, koji je teme P1, ima oznake {1, ..., m}.

Svako teme P2 povezano sa skupom oznaka iz skupa {1, ..., m + n} na sledeći način. Za j ∈ {1, ..., n}, Teme w dobija oznaku m + j ako je xm+j = 0 u temenu w. Za i ∈ {1, ..., m}, teme w dobija oznaku i ako je Ai,1xm+1 + ... + Ai,nxm+n = 1. Pod pretpostavkom da je P2 nedegenerisano, svako teme je vezano za m pljosni P2 i ima m oznaka. Primetimo da izvor, koji je teme P2, ima oznake {m + 1, ..., m + n}.

Posmatrajmo par temena (v,w), v ∈ P1, w ∈ P2. Kažemo da je (v,w) potpuno označen ako skupovi pridruženi v i w sadrže sve oznake iz {1, ..., m + n}. Primetimo da ako su v and w izvori Rm i Rn respektivno, onda je (v,w) potpuno označen. Kažemo da je (v,w) skoro potpuno označen (u pogledu nedostajuće oznake g) ako skupovi pridruženi v i w sadrže sve oznake iz {1, ..., m + n} osim g. U tom slučaju će postojati duplikatna oznaka koja je pridružena i v i w.

Pivot operacija podrazumeva zamenu v u paru (v,w) nekim drugim temenom susednim v u P1, ili alternativno zamenom w nekim drugim temenom susednim w u P2. Efekat operacije je (u slučaju da je v zamenjeno) zamena neke oznake v nekom drugom oznakom. Za zamenjenu oznaku se kaže da je odbačena. Za bilo koju zadatu oznaku v, moguće je odbaciti datu oznaku pomeranjem na teme susedno v koje ne sadrži hiperravan povezanu sa tom oznakom.

Algoritam polazi od potpuno označenog para (v,w) sastavljenog od para izvora. Proizvoljena oznaka g se odbaci pivot operacijom, dovodeći nas do skoro potpuno označenog para (v′,w′). Bilo koji skoro potpuno označeni par podleže dvema pivot operacijama koje odgovaraju odbacivanju jedne ili druge kopije duplikatne oznake i svaka od ovih operacija može rezultovati novim skoro potpuno označenim parom ili kompletno označenim parom. Najzad, algoritam pronalazi potpuno označeni par (v*,w*), koji nije izvor. (v*,w*) odgovara paru nenormalizovanih raspodela verovatnoće u kojima svaka strategija i igrača 1 donosi dobit 1, ili donosi dobit manju od 1 i igrana je sa verovatnoćom 0 od strane igrača 1 (slično opažanje važi i za igrača 2). Normalizovanjem ovih vrednosti na raspodele verovatnoće dobijamo Nešov ekvilibrijum (čije dobiti za igrače su inverzije normalizacionih faktora).

Osobine algoritma Algoritam može da pronađe najviše n + m različitih Nešovih ekvilibrijuma. Izbor prvobitno odbačene oznake određuje koji će ekvilibrijum na kraju algoritam da pronađe.

Lemke-Hauson algoritam je ekvivalentan sledećem pristupu zasnovanom na homotopiji: Modifikovati G odabirom proizvoljne čiste strategije g i dati igraču koji poseduje tu strategiju veliku isplatu B da je odigra. U modifikovanoj igri, strategija g se igra sa verovatnoćom 1, a drugi igrač odigrava svoj najbolji odgovor na strategiju g sa verovatnoćom 1. Razmatrati kontinuum igara u kojima se B stalno smanjuje do 0. Postoji putanja Nešovih ekvilibrijuma koja povezuje jedinstveni ekvilibrijum modifikovane igre sa ekvilibrijumom G. Čista strategija g odabrana da dobije bonus B odgovara prvobitno odbačenoj oznaci.

Iako je algoritam efikasan u praksi, u najgorem slučaju broj pivot operacija može eksponencijalno zavisiti od broja čistih strategija u igri.

Takođe, pokazano je da je problem pronalaženja rešenja pomoću Lemke-Hauson algoritma PSPACE-kompletan.

Reference

Категорија:Комбинаторни алгоритми Категорија:Теорија игара