Vi bevisar existensen av -Nash jämviktsstrategier med stöd logaritmiska i antalet rena strategier. Vi visar också att utdelningar till alla spelare i någon (exakt) Nash jämvikt kan - approximeras av utdelningar till spelarna i vissa sådana logaritmiska stöd -Nash jämvikt. Dessa strategier är också enhetliga på en multiuppsättning av logaritmisk storlek och därför leder detta till en kvasi-polynomal algoritm för att beräkna en -Nash jämvikt. Så vitt vi vet är detta den första subexponentiella algoritmen för att hitta en -Nash jämvikt. Våra resultat håller för alla flerspelarspel så länge antalet spelare är konstant (dvs. det är oberoende av antalet rena strategier). Ett liknande argument visar också att för ett fast antal spelare m, utbetalningar till alla spelare i alla m-tuple av blandade strategier kan - ungefärlig av utbetalningar i vissa m-tuple av konstanta stödstrategier. Vi bevisar också att om payoff matriser av en två person spel har låg rank då spelet har en exakt Nash jämvikt med litet stöd. Detta innebär att om payoff matriser kan väl approximeras av låg matriser, spelet har en - equilibrium med litet stöd. Det innebär också att om payoff matriser har konstant rang kan vi beräkna en exakt Nash jämvikt i polynom tid.
För två spelare spel, Lipton, Mehta, och Markakis gav en kvasi-polynom tid algoritm för att hitta en konstant ungefärlig Nash jämvikt REF.
Playing large games using simple strategies
{'venue': "EC '03", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}