基于τ值的圖博弈有效權(quán)重分配規(guī)則

薛濤 董艷俠

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

關(guān)鍵詞：圖結(jié)構(gòu);有效解;τ值;分支有效性

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

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

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

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

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

1 基本定義

在合作博弈中，可以為任意一個由個局中人組成的聯(lián)盟分配一個由實數(shù)表示的收益， 這一博弈被稱為可轉(zhuǎn)移效用博弈， 即博弈。該博弈可以由有序?qū)ε急硎?，其中表示有限局中人集合?特征函數(shù)，。 用表示由個局中人組成的聯(lián)盟的收益，其中。

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

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

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

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

，，且，

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

，

如果， 則.

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

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

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

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

。

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

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

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

2 權(quán)重圖博弈有效解及其公理化

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

2.1 權(quán)重圖博弈有效解的提出

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

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

，.

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

2.2 權(quán)重圖博弈有效解的公理化

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

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

，

，

，

由于，故有.

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

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

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

成立;

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

.

證明 （1）有效性。由于

.

因此，權(quán)重圖博弈有效解滿足有效性。

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

，.

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

.

因此，權(quán)重圖博弈有效解滿足個人理性。

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

，.

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

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

因此，權(quán)重圖博弈有效解滿足剩余有效權(quán)重分配。

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

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

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

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

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

.

進而有下式成立，

.

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

.

因此，可得

.

同理，根據(jù)定義2.1可知，有下式成立，

.

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

.

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

，

.

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

由得

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

，

.

由于，

.

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

3 基于權(quán)重圖博弈有效解的特殊分配規(guī)則

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

3.1 剩余平等分配解

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

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

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

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

3.2 剩余度分配解

當(dāng)每個局中人的權(quán)重與其相連通的人數(shù)成比例時，，可以得到剩余度分配，該分配的具體表達：

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

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

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

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

3.3 舉例

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

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

4 結(jié)語

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

參考文獻

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.

王文文，孫浩，韓衛(wèi)彬.圖限制下合作對策的τ值[J].運籌學(xué)學(xué)報，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