Shapley 值的最優實現及其公理化

張 莉

（長治學院 數學系, 山西 長治 046011）

引言

合作博弈描述了參與者通過相互合作產生價值的情形.假設大聯盟最終會形成，如何公平合理的分配大聯盟的價值是合作博弈研究的根本問題之一.已有研究提出了各種各樣的合作博弈解，其中1953 年Shapley 提出的Shapley 值[1]是最為經典的合作博弈解之一，受到研究者的廣泛關注.目前，對于Shapley 值的理論研究主要集中于對Shapley 值的公理化研究[2-4]，用于說明Shapley 值的公平合理性。此外, Pérez-Castrillo從非合作的角度，給出了Shapley 值的非合作投標機制設計，證明了該機制的子博弈完美納什均衡的均衡結果與Shapley 值是一致的[5].從優化的角度對Shapley 值進行的研究還比較缺乏.事實上，當前文獻對于合作博弈解的優化實現有許多研究成果，例如1969 年Schmeidler 提出了核子[6]，核子是基于聯盟抱怨，用字典序的方法在分配集中找到的最優解.類似于核子的基本思想，研究者通過定義不同的聯盟抱怨，得到了廣義核子[7]、SM-核子[8]、SD-預核子[9]等.

文章考慮單個參與者對于分配的抱怨，提出了一個衡量參與者抱怨的標準.基于這一標準，用字典序的方法在預分配集中得到最優解，并證明了該最優解與Shapley 值是一致的.最后，文章提出了一個新公理——個體超量相等性，該公理旨在說明每個參與者對于分配的抱怨是相等的，用有效性與個體超量相等性可以對Shapley 值進行公理化.

1 基本概念

2 主要結論

2.1 最優實現

這一小節給出Shapley 值的最優實現。具體來說，從參與者個體的角度出發，結合大聯盟的形成過程，首先提出衡量單個參與者抱怨的標準，然后在預分配集中尋找使得參與者抱怨按字典序最小的預分配，該最優解與Shapley 值是一致的.

由上述定理可知，Shapley 值是預分配集中使得 按字典序最小的解.

2.2 Shapley 值的公理化

這一小節介紹一個新公理，即個體超量相等性，結合有效性，個體超量相等性可以公理化Shapley 值.

定理7 Shapley 值是唯一滿足有效性和個體超量相等性的解.

證明：

（1）存在性：顯然Shapley 值滿足有效性.由定理5 的證明可知，Shapley 值滿足個體超量相等性，且Shapley 值使得每個參與者的個體超量均為0.

有效性與個體超量相等性是邏輯獨立的.

考慮均分解（簡稱ED）：

該解滿足個體超量相等性，但不滿足有效性.

3 結語

文章主要研究了Shapley 值的優化實現及其公理化.從參與者個體的角度定義了個體超量的概念.證明了Shapley 值是預分配集中選擇使得個體超量向量按字典序最小的預分配.此外，文章給出了Shapley 值的一組公理化.對于其他合作博弈解的優化實現可進一步進行研究.