Abstract
Simulating large-scale spatial evolutionary games is computationally expensive, especially as the number of available strategies grows. This paper introduces Surrogate Bayesian Networks, a method that uses a small, parameterized network to approximate the dynamics of a much larger one. By using a novel "KL-search" algorithm to find the most informative samples for training, the authors achieve higher accuracy and better sample efficiency than state-of-the-art approximate inference techniques.
Introduction
In Evolutionary Game Theory (EGT), researchers model how populations of agents change their strategies over time based on interactions with their neighbors. When these interactions occur on a grid or network (spatial EGT), the system's complexity scales rapidly.
Previous work introduced Symmetric Dynamic Bayesian Network Approximation (SD-BNA) to track these dynamics without full-scale simulation. However, SD-BNA hits a "complexity wall": as more strategies are added or larger neighborhoods are considered for better accuracy, the "induced width" of the Bayesian Network explodes, making exact inference mathematically intractable. Standard approximate inference methods, like Abstraction Sampling, often require too many samples to be practical or fail to capture subtle inflection points in population shifts.
Methodology
The authors propose a "surrogate" approach: instead of performing inference on a massive 25-node network, they utilize a much smaller network. To compensate for the lost information, they introduce new parameters ($\theta$) to the small network that exploit the inherent symmetry of the spatial grid.
The core technical contributions include:
- Surrogate Parameterization: The authors add "dummy" nodes and edges to the small network to capture the influence of the wider neighborhood. Because the grid is symmetric, they employ parameter sharing, ensuring the same learned values apply across all neighboring nodes.
- KL-Search Algorithm: Rather than picking random samples to train the surrogate (Monte Carlo), the method uses a best-first search on an OR-search tree. This search is guided by a heuristic that specifically looks for configurations where the surrogate model and the large model disagree most (maximizing KL-divergence).
- Fast KL-Search: For games with many strategies, they introduce a version that uses a stochastic estimate of the partition function, allowing the method to scale to complex games like 6-strategy variants of Rock-Paper-Scissors.
Experimental Evaluation
The paper evaluates the method using several classic evolutionary game models as benchmarks, including the Prisoner’s Dilemma (pd), Snowdrift (sd), Battle of the Sexes (bos), and Rock-Paper-Scissors (rps). These are dynamic environments where the "ground truth" is established via expensive, long-running simulations.
Key Results
- Superior Accuracy: In the Deadlock game, the KL-search approach achieved significantly lower KL-divergence (error) compared to both exact inference on small networks and Abstraction Sampling on large ones.
- Sample Efficiency: KL-search with only 100 samples consistently outperformed Abstraction Sampling and Forward Sampling even when those methods were given 400 samples.
- Speed and Scalability: For a 2-strategy game, KL-search was roughly 8x faster per sample than Abstraction Sampling. Furthermore, Fast KL-Search was the only method tested that could successfully run on games with more than 3 strategies (like the 6-strategy RPS), where memory requirements for other methods became prohibitive.
Conclusion
The "surrogate" approach effectively reframes the problem of predicting population evolution as a parameter optimization problem. While the current implementation assumes a square lattice, the authors suggest it could be adapted to other structures like hexagonal or random graphs. This methodology represents a promising avenue for modeling other spatial Markov processes, such as voter models or disease spread (SIS models), in computational social science.
Summary updated