Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper proposes a (decentralized) method for online adjustment of agent incentives in multi-agent learning scenarios, as a means to obtain higher outcomes for each agent and for the group as a whole. The paper uses the “price of anarchy” (the worst value of an equilibrium divided by the best value in the game) as a proxy for the efficiency of the game outcome, and derive an upper bound on a local price of anarchy that agents can differentiate. In several experiments (a traffic network, the coin game, Cleanup), their method leads to improved individual agent and group outcomes relative to baselines, while avoiding cases of stark division of labor that sometimes emerges when agents directly optimize the sum of all agent rewards. 

Pros:
Overall, I thought this paper was quite strong. I agree with the claim in the paper that having agents simply optimize the cooperative return is not always realistic or interesting. The framing of compromise as the mixing of agent incentives is particularly interesting, and it makes intuitive sense to me. I’m not familiar enough with the literature to know if this formulation is novel (and unfortunately the paper does not have a Related Work section). The paper makes significant contributions towards making this idea practical, including relaxing the requirement that the agents can observe or directly differentiate with respect to the other agent strategies. 

The paper is also pretty well written and communicated, though I did not dive into the proofs and skimmed some of the technical details. I appreciated the frankness with which the paper describes their method, e.g. in the following excerpts:
“Ideally, one meta-algorithm would allow a multi-agent system to perform sufficiently well in all these scenarios. The approach we propose, D3C (Sec. 2), is not that meta-algorithm, but it represents a holistic effort to combine critical ingredients that we hope takes a step in the right direction”
“We also provide specific, albeit narrow, conditions under which agents may achieve a Nash equilibrium”

Cons:
Of course, the ‘mixing of losses’ strategy proposed in the paper requires that agents be able to observe the losses of other agents, which is not always feasible in practice.

Other notes:
I was a bit confused by the sentence: “Our agents reconstruct their losses using the losses of all other agents as a basis”, which seems to imply that the agents’ own loss function is not used as part of this basis. 

The Appendix also seems to be missing from the paper, although there are references to it in the text (e.g. reference to F.4). 

Overall:
On the whole, I think this paper is quite good and worthy of acceptance. 

review_title: Review

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##########################################################################

Summary:

This paper proposes a differentiable, local estimator of multi game inefficiency, as measured
by price of anarchy. We then present two instantiations of a single decentralized meta-algorithm, one
1st order (gradient-feedback) and one 0th order (bandit-feedback), that reduce this inefficiency. Experiments conducted in three domains (traffic network, Coins and Cleanup) show that agents minimizing local estimates of price of anarchy achieve lower loss on
average than selfish agents without the ability to compromise.

##########################################################################

Reasons for score: 

Overall the paper is well organized and provided clear motivation of the problem. The proposed approach is well-presented and the idea of mixing losses is interesting. An upper bound for the optimized price of anarchy is presented.

##########################################################################Pros: 

Detailed comments and concerns:

1. What is the implication of "mixing losses" in practical systems? What are the incentives for agents to adjust their original incentives? I would like to see more discussions addressing the incentive compatibility issue in adjusting for a mixing losses.

2. The authors show that if each agent’s original loss is convex with diagonally dominant Hessian and the strategy space is unconstrained, the the unique, globally stable fixed point of the game defined with mixed losses is a Nash. I would be willing to see more discussions on if these restrictions could be relaxed to achieve Nash under the mixed losses.

3. What are the computation times for running D3C, and how does that compare to the baselines?

----- Post Discussion ---- Updates to the paper have helped make the motivation/technical parts of the paper more clear. The authors' response are helpful w.r.t the questions I raised in the review.

 
review_title: recommendation to accept

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper details a method by which it attempts a method to change the utility function for agents so they incorporate the utilities of other agents, resulting in more cooperating agents, so that the price of anarchy is minimized. It examines such trained agents in several problem settings, seeing them performing quite well.

The attempt to change the utility is quite interesting, but, sadly, it is not really explored enough. That is, while agents improve, no attempt has been made to examine the new "mixing" matrix, and see what changed to make the agents collaborate better (or not). It is quite a pity, as in this case, unlike many other learning cases, the result is quite interpretable for us.

As more a game-theorist than a ML expert, I did struggle a bit with the technical bits in section 2. The definition of "local price of anarchy" seems sometime overlapping, but not really the same as the definition of that of Ben-Zwi and Ronen from 2011 ("Local and global price of anarchy of graphical games", TCS 412, 1196-1207). I had some difficulty following algorithm 1, as \Delta t_b seems always negative, and it was not clear to me what G is (and in particular, for negative values).

In the experimental section, as noted above, an interpretation of the A matrix would have helped. At least in some of the examples, it seems a matrix A with each value being 1/n seems to satisfy all that's needed (e.g. the Braess paradox). I could not follow the setting of the "zero-sum election", and what is the described game. Moreover, the introduction promises an incentive-compatible setting. What is intended to be an IC mechanism?

UPDATE POST-REBUTTAL
————————————
Many of my questions have been answered, though I do think reviewers should explicitly note Ben-Zwi and Ronen's paper, and change their use of "incentive compatible". I think a deeper and more systematic analysis of the A matrix is also warranted, but I do now feel the paper has better scientific merit.
review_title: Nice idea, but not explored deeply enough

final_score: rating: 3: Clear rejection
review_content: The authors propose to change agents' incentives in order to lead to a better Nash equilibrium outcome. 
They propose a practical decentralized approach to computing the "optimal" change of incentives.
I'm confused by many aspects of this paper:
1. How would you implement the change of incentives in a any of the game theoretic domains? I.e. in what context would agents who lose money agree to participate without a centralized authority ordering them to?
2. Why do you consider changes of incentives with bounded KL-divergence? What does that have to do with your motivating concern around communication (3rd paragraph of intro)?
3. Why do you optimize the price of anarchy instead of social welfare at worst Nash equilibrium? These should be the same when you don't change the total loss, but then I don't understand the denominator of (3).
4. What is $t$ in (4)? How does f^A_i depend on t?
5. Shouldn't \beta_i appear in (4)? Or does (4) hold for all \beta_i (e.g. approaching infinity)?
6. What should I conclude from your experiments? Of course if you completely mix the agents' utilities the Nash equilibrium would be locally optimal. The Nash equilibrium utilities at the modified games seem better, but it's not clear how much the games were modified.

Misc:
(A) Computing the Price of Anarchy in general is NP-complete rather than PPAD-complete because PPAD corresponds to finding *any* Nash equilibrium rather than the worst one.
(B) "set of the equilibria of the game restricted to the line" - I don't understand what this sentence means.
(C) Why don't you define utilitarian/egalitarian before Theorem 1?
(D) Typos: "one-hot" "the the"


review_title: I'm confused about too many things with this paper

Meta-review: This paper proposes a method of decentralized mechanism design to reduce the price of anarchy. Based on the detailed responses of the authors, all reviewers were satisfied by the technical contribution after the rebuttal period. 

There was, however, a heavily engaged and lengthy discussion between most reviewers regarding the applicability of the method and how it links to the motivation given in the paper. The paper could be improved by (1) highlighting an exemplar real world use case in the paper motivation (there are a couple mentioned briefly in the introduction but one of these could be emphasized more); and (2) connecting the choices made in the design of the approach to the opening motivation sections and exemplar use case.

The level of engagement from most reviewers demonstrates a good level of interest from a representative sample of the ICLR community but demonstrated that their remained work outstanding to clarify the core message and significance of the contribution.
Decision: Reject