合作博弈论

合作博弈论

合作博弈论是博弈论中的一种理论，又称正和博弈。是指一些参与者以形成联盟、互相合作的方式所进行的博弈。这样一来博弈活动就变成了不同集团之间的对抗。 ## 定义

合作博弈论（英语：cooperative game theory）是博弈论中的一种理论，又称正和博弈。是指一些参与者以形成联盟、互相合作的方式所进行的博弈。这样一来博弈活动就变成了不同集团之间的对抗。

在合作博弈中，参与者未必会做出合作行为，会有一个来自外部的机构用不同方式(例如合约)惩罚非合作者。合作博弈的相反是非合作博弈，指的是参与者不可能形成联盟或任何合作机制都必须为自我履约契约（例如，透过置信威胁的方式）。

合作博弈通常是借由分析合作博弈的理论框架而得，试图想要预测会如何形成合作联盟、如何采取联合的行动以及合作所导致的成果。合作博弈和传统非合作博弈的研究方向相反，非合作博弈试图预测的是个人在博弈中的行动与成果，并分析纳什方程式。

概念

  • 合作： 玩家可以通过协商、协议或结成联盟（coalition）来实现比单独行动更大的收益。合作博弈论研究这些联盟的形成和稳定性。
  • 特征函数： 表示每个联盟能够获得的总收益。若玩家集合为 N ，联盟 S ⊆ N 的收益用 v(S) 表示，其中 v 是特征函数。
  • 可转移效用（Transferable Utility, TU）： 假设收益可以在玩家之间自由分配。若收益不可转移，则称为非可转移效用博弈（Non-Transferable Utility, NTU）。

分析的问题

  1. 收益分配： 核心问题是如何在联盟内部公平分配收益。主要的分配方案包括： • Shapley值（Shapley Value）：基于每个玩家对不同联盟的边际贡献，计算出公平的收益分配。 • 核（Core）：所有联盟都无力通过自我行动获得更大收益的分配方案集合，反映稳定性。 • 凯利指数（Banzhaf Index）：一种考虑玩家影响力的分配方法。
  2. 联盟稳定性：关注联盟的稳定性，即现有分配是否能防止玩家脱离联盟。稳定性通常由核来表征。
  3. 成本分摊： 对于某些共享成本的问题，如基础设施建设或联合采购，合作博弈论提供了一种公平的分摊方式

问题重述

定义：

合作表示为三元组(N, v),其中N是玩家集合，v : 2N → ℝ表示所有可能的合作组合S的收益函数。

超可加性(Superadditive)

对于博弈G = (N, v)若对任何S, T ⊆ N，S ∩ T = ∅，都有v(S∪ > T) ≥ v(S) + v(T),则称该博弈是超可加的。

超可加性描述的是合作比单独行动更有利，大联盟比小联盟收益更高。

需要解决的问题

1.如何构建联盟 2.如何分配收益

  • 对于问题1，我们需要考虑联盟的稳定性，即是否存在一个分配方案，使得所有玩家都不愿意离开联盟。这个问题可以通过核（Core）来解决。
  • 对于问题2，我们需要考虑如何公平地分配收益。这个问题可以通过Shapley值来解决。

shapley Value（夏普利值）

  • 基于每个玩家对合作的边际贡献计算，每个玩家的分配与其对整体收益的贡献成正比。

$$ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!(n - |S| - 1)!}{n!} \cdot [v(S \cup \{i\}) - v(S)] $$

  • v(S) ：子集 S 的收益。
  • |S|：集合 S 中的玩家数量。
  • (|N|−|S|−1)!表示加入玩家 i 后，这期间加入的成员有多少种排列方式。

这个公式的意义是，对于每个玩家 i，我们考虑所有不包含 i 的子集 S，计算 S 和 S ∪ i 的收益差值，然后对所有子集 S 的差值求和，最后乘以一个系数。

举个具体的例子，例如说我们有三个玩家 {A,B,C}，，他们之间合作带来的收益为：

  • {A} = {b} = {c} = 0
  • {A,b} = {A,c} = 3
  • {b,c} = 2
  • {A,b,c} = 6

那么我们可以计算出每个玩家的 Shapley 值，对于玩家 A，我们可以列出总共6种排列组合：

  1. ()->(A)->(A,b)->(A,b,c)
  2. ()->(A)->(A,c)->(A,b,c)
  3. ()->(b)->(A,b)->(A,b,c)
  4. ()->(b)->(b,c)->(A,b,c)
  5. ()->(c)->(A,c)->(A,b,c)
  6. ()->(c)->(b,c)->(A,b,c)

对于每种排列组合，我们可以计算出 A 的边际贡献，然后求和，最后乘以系数，就是 A 的 Shapley 值.即 $\phi_A(v) = \frac{1}{6}[(0)+(0)+(3-0)+(3-0)+(6-2)+(6-2)] = 7/3$

原则：

  • 对称性：如果两个玩家对于合作的边际贡献相同，那么他们的分配应该相同。即ϕi(N, v) = ϕj(N, v)。
  • 零和(dummy player)：如果一个玩家对于合作没有贡献，那么他的分配应该为0。即ϕi(N, v) = 0。
  • 可加性(additivity)：如果博弈分为两部分分别博弈，那么每个玩家的分配应该是两个博弈的分配之和。即ϕi(N, v1 + v2) = ϕi(N, v1) + ϕi(N, v2)。可加性实际上是在说若进行两项互不影响的博弈，则它们的分配也应当互不影响。

满足三条原则的合作博弈，shaapley value 是唯一的。

核（Core）

定义

博弈G = (N, v)的核是指一个分配方案，使得所有玩家都不愿意离开联盟。即存在一个分配向量x，使得forallS ⊆ N, ∑i ∈ Sxi ≥ v(S)。则称x是核心分配。

核心分配的意义是，如果一个分配方案是核心分配，那么所有玩家都不愿意离开联盟，因为他们无法通过自己的行动获得更多的收益。这个概念有点类似于纳什均衡，只不过核心分配是在合作博弈中，而纳什均衡是在非合作博弈中。

那么需要考虑几个问题：

  • 核心分配是否存在？
  • 核心分配是否唯一？
  • shaapley value 和核心分配的关系？即沙普利值是否一定在核中？

例子，对于三个玩家 {A,B,C}，假设分配向量为[xA, xB, xC]是分配给他们的收益，则需要满足分配收益之和为联盟的收益，即xA + xB + xC = v(N)，同时对于任意子集S，xS ≥ v(S)。

即：

xA + xB + xC = 6, xA + xB ≥ 3, xA + xC ≥ 3, xB + xC ≥ 2

我们可以发现，沙普利值(7/3,11/6,11/6)在核中，并且核中还有其他的分配方案，比如(2,2,2)。

shaapley value 和核心分配的关系

沙普利值描述的是公平性，即每个玩家对于合作的边际贡献计算，每个玩家的分配与其对整体收益的贡献成正比。而核心分配描述的是稳定性，即存在一个分配方案，使得所有玩家都不愿意离开联盟。

  • 若沙普利值不在核中，但是我们取了沙普利值作为分配方案，那么此时联盟就不会稳定，这个联盟压根无法形成。
  • 若沙普利值不在核中，我们取了核中的其他分配方案，那么此时联盟是稳定的，但是不公平，因为每个玩家的分配与其对整体收益的贡献不成正比。

若沙普利值在核中，那么此时联盟是稳定的，且公平。