Characterizing the Convergence of Game Dynamics via Potentialness
Authors: Martin Bichler, Davide Legacci, Panayotis Mertikopoulos, Matthias Oberlechner, Bary Pradelski
TMLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We conduct our numerical experiments on randomly generated and economically motivated games. Our analysis focuses mainly on two aspects, namely, the existence of strict pure Nash-equilibria (SPNE) and the convergence of learning dynamics as a function of the potentialness of the games. |
| Researcher Affiliation | Academia | Martin Bichler EMAIL Department of Computer Science, Technical University of Munich Davide Legacci EMAIL Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG Panayotis Mertikopoulos EMAIL Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG Matthias Oberlechner EMAIL Department of Computer Science, Technical University of Munich Bary Pradelski EMAIL Maison Française d Oxford, CNRS |
| Pseudocode | Yes | Algorithm 1: Online Mirror Descent Input : initial mixed strategies si,0 for t = 1 to T do for agent i = 1 to N do observe gradient vi,t; set si,t Psi,t 1(ηtvi,t); end end |
| Open Source Code | Yes | The code is available on Github at https://github.com/MOberlechner/games_learning. |
| Open Datasets | No | To generate a random game G = (N, A, u) for a certain setting (number of agents N and actions per agent Ai), we independently sample each payoff value from a uniform distribution, i.e., ui(a) U([0, 1]) for all a A and i N; our dataset consists of 106 games for each considered setting. For economic games, we discretize each action space Ai into Ai equidistant points. |
| Dataset Splits | No | The paper describes generating games and running simulations (e.g., "randomly sampled 25 initial strategies"), but does not refer to traditional dataset splits (e.g., train/test/validation) in the context of model training or evaluation. |
| Hardware Specification | No | The average runtime (over 100 runs) for computing potentialness in our experiments, performed on a standard notebook, is shown in Figure 2. This does not provide specific hardware details (e.g., CPU/GPU model, memory). |
| Software Dependencies | No | The paper does not explicitly state any specific software dependencies with version numbers. |
| Experiment Setup | Yes | We use a step-size sequence of the form ηt = η0 t β for some η0 > 0 and β (0, 1], and consider Algorithm 1 to have converged to an (approximate) NE of the game if the relative utility loss, ℓi(st) = 1 ui(st)/ui(bri, s i,t), falls below a predefined tolerance of ε = 10 8 for all agents i N within a fixed number of iterations, T = 2 000. In the above, bri denotes a best response of agent i given the opponents strategy profile s i,t. For each group k, we run Algorithm 1 with step-size ηt = η0 t β, letting η0 = 23 and β = 20 1. The initial condition is fixed to the uniform strategy, si,0 = A 1 i 1, for all agents i. |