Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies a coalition formation process in federated learning. When agents form a coalition, they aggregate their learned parameters in the hope of a more accurate result. The paper presented an algorithm to obtain the optimal way of partitioning the agents in coalitions, so that the total weighted error of the agents is minimized. In addtion, the paper also analyzed the price of anarchy and provided upper bounds of it.
main_review: The paper presented some interesting and novel results. The topic about incentives in federated learning also looks important for this research area and is likely to inspire new ideas. 

The paper is well-written. The presentation is mostly clear and the results look sound (though I didn't check details in the appendix). 

One question I have is about the emptiness of the core: Does a core (or individual) stable arrangement always exist? If this is not guaranteed, I wonder how meaningful the PoA bounds are.

Several typos:

- 131, Page 3, "...if player j has samples than..." --> if player j has more samples?

- 205, Page 5, "could could"

- 216, Page 5, there's a grammar issue.
limitations_and_societal_impact: Adequately addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies price of anarchy (PoA) in federated learning. Following the prior work of Donahue and Kleinberg [2021] which initiate a game theoretic model for federated learning, the authors propose a notion of optimality given the average error rates among agents. Under this notion of optimality, the authors first provide an efficient algorithm to compute the optimal solution, and then give PoA bounds that depend on parameters of settings.
main_review: This paper is well-written, clear, and easy to follow. The problem studied is well-motivated from the context of federated learning and is important for practical applications. The collection of results seems novel and technically strong, and they give useful insight for real practice. The reviewer did not check all the proofs but they all look plausible in hindsight.

Comments:

1. In line 131-132, it seems something is missing in the sentence? Do you mean "player j has *more* or *less* samples than k"? The reviewer wonders whether the claim that "player j will have lower expected error than k" is always true in either situation. Doesn't it also depend on noise and dissimilarity of the distributions?

2. It seems that all the lemmas and theorems in section 4.1 highly depend on the modeling assumption, such as the notion of optimality and utility models of agents. How robust are these results? Could they be extended to more broader models?

3. The reviewer finds that the contrast of PoA bounds due to sample sizes v.s. noise and dissimilarity is very interesting. Could you provide more insights about these results? It seems that the results are driven by the fact that the only difference across agents is the number of samples they have (as their distributions are drawn from the same prior). It would be interesting to see what happen if their priors are different.

Minors:

1. Line 56: "leaves open" remove one of them
2. Line 237: Lemma 9 here?
limitations_and_societal_impact: The reviewer is curious about whether the results can be generalized to other game-theoretic models of federated learning, e.g., for different notion of optimality and utility models of agents.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper examines the game theoretic aspect of federated learning. In the proposed model, the players are strategic and may not provide their data to the learning platform and choose to federate in a small coalition. The authors provide an algorithm to compute the optimal federating arrangement, and also analyze the bound of the price of anarchy in theory.
main_review: This paper is written in a nice way and easy to understand. The concept of price of anarchy is worth investigating in this setting as a low price means the federtion is beneficial to the welfare. The theoretic results are interesting and obtained through careful analyses (did not check all the details though). However, I am concerned with one of the fundamental assumptions of the paper. Lemma 1, which is from another paper, assumes that the parameter \theta_j of player j is drawn from a common distribution. This paper also implicitly used the same assumption. Line 169 further assumes that n_i is fixed and known by all player. With this assumption, all players know the actual underlying data distribution and can just learn any model by simply sample enough points from this distribution. One of the implicit but fundamental assumptions of federated learning is that each player does not know the data distribution of others so they cannot get more useful data to train their own model. Can the authors provide more justifications to their modeling choice?
limitations_and_societal_impact: Please refer to the main review for details.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies a basic federated learning problem, in which some agents, each one with their own dataset, have to jointly agree on a global model. The paper focuses on the trade-off between stability (enforcing that agents are incentivized to collaborate in the global model) and optimality (maximizing social welfare). The paper studies this trade-off by means of a Price of Anarchy analysis.
main_review: Originality: The problem studied in the paper is interesting, being part of a rather new research filed that is receiving a growing attention from the literature in recent years. As far as I am concerned, the Price of anarchy analysis is novel in this field.

Quality: As far as I am concerned, all the proofs are correct.

Clarity: The paper has some major problem in the presentation. First, it is not clear from the first three sections which elements are introduced in this paper and which ones are taken from the literature. I think that re-organizing the sections so as to have one section entirely devoted to preliminaries and model definition would help improve clarity.

Significance: The approach of the paper to federated learning is mainly theoretical, I think that some more experimental analysis would be expected for a NeurIPS paper on this topic.
limitations_and_societal_impact: Adequate.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the stable coalition in federated learning, where the agents can choose to join one coalition or leave with incentives to minimize their own errors. The paper focuses on the task of mean estimation, where the error has a closed-form solution. The main contributions are:
1. proposing an optimal algorithm to minimize the weighted sum of errors;
2. providing the upper bound on PoA.
main_review: Originality: The task and the methods are new. The paper provides an optimal algorithm and an upper bound on PoA, which have not been studied before.

Quality: The submission is technically sound. All claims are well supported.

Clarity: The writing is clear. But some important notions should be addressed more formally, e.g., core stable and individually stable. It would be better if both notions could be defined mathematically. Besides, in line 261, the authors states "all members of $C$ weakly prefer...", where I don't understand what "weakly" means here. 

Significance: The paper studies an interesting problem on the stable coalition in federated learning. 
It looks like this paper only discusses the results of the mean estimation problem. In this specific task,  the error has a closed-form solution, which makes the analysis easier than that in a more general task. But it is still a good first step towards analyzing a more general problem. The results are important.  The paper provides an elegant algorithm achieving optimality and shows that PoA w.r.t. individually stability is upper bounded by 9.

Other comments:
1. The paper mentions that it focuses on mean estimation game in Line 163. If this submission only focuses on the mean estimation task, this should be addressed earlier, including the abstract, intro and even the title, as the paper does not study the general problem of federated learning.
2. Typo: In line 131, it should be " if agent $j$ has \emph{more} samples than ..."



limitations_and_societal_impact: Yes
review_title: null

Meta-review: The rebuttals helped the Reviewers to understand better the original contributions provided in the paper. However, I have two major suggestions for the authors when producing the camera-ready version of the paper:
1. clarify better the assumptions, even those made implicitly, and clarifying them in the formal statements;
2. re-organize the first three sections to clarify which are the original contributions and which are related works, in particular it would be nice to have one section entirely devoted to preliminaries and model definition.
Decision: Accept (Poster)