子模块功能一直是多种现实应用程序的强大数学模型。最近，用于建模数据和功能等实体之间的建模概念（例如信息和冗余），在机器学习（ML）中越来越重要。在这些应用中，一个关键问题是回报分配，即如何评估每个实体对集体目标的重要性？为此，合作游戏理论的经典解决方案概念提供了有原则的收益分配方法。然而，尽管游戏理论文献广泛，但在研究中的收益分配相对不足。特别是，在新兴的子模型应用程序中出现的一个重要概念是冗余，这可能来自各种来源，例如丰富的数据或恶意操纵，在这些来源中，玩家复制其资源并在多个身份下行动。尽管许多游戏理论解决方案概念可以直接用于子模型游戏中，但天真地将它们应用于这些设置中的回报可能会导致鲁棒性问题，以防止复制。在本文中，我们系统地研究了子模型游戏中的复制操作并研究了复制鲁棒性，该指标可以定量测量解决方案概念抗复制的鲁棒性。使用该指标，我们提出了从理论上描述半相象的鲁棒性的条件，该标准是夏普利和班扎夫价值在内的广泛解决方案概念的鲁棒性。此外，我们从经验上验证了我们在新兴的Subsodular ML应用程序（即ML数据市场）上验证我们的理论结果。

本文研究了数据估值对嘈杂模型性能得分的鲁棒性。特别是，我们发现广泛使用的随机梯度下降的固有随机性会导致现有的数据值概念（例如，沙普利值和剩余错误），以在不同运行中产生不一致的数据值排名。为了应对这一挑战，我们首先提出一个正式的框架，在该框架中可以测量数据值概念的鲁棒性。我们表明，Banzhaf的价值是一个源自合作游戏理论文献的价值概念，它在所有半估计中实现了最大的鲁棒性 - 一类价值概念满足ML应用程序所带来的重要属性。我们提出了一种算法，以根据最大样本重用（MSR）原理有效地估计Banzhaf值。我们得出了Banzhaf值近似的下限样品复杂性，并表明我们的MSR算法的样品复杂性几乎与下限匹配。我们的评估表明，Banzhaf值的表现优于几个下游ML任务（例如使用加权样品学习和嘈杂的标签检测）的现有基于半半数的数据值概念。总体而言，我们的研究表明，当基础ML算法是随机的时，Banzhaf值是基于半杂志的数据值方案的有前途的替代方法，因为其计算优势和能力可靠地区分数据质量。

基因集合是研究特定表型特征基因富集的共同点。基因集富集分析旨在鉴定基因集集合中代表过多的基因，并且可能与特定的表型性状有关。但是，由于这涉及大量的假设检验，因此通常值得怀疑的是，减少基因集的预处理步骤是否有帮助。此外，通常高度重叠的基因集以及基因集集合的低解释性要求减少所包含的基因集。受到这种生物信息学上下文的启发，我们提出了一种方法，可以根据单例及其大小在集合中进行排名。我们通过计算shapley值而不会导致值函数的评估数量数量来获得集合的重要性得分。此外，我们解决的挑战是，在我们的情况下，如果它们显示出突出的十字路口，则在获得的排名中包括冗余意识。我们最终评估了基因集合的方法；获得的排名显示出低冗余和高覆盖基因。拟议的排名的无监督性质不允许在减少集合的大小时明显增加特定表型特征的显着基因集数量。但是，我们认为提出的排名用于生物信息学以提高基因集集合的解释性，并向前迈出一步，将冗余纳入沙普利价值计算中。

测量贡献是合作游戏理论中的一个经典问题，其中沙普利价值是最著名的解决方案概念。在本文中，我们在参数贝叶斯学习游戏中建立了沙普利价值的收敛属性，玩家使用其组合数据进行贝叶斯推断，后端kl差异被用作特征函数。我们表明，对于任何两个玩家，在某些规律性的条件下，其在Shapley价值上的差异与限制性游戏的Shapley值的差异有关，其特征功能与联合Fisher信息的对数确定性成正比。作为一个应用程序，我们介绍了一个在线协作学习框架，该框架是渐近的沙普利 - 费尔。我们的结果使得可以实现这一目标，而无需对后端KL差异的任何昂贵计算。仅需要一致的Fisher信息估计器。使用现实世界数据通过实验证明了我们框架的有效性。

在许多多机构设置中，参与者可以组建团队以实现可能超过其个人能力的集体成果。衡量代理商的相对贡献并分配促进持续合作的奖励份额是艰巨的任务。合作游戏理论提供了识别分配方案（例如沙普利价值）的解决方案概念，这些概念公平地反映了个人对团队或核心表现的贡献，从而减少了代理人放弃团队的动机。此类方法的应用包括识别有影响力的特征并分享合资企业或团队成立的成本。不幸的是，即使在受限设置中，使用这些解决方案也需要解决计算障碍，因为它们很难计算。在这项工作中，我们展示了如何通过训练神经网络提出公平和稳定的回报分配来将合作游戏理论解决方案蒸馏成学习的模型。我们表明，我们的方法创建的模型可以推广到远离训练分布的游戏，并且可以预测比训练期间观察到的更多玩家的解决方案。我们框架的一个重要应用是可以解释的AI：我们的方法可用于加快在许多情况下的Shapley价值计算。

机器学习模型，尤其是人工神经网络，越来越多地用于为在各个领域的高风险场景中（从金融服务，公共安全和医疗保健服务）提供信息。尽管神经网络在许多情况下都取得了出色的性能，但它们的复杂性质引起了人们对现实情况下的可靠性，可信赖性和公平性的关注。结果，已经提出了几种A-tostori解释方法来突出影响模型预测的特征。值得注意的是，Shapley的价值 - 一种满足几种理想特性的游戏理论数量 - 在机器学习解释性文献中获得了知名度。然而，更传统上，在统计学习中的特征是通过有条件独立性正式化的，而对其进行测试的标准方法是通过有条件的随机测试（CRT）。到目前为止，有关解释性和特征重要性的这两个观点已被认为是独特的和独立的。在这项工作中，我们表明基于沙普利的解释方法和针对特征重要性的有条件独立性测试密切相关。更确切地说，我们证明，通过类似于CRT的程序实现了一组特定的条件独立性测试，评估了Shapley系数量，以执行特定的条件独立性测试，但用于不同的零假设。此外，获得的游戏理论值上限限制了此类测试的$ p $值。结果，我们授予大型Shapley系数具有精确的统计意义，并具有控制I型错误。

Shapley values are ubiquitous in interpretable Machine Learning due to their strong theoretical background and efficient implementation in the SHAP library. Computing these values previously induced an exponential cost with respect to the number of input features of an opaque model. Now, with efficient implementations such as Interventional TreeSHAP, this exponential burden is alleviated assuming one is explaining ensembles of decision trees. Although Interventional TreeSHAP has risen in popularity, it still lacks a formal proof of how/why it works. We provide such proof with the aim of not only increasing the transparency of the algorithm but also to encourage further development of these ideas. Notably, our proof for Interventional TreeSHAP is easily adapted to Shapley-Taylor indices and one-hot-encoded features.

Data valuation, especially quantifying data value in algorithmic prediction and decision-making, is a fundamental problem in data trading scenarios. The most widely used method is to define the data Shapley and approximate it by means of the permutation sampling algorithm. To make up for the large estimation variance of the permutation sampling that hinders the development of the data marketplace, we propose a more robust data valuation method using stratified sampling, named variance reduced data Shapley (VRDS for short). We theoretically show how to stratify, how many samples are taken at each stratum, and the sample complexity analysis of VRDS. Finally, the effectiveness of VRDS is illustrated in different types of datasets and data removal applications.

在本文中，引入了传输分配系统灵活性市场，其中系统运营商（SOS）共同采购不同系统的灵活性，以满足他们使用公共市场的需求（平衡和拥堵管理）。然后，这种共同的市场是作为一个合作游戏，旨在识别参与SOS之间联合采购灵活性的成本稳定有效地分配，以激励其合作。然后在数学上证明了这场比赛的核心的非空虚，暗示了游戏的稳定性以及SOS之间的合作自然而然的激励。然后引入了几种成本分配机制，同时表征了它们的数学特性。专注于互连系统的数值结果（由IEEE 14总线传输系统和MATPower 18-Bus，69总线和141母线分布系统组成）展示了系统范围内灵活性采购成本的合作诱导的降低，在各种成本分配方法下识别不同的SOS所承受的不同成本。

随机森林已被广泛用于其提供的所谓重要措施，在输入变量的相关性来预测某一输出全局（每个数据集）级洞察能力。在另一方面，根据沙普利值方法已被引入特征相关的基于树的模型分析细化到本地（每个实例）的水平。在这种情况下，我们首先证明杂质（MDI）变量重要性得分的全球平均减少对应的Shapley值在某些条件下。然后，我们推导出变量相关的本地MDI重要的措施，这与全球MDI衡量一个非常自然的连接，并且可以与局部特征相关的一个新概念。我们进一步联系当地MDI重要性有关与沙普利值和从文献中有关措施的光进行讨论。这些措施是通过实验在几个分类和回归问题的说明。

我们开发了一种新的原则性算法，用于估计培训数据点对深度学习模型的行为的贡献，例如它做出的特定预测。我们的算法估计了AME，该数量量衡量了将数据点添加到训练数据子集中的预期（平均）边际效应，并从给定的分布中采样。当从均匀分布中采样子集时，AME将还原为众所周知的Shapley值。我们的方法受因果推断和随机实验的启发：我们采样了训练数据的不同子集以训练多个子模型，并评估每个子模型的行为。然后，我们使用套索回归来基于子集组成共同估计每个数据点的AME。在稀疏假设（$ k \ ll n $数据点具有较大的AME）下，我们的估计器仅需要$ O（k \ log n）$随机的子模型培训，从而改善了最佳先前的Shapley值估算器。

我们展示了一种新颖的虚构播放动态变种，将经典虚拟游戏与Q学习进行随机游戏，分析其在双球零点随机游戏中的收敛性。我们的动态涉及在对手战略上形成信仰的球员以及他们自己的延续支付（Q-Function），并通过使用估计的延续收益来扮演贪婪的最佳回应。玩家从对对手行动的观察开始更新他们的信仰。学习动态的一个关键属性是，更新Q函数的信念发生在较慢的时间上，而不是对策略的信念的更新。我们在基于模型和无模式的情况下（不了解播放器支付功能和国家过渡概率），对策略的信念会聚到零和随机游戏的固定混合纳什均衡。

我们考虑战略设置，其中几个用户在重复的在线互动中聘用，辅助最小化的代理商代表他们反复发挥“游戏”。我们研究了代理人的重复游戏的动态和平均结果，并将其视为诱导用户之间的元游戏。我们的主要焦点是用户可以在此元游戏中从“操纵”他们自己的代理商中可以受益于他们自己的代理商。我们正式定义了普通游戏的这种“用户代理元荟萃游戏”模型，讨论了自动化代理动态的不同概念下的属性，并分析了2x2游戏中用户的均衡，其中动态收敛到a单均衡。

Explaining machine learning models is an important and increasingly popular area of research interest. The Shapley value from game theory has been proposed as a prime approach to compute feature importance towards model predictions on images, text, tabular data, and recently graph neural networks (GNNs) on graphs. In this work, we revisit the appropriateness of the Shapley value for GNN explanation, where the task is to identify the most important subgraph and constituent nodes for GNN predictions. We claim that the Shapley value is a non-ideal choice for graph data because it is by definition not structure-aware. We propose a Graph Structure-aware eXplanation (GStarX) method to leverage the critical graph structure information to improve the explanation. Specifically, we define a scoring function based on a new structure-aware value from the cooperative game theory proposed by Hamiache and Navarro (HN). When used to score node importance, the HN value utilizes graph structures to attribute cooperation surplus between neighbor nodes, resembling message passing in GNNs, so that node importance scores reflect not only the node feature importance, but also the node structural roles. We demonstrate that GStarX produces qualitatively more intuitive explanations, and quantitatively improves explanation fidelity over strong baselines on chemical graph property prediction and text graph sentiment classification.

沙普利价值是衡量单个特征影响的流行方法。尽管Shapley功能归因是基于游戏理论的Desiderata，但在某些机器学习设置中，其某些约束可能不太自然，从而导致不直觉的模型解释。特别是，Shapley值对所有边际贡献都使用相同的权重 - 即，当给出大量其他功能时，当给出少数其他功能时，它具有相同的重要性。如果较大的功能集比较小的功能集更具信息性，则此属性可能是有问题的。我们的工作对沙普利特征归因的潜在局限性进行了严格的分析。我们通过为较小的影响力特征分配较大的属性来确定Shapley值在数学上是次优的设置。在这一观察结果的驱动下，我们提出了加权图，它概括了沙普利的价值，并了解到直接从数据中关注哪些边际贡献。在几个现实世界数据集上，我们证明，与沙普利值确定的功能相比，加权图确定的有影响力的特征可以更好地概括模型的预测。

尽管自1970年代以来就已经知道，普通付款游戏中的全球最佳策略概况是纳什均衡，但全球最优性是严格的要求，它限制了结果的适用性。在这项工作中，我们表明任何本地最佳的对称策略概况也是（全局）NASH平衡。此外，我们证明了这一结果对通用收益和本地最佳的扰动是可靠的。应用于机器学习，我们的结果为任何梯度方法提供了全球保证，该方法在对称策略空间中找到了局部最佳。尽管该结果表明单方面偏差的稳定性，但我们仍然确定了广泛的游戏类别，这些游戏混合了当地的最佳选择，在不对称的偏差下是不稳定的。我们通过在一系列对称游戏中运行学习算法来分析不稳定性的普遍性，并通过讨论结果对多代理RL，合作逆RL和分散的POMDP的适用性来得出结论。

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值的功能归因在解释机器学习模型中很受欢迎。但是，从理论和计算的角度来看，它们的估计是复杂的。我们将这种复杂性分解为两个因素：（1）〜删除特征信息的方法，以及（2）〜可拖动估计策略。这两个因素提供了一种天然镜头，我们可以更好地理解和比较24种不同的算法。基于各种特征删除方法，我们描述了多种类型的Shapley值特征属性和计算每个类型的方法。然后，基于可进行的估计策略，我们表征了两个不同的方法家族：模型 - 不合时宜的和模型特定的近似值。对于模型 - 不合稳定的近似值，我们基准了广泛的估计方法，并将其与Shapley值的替代性但等效的特征联系起来。对于特定于模型的近似值，我们阐明了对每种方法的线性，树和深模型的障碍至关重要的假设。最后，我们确定了文献中的差距以及有希望的未来研究方向。

Cheung和Piliouras（2020）最近表明，乘法权重更新方法的两个变体 - OMWU和MWU-显示的相反的收敛性属性取决于游戏是零和合作的。受这项工作的启发以及有关学习以优化单个功能的最新文献，我们引入了一个新的框架，用于学习在游戏中与NASH Eqeilibria的最后近期融合，在这种情况下，更新规则的系数（学习率）沿着轨迹学习了，这是由增强力学学习的以游戏性质为条件的学习策略：\ textit {游戏签名}。我们使用两人游戏的新分解构建后者，分成对应于交换性投影操作员的八个组件，从而概括和统一文献中研究的最新游戏概念。当学习系数时，我们比较了各种更新规则的性能，并表明RL策略能够利用各种游戏类型的游戏签名。在此过程中，我们介绍了CMWU，这是一种将共识优化扩展到受约束案例的新算法，对零和bimatrix游戏具有本地收敛保证，并证明它在具有恒定系数和跨系数的零和零游戏上都具有竞争性能学习系数时的频谱。

This paper proposes a novel approach to explain the predictions made by data-driven methods. Since such predictions rely heavily on the data used for training, explanations that convey information about how the training data affects the predictions are useful. The paper proposes a novel approach to quantify how different data-clusters of the training data affect a prediction. The quantification is based on Shapley values, a concept which originates from coalitional game theory, developed to fairly distribute the payout among a set of cooperating players. A player's Shapley value is a measure of that player's contribution. Shapley values are often used to quantify feature importance, ie. how features affect a prediction. This paper extends this to cluster importance, letting clusters of the training data act as players in a game where the predictions are the payouts. The novel methodology proposed in this paper lets us explore and investigate how different clusters of the training data affect the predictions made by any black-box model, allowing new aspects of the reasoning and inner workings of a prediction model to be conveyed to the users. The methodology is fundamentally different from existing explanation methods, providing insight which would not be available otherwise, and should complement existing explanation methods, including explanations based on feature importance.