I den här artikeln undersöker vi komplexitetsfrågor relaterade till ren Nash equilibria av strategiska spel. Vi visar att, även i mycket restriktiva inställningar, avgöra om ett spel har en ren Nash Equilibrium är NP-hård, samtidigt avgöra om ett spel har en stark Nash jämvikt är St-fullständig. Därefter studerar vi praktiskt taget relevanta restriktioner som minskar komplexiteten. I synnerhet är vi intresserade av kvantitativa och kvalitativa begränsningar av hur varje spelares rörelse beror på andra spelares rörelser. Vi säger att ett spel har litet område om "nyttofunktionen för varje spelare beror endast på (åtgärder av) ett logaritmiskt litet antal andra spelare, Beroendestrukturen i ett spel G kan han uttryckas av en graf G(G) eller av en hypergraf I-I(G). Bland andra resultat, visar vi att om jC har litet område och I-I(G) har botmdecl hypertree bredd (eller om G(G) har avgränsat trädbredd), då hitta ren Nash och Pareto equilibria är möjligt i polynom tid. Om spelet är grafiskt, då dessa problem är LOGCFL-komplett och därmed i klassen _NC~ av mycket parallelliserbara problem.
Även om det är naturligtvis lätt att hitta ren Nash jämvikt av normala form spel, Gottlob et al. REF visar att de flesta versioner av problemet med att hitta ren Nash Equilibria är svårt när spelet beskrivs kortfattat.
Pure Nash equilibria: hard and easy games
{'venue': "TARK '03", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}