[發明專利]基于概率分布的合作博弈值的高效計算方法

在審

• 申請號: 201610096634.0
• 申請日: 2016-02-22
• 公開（公告）號: CN105760350A
• 公開（公告）日: 2016-07-13
• 發明（設計）人: 張澤宇;董雨
• 申請（專利權）人: 中國科學技術大學
• 主分類號: G06F17/15
• 分類號: G06F17/15
• 代理公司: 北京凱特來知識產權代理有限公司 11260
• 代理人: 鄭立明;鄭哲

1.一種基于概率分布的合作博弈值的高效計算方法，其特征在于，包括：

獲取合作博弈在各個聯盟組合情況下的局中人個數及相應的聯盟支付數據；

根據各個聯盟組合情況下的局中人個數區分聯盟種類，并結合相應的聯盟支付數據使用概率分布以條件概率的角度分步計算合作博弈的值，從而實現合作博弈值的高效計算。

2.根據權利要求1所述的方法，其特征在于，所述根據各個聯盟組合情況下的局中人個數區分聯盟種類，并結合相應的聯盟支付數據使用概率分布以條件概率的角度分步計算合作博弈的值包括：

步驟S1、根據各個聯盟中局中人個數s區分聯盟種類；其中，設定s＝0時的聯盟唯一存在，其支付數據為0；s＝n時，聯盟為唯一的大聯盟，所述n表示合作博弈局中人的總數；

步驟S2、確定需要計算支付情況的局中人i；

步驟S3、依據聯盟中局中人個數s＝0至s＝n-1的順序，分別計算不包含局中人i的支付數據與包含局中人i的支付數據之差的絕對值，并按照不包含局中人i的聯盟中局中人數s的順序進行分類保存，類別記為：T0、T1、......T(n-1)；

步驟S4、按照類別T0至T(n-1)的順序，逐一計算每一類別內數值的算術平均值，得到結果A0、A1、......A(n-1)，該結果為支付數據增加值的均值；

步驟S5、判斷需要計算Shapley值或是Banzhaf值；若需計算Shapley值，則轉入步驟S6；若需計算Banzhaf值，則轉入步驟S7；

步驟S6、Shapley值為的形式，分解后變為：其中，N表示所有聯盟構成的集合；v表示相應的支付數據；S為N中的子集，表示一個聯盟；將步驟S4獲得的支付數據增加值的均值A0、A1、......A(n-1)求和，再除以n得到局中人i在Shapley值分配下獲得的支付；重復上述步驟S2～S6，直至計算完所有局中人在Shapley值分配下獲得的支付，從而獲得相應的Shapley值結果；

步驟S7、Banzhaf值為的形式，分解后變為：將步驟S4獲得的支付數據增加值的均值A0、A1、......A(n-1)乘以s相對應的的二項分布系數，再求加權和，得到局中人i在Banzhaf值分配下獲得的支付；重復上述步驟S2～S7，直至計算完所有局中人在Banzhaf值分配下獲得的支付，從而獲得相應的Banzhaf值結果。