Abstrakt. Vi undersöker hur väl kontinuerligt fiktivt spel i tvåspelarspel presterar i termer av genomsnittlig payoff, särskilt jämfört med Nash jämvikt payoff. Vi visar att i många spel, fiktivt spela överträffar Nash jämvikt i genomsnitt eller ens hela tiden, och dessutom att varje spel är linjärt likvärdigt med en där detta är fallet. Omvänt ger vi villkor under vilka Nash jämvikt payoff dominerar fiktiva spel payoff. Ett viktigt steg i vår analys är att visa att fiktiv lekdynamik asymptotiskt konvergerar uppsättningen av grov korrelerad jämvikt (ett faktum som är implicit i litteraturen). Kontinuerligt fiktivt spel (FP) har först introducerats av Brown [7, 8] och det har sedan dess varit en standardmodell för myopiskt lärande, ofta används som en praktisk referensalgoritm på grund av dess beräknings enkelhet (se t.ex. [11, 31] ). Det har visat sig konvergera till Nash jämvikt i många viktiga klasser av spel, såsom nollsummespel [19], non-degenerate 2 × n games [3], non-degenerate kvasi-supermodulära spel med minskande avkastning eller dimension 3 × n eller 4 × 4 [5, 4] och andra. Å andra sidan är konvergens till Nash jämvikt (även när den är unik) inte garanterad, vilket visas av Shapley berömda exempel [27] av en 3 × 3 Rock-Paper-Scissors-liknande spel med en stabil gräns cykel för FP. I det icke-konvergenta fallet uppstår därför frågan huruvida utdelningen till spelarna längs FP:s banor är fördelaktig i jämförelse med Nash-jämviktsutdelningen. I detta dokument undersöker vi förhållandet mellan Nash jämvikt payoff och genomsnittlig payoff längs FP banor. I synnerhet visar vi att i många tvåspelarspel, kan FP i det långa loppet tjäna en högre payoff till båda spelarna än Nash balansspel, antingen i genomsnitt, eller hela tiden. Vi visar också att varje spel med två spelare är "linjärt likvärdigt" med ett där FP Pareto dominerar Nash jämvikt (vid alla tillfällen, längs varje icke-equilibrium FP omlopp). Omvänt ger vi villkor under vilka ramprogrammet domineras av Nash jämvikt i fråga om utdelning, och visar numeriska exempel på detta (snarare atypiska) beteende. Tidningen är organiserad enligt följande. I avsnitt 1 introducerar vi grundläggande notation. I avsnitt 2 analyserar vi det begränsande beteendet hos FP-dynamiken och visar att FP konvergerar till den så kallade uppsättningen grovkorrelerade jämvikten. I Avsnitt 3 använder vi detta för att jämföra payoff längs gränsen uppsättningar med Nash jämvikt payoffs. I slutändan gör detta att vi kan visa att varje bimatrixspel är linjärt likvärdigt med ett där FP Pareto dominerar Nash jämvikt och vi diskuterar villkoren för utbetalning jämförelse av dessa två. I Avsnitt 4 presenterar vi en viss familj av 3×3 spel där FP ger högre genomsnittlig payoff till båda spelarna än Nash jämvikt. I Avsnitt 5 undersöker vi möjligheten av spel där Nash jämvikt spel dominerar FP. Vi drar också slutsatser om villkoren för detta och fastställer numeriskt exempel där så är fallet. Diskussionen visar att dessa exempel är relativt sällsynta. Slutligen, i avsnitt 6 diskuterar vi konsekvenserna av dessa resultat för begreppen jämvikt (i samband med avkastning prestanda lärande algoritmer) och spel likvärdighet. Författarna vill tacka Christopher Harris, Sergiu Hart och Ulrich Berger för användbara diskussioner och kommentarer.
Ostrovski och van Strien REF studerade FP:s konvergens och banor i kontinuerlig tid för 3 × 3 matcher.
Payoff Performance of Fictitious Play
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}