Computing Optimal Nash Equilibria in Multiplayer Games
Authors: Youzhi Zhang, Bo An, Venkatramanan Subrahmanian
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We compare our CRM4 shown in Algorithm 2, i.e., solving Program (13) based on our N, to the state-of-the-art algorithms: i) MIBP [34, 13]: the equivalent of solving Program (5) based on N; ii) EXCLUSION [4]: the first implemented algorithm guarantees to converge to an NE by using a tree-search based method by splitting the continuous probability space of the solution; and iii) ENUMPOLY [28]: an algorithm in the well-known game-solving package Gambit which tries to find all NEs by enumerating all the supports which could be the support of an NE and then searching for an equilibrium on that support. and Table 1: Part of experimental results (more results are in Tables 4 and 5 of Appendix H. |
| Researcher Affiliation | Academia | Youzhi Zhang Centre for Artificial Intelligence and Robotics Hong Kong Institute of Science & Innovation Chinese Academy of Sciences youzhi.zhang@cair-cas.org.hk Bo An School of Computer Science and Engineering Nanyang Technological University Singnapore boan@ntu.edu.sg V. S. Subrahmanian Department of Computer Science Northwestern University Evanston, USA vss@northwestern.edu |
| Pseudocode | Yes | Algorithm 1 Generate N, Algorithm 2 CRM, Algorithm 3 Generate N: full details of Algorithm 1, Algorithm 4 Build(N ) |
| Open Source Code | Yes | Codes are available at https://github.com/Youzhi333/optimal_NE. |
| Open Datasets | Yes | Following prior work for NEs [34, 4, 13], we evaluate our approach on two sets of games: randomly generated games (i.e., (n, m) with n players and m actions for each player) and six-player three-action games that are generated by GAMUT [31]. The citation [31] refers to 'Eugene Nudelman, Jennifer Wortman, Yoav Shoham, and Kevin Leyton-Brown. Run the GAMUT: A comprehensive approach to evaluating game-theoretic algorithms. In AAMAS, volume 4, pages 880 887, 2004.' |
| Dataset Splits | No | The paper does not provide explicit training/validation/test dataset splits in terms of percentages or sample counts. It describes generating 'randomly generated games' and using 'GAMUT' games, where experiments are run over '30 cases', which implies multiple independent game instances rather than a fixed dataset partitioned into splits. |
| Hardware Specification | Yes | Experiments are run on an eight-core Intel Core I9 machine at 2.3 GHz with 16GB of RAM. |
| Software Dependencies | Yes | We use the non-convex solver of Gurobi 9.5 to solve all mixed-integer bilinear programs with the optimality gap set to 0.0001 (the default setting). |
| Experiment Setup | Yes | The objective function used in the experiments maximizes the expected utility of player n. We use the non-convex solver of Gurobi 9.5 to solve all mixed-integer bilinear programs with the optimality gap set to 0.0001 (the default setting). Payoffs are generated from the interval between 0 and 100 (other ranges (e.g., [0, 1]) do not affect the result). |