Solving Graph-based Public Goods Games with Tree Search and Imitation Learning
Authors: Victor-Alexandru Darvariu
Stephen Hailes
Mirco Musolesi
Venue: NeurIPS 2021 Poster (2021)
Keywords: public goods games
network games
multi-agent systems
maximal independent sets
tree search

Abstract: 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.

Solving Graph-based Public Good Games with Tree Search and Imitation Learning
Vietor-Alexandru Darvariu 1:2 Stephen Hailes', Mirco Musolesi! 1223
University College London "The Alan Turing Institute University of Bologna {v. daraarari,, s s.hailes, m. m.musoessi@cs. ceceeossscccll..c.coooooooecccec www.uc.......oooooo.... ac.ak. .uk
Abstract
Public goods games represent insightful settings for studying incentives for indi- vidual 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 global view of 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 Markov Decision Process which incrementally generates an mIS, and adopt planning method search for equilibria, outperforming existing methods. Furthermore, we devise a graph imitation learning technique that uses demonstrations of the search to obtain graph neural network parametrized policy which quickly generalizes to unseen game instances. Our evaluation results show that this policy is able to reach 59.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 large class of public goods games of potentially high societal impact and more broadly to other graph combinatorial optimization problems.
Introduction
In public goods game (PGG), individuals choose invest in expensive good (paying cost), with benefits being shared by wider society (37). It is form of n-party social dilemma that has been used study the tension between decisions that benefit the individual and the common good [36]. Aspects characteristic to public goods are observed many important societal problems such as meeting climate change targets [32 41 the dynamics of research and innovation (2]] the design of effective vaccination programs 19 and, more generally, situations in which contributions are
non-excludable. The analysis of this class of games related to ongoing efforts study cooperation in multi-agent systems as means of driving progress on societal challenges [3]
The best-shot PGG is variant in which investment decisions are binary and agents benefit if either they or a neighbor own the good [26]. Since patterns of connections along social and geographical dimensions in networks to limit the impact of contributions to an agent's ' neighbors. Graph- based best-shot public goods games exhibit multiple pure-strategy Nash equilibria (PSNE) (16). Given this multiplicity, natural question that arises is how to compute equilibria that satisfy some properties, a task known to be NP-complete in general for multiplayer games 22 12]. Examples of desirable equilibria those that maximize the social welfare (total utility) of agents or those with a high degree of fairness in terms of contributions. For graph-based best-shot PGGs, it has been shown that each equilibrium
known to shape individual deccision-makin 9 223, natural restriction
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

t t= 0
(a(s)
h
π
Collection demonstrations by Monte Carlo Tree Search policy π
b) Training of GNN- CNNN-parametrized policy by imitation learning
Use of quickly predict unseen game instances
Figure 1: Schematic of our approach for finding desirable equilibria in the graph-based best-shot
game. (a) We exploit the correspondence between agents acquiring the public good in equilibria (pictured in dark blue above) and the Maximal Independent Set (mIS) structural property of graphs. We define MDP that incrementally grows independent
until it is maximal, and use Monte Carlo Tree Search (MCTS) to plan in this MDP in order to find desirable equilibrium configurations of the game. (b) We propose a Graph Imitation Learning method which uses demonstrations of the MCTS policy π to learn a policy क parametrized by a graph neural network. (c) We use î to find optimal equilibrium configurations on unseen instances of the game.
corresponds to a Maximal Independent Set (mIS) 9 : set of vertices of maximal size in which no two nodes are adjacent. Since enumerating mISs to identify desirable equilibria quickly becomes unfeasible for non-trivially sized graphs, practical alternatives
needed for larger graphs.
Towards this goal, Dall' Asta et al. [16] proposed a centralized algorithm based on best-response dynamics that converges to the optimal equilibrium (w.r.. social welfare) in the limit of infinite time, and suggested a simulated annealing alternative. Levit et al. [38] proved that the general version of the best-shot PGG is potential game and derived algorithm for finding equilibria based side payments, which are used by agents that are unhappy with their outcome to convince neighbors to switch. While superior results between the equilibria found by this approach and optimal equilibria as found by exhaustive search on small graphs. Furthermore, current methods cannot optimize for criteria other than social welfare.
obtained over best-response dynamics, there is still wide gap
Contributions. Our contributions can be summarized as follows:
1. We propose to directly take advantage of the connection between equilibria in this class of games and Maximal Independent Sets. This relationship allows us define an MDP which incrementally generates mIS to optimize a desired property: thus, every configuration found is, by construction, an equilibrium of the game We adopt a variant of the Monte Carlo Tree Search algorithm for planning in this MDP. On small graphs, where exhaustive enumeration of equilibria can be performed, the best outcomes found by this method are matched in most settings. On larger graphs existing methods are outperformed, especially in cases where the costs for acquiring the public good differ among players.
2. We devise a way to learn the structure of the solutions found by the planning algorithm based on imitation learning, such that predictions can be obtained on unseen game instances without repeating the search process. Specifically, we use a dataset demonstrations of the search in order to learn graph neural network parametrized policy through imitation learning, a procedure we call Graph Imitation Learning. The resulting policy is able to achieve 99.5% of the performance of the search method while being approximately three orders of magnitude quicker to evaluate and even exceeding the performance of the original search in some cases. This method is applicable beyond this class of networked public goods games, i.e., to a variety of graph- maphhbbaedd decision-making problems where a model of the MDP is available and the goal is to maximize graph-level objective function.
We highlight the difference between Maximal Independent Set and Maximum Independent Set. Maximal IS (mIS) is an IS that is not a proper subset of another IS. A Maximun IS (MIS) is an mIS of the largest possible size. In PGGs, MIS may not be desirable equilibrium, since it involves many players expending the cost.

---

2 Background and Related Work
Network Games and Public Goods Games. The literature on network (i.e., graph-based) games focuses on several fundamental questions regarding the behavior of agents that are connected by a network structure (28): examples include proving the existence of and characterizing profiles of behavior in equilibria, reasoning in the presence of partial or probabilistic information [20], and examining the effect of new links in the graph [9]. Graphical games [30] represent a class of games on graphs in which actions are binary and utilities are defined in terms of neighbors in the graph structure. The networked PGG is a graphical game in which agent utilities are a function of aggregated neighbors' efforts, with the best-shof version being sub-category in which utilities a maximum of neighhor quantities. Recent works in this area treat the properties of binary PGGs (52) as well as designing strategies for inducing equilibria in such games by manipulating the graph structure itself [31].
Computing Equilibria. The problem of computing equilibria in non-cooperative games is well- studied. A large spectrum of techniques exist for 2-player and n-player games that find sample equilibrium enumerate all equilibria, with the task being computationally challenging or intractable in many cases [39, [1].. In graphical games, more efficient algorithms can be derived for restricted cases such as complete graphs or trees 330 (22. For best-shot PGGs, best-response dynamics have been proven to converge to a PSNE 38 and as previously described several methods have been proposed for finding PSNES T6
38 that improve on standard best-response.
Monte Carlo Tree Search. For MDPs in which a model is available, lookahead can be used in order to select (plan) near-optimal actions. The Monte Carlo Tree Search (MCTS) family of algorithms uses returns estimated from sampled runs in order to make such decisions, with the UCT algorithm [35] formulating the decision at each node as multi-armed bandit problem. UCT has been used to great success as a framework for challenging two-player zero-sum games such as Go [46]. Demonstrations of UCT have been used in order to train deep neural networks that mimic its policies while being much cheaper to evaluate [24]. Function approximators trained with this mechanism can be leveraged to bias the tree search, yielding an iterative procedure where both search and neural network improve 3 47 In the context of a different graph problem (namely, Knowledge Base Completion), M-Walk 45] also formulates the task deterministic MDP and uses MCTS in conjunction with neural network parametrized policy.
Learning and Search in Combinatorial Optimization. In combinatorial optimization, the goal is to select an optimal solution among a large set of possible options. Graph-based combinatorial optimization problems such as the Traveling Salesperson Problem are well-studied, and due to their intractability (21) typically make use of approximate search or heuristics. Similarities among instances of such problems make them an attractive target for machine learning approaches (8), with this area of work gaining momentum in recent years 449 6, 42). Notably, Khalil et al. [33] proposed framework for the discovery of combinatorial optimization heuristics using the DQN algorithm together with representations based on the structure2vec (S2V) graph neural network [14. Various improvements this scheme have been proposed, for example by allowing the agents to reverse
decisions at runtime [5] or constructing several parts of the solution in parallel [2]. Alternatively,
sample efficiency and generalization performance can be improved in some cases by combining graph neural network with MCTS I.
3 Notation and Problem Statement
Game Definition. A networked, best-shot public goods game takes place over an undirected,
unweighted graph G == (N, E) with no self-loops. Each vertex in N = {NV, .N..... NN.) represents a player, while edges E' capture the interactions between agents in the game. Each player chooses an action a; E A,, where A, {0, 1} denotes the action space of player We let action 1 denote investment in the public good by the agent and 0 denote ion-investment. An action profile (a1..... ar)) captures the choices of all players. The set = A₁ x A2.-. A, denotes the set of all possible action profiles. We use a to refer to actions of all other players except i, and ((a) to denote the set of all players that play action in action profile a. Investment in the public good carries a cost G; E (0, 1) for each player i. We use the terms identicul cost (IC) to refer to the setting in which costs are the same for all players, and heterogeneous cost (HC) to refer to that in which costs are different between players. We let (cI....,,C) Cn).
3

---

We also define, for each player i. neighborhood N₁, which contains i and all adjacent players, i.c., N (N, E (i,j) E}. The utility u, for player under an action profile is defined as:
- ca if
(a(a)
1, if = 0 3j EjEN, 03 = if, = 0 A Vj E NG az= a
We are interested Pure Strategy Nash Equilibrium (PSNE) solutions, since there are no mixed strategy equilibria in this game [9] A pure strategy is complete, deterministic description of how player will play the game, An action profile a PSNE if all players would not gain higher utility by changing their action choice, given the actions of the other players. Formally, a E A is a PSNE if and only if ua a-:) 2 u,(a,, Vi N, o; A. The tuple (G, u, c) defines an instance of this game. We let the set denote all Pure Strategy Nash Equilibria of a game instance.
Problem Statement. We formulate our problem as follows: given game instance (G,A,u, and an objective function f: > [0, 1], the goal is to find the PSNE for which f is maximized; concretely, finding a that satisfies argmaXace f(a).
What constitutes a desirable equilibrium in this game? From a utilitarian perspective, desirable equilibrium is one that muximizes the social welfare of agents. We define the SW(a (a) objective as below, normalizing by the number of players |N] so that games of different sizes are comparable:
SW SW(a) = EieN (;(a)
[N]
further desirable characteristic is fairness, or equality between players' utilities. We define the fairness objective F(a) as the complement of the Gini coefficient, measure of inequality:
F(a) 11 EIEN ΣjEN (u((a) u, (a) 2n LjeN Uy(N)
Maximal Independent Sets. subset of vertices / S N is an Independent Set (IS) of the graph G = (N, E)) if none of the vertices in the set are adjacent to each other. Formally, Vi,j E I s.t. of j (1. &
Maximal Independent Set (mIS) is an independent set that is not proper subset of any other independent set. Bramoullé and Kranton between the set of players playing in equilibria of the networked best-shot PGG and mlSs. Thus, one way of finding desirable equilibria that is faster than considering all 2" action profiles could be to enumerate all mISs. However, the best known family of algorithms 10 for this task has worst-case running time (33/33), which makes even this approach impractical beyond very small graphs.
9 have proven a bidirectional correspondence
Proposed Method
The proposed approach, in contrast with previous methods, directly exploits the relationship between equilibria of this game and the Maximal Independent Set property. We assume that a central planner, with global view of the graph, seeks to find optimal outcomes of this game. To this end, formulate the construction of a mIS as a Markov Decision Process (MDP), in which an agent incrementally builds an IS, receiving reward signal based on the objective f once the IS is maximal. To plan in this MDP, we use the UCT algorithm. We also describe an imitation learning procedure based on behavioral cloning mimicking the moves of the search. This policy can be evaluated rapidly on new instances of the game without performing a new search. Our method is illustrated in Figure and detailed below.
44 that be used to learn generalizable model of equilibrium structure by
4.1 MDP Definition
The MDP we propose defined below and illustrated in Figure
State S. A state St is tuple (G, 4)) formed of the graph and independent set 4, with Io 2.

---

Actions A. An action corresponds to the selection of a node that is not currently in the independent set. Given a state (G, It), we define available actions as A, = Usez, Ni, i.e., nodes currently in the independent set and all their neighbors are excluded.
Transitions P. Transitions dition of a node to the independent set. Concretely, given that the agent selects node a at time
deterministic and correspond the ad-
the next state is defined as 4r), where
0
4 4--1 U {a}.
Rewards R. Rewards depend the objective function f considered (concretely, SW or F), and are provided once an mIS is constructed, with all other intermediate rewards being 0.
1
Terminal. Episodes proceed until the agent has constructed an miS and thus no valid actions remain.
2
4.2 Collection of Demonstrations by Monte Carlo Tree Search
agent that acquires public good neighbor access it
Since the MDP formulation above fully deseribes the transition and re- ward functions of this MDP, we may use model-basee planning algorithms in order plan mIS that maximizes the desired objective. Concretely, we opt for the UCT (35] variant of the Monte Carlo Tree Search algo-
Figure 2: Illustration of
the proposed MDP.
rithm, which has proven to be effective framework in wide variety of decision-man making problems. The UCT algorithm selects the child node corresponding to action a that maximizes
R(s,u) + 2001 UCT(s,a) = C(s,a)
21n C(s) C(s.a)
where R(s, a) is the sum of returns observed when taking action a in state s, C(s) is the visit count for the parent node, C(s, a) is the number of child visits, and e, is constant that controls the level of exploration (35). We use the UCT policy π to collect demonstrations using set of training game instances train each of which contains n players. This process illustrated in Figure [p. We let D, denote this dataset of demonstrations. Each demonstration is effectively a datapoint and is composed of tuple (S,, A(S,), n, v), where:
S. represents the state from which the move is executed (i.e., for the mIS problem, the underlying graph G and the current independent set I,);
A(S;) represents the valid actions available at the state (i.e., it contains nodes that are not currently in 1 or are a neighbor of any node in I,);
represents the size of the underlying graph (i.e., the number of nodes players);
v is a vector of size (A(S)),, where each entry equal to C'S,,, a), for each valid action a. This represents the number of visits of the search policy from the root state S, to each of the possible actions a. Given that C(S.) = EaEs, C(S:, a), the empirical policy is then .(S..))
estimated T (a) S.) C(S.)
4.3 Graph Imitation Learning
Policy Parametrization. The main disadvantage in using planning algorithms is that predictions are expensive to obtain for new game instances. To mitigate this, we explore the possibility of learning a policy à parametrized by graph neural network (GNN). Specifically, we use the structure2vec GNN [4]. which produces for each vertex N₂ E N an embedding vector μ.N. that captures the structure of the graph as well as interactions between neighbors. This is achieved in several rounds of combining the features of node with an aggregation of its neighbors' features, to which an activation function is applied. Prior this aggregation, node and neighbor features are multiplied by of parameters g(1), Embeddings for a state St can be obtained by summing node embeddings: ((.)) Σn, JN. We use node features xN, corresponding to a one-hot encoding that captures whether the node is in the independent set, i.e., XN; = [1, 0JT N I and xN; [0, 1]" otherwise.
important challenge in this setting the fact that at any timestep significant number of actions not available. Thus, the default choice of having the output layer consist of a softmax layer with
5

---

one unit per vertex in N is potentially wasteful. In addition, such an architecture is sensitive to node relabeling and not transferable other graphs. We thus consider a different approach: we make the final layer the policy network oulput a proto-action ((Si) (e2) (0()) ((())) Then, in order to obtain probabilities, we measure the Euclidean distances d(a,, Φe) between the proto-action and the embeddings of all available actions, normalized using a softmax with temperature This allows us to compute probabilities for all possible actions in single forward pass. Formally:
e (ls))))(SS)//)/))) # *A.(S.) ElEA(S.) exp(d(pa: ((S))/T)
(1)
Loss Term. For training the policy network, we minimize the KL divergence between the distribution of the policy network and the empirical distribution formed by the number of child visits [3, i.e.,
C(s,a) log(f(als))
L =
Σ GEA(s)
(2)
C(s)
Training Strategies. We consider several training strategies for obtaining a model for a target size of game instances (i.e., games in which there are players). Since the structure of equilibria for increasingly large number of players are potentially more complex (i.e., we have to deal with larger graphs), also consider whether training additionally smaller graphs (thus simpler examples) brings a generalization benefit. We employ curriculum learning, a methodology successful a variety of machine learning settings (5)., and compare against training only the target size as well as mixing the examples of different sizes instead of constructing a curriculum. Concretely, we consider the following training strategies, noting that validation is performed on the target size n:
separate: train only on examples from Dn
mixed: train on examples from Um Dm
curriculum: carry out the training in several epochs, each epoch considering only examples from Dm. with each value m S n considered in ascending order.
We learn the parameters = 12 as well as the softmax temperature T in an end-to-end fashion. greedy action selection. Our method, which we refer as
When evaluating this policy, GIL (Graph Imitation Learning), is illustrated in Figure Tb. A pseudocode description is given in Algorithm in the Appendix.
Experiments
5.1 Evaluation Procedure
Game Instances. To evaluate our approach and all baselines, we create instances of network games over graphs with number of players (15, 25, 50, 75, 100). For each size and each underlying graph model, generate: 10 training instances Grain, 10 validation instances Geval used for hyperparameter optimization; and 102 test instances Glest To set costs c, in the IC case we fix 1/2, Vi, while for HC consider costs uniformly sampled in (0, 1). To generate the underlying graphs G over which the game is played, we use the following synthetic models:
Erdös- Rényi (ER): graph sampled uniformly out of all graphs with n nodes and m 20
edges [18]. We use m
Na(N-1) which represents 20% of all possible edges.
100
Barabási-Albert (BA): A growth model where n nodes each attach preferentially to M existing nodes We use M 2.
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 coeffi- cient [5 Starting with a regular ring lattice with vertices with & edges each, edges are rewired to random node with probability We use k = 2 and 0.1.
Baselines. We compare to the following basclines that have been proposed in prior work:

---

Table 1: Mean rewards obtained by the methods split by cost setting, graph model, and objective.
Random
TH TLC
BR
SA
UCT
GILL (ours)
G
f
HC
BA
F
0.745 oos
0.802
0.774
0.742
0.791
0.815 000
0.837 000
0.834 001
SW
0.697.10 oor
0.779
0.727
0.69120-005
0.76010.019
0.795
0.815
0.81310.000
ER
F
0.877 t.0001
0.896
0.920
0.877 -0.7000000
0.91 =911=00002
0.908=0.001
0,945+0.000
0.940=o.00x
SW
0.868 0ot
0.890
0.912
0.867 00000
0.903=o.0m
0.903 0010
0.940 000
0.935 001
WS
F
0.803
0.806
0.865
0.804
0.821 1. 003
0.832
0.892.0
0.89220
SW
0.78 0.0000
0.785
0,846
0.782
0.80 0.800
0.817
0,876
0.876
IC
BA
F
0.833 000
0.844
0.834=0.000
0.84==0.000
0.849=0,00m 0,0000
0. 0.847=00.m 000
0.847 000000
SW
0.697..0 007
0.779
0.691
0.757
0.794.o
0.795
0,795
BR
F
0.893 0oo
0,906
0.89220.000
0.907
0.91620.000
0.922 1922..0..0k 000
0.91920.002
SW
0.867 +-0 +00000
0.889
0.866=0.001
0.889=0.002
0,903=0.000
0.910=0.000
0.908
WS
F
0.842 00!
0.843
0.842 001
0.847=0.00
0.856 0000
0.862
0.864
SW
0.777..0.00
0000
0.782
0.779_..003
0.79120.004
0.813.0.001
0.824 0.000
0.828 20.000
Exhaustive Search (ES): Select the PSNE that maximizes the objective out of 2 possible action profiles. Only applicable on very small graphs due to its computational complexity.
Best Response (BR): In the graph-based best-shot PGG, Best Response converges to a PSNE (38) We start from randomly selected action profile, allow the agents to iteratively play Best Response, and measure f once a PSNE is reached.
Payoff Transfer (PT): The method of Levit al. 38 modifies the definition of utilities in this game to include an additional term that represents payoff. The distributed procedure they propose enables agents to convince their neighhors to switch their action by providing a payoff. As with BR, we start from a randomly selected action profile, and measure f once a PSNE is reached. Even though the PSNEs reached do not necessarily correspond to mlSs, we evaluate the objective functions by considering the utilities of the players.
Simulated Annealing (SA): The method proposed by Dall' Asta et al. [66 works by randomly selecting an agent playing O, incentivizing them to switch their action 1, then iterating on the BR rule. The new PSNE reached is either accepted or rejected based on a simulated annealing rule with certain temperature parameter e. In the limit of infinite time, this method converges to the optimal Nash equilibrium in terms of social welfare in the IC case.
We also consider the additional baselines listed below, which exploit the mIS connection. We note that TH and TLC have not been considered in prior work but are potentially effective heuristics.
Random: Incrementally construct an mIS by randomly picking, at each step, a node that is not in the IS and is not adjacent to any nodes in the IS.
Target Hubs (TH): Pick the highest-degree node available that is not yet included in the IS. While this strategy is not guaranteed to find global maximum, placing the public good on nodes with many connections means that many others can access it.
Target Lowest Cost (TLC): Place the public good on nodes for which the cost c is lowest (only applicable in HC case). This may result in equilibria with high social welfare and fairness since the good is acquired only by those players for which it is cheap to do so.
Training and Evaluation Protocol. Evaluation (and training, where applicable) performed separately for each n. graph model, objective f. and cost setting (IC or HC). To compute means and confidence intervals, we repeat the evaluation (and training) across 10 different random seeds.
Hyperparameters. We optimize hyperparameters for UCT, GIL, and the SA methods; the other methods are hyperparameter- free. For UCT, we use random simulation policy and a number of node expansions per move Ngims = 20n (larger values provide diminishing returns). At each step, once simulations are completed, we select the child node with the largest number of visits as the action (ROBUSTCHILD) We treat cp as hyperparameter to be optimized, and for each problem instance we consider e, E {0.05, 0.1, 0.25, 0.5, 1,2.5.. Since the ranges of the rewards may vary in different settings, we further standardize Cp by multiplying with the average reward R(s) observed at the root in the previous timestep- ensuring consistent levels of exploration. For GIL,, the learning rate 77 E {10-2 10-3 10-1), the number of S2V message passing rounds K (3, 4, 5, 6). and the
7

---

KC, P
RC. SW
HC.. P
HCC, SW
Bazaleai Albort
0.825
0.50
0.775
0.8400
0.800
0.8335
0.775
0.75
0.9030
0.735
0.750
0.700
1000
2000
Giee nemn cegurd
0.95
EreSs Réggi
0.35
0.365
0.94
0.991
0.94
0.93
0.96
1000
2000
0
1000
2000
0
1000
2000
1000
2000
0h mets seaued
03.96
0.82
0.85
Watts
0.85
0.80
0.85
0.78
0.80
0.76
0.75
1000
2000
1000
2000
0
1000
2006
1000
2000
batch number
batch mumber
batch numbee
batch zumber
Figure 3: Training curves for GIL, showing performance on the held-out validation set.
Raxl
TH
TLC
88
BR
PT
8h
DCT
CIL (oxz)))
IC,
IC, SW
HC,
HC,
Q soom cowred
0.80
0.85
0.85
0.80
Barshtei
0.75
0.75
0.84
0.70
0.83
15:25
60
75
100
15 25
50
75
100
16 25
50
75
100
1. 85
50
75
100
1001: reerrd
0.06
0.95
Erdia Démyi
0.955
0.9
0.55
0.85
0.85
0.50
0.8
15.25
50
75
100
15.25
50
75
100
751
775
100
35
20
75
100
0.90
Stezts-troogzz
pesn povernl
0.90
0.86
0.62
0.85
0.85
0.50
0.85
0.80
0.78
0.81
0.80
100
75
100
775
number of playens 12
mumber o8 pleyerts 12
munder of players T
somnber players 7
Figure 4: Mean rewards obtained by the methods function of the number of players
training strategy (separate, mixed, or curriculum) are optimized using grid search. For SA, consider e E [10' 102, 103, 104), stop the optimization after 10a steps without an improvement, and use cut-off of 107 steps. Further details are provided in the Appendix.
GIL Training. GIL is the only method that requires training. The datasets on which this method is trained correspond to demonstrations of the hyperparaaeeteroppiiiiee UCT. We carry out the imitation learning procedure as described in Section 4.3 and evaluate performance on the validation instances every 50 steps. We train using the Adam [34] optimizer for 2 x 103 steps and use batch size in all cases (larger batch sizes proved harmful). The dimension of the proto-action vector ő and the number of S2V latent variables both 64. The temperatrre is initialized 10.
Implementation. Our implementation available at pitttts:: htapp::///ite httggttuu.cco//aaee. com catihbbbcoooiiittooraaaaalll solving graph-pgg Please consult the Appendix for more details.

---

eepondee
mbbo
curricllo
IC, F
IC, SW
HC, P
HC, SW
Becybeai Albert
pe0g sontad
0.8
007
0.7
76
100
25
25
25
Drlbe Böngi moon reward
0.9
15
25
50
75
100
15
25
50
75
100
15
25
50
75
100
15
25
50
75
100
Warts- Stropatt
G quemn m roward
0.9
0.8
100
16 95
100
25
25 cammber of playens in
number of playens v
mumber of playorrs T2
mmmber of players 7
Figure 5: Mean rewards obtained on the validation set by GIL using different training procedures. The choice of an appropriate procedure depends on the underlying graph structure. We observe that it is more important in the HC case and it increases in importance with graph size.
5.2 Evaluation Results
We show the main results obtained in Table L in which entries are aggregated across game sizes E (15, 25, 50, 75, 100} (for a version in which they are separated, consult Table 2 the Appendix). ). Each reported value corresponds to the average objec- tive function value of an equilibrium of the graph-based best-shot public goods game. Performance obtained during training the held-out validation set of instances with n = 100 is shown in Figure B] The performance in which the r-axes represent the number of players. We also
Baoi
TH
BR
ECT
T1C
PT
Gill. (cam)
Episode duration (ms)
10
109
the test set is shown in Figure 4
101
show a comparison of the runtime per episode in milliseconds
used by the different methods in Figure 6) In the figures, the stars at 15 represent exhaustive search.
15
25
50
75
100
number of players n
We find that the UCT planning method outperforms previous methods in all cases except the IC, F case in which the SA baseline does better as game size increases. For the smallest graphs, UCT nearly performs on par with exhaustive search. The Random and BR baselines consistently perform the poorest, as expected. The gap between the methods enabled by approach (UCT and GIL) are higher in the HC settings where costs for acquiring the public good differ between players.
Figure 6: Mean milliseconds needed to complete episode (i.e., construct an mlS) as a func- tion of the number of players.
Imitation Learned Policy. We find that the performance of the imitation learned policy GIL is very close to that of the planning method (at least 99.5%). even clearly exceeding it in certain cases (in the IC setting for Watts-Strogatz graphs and both objectives). Given the timings in Figure 6 this closeness in performance is even more remarkable since the imitation learned policy is approximately three orders of magnitude cheaper to evaluate than the planning method on the largest graphs tested.
Impact of Training Strategies. Additionally, we also explore the impact of the training strategies used for the imitation learning phase in Figure 5 Since the choice of which examples to present to the model as well as their order could have an impact on the performance of the imitation-learnnn trained policy and there is no priori knowledge of which strategy is optimal, we treat the training strategy as a tunable hyperparameter. We find that no training strategy is better across the board; rather, their rankings are consistent depending on the graph model on which the method is trained. For BA graphs, the mixed strategy performs best; in the case of ER graphs the currieulum strategy achieves the highest reward; for WS the differences between the averages are very small. Additionally,

---

for BA and ER graphs, the relative differences between the methods are higher in the HC setting than in IC. In all cases, the difference mean reward for the different training strategies insignificant on small graphs, and increases in importance the larger the size.
Discussion
Limitations. Since the proposed method exploits the connection with the mIS property, it is only applicable for the class of games for which it holds, and cannot be directly applied to a wider class of networked public goods games. In addition, given that this method assumes centralized perspective, it is only applicable in situations in which the network structure is known or can be reasonably inferred. Even though the work in this paper answers the question of what outcomes could be reached by self-interested players, the design of mechanisms to move towards such configurations remains challenging problem. Possible incentivization mechanisms that we aim to explore in future work include incentivizing individual players as well as modifying the network structure itself. Since the impact of such interventions on players' actions can be captured by best-response dynamics. this can be formulated as search problem in which the goal is to find the set of interventions that brings us arbitrarily close to the goal state. At a high level, an approach similar the proposed method, which leverages a different deterministic MDP model capturing the impact of interventions, may be used.
Societal Impact and Implications. The direct implication of this work is that it enables a social planner to find beneficial outcomes that can be achieved and maintained by self-interested players for situations that can be modeled by networked best-shot games. This class of games is relevant for variety of scenarios in which the agents forming a society can choose to contribute effort to a public good, and our work is motivated by positive societal impact. We cannot foresee situations in which this method can be directly misused. This relies, however, on the assumption that the social planner aims improve outcomes, rather than have negative impact. Furthermore, this type of modeling necessarily abstract and makes simplifying assumptions that may not hold in the real world.
7 Conclusion
In this work, we have considered the problem of finding desirable equilibria of the graph-base based best-shot public goods game. We have approached this from the perspective of a principal agent with global knowledge of the game, who aims to find optimal Pure Strategy Nash Equilibria in terms of social welfare and fairness of outcomes. We have defined an MDP to find such equilibria, which relies on the connection with the Maximal Independent Set structural property of graphs. Using the UCT algorithm to plan in this MDP yields better results than existing approaches, especially in the case where the costs of acquiring the public good differ between players. We have also proposed Graph Imitation Learning method which is able to learn the structure of these equilibria, yielding performance within 99.5% of the planning method while generalizing different game instances and generating predictions approximately three orders of magnitude quicker on the largest graphs tested.
The proposed method is directly applicable to other settings in which mIS are of interest (see e.g. [15) More broadly, the method for performing planning and imitation learning presented in this work is applicable to a variety of problems which can be formulated as decision-making process graph with the goal of maximizing a given objective function. Areas where this may be of interest include combinatorial optimization and algorithmic reasoning over graphs [8 (1), provided that the horizon for the task is manageable by a search procedure. While we have focused on constructing generalizable models, if predictions need be made for single graph instance, one could also consider combining the planning and imitation learning step in an iterative method similarly to the Exit algorithm [3 47 This work is related other recent work that considers learning in network games (e.g., [48] treats network emergence games) as well as more broadly to ongoing initiatives to study cooperation in multi-agent systems and its impact on societal problems [3]
Acknowledgments and Disclosure of Funding
This work was supported by The Alan Turing Institute under the UK EPSRC grant 101/510 The authors declare no competing financial interests with respect to this work.
10

---

References
[1] Kenshin Abe, Zijian Xu, Issei Sato, and Masashi Sugiyama. Solving NP-hard Problems Graphs with Extended AlphaGio Zero. arXiv preprint arXiv: 19905//6233 2019.
[2] Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning What Defer for Maximum Independent Sets. In ICML, 2020.
[3] Thomas Anthony, Zheng Tian, and David Barber. Thinking Fast and Slow with Deep Learning and Tree Search. In NeurlPS, 2017.
[4] Albert-Láásp Barahási and Réka Albert. Emergence of Scaling in Random Networks. Science, 286(5439); 509-512, 1999.
[5] Thomas D. Barrett, William R. Clements, Jakob N. Foerster, and A. I. Lvovsky, Exploratory Combinatorial Optimization with Reinforcement Learning. In AAAI, 2020.
[6] Irwan Bello, Hicu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural Combinatorial Optimization with Reinforcement Learning. 161.0990 2016.
[7] Yoshua Bengio, Jérôme Louradour, Ronan Collohert, and Jason Weston. Curriculum learning. In ICMI., 2009.
[8] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine Leamingg for Combinatorial Optimization: Methodological Tour d' H'rrrizo.. European Journal Operational Research, 290:405-421, 2021.
[9] Yann Bramoullé and Rachel Kranton. Public goods in networks. Journal of Economic Theory, 135(1): 478-494, 2007.
[10] Coen Bron and Joep Kerbosch. Algorithm 457: Finding all cliques of an undirected graph. Communications of the ACM, 16(9):575-577, 1973.
[11] Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. In ISCAI, 2021.
[12] Vincent Conitzer and Tuomas Sandholm. Complexity Results about Nash Equilibria. In IJCAI, 2003.
[13] Allan Dafoe, Edward Hughes, Yoram Bachrach, Tantum Collins, Kevin R McKee, Joel Z Leibo, Kate Larson, and Thore Graepel. Open Problems in Cooperative AI. arXiv preprint arXiv:2012.08630 2020.
[14] Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for structured data. In ICML, 2016.
[15] L. Dall' Asta, P. Pin, and A. Ramezanpour. Statistical Mechanics of maximal independent sets. Physical Review F, 80(6):01 136, 2009.
[16] Luca Dall' Asta, Paolo Pin, and Abolfazl Ramezanpour. Optimal Equilibria of the Best Shot Game, Journal of Public Economic Theory, 13(6)8885991,, 2011.
[17] Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The Complexity of Computing Nash Equilibrium. SIAM Journal on Computing, (9(1):195-253 2009.
[18] Paul Erdōs and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1): 17- 77-00,15 1960.
[19] Feng Fu, Daniel Rosenbloom, Long Wang, and Martin A. Nowak. Imitation dynamics of vaccination behaviour social networks. Proceedings of the Royal Society B: Biological Sciences, 278(1702):42-49 2011.
[20] Andrea Galeotti, Sanjeev Goyal, Matthew O. Jackson, Fernando Vega-Redondo. and Leeat Yariv, Network Games. Review of Economic Studies, (7(1):2188244) 2009.
[21] Michael R. Garey and David S. Johnson. Computers and Intractability. A Guide to the Theory of NP- Completeness. W. H. Freeman and Co, 1979.
[22] Itzhak Gilboa and Eitan Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1()):00 93, 1989.
[23] Sanjeev Goyal. Connections: An Introduction to the Economics of Networks. Princeton University Press, 2012.

---

[24] Xiaoxiao Guo. Satinder Singh. Honglak Lee, Richard L. Lewis, and Xiaoshi Wang, Deep Learning for Real-Time Atari Game Play Using Offline Monte-Carlo Tree Search Planning. In NeurlPS, 2014.
[25] Aric Hagberg, Pieter Swart, and Daniel S. Chult. Exploring network structure, dynamics, and function using networkx. In SciPy, 2008.
[26] Jack Hirshleifer. From weakest-link to best-shot: The voluntary provision of public goods. Public Choice, 41(3):371-388 1983.
[27] J. D. Hunter. Matplotlib: A 2D graphics environment. Computing in Science & Engineering, 9(3):90-95, 2007.
[28] Matthew O. Jackson and Yves Zenou. Chapter 3 Games on Networks. In Handbook of Game Theory with Economic Applications, volume 4. pages 163, Elsevier, 2015.
[29] Adam B. Jaffe, Manuel Trajienberg, and Rebecca Henderson. Geographic localization of knowledge spillovers as evidenced by patent citations. The Quarterly Journal of Economics, 108(3):577-599, 1993,
[30] Michael Kearns, Michael L. Littman, and Satinder Singh. Graphical Models for Game Theory, In UAI, 2001.
[31] David Kempe, Sixie Yu, and Yevgeniy Vorobeychik. Inducing Equilibria in Networked Public Goods Games through Network Structure Modification. AAMAS, 2020.
[32] D. Kennedy. Sustainability and the Commons. Science, 302(5652);; 18-1-186111-111 2003.
[33] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In NeurIPS, 2017.
[34] Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In ICLR, 2015.
[35] Levente Koesis and Csaba Szepesvári. Bandit Based Monte-Carla Planning. ECML, 2006.
[36] Peter Kollock. Social Dilemmas: The Anatomy of Cooperation. Annual Review of Sociology, 24(1): 183-214, 1998.
[37] John O. Ledyard. Public Goods: A Survey of Experimental Research, pages 111-194. Princeton University Press, 1995.
[38] Vadim Levit, Zohar Komarovsky, Tal Grinshpoun, and Amnon Meisels. Incentive- based search for efficient equilibria of the public goods game. Artificial Intelligence, 262:142-166 1622, 2018.
[39] Richard D. McKelvey and Andrew McLennan. Computation of equilibria in finite games. Handbooo of Computational Economics, 1:87-142, 1996.
[40] Wes McKinney et al. pandas: foundational Python library for data analysis and statistics. Python for High Performance and Scientific Computing, 14(9):19. 2011.
[41] M. Milinski, D. Semmann, H.-J. Krambeck, and J. Marotzke. Stabilizing the Earth's climate is not losing game: Supporting evidence from public goods experiments. PNAS, 103(11):3994 3998, 2006.
[42] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takáč. Reinforcement Learning for Solving the Vehicle Routing Problem. In NewrlPS, 2018.
[43] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, et al. Pytorch: An imperative style, high- performance deep learning library. In NeurlPS, 2019.
[44] Dean A. Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural Computation, 3(1):88 97, 1991.
[45] Yelong Shen, Jianshu Chen, Po-Sen Huang, Yuqing Guo, and Jianfeng Gao. M-Walk: Leamingg Walk over Graphs using Monte Carlo Tree Search. In NewrlPS, 2018.
[46] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):844 489, 2016.
[47] David Silver, Julian Schritwieser, Karen Simonyan, Ioannis Antonoglou, et al. Mastering the game of Go without human knowledge. Nature, 550(7676):354-355 2017.
[48] Rakshit Trivedi and Hongyuan Zha. Learning strategic network emergence games. In NeurIPS, 2020.
12

---

[49] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer Networks. In NeurIPS, 2015.
[50] Michael L. Waskom. Seaborn: statistical data visualization. Journal of Open Source Software, 6(60):3021, 2021.
[51] Duncan J. Watts and Steven H. Strogatz. Collective dynamics 'small-world" networks. Nature, 393 (6684):440, 1998.
[52] Sixie Yu, Kai Zhou, P. Jeffrey Brantingham, and Yevgeniy Vorobeychik, Computing Equilibria in Binary Networked Public Goods Games. In AAAI, 2019.
[53] Wojeiech Zaremba and Ilya Sutskever, Learning to execute. arXiv preprint 2014.
13


Reviews:
[{"review_id": "txIBtASxrAI", "reviewer": "Reviewer_Ti5Q", "summary": "This paper tries to solve the public good game problem (NP-complete). Existing methods can only find sub-optimal results of this problem and cannot optimize in different criteria. This paper proposes a method that directly uses the relationship between equilibria of the public good game problem and the Maximal Independence Set problem. The proposed method outperforms existing approaches in searching for the best equilibria. The paper uses imitation learning technique to generalize the learned equilibria to unseen game instance effectively.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: First, this paper proposes a new method to solve the classic public good game problem. It uses the correspondence of this problem and maximal independence set problem to define a Markov decision process. And by doing this, it adopts a variant of Monte Carlo Tree Search method to solve the planning problem in this MDP. The searched result is the wanted equilibria in the public good game problem. In a word, this paper transforms the public good game problem into a search problem and uses Monte Carlo Tree search method to solve it. Second, this paper use imitation learning to learn the structure of the equilibria found by the proposed MDP, such that it could predict on novel game instances without repeating the search process. It uses a dataset of demonstration of the Monte Carlo Tree Search to train a graph neural network and this GNN represented a policy learn from the dataset. \n\nQuality: the paper shows that the proposed method outperforms many baseline methods. It has higher mean rewards on many game instances and the outperformance holds as the size of the problem increases. The proposed method did run faster than some baseline methods. \n\n- As for the imitation learning part (section 4.3), the description of Figure 4 is not very clear. What is the use of that figure to explain the quality of the imitation learning part?\n\n- As for the collection of demonstration part (section 4.2), how does the demonstration look like and how to collect it to be the dataset is not stated very clearly. Providing more details might help the reviewer to have a more straightforward understanding in the following imitation learning part.\n\nClarity: this paper is well organized. It first introduces public good game problem clearly and explain many infrequent notion and terms used in the paper, so it won’t cause too much difficulty in reading this paper. The proposed method part is well organized and easy to follow. \n\nSignificance: This paper is proposing an important method. First, it can be used to solve the public good game problem that outperforms existing methods. Second, the problem it tries to solve is very hard (NP-complete) and the current method (including the proposed one) can only reach a sub-optimal solutions. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "Yp6WkKtPcJv", "reviewer": "Reviewer_cDVM", "summary": "The problem studied by the authors is finding pure Nash equilibria in public goods games on graphs that maximize certain functions (e.g., social welfare, fairness). The authors search over maximal independent sets on the graph, a connection that was proven equivalent to PSNE by previous authors. Past approaches include exhaustive search, iterative best response, and several bespoke algorithms developed over the past 20 years. The authors formulate the search problem as an MDP, where the maximal independent set is formed by adding one node at a time. The authors solve this search problem in two ways. The first is with out-of-the-box Monte Carlo tree search (UCT). The second is via imitation learning, where a GNN is trained to predict the best decisions in Monte Carlo tree search. The first, UCT, approach achieves strong performance w.r.t. mean reward across many instances, beating the benchmarks. The imitation learning approach also beats the benchmarks and run several orders of magnitude faster once trained. Both methods appear to lie on the Pareto frontier of speed vs. performance, in the slower speed/higher performance part of the space.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors' approach falls under the broad umbrella of applying AI/ML techniques to combinatorial optimization. This is not a new idea in itself, but there are not that many examples where it has looked as useful as it does here. The paper is well written and clear overall. I have a few specific comments:\n- The authors should include a formal description of their algorithms in pseudocode, either in the main text or supplement. This is particularly an issue for the imitation learning approach, which is complex and not that clearly described in the text.\n- The authors should report more statistics than average reward and standard error in experiments. In particular, they should report some kind of win/loss metric, potentially in the supplemental material. The issue is that some methods could be outperforming others by a large amount on a small number of problems, but by a lot, and still be performing worse on many.\n- I could not find a clear report of the time spent training IL-UCT to get the level of performance they achieve. Training curves for IL-UCT and time per iteration need to be included.\n\nI thought the method of selecting actions via the proto-action was interesting and the authors could advertise this contribution more (say in a sentence in the intro).\n\nPost-response: I appreciate the authors' response. It seems there are no major points of disagreement.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have a para devoted to limitations and one devoted to social impact. Both are clear and useful. I would suggest moving the social impact para to the supplement if more space is needed—the work is quite abstract, and I did not find social impact to be a major concern.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "I9H8-V-WU5D", "reviewer": "Reviewer_ExWG", "summary": "This paper algorithms for computing desirable equilibrium strategies (maximize social welfare or fairness) in best-shot public good games (PGGs), which are PGGs on graphs in which each agent wants itself (good) or one of its neighbors (best) to have a good (though obtaining the good itself comes with a cost).  Initially, the paper describes an algorithm for computing equilibria of such games by defining and MDP constructed by identifying Maximal Independent Sets.  The resulting algorithms performs well, particularly on large graphs.  The paper also proposed a way to learn the structure of the solutions found by the planning algorithm based on imitation learning, which achieves 99.5% performance will reducing the computation time by approximately 3-orders of magnitude.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n\n+ The problem definition, solutions, and results are describe carefully, rigorously, and clearly, such that is it easy to follow the paper.  \n\n+ The outcomes of the algorithms are good, exceeding the state-of-the-art, and the analysis is extensive.\n\n+ The paper is presented in a way that it is enjoyable to read.\n\nQuestions about significance:\n\n- PGGs are interesting because the group good is somewhat in conflict with individual incentives.  Computing desirable solutions in these games from a centralized perspective may be useful, as it defines what society could do.  However, as the paper acknowledges, it is unclear how to get individuals to actually carry out the computed solution.  So I in some sense question the papers usefulness (perhaps because I lack some domain knowledge or an imagination).\n\n- As acknowledged in the paper, the paper’s scope is limited in that it only works for this very specific set of games.\n\nIn short, the paper is well-done in all respects.  My questions regarding the work lie in its significance to the NeurIPS community, but I hesitate somewhat to maintain that position (as it seems somewhat unfair).\n\nIrrelevant nitpick:\n- Figure 4 is discussed in the test after Figure 5 (I think).  Perhaps reorder the figures?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "?"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper tackles graph-based public good games and proposes efficient search-based and learning-based algorithms for finding desirable equilibria. Based on all the reviews, responses, and discussions, here is the overall evaluation: 
(+) It is a solid paper with a clearly defined problem (public good game on a graph) and analysis.
(+) It proposes tree-search-based (case-specific) and imitation learning-based (generalizable to new cases) algorithms for computing desirable pure strategy Nash equilibrium and these algorithms show superior performance in the experiments. The latter leverages the graph-neural network and is a new example of learning-powered combinatorial optimization with very good performance. 
(-) The description of the algorithm, figure, and experimental results lack some details. The authors agree to provide additional results and details in their responses, which partially addresses the reviewers’ concerns.
(-) The team is not fully sure whether it can lead to a significant impact on society as it is hard to apply this algorithm to guide individuals in practice in a concrete application. Since the analysis of equilibrium is an important step towards a better understanding of public good games, the team still thinks the work is of value to the community. 

Overall, the reviewer team has a positive view of the paper. We suggest the authors make changes they promised in the responses to improve the paper.
Decision: Accept (Poster)