When autonomous agents interact in the same environment, they must often cooperate to achieve their goals. One way for agents to cooperate effectively is to form a team, make a binding agreement on a joint plan, and execute it. However, when agents are self-interested, the gains from team formation must be allocated appropriately to incentivize agreement. Various approaches for multi-agent negotiation have been proposed, but typically only work for particular negotiation protocols. More general methods usually require human input or domain-specific data, and so do not scale. To address this, we propose a framework for training agents to negotiate and form teams using deep reinforcement learning. Importantly, our method makes no assumptions about the specific negotiation protocol, and is instead completely experience driven. We evaluate our approach on both non-spatial and spatially extended team-formation negotiation environments, demonstrating that our agents beat hand-crafted bots and reach negotiation outcomes consistent with fair solutions predicted by cooperative game theory. Additionally, we investigate how the physical location of agents influences negotiation outcomes.
Note: This is an emergency review. I managed not to look at existing comments/ratings for this paper before writing my review.
Summary
---
This paper studies deep multi-agent RL in settings where all of the agents must cooperate to accomplish a task (e.g., search and rescue, multi-player video games). It uses simple cooperative weighted voting games 1) to study the efficacy of deep RL in theoretically hard environments and 2) to compare solutions found by deep RL to a fair solution concept known in the literature on cooperative game theory.
In a weighted voting game each agent is given a weight and the agents attempt to form teams. The first team whose total weights exceed a known threshold get the total reward, which is distributed amongst the team members. Given such a game, the __shapely value__ of an agent measures the importance of that agent. How much does it contribute to a team from this set of agents? How much payoff should it get? These have existed in the literature for over 60 years and appear to be widely known and used.
All of this is agnostic to how the agents communicate to form teams: i.e., the communication protocol or the actions available in the environment. The protocol matters because it can allow certain teams to form more or less easily than others, even though the same team would get the same reward regardless of protocol. This can make an agent more or less effective under different protocols. Here two protocols are considered - one where agents suggest proposed teams directly and another where they suggest teams by congregating on a 2d plane. Both protocols result in games whose Nash equilibria are computationally intractable.
The paper shows 4 results:
1) It considers a hand-designed bot similar to models from the game theory literature. Relative to a group of RL agents, an additional RL bot will outputperform a hand-designed bot in terms of average reward it receives.
2) The average reward of a bot is strongly correlated with that bots shapely value.
3) In the negotiation by congregation environment, a bot's spatial position can affect its ability to negotiate.
4) Shapely values can be predicted quite accurately from the weights and threshold that define a cooperative voting game, though these predictions have high variance.
The paper concludes that deep RL is effective at learning agents for cooperative games in multiple ways:
1) Deep agents are better than a hand-designed agent.
2) Deep agents easily extend across negotiation protocols (something hand-designed agents don't do).
3) A popular result in cooperative game theory predicts how effective agents should be. Deep agents are just about that effective.
Strengths
---
* The paper does a pretty good job of reviewing relevant work from game theory.
* Some of the organization is nice (e.g., the list of reasons classic game theory doesn't extend to practice; one section per experiment).
Weaknesses mentioned in individual sections...
Quality
---
Overall, things were well thought through, but I would have liked more out of the experiment 4 section and I think a few minor details might have been missed.
Details:
Section 4.5/Experiment 4: The Shapely value comparison is the most important part of the paper.  This section is important because it tries to explain those results, but it seems like there's more work to be done here. I'm not sure capacity is eliminated as a concern, and there might be other concerns not listed like optimization error.
* I'm not sure what conclusion to take from experiment 4. Shapely values can be computed from the cooperative games directly, independent of protocol. We're interested in __policies__ that get exactly the shapley values as their average reward. Policies depend on the protocol. Does being able to predict shapley values mean that a model with similar capacity can learn a policy that will have the desired shapley value? Was that the desired conclusion?
Other comments:
* The current hand-designed baseline uses weights to form a probability distribution. There should be another baseline that uses Shapley values instead of weights.
* It's not clear exactly what the spatial nature of the Team Patches environment adds. It is good to try another environment just to have an additional notion of generalization.
Clarity
---
Overall, the motivation could be clearer. Is the point to do work on cooperative games or to compare to Shapley values?
Presentation details:
* The paper does not get to specific examples of agents acting in environments until about page 4. Providing a simple, brief example which leaves out some details at the beginning would go a long way toward aiding intuitions about the abstract concepts discussed. Here are some clarity issues I had that might have been helped with an example:
    * What exactly is it about a task which requires agents to form teams? How necessary are those teams?
    * What exactly is a negotiation protocol?
    * What does it mean to distribute/share a reward across agents?
* When talking about shapely values, fairness seems to be emphasized somewhat often, but no concrete intuition about what fairness means in this setting is provided.
* Intro para 4: What does the human data measure? And thus how might it be useful?
* Intro para 7: People in the ICLR community will be more familiar with this work. What is the difference between communication and team forming?
* The section on Shapley values should provide more intuition about what they're thought about as measuring. (An agent's importance or what payoff it should expect, according to wikipedia.)
* Instead of measuring correlation to Shapley values, the paper measures whether average reward approximates Shapley values. It seems like the two are on a different scale. Average reward is unbounded and Shapley values are in [0, 1]. How are they comparable?
* The paper mentions how results vary over different types of boards (ones with higher and lower variance in the sampled weights). It does not show results to support this discussion. A conditional analysis of performance would be interesting and relevant, perhaps conditional versions of Fig. 3.
Originality
---
I do not know much about game theory and I'm only somewhat familiar with multi-agent deep RL, so I am not in a great position to judge novelty. Nonetheless, Given existing work in multi-agent RL, it is unsurprising that deep RL agents learn reasonable policies in these environments.
As far as I know, the comparison of average reward to shapely values has not been done before. 
Significance
---
Most work in multi-agent RL evaluates by 1) comparing to baselines or 2) measuring some environment/task-specific metric. The best thing about this work is that it evaluates by comparing actual performance to some external theory that suggests how well an agent should be able to do, falling into a 3rd category.  It's not alone in this category (e.g., paper compare to theoretically optimal baselines if they can), but it is interesting to see another example of this kind of evaluation.
The community might possibly start to focus more on cooperative games because of this paper. A more interesting result would occur if others are inspired to implement more comparisons to how agents __should__ perform in theory.
Justification for Final Rating
---
I am unsure about novelty. As described above, the paper is lacking in clarity and quality (esp. section 4.5), but I don't think these concerns would invalidate the main result. I think the contribution is significant because of the kind of evaluation, but I'm not sure it will ultimately have a large impact. Thus I think some of the concerns above should be addressed before publication, but I would not be very disappointed if it were published as is.