基于τ值的圖博弈有效權重分配規則

薛濤 董艷俠

摘 要：首先，本文提出基于τ值的權重圖博弈有效解，這個單值解既是圖博弈下τ值的推廣，又是基于τ值的剩余平均分配解的擴展。其次，利用分支有效性、S均衡下的相對不變性、剩余有效權重分配和線性限制權重成比例對權重圖博弈有效解進行公理刻畫。最后， 介紹基于權重圖博弈有效解的特殊分配規則。

關鍵詞：圖結構;有效解;τ值;分支有效性

本文索引：薛濤，董艷俠.<變量 2>[J].中國商論，2021（22）：-141.

中圖分類號：F279.23 文獻標識碼：A 文章編號：2096-0298（2021）11（b）--05

在博弈中， 所有局中人通過合作獲得總收益， 再經過合理的分配模式得到各自的收益， 他們相互關聯形成各自的聯盟。 但是，在很多情況下，受到技術、人際關系等方面的限制，因此只有相互聯系的局中人才能形成聯盟。 建立在這一假設前提下，Myerson[1]提出了圖限制博弈，并建立在值的基礎上給出一個在圖博弈上的分配規則，即值，并對其進行了公理刻畫。（1981）提出另外一種分配規則等（2011）值，并由王文文[3]將這一經典合作博弈下的單值解推廣到圖博弈中并給出公理刻畫。

隨著合作博弈的不斷發展， 對于分支間進行合作形成大聯盟后得到的收益大于各分支收益之和的情況， 學者也提出了許多擴展解。（2019）提出了兩步值，（2011）基于τ值提出了兩個有效解， 分別是剩余公平分配解與兩步τ值。（2012）建立在相鄰公平性的基礎上，提出分支公平解、分支公平剩余解以及兩步分支公平剩余解;（2016）提出度公平性、具有度值的公平性以及具有度剩余值的度公平性擴展了提出的一類逐分支公平解，從而得到了新的分配規則， 分別為：逐分支比例解、逐分支比例剩余解以及兩步逐分支比例剩余解;? （2020）提出分支權重解、分支權重剩余解以及兩步分支權重剩余解，作為在這一領域的進一步推廣。 為了從值的角度進行擴展，（2012）建立在剩余公平分配的基礎上提出基于值的剩余公平分配解; （2018）提出基于值的兩步剩余公平分配解; 提出了一類有效權重（2019）值作為這一領域的進一步推廣。 本文研究了在圖博弈下基于值的有效權重解同時研究了有效權重解滿足的性質，并給出有效權重解公理刻畫。 最后提出了基于這一有效權重解的特殊分配規則并給出了公理化方法。

本文第1節介紹了圖博弈、擬均衡博弈、 τ值等概念; 第2節提出權重圖博弈有效解的精確表達式，給出權重圖博弈有效解的性質并對權重圖博弈有效解進行公理刻畫。 第3節提出基于權重圖博弈有效解的特殊分配規則并提出公理化方法。

1 基本定義

在合作博弈中，可以為任意一個由個局中人組成的聯盟分配一個由實數表示的收益， 這一博弈被稱為可轉移效用博弈， 即博弈。該博弈可以由有序對偶表示，其中表示有限局中人集合， 特征函數，。 用表示由個局中人組成的聯盟的收益，其中。

對任意圖結構， 其中表示有限局中人集合，無序集合。 其中任意的表示局中人的雙邊關系。通過代替，簡化表示一條邊。 用表示與局中人相鄰的局中人個數，表示為局中人的強度， 即;強度反映了該局中人在聯盟中與其他局中人合作的緊密程度，強度越大該局中人合作能力越強;反之，合作能力越弱。

對于任何一個聯盟，表示為的子圖，其中，。 由一系列局中人形成的序列稱為在圖上的路，如果成立，對于。 圖結構是連通圖，如果在個局中人中，任意兩個局中人之間都存在一條路。 在連通圖中，所有連通聯盟的集合用表示，個局中人中的最大連通子集被稱為圖結構的連通分支，該分支用表示。 所有連通分支的集合表示為，用表示的所有連通分支。 用表示中除去局中人后局中人的集合。 表示中包括的連通分支，任意一個連通分支的強度可以表示為。

表示博弈，表示包含v個局中人的圖結構，故任意圖博弈可以表示為，為簡化，表示所有圖博弈。 圖博弈的解可以分為兩類，一類是滿足分支有效性的分支有效解，另一類是滿足有效性的解即圖博弈有效解。 其中，分支有效解有滿足分支有效性的值，本文則是建立在值的基礎上通過引入權重進而做出有關有效解的推廣。 通過映射為每一個圖博弈分配一個支付向量，且。 分支聯盟收益之和表示為，分支聯盟合作而形成大聯盟的收益表示為。

根據參考文獻[3]可知，在圖博弈中， 對于任意的局中人，其上向量的元素可以表示為， 故表示為局中人加入其所在的分支聯盟后可以得到的最大收益。 對于連通聯盟集合， 聯盟S的間隙函數表示。局中人關于聯盟S的剩余收益表示為。因此，對于連通聯盟，如果能夠使除局中人以外的每一位局中人都得到各自的上向量，則表示局中人應該損失的收益。 故這一讓步值對于單個局中人來說，越小越好。 對于任意有讓步向量。擬均衡博弈可以表示為：

，，且，

定義1.1 對于任意的擬均衡圖博弈，值可以表示為：

，

如果， 則.

引理1.1 在擬均衡博弈中，值滿足以下性質：

（1）分支有效性：對于任意的，使得。

（2）個體理性：對任意的，有。

（3）S均衡下的相對不變性：對于任意，，使得，則下式成立：

。

（4）啞元性：若為啞元，即對于任意的，，使得，那么對任意，使得成立。

（5）可替代性：若是可替代的局中人，即，，則。

（6）如果，對于任意的，存在，使得下式成立：。

2 權重圖博弈有效解及其公理化

本節建立在τ值的基礎上，通過引入權重，向圖博弈有效解做出推廣。 這里我們分為兩個部分介紹：2.1節提出了權重圖博弈有效解;2.2節對權重圖博弈有效解進行了公理性刻畫。

2.1 權重圖博弈有效解的提出

在本小節中，我們考慮各分支聯盟進行合作而形成大聯盟的收益大于各分支聯盟收益之和的情況， 即對于任意的，有成立。建立在此基礎上，我們提出基于值的權重圖博弈有效解。

定義2.1? 對于任意的擬均衡圖博弈， 存在一個測度函數， 并且該測度函數給予每一個局中人 一個正值， 對于任意給定的測度函數， 其權重圖博弈有效解， 記作：

，.

根據權重圖博弈有效解的定義，我們可以發現這一分配規則對于每一位局中人， 首先分配給其τ值，再根據占的權重分配大聯盟收益與各個分支聯盟收益之和的剩余值，即。 如果取 且，則權重圖博弈有效解與剩余平等分配解等價; 因為權重圖博弈滿足有效性，特別是如果，則權重圖博弈有效解與圖博弈的τ值等價。 因此，權重圖博弈有效解不僅是剩余平等解的擴展，還是圖博弈τ值的一個推廣。

2.2 權重圖博弈有效解的公理化

在本小節中，對2.1節提出的權重圖博弈有效解做進一步研究，主要涉及有效權重解滿足的性質以及其公理化過程。

引理2.1 令且，對于圖博弈其上向量、間隙函數與讓步向量分別為：

，

，

，

由于，故有.

定理2.1? 對于任意擬均衡博弈，權重圖博弈解滿足：

（1）有效性;（2）個體理性;（3）均衡下的相對不變性;

（4）線性限制權重成比例：對于任意且對于任意的和;滿足;對于任意， 存在實數，使得任意局中人，有

成立;

（5）剩余比例分配：任意兩個局中人，如果脫離大聯盟而形成各自的分支聯盟，其收益的變化與各自的測度函數成比例。具體對于擬均衡博弈，任意的局中人， 有以下公式成立：

.

證明 （1）有效性。由于

.

因此，權重圖博弈有效解滿足有效性。

（2）個體理性。由定義2.1可知

，.

由于，有，進而有 。根據已知，易得對于任意的，有，故

.

因此，權重圖博弈有效解滿足個人理性。

（3）均衡下的相對不變性。 由引理2.1可知權重圖博弈有效解滿足均衡下的相對不變性。 對于任意的，，

，.

（4）對于線性限制權重成比例。且對 ， ， 假設成立，如果 ，則令;如果，則令。因此， 根據定義2.1可知，權重圖博弈有效解滿足線性限制權重成比例性。

（5）剩余有效權重分配。對于任意，我們有：

因此，權重圖博弈有效解滿足剩余有效權重分配。

引理2.2? ?令，由于， ，并根據，得到下式，.

定理2.2 對于任意擬均衡博弈，權重圖博弈有效解是滿足有效性，均衡下的相對不變性，線性限制權重成比例以及剩余有效權重分配的唯一解。

證明? 假設是在擬均衡博弈上滿足有效性、均衡下的相對不變性、線性限制權重成比例，以及剩余有效權重分配的一個分配規則。 接下來我們證明，對于，有成立。 對于任意的，滿足剩余有效權重分配，即存在一個常數，使得? ? ? ? ? ? ? ? ? ? ? ? .

又由于滿足有效性，則有.

因此，對于任意局中人，有下式成立，

.

進而有下式成立，

.

對于的子博弈，也滿足有效性，則下式成立，

.

因此，可得

.

同理，根據定義2.1可知，有下式成立，

.

綜上所述，對于任意的，有下式成立，

.

令并且.因為，則. 由于與 均滿足S均衡下的相對不變性，因此有

，

.

那么，想要證明，證明即可。

由得

根據引理2.2，再由線性限制權重成比例性，對于任意，都存在兩個實數分別為使得下式成立

，

.

由于，

.

又因為 ， 因此. 由此可得對于任意的， 有成立， 進而有成立，即成立。 定理得證！

3 基于權重圖博弈有效解的特殊分配規則

權重圖博弈有效解是剩余平等分配解的推廣，相比于剩余平等分配解，權重圖博弈有效解包含了更為一般的情況， 建立在權重圖博弈有效解的基礎上，本節提出了以下幾種分配規則， 雖然他們是權重圖博弈有效解的特殊情況，但是在使用他們研究分配問題時卻有著不同的傾向和側重點。

3.1 剩余平等分配解

當每個局中人的權重均相同時，即 ，可以得到剩余平等分配，該分配的具體表達為：

定義3.1 （個人剩余公平性）對于任意擬均衡博弈，任意的，有變量滿足如下關系：

定理3.1? 剩余平等分配解是滿足有效性、均衡下的相對不變性、剩余公平性與限制成比例性的唯一解。

這一分配方式公理化的具體證明過程省略，該證明方式以定義2.1與定理2.2為依據與定理2.1證明過程類似。

3.2 剩余度分配解

當每個局中人的權重與其相連通的人數成比例時，，可以得到剩余度分配，該分配的具體表達：

定義3.2? （剩余度公平性）對于任意擬均衡博弈，任意的，有變量滿足如下關系：

定義3.3 （線性限制度值成比例）對于任意且對于任意的和;滿足;對于任意，存在實數，使得任意局中人， 有 成立。

定理3.2? ?剩余度分配解是滿足有效性、S均衡下的相對不變性、剩余度公平性以及限行限制度值成比例的唯一解。

具體證明過程省略，與定理3.1證明過程類似。

3.3 舉例

考慮擬均衡圖博弈，局中人的集合為; 特征函數為 其中表示其他聯盟。 ;通訊圖，用 表示兩大分支，分別為。 根據分配規則，τ值、剩余平等分配解、剩余度分配解的結果如表1所示。

根據分配結果我們可以發現，三大分配規則均滿足局中人聯系越廣泛收益越高的原則。將剩余度分配解與剩余平等分配解相比較發現，剩余度分配解對剩余的分配更有利于個人能力強的局中人，即合作密度越大，則收益所得越高;剩余平等分配對于剩余的分配更有利于弱勢群體，個人能力小的局中人所獲得的剩余比在剩余度分配解中能力小的局中人獲得收益更多。 因此，對于合作密度更大的局中人，剩余度分配解分配給他們的更多;對于合作密度更小的局中人，剩余平等分配解分配給他們的更少。

4 結語

本文提出了一種基于τ值的分配規則，并根據新的公理完成兩個具體分配規則的公理化。作為對經典τ值的推廣，第一，提出線性限制成比例、剩余比例分配，建立在這一基礎上公理化權重圖博弈有效解。 第二，提出個人剩余公平性、剩余度公平性，進而可公理化剩余平等分配解以及剩余度公平分配解這兩個特殊分配規則，并對比這兩種特殊分配規則在具體情境下的分配情況。我們發現對于剩余度分配解更有利于機理能力強的局中人，而剩余平等分配解更關注弱勢群體。

參考文獻

Myerson R B. Graphs and cooperation in games[J]. Mathematics of Operations Research， 1977（2）：225-229.

Tijs H.Bounds for the core and the T-value.Moeschlin O.and Pallaschke D.（eds.），Game Theory and Mathematical Economics， North-Holland，1981.

王文文，孫浩，韓衛彬.圖限制下合作對策的τ值[J].運籌學學報，2011，15（4）：75-84.

Kamijo Y.A two-step Shapley value for cooperative games with coalition structures [J]. International Game Theory Review， 2009， 11

Guang Zhang， Erfang Shan， Liying Kang， Yanxia Dong， Two efficient values of cooperative games with graph structure based on τ-value[J]. Journal of Combinatorial Optimization， 2017， 34（2）： 462-482.

Sylvain Béal， Eric Rémila， Philippe Solal. Fairness and fairness for neighbors：The difference between the Myerson value and component-wise egalitarian solutions[J]. Economics Letters， 2012，117（1）：263-267.

Erfang Shan，Guang Zhang，Yanxia Dong.Component-wise proportional solutions for communication graph games[J].Mathematical Social Sciences，2016（81）：22-28.

Jilei Shi，Erfang Shan.Weighted component-wise solutions for graph games[J].Economics Letters，2020.

van den Brink R， Khmelnitskaya A， van der Laan G. An efficient and fair solution for communication graph games [J]. Economics Letters， 2012， 117 （3）： 786–789.

Hu X F，Li D F， Xu G J.Fair distribution of surplus and efficient extensions of the Myerson value[J]. Economics Letters，2018，165：1-5.

Erfang Shan， Jiayu Han，Jilei Shi.The efficient proportional Myerson values[J].Operations Research Letters，2019，47（6）： 574-578.

Efficient Weight Allocation Rules for Graph Game Based on τValue

School of Statistics and Information， Shanghai University of International Business and Economics

XUE Tao? DONG Yanxia

Abstract： Firstly， the effective solution of the weight graph game based on τvalue is proposed， and this single-valued solution is both a generalization of τvalue of under the graph game and an extension of the solution based on the remaining average distribution of τ. Secondly， the effective solution of the weight graph game is axiomatic described by using branch validity， relative invariance under S-equilibrium， residual effective weight distribution and linear limited weight proportion. Finally， a special allocation rule based on the effective solution of weight graph game is introduced.

Keywords： graph structure; efficient solution; τvalue; component efficiency