Abstrakt. Att hitta en jämvikt av en omfattande form spel av ofullständig information är ett grundläggande problem i beräkningsspel teori, men nuvarande tekniker inte skala till stora spel. För att ta itu med detta introducerar vi det beställda spelet isomorfism och den relaterade beställda spelet isomorf abstraktion omvandling. För ett flerspelars sekventiellt spel med ofullständig information med observerbara åtgärder och ett beställt signalutrymme, bevisar vi att varje Nash-jämvikt i ett abstrakt mindre spel, som erhålls genom en eller flera tillämpningar av omvandlingen, enkelt kan omvandlas till en Nash-jämvikt i det ursprungliga spelet. Vi presenterar en algoritm, GameShrink, för abstraktion spelet med hjälp av vår isomorfism uttömmande. Dess komplexitet är Õ(n 2 ), där n är antalet noder i en struktur som vi kallar signalträdet. Det är inte större än spelet träd, och på icke-triviala spel är det drastiskt mindre, så GameShrink har tid och utrymme komplexitet sublinear i storleken på spelet träd. Med GameShrink hittar vi en balans till ett pokerspel med 3,1 miljarder noder-över fyra storleksordningar mer än i det största pokerspelet löst tidigare. För att ta itu med ännu större spel, introducerar vi approximativa metoder som inte bevarar jämvikt, men ändå avkastning (ex post) bevisligen nära-optimala strategier.
Lossless abstraktion algoritmer REF ser till att varje jämvikt i det abstrakta spelet också är en jämvikt i det ursprungliga spelet.
Lossless abstraction of imperfect information games
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}