Beating Price of Anarchy and Gradient Descent without Regret in Potential Games
Authors: Iosif Sakos, Stefanos Leonardos, Stelios Andrew Stavroulakis, William Overman, Ioannis Panageas, Georgios Piliouras
ICLR 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, in section 5, we present experiments in larger PGs for which risk-and payoff-dominance can be properly generalized (diagonal payoff matrices). Such games are, in fact, designed to be as hard as possible from the perspective of average case performance due to their exponentially large number of NE and unbounded Po A. However, as our experimental results rather surprisingly indicate, increasing the size of the game seems to have little to no effect on average-case or relative performance and the analogues of Theorem 4.6, i.e., comparative performance of RD and GD, and Theorem 4.8, i.e., bounded APo A (in fact typically around 1.2), continue to hold. |
| Researcher Affiliation | Academia | Iosif Sakos Singapore University of Technology and Design iosif_sakos@mymail.sutd.edu.sg Stefanos Leonardos King s College London stefanos.leonardos@kcl.ac.uk Stelios Andrew Stavroulakis UC Irvine sstavrou@uci.edu William Overman Graduate School of Business, Stanford University wpo@stanford.edu Ioannis Panageas UC Irvine ipanagea@ics.uci.edu Georgios Piliouras Singapore University of Technology and Design georgios@sutd.edu.sg |
| Pseudocode | No | The paper does not contain any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper describes generating random game instances for experiments ("In each game, the payoffs u1, u2, . . . , um are selected (pseudo-)randomly and satisfy the following properties:"). It does not mention using or providing access information for a publicly available or open dataset in the traditional sense. |
| Dataset Splits | No | The paper describes simulating dynamics on sampled game instances and initial conditions, but it does not specify training, validation, or test dataset splits. For example, it states, "For each dimension, we sample 100 random games and run the gradient descent and standard replicator dynamics for 1000 initial conditions till convergence." |
| Hardware Specification | No | The paper does not provide any specific details about the hardware (e.g., GPU models, CPU types, memory) used to run the experiments or simulations. |
| Software Dependencies | No | The paper does not provide any specific software dependencies with version numbers (e.g., programming languages, libraries, or simulation environments). |
| Experiment Setup | Yes | Experimental setup. We run experiments in random 2-agent, symmetric diagonal PRPGs of dimensions m = 2, 3, . . . , 20 (size of each agent s action space). In each game, the payoffs u1, u2, . . . , um are selected (pseudo-)randomly and satisfy the following properties: (i) the lowest diagonal payoff, u1, is at least as large as some predefined positive constant (set equal to 1e-12 for the experiments), (ii) the highest payoff, um, is equal to the dimension, m, of the game, i.e., um = 2, 3, . . . and 20 respectively, and (iii) u2, . . . , um 1 are in ascending order strictly between u1 and um with randomly selected distances between them. For each dimension, we sample 100 random games and run the gradient descent and standard replicator dynamics for 1000 initial conditions till convergence. |