The proportional coalitional Shapley value

We propose a modification of the Shapley value for monotonic games with a coalition structure. The resulting coalitional value is a twofold extension of the Shapley value in the following sense: (1) the amount obtained by any union coincides with the Shapley value of the union in the quotient game; and (2) the players of the union share this amount proportionally to their Shapley value in the original game (i.e., without unions). We provide axiomatic characterizations of this value close to those existing in the literature for the Owen value and include applications to coalition formation in bankruptcy and voting problems.     

An overview of recent applications of Game Theory to bioinformatics

The goal of this work is to provide a comprehensive review of different Game Theory applications that have been recently used to predict the behavior of non-rational agents in interaction situations arising from computational biology.In the first part of the paper, we focus on evolutionary games and their application to modelling the evolution of virulence. Here, the notion of Evolutionary Stable Strategy (ESS) plays an important role in modelling mutation mechanisms, whereas selection mechanisms are explained by means of the concept of replicator dynamics.In the second part, we describe a couple of applications concerning cooperative games in coalitional form, namely microarray games and Multi-perturbation Shapley value Analysis (MSA), for the analysis of genetic data. In both of the approaches, the Shapley value is used to assess the power of genes in complex regulatory pathways.     

A linear approximation method for the Shapley value

The Shapley value is a key solution concept for coalitional games in general and voting games in particular. Its main advantage is that it provides a unique and fair solution, but its main drawback is the complexity of computing it (e.g., for voting games this complexity is #p-complete). However, given the importance of the Shapley value and voting games, a number of approximation methods have been developed to overcome this complexity. Among these, Owen's multi-linear extension method is the most time efficient, being linear in the number of players. Now, in addition to speed, the other key criterion for an approximation algorithm is its approximation error. On this dimension, the multi-linear extension method is less impressive. Against this background, this paper presents a new approximation algorithm, based on randomization, for computing the Shapley value of voting games. This method has time complexity linear in the number of players, but has an approximation error that is, on average, lower than Owen's. In addition to this comparative study, we empirically evaluate the error for our method and show how the different parameters of the voting game affect it. Specifically, we show the following effects. First, as the number of players in a voting game increases, the average percentage error decreases. Second, as the quota increases, the average percentage error decreases. Third, the error is different for players with different weights; players with weight closer to the mean weight have a lower error than those with weight further away. We then extend our approximation to the more general k-majority voting games and show that, for n players, the method has time complexity O(k²n) and the upper bound on its approximation error is .     

Internal structure of coalitions in competitive and altruistic graphical coalitional games

This paper introduces a certain graphical coalitional game where the internal topology of the coalition depends on a prescribed communication graph structure among the agents. The game Value Function is required to satisfy four Axioms of Value. These axioms make it possible to provide a refined study of coalition structures on graphs by defining a formal graphical game and by assigning a Positional Advantage, based on the Shapley value, to each agent in a coalition based on its connectivity properties within the graph. Using the Axioms of Value the graphical coalitional game can be shown to satisfy properties such as convexity, fairness, cohesiveness, and full cooperativeness. Three measures of the contributions of agents to a coalition are introduced: marginal contribution, competitive contribution, and altruistic contribution. The mathematical framework given here is used to establish results regarding the dependence of these three types of contributions on the graph topology, and changes in these contributions due to changes in graph topology. Based on these different contributions, three online sequential decision games are defined on top of the graphical coalitional game, and the stable graphs under each of these sequential decision games are studied. It is shown that the stable graphs under the objective of maximizing the marginal contribution are any connected graph. The stable graphs under the objective of maximizing the competitive contribution are the complete graph. The stable graphs under the objective of maximizing the altruistic contribution are any tree.     

Optimum profit allocation in coalitional VoD service

Although video-on-demand (VoD) services are provided by many ISPs, the amount of content provided by each VoD service is one order smaller than that provided by rental video services, so the limited content count is one of the obstacles to widespread VoD services. To solve this problem, ISPs can form a coalition with other ISPs and use content owned by other ISPs. However, to form a coalition among multiple ISPs, ISPs need to rationally allocate the profit obtained by the coalition to convince all ISPs participating in the coalition. We propose using the Shapley value of the coalitional game as the rational allocation of profit. Assuming that all but one ISP has the same number of users or (and) the same number of rare content, we derive the Shapley value in closed form and clarify the influence of the numbers of users and rare content on the coalition. We also compare the Shapley value with three general allocation models and show that the Shapley value agrees with the allocation when the profit obtained by each content delivery is equally shared by two ISPs, one that accommodates the receiving user and the other that owns the delivered content.     

A Rough Set Approach to Estimating the Game Value and the Shapley Value from Data

A value of a game v is a function which to each coalition S assigns the value v(S) of this coalition, meaning the expected pay–off for players in that coalition. A classical approach of von Neumann and Morgenstern [6] had set some formal requirements on v which contemporary theories of value adhere to. A Shapley value of the game with a value v [14] is a functional Φ giving for each player p the value Φ_p(v) estimating the expected pay-off of the player p in the game. Game as well as conflict theory have been given recently much attention on the part of rough and fuzzy set communities [11,8,1,4,7,2]. In particular, problems of plausible strategies [1] in conflicts as well as problems related to Shapley's value [3,2] have been addressed.We confront here the problem of estimating a value as well as Shapley's value of a game from a partial data about the game. We apply to this end the rough set ideas of approximations, defining the lower and the upper value of the game and, respectively, the lower and upper Shapley value. We also define a notion of an exact coalition, on which both values coincide giving the true value of the game; we investigate the structure of the family of exact sets showing its closeness on complements, disjoint sums, and intersections of coalitions covering the set of players. This work sets open a new area of rough set applications in mining constructs from data. The construct mined in this case are values as well as Shapley values of games.     

Approximating power indices: theoretical and empirical analysis

Many multiagent domains where cooperation among agents is crucial to achieving a common goal can be modeled as coalitional games. However, in many of these domains, agents are unequal in their power to affect the outcome of the game. Prior research on weighted voting games has explored power indices, which reflect how much “real power” a voter has. Although primarily used for voting games, these indices can be applied to any simple coalitional game. Computing these indices is known to be computationally hard in various domains, so one must sometimes resort to approximate methods for calculating them. We suggest and analyze randomized methods to approximate power indices such as the Banzhaf power index and the Shapley–Shubik power index. Our approximation algorithms do not depend on a specific representation of the game, so they can be used in any simple coalitional game. Our methods are based on testing the game’s value for several sample coalitions. We show that no approximation algorithm can do much better for general coalitional games, by providing lower bounds for both deterministic and randomized algorithms for calculating power indices. We also provide empirical results regarding our method, and show that it typically achieves much better accuracy and confidence than those required.     

一种云间合作博弈资源提供方法

为了满足云资源消费者的需求,并有效扩展云资源的服务能力,设计基于云间合作博弈的资源联盟形成算法。以联盟总体利益最大化为目标,将多个云资源提供者间的合作行为建模为联盟博弈模型,从而得到最优联盟结构满足用户方的虚拟机实例请求;设计一种联盟的合并与分裂规则,使得最终联盟结构是稳定不变的;设计基于联盟成员贡献能力的标准化估计Banzhaf值法实现联盟总体利益的个体分割。实验结果表明,在不同虚拟机请求类型测试条件下,云联盟形成算法不仅可以确保更高的联盟总体利益,而且使利益分割更加公平,其算法执行效率也更高。     

Shapley值法的改进及其应用研究

为了求解没有哑元的合作对策问题,以经典Shapley值法为基础,提出了改进的Shapley值求解模型,并通过证明和推理对该改进Shapley值解进行了描述和刻画,结果表明:改进的Shapley函数和经典Shapely函数在形式上具有一致性,可以认为:改进的Shapley函数是经典Shapely函数在模糊领域的一个自然延续和拓展。在此基础上,以单个制造商、单个分销商和单个零售商构成的三级供应链为背景,将改进Shapley值法运用到其利润分配问题中,并用一个算例说明了该改进Shapley解的实用性和可行性。     

On the cardinality index and attitudinal character of fuzzy measures

We briefly introduce the fuzzy measure and then discuss its use in representing information about uncertain variables. A relationship between the fuzzy measure and the Dempster-Shafer belief structure is discussed and a method for generating the family of fuzzy measures associated with a belief structure is described. We discuss the use of the Shapley index as a means for introducing an extension of the concept of entropy to fuzzy measures called the Shapley entropy. It is shown that all fuzzy measures generated from a given Dempster-Shafer belief structure have the same value for their Shapley entropy. We introduce the cardinality index of a fuzzy measure and use it to define the attitudinal character of a fuzzy measure. A semantics for this attitudinal character in the framework of using fuzzy measures to represent information about uncertain variables is suggested.     

基于改进Shapley值的四级供应链利润分配研究

为求解供应链利润分配问题,以经典Shapley值法为基础,将利润分配视为没有哑元的合作对策问题,提出改进的Shapley值模型,通过证明和推理对该改进Shapley值解进行描述和刻画,运用该模型求解四级供应链利润分配问题,并用一个算例说明该改进Shapley解的实用性和可行性。结果表明,改进的Shapley函数和经典Shapley函数在形式上具有一致性,是经典Shapley函数在模糊领域的一个自然延续和拓展,能够有效解决供应链利润分配问题。     

Proof systems and transformation games

We introduce Transformation Games (TGs), a form of coalitional game in which players are endowed with sets of initial resources, and have capabilities allowing them to derive certain output resources, given certain input resources. The aim of a TG is to generate a particular target resource; players achieve this by forming a coalition capable of performing a sequence of transformations from a combined set of initial resources to the target resource. TGs can model a number of natural settings, such as cooperative proof systems, where a collection of agents having different expertise work together to derive a proof for a target theorem, or supply chains, where agents cooperate to create a target product from base resources. After presenting the TG model, and discussing its interpretation, we consider possible restrictions on the transformation chain, resulting in different coalitional games. Following the basic model, we consider the computational complexity of several problems in TGs, such as testing whether a coalition wins, checking if a player is a dummy or a veto player, computing the core of the game, computing power indices, and checking the effects of possible restrictions on the coalition. Finally, we consider extensions to the model in which transformations have associated costs.     

Characterizations of a Shapley value for multichoice games

The main focus of this paper is on a Shapley value for multichoice games introduced by van den Nouweland et al. (ZOR–Math. Meth. Oper. Res. 41?:?289–311, 1995). Here we provide several characterizations from traditional game theory and redefine them in the framework of multichoice games. Meanwhile, the relationship between core and this Shapley value for multichoice games is discussed. When multichoice games are convex, this Shapley value is a multichoice population monotonic allocation scheme (MPMAS).     

Two-stage network games

In the paper, two-stage network games are studied. At the first stage of the game, the players form a network, while at the second stage they choose strategies according to the network realized at the first stage. Both noncooperative and cooperative settings are considered. In the noncooperative case, the Nash equilibrium is used as a solution concept, whereas the cooperative setting involves an allocation (the Shapley value) as a solution concept. It is demonstrated that the Shapley value does not satisfy the time consistency property.     

Cooperative games with multiple attributes

ABSTRACT

In this paper, we introduce the notion of a cooperative game with multiple attributes where players can provide partial participations in multiple attributes and form coalitions. The power or influence of the players due to their multiple attributes is evaluated based on their memberships in the coalitions. Our game therefore, extends the notion of cooperative games with fuzzy coalitions. The Shapley function for this class of games is proposed as a rational and fair solution concept. Every fuzzy game stems out of a specific crisp game under the assumption that the players provide partial memberships in forming multiple coalitions simultaneously. We adopt similar techniques to obtain the cooperative games with multiple attributes from their crisp counterparts and subsequently determine their Shapley functions.     

The Shapley value of cooperative games under fuzzy settings: a survey

We survey the recent developments in the studies of cooperative games under fuzzy environment. The basic problems of a cooperative game in both crisp and fuzzy contexts are to find how the coalitions form vis-á-vis how the coalitions distribute the worth. One of the fuzzification processes assumes that the coalitions thus formed are fuzzy in nature having only partial participations of the players. A second group of researchers fuzzify the worths of the coalitions while a few others assume that both the coalitions and the worths are fuzzy quantities. Among the various solution concepts of a cooperative game, the Shapley value is the most popular one-point solution concept which is characterized by a set of rational axioms. We confine our study to the developments of the Shapley value in fuzzy setting and try to highlight the respective characterizations.     

On the computational complexity of qualitative coalitional games

We study coalitional games in which agents are each assumed to have a goal to be achieved, and where the characteristic property of a coalition is a set of choices, with each choice denoting a set of goals that would be achieved if the choice was made. Such qualitative coalitional games (qcgs) are a natural tool for modelling goal-oriented multiagent systems. After introducing and formally defining qcgs, we systematically formulate fourteen natural decision problems associated with them, and determine the computational complexity of these problems. For example, we formulate a notion of coalitional stability inspired by that of the core from conventional coalitional games, and prove that the problem of showing that the core of a qcg is non-empty is D^p₁-complete. (As an aside, we present what we believe is the first “natural” problem that is proven to be complete for D^p₂.) We conclude by discussing the relationship of our work to other research on coalitional reasoning in multiagent systems, and present some avenues for future research.     

要素双重模糊下的合作博弈Shapley值的算法

考虑到现实应用中,局中人可能以不同的参与度参加到不同的联盟中,并且他们在合作之前不确定不同合作策略选择下的收益,则在传统合作博弈中应用模糊数学理论。基于Choquet积分,将支付函数和参与度拓展为模糊数,给出要素双重模糊下的模糊合作博弈的定义和模糊合作博弈Shapley值的定义。应用模糊结构元理论,构造了要素双重模糊下的模糊合作博弈的Shapley值,使模糊Shapley值的隶属函数得到解析表达。通过一个算例,来说明该模型的具体应用。可以看出,该研究方法和结论易掌握、推广,使模糊合作博弈理论可以更广泛地应用到现实生活中。     

A Cooperative Coalitional Game in Duopolistic Supply-Chain Competition

Cooperative coalitional games study the selection of chain partners, the formation of supply chains and outcome allocations. The chain value of a coalition depends on the outcome of inter-chain competition. Subsequently, chain partners may accept their payoffs or decide to defect to another coalition that has made a higher tender offer. The formation and defection continues until a stable Cournot-Nash equilibrium is reached. This is the state where no player may unilaterally defect to another coalition and earn a higher profit. We formulate the cooperative coalitional game as a variational inequality problem and propose an iterative diagonalization algorithm to determine the steady state for the game. The computational results illustrated that (1) supply-chain competition may not necessarily preserve the same level of social welfare; (2) internalization of resources and costs may distort the general competition economy; and (3) wielding the power in a supply chain does not necessarily translate into higher profits.     

Shapley Value of a Cooperative Game with Fuzzy Set of Feasible Coalitions

The paper investigates Shapley value of a cooperative game with fuzzy set of feasible coalitions. It is shown that the set of its values is a type 2 fuzzy set (a fuzzy set whose membership function takes fuzzy values) of special type. Furthermore, the corresponding membership function is given. Elements of the support of this set are defined as particular Shapley values. The authors also propose the procedure of constructing these elements with maximum reliability of their membership and reliability of non-membership, not exceeding a given threshold.