論文標(biāo)題：Incentive Mechanisms for Federated Learning: From Economic and Game Theoretic Perspective

分類圖

總體而言，分類如下：
博弈論激勵(lì)：非合作游戲、stackelberg游戲、聯(lián)盟游戲
拍賣激勵(lì)：盲拍、前向、倒向、雙拍、組合拍賣
合同理論
匹配理論

博弈論

博弈論可以為多參與者交互決策建模，其中一個(gè)參與方的決定會(huì)潛在影響另一個(gè)參與方的。在FL的背景下，參與方可以市MO和DO，我們下面簡(jiǎn)要介紹一下博弈論的激勵(lì)機(jī)制，然后它們有一些可以很好的獎(jiǎng)勵(lì)FL的參與方。一些術(shù)語：

玩家：決策者，可以選擇它的動(dòng)作，它們會(huì)傾向讓自己的收益最大化
收益：表示玩家從游戲中賺或虧的錢
策略：是一套完整的動(dòng)作計(jì)劃，為了到達(dá)理想的結(jié)果。這個(gè)payoff取決于多個(gè)玩家的actions
平衡：每個(gè)玩家都可以達(dá)到它們認(rèn)為的最大收益，如果它們要改變策略的話它們不會(huì)有任何收益，反應(yīng)了博弈的穩(wěn)定性

1）非合作博弈：每個(gè)player都是自私的，只關(guān)心自己收益的最大化，不關(guān)心FL系統(tǒng)的整體福利。players之間是不會(huì)合作的。我們考慮FL市場(chǎng)中的定價(jià)作為例子。DO（賣家）可以為提供的計(jì)算資源設(shè)置價(jià)格給MO（買家）。非合作游戲可以定義為三元組G = （Pi，ui，i belongs to N）這里N表示有N個(gè)賣家，Pi是i的賣出價(jià)格，ui是對(duì)于i來說，所有玩家固定策略時(shí)的收益。

我們有如下定義：
DEF1：假設(shè)pi是玩家i的最優(yōu)策略，那么（pi,…,pn*)就是一個(gè)納什均衡，意味著沒有玩家可以通過改變當(dāng)前策略（其他玩家不改變）的時(shí)候提高自己的收益，用式子表示就是：

這個(gè)式子表明，納什均衡是這個(gè)游戲的穩(wěn)定結(jié)果，因?yàn)橘u家如果改變它們的策略并不會(huì)獲得收益（單方面）。
然而，在一個(gè)游戲里面，可能會(huì)不存在NE或者存在多個(gè)NE，這就讓palyer很難預(yù)測(cè)游戲的結(jié)果。因此在非合作游戲中，我們要驗(yàn)證NE的存在唯一性。有定理表明，唯一的NE存在當(dāng)且僅當(dāng)每一個(gè)player的策略空間是凸集（非空，閉集，有界）且收益函數(shù)是連續(xù)且類凹函數(shù)。

非合作博弈假設(shè)信息作為特征，player的收益函數(shù)和策略是公開的，這個(gè)就是一個(gè)完全信息游戲。然而，在實(shí)際當(dāng)中，一個(gè)player可能不會(huì)太注意到其他palyer的信息，可能只知道每種類型出現(xiàn)的概率，這種就叫做不完全信息博弈。在FL市場(chǎng)中，關(guān)于DO可靠性和信譽(yù)的先驗(yàn)知識(shí)可以幫助分配獎(jiǎng)勵(lì)的，這些知識(shí)MO可能不知道。一個(gè)典型例子就是貝葉斯博弈，游戲的結(jié)果可以通過貝葉斯分析來預(yù)測(cè)。這個(gè)的均衡就是BNE，類似完全信息博弈的NE，當(dāng)每一個(gè)player選擇一個(gè)策略取最優(yōu)化它們的期待收益（利用它們對(duì)其他player類型和策略的估計(jì)），BNE可以被計(jì)算出來。因?yàn)榉呛献鞑┺臉?gòu)建了自私players之間的沖突，F(xiàn)L市場(chǎng)中DO是競(jìng)爭(zhēng)的然后MO的錢是有限的都可以構(gòu)建為非合作博弈。這個(gè)對(duì)應(yīng)的NE勻速DO有一個(gè)最優(yōu)的參與策略。在FL中，這可以利用有競(jìng)爭(zhēng)力的預(yù)測(cè)服務(wù)提供者進(jìn)行計(jì)算資源交易。

2）Stackbelberg Game：
Stackelberg博弈是一個(gè)隨著時(shí)序移動(dòng)的博弈，在這里面，player作為leader的首先移動(dòng)，然后其他player作為follwers的在觀察了leader的移動(dòng)之后再移動(dòng)。因此，它也叫做leader-follower博弈。這個(gè)博弈的目標(biāo)是建模一個(gè)多agent的決策過程，然后最大化在給定leader策略下的leader和follower的最大收益。

重新考慮一下我們有兩個(gè)player，也就是計(jì)算資源的銷售方。P1和P2表示兩個(gè)player各自的策略。1和2都希望最大化它們的效用ui(p1,p2)。假設(shè)player 1在階段1選擇了它的策略，因此它就是一個(gè)leader。player2在階段2選擇了策略，所以他就是follower。這個(gè)關(guān)于leader和follower的共同優(yōu)化問題就是Stackelberg游戲，它們的解構(gòu)成了SE

DEF2：假設(shè)p1和p2分別是leader和follower的最優(yōu)策略，那么(p1*,p2*)是SE當(dāng)且僅當(dāng)對(duì)于任意的(p1,p2)
我們有

通常來說，反向推理方法經(jīng)常用于求解SE。在上述的例子中，給定p1，首先我們可以讓follower求解出p2*，然后對(duì)于leader而言，我們用p2替換掉p2就可以求解出p1。因?yàn)閜layer1知道paler2知道p1作為優(yōu)勢(shì)，player1會(huì)強(qiáng)加一個(gè)對(duì)自身有利的solution。
因此，在SE中，leader的效用總是高于follwer的，這個(gè)就叫做第一個(gè)移動(dòng)者的優(yōu)勢(shì)。對(duì)應(yīng)地，當(dāng)?shù)竭_(dá)了SE之后，leader可以獲得至少和對(duì)應(yīng)NE相當(dāng)?shù)厥找?。這個(gè)特征使得Stakelberg博弈適合FL的激勵(lì)機(jī)制的設(shè)計(jì)。例如，它可以允許followers在知道leader（MO）對(duì)CPU資源的需求或者獎(jiǎng)勵(lì)的發(fā)放后，再來決定計(jì)算資源的定價(jià)

3）聯(lián)盟博弈：在合作游戲中，player之間互相合作來使得整個(gè)聯(lián)盟的共同目標(biāo)最優(yōu)化。進(jìn)一步來說，player之間簽訂了強(qiáng)制性的條款。在這情況下，palyer可以協(xié)調(diào)策略然后達(dá)成一個(gè)關(guān)于怎么分配總收益給聯(lián)盟中的player的共識(shí)。聯(lián)盟博弈的目標(biāo)是為了尋找一個(gè)穩(wěn)定的解可以保證博弈的結(jié)果是免疫于player的變更的

拍賣

拍賣是一種經(jīng)濟(jì)的機(jī)制，它的目的就是分配商品（例如訓(xùn)練數(shù)據(jù)，計(jì)算資源和帶寬等），然后建立一個(gè)對(duì)應(yīng)的價(jià)格通過一個(gè)叫“競(jìng)價(jià)”的過程。一個(gè)拍賣包括一個(gè)精確的規(guī)則集合，這些規(guī)則通過市場(chǎng)參與者的基礎(chǔ)來決定資源的分配和價(jià)格。拍賣中有術(shù)語如下：

競(jìng)價(jià)方：競(jìng)價(jià)方就是買方，它們希望在拍賣中購買物品。在FL中，買房可能是MO或者是FL需求方
賣方：賣方給賣方提供服務(wù)或資源。在FL中，賣方通常是DO或者那些使用本地?cái)?shù)據(jù)訓(xùn)練共享模型的客戶
拍賣中間商：中介，決定價(jià)格和獲勝方。很多情況下，賣方也擔(dān)任中介。
價(jià)格：可能是asking price或者bidding price。asking price就是seller希望獲得的price，然后bidding price就是buyer希望支付的price。Hammer price就是最終拍板的價(jià)格。
商品：買方和賣方要交易的東西，它對(duì)應(yīng)著buyer和seller想買的價(jià)格和想賣的價(jià)格。在FL中，商品可以是一個(gè)數(shù)據(jù)單元（訓(xùn)練數(shù)據(jù)樣例）或者是一個(gè)計(jì)算資源單元（do提供的）
價(jià)值：在拍賣中，價(jià)值就是值商品值多少錢。不同的買賣方會(huì)根據(jù)自己的偏好得到不同的價(jià)值。每個(gè)參與者心中的價(jià)值可以是私有的也可以是公開的。
效用：買方的效用是不同于商品的價(jià)值和最終的支付的。賣方的效用，也就是收益，指的是它從buyer那里獲得的總支付。在FL中，buyer的效用，例如MO，可以是正比于全局模型的精確度以及反比于給DO的總支付
社會(huì)福利：指的是每個(gè)user（buyer + seller）的總效用

拍賣機(jī)制被廣泛地應(yīng)用在多個(gè)領(lǐng)域，例如無線系統(tǒng)地資源分配，安全數(shù)據(jù)下載，網(wǎng)絡(luò)安全。接下來，我們介紹在FL中常用的拍賣類型

1）盲拍：不同于公開拍賣，在盲拍中，buyer提交一個(gè)隱藏的競(jìng)價(jià)給中介。對(duì)應(yīng)的，沒有bidder知道別人的bidding價(jià)格，也不能更換自己的價(jià)格。下面是三種類型的拍賣：

• First-price 盲拍：誰bid的錢最多誰就是贏家，然后可以獲得item
• Second-price 盲拍（Vickrey）：第二高bid的玩家才是贏家。因?yàn)閯僬咧Ц兜膬r(jià)格比它期待的要少，所以這個(gè)協(xié)議促使buyer真實(shí)的拍賣，因此拍賣很可信。這個(gè)特征使得**這個(gè)拍賣策略在FL中常被使用，用來防止不可信節(jié)點(diǎn)的惡意行為
• Vickrey-Clarke-Groves拍賣（VCG)：是一個(gè)冠以的Vickrey拍賣（適用于多個(gè)商品）。在VCG里面，商品根據(jù)社會(huì)最優(yōu)的行為來分配，然后勝者支付由于贏了商品造成的社會(huì)價(jià)值的丟失。這種支付規(guī)則使得bidder會(huì)根據(jù)商品之際價(jià)值正常的叫價(jià)。因此，VCG是一個(gè)可信的機(jī)制。在FL中，VCG機(jī)制可以用來激勵(lì)DO來報(bào)告它們關(guān)于網(wǎng)絡(luò)操作的真實(shí)價(jià)值，從而來最大化社會(huì)的福利。

2）前向拍賣，反向拍賣，二次拍賣：

• 前向拍賣：多個(gè)buyer先提交bids，然后對(duì)于一個(gè)seller來說看看誰的叫價(jià)高
• 反向拍賣：多個(gè)seller先提交asks，然后對(duì)于一個(gè)buyer來說看看誰能接受。一般來說，反向拍賣都和盲拍結(jié)合之類的。
• 二次拍賣：在FL中，存在多個(gè)MO和DO，二次拍賣可以用來匹配供給和需求。在二次拍賣中，buyer和seller同時(shí)提供它們的bids和asks，給一個(gè)中介。中介會(huì)決定一個(gè)price p，就是交易費(fèi)，為了清空市場(chǎng)，一般來說asks < p and bids > p。一般來說p = (pb + ps) / 2,pb是bids，ps是asks。買方接受資源，賣方獲得交易費(fèi)。（那消失的(pb - ps) / 2是不是被中介吞了？）這個(gè)過程一直重復(fù)，直到?jīng)]有新的交易出現(xiàn)或者到達(dá)預(yù)計(jì)的結(jié)束時(shí)間

3）組合拍賣：在組合拍賣中，buyer的每一個(gè)bid都意味著一大串的商品?；赽id中的信息和seller中的商品容量，中介可以決定最優(yōu)的分配策略和獲勝者。然而，解決winner對(duì)于組合拍賣是NP難問題，沒有多項(xiàng)式解法來找到最優(yōu)的分配。這里有很多算法來得到問題的近似解，例如拉格朗日估值。在FL中，組合拍賣用來分配網(wǎng)絡(luò)操作者的帶寬來掌控FL SP（service provider）

合同和匹配理論

合同和匹配理論被認(rèn)為是建模關(guān)于不同類型的明知且自利的player動(dòng)態(tài)和互相利益關(guān)系的兩大殺器。特別地，它們可以有效地解決交易市場(chǎng)的高動(dòng)態(tài)性，以及自利和競(jìng)爭(zhēng)的player。下面，我們簡(jiǎn)單介紹合同和匹配理論以及FL的設(shè)計(jì)

1）合同理論：合同理論是一個(gè)經(jīng)濟(jì)的理論，他認(rèn)為每個(gè)交易和機(jī)構(gòu)都是一種合同。他在雇傭者和雇傭人的非對(duì)稱信息里面經(jīng)常使用（也就是說，員工的未來老板是不準(zhǔn)確知道的）。在FL里面，因?yàn)榇蚬ぷ卸际亲运降娜缓笏鼈兛赡懿粫?huì)暴露它們的真實(shí)bids以及它們?cè)贔L中的隱私保護(hù)性質(zhì)，因此存在著信息不對(duì)稱。合同理論可以設(shè)計(jì)一個(gè)最優(yōu)的合同來減少道德威脅，不利的選舉，以及在信息不對(duì)稱中的派系扭曲這個(gè)特征使得合同理論可以使用于FL中的激勵(lì)機(jī)制的設(shè)計(jì)。在FL背景下，一個(gè)老板可以是一個(gè)MO它希望雇傭worker來完成FL的模型訓(xùn)練。同樣的，一個(gè)員工（do），希望加入到FL中。一個(gè)三維的合同激勵(lì)機(jī)制同時(shí)考慮任務(wù)的支出和隱私問題在70中被提出。一個(gè)兩階段的基于動(dòng)態(tài)合同的激勵(lì)機(jī)制在71提出，來激勵(lì)不同意愿的user來參加。基于個(gè)人隱私保護(hù)的合同激勵(lì)72可以提供對(duì)不同隱私偏好的worker進(jìn)行傳統(tǒng)的支付（ps：這就是激勵(lì)+ 隱私嘛？？?。。?/p>

2）匹配理論：匹配理論的目標(biāo)是最優(yōu)化匹配兩個(gè)不相交的agent集合（給定它們每個(gè)個(gè)體的效用下）。在通常的分配博弈模型，可能會(huì)有多個(gè)agents在matching的兩端出現(xiàn)，然后一邊的agents會(huì)和另一邊的agents進(jìn)行交易。因此，這種游戲叫做雙邊匹配。在匹配理論中，agents之間互相競(jìng)爭(zhēng)，從而最大化它們的效用（自私程度），然后總是做那些可以增大它們效用的決定（貪心，理智）。**在FL中，這個(gè)被用來進(jìn)行任務(wù)的分配，目標(biāo)就是最小化系統(tǒng)的延遲（在多任務(wù)FL的場(chǎng)景下）

總結(jié)

這節(jié)介紹了經(jīng)濟(jì)學(xué)和博弈論模型的知識(shí)，然后提出它在FL的應(yīng)用。具體的，我們介紹了定義，機(jī)制描述，合理性分析等。文章來源地址http://www.zghlxwxcb.cn/news/detail-417617.html

到了這里，關(guān)于激勵(lì)機(jī)制中的經(jīng)濟(jì)學(xué)和博弈論模型（2）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！