双层规划中的领导者-跟随者均衡的正规型和多矩阵对策的计算方法

13NP APX P=NP···原始论文EURO Journal on Computational Optimization（2020）8：3https://doi.org/10.1007/s13675-019-00114-8双层规划计算方法正规型和多矩阵对策Nicola Basilico1 ·Stefano Coniglio2·Nicola Gatti3·AlbertoMarchesi投稿时间：2018年10月3日/受理时间：2019年5月10日/在线发表时间：2019年5月18日©作者（S）2019摘要领导者-跟随者（或斯塔克伯格）均衡的概念在许多接近数学优化和博弈论的实际应用虽然单追随者的情况下，已经调查了自双层规划的开创性工作冯Stackelberg成立以来，结果的情况下，多个追随者只是零星的，并没有很多计算负担得起的方法。在这项工作中，我们考虑Stackelberg游戏与两个或两个以上的追随者谁发挥（纯或混合）纳什均衡一旦领导者已承诺（纯或混合）的战略，专注于正常形式和多矩阵游戏。作为二层规划中的习惯，我们解决了两个极端的情况下，如果领导者的承诺在追随者的游戏中产生更多的纳什均衡，一个最大化（乐观情况）或最小化（悲观情况）的领导者首先，我们证明，在这两种情况下，当假设混合策略时，与寻找Stackelberg均衡的搜索问题相关的优化问题是- 硬，而不是在聚-除非。然后，我们考虑不同的情况下，根据领导者或追随者是否可以发挥混合策略或仅限于纯策略，提出精确的非凸数学规划公式的乐观情况下的正规形式和多矩阵游戏。对于悲观的问题，这不能解决（单级）数学规划制定，我们提出了一个启发式黑盒算法。所有的方法和配方，我们提出了彻底的计算评估。双层规划;博弈论; Stackelberg对策;均衡计算数学科目分类91A10· 91A65· 91A90· 90C26在文章的最后一页上提供了扩展的作者信息134N. Basilico等人1 介绍领导者-追随者（或斯塔克伯格）游戏模拟了当分层决策结构就位时理性代理（或玩家）之间的互动为了简单起见，考虑到两个玩家的情况，斯塔克伯格博弈模拟了这样的情况，即一个代理人（领导者）首先采取行动，第二个代理人（追随者）在观察领导者选择的策略后紧随其后。在现实世界中，领导者-追随者（或Stackelberg）结构可以被识别的问题数量非常大。这在安全领域中是经常发生的情况（Anet al.2011; Kiekintveld等人2009年），其中一个防御者，旨在保护一组有价值的目标从攻击者，发挥第一，而攻击者，作为追随者，只有在观察领导者的防御策略后才采取行动其他值得注意的案例包括阻断问题（Caprara et al.2016; Matuschke et al.2017）、收费设置问题（Labbé and Violin2016）、网络路由问题（Amaldi et al.2013）和（单例）拥塞博弈（Castiglioni et al.2018; Marchesi et al.2018年）。然而，自从von Stackelberg（2010）的开创性工作以来，具有单个领导者和单个跟随者的情况已经被广泛研究，对于具有多个跟随者的情况，只有少数结果是已知的，并且没有多少计算负担得起的方法可用于解决相应的均衡发现问题。在本文中，我们专注于单领导者多跟随者游戏的基本情况，每个玩家的动作数量有限，整个游戏可以表示为正规形式或多矩阵游戏-后者是有趣的，因为它在许多应用中起着重要作用，例如在安全领域，防御者可能需要优化多个不协调的攻击者，只对破坏领导者感兴趣。在整个论文中，我们假设（两个或更多）追随者同时以非合作的方式进行游戏，因此很自然地假设，在观察领导者的游戏（无论是作为一种策略还是作为一种行动）之后我们把这种博弈中的均衡称为领导者-追随者纳什均衡（LFNE）。由于它是典型的双层规划，我们研究了两个极端的情况下：乐观的一个，如果领导者特别是，领导者因此，在悲观均衡下，领导者从这个角度来看，一个愿意承担风险的领导者会按照乐观的均衡进行博弈，而一个厌恶风险的领导者会按照悲观的均衡进行博弈。有关这两个概念的更多类型的解决方案，我们建议读者参考Alves和Antunes（2016）。Bilevel Programming Methods for Computing513NP APX P=NP=p∈ ∈ {}为||∈∈ []={}∈p∈ \{}ppQ N p对于PM博弈（参考Yanovskaya（1968）），我们有一个效用矩阵我们工作的最初贡献如下。1首先，我们说明了当跟随者玩最大化或最小化领导者效用的NE时，与在混合策略中计算LFNE的搜索问题相关联的优化问题是- 硬，而不是在聚-除非。在将一般的混合策略承诺问题转化为两层条件后，我们针对乐观情形提出了不同的非线性和非凸单层数学规划公式，适用于最先进的空间分支定界求解器.对于悲观的情况下，不承认一个单级的数学规划重新制定的多项式大小，我们提出了一个启发式方法的基础上结合的空间分支定界求解器与黑盒算法。我们还简要地调查（更容易）的变种的问题时，限制无论是领导者或追随者的纯战略承诺。最后，我们提供了一个全面的实验评估，我们的技术在一个（正常形式和多矩阵）的测试平台上生成的GAMUT（Nudelman等人。2004），也encom-通过一些结构化的游戏，采用不同的求解器：BARON，SCIP，CPLEX，SNOPT和RBFOpt。(The后者用于黑盒优化）。2 符号设N1、......、n是代理的集合。对于每个pN，我们用A p表示智能体的动作集，其中m pA p.对于每个代理pN，我们用x p表示0，1 mp，其中e T x p1（其中e是全一向量），它们的策略向量（或简称策略）。xp的每个分量xa表示代理p采取行动a Ap的概率。我们称x p为纯策略向量，如果x p为0，1 mp，或者在一般情况下为混合策略向量。我们表示一个策略剖面，即，的收集每个智能体采用的策略，通过x=（x1，...， x n）。M对于每个代理p∈N，我们将其效用函数定义为up：[0，1]1×··· ×[0， 1]mn→R。一个策略轮廓x=（x1，...，xn）是NE当且仅当，对于每个agenttp∈N，up（x1， . ，xn）≥up（x1r， . ，xnr），其中xqr=xq，对所有q∈N\{p}和dxrp/=x p. （这与不存在的问题相对应。会发生单方面的偏差我们考虑两个博弈类：正规形式(NF)多矩阵（PM）对于NF游戏（参见Shoham和Leyton-Brown（2008）作为参考），我们让U p∈Rm1×···×mn 表示对于每个代理p∈N，它们的（多维）效用（或支付）矩阵，其中每个分量U为1，...，an表示代理p 的效用当所有代理执行动作A1，...， 一个; 给定一个策略轮廓（x1，...， x n），代理人p ∈ N的期望效用等于多线性函数u p（x1，...，xn）=xT（U p·.x q）。对于每对代理p， q∈A，UPq∈Rmp×mq 给定一个策略轮廓（x1，...， x n），代理p的期望效用等于双线性函数up（x1，...， x n）=.q∈N xTU pqx q.[1]该论文的某些部分在Basilico等人的初步阶段提出（2016）和Basilico et al.（2017）。6N. Basilico等人13NPNP我们注意到，虽然在NF的情况下，对应于代理的预期效用的多项式的次数该属性的计算影响将在本文中讨论。3 以前的作品自纳什（1950）的原始工作以来，计算多人博弈（没有领导者）中的纳什均衡 问 题 引 起 了 人 们 的 极 大 兴 趣 - 参 见 专 著 （ von Stengel2010 和 Chen andDeng2006; Conitzer and Sandholm2008），其中解决了问题的复杂性有关非合作博弈论的更多细节，我们建议感兴趣的读者阅读Shoham和Leyton-Brown（2008）。据我们所知，大多数关于Stackelberg博弈的博弈论研究主要是针对单个跟随者的情况。在这样的设置中，已知单个跟随者可以在不失一般性的情况下采取纯策略，即，总是有一个纯策略，通过它他们可以最大化他们的效用，并且与计算均衡的搜索问题相关的优化问题在完全信息下很容易（von Stengel和 Zamir2010 ） ， 而 对 于 贝 叶 斯 博 弈 来 说 ， 它 变 得 很 难 （ Conitzer 和Sandholm2006）。Conitzer和Sandholm（2006）提出了算法。对于两个以上参与者的Stackelberg博弈，一些研究已经研究了多个领导者和一个追随者的情况;参见Leyffer和Munson（2010）。对于涉及一个领导者和多个追随者的问题（我们在本文中关注的问题），只有少数结果可用。例如，众所周知，如果追随者在乐观情况下扮演相关均衡，则可以在多项式时间内找到均衡（Conitzer和Korzhyk 2011）（参见Shoham和Leyton-Brown2008了解相关均衡的更多细节），而相关的优化问题是- 如果他们一个接一个地按 顺 序 播 放 ，时 间 （ 如 在 一 个 经 典 的Stackelberg 游 戏 与 许 多 球 员 ）（Conitzer和Sandholm2006）。4 问题陈述、双层透视与计算复杂性在这一节中，我们形式化的问题，我们解决的文件中，投在双层条款，并研究其计算复杂性和逼近。4.1 问题陈述在形式上，我们在本文中处理的计算LFNE问题的两个主要版本Bilevel Programming Methods for Computing713≥≥=∈：=\{}=\{}=={}∈Δ×Δ×Δ1 24O-LFNE：给定一个n-代理博弈，n = 3，为领导者找到一个策略向量δ，使得在提交后，在δ参数化的追随者博弈中，领导者在所有NE上的最大效用尽可能大。P-LFNE：给定一个n-代理博弈，n = 3，为领导者找到一个策略向量δ，使得在提交后，在δ参数化的追随者博弈中，领导者在所有NE上的最小效用尽可能大。当符号方便时，我们将把乐观或悲观的LFNE称为O/P-LFNE。我们将区分领导者或追随者被限制或不限于纯策略的情况，考虑四种情况 ： 领 导 者 混 合 和 追 随 者 混 合 （ LMFM ） ， 领 导 者 纯 和 追 随 者 混 合（LPFM），领导者混合和追随者纯（LMFP），领导者纯和追随者纯（LPFP）。在一般（混合）情况下，我们假设领导者承诺一个策略，即，他们（领导者）根据概率分布选择他们的行动，并且，虽然追随者可以观察领导者选择的分布，但他们（追随者）不能观察其实现（即，领导者扮演的角色）。例如，安全游戏领导者的策略是纯策略的情况跟随者采取混合策略的假设与没有领导者的博弈相同我们可以考虑重复博弈，其中领导者必须在博弈开始前承诺单一策略，而追随者可以在每次迭代中从他们的选择分布中绘制不同的行动轮廓，从而玩混合策略。为了便于演示，在本文的其余部分，我们假设n3（一个领导者，两个追随者）。我们注意到，我们的结果可以适用于任何n。节中 9，我们将确实报告对具有两个以上追随者的游戏进行的计算实验。在本文的其余部分，我们假设最后一个代理（第三个），我们重新标记为代理4，担任领导者的角色。所有其他的代理人（追随者）都由集合F表示N四、当n3、F一，二。对于所有fF，我们定义FrF f.我们还用δ表示x4（领导者的策略向量），x1，x2（追随者的策略向量）乘以ρ1，ρ2。对于每个pN，我们令Δp是参与人p的策略单形，即，非负向量集δ，ρ1或ρ2加起来是1。4.2 双层规划透视图计算O/P-LFNE相当于解决一个双层规划问题。在乐观情况下，我们可以通过解决以下问题来计算O-LFNE（O-LFNE）max...乌伊克岛4jk（1a）（ρ1，ρ2，δ）∈i∈A1j∈A2k∈A4ρ1ρ2δ8N. Basilico等人13∈∈ × ×Δ×Δ1 2NPNPρ1∈Δ1i∈ A1 j∈ A2 k∈A41ρ 1ρ 2δρ2∈Δ22ρ 1ρ 2δS.T. ρ1∈argmax。...乌伊克我jk（1b）ρ2∈ argmax。...乌伊克我jk.（1c项）i∈ A1 j∈ A2 k∈A4由于约束条件（1b）-（1c），第二层问题需要一对（ρ1，ρ2）跟随者的策略，在第一层领导者选择的策略δΔ4诱导的跟随者博弈中形成一个NE。注意，由于NE的定义，在δ诱导的博弈中，（ρ1，ρ2）是NE当且仅当ρ1（分别为，ρ2）最大化参与人1参与人2参与者1）参与ρ2（分别，ρ1）。在这些约束条件下，第一级要求三元组（ρ1，ρ2，δ）最大化领导者这个问题是乐观的，因为假设第二层允许许多NE（ρ1，ρ2）用于所选的δ，它需要一个对（ρ1，ρ2），它与δ一起最大化领导者请注意，虽然任何三元组（ρ1，ρ2，δ）Δ1Δ2Δ 4都是问题的可行解，只要（ρ1，ρ2）是由δ诱导的博弈中的NE，但问题（1a）-（1c）要求三元组（ρ 1，ρ 2，δ）是最优的-因为，如果不是，领导者会更愿意改变他们的策略，并且（ρ 1，ρ 2，δ）不会是LFNE。在悲观的情况下，计算P-LFNE相当于解决以下问题：（P-LFNE）maxmin ...乌伊克岛4jk（2a）δ∈Δ4（ρ1，ρ2）∈i∈A1j∈A2k∈A4ρ1ρ 2δS.T. 约束条件（1b）、（1c）。（二）这个问题不同于它的乐观对应，因为由于悲观主义的假设，领导者在这里最大化他们在所有对（ρ1，ρ2）上的效用的最小值，这些对在由δ -诱导的追随者博弈中是NE，也4.3 复杂性结果正如我们将展示的，与计算LFNE的搜索问题相关联的优化问题在LMFM情况下的两个版本（O-LFNE和P-LFNE）中都是困难和不可近似的，即使具有单个领导者动作（这意味着结果也适用于LPFM情况）。这是因为- 硬度和计算问题的不可近似性，在两个玩家的游戏中，最大化玩家效用总和的混合策略NE（所谓的社会福利）（Conitzer和Sandholm 2008）：命题1（Conitzer and Sandholm 2008）计算一个最大化局中人总效用的混合策略NE的问题是NP -难的，除非P = NP，否则它不在APX中，即使当博Bilevel Programming Methods for Computing913弈是多矩阵时。10N. Basilico等人13α1APX2mP=NPAPX P=NPM =2个2m2mMm结果是基于这样的事实，对于任何SAT实例，都可以构建一个对称的两人游戏（U1，U2），NF或PM，使得：(i) 存在一个（纯策略）NE，其中两个参与者都采取他们的最后一个行动，并获得等于<$>0的效用，其中<$是一个任意小的常数;(ii) 游戏允许（混合策略）NE为每个参与者提供效用m，其中m是动作的数量，当且仅当SAT实例是YES实例。这意味着，在任何这样的博弈中，找到一个NE，其中参与者实现的效用严格大于<$，就足以声称相应的SAT实例是一个YES实例。由此可见，人们不能在多项式时间内决定这样的游戏是否允许NE为玩家提供严格大于<$的效用，除非因为，如果是这种情况，SAT的YES实例可以在多项式时间内决定这也表明，找到一个最大化社会福利（定义为总参与者的效用）的NE这是因为，如果存在一个能为参与者提供严格大于2<$的总效用的NE，就足以得出结论，即相应的SAT实例承认答案是肯定的。我们证明，Conitzer和Sandholm（2008）的结果可以通过一个简单的观察得到加强命题2计算最大化局中人总效用的混合策略NE的问题不在Poly中，除非，即使博弈是Polymartrix。证明让<$=1。在对应于YES SAT实例（允许总效用为2m的NE）的对策上，将使所总效用的NE至少为12m。注意，如果12m>2<$（即，1><$），SATα m实例被证明是YES实例。因此，不可能存在多项式时间近似算法的因子优于<$1，除非P=NP。以来这个因子的倒数是超多项式，这个问题在Poly-APX中不存在。п对于计算O/P-LFNE的问题，我们给出了以下结果：命题3与在LMFM和LPFM情形下计算O/P-LFNE的搜索问题相关联的优化问题是NP-困难的，并且除非P=NP，否则它不在Poly-APX中，即使当博弈是多矩阵时。让我们首先考虑O-LFNE的情况。给定一个效用为（U1，U2）的博弈，每个参与人有m个行动，如Conitzer和Sandholm（2008）所定义的，我们构造了一个3人领导者-跟随者多矩阵博弈，其中：– 领导者只有一个行动和效用矩阵U 4f1=U 4f2=U 4 f1，.，1.1公斤;– 局中人f1– 参与人f2由于只有一个动作，领导者的存在是无关紧要的。(Note因此，LMFM和LPFM的情况一致。因此，领袖-追随者博弈中追随者的均衡集与原始的两人博弈中的均衡集相同。因此，SAT的答案是肯定的，当且仅当领导者-追随者博弈允许领导者的效用严格大于1的均衡10N. Basilico等人13ααAPX P=NP4FNP4F2m2m2m在追随者博弈中，每个参与者的效用都严格大于<沿着前面的证明，对于YES实例，近似因子为1的算法将产生至少为1的领导者效用，这使得我们可以得出结论，如果1>1，则实例是YES实例。这表明，计算一个α2mO-LFNE不属于Poly-unless（即使在多矩阵博弈中）。对于P-LFNE的计算，除了定义之外，推理是相同的。U1 =U2 =1，1，...， 1，1英尺。п最后，我们通过展示决定领导者的一个行动是否可以被安全地丢弃是一个困难的问题来结束这一节命题4在LMFM情况下，决定领导者的行动是否在O/P-LFNE上以严格正概率进行是NP困难的。给定一个对称的两人博弈（U1，U2），有m个行动，如Conitzer和Sandholm（2008）所定义的，我们构建一个三人博弈（U4， Uf1，Uf2），其中：– leader有两个动作，f1和f2各有m个动作– 当领导者采取第一个行动时，所有参与人的收益都是1/ 4;– 当领导者采取第二个行动时，f1和f2的收益是（U1，U2）中的收益，并且对于f1和f2的所有行动，领导者我们证明了当且仅当博弈（U1，U2）允许混合策略NE为局中人提供效用m时，领导者的第一个行动可以安全地从博弈（U4，Uf1，Uf2）中被丢弃，这意味着决定领导者的第一个行动是否可以被丢弃是困难的。如果领导者采取第一个行动，他们得到的效用为1/ 4。如果领导者采取他们的第二个行动，追随者为领导者采取最好的NE，它可以是（i）纯策略NE，其中双方都采取他们的最后一个行动，为领导者提供效用0，或者（ii）如果存在，为领导者提供效用1的混合策略 NE对于领导者的任何混合策略在这种情况下，领导者将他们的第二个行动作为一个纯策略。这是因为，当领导者在他们的两个行动之间随机化，追随者f1和f2的效用是U1和U2的一个仿射变换（具有正系数），使他们完全像领导者作为纯策略采取第二个行动的情况一样。因此，在乐观LFNE下，领导者采取纯策略，如果（U1，U2）不允许混合策略NE，则采取第一个因此，当且仅当（U1，U2）允许一个混合策略NE为参与人提供效用m时，领导者的第一个行动才能被安全地丢弃。在交换了领导者的收益值0和1之后的悲观情况下，证明是类似的пBilevel Programming Methods for Computing11131≥41242ρ1∈Δ1i∈ A1 j∈A21121121ρ 2 ρ11 ρ2。212215 混合领导者和混合追随者的乐观情况（O-LMFM）在本节中，我们将重点讨论在一般情况下的乐观设置，即每个参与人都可以采用混合策略。我们提出了三种不同的精确的数学规划公式NF游戏，然后说明他们如何可以简化PM游戏。5.1 NF对策我们报告的三个配方，说明如何推导出它们中的每一个顺序。5.1.1 O-NF-LMFM-I为了获得问题的单级公式，我们通过应用涉及互补约束的标准重新公式化（Shoham和Leyton-Brown2008）来进行设对所有i∈A1和dj∈A2，U∈ij：=.k∈A U i jkδk和Ui j=.k∈AU i jkδkbe跟随者博弈的矩阵根据约束（1b），若（ρ1，ρ2）为NE，则ρ1必为线性规划（LP）的最优解：max. ..Ui jρiρj，其中如果ρ 2是固定的，则U_i_j ρ_i ρ_j是ρ 1的线性函数。由于LP是可行的，对于任何ρ2∈Δ2有界，通过互补松弛性，我们得到ρ1∈Δ1是最优的当且仅当存在标量v1使得对所有i∈A1以下成立：. v1 −。j ∈ A 乌吉吉i=0v1 ≥.j ∈ A 乌吉 吉Jv1可以解释为跟随者1的最佳响应值，等于跟随者在均衡时可以实现的最大效用。对ρ2应用类似的推理，我们得到ρ2∈Δ2是最优的当且仅当存在标量v2使得对于所有的j∈A2成立：. v 2 −。i∈A Ui jρiρj=0v2≥.i∈A Ui jρi.我们得出结论：（ρ1，ρ2）是NE当且仅当存在v1，v20使得ρ1和ρ2同时满足这四个条件。221112N. Basilico等人13.1ρ 2δ1212214ρ1ρ 2δj∈ A2 k∈A41ρ 2δ1j∈ A2 k∈A41ρ 2δ21221i∈ A1 k∈A4i∈ A1 k∈A4将U1和U2代入它们的线性表达式sinδ后，我们得到了参与人1和所有i∈A1的以下约束：.v1 −。j∈ A.k∈A乌伊克Ji=0v1 ≥.j∈A。k∈A乌伊克J K2对于参与人2和所有j∈A2，我们得到：41 ρ2δ。.v 2 −。i∈A.k∈AUijkρiδkρj=0v2≥..U ijkρiδk.通过施加这样的约束来代替问题（1）的两个第二层argmax约束（约束（1b）-2总的来说，案文如下：Max...乌伊克岛i∈ A1 j∈ A2 k∈A4（3）S.T..v1−。.乌伊克J k<$ρi=0 <$i∈A1（4）v1≥. .乌伊克jk<$i∈A1（5）.v2−。.Uijk ρiδk<$ρ j= 0<$j∈ A2（6）v2≥..Uijk ρiδk <$j ∈A2（7）δk=1，δ≥ 0（8）k∈A4.ρi =1，ρf≥ 0<$f∈F（9）i∈ AfF4214ρ1，ρ 2，δ，vi∈ A1 k∈A4Bilevel Programming Methods for Computing1313++vf≥ 0f ∈ F.（十）该问题包含m1m2三次约束，m1m2二次约束和一个三次目标函数.[2]注意，强对偶性可以用来代替互补松弛性。初步实验表明，第二种选择在计算上更可取。14N. Basilico等人13联系我们F2F2212ρ1，ρ 2，δ，v，s4ρ1ρ 2δj∈ A2 k∈A41ρ 2δ1212Fi∈ A1 k∈A4i∈ A1 k∈A45.1.2 O-NF-LMFM-II我们现在提出的是一个可以更有效地解决的公式。 由于我们引入的互补约束的每一项都是上下有界的，因此我们可以沿着Sandholm等人（2005）的路线应用一个简单的重新表述。让我们10， 1m1和s20， 1m2是ρ1和ρ2的反支持向量，（即，两个二进制向量，分别有m1和m2个分量，每个分量的值为0，当且仅当ρ1和ρ2在该分量中分别为严格正）。它足以对所有i∈A1施加以下约束：ρi≤1 −siv 1 −。1.乌伊克1J k≤Msij∈ A2 k∈ A4对于所有的j∈A2，1ρ2δ1ρj≤1−sjv2−。.U ijkρiδk≤ Ms j。M是U1、U2的项的上界。这样，在仍然保留原始三线性目标函数的同时，仅需要双线性约束。我们得到如下的重新表述：Max...乌伊克岛i∈ A1 j∈ A2 k∈A4中国（11）S.T.v1−。.乌伊克J k≤Msi（12）v2−。.U ijkρiδk≤ Ms j <$j ∈ A2（13）我 ≤1−si<$f∈F， i∈Af（14）sj∈ {0， 1}<$f∈F， j∈Af（15）约束条件（5）、（7）、（8）-（10）。（十六）ρBilevel Programming Methods for Computing1513在引入二进制变量的成本，与此配方，我们实现更少的非线性：只有2m1+ 2m2二次约束和一个立方目标函数。5.1.3 O-NF-LMFM-III最终，我们的目标是解决这个问题的空间分支定界技术，如那些在BARON和SCIP实现这种方法的主要策略是16N. Basilico等人134--12422ρ2δ1111 2224j∈ A2 k∈A41221j∈ A2 k∈A4121212FFi∈ A1 k∈A4处理非线性是通过将“简单的”非线性项（在我们的情况下是双线性或三线性的）转移到应用凸包络的新的（所谓的定义）约束中来隔离我们建议预测这种重新表述，以便能够得到一些有效的约束。首先，我们介绍：(i) 变量y jk和约束y jk=j k对所有j∈A2，k∈A4，(ii) 变量yik和约束yik=ρiδk，其中i∈A1，k∈A4，(iii) 变量zijk和约束zijk=ρiyjk，其中i∈A1，j∈A2，k∈A4。通过用新引入的变量替换每个双线性和三线性项，我们得到了一个处处线性的公式，除了定义约束本身。先验地执行该重新表述步骤的优点是，我们现在注意，在引入新变量后，矩阵{yjk}jk∈A×A为，定义，随机向量ρ2和δ的外积，因此，本身就是一个随机矩阵。这同样适用于张量zijkijk∈A1×A2×A，它是向量ρ1，ρ2，δ的外积，因此是一个随机张量。这意味着以下三个约束的有效性..y ik= 1i∈ A1 k∈ A4..y jk= 1j∈ A2 k∈ A4...z ijk= 1。i∈ A1 j∈ A2 k∈ A4我们注意到，这些不等式是那些通过对约束（8）和（9）应用laSherali和Adams（1990）的松弛线性化技术而得到的不等式的子集我们得到的公式如下：Maxρ1，ρ 2，δ，v，s， y， z...U ijkz ijk（17）i∈A1j∈A2k∈A4S.T.v1≥. .Uijkyjk（18）v2 ≥..Uijk yiji∈ A1 k∈A4n∈A2（19）v1−。 .Uijkyjk≤Msii∈A1（20）v2−。.U ijky ik≤ Ms j ∈ A2Bilevel Programming Methods for Computing1713（21）yik=ρiδk k∈A4，f∈F， i∈Af（22）18N. Basilico等人13FF++=1∈21412 ρ2。411k∈A4j∈ A2zijk=ρiyjkk∈A4，i∈A1，j∈A2（23）..y ik= 1<$f∈ F（24）i∈ Af k∈A4...z ijk= 1（25）i∈ A1 j∈ A2 k∈ A4yij≥0 <$f∈F， i∈Af， k∈A4（26）zijk≥0<$i∈A1，j∈A2，k∈A4（27）约束条件（8）-（10）、（14）-（15）。（二十八）总的来说，我们得到m 4（m1m2）m 4 m1m2二次约束和一个线性目标函数，产生一个更紧密的制定比O-NF-LMFM-II，我们将显示计算。5.2 PM游戏的精确公式我们说明了我们提出的三个公式如何在PM游戏中得到实质性的5.2.1 O-PM-LMFM-I在PM博弈中，对应于行动i A1的追随者1的期望效用（对于n =3且一般为n阶的NF博弈，这是一个三线性函数）被定义为以下线性函数（对于任何n都是线性的，特别是对于n=3）：.Uikδk+。Uij J领导者的效用是下面的函数，对任何n都是双线性的..Uikρi δk+.k∈ A4 i∈A1.UJKJKk∈ A4 j∈A2Bilevel Programming Methods for Computing19134 2 ρ2δ。41142ρ 2δk∈A414j∈ A212224211因此，与制剂O-NF-LMFM-I对应的PM内容如下：Max..Uikρi δk+.k∈A4i∈ A1k∈A4.UJKj∈ A2简体中文（zh_cn）S.T.v1≥.U ikδk+。U ijρ ji∈A1（30）v2≥.U jkδk+。Uijρik∈A4i∈ A1n∈A2（31）ρ1，ρ 2，δ，v16N. Basilico等人13+F∈∈141221k∈A424i∈ A12112ρ1，ρ 2，δ，v，s41142ρ 2δk∈A414j∈ A21221242112k∈A4j∈ A2k∈A4i∈ A1.v1−。U ikδk+。U ijρ j<$ρi= 0<$i ∈ A1（32）.v2−。U jkδk+。U ijρi<$ρ j= 0 <$j ∈ A2（33）限制（8）-（10.（三十四）与NF情况类似，该公式仅包含m1m2二次约束和二次目标（因为约束（5）和（7）在这里变为线性，而约束（4）和（6）以及目标（3）变为二次）。5.2.2 O-PM-LMFM-II将我们在O-NF-LMFM-II中进行的相同重新表述应用于PM情况，我们得到：Max..Uikρi δk+.k∈A4i∈ A1k∈A4.UJKj∈ A2中国（35）S.T. v1−。U ikδk+。U ijρ j≤Ms i（36）v2−。U jkδk+。U ijρi≤ Ms j<$j ∈ A2（37）约束条件（8）-（10）、（14）-（15）、（30）-（31）。（三十八）除了二进制变量，这个公式只包含线性约束和二次目标。5.2.3 O-PM-LMFM-III类似于O-NF-LMFM-III，该公式是通过重新公式化O-PM-LMFM-II中的每个多线性项而导出的在后者中，唯一的非线性是目标函数。因此，O-PM-LMFM-III只需对所有f F和j重新公式化它所包含的乘积δiρj即可获得A f，添加与我们添加到O-NF-LMFM-III的有效约束相同的有效约束。我们得到：Max..你好，我好。k∈ A4 i∈A1.U jky jk（三十九）