博弈论之合作博弈

Jan 6, 2021 · 博弈论  ·
分享到:

博弈论之合作博弈

合作博弈的一般表示形式

在\(n\)人博弈中，参与人的集合用\(I=\{1, 2,...,n\}\)表示，\(I\)的任意子集\(S\)称为一个联盟。

下面给出\(n\)人博弈的特征函数式：

设有\(n\)个人参与人的集合\(I=\{1, 2,...,n\}\)，对任一子集\(S\subseteq I\)，定义一个集合到实数的映射（集合函数）\(V(S)\)满足条件：

  1. \(V(\varnothing)=0\)
  2. 当\(S_1\cap S_2=\varnothing,S_1\subset I, S_2 \subset I\)时，\(V(S_1\cup S_2)≥V(S_1)+V(S_2)\)（称为超可加性，在经济学上称之为协同效应）

我们把\([I,V]\)称为一个\(n\)人合作博弈，称\(V(S)\)为这个\(n\)人合作博弈的特征函数，其中\(S\)是\(I\)的任意子集（联盟），\(V(S)\)描述了联盟的效益。特征函数式对\(n\)人合作博弈的每一种可能联盟都给出了相应的联盟收益，也就是给出了一种集合函数。

大联盟博弈

参与博弈的\(n\)个人形成一个合作联盟，称此联盟对应的博弈为n人大联盟合作博弈。\(n\)人大联盟合作博弈的解是指对大结盟所获利益\(V (I)\)的一个分配方案。即大联盟主要研究分配方案（前提是允许局中人之间转移支付）。

若用\(\varphi_i(V(I)),i\in I\)表示参与人\(i\)从\(n\)人大联盟合作博弈中获得的收益，则\(\varphi_i(V(I))\)至少应该满足：

  1. 个体合理性：\(\varphi_i(V(I))≥V(\{i\}),i\in I\)，即合作至少不比单干差；
  2. 总体合理性：\(\sum\limits_{i\in I}\varphi_i(V(I))=V(I)\)，即将合作博弈\([I,V]\)中获得的收益\(V(I)\)分光。

因此，解决\(n\)人合作博弈问题的任务是如何获得一个合理的分配方案 \[ \varPhi(V(I))=(\varphi_1(V(I)),\varphi_2(V(I)),\dotsb,\varphi_n(V(I))) \]

Shapley值

如果说纳什均衡是非合作博弈中的核心概念，那么 Shapley 值是合作博弈中的最重要的概念，Shapley 值是合作性博弈的一种解。

1953年，美国运筹学家罗伊德·夏普利（Lloyd S. Shapley）采用逻辑建模方法归纳出了三条合理分配原则，即在\(n\)人合作博弈\([I,V]\)中，参与人\(i\)从\(n\)人大联盟博弈所获得的收益\(\varphi_i(V)\)应当满足的基本性质（用公理形式表示），进而证明满足这些基本性质的合作博弈解是惟一存在的，从而妥善地解决了某类合作博弈的合理分配问题。

这三条分配原则是：

  1. 对称性原则。每个参与人获得的分配与他在集合\(I=\{1,2,\dotsb,n\}\)中的排列位置无关。
  2. 有效性原则。若参与人\(i\)对他所参加的任一合作都无贡献,则给他的分配应为0。数学表达式为：任意\(i\in S\)，若\(V(S)=V(S\setminus \{i\})\)，则\(\varphi_i(V)=0\)。完全分配：\(\sum\limits_{i\in I}\varphi_i(V)=V(I)\)
  3. 可加性原则。对\(I\)上任意两个特征函数\(U\)与\(V\)，\(\varPhi(U+V)=\varPhi(U)+\varPhi(V)\)。可加性原则表明：\(n\)个人同时进行两项互不影响的合作，则两项合作的分配也应互不影响，每人的分配额是两项合作单独进行时应分配数的和。

满足上述三条分配原则的\(\varphi_i(V),i\in I\),称为Shapley值。夏普利不仅证明了 Shapley 值的存在惟一性，而且给出了Shapley值的计算公式。下面给出这个重要结果：

对任一\(n\)人合作博弈\([I,V]\)，Shapley值是惟一存在的，且 \[ \varphi_i(V)=\sum_{S \subseteq I\setminus \{i\}}W(|S|) [V(S)\cup \{i\}-V(S)],i=1,2,\dotsb,n \] 其中，\(W(|S|)=\frac{|S|!(n-|S|-1)!}{n!},|S|\)为集合\(S\)的基数。

Shapley公式解释：首先Shapley值是用来在联盟内部进行收益公平分配的，不考虑联盟以外的成员。分配原则本质上是对共同收益的加权平均。

先看第二项\(V(S)\cup \{i\}-V(S)\)这个说的是有没有用户\(i\)对联盟\(S\)收益（特征函数）的影响，即\(i\)在加入联盟\(S\)的边际收益或者说\(i\)对联盟\(S\cup \{i\}\)的贡献值。而系数\(W(|S|)\)是指联盟\(S\)的加权平均系数，以联盟人数\(|S|\)为分组标准，分为组内平均和组间平均。组建平均很好理解，依照联盟的人数，可以分为\(0\rightarrow N-1\)共\(N\)个组，因此平均为\(\frac{1}{N}\)。而从\(N-1\)个剩余成员中挑选人数为\(|S|\)的联盟共有\(\frac{(n-1)!}{|S|!(n-|S|-1)!}\)个，我们简单用其倒数来平均\(i\)的贡献值，组内组间平均综合即为\(W(|S|)\)。

班扎夫权力系数

称为关键参与者的次数紧性归一化即为班扎夫权力指数。

存在小团体的合作博弈

在参与人多于两个的情况下，就可能出现部分参与人联合起来追求小团体利益的行为，但其前提条件是参与人在小团体中得到的利益大或等于在大联盟中得到的利益，即存在子集\(S=\{i_1,i_2,\dotsb,i_k\}\subset I\)，相应的总收益为\(V(S)\)，分配方案 \[ \varPhi(V(S))=(\varphi_{i_1}(V(S)),\varphi_{i_2}(V(S)),\dotsb,\varphi_{i_n}(V(S))) \] 满足 \[ \begin{aligned} &\varphi_{i_1}(V(S))≥\varphi_{i_1}(V(I))\\ &\varphi_{i_2}(V(S))≥\varphi_{i_2}(V(I))\\ &\dots\dots\\ &\varphi_{i_k}(V(S))≥\varphi_{i_k}(V(I))\\ \end{aligned} \] 且其中至少有一个严格不等式成立。

为使记号简便，我们将\(V(\{i\})\)简记为\(V(i)\)，将\(n\)人合作博弈问题的分配方案简记为\(\varPhi(V)=(\varphi_1(V),\varphi_2(V),\dotsb,\varphi_n(V))\)。

核

在一个合作博弈中，满足帕累托标准（除非损人才能利己）的联盟结构称为博弈的一个有效解，所有有效解的集合称为该博弈的解集。

但是解集中的有效解并不都是稳定的。通俗的来说，如果在某一联盟\(V(S)\)中，一部分成员通过组成另一个联盟\(V(S')\)，并且\(S'\)的所有成员按照分配规则\(Φ(V(S'))\)（比如shapley值）能够比在按原来联盟中分配\(Φ(V(S))\)获得更高的收益，那么这些原来联盟的成员就有理由背离联盟\(S\)，使得这个联盟不稳定，从而这个有效解也是不稳定的。

如果一个联盟结构能使得所有参与者都不能从联盟重组中获益，这个联盟结构就是这个合作博弈的核。也就是说在这种联盟结构中所有的参与者都没有改变目前结构的动力。

形式化定义：对于合作博弈中\((I,V)\)的核，核内的成员收益应当且仅当满足 \[ \forall S\subseteq I, \sum_{i\in S} x_i\geq V(S) \]

核不一定存在，如果核存在，则其一定是博弈的有效解。

凸博弈

定义：对于一个博弈\(G=(I,V)\)如果是凸博弈，那么对于\(\forall S,T\subset N,V(S\cup T)\geq V(S)+V(T)-V(S\cap T)\)

凸博弈的要求比超可加性更强。

定理：每一个凸博弈都有非空的核，并且Shapley值在核中。