基于博弈論的關聯網絡攻防博弈分析

摘要： 根據現實中關聯網絡復雜的關聯特性和網絡中重要的評估指標，提出了5種不同的耦合方式，建立了9種關聯網絡模型；考慮到網絡中信息的傳輸，再分配和級聯故障，建立了基于介數虛擬流的級聯失效模型；基于博弈論，從復雜網絡的角度分析了關鍵基礎設施的攻防問題，分析了多種關聯網絡的魯棒性。發現了關聯網絡中博弈參與者的偏好，為基礎設施網絡的保護提供了決策支持。

關鍵詞： 復雜網絡；關聯網絡；攻防博弈；魯棒性分析

中圖分類號："""" O157.5；O225文獻標識碼： A

Attack-defense Game Analysis of Interdependent Networks Based on Game Theory

WANG Shuliang， SUN Jingya， BIAN Jiazhi，ZHANG Jianhua， DONG Qiqi， LI Junjing

（School of Electrical Engineering and Automation， Jiangsu Normal University， Xuzhou 221116，China）

Abstract：

According to the complex correlation characteristics of the actual interdependent network and the important evaluation indicators in the network， five different coupling methods are proposed， and nine interdependent network models are established. Considering the information transmission， redistribution and cascading failures in the network， a cascading failure model based on betweenness artificial flow models is established. We based on the game theory， attack-defense game problems of critical infrastructure are analyzed from the perspective of complex network， and the robustness of various interdependent networks is analyzed. We discovered the preferences of game participants in the interdependent networks， providing decision support for the protection of infrastructure networks.

Keywords：

complex network; interdependent network; attack-defense game; robustness analysis

0 引言

通信、電力、鐵路、能源系統等關鍵基礎設施系統在維護社會穩定中發揮著重要作用[1]。一旦這些設施受損將會對人民群眾生命財產安全造成嚴重的影響。所以，關鍵基礎設施網絡的保護問題成為近年來系統安全領域的熱門話題[2]。復雜網絡理論[3]為從整體角度研究關鍵基礎設施組件之間的交互提供了一種新方法，而博弈論[4]嚴格的數學基礎為模擬智能對手之間的對抗提供了適當的框架。

現有的復雜網絡研究[56]大多將復雜系統作為孤立的網絡來收集、建模和分析。然而，現實世界中的基礎設施系統網絡并不是孤立的，而是相互依賴的[7]。例如供水、運輸、燃料和發電站等不同基礎設施網絡相互耦合，這些相互依賴的網絡保障了人類的正常生活和國家的發展。但是這些關聯網絡往往非常脆弱[8]，其中任何一個網絡上的故障都可能會引發多米諾骨牌效應，進而導致整個系統崩潰[910]。Wu等[11]模擬了恐怖襲擊下相互依賴的基礎設施的級聯故障。MacKenzie等[12]分析了用于恢復相互依存系統的靜態和動態資源分配模型，并以深水地平線漏油事件為例進行了說明。Wang等[13]分析了相互依賴網絡上的過載行為，為現實世界中多個網絡組成的大規模網絡中因過載而產生的級聯故障問題提供了解決思路。馬海瑛等[14]建立了一種三層復雜網絡演化模型，并定義了隨機概率，定量刻畫多層網絡層間的依賴關系。

在過去的幾年里，相互依賴網絡中的攻防博弈引起了研究者的廣泛關注[1516]。Hausken等[17]研究了兩個目標之間的相互依賴概率以及多種系統特性對玩家努力的影響。Li等[18]針對關鍵基礎設施網絡中的蓄意攻擊提出了一種基于不完全信息博弈的兩個階段的聯合優化方法。Fu等[19]提出了考慮級聯效應影響的網絡攻防博弈模型，通過對節點進行分類，實現了博弈的重心從對節點決策到資源分配的轉變。Peng等[20]分析了在由相互依賴的子網絡組成的網絡上的攻防博弈中參與者的最優策略。

現有的研究大多從宏觀的角度分析關聯網絡的結構，很少綜合分析影響網絡的其他因素。實際上，不同的網絡耦合和采用不同的耦合方式得到的關聯網絡面對攻擊時會表現出不同的魯棒性。因此本文根據現實中的復雜網絡模型，研究了由不同類型的網絡組成的相互依賴網絡上的博弈情形。利用網絡博弈均衡收益的變化，分析了不同的網絡耦合、耦合策略下攻防雙方的偏好和網絡的魯棒性。

1 關聯網絡的建模

1.1 關聯網絡

網絡系統之間的互連創建了一個關聯網絡，其中相互的關聯關系在它們功能和性能方面發揮著重要作用。相互依賴的網絡之間的連通性對于整個系統的穩健性和魯棒性至關重要。連通性越高信息交換和對自然或人為災害的應急響應越快，網絡的魯棒性越強。不同依賴關系下的關聯網絡自身性能與抵御意外攻擊的能力也有所不同，本文根據網絡中的節點關系建立了相應的依賴關系，如圖1所示。

1.2 關聯方式

度值是目前描述節點重要性時使用較多的指標[21]，而介數是考慮虛擬流模型中很重要的一個參數，所以本文設置網絡A和網絡B的關聯方式為：

隨機耦合（Random Coupling，RC）：隨機選取網絡A中的節點與網絡B中的節點相互關聯；

度值正向耦合（Degree value Positive coupling，DPC）：將網絡A和網絡B中的節點按照度值進行正向排序后依次連接；

度值逆向耦合（Degree value Inverse coupling，DIC）：將網絡A和網絡B中的節點按照度值進行逆向排序后依次連接；

介數正向耦合（Betweenness Positive coupling，BPC）：將網絡A和網絡B中的節點按照介數值進行正向排序后依次連接；

介數逆向耦合（Betweenness Inverse coupling，BIC）：將網絡A和網絡B中的節點按照介數值進行逆向排序后依次連接。

2 網絡級聯失效模型

網絡基礎設施系統可以用簡單的無向圖G（V，E）來表示，其中V=v1，v2，…，vn是節點集合，節點數為V=n。E=e1，e2，…，enV×V，代表所有節點的邊集合。假設A（G）=（aij）N×N是G的鄰接矩陣，如果節點vi和vj相鄰，則有aij=aji=1，否則aij=aji=0。關聯網絡中的兩個子網絡分別為GA（VA，EA）和GB（VB，EB），其中VA=nA，VB=nB。

2.1 級聯失效模型

復雜網絡負載再分配模型主要包括3個因素：負載模型，容量模型和負載再分配機制[2223]。我們將介數虛擬流模型[24]擴展到由網絡A和B組成的相互依賴的網絡中。在網絡的初始階段，網絡上每個節點上的負載小于整個網絡處于穩定狀態的處理能力，設節點i上的初始負載Li為其介數值：

L（i）=2n（n－1）∑s≠t≠igst（i）gst（1）

其中，gst（i）為從節點vs到vt的所有最短路徑的數目，gst（i）為從節點vs到vt的gst條最短路徑中經過vt的最短路徑的數目。假設節點i的容量Ci與初始負載Li成正比[25]：

Ci=γLi（2）

其中，γ為容差參數，它決定了節點處理負載的能力。

在該模型中，當某個節點或某些節點發生故障時，會導致某些組件發生中斷，從而改變節點之間的最短路徑，接著導致所有線路之間的負載重新分配（見圖2a）。當網絡A中的節點5被攻擊并移除時，網絡B上對應的關聯節點1也被移除，故障后網絡中負載重新分配如（見圖2b），此時重分配后的網絡A上節點1的負載超過其容量，繼續發生故障，則網絡B中對應的節點2被移除。直到網絡中不存在超過其容量的節點，網絡達到平衡狀態，繼續穩定運行（見圖2c）。

2.2 魯棒性評估指標

網絡連通率是復雜網絡中維持各組件正常運行最基本的指標，其定義為網絡受損后最大連通子圖中包含的節點數與原有節點數之比：

LCC=n′n（3）

其中，n′為網絡受損后，其最大連通子圖中所含節點數。本文采取蓄意攻擊的方式來研究關聯網絡的魯棒性，其中蓄意攻擊采用節點度優先攻擊的方式。

3 攻防博弈模型

本文考慮的攻防博弈是一種完全信息的非零和靜態博弈[26]，完全信息在這里指的是每個參與人對其他參與人的特征，策略空間及支付函數完全了解，而靜態指的是同時行動的博弈，或者不同時但后行動者不知道之前行動者的決策。

3.1 博弈假設

針對本文的博弈模型做出以下假設：1） 只考慮一個攻擊者和一個防守者。實際上不論是多個攻擊者還是多個防御者，最終的決策目標通常都是選擇最優的結果。2） 所有的攻擊和防守行為均針對網絡中的節點。即攻擊者選取部分節點進行攻擊，防守者選取部分節點進行防守。當一個節點被成功攻擊后，節點上所連接的邊也隨之被移除。3） 當一個節點上的防御資源大于或者等于攻擊資源時，攻擊者針對此節點的攻擊視為無效，此節點依舊在網絡中發揮作用；當該節點上的防御資源小于攻擊資源時，這個節點就被成功攻擊，在網絡中該節點就被刪除。4） 攻防博弈只進行一輪。即攻擊者和防守者各自選定自己的策略，移除被成功攻擊的節點。然后計算雙方的收益，得到博弈的均衡。不考慮雙方在此基礎上繼續新一輪的博弈。

3.2 成本模型

攻擊者的目的是通過攻擊網絡中的部分節點達到網絡破壞的最大化，防御者通過對節點的資源投入盡可能地維持系統的正常運行。但是不論是攻擊還是防御，針對節點采取措施必然會消耗一定的資源或者付出一定的代價，即：

cAi=rqAi，cDi=rqDi（4）

其中，ri≥0，ri為節點的參考屬性，本文將ri設為節點的介數值。cAi（cDi）表示節點vi的攻擊（防御）成本，其中qA，qD（gt;0）表示攻擊（防御）成本敏感參數。

3.3 博弈策略

假設VAV是關聯網絡中被攻擊的節點集，攻擊策略X=x1，x2，…，xn∈SA，其中SA為攻擊者的策略集。如果節點vi被成功攻擊，則xi=1，即vi∈VA，否則xi=0。

設CX為攻擊方采取策略X時的總成本，定義為

CX=∑vi∈VACAi=∑ni=1xiCAi=∑ni=1xiαrqAi（5）

因此，可使用的攻擊資源為CA，則資源預算限制為

CX=∑ni=1xiαrqAi≤CA（6）

對于理性的攻擊者來說，攻擊絕對不是一次性的事件。而是要考慮到攻擊失敗的資源消耗并為下次的攻擊做準備。所以為了保證每一次攻擊達到資源的有效利用，應該確定每輪具體的操作節點比，定義攻擊者攻擊節點的比例限制為pA：

∑vi∈VAvin=∑ni=1xin≤pA（7）

VDV是關聯網絡中被防御的節點集合，防御策略Y=y1，y2，…，yn∈SD。當yi=1時，節點vi被成功防御。防御者在策略Y下的總成本為

CY=∑vi∈VDCDi=∑ni=1yiCDi=∑ni=1yiβrqDi（8）

可使用的攻擊資源為CD，資源預算限制為

CY=∑ni=1yiβrqAi≤CD（9）

對于處于弱勢并且希望盡可能保證網絡正常運行的防御方來說，一些至關重要的目標必須考慮資源的投入以及必要數量的節點被保護，所以防御方采取保護策略的節點比例限制為pD：

∑vi∈VDvin=∑ni=1yin≥pD（10）

3.4 博弈收益

當一個沒有防御的節點受到攻擊時，它就會被從網絡中移除，也就是說當xi=1，yi=0時，節點被移除。假設被移除的節點集是V＾V，因此，移除節點之后的網絡是G＾=（V－V＾，E＾）。則可知攻擊者的收益為

UA（X，Y）=P（G＾A）2P（GA）+P（G＾B）2P（GB）（11）

其中，Γ表示網絡性能度量函數，本文考慮介數虛擬流下的網絡級聯失效，所以將網絡故障前后所有節點的流量之和作為博弈的收益。同理當所有被攻擊的節點在無防御的情況下被移除時，網絡可表示為G＾=（V－VA，E～），則防御者的收益為

UD（X，Y）=P（G＾A）2P（GA）expP（G＾A）－P（A）2P（GA）+P（G＾B）2P（GB）expP（G＾B）－P（B）2P（GB）（12）

3.5 納什均衡求解方法

由博弈論的知識可知，靜態博弈不存在純策略的均衡解[27]，而博弈中的混合策略納什均衡求解方法主要有線性規劃算法[28]，Lemake-Howson方法[29]和Porter-Nudelman-Shoham （PNS）[30]方法等。但逐一分析求解計算量過大且耗時過長，基于實際理性的決策者對于博弈的執行一般都會遵循一定的規律與法則，例如目標的重要性，目標的位置以及執行成功的概率等。所以本文只考慮兩種常用的策略：隨機策略和介數策略。詳細來說就是：隨機攻擊策略（Random Attack Strategy，RAS）、介數攻擊策略（Betweenness Attack Strategy，BAS）；隨機防御策略（Random Defense Strategy，RDS）、介數防御策略（Betweenness Defense Strategy，BDS）。因此可得所有策略配置下的攻防收益矩陣為圖3，uij表示攻擊者選擇策略i，防御者選擇策略j。

對于本文所討論的有限節點的博弈，納什早在1950年已經證實：在任何有限博弈中，都存在至少一個納什均衡，不是混合策略納什均衡，就是純策略納什均衡[31]。由于本研究在每輪博弈中限制了操作節點比例pA（pD），對于均衡的計算采用線性規劃算法。隨機策略下的策略組合可能會不同，則收益也不同，每次博弈的結果就會不同。為了消除隨機因素對均衡的影響，獨立重復1 000次得到平均收益下的納什均衡結果。

4 數值分析

4.1 網絡關聯的魯棒性分析

為了量化不同網絡耦合和不同耦合方式下的關聯網絡的魯棒性，本文選取了節點數nA=nB=1 000的3種類型網絡：無標度網絡（BA），小世界網絡（WS）和隨機網絡（ER）。分別通過5種關聯方式進行耦合得到了9種關聯網絡：BA-BA、BA-ER、BA-WS、ER-BA、WS-BA、ER-ER、ER-WS、WS-ER和WS-WS。本文模擬了9種關聯網絡在蓄意攻擊下網絡連通率LCC的變化，仿真結果如圖4所示。

從網絡類型的角度看，當兩種相同類型的網絡關聯時，BA-BA網絡在攻擊次數達到140時幾乎完全崩潰，ER-ER網絡緊隨其后，網絡崩潰的攻擊次數為250，WS-WS網絡表現出較強的魯棒性，直到攻擊次數達到800時仍然有部分節點正常工作。一個十分有趣的現象是即使同樣兩個網絡關聯，但是魯棒性的變現卻有所差異。例如在BA-ER網絡和ER-BA網絡中，當攻擊次數達到140時，BA-ER網絡完全陷入癱瘓， ER-BA網絡卻仍有大量節點在進行信息傳輸。具有這樣相似表現的還有WS-BA網絡，ER-WS網絡。

從關聯方式的角度看，大多數情況下，DPC和BPC關聯方式下的網絡魯棒性較差，RC緊隨其后，DIC和BIC關聯方式下的網絡能夠抵御多次的蓄意攻擊。這是因為DPC和BPC兩種關聯方式都將網絡中高重要度的節點進行連接，一旦這樣的節點故障，所關聯的子團中必然包含大量節點，子團中的節點相繼失效，就造成了網絡大規模的崩潰。

4.2 均衡收益分析

為了探究關聯網絡中關聯方式對網絡博弈均衡收益的影響，在兩個子網絡均為nA=nB=200的無標度網絡上進行了攻防博弈。博弈參數分別設置為：qA=qD=α=β=0.5，CA=CD=10 000，γ=1.5，得到了如圖5所示的攻防雙方均衡收益圖。

從攻擊者的視角看，當pA=pD=0.1時，網絡中小部分節點遭到破壞，此時網絡中級聯失效的現象最嚴重，攻擊者更傾向于在此時采取行動，達到網絡破壞效果的最優。在RC關聯下的網絡中一度達到了0.62，DIC關聯下的網絡緊隨其后為0.38，BIC關聯下的網絡均衡收益僅為0.23。這是由于此時的操作節點比例pA和pD較小，只在部分關鍵節點上投入了保護性資源。

從防御者的視角可以發現，在網絡中發揮重要作用的節點相互關聯不僅增強了網絡中的信息傳輸，網絡的脆弱性也隨之增加（見圖4）。一旦網絡故障則是崩潰性的，所以防御者對于DPC和BPC關聯下的網絡需要更加關注，防御性資源也需要盡可能達到精準投入，為網絡的高效穩定運行提供必要的保障。

4.3 容忍系數分析

如圖6所示，本文探究了不同容忍系數下關聯網絡的均衡收益差異，對比了不同操作節點下攻防雙方的行動偏好。兩個子網絡均為nA=nB=200的無標度網絡關聯，博弈參數分別設置為：qA=qD=α=β=0.5，CA=CD=10 000，令pA=pD=p。

當γlt;1.2且p較小時，均衡收益的下降速率較大，γgt;1.2后處于一個相對較為穩定的狀態。這意味著γlt;1.2時的關聯網絡非常脆弱，任何節點故障都會導致崩潰。隨著γ值的增加，節點容量的增加，網絡即使遭到攻擊，造成的級聯失效影響也較小，不會影響大部分節點的正常運行。但是當p=0.05和p=0.07時，操作節點數量的增加提高了防御者的地位，使其面對攻擊者的策略時有正確的判斷，資源投入的準確性上升，降低了網絡破壞的規模，自然收益低于p較小時。

5 結論

為了探究關聯方式和網絡類型對網絡魯棒性和攻防博弈均衡的影響，本文提出了關聯網絡攻防博弈模型，對比了5種關聯方式下的9種關聯網絡的魯棒性，分析了容忍系數和關聯方式對均衡收益的影響。通過理論分析和仿真驗證得如下結論：1） 通過度值正向耦合和介數正向耦合得到的關聯網絡的網絡魯棒性較差，即使同樣兩個網絡關聯，但魯棒性的表現也有所差異;2） 操作節點比例較小時，隨機耦合和逆向耦合策略下的關聯網絡更加受到攻擊者的青睞;3） 容忍系數較小時的關聯網絡較為脆弱，隨著容忍系數的增大，網絡中級聯失效發生的概率減小。

參考文獻：

[1]ALCARAZ C， ZEADALLY S. Critical infrastructure protection： Requirements and challenges for the 21st century[J]. International journal of critical infrastructure protection， 2015， 8： 5366.

[2]卿斯漢.關鍵基礎設施安全防護[J].信息網絡安全，2015（2）：16.QING S H. Security protection of critical infrastructure[J]. Netinfo Security， 2015（2）：16.

[3]劉濤，陳忠，陳曉榮.復雜網絡理論及其應用研究概述[J].系統工程，2005，23（6）：17.

LIU T， CHEN Z， CHEN X R. Overview of complex network theory and its application research [J]. Systems Engineering，2005，23（6）：17.

[4]郭鵬，楊曉琴.博弈論與納什均衡[J].哈爾濱師范大學自然科學學報，2006，22（4）：2528.

GUO P， YANG X Q. Game theory and Nash equilibrium [J]. Journal of Natural Sciences， Harbin Normal University， 2006，22（4）： 2528.

[5]周濤，柏文潔，汪秉宏，等.復雜網絡研究概述[J].物理，2005，34（1）：3136.

ZHOU T， BAI W J， WANG B H， et al. A brief review of complex networks[J]. Physics， 2005，34（1）： 3136.

[6]王哲，李建華，康東，等.復雜網絡魯棒性增強策略研究綜述[J].復雜系統與復雜性科學，2020，17（3）：126.

Wang Z， LI J H，KANG D， et al. Review strategies enhance the robustness of complex network[J]. Complex Systems and Complexity Science， 2020，17（03）：126.

[7]RINALDI S M， PEERENBOOM J P， KELLY T K. Identifying， understanding， and analyzing critical infrastructure interdependencies[J]. IEEE Control Systems Magazine， 2001， 21（6）： 1125.

[8]NOCHENSON A， HEIMANN C F L. Simulation and game-theoretic analysis of an attacker-defender game[C]//Decision and Game Theory for Security： Third International Conference， GameSec 2012， Budapest， Hungary， 2012： 138151.

[9]VESPIGNANI A. Complex networks： the fragility of interdependency[J]. Nature， 2010， 464：984985.

[10] 董政呈，方彥軍，田猛.相互依存網絡抗毀性研究綜述[J].復雜系統與復雜性科學，2017，14（3）：3044.

DONG Z C， FANG Y J， TIAN M， Review on vulnerability of interdependent networks[J]. Complex Systems and Complexity Science， 2017，14（3）：3044.

[11] WU D， XIAO H， PENG R. Object defense with preventive strike and 1 targets[J]. Reliability Engineering amp; System Safety， 2018， 169： 7680.

[12] MACKENZIE C A， BAROUD H， BARKER K. Static and dynamic resource allocation models for recovery of interdependent systems： application to the Deepwater Horizon oil spill[J]. Annals of Operations Research， 2016， 236（1）： 103129.

[13] WANG N， JIN Z Y， ZHAO J. Cascading failures of overload behaviors on interdependent networks[J]. Physica A： Statistical Mechanics and its Applications， 2021， 574： 125989.

[14] 馬海瑛，肖玉芝，趙海興，等.三層復雜網絡模型構建及特性分析[J].復雜系統與復雜性科學，2020，17（4）：1629.

MA H Y， XIAO Y Z， ZHAO H X， et al. Three-Layer complex network model construction and characteristic analysis[J]. Complex Systems and Complexity Science， 2020，17（4）：1629.

[15] HOTA A R， SUNDARAM S. Interdependent security games on networks under behavioral probability weighting[J]. IEEE Transactions on Control of Network Systems，2016，5（1）： 262273.

[16] 徐云程，胡華，孫小軍.三層無標度關聯網絡協同傳播模型閾值研究[J].復雜系統與復雜性科學，2021，18（3）：18.

XU Y C， HU H， SUN X J， Research on threshold of cooperative propagation model of three-layer scale-free associative network[J]. Complex Systems and Complexity Science， 2021，18（3）：18.

[17] HAUSKEN K， LEVITIN G. Minmax defense strategy for complex multi-state systems[J]. Reliability Engineering amp; System Safety， 2009， 94（2）： 577587.

[18] LI Y， LIN J， ZHANG C， et al. Joint optimization of structure and protection of interdependent infrastructure networks[J]. Reliability Engineering amp; System Safety， 2022， 218： 108163.

[19] FU C Q， GAO Y J， ZHONG J L， et al. Attack-defense game for critical infrastructure considering the cascade effect[J]. Reliability Engineering amp; System Safety， 2021， 216： 107958.

[20] PENG R， WU D， SUN M， et al. An attack-defense game on interdependent networks[J]. Journal of the Operational Research Society， 2021， 72（10）： 23312341.

[21] 任曉龍，呂琳媛.網絡重要節點排序方法綜述[J].科學通報，2014，59（13）：11751197.

REN X L， L L Y. Review of ranking nodes in complex networks[J]. Chinese Science Bulletin， 2014，59（13）：11751197.

[22] 張強，曹軍海，宋太亮，等.裝備保障網絡中考慮負載再分配的級聯失效分析[J].兵器裝備工程學報，2021，42（6）：8690.

ZHANG Q， CAO J H，SONG T L， et al. Cascading failure analysis considering load redistribution in equipment support network[J]. Journal of Ordnance Equipment Engineering， 2021，42（6）：8690.

[23] 種鵬云，尹惠.蓄意攻擊策略下危險品運輸網絡級聯失效仿真[J].復雜系統與復雜性科學，2018，15（1）：4555.

ZHONG P Y， YIN H， Simulation of cascading failures on hazardous material transportation networks under targeted attack[J]. Complex Systems and Complexity Science， 2018，15（1）：4555.

[24] OUYANG M. Comparisons of purely topological model， betweenness based model and direct current power flow model to analyze power grid vulnerability[J]. Chaos： An Interdisciplinary Journal of Nonlinear Science， 2013， 23（2）： 023114.

[25] CRUCITTI P， LATORA V， MARCHIORI M. Model for cascading failures in complex networks[J]. Physical Review E， 2004， 69（4）： 045104.

[26] 王家輝.博弈論中的\"囚徒困境\"模型[J].統計與決策，2005（8）：1920.

WANG J H. The \"prisoner′s dilemma\" model in game theory[J]. Statistics and Decision Making， 2005（8）：1920.

[27] ZHANG C， RAMIREZ-MARQUEZ J E， WANG J. Critical infrastructure protection using secrecy-a discrete simultaneous game[J]. European Journal of Operational Research， 2015， 242（1）： 212221.

[28] TARDOS E， VAZIRANI V V. Basic solution concepts and computational issues[DB/OL]. [20220315] https：//www.cs.cornell.edu/～eva/agtchap1.pdf.

[29] LEMKE C E， HOWSON， J T J. Equilibrium points of bimatrix games[J]. Journal of the Society for Industrial and Applied Mathematics， 1964， 12（2）： 413423.

[30] PORTER R， NUDELMAN E， SHOHAM Y. Simple search methods for finding a nash equilibrium[J]. Games and Economic Behavior， 2008， 63（2）： 642662.

[31] NASH J F. Equilibrium points in n-person games[J]. Proceedings of the National Academy of Sciences， 1950， 36（1）： 4849.

（責任編輯 耿金花）