Om en klass av spel är känd för att ha en Nash jämvikt med sannolikhetsvärden som är antingen noll eller 1 -och därmed med stöd av begränsad storlek - då uppenbarligen denna jämvikt kan hittas uttömmande i polynom tid. Något överraskande visar vi att det finns en PTAS för den klass av spel vars jämvikt garanteras att ha ) -värden, och därför stora - på - stöd. Vi påpekar också att det finns en PTAS för spel med gles payoff matriser, en familj för vilken det exakta problemet är känt att vara PPAD-fullständig [6]. Båda algoritmerna är av ett speciellt slag som vi kallar omedvetna: Algoritmen bara prover en fast fördelning på par av blandade strategier, och spelet används bara för att avgöra om de utvalda strategierna utgör en -Nash jämvikt; svaret är "ja" med omvänd polynom sannolikhet (i det andra fallet är algoritmen faktiskt deterministisk). Dessa resultat medför frågan: Finns det en glömsk PTAS för att hitta en Nash jämvikt i allmänna spel? Vi besvarar denna fråga i negativ; vår nedre gräns kommer nära den kvasi-polynomiska övre gränsen [18]. En annan nyligen PTAS för anonyma spel [13, 14, 7] är också omedvetna i en svagare mening lämplig för denna klass av spel (det prover från en fast distribution på oordnade samlingar av blandade strategier), men dess körtid är exponentiellt i 1. Vi bevisar att alla omedvetna PTAS för anonyma spel med två strategier och tre spelare typer måste ha, gör algoritmen i [7] (som fungerar med eventuellt begränsat antal spelare typer) i huvudsak optimal inom omedvetna algoritmer. I kontrast, vi utformar en poly(n) · (1/ ) O(log 2 (1/ )) non-oblivious PTAS för anonyma spel med två strategier och eventuellt begränsat antal spelare typer. Den viktigaste idén med vår algoritm är att söka inte över oordnad * Detta arbete gjordes medan författaren var en postdoktor vid Microsoft Research, New England. † Med stöd av NSF beviljar CCF -0635319, en gåva från Yahoo! Forskning, och ett MICRO-bidrag. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. uppsättningar av blandade strategier, men över en noggrant utformad uppsättning samlingar av de första O(log 1 ) ögonblicken av fördelningen av antalet spelare spelar strategi 1 vid jämvikt. Algoritmen fungerar på grund av ett probabilistiskt resultat av mer allmänt intresse som vi bevisar: det totala variationsavståndet mellan två belopp av oberoende indikator slumpmässiga variabler minskar exponentiellt med antalet ögonblick av de två belopp som är lika, oberoende av antalet indikatorer.
Dessutom har REF visat sig vara en lägre gräns på den körtid som krävs av en omedveten algoritm, som låter den senare algoritmen vara i huvudsak optimal.
On oblivious PTAS's for nash equilibrium
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}