Solving Graph-based Public Good Games with Tree Search and Imitation Learning

Victor-Alexandru Darvariu, Stephen Hailes, Mirco Musolesi

Abstract

Finding optimal equilibria in graph-based Public Goods Games (PGG) is a critical challenge for policy-making, yet it remains an NP-complete problem. This paper presents a novel framework that combines Monte Carlo Tree Search (MCTS) with Graph Imitation Learning (GIL) to identify high-quality solutions efficiently. By establishing a mathematical correspondence between game equilibria and Maximal Independent Sets (mIS), we frame the problem as a Markov Decision Process. Our approach uses MCTS to generate expert demonstrations, which then train a Graph Neural Network (GNN) to predict optimal moves on unseen networks. Experimental results show that the learned policy maintains 99.5% of the performance of the MCTS planner while achieving a 1,000x speedup, enabling real-time optimization of social welfare and fairness in large-scale social networks.

Introduction: The Complexity of Public Goods

In a Public Goods Game (PGG), individuals decide whether to invest in a costly resource—such as a vaccination or a clean energy project—that benefits their entire neighborhood. The "best-shot" variant is particularly significant: an individual benefits as long as at least one person in their immediate social circle provides the good.

Illustration of the best-shot public goods game progression on a graph.

While these games naturally reach a Nash Equilibrium, multiple such states often exist. A central planner typically aims to find the specific equilibrium that maximizes social welfare or ensures fairness. However, finding these optimal configurations is computationally prohibitive as networks grow. Traditional algorithms often struggle with sub-optimal solutions or lack the flexibility to optimize for diverse metrics like the Gini coefficient.

Methodology: From Planning to Imitation

The proposed framework addresses this complexity through a two-stage pipeline that bridges game theory and combinatorial optimization.

1. The Planning Stage (MCTS)

The researchers proved a bidirectional correspondence between the game's equilibria and the graph-theoretic property of Maximal Independent Sets (mIS). By framing mIS construction as a Markov Decision Process (MDP), they utilize Monte Carlo Tree Search (MCTS) to explore the state space. MCTS "looks ahead" to identify which nodes should invest to maximize specific policy objectives, providing high-quality expert trajectories.

2. The Learning Stage (Graph Imitation Learning)

To overcome the high computational cost of MCTS during inference, the successful search paths are used as training data for a Graph Neural Network (GNN). Using a technique termed Graph Imitation Learning (GIL) and the structure2vec architecture, the model learns a policy $\hat{\pi}$ that captures the underlying structural logic of optimal node selection. This allows the model to generalize to entirely new, unseen graph instances without further tree search.

Overview of the MCTS-GIL pipeline: (a) demonstration collection, (b) policy training, and (c) inference on unseen instances.

Experimental Setup and Key Results

The framework was evaluated on three standard synthetic graph models: Erdős–Rényi (random), Barabási–Albert (scale-free), and Watts–Strogatz (small-world). The study tested networks ranging from 15 to 100 players with both identical and heterogeneous investment costs.

  • Near-Optimal Efficiency: The GIL policy achieved 99.5% of the performance of the original MCTS planner.
  • Massive Computational Speedup: On large-scale graphs, the learned policy was three orders of magnitude (1,000x) faster than MCTS.
  • Robust Generalization: The framework consistently outperformed traditional baselines like Best-Response dynamics and Simulated Annealing, particularly in complex scenarios with heterogeneous costs.
  • Multi-Objective Optimization: Beyond social welfare, the framework successfully optimized for fairness metrics, demonstrating its versatility for diverse societal goals.

Conclusion and Future Directions

This research demonstrates that combining tree search with imitation learning can effectively solve complex economic dilemmas on networks. By distilling expensive search processes into a GNN, the method provides a scalable tool for central planners. Future work may address the limitations of centralized assumptions by exploring decentralized models where agents have only local information, or extending the framework to dynamic networks where social links evolve over time.

Summary updated

BibTeX
@misc{darvariu2021solving,
  author = {Victor-Alexandru Darvariu and Stephen Hailes and Mirco Musolesi},
  title = {{Solving Graph-based Public Good Games with Tree Search and Imitation Learning}},
  year = {2021},
  eprint = {2106.06762},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.06762},
}
Figure