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

在審

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

技術領域

本發明涉及數據處理技術領域，尤其涉及一種基于概率分布的合作博弈值的高效計算方法。

背景技術

目前，對合作博弈的使用越來越多，在應急物資儲備、上市公司股權權力分析、環境保護的成本分攤等各實踐方面都有多樣應用。這些應用領域在求解過程中都面臨隨著局中人數加大，運算效率大幅下降，嚴重限制了合作博弈的應用范圍。另一方面，目前合作博弈的研究過程中也過于重視公理性刻畫，對于實踐的指導性存在不足。

發明內容

本發明的目的是提供一種基于概率分布的合作博弈值的高效計算方法，將合作博弈值的計算量大幅縮減，使得合作博弈值無論是Shapley值還是Banzhaf值都能被更加高效的計算出來，從而推動合作博弈應用于實踐領域。

本發明的目的是通過以下技術方案實現的：

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

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

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

所述根據各個聯盟組合情況下的局中人個數區分聯盟種類，并結合相應的聯盟支付數據使用概率分布以條件概率的角度分步計算合作博弈的值包括：

步驟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值結果。

由上述本發明提供的技術方案可以看出，避免了在計算Shapley值和Banzhaf值的過程中的系數計算問題，其中Shapley值完全規避了系數計算問題，全部使用算術平均值進行計算；而Banzhaf值不再使用指數計算，以二項分布的系數作為替代，達到了與計算Shapley值的統一，從可以很好的提高合作博弈的解的計算效率。

附圖說明

為了更清楚地說明本發明實施例的技術方案，下面將對實施例描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對于本領域的普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他附圖。

圖1為本發明實施例提供的一種基于概率分布的合作博弈值的高效計算方法的流程圖。

具體實施方式

下面結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基于本發明的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬于本發明的保護范圍。

圖1為本發明實施例提供的一種基于概率分布的合作博弈值的高效計算方法的流程圖。如圖1所示，其主要包括如下步驟：