Solving Graph-based Public Good Games with Tree Search and Imitation
  Learning
  Public goods games represent insightful settings for studying incentives for
individual agents to make contributions that, while costly for each of them,
benefit the wider society. In this work, we adopt the perspective of a central
planner with a global view of a network of self-interested agents and the goal
of maximizing some desired property in the context of a best-shot public goods
game. Existing algorithms for this known NP-complete problem find solutions
that are sub-optimal and cannot optimize for criteria other than social
welfare.
  In order to efficiently solve public goods games, our proposed method
directly exploits the correspondence between equilibria and the Maximal
Independent Set (mIS) structural property of graphs. In particular, we define a
Markov Decision Process which incrementally generates an mIS, and adopt a
planning method to search for equilibria, outperforming existing methods.
Furthermore, we devise a graph imitation learning technique that uses
demonstrations of the search to obtain a graph neural network parametrized
policy which quickly generalizes to unseen game instances. 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. The methods presented in this work can be applied to a
large class of public goods games of potentially high societal impact and more
broadly to other graph combinatorial optimization problems.
