Abstrakt. Kan lära algoritmer hitta en Nash jämvikt? Detta är en naturlig fråga av flera skäl. Lärande algoritmer liknar beteendet hos spelare i många naturligt uppkommande spel, och därmed resultat på konvergens eller icke-konvergens egenskaper av sådan dynamik kan informera vår förståelse av tillämpligheten av Nash equilibria som en rimlig lösning koncept i vissa inställningar. Ett andra skäl till att ställa denna fråga är i hopp om att kunna bevisa ett omöjligt resultat, inte beroende av komplexa antaganden, för att beräkna Nash equilibria via en begränsad klass av rimliga algoritmer. I detta arbete, vi börjar svara på denna fråga genom att överväga dynamiken i standard multiplikativa vikter uppdatera lärande algoritmer (som är kända för att konvergera till en Nash jämvikt för nollsummespel). Vi återbesöker ett 3 × 3 spel som definieras av Shapley [10] på 1950-talet för att fastställa att fiktiva spel inte konvergerar i allmänna spel. För detta enkla spel, visar vi via en potentiell funktion argument att i en mängd olika inställningar multiplikativa uppdateringar algoritmen imponerande misslyckas med att hitta den unika Nash jämvikt, genom att den kumulativa fördelningen av spelare som produceras genom att lära dynamik faktiskt glida bort från jämvikten.
I REF visades det särskilt att algoritmen för multiplikativa uppdateringar inte hittar den unika Nash-jämvikten i 3 × 3 Shapley-spelet.
On Learning Algorithms for Nash Equilibria
{'venue': 'International Symposium on Algorithmic Game Theory', 'journal': None, 'mag_field_of_study': ['Computer Science']}