Vi studerar den deterministiska och randomiserade frågekomplexiteten hos att hitta ungefärlig jämvikt i ett k × k bimatrix-spel. Vi visar att den deterministiska frågan komplexitet att hitta en -Nash jämvikt när < 1 2 är (k 2 ), även i noll ett konstant-sum spel. I kombination med tidigare resultat [Fearnley et al. 2013 ], detta ger en fullständig karakterisering av den deterministiska frågekomplex av ungefärlig Nash equilibria. Vi studerar också randomiserade frågealgoritmer. Vi ger en randomiserad algoritm för att hitta en ( 2 ) payoff frågor, som visar att 1 2 barriär för deterministiska algoritmer kan brytas genom randomisering. För väl stöttade Nash Equilibria (WSNE), ger vi först en randomiserad algoritm för att hitta en -WSNE av en nollsumma bimatrix spel med hjälp av O( k·log k 4 ) payoff frågor, och vi använder sedan detta för att få en randomiserad algoritm för att hitta en ( 2 3 + )-WSNE i en allmän bimatrix spel med hjälp av O( k·log k 4 ) payoff frågor. Slutligen inleder vi studien av lägre gränser mot randomiserade algoritmer i samband med bimatrix spel, genom att visa att randomiserade algoritmer kräver (k 2 ) payoff frågor för att hitta en -Nash jämvikt med < 1 4k, även i noll ett konstant-sum spel. Detta utesluter särskilt frågeeffektiva randomiserade algoritmer för att hitta exakta Nash equilibria.
För slumpmässig frågekomplexitet visade REF en lägre gräns för att hitta en ε-ungefärlig Nash-jämvikt, där ε < 1 /4N.
Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries
{'venue': 'TEAC', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}