Lemke-Hauson algoritam

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) P₁ i P₂, u m dimenzija i n dimenzija respektivno, definisana na sledeći način:

P₁ je iz R^m; neka {x₁,...,x_m} predstavlja koordinate. P₁ je definisano sa m nejednakosti x_i ≥ 0, za sve i ∈ {1,...,m}, i dodatnih n nejednakosti B_1,jx₁+...+B_m,jx_m ≤ 1, za sve j ∈ {1,...,n}.

P₂ je iz Rⁿ; neka {x_m+1,...,x_m+n} predstavlja koordinate. P₂ je definisano sa n nejednakosti x_m+i ≥ 0, za sve i ∈ {1,...,n}, i dodatnih m nejednakosti A_i,1x_m+1+...+A_i,nx_m+n ≤ 1, za sve i ∈ {1,...,m}.

P₁ 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. P₂ ima slično značenje, pri čemu su uloge igrača obrnute.

Svako teme P₁ 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 x_i = 0 u temenu v. Za j ∈ {1, ..., n}, teme v dobija oznaku m + j ako je B_1,jx₁ + ... + B_m,jx_m = 1. Pod pretpostavkom da je P₁ nedegenerisano, svako teme je vezano za m pljosni P₁ i ima m oznaka. Primetimo da izvor, koji je teme P₁, ima oznake {1, ..., m}.

Svako teme P₂ 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 x_m+j = 0 u temenu w. Za i ∈ {1, ..., m}, teme w dobija oznaku i ako je A_i,1x_m+1 + ... + A_i,nx_m+n = 1. Pod pretpostavkom da je P₂ nedegenerisano, svako teme je vezano za m pljosni P₂ i ima m oznaka. Primetimo da izvor, koji je teme P₂, ima oznake {m + 1, ..., m + n}.

Posmatrajmo par temena (v,w), v ∈ P₁, w ∈ P₂. 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 R^m i Rⁿ 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 P₁, ili alternativno zamenom w nekim drugim temenom susednim w u P₂. 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.