Solving Graph-based Public Goods Games with Tree Search and Imitation Learning
Authors: Victor-Alexandru Darvariu, Stephen Hailes, Mirco Musolesi
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our evaluation results show that this policy is able to reach 99.5% of the performance of the planning method while being three orders of magnitude faster to evaluate on the largest graphs tested. We show the main results obtained in Table 1, in which entries are aggregated across game sizes n {15, 25, 50, 75, 100} (for a version in which they are separated, consult Table 2 in the Appendix). Each reported value corresponds to the average objective function value of an equilibrium of the graph-based best-shot public goods game. Performance obtained during training on the held-out validation set of instances with n = 100 is shown in Figure 3. The performance on the test set is shown in Figure 4, in which the x-axes represent the number of players. |
| Researcher Affiliation | Academia | Victor-Alexandru Darvariu1,2, Stephen Hailes1, Mirco Musolesi1,2,3 1University College London 2The Alan Turing Institute 3University of Bologna {v.darvariu, s.hailes, m.musolesi}@cs.ucl.ac.uk |
| Pseudocode | Yes | A pseudocode description is given in Algorithm 1 in the Appendix. |
| Open Source Code | Yes | Our implementation is available at https://github.com/Victor-Darvariu/solving-graph-pgg. Please consult the Appendix for more details. |
| Open Datasets | Yes | To generate the underlying graphs G over which the game is played, we use the following synthetic models: Erd os Rényi (ER): A graph sampled uniformly out of all graphs with n nodes and m edges [18]. Barabási Albert (BA): A growth model where n nodes each attach preferentially to M existing nodes [4]. Watts Strogatz (WS): A model designed to capture the small-world property found in many social and biological networks, which generates networks with high clustering coefficient [51]. |
| Dataset Splits | Yes | For each size and each underlying graph model, we generate: 103 training instances Gtrain; 102 validation instances Geval used for hyperparameter optimization; and 102 test instances Gtest. |
| Hardware Specification | No | The paper does not provide specific hardware details such as GPU/CPU models, memory specifications, or cloud computing instance types used for experiments. |
| Software Dependencies | No | The paper mentions several software libraries like PyTorch [43], networkx [25], matplotlib [27], pandas [40], and seaborn [50], but does not provide specific version numbers for any of them. |
| Experiment Setup | Yes | For UCT, we use a random simulation policy and a number of node expansions per move nsims = 20n (larger values provide diminishing returns). ... we consider cp {0.05, 0.1, 0.25, 0.5, 1, 2.5}. ... For GIL, the learning rate η {10 2, 10 3, 10 4}, the number of S2V message passing rounds K {3, 4, 5, 6}, and the training strategy (separate, mixed, or curriculum) are optimized using a grid search. ... We train using the Adam [34] optimizer for 2 × 103 steps and use a batch size of 5 in all cases (larger batch sizes proved harmful). The dimension of the proto-action vector φ and the number of S2V latent variables are both 64. The temperature τ is initialized to 10. |