The symmetric Banzhaf value for fuzzy games with a coalition structure

In this paper,a generalized form of the symmetric Banzhaf value for cooperative fuzzy games with a coalition structure is proposed.Three axiomatic systems of the symmetric Banzhaf value are given by extending crisp case.Furthermore,we study the symmetric Banzhaf values for two special kinds of fuzzy games,which are called fuzzy games with multilinear extension form and a coalition structure,and fuzzy games with Choquet integral form and a coalition structure,respectively.     

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

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 .     

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

考虑到现实应用中,局中人可能以不同的参与度参加到不同的联盟中,并且他们在合作之前不确定不同合作策略选择下的收益,则在传统合作博弈中应用模糊数学理论。基于Choquet积分,将支付函数和参与度拓展为模糊数,给出要素双重模糊下的模糊合作博弈的定义和模糊合作博弈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.     

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.     

基于合作博弈的虚拟化资源效用分配策略

效用分配是网格虚拟化资源提供者结成联盟完成用户任务时的关键问题。针对资源提供者建立联盟来提高网格整体效用的情况,研究了利用合作博弈论分配网格资源。给出了资源建立联盟的依据,并以基于费用最小化的MIN_COST算法得到了资源的最优化映射方案。在效用分配中,分别从联盟效用的平均分配和Shapley值分配两方面进行了分析,提出了基于Shapley值的资源联盟效用分配策略。算例结果表明,网格资源联盟可以提高任务的执行效率和资源整体收益,而Shapley值法在均衡联盟个体的效用分配方面也是有效可行的。     

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.     

Cooperative network design: A Nash bargaining solution approach

The Network Design problem has received increasing attention in recent years. Previous works have addressed this problem considering almost exclusively networks designed by selfish users, which can be consistently suboptimal. This paper addresses the network design issue using cooperative game theory, which permits to study ways to enforce and sustain cooperation among users. Both the Nash bargaining solution and the Shapley value are widely applicable concepts for solving these games. However, the Shapley value presents several drawbacks in this context.For this reason, we solve the cooperative network design game using the Nash bargaining solution (NBS) concept. More specifically, we extend the NBS approach to the case of multiple players and give an explicit expression for users’ cost allocations. We further provide a distributed algorithm for computing the Nash bargaining solution. Then, we compare the NBS to the Shapley value and the Nash equilibrium solution in several network scenarios, including real ISP topologies, showing its advantages and appealing properties in terms of cost allocation to users and computation time to obtain the solution.Numerical results demonstrate that the proposed Nash bargaining solution approach permits to allocate costs fairly to users in a reasonable computation time, thus representing a very effective framework for the design of efficient and stable networks.     

A study on the goal value for massively multiplayer online role-playing games players

This study examines the goal of value sought by players of the massively multiplayer online role playing games (MMORPGs). We drew on the Means-end Chains (MECs) model frequently used in marketing as a theoretical basis. Soft laddering method was also adopted as a tool for in-depth interviews. Content analysis was used to analyze the “Attributes–Consequences–Values” for MMORPGs players, then converted into a hierarchical value map (HVM). The study found that role-playing, interface design, multiplayer gaming, independent play, popularity and virtual pets were the order of game attributes users took into consideration when playing MMORPGs. The consequences benefits for the users were, in order, enhanced interaction, more fun, enhanced efficiency, fantasy fulfillment, winning, novelty, more insurance, increased wealth and stress relief. The value targets sought by players were concluded to be fun and enjoyment in life, sense of accomplishment, warm relationships with others, sense of belonging and security in order of importance.     

Harsanyi power solutions for cooperative games on voting structures

This paper deals with Harsanyi power solutions for cooperative games in which partial cooperation is based on specific union stable systems given by the winning coalitions derived from a voting game. This framework allows for analyzing new and real situations in which there exists a feedback between the economic influence of each coalition of agents and its political power. We provide an axiomatic characterization of the Harsanyi power solutions on the subclass of union stable systems arisen from the winning coalitions from a voting game when the influence is determined by a power index. In particular, we establish comparable axiomatizations, in this context, when considering the Shapley-Shubik power index, the Banzhaf index and the Equal division power index which reduces to the Myerson value on union stable systems. Finally, a new characterization for the Harsanyi power solutions on the whole class of union stable systems is provided and, as a consequence, a characterization of the Myerson value is obtained when the equal power measure is considered.     

Uncertain Shapley value of coalitional game with application to supply chain alliance

Uncertain coalitional game deals with situations in which the transferable payoffs are uncertain variables. The uncertain core has been proposed as the solution of uncertain coalitional game. This paper goes further by presenting two definitions of uncertain Shapley value: expected Shapley value and α-optimistic Shapley value. Meanwhile, some characterizations of the uncertain Shapley value are investigated. Finally, as an application, uncertain Shapley value is used to solve a profit allocation problem of supply chain alliance.     

Reduced game property of the Egalitarian Non-k-Averaged Contribution (EN k AC-) value and the Shapley value

The Egalitarian Non- k -Averaged Contribution (EN ^k AC-) value for TU-game represents the equal division of the surplus of the total profits, given that each player is already allocated his individual contribution specified by worths of coalitions of size k . This paper deals with the axiomatic characterization of the EN ^k AC-value on the class of cooperative games with a fixed player set as well as a variable player set. The latter axiomatization involves a consistency axiom in terms of the reduced games. The EN ^k AC-value is the unique value on the class of cooperative games with a variable player set which possesses the relative invariance under strategic equivalence, the equal treatment property and the reduced game property for two types of reduced games. We also propose a new reduced game in terms of which the Shapley value is axiomatized.     

A new fast heuristic for labeling points

In the point site labeling problem, we are given a set P={p₁,p₂,…,pn} of point sites in the plane. The label of a point pi is an axis-parallel rectangle of specified size. The objective is to label the maximum number of points on the map so that the placed labels are mutually non-overlapping. Here, we investigate a special class of the point site labeling problem where (i) height of the labels of all the points are same but their lengths may differ, (ii) the label of a point pi touches the point at one of its four corners, and (iii) the label of one point does not obscure any other point in P. We describe an efficient heuristic algorithm for this problem which runs in time in the worst case. We run our algorithm as well as the algorithm Rules proposed by Wagner et al. on randomly generated point sets and on the available benchmarks. The results produced by our algorithm are almost the same as Rules in most of the cases. But our algorithm is faster than Rules in dense instance. We have also computed the optimum solutions for all the examples we have considered by designing an algorithm, which performs an exhaustive search in the worst case. We found that the exhaustive search algorithm runs reasonably fast for most of the examples we have considered.     

An output sensitive algorithm for computing a maximum independent set of a circle graph

We present an output sensitive algorithm for computing a maximum independent set of an unweighted circle graph. Our algorithm requires O(nmin{d,α}) time at worst, for an n vertex circle graph where α is the independence number of the circle graph and d is its density. Previous algorithms for this problem required Θ(nd) time at worst.     

Configuration representation and reconfiguration optimization for the reconfigurable robots with independent manipulation

Single module of the reconfigurable robots with independent manipulation can perform the actions of locomotion and manipulation. In conformity with the request for achieving autonomous operation in the unstructurized environment instead of fixed operation in the structurized environment, these robots are applied in the complicated and dangerous environment. The existing researches on the configuration theory focus on the reconfigurable robots with limited locomotion and the ones with independent locomotion, not being applicable to the reconfigurable robots with independent manipulation. The vector configuration is put forward, the research content of which contains the topology and locomotion direction of configuration, the posture and orientation and connection relation between modules. Module state vector and configuration state matrix are proposed for representation methodology for the swarm configuration of these reconfigurable robots, which supports transformation operation to represent and trigger behavior motion of the module and reconfiguration between configurations. Optimization algorithm of assembly reconfiguration applying workload as the optimization target is presented, as well as optimization algorithm of transformation reconfiguration applying the integration of posture orientation workload and connection workload. The result of optimization is the relation of state transformation between the initial configuration and the object one as the basic of reconfiguration plan and control. Supported by the National High-Tech Research and Development Program of China (Grant No. 2006AA04Z254) and the Scientific Research Fund for Doctor of Liaoning Provice (Grant No. 20071007)     

Computing the Shapley value in allocation problems: approximations and bounds,with an application to the Italian VQR research assessment program

Abstract

In allocation problems with indivisible goods, money compensation is used to distribute worth in a fair way. Coalitional games provide a formal mathematical framework to model such problems, and the Shapley value is a solution concept widely used to realise a fair distribution. To overcome its intractability, we describe how to simplify allocation problems and we propose algorithms for computing lower bounds and upper bounds of the Shapley value that can be combined with approximation algorithms. The proposed techniques have been implemented and tested on a real-world application of allocation problems, namely, the Italian research assessment program known as VQR.     

FAHP改进Shapley值法进行工程科技创新收益分配

从合作博弈论视角分析了工程科技合作创新收益合理分配的问题,运用Shapley值法对创新联盟的收益进行初次分配;基于模糊综合评价法（FAHP）从科技创新角色重要性、合作意识、成本投入、企业实力、承担风险等量化评价各创新成员的实际贡献率,据此修正初次分配Shapley值。用工程实际创新案例进行了计算分析,结果表明改进的分配方法合理地提高了核心创新单位和承担风险大的单位的收益,分配结果与成员在联盟中的价值相匹配,有利于创新联盟的稳定,具有可操作性和实用性,可为合作创新收益分配提供理论依据与方法。