数学博弈论

元素x的选择∈ 至少有一个限制违反gi（X）<0的X将允许游戏∧=（X，Rm+，L）中的y玩家增加其与yi的效用值≈ ∞. 因此，规避风险的x-player总是会尝试选择一个可行的x。另一方面，如果gi（x）≥ 0代表所有i，y玩家能做的最简单的事情是选择y∈ Rm+使得所谓的补元松弛条件（23）mXi=1yigi（x）=yTg（x）=0，因此L（x，y）=f（x）这个想法可以追溯到J.-L.拉格朗日（1736-1813）4。拉格朗日对策47是令人满意的。因此，我们发现：原始拉格朗日问题与原始问题相同：（24）maxx∈Xminy≥0L（x，y）=maxx∈FL（x）=maxx∈Ff（x）。对偶拉格朗日最坏情况函数为（25）L（y）=maxx∈Xf（x）+yTg（x）。引理3.1。If（x）*, Y*) 是拉格朗日对策∧的平衡点，然后是x*是问题（21）的最优解。证据对于每个可行的x∈ F、 我们有（x）≤ L（y）*) = L（x）*) = f（x）*).所以x*这是最优的。4.1. KKT条件。引理3.1指出了在拉格朗日对策中识别平衡点的重要性。为了建立必要的条件，我。e、 ，平衡候选必须满足的条件，我们对问题（21）施加进一步的假设：（1）X 我认为这是一个凸集。e、 ，X包含w和每个X，X′也包括整个线段[X，X′]={X+λ（X′）-x） |0≤ λ ≤ 1 }.（2） 函数f和giin（21）具有连续的部分导数f（x）/xjandgi（x）/xj对于所有j=1，n、 因此，拉格朗日函数的所有偏导数。所以L向x变量方向d的边际变化是xL（x，y）d=f（x）d+mXi=1yigi（x）d=nXj=1f（x）xjdj+mXi=1nXj=1gi（x）xjyidj。48 3. 零和遗传算法3.3（雅可比矩阵）。

具有as系数Dg（x）ij的（m×n）矩阵Dg（x）=gi（x）函数g:Rn的偏导数→ Rmis被称为函数矩阵或雅可比矩阵。它允许拉格朗日函数的边际变化采用紧凑的矩阵表示法：xL（x，y）d=f（x）+yTDg（x）d.引理3.2（KKT条件）。这对（x，y）∈ X×Rm+不能成为LAGRANGE对策∧的平衡点，除非：（K）g（X）≥ 0，也就是说，xi是可行的。（K） yTg（x）=0。（K）xL（x，y）d≤ 0对ll d有效，因此x+d∈ X.证据。我们已经知道，可行性条件（K）和互补松弛条件（K）必然满足平衡。如果（K）被违反，并且xL（x，y）d>0为真，x-player可以通过将BIT i移动到方向d来改善L值。这与“平衡”的定义相矛盾。备注3.4。引理3.2的三个条件就是所谓的KKT条件。尽管它们总是必要的，但它们并不总是足以证明候选人（x，y）确实是一个平等的人。4.2. 影子价格。优化问题（26）maxx∈Rn+f（x）s.t.a（x）≤ B安（x）≤ 具有m个限制函数gi（x）=bi的（21）型BMI- ai（x）和拉格朗日函数c。G.雅各比（1804-1851），以数学硕士卡鲁什、库恩和塔克的名字命名。拉格朗日对策49L（x，y）=f（x）+mXi=1yi（bi）- ai（x））=f（x）-mXi=1yiai（x）+mXi=1yibi。对于问题（26）的直观解释，可以将a向量处的d=（x，…，xn）视为n个产品的生产计划，数量为x，f（x）为x的市场价值。假设x需要使用m种材料，数量分别为ai（x），对于i=1。

，m，并且偏差是制造商同意的材料数量。如果Yi代表m种材料的市场价格（每单位），L（x，y）是生产x的市场价值加上生产x后留在库存的材料价值。制造商当然希望该值尽可能高。”“市场”是制造商的对手，并关注其价值-L（x，y）=mXi=1yi（ai（x）- bi）- f（x），即制造商为生产x而必须在市场上购买的材料的价值减去市场为生产x而必须向制造商支付的生产价值。市场希望将价格设置为-L（x，y）尽可能大。因此：o制造商和市场扮演着拉格朗日∧的角色等平衡平衡（x*, Y*) 其中∧反映了一种经济平衡：无论是制造商还是市场都无法通过改变生产计划或设定不同的价格来保证提高其价值。从这个意义上说，生产计划x*这是最优的。（从市场的角度）最优价格是y*, . . . , Y*制造所谓的材料影子价格。50 3. 零和GA MES互补松弛条件（K）表示一种材料在库存中，但x没有完全使用*市场价值为零：ai（x）*) < 毕==> Y*i=0。条件（K）意味着x是最优值f（x）的生产计划*) = L（x）*, Y*) 在给定的限制下。

此外，一个hasmXi=1y*iai（x）*) =mXi=1y*ibi表示，用于生产x的材料的价格*等于影子价格y下的存货价值*i、 Property（K）表示，边际变化xL（x）*, Y*)在X的任何可行生产修正中，制造商价值的d为负值*到x*+ d且仅适用于市场，因为x(-L（x）*, Y*)) = -xL（x）*, Y*).我们将回到第1.3.4.3节合作博弈理论的内容中的生产g ames。凸拉格朗日对策的平衡。值得注意的是，KKT条件对于具有可微目标函数的凸拉格朗日对策中平衡点的刻画不仅是必要的，而且是充分的。这提供了一种计算此类平衡的方法，并在实践中解决了e（21）型优化问题：o找到一个解决方案（x*, Y*) ∈ KKT不等式的X×Rm+。（十）*, Y*) 将产生∧=（X，Rm+，L）和X中的平衡*将是（21）的最佳解决方案。定理3.3。一双（x）*, Y*) ∈ X×Rm+是凸拉格朗日对策∧=（X，Rm+，L）的平衡点当且仅当（X*, Y*)满足KKT条件。证据从引理3.2中，我们知道kkT条件是必要的。为了显示效率，假设（x*, Y*) ∈ X×Rm+满意利润不是我们当前的目的，我们不打算详细研究进一步的计算方面，这可以在有关数学编程的现有文献中找到。拉格朗日对策51KKT条件。我们必须证明（x*, Y*) 是拉格朗日博弈∧=（X，Rm+，L）的均衡，即满足（27）maxx∈XL（x，y）*) = L（x）*, Y*) = 米尼≥0升（x）*, y） 对于L（x，y）=f（x）+yTg（x）。从X7开始→ L（x，y）对于每个y都是凹的≥ 0我们发现每x∈ 十、 L（X，y）*) ≤ L（x，y）*) + xL（x，y）*)（十）- 十、*) ≤ L（x）*, 十、*)因为（K）保证xL（x，x*)（十）- 十、*) ≤ 0.因此（27）中的第一个等式如下。

从（K）和（K），我们得到了g（x）*) ≥ 0和（y）*)Tg（x）*) = 0，从而推导出第二个等式：miny≥0升（x）*, y） =f（x）*) + 米尼≥0yTg（x*) = f（x）*) + 0=f（x）*) + （y）*)Tg（x）*) = L（x）*, Y*).4.4. 线性规划。线性规划（LP）是一个形式为（28）maxx的优化问题∈Rn+cTx s.t.Ax≤ b、 c在哪里∈ RN是一个n维系数向量，A∈ Rm×na矩阵和b∈ Rman m维系数向量。问题类型（28）是参数（1）X=Rn+，（2）f（X）=cTx=Pnj=1cjxj，（3）g（X）=b的（21）的特例- 以及拉格朗日函数l（x，y）=cTx+yT（b- Ax）=yTb+（电流互感器）- yTA）x，在变量x和y中都是凹的和凸的。最坏的情形函数是l（x）=cTx if Ax≤ B-∞ 如果Ax 6≤ b、 L（y）=yTb如果yTA≥ cT+∞ 如果yTA 6≥ 计算机断层扫描。为了标记这种特殊情况，我们将与线性程序（28）相关的拉格朗日对策称为LP对策，并用LP（c；a，b）表示。52 3。我们已经知道，最大化L（x）的p问题对应于原始问题（28）。最小化L（y）的对偶问题对应于优化问题（29）miny∈Rm+bTy s.t.ATy≥ c、 例3.5。制定一个与优化问题（29）等价的（28）型线性规划。例3.6。将随机矩阵对策（X，Y，U）中的最优策略问题表述为（28）形式的线性规划，即找到可测矩阵a和系数向量c a和b。我们从定理3.3知道，LP对策的平衡点可以计算为KKT条件的解。至于它们的存在性，基本定理3.4提供了一个无紧性的特征：定理3.4（关于线性规划的主要定理）。LPgame（c，A，b）有一个平衡点，当且仅当（28）和（29）两个问题都有可行解时。LP游戏本身并不像零和游戏那样有趣。

在可能有两个以上参与方的合作博弈理论（见第7章）中，线性规划是一种结构分析工具。线性规划问题在应用中尤其重要，因为它们可以有效地解决。我们不讨论算法细节，而是参考标准数学优化文献。（另见附录第4节。）e、 g.，U.FAIGLE，W.KERN和g.STILL，数学编程的算法原理，Springer，2002年第4章投资和提高赌徒的对手通常是没有特定优化目标的玩家。对手的战略选择是由机会决定的。因此，赌徒必须决定具有良好预期回报的策略。信息在寻求最佳决策中起着重要作用。因此，如何在（可能不止两个）参与者之间建立信息交换和共同知识模型的问题也值得解决。假设投资者（或投注者、赌徒或简单的玩家）正在考虑参与某项风险投资。那么，对投资者来说，一个显而易见——尽管相当模糊——的大问题是：o应该做出什么样的决定？更具体地说，投资者希望决定一项投资是否值得，如果值得，应该投资多少钱。显然，答案在很大程度上取决于其他信息：成功的可能性是什么，预期会有什么收获？aloss的风险是什么？因此，投资者将以玩家的身份参与一场双人游戏，对手的策略和目标并不总是明确或事先知道的。投资者无法完全（或可靠）获得相关信息，因此必须在不确定的情况下做出决策。

典型的icalexamples是赌博和博彩，其成功与否取决于可能发生或不可能发生的事件，因此取决于“运气”或“机会”。但是，如果事先不清楚某项投资的价值会上升还是下降，股票市场的投资也属于这一类。我们不能完全回答上面的大问题，但要讨论它的各个方面。在深入探讨更多细节之前，让我们用一个经典的——看似矛盾的——赌博情境来说明这个主题的重要性。54 4. 我在测试和完善圣彼得堡悖论。想象自己是一个潜在的玩家，在接下来的机会游戏中。例4.1（圣彼得堡比赛）。一枚硬币（有“H”和“T”两个面）被反复挤压，直到“H”出现。如果这个h出现在第n次掷骰时，参与的玩家将获得αn=2欧元。然而，aeuros的参与费是有限的。所以玩家的净增益isa=αn- a=2n- 如果游戏在第n次掷骰子时停止。参加奥运会的费用是多少？假设在圣彼得堡的比赛中有一枚公平的硬币，掷n次以上（因此第一个n次结果为“t”）的概率为qn=n=n→ 0（n）→ ∞).因此，游戏几乎肯定会在最后几次失败后结束。然而，参与者的预期回报是有限的：EP=∞Xn=1nqn=+++nn+…=+∞,这可能并不意味着玩家应该愿意为被允许进入游戏支付任何金额。然而，在实践中，这可能是arisky venture（见Ex.4.2）。例4.2。表明在圣彼得堡比赛中获得100欧元或更多奖金的概率小于1%。

因此，a=100欧元或mo re的参与费似乎不具吸引力，因为其覆盖率不超过99%。矛盾的是，当我们不是直接而是通过对数logn=n来评估收益2n的效用时，圣彼得堡的收益有一个有限的效用预期：GP=log+log++lognn+=∞Xn=1nn<2。它表明，人们应该期望效用值小于2，因此回报小于2=4欧元。1.比例4.1（对数效用）。伯努利在对圣彼得堡博弈的分析中引入了对数函数来衡量财务收益的效用值。这个凹函数在我们的分析中也起着重要的作用。无论使用logx、对数基e2还是自然对数lnx，都没有任何本质区别，因为这两个函数的区别只是一个比例因子r:lnx=（ln2）·logx。1.比例投资我们的一般模型由初始投资组合B>0欧元（或美元或…）的潜在投资者组成投资机会A。投资者要决定哪部分aB（比例因子为0）≤ A.≤ 1） B的一部分应该投资，并考虑k可能的情况A，为它的发展做准备。投资者认为其中一种情况将被具体化，hermore进一步假设：（S1）如果发生AII，则每一欧元投资的回报率为ρi≥ 0欧元。（S2）场景Ai以概率pi发生。预期收益。在投资者的假设下，每投资一欧元的预期回报率为ρ=ρp+…+ρkpk。如果投资者的决策是基于预期回报的最大化，naiv投资规则适用：（NIR）如果ρ>1，将所有B投资于A，并预期回报Bρ>B。如果ρ≤ 1.不要投资，因为没有适当的收益预期。尽管规则（NIR）具有直观的吸引力，但它还是有相当大的风险。

4.3).例4.3。对于k=2，求出返回率ρ=0和ρ=100。如果p=0.9和p=0.1，投资者预期投资回报率为10倍：ρ=0·0.9+100·0.1=10。然而，在概率p=90%的情况下，预计投资将以伯努利（1700-1782）56 4的总服务水平进行。测试并提高预期效用。关于对数效用函数Lnx，aB大小投资的预期效用为u（a）=kXi=1piln[（1- a） B+ρiaB）]=kXi=1piln[1+（ρi- 1） a]+lnb.U（a）的导数isU′（a）=kXi=1pi（ρi）-1） 1+（ρi）- 1） a=kXi=1pi1/ri+awith ri=ρi- 1是情景Ai中投资者对每个被投资区域的预期盈余。投资率*最优效用值必须满足‘（a*) = 因此，可以通过求解方程U′（a）=0来计算。例4.4。在ex4.3的情况下，一个hasU（a）=ln（1- a） +ln[（1+99a]）+ln b与导数eu′（a）=-910(1 - a） +10（1+99a）。U′（a）=0意味着a=1/11。因此，B/11部分应该按最大化预期效用的顺序进行投资。其余的B=B- B/11投资组合应保留，不得投资。2.财富公式我们转向一个基金基本问题：o一个人是否应该投资一个机会a，该机会以概率p的ρ提供预期回报，但同时也提供概率q=1的完全损失（即零回报）-P在Ex.4.4中已经遇到了这种情况的一个特例。用r=ρ表示- 1投资的预期盈余率，通常相关的预期对数效用为2。

财富公式57（30）U（a）=qln（1）- a） 带导数（31）U′（a）的+p ln（1+ra）+ln b=-q1- a+p1/r+a。如果预期损失的正概率q>1，且投资者决定进行全部投资，即选择a=1，则可用性值U（1）=-∞无论利率r有多大，都必须是预期的。另一方面，无投资的选择a=0具有效用U（0）=ln B。投资率a*在这些极端之间的某些地方存在最佳利用率。引理4.1。设U′（a）如（31）所示，0<a*< 1.ThenU′（a）*) = 0<==> A.*= P- q/r证明。（练习留给读者。）投资率的选择*最优期望对数效用U（a）*), i、 根据凯利所谓的财富公式：（32）a*= P-qrif0<p-qr<1坚定自己的信念。重要的是要记住，财富公式（32）中的概率是投资者对投资成功的主观评价。在投资时，“真实”概率通常是未知的。然而，如果反映了投资者对真实概率的最佳了解，那么投资者就没有更好的办法了。这一真理被称为投资建议，树立你的信念！J.L KELLY（1956）：对信息速率的新解释，贝尔系统技术期刊58 4。我正在测试和改进。公平的奥德桑投资机会y A，回报率为ρ≥ 1欧元pereuro以一定的概率Pr（a）投资或不回报（概率1- Pr（A））被称为对A的押注。然后，投资者是投注者（或赌徒），回报ρ是回报。假设收益由收受赌注者（或银行）担保。