Average complexity of the Best Response Algorithm in Potential Games

Stéphane Durand,Bruno Gaujal

Average complexity of the Best Response Algorithm in Potential Games

2016

Stéphane Durand
Bruno Gaujal

The best response algorithm is often used in game theory to find Nash equilibria, its worst case complexity is known.This article show the exact complexity of the best response algorithm in random potential games.

Keywords:

Game theory
Best response
Worst-case complexity
Mathematical optimization
Best, worst and average case
Time complexity
Algorithm
Mathematics
Average-case complexity
Nash equilibrium
Game complexity
Mathematical economics

Correction
Source
Cite
Save
Machine Reading By IdeaReader

References

Citations