数学博弈论

n人矩阵博弈的随机化既允许收益均衡，也允许成本均衡。备注6.2。一个随机矩阵对策的均衡是一个纳什均衡。4.交通流量交通网络流量分析的基本模型可追溯到WARDROP。它基于一个图G=（V，E）和一组（有限）节点集V，以及节点之间（有向）边集E，ve-→w、 表示从节点到其他节点的定向连接。模型假设：（W）有N个参与者。我喜欢的球员∈ N想沿着一条从起点到终点的路径旅行，并且有一组路径可供选择。从游戏理论上讲，一个策略性的行动是玩家i∈ N表示路径P的特定选择∈ 圆周率。让我们确定一条路径P∈ π及其关联向量在组件SPE中倒转=如果P通过gh e0，则为1，否则为。玩家的联合出行路径选择产生交通流量x=Xi∈恩智浦∈πλsPP的大小|xs |=XPλsP≤ n、 纳什（1950）：n人博弈中的均衡点，Proc。美国国家科学院36，48-49J。G.WARDROP（1952）：道路交通研究的一些理论方面。土木工程学会1325–3784。交通流87，其中λ表示选择s中路径P的参与者数量。组件x表示选择s导致的e边上的交通量。我们假设交通流x沿e边产生拥堵成本c（xe），从而导致总拥堵成本c（x）=xe∈Ece（xe）穿过所有边缘。

单个玩家i在其选择的路径P:C（P，x）=Xe上有阻塞成本∈Pce（xe）xe。如果我们将流量x与累计成本的潜力Φ（x）=Xe相关联∈ExeXt=1ce（t），我们发现p层i沿路径p in x的阻塞成本等于边际电势：C（p，x）=Xe∈Pce（xe）=Φ（x）- Φ（x）- P）=PΦ（x）- P）。因此，WARDROP交通模型中的玩家在可能的交通流的有限集合X上玩一个n人潜在博弈。十、∈ 如果没有一个玩家我可以通过改变当前路径P来改善其拥挤成本，那么X被认为是一个纳什流∈ Pito在总部使用另一个p∈ 圆周率。换句话说，纳什流就是成本均衡流。由于势函数Φ是在一个有限集上定义的，我们得出结论oWARDROP交通流模型允许纳什流。布雷斯悖论。如果有人假设WARDROP模型中的raf最终将TLE设置为纳什流，即交通流向成本均衡状态发展，那么众所周知的Braessis观察结果是非常直观的：（B）可能发生的情况是，特定连接上的拥堵减少会增加（！）总拥堵成本。作为Bress’s佯谬的一个例子，考虑V＝{s，r，q，t}和e= {（s，r），（s，q），（r，t），（q，t），（r，q）}的网络g=（v，e）。D.布雷斯（1968年）：¨这是一个悖论。N人博弈假设边上的代价函数是CSR（x）=x，csq（x）=4，crt（x）=4，cqt（x）=x，crq=10，并且有四个网络用户，他们选择从起点s到终点t的单独路径，并希望最小化各自的旅行时间。由于拥堵成本高，没有用户会沿着（r，q）行驶。

作为一个序列，纳什流将有两个路径P=（s）的用户→ R→ t） 而另外两个用户则会沿着P=（s）移动→ Q→ t） 。总成本为：C（2P+2P）=2·2+4·2+4·2+2·2=24。如果采取道路改善措施来减少（r，q）toc′rq=0上的拥堵，路径P的用户可以通过切换到路径q=（s）来降低当前成本C（P）=6到C（q）=5→ R→ Q→ t） 。然而，由此产生的交通流会导致更高的总成本：c′（P+Q+2P）=2·2+4·1+3·1+4·2+3·2=25。第七章合作博弈合作博弈中的玩家努力实现一个共同的目标，他们可能会从中受益。从数学上讲，这类博弈是特殊的势博弈，最好在线性代数的背景下进行研究。核心问题是如何适当分配已实现目标的利润。合作博弈的核心是一个重要的分析概念。它提供了一个链接到离散优化理论，尤其是贪婪算法。此外，联盟形成动力学的自然模型与统计物理学中的热力学模型密切相关。因此，例如，在一个潜在的游戏中，温度的概念可以变得精确。虽然前几章的两人博弈中的代理人通常称为Y，但合作博弈的模型指的是一组N=|N |玩家，他们可能会或可能不会积极地朝着一个共同目标前进。一个子集 N个潜在活跃的参与者传统上都被称为联盟。

从数学上讲，有几种方法来看待联盟系统：从集合论的观点来看，我们有第二个联盟系统 N} 。另一方面，一个可以表示子集S∈ N按其发生率x（s）∈ 与协调人一道=1如果我∈ 如果我/∈ S.关联向量x（S）表明了对i的解释∈ N在x（S）i=1时被激活。联盟是活跃玩家的集合。更进一步的解释是我想象的每一个球员∈ N有一个二进制策略集Xi={0，1}，从中选择一个元素。A=x，…，xn）∈ X×···×Xn={0,1}N RN907。合作博弈给出了n个参与者的联合策略决策，我们得到了相应的结果←→ {0，1}N=2N根据向量空间的集合论观点，通过一个合作博弈，我们将只理解一个N人博弈，它包含层集N和状态集X=N或X=2N。1.合作博弈相对于一组N个参与者的可转移效用是一个数量v，其值v（S）取决于活跃参与者的联盟，因此是一个潜在的v:n7→ R.由此产生的强对偶对策Γ=（N，v）代表一个在v.v.上具有特征函数的合作TU对策() 如果没有Nis成员在游戏Γ中活动，则为效用值。通常，（N，v）被假定为零或零化，即有v() = 0.在案例v中() 6=0，我们考虑TU博弈（N，v（0））而不是（N，v），其标准化特征函数值为零SV（0）（S）=v（S）-五().在续集中，我们将集中讨论TU游戏，因此只讨论合作游戏（N，v）。备注7.1（术语）。合作博弈（N，v）的特征函数v通常被称为合作博弈。在离散数学和计算机科学中，函数v:{0，1}n→ Ris也被称为伪布尔函数。

决策论将伪布尔函数称为集合函数。合作博弈的特征函数v可以表示成本效用或利润效用。当然，对数学分析的真实解释取决于假设的是成本模型还是收益模型。通常情况下，莫德林的背景说明了这一点。例如，参见M.GRABISCH（2016）：设置功能、游戏和容量，在De c isio nMaking，Springer-Verlag1。合作TU-GAMES 911.1。图对策的向量空间。识别一个TU博弈（N，v）及其特征值v，我们考虑函数间隔N={v:N→ R} N={S N} 作为N上所有图对策的向量空间，RN与坐标空间RN同构，且维数为dim RN=|N |=2n=dim RN。RNT的2n单位向量对应于所谓的狄拉克函数δS∈ Rn的值为δS（T）=1如果T=S0如果t6=S.集合{δS | S∈ N} 是RN的基础。任何v∈ RNhas代表v=XS∈N=v（S）δS.1.1.1。二元性。保留N作为指数集是有利的，因为可以使用N的集合论结构进行博弈论分析。一个这样的例子是d算子v7→ 五、*在RN上，其中（36）v*（S） =v（N）- v（N\\S）表示所有的 我们说游戏*) 是（N，v）的对偶。为了任何可能的联盟∈ N、 数值v*（N\\S）=v（N）- v（S）是游戏中“大联盟”N对S（N，v）的“盈余”。鸡奸表达了一种平衡*（N\\S）=v（N）适用于所有联盟S.EX.7.1。节目：（1）V7→ 五、*是RN上的线性算子。（2） 双v**= （五）*)*双重v*v的零标准化正好产生v.1.1.2的零标准化。莫比乌斯变换。对于任何v∈ RN，让我们将tsM–OBIUStransform定义为函数^v∈ Rn的值^v（S）=XTSv（T）（S）∈ N） 。A.F.M–OBIUS（1790-1868）92 7。合作博弈^v（S）总结了所有子博弈T的v值 s

从这个意义上说，特奥比乌斯变换是函数空间RN上的一种“离散积分”。例7.2（一致同意游戏）。M¨OBIUS transformbδsofthedirac函数δ称为一致性博弈，其值为bδS（T）=1如果是 T0如果s6 T当联盟T包含S的所有成员时，联盟T具有非零值BδS（T）=1。一致性博弈似乎非常简单，但却是基本的（推论7.1）。合作ga m e理论中的许多概念都是根据它们在单一博弈中的性能进行测试的。显然，莫比乌斯变换是V7→ ^v是一个线性算子。重要的观察涉及到一个逆性质：每一个特征函数v都是一个新确定的其他特征函数w的变换。定理7.1（M¨OBIUS反演）。每v∈ 恩，这里有一个女的∈ 使v=w.证明。回想一下线性代数，它足以证明^z=O意味着z=O，也就是说，M¨OBIUS变换的核只包含零向量O∈ 注册护士。让我们考虑一个任意函数z∈ RNwith transform^z=O.let∈ N是一个凝聚体，在S=:z() = ^z() = 现在，通过归纳，假设z（T）=0适用于所有T∈ N的大小为| T |<|S |。那么结论z（S）=^z（S）-XTSz（T）=0- 0=0遵循并完成证明的归纳步骤。所以z（S）=0对于所有联盟S都是正确的。1.合作图对策93因为M¨OBIUS算子是线性的，所以T heorem 7.1暗示它实际上是RN的自同构，它将基映射到基上。因此，我们特别发现：推论7.1（一致性基础）。RN的一致性对策bδSforma基础，即每个v∈ R输入formv=XS的唯一表示形式∈NλSbδ开关系数λS∈ R.EX.7.3（哈萨尼股息）。

其中v=w，在合作博弈论中，w（S）的值被称为博弈（N，v）中联盟的HARSANYI红利。任何联盟的价值v（S）都是其子联盟的哈桑红利的总和T:v（S）=^w（S）=XT西南（T）。备注7.2。文献中关于逆变换^v 7的术语和术语并不十分清楚→ v代表莫比乌斯的转变。不管怎样，M¨OBIUS变换也是数论和组合数学中一个经典而重要的工具。1.1.3. 势函数和线性泛函。A势f:N→ R、 解释为向量f∈ 定义一个线性函数f:RN→ R、 式中，f（g）=hf | gi=XS∈NFSGSFORALL g∈ 注册护士。如果g（S）是特定联盟S的（0，1）-关联向量∈ N、 我们有f（g（S））=hf | g（S）i=fS·1=fS。也就是说，f将2N（=N）上的p势f延伸到所有RN。相反，每个线性泛函G7→ hf | gi on RN定义了唯一的电势f on N vi af（S）=hf | g（S）i for all S∈ 参见，例如，g.-C.R OTA（1964）：基于组合理论I.M–OBIUS函数的理论。《华尔街日报》和《华尔街日报》94 7。合作博弈这些考虑表明，与非线性泛函上的势（特征函数）是同一枚硬币的两面。从线性代数的观点来看，我们可以等价地定义：o合作TU博弈是一对Γ=（N，v），其中N是一组参与者，v7→ hv | gi是向量空间RN上的线性函数。1.2. 边际价值。合作博弈Γ=（N，v）的特征函数v是相对于N的联盟系统N的效用。

单个p层i∈ N将通过评估v的变化来评估其相对于v的价值，v的变化可以通过活跃或不活跃来影响。作为一名球员，我∈ N、 因此，我们将其相对于公司的边际价值定义为：四(S)=v（S）∪（一）- v（S）如果我∈ N\\Sv（S）- v（S\\i）如果我∈ 美国的加法游戏。边际价值一名球员的iv（S）∈ N取决于它所指的联盟。不同的联盟可能会为玩家i产生不同的边际值。如果每个玩家的边际值相对于所有可能的联盟都是相同的，则游戏Γ=（N，v）被称为加法。所以这里有一些数字iv（S）=所有的vis∈ N和我∈ 因此，如果v是加法的，我们有v（S）=v() +席∈Svi。相反，每个向量∈ 定义一个零标准化加法博弈（N，a），理解（37）a() = 0和a（S）=Xs∈所有S 6=.例7.4。哪些一致性游戏（见Ex.7.2）是加法游戏？证明了N上所有加法对策的向量空间都有维数|N |+1。N上所有零正规加法对策的子空间都有维数|N |。现在我们来看更多合作游戏的例子。1.合作TU-GAMES 951.3。制作游戏。在第4.2节中，考虑从M原料M生产K种不同类型的产品的工厂，…嗯。Letx=（x，…，xk）是一个计划，该计划提出生产第j种商品的xjunits，并假设（1）x需要ai（x）单位的材料Mifor i=1，M（2） 产品x可以以f（x）的价格出售（欧元、美元或其他任何价格）；（3） 有一组供应商，每个供应商∈ N拥有两个单位的材料Mi。如第4.2节所述，寻求最佳生产计划*导致优化问题Maxx∈Rk+f（x）s.t.ai（x）≤Xs∈Nbis（i=1，…m）。假设材料的市场价格为y*, . . .

Y*m（每单位）。然后是一个可选的imal生产计划x*需要购买v（N）=Xs∈纽约*iai（x）*) =mXi=1y*ibi（含bi=mXs）∈NBI）供应商提供的材料价值。一个人的价值应该如何∈ N需要评估吗？自然参数是s：（38）w拥有的所有材料的市场价值*s=nXi=1y*宜必思。这是s 7吗→ W*sto个别供应商的“公平”？为了在这个问题上大开眼界（不回答它），让我们考虑另一种方法：假设一个联盟从阴影PrICESYSI，评估它的内在价值，…S-限制优化问题（39）maxx的性质∈Rk+f（x）s.t.ai（x）≤Xs∈SBI（i=1，…m）。最优解xSof（39）要求V（S）=mXi=1YSAI（xS）=mXi=1ySibSi（bSi=mXs∈Sbis）96 7。合作博弈是物质的结合，产生了合作博弈（N，v）。在这种情况下，供应商的价值∈ N\\T对于一个coaliti on T是sv（T）=v（T∪（s）- v（T）。因此，有人可能会认为，对供应商的“公平”评估应该考虑其边际价值。（下文第3.2节将进一步研究这一想法。）1.4. 线性生产游戏。暂时不考虑边际值，在线性目标和线性生产需求的情况下，情况尤其明显：f（x）=cTx=cx+…+cnxnai（x）=aTix=ai1x+…+ainxn（i=1，…，m）。其中A表示带有m行向量aTi的矩阵，即阴影向量y*是对偶线性规划的最优解∈Rm+yTb s.t.yTA≥ cTand的属性为yv（N）=mXi=1biy*i=nXj=1cjx*j=f（x）*).请注意，S-限制生产问题的对偶具有相同的约束，不同之处仅在于目标函数的系数：miny∈Rm+yTbSs。T

伊塔≥ 计算机断层扫描。最优解xS和影子价格向量ySyieldv（S）=mXi=1bSiySi=nXj=1cjxSj=f（xS）。所以影子价格向量y*对于S-限制也是可行的（但不一定是最优的），我们得出结论（w*sas in（38））：（40）v（S）≤mXi=1bSiy*i=Xs∈西南*s=w*（S） 。备注7。3.不确定性（40）表明影子价格是不稳定的*令人满意的联盟在某种意义上说，每一个联盟都获得了一个有价值的物质财富*（S） 这至少和它的纯市场价值v（S）一样大。这就是游戏核心概念背后的想法（参见下面第2节）。合作TU-GAMES 971.5。网络连接游戏。考虑某个实用程序的用户的集合n＝{p，…，pn }，这些用户将直接或间接地连接（ViaTor用户）到S OME的S上节点P。假设TH以建立PijPito与CIJ（欧元，美元或任何东西）之间的链路为代价。关联合作博弈具有效用函数C（S）=仅将S连接到p的最小成本。相关问题是：o一个用户需要多少pi∈ N充电，以便建立具有所需连接的网络？从最小总成本c（N）的一种构造方法出发，导出了一种可能的成本分配方案。贪婪算法建立了一个联盟链 = s s s . . .  Sn=n根据以下迭代程序：（G）S=;（Gj）如果已建造SJ，则选择p∈ N\\Sj使C（Sj∪ p） 尽可能小，收取边际成本jv（S）=c（Sj）∪ p）- c（Sj）。（Gn）设置Sj+1=Sj∪ p并继续，直到所有用户都被选中。不是贝尼。贪婪算法确保用户在Totalis中设置N收取最小可能的连接成本：nXj=1[c（Sj）- c（Sj）-1） ]=c（序列号）- c（S）+n-1Xk=1[c（Sk）-c（Sk）]=c（N）- c（) = c（N）。从这个意义上说，贪婪算法是有效的。