A quantitative assessment of the global importance of an agent in a team is as valuable as gold for strategists, decision-makers, and sports coaches. Yet, retrieving this information is not trivial since in a cooperative task it is hard to isolate the performance of an individual from the one of the whole team. Moreover, it is not always clear the relationship between the role of an agent and his personal attributes. In this work we conceive an application of the Shapley analysis for studying the contribution of both agent policies and attributes, putting them on equal footing. Since the computational complexity is NP-hard and scales exponentially with the number of participants in a transferable utility coalitional game, we resort to exploiting a-priori knowledge about the rules of the game to constrain the relations between the participants over a graph. We hence propose a method to determine a Hierarchical Knowledge Graph of agents' policies and features in a Multi-Agent System. Assuming a simulator of the system is available, the graph structure allows to exploit dynamic programming to assess the importances in a much faster way. We test the proposed approach in a proof-of-case environment deploying both hardcoded policies and policies obtained via Deep Reinforcement Learning. The proposed paradigm is less computationally demanding than trivially computing the Shapley values and provides great insight not only into the importance of an agent in a team but also into the attributes needed to deploy the policy at its best.

本文提出了一种基于Shapley分析实现多智能体系统中个体贡献度评估的方法，并利用层次化知识图谱用于降低计算复杂度，同时通过测试证明了该方法不仅能评估团队中个体的重要性，还能揭示实现最佳策略所需的特征属性。

Towards a more efficient computation of individual attribute and policy
  contribution for post-hoc explanation of cooperative multi-agent systems
  using Myerson values

利用Myerson值更高效地计算合作多智能体系统的个人属性和政策贡献，以实现事后解释