7.2.2 合作博弈的表示和算法
在定义合作博弈的特征函数时，列出每个联盟及其价值是最直接的表示法。但是，随着玩家数量的增加，联盟的数量呈指数级增长，在大多实际应用场景下并不实用。因此，需要一种更简洁的表示形式。但是，一个简单的计数论证表明，没有任何一种语言可以一般性地简洁，即使用poly(n)位，编码 n 个局中人的特征函数。
目前比较流行的方法有两种：第一种是组合优化合作博弈：我们可以专注于通过“小型”组合结构定义的博弈子类。虽然这种表示法可能无法普遍地表达（即可能存在无法用这种方式表示的特征函数），但它确保具备简洁性。这种方法在理论计算机科学和运筹学文献中得到了广泛关注。第二种是面向一些有用的合作博弈子类，我们去开发出普遍表达的表示语言，并用这些表示语言对博弈子类进行简洁的描述。在多智能体系统文献中最近提出了几种这类语言。另外，黑箱模型也经常用于特征函数的输出，即允许有一个有效的算法，当给定一个联盟时，其输出是其价值。在本节中，我们主要聚焦第一种组合优化博弈类型，列举几类常见的组合优化博弈问题和相关结果。
7.2.2.1 导出子图博弈（Induced Subgraph Games）
导出子图博弈最早是由邓小铁和 Papadimitriou[17] 提出，主要思 想为：给定一个无向权重图𝒢 = (𝑁, 𝐸)，每一条边(𝑖, 𝑗) 的权重记为𝑤𝑖,𝑗，
并令𝐰 = (𝑤𝑖,𝑗)𝑖,𝑗∈𝑁。一个导出子图博弈𝐺 = (𝒢, 𝐰)基于局中人集合𝑁
和特征函数𝑣，其中𝑣满足对于任意联盟𝐶 ⊆ 𝑁，𝑣(𝐶)定义为以点集𝐶
导出的子图的边权之和，即
𝑣(𝐶) = ∑(𝑖,𝑗)∈𝐸 𝑤𝑖,𝑗。
{𝑖,𝑗}⊆𝐶
显然，诱导子图博弈的表示就是简洁的，因为我们只要编码边权重，所需的位数是 n = |N|的多项式，即使用邻接矩阵来表示图仅需要
2
2
𝑛2个元素。当所有边权均为非负数时，诱导子图博弈不仅是单调的，而且是凸的，因此保证具有非空核心。邓小铁和 Papadimitriou[17] 设 计了一个基于网络流的有效算法，去判定任意一个结果是否在核心内。相比之下，如果权重可以为负数，则确定核心是否为空是 NP 完全问 题，而检查特定结果是否在核心中是 co-NP 完全问题[17] 。此外，Greco 等人[18] 最近表明，检查一个结果是否在核中是Δ𝑝-完全问题，而检查 一个结果是否在谈判集中是𝛱𝑝-完全问题。邓小铁和 Papadimitriou[17] 表明，导出子图博弈可以使用高效的算法计算 Shapley 值。
7.2.2.2 网络流博弈（Network Flow Games）
在网络流博弈[19] [20] 中，局中人是起点为 s 和终点为 t 的网络中的边，即边集𝐸。每个边（局中人）𝑒 ∈ 𝐸都具有一个正整数容量𝑐𝑒，表示它可以承载多少流量。联盟𝐶的价值𝑣(𝐶)是仅使用𝐶中的边从 s 到 t 可以发送的最大流量。Granot 和 Granot[21] 研究了该类博弈的几个与稳定性相关的解概念。随后，邓小铁等人[22] 表明，在单位容量的情况下，可以有效地计算网络流博弈的核心，但在一般情况下是困难的。
Bachrach 和 Rosenschein[23] 引入网络流博弈的一个变种称为阈值网络流博弈，其目的是从起点 s 发送至少 k 个单位到终点 t：如果联盟可以承载大小为 k 的 s-t 流，则其价值为 1，否则为 0。随后由 Aziz 等人[24] 和 Resnick 等人[25] 进行了研究。Bachrach 等人[23] 表明，在阈值网络流博弈中计算 Banzhaf 指数[8] 是#P-完全的。事实上，
甚至判定一个玩家是否是无贡献者，也是计算困难的。但是，Bachrach等人[23] 给出了在一些特殊的图类下，可以有效地计算 Banzhaf 指数。
网络流博弈的另一个特例是指派博弈[26] 。在指派博弈中，局中人是加权二分图的顶点。每个联盟的价值是其最大权匹配的大小。相比于网络流博弈，指派博弈具有额外的结构，使其更易处理。Granot和 Granot[21] 研究了指派博弈的稳定性，并展示了核心、核和核仁的关系；后来他们的结果被用于设计一个多项式时间算法来计算分配博弈中的核仁[27] 。匹配博弈[28] 是指派博弈的一种推广，其中图不需要是二分图。Kern 和 Paulusma[29] 研究了这些博弈中核心、最小核心和核仁的计算复杂性。
7.2.2.3 最小费用支撑树博弈（Minimum Cost Spanning Tree Games）
到目前为止考虑的所有博弈都是盈利博弈，即博弈中每个联盟的 价值都是正的，但最小费用支撑树博弈[30] 不同于所有其他博弈，因 为它们是费用分摊博弈而不是盈利博弈，即每个联盟的价值是非正的。详细地，一个最小费用支撑树博弈由局中人集合𝑁、一个供应商 s、 一个完全权重图𝒢 = (𝑁 ∪ {𝑠}, 𝐸)和费用𝑐𝑖,𝑗 组成。一个联盟𝐶的价值
𝑣(𝐶)为该联盟成员和 s 组成的点集形成的最小支撑树的花费。不难发
现，最小费用支撑树博弈的核心非空[31] 。然而，Faigle 等人[32] -[33]表明，判定给定结果是否属于核心，并计算最小核心和核仁的问题是 NP 难的。