許 月，謝 歆

（1.安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001；2.黃山學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，安徽 黃山 245041）

經(jīng)濟(jì)博弈[1]最具代表性的市場(chǎng)結(jié)構(gòu)是寡頭壟斷。它是少數(shù)幾家大廠商占整個(gè)行業(yè)的絕大部分產(chǎn)量，并且相互依賴。所有廠商均在假定競(jìng)爭(zhēng)對(duì)手行為最優(yōu)條件下，采取使自己收益最大化的策略，來達(dá)到寡頭壟斷市場(chǎng)的均衡——納什均衡[2]。納什均衡所對(duì)應(yīng)的一組決策，稱為納什均衡點(diǎn)，它是衡量博弈網(wǎng)絡(luò)中穩(wěn)定的一個(gè)重要標(biāo)準(zhǔn)。

通過鞍點(diǎn)優(yōu)化方法[3]在經(jīng)濟(jì)博弈中找到納什均衡[4-5]，是一條新蹊徑。鞍點(diǎn)方法是一種原始對(duì)偶方法，通過交替更新決策變量（原變量）和拉格朗日乘子變量（對(duì)偶變量）有效地處理優(yōu)化問題的等式或不等式約束：

式中：xt和λt是第t次迭代的原變量和對(duì)偶變量；?xL(xt,λt)和 ?λL(xt,λt)表示對(duì)函數(shù)L(xt,λt)分別求x和λ偏導(dǎo)；αt為迭代的步長(zhǎng)；PX表示將值[xt-αt?xL(xt,λt)]投影到集合X上，其中X={x1,x2,…,xT}；[·]+為取正實(shí)數(shù)。運(yùn)用鞍點(diǎn)方法的思想，找出一組原變量和對(duì)偶變量(x,λ)，其中x和λ依據(jù)在線梯度下降法更新迭代。而[6]是在[3]的算法基礎(chǔ)上證明該算法的遺憾界不大于（T為迭代次數(shù)）[6]。不同的是，SP-FTL(saddle-point follow-theleader)[7]算法是求解經(jīng)過拉格朗日對(duì)偶變換的回報(bào)函數(shù)累計(jì)和的鞍點(diǎn)值，即納什均衡點(diǎn)作為這個(gè)“l(fā)eader”來進(jìn)行 (x,λ)迭代，并且驗(yàn)證了 SP-Regret和Ind-Regret不能同時(shí)達(dá)到次線性遺憾。跟隨領(lǐng)導(dǎo)者算法(FTL)決策更新依賴于初始“l(fā)eader”，算法如下：

其中：xt+1表示t+1時(shí)刻的決策變量；τ為[1,t]之間的時(shí)間變量；表示總收益函數(shù)。

在[7]的基礎(chǔ)上將SP-FTL算法應(yīng)用經(jīng)濟(jì)博弈中，并且加上正則化項(xiàng)以達(dá)到穩(wěn)定決策的目的。由于在線凸優(yōu)化算法[8]只涉及一個(gè)優(yōu)化對(duì)象，而在線鞍點(diǎn)優(yōu)化涉及兩個(gè)如(1)式的(x,λ)，所以在線凸優(yōu)化框架可以看作是在線鞍點(diǎn)問題的一個(gè)特例。不僅如此，將上述鞍點(diǎn)優(yōu)化算法置于在線環(huán)境[9]下，得到算法OSP-RFTL(online saddle-point regularization follow-the-leader)，并驗(yàn)證了算法的有效性。為了進(jìn)一步模擬真實(shí)的經(jīng)濟(jì)網(wǎng)絡(luò)，需要考慮存在一些不穩(wěn)定因素，如Byzantine故障，完全壟斷市場(chǎng)的廠商被看成是破壞納什均衡的Byzantine故障[10]（即惡意攻擊點(diǎn)）。其原始問題是Byzantine將軍問題：愛國(guó)的將軍為不被叛國(guó)將軍破壞行動(dòng)而要達(dá)成一致。Byzantine容錯(cuò)的目的是能夠抵御故障，在滿足整個(gè)經(jīng)濟(jì)市場(chǎng)穩(wěn)定的同時(shí)允許出現(xiàn)這樣帶有攻擊性的廠商最大數(shù)量。

1 問題建立

問題一：鞍點(diǎn)優(yōu)化算法與博弈決策選擇的等價(jià)性建立。

定義由{1,2,…,N}個(gè)體構(gòu)成的多個(gè)體網(wǎng)絡(luò)[11]，這些個(gè)體在寡頭壟斷的經(jīng)濟(jì)市場(chǎng)下視為競(jìng)爭(zhēng)廠商，選擇滿足納什均衡的決策：

其中：xt+1，yt+1分別表示在t+1時(shí)刻原變量和對(duì)偶變量；表示累積收益。為使得整個(gè)網(wǎng)絡(luò)穩(wěn)定，每次的決策希望能夠在給定的范圍內(nèi)波動(dòng)。

問題二：優(yōu)化算法性能的衡量。

鞍點(diǎn)遺憾RgtSP表示累積收益與總收益函數(shù)的差值，其最小化定義為

在線鞍點(diǎn)問題的目標(biāo)是共同選擇雙方的決策，使雙方的收益都接近納什均衡。此外，當(dāng)一次只優(yōu)化一方的收益時(shí)，標(biāo)準(zhǔn)的在線凸優(yōu)化環(huán)境適用于在線鞍點(diǎn)問題。具體來說，將雙方的個(gè)人遺憾定義為：

本文的目標(biāo)是在每次迭代中為雙方共同選擇一組決策，使每一方在最后的累積收益盡可能接近于總博弈的納什均衡(即鞍點(diǎn))。

問題三：算法推廣到Byzantine環(huán)境下應(yīng)用目的。

當(dāng)寡頭市場(chǎng)中出現(xiàn)敵意廠商，政府如何及時(shí)有效地介入市場(chǎng)控制壟斷現(xiàn)狀呢？

2 算法介紹

2.1 預(yù)備知識(shí)

若函數(shù)L(x,y)是凸-凹的，X={x1,x2,…,xT}，Y={y1,y2,…,yT}對(duì)任何原變量x∈X和對(duì)偶變量y∈Y，收益函數(shù)L的鞍點(diǎn)(x*,y*)滿足

若f是關(guān)于X→R的H-強(qiáng)凸的，有下列式子成立：

這里，?f(x)表示f在x處的次梯度。強(qiáng)凸性意味著最小化問題f(x)有唯一解。同樣地，如果L是H-強(qiáng)凸凹的，那么存在唯一鞍點(diǎn)(x*,y*)。

2.2 假設(shè)條件

假設(shè)1 個(gè)體所在網(wǎng)絡(luò)由{1,2,…,N}構(gòu)成的全耦合網(wǎng)絡(luò)。

假設(shè)2 {Lt,(p,q)(x,y)}為個(gè)體p與q在t時(shí)刻的收益函數(shù)，x，y分別為p和q對(duì)應(yīng)的決策變量，p,q∈(1,2,…,N)且(p,q)=(q,p),p≠q。{Lt,(p,q)(x,y)}是一系列H-強(qiáng)凸凹的并且滿足G-Lipschitz的函數(shù)。

假設(shè)3 為了阻止廠商的惡意計(jì)劃，所有廠商都直接相互交換信息。

2.3 在線鞍點(diǎn)FTL算法

OSP-FTL依據(jù)以下規(guī)則進(jìn)行迭代更新：

2.4 FTL算法——決策正則化

令決策變量x∈[-1,1]，，并且對(duì)對(duì)迭代次數(shù)τ=2,…T時(shí)，讓fτ在-x和x間交替變換。因此，

可以看出決策將在xt=-1和xt=1之間變化，這樣的決策是不穩(wěn)定的。修改FTL方法，引入正則化[8]，使其不會(huì)頻繁改變決策，從而降低的遺憾。

OSP-RFTL依據(jù)(11)式進(jìn)行迭代更新

2.5 OSP-RFTL算法的應(yīng)用

2.5.1 Byzantine容錯(cuò)思想的引入

如圖1，惡意節(jié)點(diǎn)C給A發(fā)送值9，給B發(fā)送值12，A計(jì)算中位數(shù){9,10,11}=10，B計(jì)算中位數(shù){10,11,12}=11，C的攻擊行為導(dǎo)致A，B計(jì)算結(jié)果不一致。若有f個(gè)廠商想要壟斷，能使得市場(chǎng)處于均衡狀態(tài)的總廠商數(shù)量是未知的。

圖1 節(jié)點(diǎn)交流輸出中位數(shù)

2.5.2 3f+1容錯(cuò)思想在政府反壟斷中的應(yīng)用

為了容納一個(gè)錯(cuò)誤結(jié)點(diǎn)，不防設(shè)個(gè)體1為惡意結(jié)點(diǎn)，總共有4個(gè)結(jié)點(diǎn)，如圖2。個(gè)體1因?yàn)楣餐瑓f(xié)議不能滿足個(gè)人需求，暗自更改決策更新規(guī)則?！?”表示表面與其他廠商約定的決策更新規(guī)則與背地里的更新規(guī)則不一致。

圖2 廠商交流網(wǎng)絡(luò)示意圖

2.5.3 OSP-RFTL算法的推廣

把意圖想要完全壟斷市場(chǎng)的廠商看成是有Byzantine故障的（惡意攻擊的個(gè)體），即上述(12)式的*所表示的含義，*的右邊表示的是向量，滿足使他個(gè)人達(dá)到最優(yōu)情況的集合：要么取得最小值，要么取得最大值。如果該廠商謀取成功，那么當(dāng)前迭代值取自這樣特定的集合的任意值；如果未取得成功，隨著時(shí)間的推移，廠商將重新回到與其他廠商相互制約的均衡狀態(tài)。這樣就得到了算法BOSP-RFTL(Byzantine online saddle-point regularization follow-the-leader)。具體如算法1。

算法1 BOSP-RFTL算法1：初始化 xt，f=0，[m]2：for t={0,1,…,T}do 3：所有個(gè)體對(duì)外發(fā)送“合作”信號(hào)4：for all i∈[m]do in parallel 5：更新xt+1←arg min x max M∑L(x,M)，其中M=[m]/i 6：ifL(xt+1)≤ε//判斷協(xié)議能不能讓該廠商滿意//若不滿意，就會(huì)按照自己意愿設(shè)定價(jià)格7：重新更新迭代規(guī)則：xt+1←arg max∑L(xt)8：輸出“該個(gè)體i攻擊點(diǎn)”9：攻擊點(diǎn)計(jì)數(shù)f=f+1 10：else輸出“該個(gè)體i正?！?1：end for 12：if 3f+1≤[m]13：輸出經(jīng)濟(jì)市場(chǎng)均衡14：else政府需介入進(jìn)行反壟斷操作15：end for

顯然，該算法的時(shí)間復(fù)雜度為O(T)。

3 收斂性分析

驗(yàn)證加入正則化的鞍點(diǎn)遺憾是否仍能達(dá)到次線性遺憾界，證明見文獻(xiàn)[7]數(shù)學(xué)歸納法。

引理1

其中，G為L(zhǎng)ipschitz連續(xù)常數(shù)。

定理1

4 仿真實(shí)驗(yàn)分析

數(shù)值仿真函數(shù)如下

Lt,(p,q)(x,y)表示收益函數(shù)，該函數(shù)具有時(shí)變性。設(shè)定迭代次數(shù)T，x和y初始狀態(tài)值從（0,1）隨機(jī)選取，由t=1開始，x和y根據(jù)FTL算法達(dá)到鞍點(diǎn)值。

沒有加入正則化之前，鞍點(diǎn)優(yōu)化算法的收斂性為：鞍點(diǎn)遺憾能夠達(dá)到次線性而有個(gè)體遺憾只能夠達(dá)到線性，如圖3。因此，鞍點(diǎn)遺憾和個(gè)體遺憾仍不能同時(shí)達(dá)到次線性。正如公式(11)所示，本正則項(xiàng)R（x,y）=正則化參數(shù)用于控制兩個(gè)目標(biāo)的平衡關(guān)系：在最小化訓(xùn)練誤差的同時(shí)正則化參數(shù)能使模型簡(jiǎn)單。這里取α1和α2的值為由圖4可知，遺憾接近次線性，并且最后能夠趨向平穩(wěn)。

由圖5（a)可看出，兩個(gè)體間的相互決策結(jié)果的納什均衡在不同時(shí)刻值都不一樣。

圖3 鞍點(diǎn)遺憾和個(gè)體遺憾

圖4 正則化后的遺憾

加入正則化后，相互協(xié)商的兩個(gè)體決策變量穩(wěn)定在一定的范圍內(nèi)。仿真中給決策x加入0.9倍的L2范數(shù)。由圖5(b)可以看出，x在值2上下波動(dòng)。給決策y加入0.1倍的L2范數(shù)，同樣可看出y在0.6上下波動(dòng)。這里給出正則項(xiàng)前面不同的系數(shù)，以便比較觀察正則化的影響。通過加入正則項(xiàng)，納什均衡可以隨著時(shí)間推移穩(wěn)定在一定范圍內(nèi)波動(dòng)。

圖5 決策狀態(tài)圖 (a)正則化前；(b)正則化后

5 小結(jié)

本文把近年來在線鞍點(diǎn)問題的研究成果應(yīng)用到經(jīng)濟(jì)博弈中，提出了追隨領(lǐng)導(dǎo)者算法來解決這類決策優(yōu)化問題，并加入正則化以穩(wěn)定決策，最后給出了納什均衡決策的穩(wěn)定性狀態(tài)分析，并將Byzantine容錯(cuò)思想應(yīng)用到政府反壟斷實(shí)際中。結(jié)合近幾年來對(duì)Byzantine故障容錯(cuò)的研究，3f+1的方法可以更具有彈性，選有檢查點(diǎn)[12]，沒有故障時(shí)，只需f+1個(gè)結(jié)點(diǎn)即可。下一步工作是將算法應(yīng)用于實(shí)際市場(chǎng)，進(jìn)行有效地監(jiān)測(cè)使用，更好地便于政府反壟斷控制。