有向图对策下的Banzhaf值及其应用

Banzhaf Value for Digraph Games and Its Applications

Banzhaf值是经典可转移效用合作对策中重要的分配规则之一,它假设任何有限参与者间均能进行合作形成可行联盟。2006年,Alonso-Meijide和Fiestras-Janeiro考虑无向网络,定义了图对策下的Banzhaf值,以此反映合作网络对参与者间合作以及分配结果的影响。本文则在此基础上,考虑合作网络的方向性,将Banzhaf值进一步推广到有向图对策中,提出了新的分配规则——有向Banzhaf值。首先,本文证明了有向Banzhaf值满足准隔离性、收缩性、公平性、强分支可分解性以及强分支总贡献性。其次,证明了有向Banzhaf值可由公平性、准隔离性以及收缩性唯一刻画,也可由公平性结合强分支总贡献性唯一刻画。最后,以湿地水循环系统为例,对有向Banzhaf值和其他值进行了比较分析,讨论了有向Banzhaf值的应用价值。

Banzhaf value is one of the important allocation rules in classical cooperative games with transferable utility,which assumes that any participants can cooperate to form a feasible coalition.However,in reality,cooperation between participants is often constrained by various cooperation structures,resulting in some coalitions that cannot be truly formed.Considering the influence of cooperation structures on participants,Myerson proposed a cooperative game with graph structure,also known as communication situation game,referred to as graph game.The graph game describes the cooperation structure between participants by an undirected graph.The points of the graph represent the participants,and the edges of the graph represent some bilateral connection between the participants.He assumed that only connected coalitions can fully cooperate and produce cooperative utility,while the utility of other coalitions can only be obtained by the sum of the utility of the connected components it contains.Based on this idea,Alonso-Meijide and Fiestras-Janeiro extended Banzhaf value to graph games,and defined Banzhaf value under graph restricted games,namely the graph Banzhaf value.At the same time,they proved that the graph Banzhaf value can be given four axiomatic characterizations by fairness,isolation,merging,component total power and balanced contribution.Although the graph game reflects some bilateral connections between participants,not all the connections between participants are bilateral.For example,the water cycle in nature has a clear direction;The South-to-North Water Diversion Project transfers water from the Yangtze River,and flows through the northern region in turn,which is also directional;The industrial water system first uses industrial water for the production water subsystem,and then discharges the sewage generated by the production water subsystem into the sewage treatment subsystem.According to the flow direction of the river,the main body of water use in public rivers has an upstream and downstream relationship.Therefore,when studying the resource allocation problem of public rivers,the direction of the model cannot be ignored.In order to describe such problems,scholars have introduced directed graphs into cooperative games and proposed cooperative games with directed graph structure,referred to as directed graph games.Li and Shan studied the definition of feasible coalition in directed graph games.They argue that a strong component can be used as a feasible coalition in a directed graph game,assuming that a strongly connected coalition can obtain full utility,while the utility of a non-strongly connected coalition is realized by the sum of all the strong component utilities it contains.The research of Li and Shan makes it very easy to find feasible coalitions in directed graph games,and also provides convenience for further research on allocation rules in directed graph games.On this basis,studying the allocation rules in directed graph games can provide a theoretical basis for solving directed network problems such as water resources allocation.On this basis,we consider directionality of cooperative network,extend the Banzhaf value to digraph game,and propose a new allocation rule,called digraph Banzhaf value.We prove that the digraph Banzhaf value satisfies quasi-isolation,contractibility,fairness,strong component decomposability and strong component total power,and give two axiomatic characterizations.Finally,we discuss an application of digraph Banzhaf value in wetland water circulation systems and compare it with other values.