耿方興，李卓*，陳昕

基于多領(lǐng)導(dǎo)者Stackelberg博弈的分層聯(lián)邦學(xué)習(xí)激勵(lì)機(jī)制設(shè)計(jì)

耿方興1，2，李卓1，2*，陳昕2

（1.網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點(diǎn)實(shí)驗(yàn)室（北京信息科技大學(xué)），北京 100101； 2.北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京 100101）（ ? 通信作者電子郵箱lizhuo@bistu.edu.cn）

分層聯(lián)邦學(xué)習(xí)中隱私安全與資源消耗等問題的存在降低了參與者的積極性。為鼓勵(lì)足夠多的參與者積極參與學(xué)習(xí)任務(wù)，并針對多移動(dòng)設(shè)備與多邊緣服務(wù)器之間的決策問題，提出基于多領(lǐng)導(dǎo)者Stackelberg博弈的激勵(lì)機(jī)制。首先，通過量化移動(dòng)設(shè)備的成本效用與邊緣服務(wù)器的支付報(bào)酬，構(gòu)建效用函數(shù)并定義最優(yōu)化問題；其次，將移動(dòng)設(shè)備之間的交互建模為演化博弈，將邊緣服務(wù)器之間的交互建模為非合作博弈。為求解最優(yōu)邊緣服務(wù)器選擇和定價(jià)策略，提出多輪迭代邊緣服務(wù)器選擇算法（MIES）和梯度迭代定價(jià)算法（GIPA），前者用于求解移動(dòng)設(shè)備之間的演化博弈均衡解，后者用于求解邊緣服務(wù)器之間的定價(jià)競爭問題。實(shí)驗(yàn)結(jié)果表明，所提算法GIPA與最優(yōu)定價(jià)預(yù)測策略（OPPS）、歷史最優(yōu)定價(jià)策略（HOPS）和隨機(jī)定價(jià)策略（RPS）相比，可使邊緣服務(wù)器的平均效用分別提高4.06%、10.08%和31.39%。

分層聯(lián)邦學(xué)習(xí)；激勵(lì)機(jī)制；定價(jià)策略；多領(lǐng)導(dǎo)者Stackelberg博弈；演化博弈

0 引言

隨著移動(dòng)設(shè)備的普及和網(wǎng)絡(luò)程序的廣泛應(yīng)用，私人數(shù)據(jù)量呈爆炸式增長。得益于服務(wù)器計(jì)算能力與存儲(chǔ)容量的提升，大數(shù)據(jù)驅(qū)動(dòng)的機(jī)器學(xué)習(xí)方法能夠?qū)崿F(xiàn)大規(guī)模的集中式訓(xùn)練，該方法通過大量移動(dòng)設(shè)備將本地?cái)?shù)據(jù)上傳至云服務(wù)器，完成全局模型的訓(xùn)練。然而，移動(dòng)設(shè)備所產(chǎn)生的本地?cái)?shù)據(jù)中通常包含重要的私人信息，一旦此類數(shù)據(jù)泄露［1］或被用于預(yù)期以外的目的，用戶隱私將受到損害。鑒于上述存在的數(shù)據(jù)安全隱患，用戶不愿將私人數(shù)據(jù)共享至云服務(wù)器。為解決集中式訓(xùn)練存在的數(shù)據(jù)安全問題，聯(lián)邦學(xué)習(xí)［2］應(yīng)運(yùn)而生。聯(lián)邦學(xué)習(xí)的分布式設(shè)計(jì)使得所有的訓(xùn)練數(shù)據(jù)保存在設(shè)備本地，移動(dòng)設(shè)備基于模型所有者發(fā)布的模型，在本地完成參數(shù)更新，實(shí)現(xiàn)模型的協(xié)同訓(xùn)練。

為達(dá)到預(yù)期的模型精度，聯(lián)邦學(xué)習(xí)中的大量模型參數(shù)需要通過復(fù)雜的網(wǎng)絡(luò)環(huán)境進(jìn)行多輪次的數(shù)據(jù)傳輸，因此移動(dòng)設(shè)備面臨著網(wǎng)絡(luò)擁塞和通信故障的問題。針對上述問題，研究人員提出分層聯(lián)邦學(xué)習(xí)框架［3］，其中移動(dòng)設(shè)備不直接將本地模型上傳至云端而是上傳至邊緣服務(wù)器。邊緣服務(wù)器作為中轉(zhuǎn)站，聚合移動(dòng)設(shè)備的模型參數(shù)，并上傳至云端實(shí)現(xiàn)全局模型的聚合。

在分層聯(lián)邦學(xué)習(xí)過程中，當(dāng)移動(dòng)設(shè)備參與學(xué)習(xí)任務(wù)時(shí)，不可避免地會(huì)消耗設(shè)備資源，包括計(jì)算、通信資源等。因此移動(dòng)設(shè)備無償?shù)刎暙I(xiàn)資源是不切實(shí)際的；同時(shí)分層聯(lián)邦學(xué)習(xí)框架仍然面臨各種安全風(fēng)險(xiǎn)，如惡意節(jié)點(diǎn)可以通過中間梯度推斷訓(xùn)練數(shù)據(jù)的重要信息、邊緣服務(wù)器也可通過生成的對抗網(wǎng)絡(luò)學(xué)習(xí)客戶訓(xùn)練數(shù)據(jù)的私人信息［4］。由于這些風(fēng)險(xiǎn)與參與分層聯(lián)邦學(xué)習(xí)任務(wù)成本的增加，如果沒有足夠的補(bǔ)償，移動(dòng)設(shè)備可能不愿意參與并上傳訓(xùn)練后的模型參數(shù)。因此，為促進(jìn)分層聯(lián)邦學(xué)習(xí)的持續(xù)發(fā)展需要設(shè)計(jì)有效的激勵(lì)機(jī)制。

目前基于分層聯(lián)邦學(xué)習(xí)的激勵(lì)機(jī)制研究中存在的問題主要包括：

1）現(xiàn)有的部分聯(lián)邦學(xué)習(xí)研究中，參與者是完全理性的［5-7］，但這種假設(shè)并不符合實(shí)際，因?yàn)橐苿?dòng)設(shè)備的地理位置與網(wǎng)絡(luò)擁塞情況都會(huì)影響參與者獲取信息的速度和信息完整性。同時(shí)由于邊緣服務(wù)器給予的報(bào)酬有限，使得移動(dòng)設(shè)備之間存在競爭關(guān)系。因此如何建立設(shè)備之間的博弈模型，求解出移動(dòng)設(shè)備的最優(yōu)選擇策略是當(dāng)前存在的問題。

2）移動(dòng)設(shè)備通過貢獻(xiàn)自身的數(shù)據(jù)和計(jì)算資源獲得報(bào)酬，同時(shí)邊緣服務(wù)器也可通過購買移動(dòng)設(shè)備的資源訓(xùn)練出高質(zhì)量的模型，獲得更高的收益。而移動(dòng)設(shè)備提供的資源有限，因此邊緣服務(wù)器之間存在競爭關(guān)系，如何建立一個(gè)合理的博弈模型，求解各方都滿意的定價(jià)策略，也是當(dāng)前存在的問題。

針對上述問題，本文將移動(dòng)設(shè)備之間的交互構(gòu)建為演化博弈，同時(shí)將多邊緣服務(wù)器之間的競爭構(gòu)建為非合作博弈，并證明了移動(dòng)設(shè)備之間的博弈納什均衡的存在性；提出了基于多領(lǐng)導(dǎo)者Stackelberg博弈的激勵(lì)機(jī)制，該機(jī)制通過調(diào)整移動(dòng)設(shè)備和邊緣服務(wù)器的策略，解決了效用的最優(yōu)化問題；通過實(shí)驗(yàn)分析，驗(yàn)證了基于多領(lǐng)導(dǎo)者Stackelberg博弈激勵(lì)機(jī)制的可行性，并通過對比歷史最優(yōu)定價(jià)策略（Historical Optimal Pricing Strategy， HOPS）、最優(yōu)定價(jià)預(yù)測策略（Optimal Pricing Prediction Strategy， OPPS）和隨機(jī)定價(jià)策略驗(yàn)證了該機(jī)制的有效性。

1 相關(guān)工作

基于演化博弈激勵(lì)機(jī)制設(shè)計(jì)的現(xiàn)有工作中，文獻(xiàn)［8］中將企業(yè)和領(lǐng)先用戶作為博弈主體，構(gòu)建演化博弈模型，并探究領(lǐng)先用戶的知識共享激勵(lì)機(jī)制問題；文獻(xiàn)［9］中提出了一個(gè)基于演化博弈理論的動(dòng)態(tài)激勵(lì)模型，對用戶在數(shù)據(jù)共享中的博弈過程進(jìn)行建模，并分析了模型策略的穩(wěn)定性；文獻(xiàn)［10］中為具有有限理性的移動(dòng)設(shè)備構(gòu)建了演化博弈模型，以調(diào)整它們的訓(xùn)練策略，從而最大化設(shè)備的個(gè)體效用；文獻(xiàn)［11］中將異構(gòu)網(wǎng)絡(luò)中的用戶接入問題建模為演化博弈問題，并基于強(qiáng)化學(xué)習(xí)設(shè)計(jì)了低復(fù)雜度自組織用戶接入算法，實(shí)現(xiàn)了用戶的公平性；為了實(shí)現(xiàn)高效的分層聯(lián)邦學(xué)習(xí)，在非合作參與方（即移動(dòng)設(shè)備、邊緣服務(wù)器和云服務(wù)器）的背景下，文獻(xiàn)［12］為解決邊緣關(guān)聯(lián)和資源分配問題，將分層聯(lián)邦學(xué)習(xí)分為兩層，采取演化博弈模擬移動(dòng)設(shè)備的選擇過程，并通過性能評估驗(yàn)證了演化博弈的唯一性和穩(wěn)定性。但上述方法主要針對移動(dòng)設(shè)備之間的交互與策略變換，并集中解決移動(dòng)設(shè)備所產(chǎn)生的問題，未考慮邊緣服務(wù)器作為分層聯(lián)邦學(xué)習(xí)中的參與方對系統(tǒng)模型的影響。

在基于Stackelberg博弈激勵(lì)機(jī)制設(shè)計(jì)的現(xiàn)有工作中，文獻(xiàn)［13］中構(gòu)建了Stackelberg博弈模型以研究移動(dòng)設(shè)備之間以及移動(dòng)設(shè)備與模型所有者之間的交互作用，在該模型中，移動(dòng)設(shè)備能夠提供中繼服務(wù)，并收取一定報(bào)酬。此外，對于聯(lián)邦學(xué)習(xí)中服務(wù)器與移動(dòng)設(shè)備之間的交互也可采用Stackelberg博弈，如文獻(xiàn)［14］中采用兩個(gè)階段的Stackelberg博弈模型，同時(shí)設(shè)計(jì)了激勵(lì)機(jī)制，該機(jī)制不僅激勵(lì)移動(dòng)設(shè)備盡最大努力訓(xùn)練聯(lián)邦學(xué)習(xí)模型，也保證服務(wù)器達(dá)到最優(yōu)效用。文獻(xiàn)［15］中采用Stackelberg博弈對云服務(wù)器和參與聯(lián)邦學(xué)習(xí)的設(shè)備之間基于激勵(lì)的交互進(jìn)行建模，以激勵(lì)設(shè)備參與聯(lián)邦學(xué)習(xí)。除此之外，文獻(xiàn)［16］中研究了群體感知服務(wù)提供商的最優(yōu)激勵(lì)機(jī)制，提出了兩階段Stackelberg博弈，分析了移動(dòng)用戶的參與水平，同時(shí)采用反向歸納法分析了群體感知服務(wù)提供商的最優(yōu)激勵(lì)機(jī)制。類似地，文獻(xiàn)［17］中設(shè)計(jì)了多領(lǐng)導(dǎo)者多追隨者的兩層Stackelberg博弈模型，并構(gòu)建了一種分布式機(jī)制以分析移動(dòng)邊緣計(jì)算支持的邊緣云系統(tǒng)中服務(wù)商與移動(dòng)設(shè)備之間的交互。該模型證明了Stackelberg均衡的存在性，同時(shí)提出了一種分布式算法，即迭代的Stackelberg博弈定價(jià)算法。實(shí)驗(yàn)結(jié)果表明，與其他傳統(tǒng)的任務(wù)卸載方案相比，該算法能顯著降低物聯(lián)網(wǎng)移動(dòng)設(shè)備的負(fù)效用；然而，該算法主要針對計(jì)算卸載，對于移動(dòng)設(shè)備之間的博弈，它未考慮到移動(dòng)設(shè)備之間存在信息不對稱的問題，因此該算法并不適用于信息不完全的場景。針對上述相關(guān)模型的不足，本文構(gòu)建了演化博弈模型與非合作博弈模型，并基于多領(lǐng)導(dǎo)者Stackelberg博弈設(shè)計(jì)激勵(lì)機(jī)制，在資源有限的條件下探究了移動(dòng)設(shè)備策略的動(dòng)態(tài)性，并優(yōu)化了移動(dòng)設(shè)備和邊緣服務(wù)器的效用。

2 系統(tǒng)模型與問題定義

2.1　分層聯(lián)邦學(xué)習(xí)框架

1）本地更新。移動(dòng)設(shè)備能夠接收來自邊緣服務(wù)器的全局模型，并基于本地?cái)?shù)據(jù)進(jìn)行模型訓(xùn)練，同時(shí)該過程會(huì)消耗移動(dòng)設(shè)備的部分資源。最終移動(dòng)設(shè)備將訓(xùn)練完成的模型參數(shù)上傳至邊緣服務(wù)器，并獲得邊緣服務(wù)器給予的報(bào)酬。

2）邊緣服務(wù)器端聚合。邊緣服務(wù)器對接收的模型的參數(shù)進(jìn)行聚合，并將聚合后的模型參數(shù)上傳至云服務(wù)器，并獲得模型擁有者給予的報(bào)酬。

3）云端聚合。云服務(wù)器進(jìn)行全局模型參數(shù)聚合，并將更新完成的模型參數(shù)發(fā)送給邊緣服務(wù)器，再由邊緣服務(wù)器發(fā)送給移動(dòng)設(shè)備。

上述三個(gè)步驟將會(huì)持續(xù)迭代進(jìn)行，直到全局模型收斂或達(dá)到最大迭代次數(shù)。

2.2　移動(dòng)設(shè)備與邊緣服務(wù)器的效用模型

圖1　分層聯(lián)邦學(xué)習(xí)框架

在種群的移動(dòng)設(shè)備會(huì)因選擇邊緣服務(wù)器進(jìn)行模型訓(xùn)練而產(chǎn)生一定的成本，即計(jì)算成本與通信成本。在不同種群中，移動(dòng)設(shè)備之間的數(shù)據(jù)量存在一定差異，因此計(jì)算成本隨之變動(dòng)。隨著數(shù)據(jù)量的增多，移動(dòng)設(shè)備的計(jì)算成本也會(huì)增加［13］。在時(shí)刻的計(jì)算成本定義如下：

為激勵(lì)移動(dòng)設(shè)備積極參與分層聯(lián)邦學(xué)習(xí)，邊緣服務(wù)器根據(jù)種群中的移動(dòng)設(shè)備的數(shù)據(jù)貢獻(xiàn)占比與平均數(shù)據(jù)貢獻(xiàn)作比較，模型訓(xùn)練的數(shù)據(jù)量越大，則獲得的報(bào)酬越多。在經(jīng)過次迭代后，報(bào)酬定義如下：

由上述的移動(dòng)設(shè)備的通信與計(jì)算模型可得，種群中移動(dòng)設(shè)備因選擇邊緣服務(wù)器所產(chǎn)生的總成本為：

由式（3）與式（4）可得，定義種群中選擇邊緣服務(wù)器的移動(dòng)設(shè)備總效用為：

同時(shí)可得種群的總效用為：

通過將接收到的局部模型聚合后，邊緣服務(wù)器會(huì)根據(jù)模型的質(zhì)量獲得一定的收益。由于具有更大數(shù)據(jù)覆蓋率的邊緣服務(wù)器被認(rèn)為對分層聯(lián)邦學(xué)習(xí)模型具有更高價(jià)值，因?yàn)槟Ｐ托阅芸傻玫礁筇嵘?，如模型精度?8］。因此定義邊緣服務(wù)器的收益如下：

2.3　問題定義

針對上述移動(dòng)設(shè)備和邊緣服務(wù)器的效應(yīng)函數(shù)分析，對于邊緣服務(wù)器的定價(jià)策略，種群中的移動(dòng)設(shè)備動(dòng)態(tài)變換選擇邊緣服務(wù)器的策略，以最大化自身效用，即：

3 多領(lǐng)導(dǎo)者Stackelberg博弈模型構(gòu)建

本文將移動(dòng)設(shè)備與邊緣服務(wù)器之間的交互建模為多領(lǐng)導(dǎo)者Stackelberg博弈模型，如圖2所示。該博弈由移動(dòng)設(shè)備之間的演化博弈與邊緣服務(wù)器之間的非合作博弈構(gòu)成。隨著博弈的進(jìn)行，二者不斷調(diào)整策略，以實(shí)現(xiàn)效用最大化。

圖2　多領(lǐng)導(dǎo)者Stackelberg博弈模型

3.1　移動(dòng)設(shè)備之間的演化博弈均衡分析

與傳統(tǒng)博弈中的參與者立即獲得最優(yōu)解的方式不同，演化博弈中的參與者逐漸調(diào)整他們的策略并最終達(dá)到均衡解［20-21］。同時(shí)，演化博弈可以捕捉參與者策略適應(yīng)過程中的動(dòng)態(tài)和趨勢，因此能夠很好地刻畫分層聯(lián)邦學(xué)習(xí)中移動(dòng)設(shè)備之間的動(dòng)態(tài)交互與有限理性。

根據(jù)邊緣服務(wù)器決定的定價(jià)，移動(dòng)設(shè)備通過改變選擇服務(wù)器的策略相互競爭，以最大化自身利益。將移動(dòng)設(shè)備之間的演化博弈定義為：

演化博弈過程中，種群的移動(dòng)設(shè)備不斷地變換策略以尋求最優(yōu)的效用值。因此，定義時(shí)刻時(shí)，種群的平均效用為：

結(jié)合上述效用分析，同時(shí)為捕捉有限理性的移動(dòng)設(shè)備動(dòng)態(tài)調(diào)整策略的過程，引入復(fù)制動(dòng)態(tài)方程，定義如下：

3.2　邊緣服務(wù)器之間的非合作博弈均衡分析

作為領(lǐng)導(dǎo)者的邊緣服務(wù)器并不能在當(dāng)前輪次獲得所有定價(jià)信息，只能根據(jù)移動(dòng)設(shè)備的選擇策略動(dòng)態(tài)地調(diào)整定價(jià)。同時(shí)由于資源的有限性，邊緣服務(wù)器之間存在著競爭關(guān)系。

在分層聯(lián)邦學(xué)習(xí)中，每個(gè)邊緣服務(wù)器都被認(rèn)為是自私的，同時(shí)它們之間沒有合作或協(xié)定［23］。由于非合作博弈描述了自利參與者之間的沖突關(guān)系，因此在有限預(yù)算下，邊緣服務(wù)器之間的激勵(lì)問題可被建模為非合作博弈［24］。將非合作博弈定義為：

下面將對邊緣服務(wù)器之間博弈的均衡解進(jìn)行分析。

由式（10）與式（19）將優(yōu)化問題改寫為：

綜上所述，通過證明移動(dòng)設(shè)備之間的演化博弈和邊緣服務(wù)器之間的非合作博弈存在納什均衡，從而證明多領(lǐng)導(dǎo)者Stackelberg博弈均衡的存在性。

4 基于多領(lǐng)導(dǎo)者Stackelberg博弈的激勵(lì)機(jī)制設(shè)計(jì)

本文通過求解演化博弈與非合作博弈均衡解的算法，進(jìn)而求得多領(lǐng)導(dǎo)者Stackelberg博弈均衡解。在每一輪定價(jià)更新中，通過自身效用與平均效用的比較，移動(dòng)設(shè)備不斷更新選擇邊緣服務(wù)器的策略，最終達(dá)到演化博弈的納什均衡。根據(jù)上一輪其他邊緣服務(wù)器的定價(jià)策略，邊緣服務(wù)器更新自身定價(jià)，并開始下一輪的定價(jià)更新。

4.1　邊緣服務(wù)器選擇算法設(shè)計(jì)

算法1 多輪迭代邊緣服務(wù)器選擇算法（MIES）。

6） end for

9） 移動(dòng)設(shè)備變換選擇策略，以獲得更高效用

10） end if

11） end for

12） end for

15） end for

4.2　邊緣服務(wù)器的定價(jià)算法設(shè)計(jì)

算法2 梯度迭代定價(jià)算法（GIPA）。

7） end for

10） end while

5 實(shí)驗(yàn)與結(jié)果分析

表1　模擬參數(shù)設(shè)置

5.1　MIES算法分析

本節(jié)通過實(shí)驗(yàn)分析種群占比的變化趨勢，并討論MIES對移動(dòng)設(shè)備效用的影響。

圖3　隨迭代次數(shù)的變化趨勢（）

圖5顯示的是在邊緣服務(wù)器定價(jià)不變的情況下，不同種群中移動(dòng)設(shè)備總效用的對比。從圖5中可以看到，在初始情況下，種群2的總效用最高，但隨著迭代次數(shù)的增加總效用逐漸下降。根據(jù)MIES算法，為追求自身效用最大化，移動(dòng)設(shè)備的策略逐漸趨向于最優(yōu)解，因此種群2的策略不再占優(yōu)。同時(shí)由于種群中數(shù)據(jù)量的不同，獲得的收益趨于不同的穩(wěn)定值。

圖4　不同初始狀態(tài)下隨迭代次數(shù)的變化趨勢（）

圖5　邊緣服務(wù)器定價(jià)不變時(shí)不同種群中移動(dòng)設(shè)備總效用的對比

5.2　GIPA分析

本節(jié)通過實(shí)驗(yàn)分析邊緣服務(wù)器定價(jià)的變化趨勢，并討論GIPA對邊緣服務(wù)器效用的影響。

圖6　有限次迭代后邊緣服務(wù)器的定價(jià)趨勢

邊緣服務(wù)器購買移動(dòng)設(shè)備的資源，確定資源的價(jià)格，并通過聚合移動(dòng)設(shè)備的訓(xùn)練模型獲得收益。針對服務(wù)器的定價(jià)，比較了以下四種定價(jià)策略：

1）隨機(jī)定價(jià)策略（Random Pricing Strategy， RPS）：在最大與最小定價(jià)區(qū)間內(nèi)，邊緣服務(wù)隨機(jī)確定資源定價(jià)。

2）歷史最優(yōu)定價(jià)策略（HOPS）［26］：根據(jù)歷史最優(yōu)定價(jià)策略，邊緣服務(wù)器將它作為當(dāng)前資源定價(jià)策略。

3）最優(yōu)定價(jià)預(yù)測策略（OPPS）［27］：采用指數(shù)遺忘函數(shù)分配權(quán)重，對距離當(dāng)前最近的定價(jià)的歷史記錄賦予更大的權(quán)重，并對過時(shí)的定價(jià)記錄賦予更小的權(quán)重，根據(jù)權(quán)重分配獲得當(dāng)前的定價(jià)策略。

4）梯度迭代定價(jià)算法（GIPA）：根據(jù)移動(dòng)設(shè)備之間的演化博弈結(jié)果，服務(wù)器持續(xù)更新價(jià)格，直到給出最優(yōu)資源定價(jià)策略。

圖7　不同收益參數(shù)下的邊緣服務(wù)器效用

圖8給出了上述四種不同的定價(jià)策略下邊緣服務(wù)器的效用對比。實(shí)驗(yàn)結(jié)果表明，在相同的實(shí)驗(yàn)條件下，GIPA與OPPS、HOPS和RPS相比，邊緣服務(wù)器的平均效用分別提高了4.06%、10.08%和31.39%。這是由于GIPA能夠找到最適合當(dāng)前移動(dòng)設(shè)備的資源定價(jià)，并在與移動(dòng)設(shè)備的博弈過程中獲得最大效用。

圖8　不同的定價(jià)策略下的邊緣服務(wù)器的效用對比

上述實(shí)驗(yàn)結(jié)果驗(yàn)證了GIPA能夠?qū)崿F(xiàn)邊緣服務(wù)器的效用最大化。節(jié)點(diǎn)獲得的報(bào)酬能夠以某種方式影響設(shè)備的決策。在不同報(bào)酬的激勵(lì)機(jī)制下，設(shè)備將執(zhí)行不同的訓(xùn)練策略，從而影響最終的分層聯(lián)邦學(xué)習(xí)模型性能［28］。因此，為探究多領(lǐng)導(dǎo)者Stackelberg博弈激勵(lì)機(jī)制對設(shè)備提供高質(zhì)量模型影響，定義邊緣服務(wù)器訓(xùn)練模型的積極程度為：

如圖9所示，隨著參與到分層聯(lián)邦學(xué)習(xí)中的移動(dòng)設(shè)備數(shù)量增多，邊緣服務(wù)器的積極程度也隨之變化。由圖9可知，積極程度變化的幅度較為平緩，這是由于在移動(dòng)設(shè)備為邊緣服務(wù)器提供更多數(shù)據(jù)的同時(shí)，也會(huì)產(chǎn)生相應(yīng)的資源消耗。同時(shí)，與OPPS、HOPS和RPS定價(jià)策略相比，GIPA策略下的邊緣服務(wù)器能獲得更高的收益并且更積極地提高模型質(zhì)量。

圖9　不同定價(jià)策略下模型的積極程度對比

6 結(jié)語

針對移動(dòng)設(shè)備與邊緣服務(wù)器的最優(yōu)化問題，本文將移動(dòng)設(shè)備與邊緣服務(wù)器之間的交互建模為多領(lǐng)導(dǎo)者Stackelberg博弈，該博弈由移動(dòng)設(shè)備之間的演化博弈與邊緣服務(wù)器之間的非合作博弈構(gòu)成；還設(shè)計(jì)了MIES和GIPA分別求解演化博弈的均衡解和邊緣服務(wù)器之間非合作博弈的均衡解，進(jìn)而得到最優(yōu)的邊緣服務(wù)器選擇和定價(jià)策略。實(shí)驗(yàn)結(jié)果表明所提算法GIPA與OPPS、HOPS和RPS相比，邊緣服務(wù)器的平均效用分別提高了4.06%、10.08%和31.39%。本文探究了移動(dòng)設(shè)備與邊緣服務(wù)器之間的博弈，但并未考慮云服務(wù)器與它們之間的博弈，在未來的工作中，可從三者相互博弈的角度出發(fā)，設(shè)計(jì)更有效的激勵(lì)機(jī)制。

[1] 譚作文，張連福. 機(jī)器學(xué)習(xí)隱私保護(hù)研究綜述［J］. 軟件學(xué)報(bào)， 2020， 31（7）：2127-2156.（TAN Z W， ZHANG L F. Survey on privacy preserving techniques for machine learning［J］. Journal of Software， 2020， 31（7）： 2127-2156.）

[2] McMAHAN H B， MOORE E， RAMAGE D， et al. Communication-efficient learning of deep networks from decentralized data［C］// Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. New York： JMLR.org， 2017：1273-1282.

[3] ABAD M S H， OZFATURA E， GüNDüZ D， et al. Hierarchical federated learning across heterogeneous cellular networks［C］// Proceedings of the 2020 IEEE International Conference on Acoustics， Speech and Signal Processing. Piscataway： IEEE， 2020： 8866-8870.

[4] TU X， ZHU K， LUONG N C， et al. Incentive mechanisms for federated learning： from economic and game theoretic perspective［J］. IEEE Transactions on Cognitive Communications and Networking， 2022， 8（3）： 1566-1593.

[5] TIAN M， CHEN Y， LIU Y， et al. A contract theory based incentive mechanism for federated learning［EB/OL］. （2021-08-12） ［2022-08-10］.https：//arxiv.org/pdf/2108.05568.pdf.

[6] YU H， LIU Z， LIU Y， et al. A fairness-aware incentive scheme for federated learning［C］// Proceedings of the 2020 AAAI/ACM Conference on AI， Ethics， and Society. New York： ACM， 2020： 393-399.

[7] ZENG R， ZHANG S， WANG J， et al. FMore： an incentive scheme of multi-dimensional auction for federated learning in MEC［C］// Proceedings of the IEEE 40th International Conference on Distributed Computing Systems. Piscataway： IEEE， 2020： 278-288.

[8] 李從東，黃浩，張帆順. 基于演化博弈的領(lǐng)先用戶知識共享行為激勵(lì)機(jī)制［J］. 計(jì)算機(jī)應(yīng)用， 2021， 41（6）：1785-1791.（LI C D， HUANG H， ZHANG F S. Knowledge sharing behavior incentive mechanism for lead users based on evolutionary game［J］. Journal of Computer Applications， 2021， 41（6）： 1785-1791.）

[9] CHEN Y， ZHANG Y， WANG S， et al. DIM-DS： dynamic incentive model for data sharing in federated learning based on smart contracts and evolutionary game theory［J］. IEEE Internet of Things Journal， 2022， 9（23）： 24572-24584.

[10] ZOU Y， FENG S， NIYATO D， et al. Mobile device training strategies in federated learning： an evolutionary game approach［C］// Proceedings of the 2019 IEEE International Conference on Internet of Things/ Green Computing and Communications/ Cyber， Physical and Social Computing/ Smart Data. Piscataway： IEEE， 2019： 874-879.

[11] 王月平，徐濤. 基于演化博弈的用戶接入機(jī)制［J］. 計(jì)算機(jī)應(yīng)用， 2020， 40（5）：1392-1396.（WANG Y P， XU T. User association mechanism based on evolutionary game［J］. Journal of Computer Applications， 2020， 40（5）： 1392-1396.）

[12] LIM W Y B， NG J S， XIONG Z， et al. Dynamic edge association and resource allocation in self-organizing hierarchical federated learning networks［J］. IEEE Journal on Selected Areas in Communications， 2021， 39（12）： 3640-3653.

[13] FENG S， NIYATO D， WANG P， et al. Joint service pricing and cooperative relay communication for federated learning［C］// Proceedings of the 2019 IEEE International Conference on Internet of Things/ Green Computing and Communications/ Cyber， Physical and Social Computing/ Smart Data. Piscataway： IEEE， 2019： 815-820.

[14] XIAO G， XIAO M， GAO G， et al. Incentive mechanism design for federated learning： a two-stage Stackelberg game approach［C］// Proceedings of the IEEE 26th International Conference on Parallel and Distributed Systems. Piscataway： IEEE， 2020： 148-155.

[15] KHAN L U， PANDEY S R， TRAN N H， et al. Federated learning for edge networks： resource optimization and incentive mechanism［J］. IEEE Communications Magazine， 2020， 58（10）： 88-93.

[16] NIE J， LUO J， XIONG Z， et al. A Stackelberg game approach toward socially-aware incentive mechanisms for mobile crowdsensing［J］. IEEE Transactions on Wireless Communications， 2019， 18（1）： 724-738.

[17] SU Y， FAN W， LIU Y， et al. Game-based pricing and task offloading in mobile edge computing enabled edge-cloud systems［EB/OL］. （2021-01-14） ［2022-08-10］.https：//arxiv.org/pdf/2101.05628.pdf.

[18] ZHAN Y， LI P， QU Z， et al. A learning-based incentive mechanism for federated learning［J］. IEEE Internet of Things Journal， 2020， 7（7）： 6360-6368.

[19] GONG X， DUAN L， CHEN X， et al. When social network effect meets congestion effect in wireless networks： data usage equilibrium and optimal pricing［J］. IEEE Journal on Selected Areas in Communications， 2017， 35（2）： 449-462.

[20] HAN Z， NIYATO D， SAAD W， et al. Game Theory in Wireless and Communication Networks： Theory， Models， and Applications［M］. Cambridge： Cambridge University Press， 2012： 139-143.

[21] HOFBAUER J， SIGMUND K. Evolutionary game dynamics［J］. Bulletin of the American Mathematical Society， 2003， 40（4）： 479-519.

[22] GAO X， FENG S， NIYATO D， et al. Dynamic access point and service selection in backscatter-assisted RF-powered cognitive networks［J］. IEEE Internet of Things Journal， 2019， 6（5）： 8270-8283.

[23] PEJó B， TANG Q， BICZóK G. Together or alone： the price of privacy in collaborative learning［EB/OL］. ［2022-08-10］.https：//arxiv.org/pdf/1712.00270.pdf.

[24] WENG J， WENG J， HUANG H， et al. FedServing： a federated prediction serving framework based on incentive mechanism［C］// Proceedings of the 2021 IEEE Conference on Computer Communications. Piscataway： IEEE， 2021： 1-10.

[25] GONDZIO J. Interior point methods 25 years later［J］. European Journal of Operational Research， 2012， 218（3）： 587-601.

[26] LENG Y， WANG M， MA B， et al. A game-based scheme for resource purchasing and pricing in MEC for Internet of Things［J］. Security and Communication Networks， 2021， 2021： No.1951141.

[27] DENG Y， LYU F， REN J， et al. Improving federated learning with quality-aware user incentive and auto-weighted model aggregation［J］. IEEE Transactions on Parallel and Distributed Systems， 2022， 33（12）： 4515-4529.

[28] ZHAN Y， ZHANG J， HONG Z， et al. A survey of incentive mechanism design for federated learning［J］. IEEE Transactions on Emerging Topics in Computing， 2022， 10（2）： 1035-1044.

Incentive mechanism design for hierarchical federated learning based on multi-leader Stackelberg game

GENG Fangxing1，2， LI Zhuo1，2*， CHEN Xin2

（1（），100101，；2，，100101，）

The existence of privacy security and resource consumption issues in hierarchical federated learning reduces the enthusiasm of participants. To encourage a sufficient number of participants to actively participate in learning tasks and address the decision-making problem between multiple mobile devices and multiple edge servers， an incentive mechanism based on multi-leader Stackelberg game was proposed. Firstly， by quantifying the cost-utility of mobile devices and the payment of edge servers， a utility function was constructed， and an optimization problem was defined. Then， the interaction among mobile devices was modeled as an evolutionary game， and the interaction among edge servers was modeled as a non-cooperative game. To solve the optimal edge server selection and pricing strategy， a Multi-round Iterative Edge Server selection algorithm （MIES） and a Gradient Iterative Pricing Algorithm （GIPA） were proposed. The former was used to solve the evolutionary game equilibrium solution among mobile devices， and the latter was used to solve the pricing competition problem among edge servers. Experimental results show that compared with Optimal Pricing Prediction Strategy （OPPS）， Historical Optimal Pricing Strategy （HOPS） and Random Pricing Strategy （RPS）， GIPA can increase the average utility of edge servers by 4.06%， 10.08%， and 31.39% respectively.

hierarchical federated learning; incentive mechanism; pricing strategy; multi-leader Stackelberg game; evolutionary game

1001-9081（2023）11-3551-08

10.11772/j.issn.1001-9081.2022111727

2022?11?21；

2023?04?03；

北京市自然科學(xué)基金資助項(xiàng)目（4232024）； 國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（2022YFF0604502）； 國家自然科學(xué)基金資助項(xiàng)目（61872044）； 北京市青年拔尖人才項(xiàng)目。

耿方興（1999—），男，河南駐馬店人，碩士研究生，主要研究方向：邊緣計(jì)算； 李卓（1983—），男，河南南陽人，副教授，博士，CCF會(huì)員，主要研究方向：移動(dòng)無線網(wǎng)絡(luò)、分布式計(jì)算； 陳昕（1965—），男，江西南昌人，教授，博士，CCF會(huì)員，主要研究方向：網(wǎng)絡(luò)性能評價(jià)、網(wǎng)絡(luò)安全。

TP393

A

2023?04?04。

This work is partially supported by Beijing Natural Science Foundation （4232024）， National Key Research and Development Program of China （2022YFF0604502）， National Natural Science Foundation of China （61872044）， Beijing Municipal Program for Young Talents.

GENG Fangxing， born in 1999， M. S. candidate. His research interests include edge computing.

LI Zhuo， born in 1983， Ph. D.， associate professor. His research interests include mobile wireless network， distributed computing.

CHEN Xin， born in 1965， Ph. D.， professor. His research interests include network performance evaluation， network security.