Geometrical Regret Matching
This work addresses a specific issue in game theory algorithms for researchers and practitioners, but it is incremental as it modifies an existing method without broad new applications.
The paper tackles the problem of 'jumpy' strategy updates in existing regret matching algorithms for Nash equilibrium approximation by proposing a geometrical regret matching that enables smooth strategy updating. The results show that continuously suppressing unprofitable strategies is sufficient for the game to evolve towards equilibrium, though the method has limitations in optimizing approximation accuracy.
We argue that the existing regret matchings for Nash equilibrium approximation conduct "jumpy" strategy updating when the probabilities of future plays are set to be proportional to positive regret measures. We propose a geometrical regret matching which features "smooth" strategy updating. Our approach is simple, intuitive and natural. The analytical and numerical results show that, continuously and "smoothly" suppressing "unprofitable" pure strategies is sufficient for the game to evolve towards Nash equilibrium, suggesting that in reality the tendency for equilibrium could be pervasive and irresistible. Technically, iterative regret matching gives rise to a sequence of adjusted mixed strategies for our study its approximation to the true equilibrium point. The sequence can be studied in metric space and visualized nicely as a clear path towards an equilibrium point. Our theory has limitations in optimizing the approximation accuracy.