Vi granskar på nytt vad det innebär att beräkna Nash equilibria och mer allmänt vad det innebär att beräkna en fast punkt för en viss Brouwer-funktion, och vi undersöker komplexiteten i de tillhörande problemen. Specifikt studerar vi komplexiteten av följande problem: med tanke på en ändlig spel, Ε, med 3 eller fler spelare, och ges > 0, beräkna en vektor x (en blandad strategi profil) som ligger inom avstånd (säg, l ❌ ) av vissa (exakt) Nash jämvikt. Vi visar att approximationen av en (faktisk) Nash jämvikt för spel med 3 spelare, även inom någon icke-trivial konstant additiv faktor < 1/2 i bara en önskad koordinat, är minst lika svårt som den långvariga kvadrat-rot sum problem, liksom mer allmänna aritmetiska kretsen beslutsproblem, och därmed att även placera approximationsproblem i NP skulle lösa ett stort öppet problem i komplexiteten av numerisk beräkning. Dessutom visar vi att (exakt eller ungefärlig) beräkning av Nash Equilibria för 3 eller fler spelare är komplett för den klass av sökproblem, som vi kallar FIXP, som kan gjutas som fasta punkt beräkningsproblem för funktioner som representeras av algebraiska kretsar (straight line program) över bas {+, *, −, /, max, min}, med rationella konstanter. Vi visar att det linjära fragmentet av FIXP är lika med PPAD. Många problem i spelteori, ekonomi och sannolikhetsteori, kan gjutas som fasta punktproblem för sådana algebraiska funktioner. Vi diskuterar flera viktiga sådana problem: beräkning av värdet av Shapleys stokastiska spel, och enklare spel av Condon, utrotning sannolikheter för förgrening processer, avslutande sannolikheter för stokastiska sammanhangsfri grammatik, och Recursive Markov Chains. Vi visar att för vissa av dem, approximationen, eller till och med exakt beräkning, problem kan placeras i PPAD, medan för andra, de är minst lika svårt som kvadrat-rot summan och aritmetiska kretsen beslutsproblem.
Dessutom är linjärisering också relaterad till Etessami och Yannakakis formulering av PPAD som klass av fasta-punkt problem för bitvis-linjära funktioner (som kan beräknas med +, skala, max) REF.
On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract)
{'venue': "48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)", 'journal': "48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)", 'mag_field_of_study': ['Mathematics', 'Computer Science']}