The Shapley and Banzhaf values in microarray games

We provide a characterization of the Banzhaf value on the class of the microarray games, and another characterization of the Shapley value, on the same class, in the spirit of [Moretti S, Patrone F, Bonassi S. The class of microarray games and the relevance index for genes. TOP 2007;15:256–80]. Then we compare the results given by the two indices when applied to a colon tumor data-set published in literature.     

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).     

Simplification of Shapley value for cooperative games via minimum carrier

Shapley value is one of the most fundamental concepts in cooperative games. This paper investigates the calculation of the Shapley value for cooperative games and establishes a new formula via carrier. Firstly, a necessary and sufficient condition is presented for the verification of carrier, based on which an algorithm is worked out to find the unique minimum carrier. Secondly, by virtue of the properties of minimum carrier, it is proved that the profit allocated to dummy players (players which do not belong to the minimum carrier) is zero, and the profit allocated to players in minimum carrier is only determined by the minimum carrier. Then, a new formula of the Shapley value is presented, which greatly reduces the computational complexity of the original formula, and shows that the Shapley value only depends on the minimum carrier. Finally, based on the semi-tensor product (STP) of matrices, the obtained new formula is converted into an equivalent algebraic form, which makes the new formula convenient for calculation via MATLAB.     

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

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

模糊合作对策区间Shapley值法的改进及应用

模糊合作对策的收益分配是个复杂问题,受到合作方的风险承担、合作努力、市场竞争、创新贡献和资源投入等因素的影响,而且不同因素有着不同的重要性。运用区间Shapley值法对模糊合作对策的收益进行初步分配。通过将AHP-GEM法和模糊综合评价法相结合,引入收益分配的综合修正因子,对区间Shapley值法进行改进,建立了模糊合作对策利益分配的改进模型。以制造业和物流业联盟为例,说明了改进模型的实用性和可行性。     

基于动态模糊联盟合作博弈的区间模糊Shapley值

利用模糊数学相关理论,针对n人合作博弈中支付函数是模糊三角函数的情形,对经典Shapley值提出的三条公理进行了拓展,并构造了区间模糊Shapley值。考虑到盟友在合作结束后需要对具体的联盟收益进行分配,利用构造的区间模糊Shapley值隶属函数给出了确定的收益分配方案。最后利用实例对该方法的有效性和可行性进行了说明。     

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.     

Parallel characterizations of a generalized Shapley value and a generalized Banzhaf value for cooperative games with level structure of cooperation

We present parallel characterizations of two different values in the framework of restricted cooperation games. The restrictions are introduced as a finite sequence of partitions defined on the player set, each of them being coarser than the previous one, hence forming a structure of different levels of a priori unions. On the one hand, we consider a value first introduced in Ref. [18], which extends the Shapley value to games with different levels of a priori unions. On the other hand, we introduce another solution for the same type of games, which extends the Banzhaf value in the same manner. We characterize these two values using logically comparable properties.     

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 .     

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.     

Missing value estimation for microarray data through cluster analysis

Microarray datasets with missing values need to impute accurately before analyzing diseases. The proposed method first discretizes the samples and temporarily assigns a value in missing position of a gene by the mean value of all samples in the same class. The frequencies of each gene value in both types of samples for all genes are calculated separately and if the maximum frequency occurs for same expression value in both types, then the whole gene is entered into a subset; otherwise, each portion of the gene of respective sample type (i.e., normal or disease) is entered into two separate subsets. Thus, for each gene expression value, maximum three different clusters of genes are formed. Each gene subset is further partitioned into a stable number of clusters using proposed splitting and merging clustering algorithm that overcomes the weakness of Euclidian distance metric used in high-dimensional space. Finally, similarity between a gene with missing values and centroids of the clusters are measured and the missing values are estimated by corresponding expression values of a centroid having maximum similarity. The method is compared with various statistical, cluster-based and regression-based methods with respect to statistical and biological metrics using microarray datasets to measure its effectiveness.     

Allocating the fixed cost based on data envelopment analysis in view of the Shapley value

This paper considers fixed cost allocation in view of cooperative game theory and proposes an approach based on data envelopment analysis while incorporating the perspectives of coalition efficiency and the Shapley value. To do this, we first build two models to evaluate coalition efficiencies before and after cost allocation, and we prove that all coalitions can be efficient after fixed cost allocation. Then, following the premise that each coalition makes itself efficient without reducing the efficiencies of other decision-making units' preallocation efficiency, we propose a model that determines the acceptable range of each coalition's allocated fixed cost. Furthermore, a model is constructed to determine the final cost allocation based on three principles: efficiency, monotonicity, and similarity. Moreover, the Shapley value is employed to obtain the cost allocated to each decision-making unit (DMU). The proposed approach considers the relationships among DMUs across their forming coalitions to determine their interaction types and then generates a fixed cost allocation result that possesses the features of the Shapley value. This process makes the fixed cost allocation more acceptable. Finally, a simple numerical example and an empirical case are provided to illustrate the calculation process of the proposed approach and compare our approach with the traditional methods.     

Polynomial calculation of the Shapley value based on sampling

In this paper we develop a polynomial method based on sampling theory that can be used to estimate the Shapley value (or any semivalue) for cooperative games. Besides analyzing the complexity problem, we examine some desirable statistical properties of the proposed approach and provide some computational results.     

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

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

Determination of the weights for the ultimate cross efficiency using Shapley value in cooperative game

This paper firstly revisits the cross efficiency evaluation method which is an extension tool of data envelopment analysis (DEA), then analyzes the potential flaws which happens when the ultimate average cross efficiency scores are used. In this paper, we consider the DMUs as the players in a cooperative game, where the characteristic function values of coalitions are defined to compute the Shapley value of each DMU, and the common weights associate with the imputation of the Shapley values are used to determine the ultimate cross efficiency scores. In the end, an empirical example is illustrated to examine the validity of the proposed method, and we also point out some further research directions in future.     

Statistical designs for two-color microarray experiments involving technical replication

In a two-color microarray experiment, we consider the issues of determination of which mRNA samples are to be labeled with which fluorescent dye and which mRNA samples are to be hybridized together on the same slide. Specific attention is given to the test-control experiments whose primary interest lies in comparing several test treatments with a control treatment. A statistical linear model is proposed to characterize two major sources of systematic variation: the variation among distinct slides and that between fluorescent dyes. Furthermore, the possible correlation due to technical replication is also incorporated into the model. A series of A-optimal or highly efficient designs are generated from a heuristic algorithm based on the proposed model. It is shown that the obtained designs are robust not only to the variation of the correlation because of technique replication, but also to the loss of one or two slides. In addition, the comparative experiments involving technical replication are also discussed.     

Computational aspects of the coarsening at random model and the Shapley value

This paper is concerned with computational aspects of coarse data in information technology. A method for calculating the CAR (coarsening at random) model of a finite random set is obtained, and a formula for computing the Shapley value using the distribution of the random set is given. The relationship between the CAR model solution and the Shapley value is also discussed. Several examples are given to illustrate our results.     

A value for games with a priori incompatible players

ABSTRACT

Numerous situations in decision-making deal with a set of agents who need to work together but they have some a priori bilateral problems among them. This paper introduces cooperative games with a priori incompatibilities using particular coalition systems. In these games, there are some red lines between some players, so that the negotiation has two stages. In the first stage, players can only negotiate with those with whom they are compatible. After that, the grand coalition will be formed. A value for these games is defined by using cooperative games with coalition configuration. A characterization of this value is obtained.     

基于修正区间模糊Shapley值信息产品供应链利益分配算法

信息产品供应链参与体面临风险差异,提出区间模糊Shapley算法分配信息产品收益以实现公平性。在收益不确定的条件下构造收益模糊值,引入区间模糊Shapley值的隶属度函数,给出确定的分配方案。综合考虑各项风险因素对利益分配的影响,采用模糊层次分析法对风险因子进行修正,以确保信息产品供应链的稳定性