Practical exact algorithm for trembling-hand equilibrium refinements in games
Authors: Gabriele Farina, Nicola Gatti, Tuomas Sandholm
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We apply it to finding a QPE and an EFPE in many different card games: Kuhn poker, Leduc poker with various numbers of ranks, and two versions of Goofspiel [Ross, 1971] with various numbers of ranks. Our algorithm dramatically outperforms the prior algorithms in the literature. It is able to solve games up to four orders of magnitude larger than those previously solvable. |
| Researcher Affiliation | Academia | Gabriele Farina Computer Science Department Carnegie Mellon University gfarina@cs.cmu.edu Nicola Gatti DEIB Politecnico di Milano nicola.gatti@polimi.it Tuomas Sandholm Computer Science Department Carnegie Mellon University sandholm@cs.cmu.edu |
| Pseudocode | No | The paper describes algorithms verbally and through mathematical formulations (Figure 1), but does not include any explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statements about releasing code, nor does it include links to a code repository. |
| Open Datasets | No | The paper refers to 'Kuhn poker, Leduc poker with various numbers of ranks, and two versions of Goofspiel' as 'game instances' and states they are 'fairly standard in the computational game theory literature' with a detailed description in Appendix B. However, it does not explicitly refer to them as 'datasets' or provide specific access information (e.g., URL, DOI) for downloading them as data files. |
| Dataset Splits | No | The paper does not provide specific details on training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not describe any specific hardware used for running the experiments (e.g., CPU, GPU models, memory). |
| Software Dependencies | Yes | The LP oracle we use is GLPK 4.63 [GLPK, 2017]. |
| Experiment Setup | Yes | When ϵ 1/500 we use the finite-precision simplex algorithm provided by GLPK, while for ϵ < 1/500 we use the arbitrary-precision variant, as, from our observations, when ϵ < 1/500 the finite-precision solver is doomed to eventually fail due to numerical instability. [...] The second iteration is performed with ϵ = 1/10, and ϵ is halved between subsequent consecutive iteration. |