合作博弈理论是(微观)经济学的一个分支,研究在战略环境中可能存在有约束力的协议的自利代理的行为。在这本书中,我们的目标是介绍合作博弈理论的计算方面的研究概况。我们首先正式定义特征函数形式的可转移效用游戏,并介绍一些关键的解决概念,如核心和沙普利值。然后我们讨论从计算的角度考虑这些游戏时出现的两个主要问题:确定游戏的紧凑表示,以及与之密切相关的高效计算游戏解决概念的问题。我们回顾了文献中提出的几种合作游戏的形式化方法,包括例如在网络上定义的合作游戏,以及MC-net和技能游戏等通用紧凑表示方案。作为一个详细的案例研究,我们考虑加权投票游戏:一类在实际应用中广泛使用且具有重要意义的合作游戏,这类游戏本质上具有自然的紧凑表示。我们研究这类游戏的解决概念的复杂性及其推广。我们简要讨论非可转移效用的游戏和分区函数游戏。接着,我们概述了用于识别福利最大化的联盟结构的算法,以及理性代理用于形成联盟(即使在不确定性情况下)的方法,包括讨价还价算法。我们最后考虑一些正在发展的主题、应用和未来的研究方向。
在过去的十年中,人们对博弈论和计算机科学交叉领域的问题的兴趣呈现出巨大的增长。这一现象在一定程度上是由互联网这一巨头推动的,它在20世纪90年代末惊人地进入公众意识。一方面,互联网可以纯粹从计算的角度来理解:它是一个庞大的、高度动态的计算节点网络,通过物理和无线连接使用精心定义的协议和程序交换数据。然而,纯粹从计算的角度看互联网肯定会遗漏对其理解至关重要的方面。互联网上的实体不是利他的或者漠不关心的。在互联网上做出决策和采取行动的实体是自利的。它们有偏好、目标和欲望,一般来说,它们会尽力采取行动来实现自己的偏好、目标和欲望。传统的计算机科学分析对互联网的这些经济方面没有任何发言权。这一观察激励研究人员将经济学技术,特别是微观经济学分支博弈论的技术,应用于网络计算机系统(如互联网)的分析。这个领域的研究主要来自两个社区:多代理系统社区(起源于人工智能的研究)[240, 261],和算法博弈论社区[195](起源于理论计算机科学的研究)。这两个计算机科学社区采用了博弈论的技术,并在理解博弈论技术如何在计算环境中有用地应用,以及如何将计算技术应用于博弈论问题方面取得了相当大的进展。在本书中,我们的目标是向读者介绍合作博弈论的计算方面的研究。这是一个重要且非常活跃的当代研究领域,对多代理系统和算法博弈论社区都很感兴趣。简单地说,合作博弈论(与非合作博弈论相对)关注的是代理人可以同意彼此合作的环境,例如通过签署相互约束的合同。约束性协议可能使代理人能够实施在非合作博弈论中不可能被考虑的解决方案。