[發(fā)明專利]有向網(wǎng)絡(luò)下基于量化通信的完全分布式納什均衡搜索方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202111384902.6
• 申請(qǐng)日: 2021-11-22
• 公開（公告）號(hào): CN114118422A
• 公開（公告）日: 2022-03-01
• 發(fā)明（設(shè)計(jì)）人: 饒心培;許文盈
• 申請(qǐng)（專利權(quán)）人: 東南大學(xué)
• 主分類號(hào): G06N5/04
• 分類號(hào): G06N5/04
• 代理公司: 南京蘇高專利商標(biāo)事務(wù)所(普通合伙) 32204
• 代理人: 向文

本發(fā)明公開了一種有向網(wǎng)絡(luò)下基于量化通信的完全分布式納什均衡搜索方法，包括如下步驟：根據(jù)通訊網(wǎng)絡(luò)結(jié)構(gòu)，獲取加權(quán)鄰接矩陣W；根據(jù)決策可行集，每個(gè)玩家選擇初始決策，并對(duì)其他所有玩家決策進(jìn)行估計(jì)；每步迭代前，根據(jù)提出的量化方案，每個(gè)玩家通過通訊網(wǎng)絡(luò)傳輸其決策估計(jì)上一步的更新信息給鄰居，同時(shí)處理鄰居傳來的信息，更新對(duì)鄰居決策估計(jì)的估計(jì)；每步迭代，根據(jù)設(shè)定的加權(quán)鄰接矩陣W，每個(gè)玩家計(jì)算出所有玩家決策估計(jì)的加權(quán)平均，并據(jù)此更新其決策估計(jì)；當(dāng)所有玩家決策估計(jì)更新量為零，即算法收斂，獲取到NE。本發(fā)明提出一種量化方案，并基于此提出一種完全分布式的NE搜索方法，此方法在有限網(wǎng)絡(luò)帶寬的限制下，能夠收斂到理論的NE。

技術(shù)領(lǐng)域

本發(fā)明屬于分布式計(jì)算與分析技術(shù)領(lǐng)域，涉及，具體涉及一種在有向網(wǎng)絡(luò)中基于量化通信的完全分布式納什均衡(NE)搜索方法。

背景技術(shù)

分布式納什均衡(NE)搜索問題是當(dāng)前網(wǎng)絡(luò)研究的一個(gè)熱點(diǎn)問題。近年來，由于非合作博弈問題在一些工程、經(jīng)濟(jì)和社會(huì)等問題中的廣泛應(yīng)用，它獲得了越來越多的關(guān)注。在博弈問題中，每個(gè)玩家都可以被認(rèn)為是一個(gè)自私的決策者，它只旨在優(yōu)化其個(gè)人，但同時(shí)又依賴于其他人決策的目標(biāo)函數(shù)。NE計(jì)算是非合作博弈中的一個(gè)關(guān)鍵問題。目前，大多數(shù)傳統(tǒng)的NE搜索算法都依賴于一個(gè)中心節(jié)點(diǎn)，該節(jié)點(diǎn)向博弈中的所有玩家廣播信息，然而，在實(shí)際應(yīng)用中，這樣的節(jié)點(diǎn)基本不可能存在。因此，分布式算法被提出。在分布式算法中，玩家可以僅通過與鄰居的通信來計(jì)算NE。

通訊在分布式算法中發(fā)揮著越來越重要的作用。在非合作博弈中，每個(gè)玩家的目標(biāo)函數(shù)不僅依賴于其自己的決策，同時(shí)還依賴于其他玩家的決策。然而在實(shí)際中，玩家可能并不能直接獲得其他所有玩家的決策。因此為了解決信息缺失的問題，玩家不得不通過與鄰居交換信息來估計(jì)其他玩家的決策。

研究量化對(duì)分布式算法的影響已經(jīng)成為了一個(gè)新的熱點(diǎn)。隨著大規(guī)模網(wǎng)絡(luò)的普及，參與博弈的玩家數(shù)量的增加，需要通過通訊網(wǎng)絡(luò)傳輸?shù)男畔⒁矘O具增加。然而，在實(shí)際應(yīng)用中，通訊網(wǎng)絡(luò)的帶寬往往是有限的，可能無法傳輸如此大量的信息。在這種背景下，人們不得不考慮將數(shù)據(jù)量化。一般來說，由于量化數(shù)據(jù)不可避免的會(huì)帶來一些量化誤差，所以量化可能會(huì)不同程度地降低算法的性能。

目前，已經(jīng)有一些研究使用量化信息的分布式優(yōu)化算法的初步工作。然而，受量化影響的非合作博弈的分布式NE尋找問題尚未得到足夠的研究關(guān)注。已有的相關(guān)研究討論了量化對(duì)基于離散時(shí)間梯度的NE尋求算法的影響，其中假設(shè)每個(gè)玩家都有能力向博弈中其他所有玩家廣播其量化信息。但在大規(guī)模博弈中，這種假設(shè)很難滿足，因而這種算法可能并不適用。

發(fā)明內(nèi)容

發(fā)明目的：為了克服現(xiàn)有技術(shù)中存在的不足，提供一種在有向網(wǎng)絡(luò)中基于量化通信的完全分布式納什均衡(NE)搜索方法，提出一種量化方案，并基于此提出一種完全分布式的NE搜索方法，此方法在有限網(wǎng)絡(luò)帶寬的限制下，能夠收斂到理論的NE。

技術(shù)方案：為實(shí)現(xiàn)上述目的，本發(fā)明提供一種有向網(wǎng)絡(luò)下基于量化通信的完全分布式納什均衡搜索方法，包括如下步驟：

S1：根據(jù)通訊網(wǎng)絡(luò)結(jié)構(gòu)，獲取加權(quán)鄰接矩陣W；

S2：根據(jù)決策可行集，每個(gè)玩家選擇初始決策，并對(duì)其他所有玩家決策進(jìn)行估計(jì)；

S3：每步迭代前，根據(jù)提出的量化方案，每個(gè)玩家通過通訊網(wǎng)絡(luò)傳輸其決策估計(jì)上一步的更新信息給鄰居，同時(shí)處理鄰居傳來的信息，更新對(duì)鄰居決策估計(jì)的估計(jì)；

S4：每步迭代，根據(jù)設(shè)定的加權(quán)鄰接矩陣W，每個(gè)玩家計(jì)算出所有玩家決策估計(jì)的加權(quán)平均，并據(jù)此更新其決策估計(jì)；

S5：當(dāng)所有玩家決策估計(jì)更新量為零，即算法收斂，獲取到NE。

進(jìn)一步地，所述步驟S1中加權(quán)鄰接矩陣W的獲取方式具體為：