数学博弈论

然而，从个人用户的角度来看，贪婪的成本分配方案可能显得“不公平”（见例7.5）。博弈论者对“最佳”网络成本分配方案存在分歧98 7。合作游戏性爱。7.5. 考虑一个用户集N={p，p}，连接成本系数c=100，c=101，c=2。贪婪算法构造了凝聚链 = s S={p} S={p.p}=Nand向用户和c（S）收费c（S）=100- c（S）=2对用户p。SOP将承担约98%的总成本c（N）=102.1.6。投票游戏。例如，有一组N个选民（不一定相等）的投票权。用我能投的票数来表示。给定阈值w，关联的投票游戏具有特征函数V（S）=1如果XI∈Swi≥ w0否则。在投票环境中，v（S）=1的解释是，联盟拥有使某项拟议措施获得通过的投票权。请注意，在v（S）=0的情况下，投票人i的值为miv（S）=v（S）∪（一）- v（S）=1有权通过加入S来改变投票。一般问题具有高度的政治重要性：o如何（或应该）在投票环境中评估选民i的总体投票权？备注7。4.一个流行的个人投票权指数是BANZHAFpower指数（见下文第3节）。然而，也有其他评估方法也有其优点。与净工作成本分配一样，抽象数学无法决定什么是“最佳”方法。2.Core在我们当前的讨论中指出了这一特点：o为了避免技术问题，我们假定本节中的所有合作游戏都是零标准化的。（零规范化）合作博弈（N，v）的核心是集合核（v）={x∈ RN | x（N）=v（N），x（S）≥ 五(S)s N} ，也称为阈值游戏2。核心99带有符号und erst和ing x（S）=Pi∈Sxs。

数学上讲，核（v）是欧几里德空间RN中有限个线性不等式的解集。在她手上的博弈论解释中，向量x∈ 核心（v）是指将个人价值观分配给我的球员∈ N，使得值v（N）完全分布，并且每个联盟S至少接收到适当的值v（S）。例如，上面的不平等（40）体现了供应商的市场价值w*s（见等式（38））是线性生产博弈中核心向量的系数。成本博弈（N，c）的核心被类似地定义为：核心*（c） ={x∈ RN | x（N）=c（N），x（S）≤ 丙(S)s N} 。十、∈ 果心*（c） 在我的球员中分配成本c（N）∈ 因此，N ocalition S支付的费用比其适当的成本c（S）要多。例7。6.展示（零规范化）合作博弈（N，v）及其对偶（N，v）*):核心（v）*) = 果心*（v） 。例7.7。给出一个合作博弈（N，v）的例子，其核心（v）=.遗憾的是，正如Ex.7.7所示，对于合作游戏中单个p层的“公平”利润（或成本）分配，核心不是一个普遍适用的概念，因为它可能是空的。因此，更进一步的价值分配概念很有意思。第3节将提供此类概念的示例。现在，让我们继续研究核心问题。2.1. MONGE算法。我们考虑了一个带n个PL埃尔斯的合作博弈（n，v）和联盟的集合n。给定一个参数向量c∈ n和一个排列π=ii。在N元素中，MONGEalgorithm构造了一个原始MONGE向量∈ r与对偶MONGE向量yπ∈ RNA如下：（M）集Sπ= 对于k=1，2，…，Sπk={i，…，ik}，n、 （M）设置xπik=v（Sπk）- v（Sπk）-1） 对于k=1，2，n、 （M）设置yπSn=cin和yπSl= 词l-词l+1用于l = 1, 2, . . . , N- 1.否则设置yπS=0。G.蒙格（1746-1818）100 7。

合作博弈不难看出，MONGE向量xπ和yπ满足恒等式ymπ（c）=Xi∈Ncixπi=XS∈N的不同排列π和ψ，当然，可能会产生不同的mπ（c）和mψ（c）。重要的是以下观察。引理7.1。设π=ii。inandψ=jj。N的两种安排≥ 词≥ . . . ≥ 辛德和cj≥ cj≥ . . . ≥ cjn。n nπ（c）=XS∈Nv（S）yπS=XS∈Nv（S）yψS=mψ（c）。证据请注意，cil= 词l+例如，1意味着yπSl= 所以我们可以假设c的分量有不同的值。但π=ψ成立，这使得这个说法变得微不足道。2.1.1. MONGE分机。Lemm a.7.1说有一个定义良好的实值函数C7→ [v] （c），其中[v]（c）=mπ（c），如果π=ii。ins。t、 词≥ 词≥ . . . ≥ 辛。函数[V]是特征函数V的Mange扩展，为了证明术语“扩展”，考虑S上的CaliTI。 N及其（0，1）关联向量c（S），在情况i中分量c（S）i=1∈ N元素的适当排列首先列出所有1个组分，然后列出所有0个组分：π=i。ik。ins。t、 c（S）i。c（S）ik…c（S）in=1。10 . . . 因此，对于t6=S，我们有yπS=1和yπT=0，对于所有的S，我们得出[v]（c（S））=v（S） N.备注7.5（CHOQUET和LOV\'ASZ）。将蒙古人的思想应用于不增加价值的安排≤ . . . ≤ 非负函数的fn:N→ R+，一个人到达CHOQUET积分ZFDV=nXk=1fk（v（Ak）- v（Ak+1）），其中Ak={k，k+1，…，n}和An+1=.参见附录2第5节。核心是地图f 7→Rfdv是函数v:N的所谓LOV\'ASZ扩展→ R.当然，mutatis mu tandis是从MONGE到CHOQUET和LOV\'ASZ的所有结构属性。2.1.2. 线性规划方面。

由于核（v）被定义为一组有限个不等式（和一个等式）的解集，因此研究以核为可行解集的线性规划是很自然的。考虑线性规划（41）MIX∈RNcTx s.t.x（N）=v（N）和x（s）≥ v（S）如果s6=N，则其对偶（42）maxy∈RNvTy s.t.XS艾斯≤ 词我∈ N和Y≥ 如果S 6=N，则为0。在ci的情况下观察≥ . . . . . . ≥ 从yπS出发，证明了相对于c的对偶MONGE向量yπ是一个可行解≥ 0满足所有S 6=N。因此，如果核心（v）6=, 两个线性规划都有最优解。线性规划对偶进一步显示（43）~v（c）=minx∈核心（v）cTx≥ vTyπ=[v]（c）。定理7.2。~v=[v]适用于对策（N，v）当且仅当所有原始MONGE xπ向量位于核（v）中。证据假设ci≥ . . . ≥ cinandπ=i。在里面如果xπ∈ 核（v），则Xπ是线性程序（41）的一个可行解。由于对偶MONGEvector yπ对（42）是可行的，我们发现xπ≥ 五（c）≥ [v] （v）=cTxπ，因此v（c）=[v]（c）。相反地，~v=[v]意味着对偶MONGE向量保证产生（42）的最优解。所以考虑阿纳尔的安排。jnn与参数向量c∈ RN的组件SCJK=n+1-k代表k=1，n、 对偶向量yψ在集Sk上有严格的正分量yψSk=1>0。根据o p时间解的KKT条件，an102 7。合作对策最优解x*∈ 相应线性规划（41）的核（v）必须满足等式X*（Sk）=Xi∈Skx*i=v（Sk）表示k=1，n、 也就是说x*正是原始MONGE向量xπ，因此，xπ∈ 核心（五）成立。2.2. 康涅狄格州。

我们把一个特征函数称为v:2N→ R凹如果v是由凹函数t对联盟S的（0，1）-关联向量c（S）的限制而产生的，即如果存在凹函数f:RN→ R使得v（S）=f（c（S））适用于所有S 因此，如果v是凹的，那么合作对策Γ=（N，v）是凹的。我们将不研究一般的conacave合作对策，而是关注一类特别重要的凹对策，它通过定理7.2与MONGE算法密切相关。建议7.1。如果对策（N，v）的所有MONGE向量都位于中心（v），则（N，v）是凹的。证据根据Theorem 7.2，这个命题的假设是，对于所有的c，v（c）=[v]（c）∈ 注册护士。因此，有必要证明v是一个凹函数。显然，对于λ>0的所有标量，λλc=λvhc）都成立，也就是说，v是正齐次的。现在考虑任意参数向量C，D∈ RNand x∈ 磁芯（v），例如：v（c+d）=（c+d）Tx.Th en＠v（c+d）=cTx+dTx≥ ~v（c）+~v（d），其显示为凹形。备注7.6。命题7.1）的逆命题是不成立的：存在一个重凹博弈，其核心不包括所有原始MONGE向量。2.核心部分是一个术语上的谨慎。博弈论文献经常将术语“凸合作博弈”应用于在核（v）中包含所有原始MONGE向量的博弈（N，v）。然而，在我们的术语中，这样的曲面不是凸的，而是凹的。为了避免术语上的混淆，人们可能更愿意将其称为超模博弈（参见下一节2.3中的定理7.3）。超常。将MONGEalgorithm与凹性联系起来的核心概念是超模性：定理7.3。

对于合作对策（N，v），下列陈述是等价的：（I）所有的MONGE向量xπ∈ Rn位于核心（v）。（二） v是超模的，即满足不等式v（s∩T）+v（S）∪ （T）≥ v（S）+v（T）代表所有S，T N.证据。假设（I），N的元素按I的顺序排列。因苏奇∩ T={i，…，ik}，S={i，…，il}, s∪T={i，…，im}。通过MONGE算法的定义，xπ然后满足xπ（S∩ T=v（S）∩T），xπ（S）=v（S），xπ（S∪ T=v（S）∪ T）。此外，xπ（T）≥ 如果xπ，v（T）成立∈ 核心（五）。所以我们推导出了超模不等式v（S）∩T）+v（S）∪ T）=xπ（S）∩ T）+xπ（S）∪ T）=xπ（S）+xπ（T）≥ v（S）+v（T）。相反，假设v不是超模。我们将展示一个MONGEvector xπ，它不是核心（v）的成员。让我们，T N是这样的亚视∩T）+v（S）∪ T）<v（S）+v（T）为真，N的元素按π=i的顺序排列。因苏奇∩ T={i，…，ik}，S={i，…，im}，S∪T={i，…，il}.104 7. 因此，MONGE向量xπ满足v（S）+v（T）>v（S）∩T）+v（S）∪T）=xπ（S）∩ T）+xπ（S）∪ T=xπ（S）+xπ（T）=v（S）+xπ（T），因此v（T）>xπ（T），表示xπ/∈ 核心（五）。例7.8。前面的证明使用了一个事实，即任何向量x∈ 满足性测试模块等式∩ T）+x（S∪ T）=x（S）+x（T）表示所有S，T N，在不理解x（S）=Pi的情况下∈Sxi。2.4. 子模块化。一个特征函数v被称为submodu larif不等式v（S∩T）+v（S）∪ （T）≤ v（S）+v（T）适用于所有S，T N.ex7.9。证明z-ero标准化对策（N，v）的等价性：（1）v是超模的。（2） 五*是子模。（3） w=-v是次模。鉴于平等的核心（c*) = 果心*（c） （例7.6），我们发现Monge算法也在核心构造向量*（c） 具有子模特征函数的合作代价对策（N，c）的注7.7。

注意定理7.3的最后一点，它在子模性语言中说：（n，c）是一个子模代价博弈当且仅当所有的向量xπ位于核中*（c） 。网络连接游戏通常不是子模块。然而，第1节中讨论的特殊成本分配向量。5 d oes位于核心*（c） ，正如这位雄心勃勃的读者所展示的。备注7.8。由于MONGE算法，子模函数和超模函数在离散优化领域发挥着重要作用。事实上，离散优化的许多结果在CFC中有直接的解释。S.FUJISHIGE（2005），《子模函数与优化》，第二版，离散数学年鉴583。合作博弈理论。相反，合作博弈模型为离散优化问题的结构提供了概念上的视角。备注7.9（贪婪算法）。Monge算法应用于具有核心类型约束的线性规划，也称为离散优化中的贪婪算法。3.价值而非边际价值球员i决定加入resp的iv（S）。从直觉上看，要想离开联盟S，还不太清楚应该如何评估ofi的整体实力。从数学的角度来看，有很多可能做到这一点。一般来说，我们理解所有TU对策（N，v）a函数Φ：RN类的b y a值→ 与每个特征函数v相关联的向量Φ（v）∈ 注册护士。给定Φ，数字Φi（v）是对Φi强度的评估∈ 根据评估概念Φ3.1，游戏中的N（N，v）。线性值。如果Φ是一个线性算子，也就是说，如果对所有的对策v，w和标量λ都有一个值Φ，那么Φ就是线性的∈ R、 等式Φ（λv+w）=λΦ（v）+Φ（w）。换句话说：如果每个分量函数Φ是向量空间RN上的线性函数，那么Φ是线性的。从前任召回。

7.2一致性对策构成RN的基础，这意味着每一个对策v都可以独立地表示为非动物性对策的线性组合。因此，一个线性值Φ完全由分配给一致性对策的值决定。当然，对于任何其他基础来说也是如此。的确，如果v，vk∈ G（N）是任意对策，λ，λkarbitraryreal标量，Φ的线性产生Φ（λv+…+λkvk）=λΦ（v）+…+λkΦ（vk）。我们给出了线性值的两个典型例子。106 7. 合作游戏SHAPLEY的价值。考虑到一致的gamebδT与conalition T的关系∈ 其中bδT（S）=1如果是 否则。在这种情况下，评估球员的实力似乎是合理的∈ N\\T为空，即ΦShj（bδT）=0，且每个参与者的强度为T∈ T的等比例为ΦSht（bδT）=| T |。将Φshv扩展到sensev=XT中的所有博弈v b y线性∈NλtbδT==> ΦSh（v）=XT∈NλTΦSh（bδT）得到一个线性值v7→ ΦSh（v），即所谓的SHAPLEY值。例7.10。显示在（N，v）和它的零规范化（N，v）中的游戏者**) 被赋予相同的形状值。班扎电力指数。BANZHAF功率指数Φbap与SHAPLEY值非常相似，评估功率ΦBs（bδt）=0（如果s∈ N\\t治疗所有t∈ T是平等的。假设t6=, 数学上的差异在于比例因子：ΦBi（bδT）=T|-1对于所有t∈ T与SHAPLEY值一样，BANZHAF幂指数从一致对策线性扩展到所有对策（N，v），从而给出一个线性值v7→ ΦB（v）。正如我们将在第3.2节中看到的，ΦShand和Φbc值之间的差异也可以通过关于联盟形成方式的两种不同概率假设来解释。备注7.10（效率）。如果| T |≥ 1、SHAPLEY值对总金额的影响∈NΦShi（bδT）=1=bδT（N）3。

对N的成员来说，值为1070，因此被认为是有效的。相比之下，wehaveXi∈NΦBi（（bδT）=| T | T|-1<1=bδT（N）如果| T |≥ 2.因此，班扎电力指数并不有效。3.2. Random值。随机值的概念是基于一个假设，即玩家∈ N加入联盟S N\\{i}以一定的概率π作为一个新的成员。i的预期边际值∈ Nthus-isEπi（v）=XSN∈{i}函数Eπ：G（N）→ RNwith components Epii（v）是关联的随机值。请注意，边际值是线性的。事实上，如果u=λv+w，则iu（S）=λ四(S)我为所有我∈ N和S 因此，随机值Eπ也是线性的：（44）Eπ（λv+w）=λEπ（v）+Eπ（w）。备注7.11。线性关系（44）隐含地假设概率π与特定的特征函数v无关。如果π依赖于v，则不再保证Eπ的线性！玻尔兹曼值（将在下文第4节中讨论）是一个随机值，在（44）的意义上不是线性的，因为相关的概率分布取决于特征函数。3.2.1. 板斧的价值。作为一个例子，让我们假设一个玩家i加入了2n中的任何一个-1.托拉斯 N\\{i}具有相等的可能性，即概率πBS=N-1、考虑一致性vt= bδt并观察ivT（S）=0持有ifi/∈ 另一方面，如果我∈ T，然后一个h作为ivT（S）=1<==> T\\{i} 因此，与美国的联盟数量ivT（S）=1等于|{S N\\{i}|T s∪{i} }|=2n-|T|-1.因此我们得出结论e108 7。合作对策（45）EπBi（vT）=XSN\\{i}ivT（S）πBS=n-|T|-1n-1=|T |，这意味着随机值EπBis与BANZHAFpower指数相同。概率方法得到了显式公式（46）ΦBi（v）=EπBi（v）=n-1XSN\\{i}（v（S）∪ （一）- 五(S)(i)∈ N） .3.2.2。边缘向量和SHAPLEY值。

让我们想象一下，N的成员以一定的顺序σ=Ⅱ建立了“大煤系离子”N。因此，他们加入了联盟的行列 = Sσ Sσ。 Sσk . . .  Sσn=nW这里Sσk=Sσk-1.∪ {ik}对于k=1，n、 给定对策（n，v），σ给出了边际向量σ（v）∈ 带组件的RNSik（v）=v（Sσk）- v（Sσk）-1） （k=1，…，n）。注意v7→ σ（v）是G（N）的线性值。我们可以根据概率分布π，从所有N阶的∑Nof集合中选取阶数σ，将该值随机化。然后是期望的边缘向量π（v）=Xσ∈∑Nσ（v）πσ当然也代表G（N）上的一个线性值。例7.11。显示值v7→ π（v）是线性且有效的。（提示：回想一下第1.5节中关于网络连接游戏贪婪算法的讨论）。边缘向量正是第2.13节的原始MONGE向量。值109PR位置7.2。SHAPLEY值是相对于∑N上的均匀概率分布的期望边缘向量，其中所有阶数的可能性相等：ΦSh（v）=N！Xσ∈∑Nσ（v）。（回忆一下组合数学中有n！=|∑n | n的有序排列）证明。由于线性关系，证明一致对策vT=bδT的命题是足够的。在里面∈ ∑Nand elementik∈ N\\T，我们有ik（vT）=0和hencen！Xσ∈∑Nσi（vT）=0表示所有i∈ N\\T。另一方面，统一分配对待所有成员∈ T相等，从而在T:N的成员之间平均有效地分配值vT（N）=1！Xσ∈∑Nσi（vT）=vT（N）|T |=所有i∈ 这正是夏普利的概念。我们可以在最初引入的随机值的框架内解释SHAPLEY值。所以我们假设一个订单σ∈ ∑Nis的选择概率为1/n！考虑一个联盟 N\\{i}。