Exclusion Method for Finding Nash Equilibrium in Multiplayer Games
Authors: Kimmo Berg, Tuomas Sandholm
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We tested the algorithms on randomly-generated games and on the games produced by the GAMUT generator (Nudelman et al. 2004). For random games, the payoffs were randomly drawn from a uniform distribution between zero and one. We ran rep = 1000 repetitions and set the stopping conditions as r(p) ϵ = 10 3 and maxtime = 900 (seconds); for the other experiments, we did not use any time limits. The results are presented in Table 1. The Dim column shows the dimension of the search space p , and Time gives the average run time. Over Time% shows the percentage of instances that hit the time limit, and Over Time ϵ gives the average errors for the repetitions that hit the time limit. The runs were conducted on Intel Core i7-6500U at 2.50 GHz with 16 GB of RAM under 64-bit Windows 7. We implemented the algorithms in Matlab R2015b. The results for GAMUT games are in Table 2; the results for all classes are available in the extended version. For these games, we used ϵ = 10 3, and no time limit. Not Solved% is the percentage of runs where ϵ > 10 3 for Algorithm 2. We can see big differences between the game classes. Polymatrix games are solved clearly slower than the other games. Note that our method solved all the instances to the given accuracy, while Algorithm 2 did not in some classes. The results show that the run times grow rapidly as the search space dimension increases. Our method has higher average run time, but it finds an ϵ-Nash (for given small ϵ) on all instances. In contrast, Algorithm 2 is faster on average but has problems on some instances and ϵ can be high. Our method seems to work better on hard instances, i.e., ϵ is smaller for those instances that take a long time to solve. In many games, especially GAMUT games, equilibria are in pure strategies or can be found with small k; thus it is reasonable that Algorithm 2 works well on those easy instances. The run time of our method can be made equally fast as Algorithm 2 s on those instances by first searching pure strategies and strategies in small support (but we did not want to design an algorithm that would take advantage of those properties that only hold for certain classes of games). We also compared against the algorithms available in the well-known game-solving software package GAMBIT. We tested the GAMBIT algorithms on the GAMUT games; see Table 3. The algorithms are the homotopy method of (Govindan and Wilson 2003) (gnm), its modification using iterated polymatrix approximation (Govindan and Wilson 2004) (ipa), the polynomial equation solver (enumpoly), the simplicial subdivision method (van der Laan, Talman, and van der Heyden 1987) (simpdiv), a function minimization approach (liap), and the quantal response method (Mc Kelvey and Palfrey 1995; Turocy 2005) (logit). |
| Researcher Affiliation | Academia | Kimmo Berg Aalto University School of Science Dept. of Mathematics and Systems Analysis kimmo.berg@aalto.fi Tuomas Sandholm Carnegie Mellon University Computer Science Department sandholm@cs.cmu.edu |
| Pseudocode | Yes | Algorithm 1 Initialize the regions and compute the rankings with g. Compute the constants M i , i N. Repeat until any stopping condition is met 1. Select the region with minimal value of g in Eq. (2). 2. Select p0. If it is outside the search space, goto 3. Else compute r(p0). If Eq. (4) is satisfied, exclude the region and return to 1. Else goto 3. 3. Bisect the region and compute g for the new regions with r(p0) and Mi(p0) in Eq. (3). (...) Algorithm 2 Initialize the value k and select constants c > 1 and k . Repeat until r(p) ϵ or k = k 1. Compute r(p) for all k-uniform strategies. 2. Update k = ck. |
| Open Source Code | No | The paper states: "We implemented the algorithms in Matlab R2015b." but does not provide a link or an explicit statement about the public availability of the source code for the methodology described. |
| Open Datasets | Yes | We tested the algorithms on randomly-generated games and on the games produced by the GAMUT generator (Nudelman et al. 2004). |
| Dataset Splits | No | The paper does not specify training, validation, or test dataset splits for the randomly-generated games or GAMUT games. It only mentions using these datasets for testing/evaluation. |
| Hardware Specification | Yes | The runs were conducted on Intel Core i7-6500U at 2.50 GHz with 16 GB of RAM under 64-bit Windows 7. |
| Software Dependencies | Yes | We implemented the algorithms in Matlab R2015b. |
| Experiment Setup | Yes | We ran rep = 1000 repetitions and set the stopping conditions as r(p) ϵ = 10 3 and maxtime = 900 (seconds); for the other experiments, we did not use any time limits. The results for GAMUT games are in Table 2; the results for all classes are available in the extended version. For these games, we used ϵ = 10 3, and no time limit. |