I detta papper beräknar vi den värsta-fall och genomsnittliga genomförandetiden för Best Response Algorithm (BRA) för att beräkna en ren Nash jämvikt i finita potentiella spel. Vårt tillvägagångssätt är baserat på en Markov-kedjemodell av BRA och en kopplingsteknik som omvandlar den genomsnittliga exekveringstiden för denna diskreta algoritm till en lösning av en vanlig differentialekvation. I ett potentiellt spel med N spelare och A strategier per spelare, visar vi att det värsta fallet komplexitet BRA (antal drag) är exakt N A N - 1, medan dess genomsnittliga komplexitet över slumpmässiga potentiella spel är lika med e γ N + O (N ), där γ är Euler konstant. Vi visar också att det effektiva antalet stater som besöks av BRA är lika med log N + c + O(1/N ) (med c e γ ), i genomsnitt. Slutligen visar vi att BRA beräknar en ren Nash Equilibrium snabbare (i stark stokastisk ordning) än någon lokal sökalgoritm över slumpmässiga potentiella spel.
Det har visats i REF att i slumpmässiga potentiella spel med n spelare där varje spelare har som mest en strategi, är det värsta fallet konvergens tid n · en n−1.
Complexity and Optimality of the Best Response Algorithm in Random Potential Games
{'venue': 'SAGT', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}