Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Strengths: 

+ The problem definition, solutions, and results are describe carefully, rigorously, and clearly, such that is it easy to follow the paper.  

+ The outcomes of the algorithms are good, exceeding the state-of-the-art, and the analysis is extensive.

+ The paper is presented in a way that it is enjoyable to read.

Questions about significance:

- 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).

- As acknowledged in the paper, the paper’s scope is limited in that it only works for this very specific set of games.

In 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).

Irrelevant nitpick:
- Figure 4 is discussed in the test after Figure 5 (I think).  Perhaps reorder the figures?
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 

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

- 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?

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

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

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


limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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:
- 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.
- 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.
- 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.

I 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).

Post-response: I appreciate the authors' response. It seems there are no major points of disagreement.
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_title: null

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)