Cooperation indices and coalitional value

Summary We introduce an allocation rule for situations defined by a TUgame, a cooperation index and a coalition structure, and characterize it axiomatically. This rule is an extension of Owen's coalitional value; in fact, a variety of previously studied game situations is shown to be embodied and unified by our model.     

Contractually stable networks

We consider situations where players are part of a network and belong to coalitions in a given coalition structure. We propose the concept of contractual stability to predict the networks that are going to emerge at equilibrium when the consent of coalition partners is needed for adding or deleting links. Two different decision rules for consent are analyzed: simple majority and unanimity. We characterize the coalition structures that make the strongly efficient network contractually stable under the unanimity decision rule and the coalition structures that sustain some critical network as contractually stable under the simple majority decision rule and under any decision rule requiring the consent of any proportion of coalition partners. Requiring the consent of coalition members may help to reconcile stability and efficiency in some classical models of network formation.     

Linear and symmetric allocation methods for partially defined cooperative games

A partially defined cooperative game is a coalition function form game in which some of the coalitional worths are not known. An application would be cost allocation of a joint project among so many players that the determination of all coalitional worths is prohibitive. This paper generalizes the concept of the Shapley value for cooperative games to the class of partially defined cooperative games. Several allocation method characterization theorems are given utilizing linearity, symmetry, formulation independence, subsidy freedom, and monotonicity properties. Whether a value exists or is unique depends crucially on the class of games under consideration. Received June 1996/Revised August 2001     

Stability of the core mapping in games with a countable set of players

Greenberg (1990) and Ray (1989) showed that in coalitional games with a finite set of players the core consists of those and only those payoffs that cannot be dominated using payoffs in the core of a subgame. We extend the definition of the dominance relation to coalitional games with an infinite set of players and show that this result may not hold in games with a countable set of players (even in convex games). But if a coalitional game with a countable set of players satisfies a mild continuity property, its core consists of those and only those payoff vectors which cannot be dominated using payoffs in the core of a subgame.     

A linear proportional effort allocation rule

This paper proposes a new class of allocation rules in network games. Like the solution theory in cooperative games of how the Harsanyi dividend of each coalition is distributed among a set of players, this new class of allocation rules focuses on the distribution of the dividend of each network. The dividend of each network is allocated in proportion to some measure of each player’s effort, which is called an effort function. With linearity of the allocation rules, an allocation rule is specified by the effort functions. These types of allocation rules are called linear proportional effort allocation rules. Two famous allocation rules, the Myerson value and the position value, belong to this class of allocation rules. In this study, we provide a unifying approach to define the two aforementioned values. Moreover, we provide an axiomatic analysis of this class of allocation rules, and axiomatize the Myerson value, the position value, and their non-symmetric generalizations in terms of effort functions. We propose a new allocation rule in network games that also belongs to this class of allocation rules.     

Intra-party decision making, party formation, and moderation in multiparty systems

We establish coalitional stable party structures of a party formation game in an elected assembly. Farsighted political players can commit to form parties and to vote on policies according to the party position which is determined by intra-party majority rule. Parties may form governments and block proposals by a randomly selected member of the government. If the government recognition rule allows for the formation of multiparty governments, the median parliamentarian either realizes her ideal point or a policy lottery which she strictly prefers to the status quo. This outcome is enforced by the threat of forming a moderating centre party.     

The Owen and Banzhaf–Owen values revisited

In this work, we consider games with coalitional structure. We afford two new parallel axiomatic characterizations for the well-known Owen and Banzhaf–Owen coalitional values. Two properties are common to both characterizations: a property of balanced contributions and a property of neutrality. The results prove that the main difference between these two coalitional values is that the former is efficient, while the latter verifies a property of 2-efficiency.     

Dynamic resource allocation in fuzzy coalitions: a game theoretic model

We introduce an efficient and dynamic resource allocation mechanism within the framework of a cooperative game with fuzzy coalitions (cooperative fuzzy game). A fuzzy coalition in a resource allocation problem can be so defined that membership grades of the players in it are proportional to the fractions of their total resources. We call any distribution of the resources possessed by the players, among a prescribed number of coalitions, a fuzzy coalition structure and every membership grade (equivalently fraction of the total resources), a resource investment. It is shown that this resource investment is influenced by the satisfaction of the players in regard to better performance under a cooperative setup. Our model is based on the real life situations, where possibly one or more players compromise on their resource investments in order to help forming coalitions.     

Cooperative game theoretic centrality analysis of terrorist networks: The cases of Jemaah Islamiyah and Al Qaeda

The identification of key players in a terrorist organization aids in preventing attacks, the efficient allocation of surveillance measures, and the destabilization of the corresponding network. In this paper, we introduce a game theoretic approach to identify key players in terrorist networks. In particular we use the Shapley value as a measure of importance in cooperative games that are specifically designed to reflect the context of the terrorist organization at hand. The advantage of this approach is that both the structure of the terrorist network, which usually reflects a communication and interaction structure, as well as non-network features, i.e., individual based parameters such as financial means or bomb building skills, can be taken into account. The application of our methodology to the analysis results in rankings of the terrorists in the network. We illustrate our methodology through two case studies: Jemaah Islamiyah’s Bali bombing and Al Qaedas 9/11 attack, which lead to new insights in the operational networks responsible for these attacks.     

Cooperation when some players are incompatible

A situation with incompatibilities is defined to be a TU-game together with a graph whose arcs link pairs of incompatible players. In this paper we introduce an efficient and fair allocation rule which selects a payoff for every possible situation with incompatibilities (when the set of players is fixed), and prove that it is uniquely determined. Besides, we demonstrate that it is stable, study its relationship with the so-calledIR-Shapley value and show that it generalizes an earlier theory for simple games. Finally, the communication situations with incompatibilities are studied.We thank University of Santiago de Compostela and Xunta de Galicia for financial support through projects 60902.25064(5060) and XUGA20701B91.     

On weighted Shapley values

Nonsymmetric Shapley values for coalitional form games with transferable utility are studied. The nonsymmetries are modeled through nonsymmetric weight systems defined on the players of the games. It is shown axiomatically that two families of solutions of this type are possible. These families are strongly related to each other through the duality relationship on games. While the first family lends itself to applications of nonsymmetric revenue sharing problems the second family is suitable for applications of cost allocation problems. The intersection of these two families consists essentially of the symmetric Shapley value. These families are also characterized by a probabilistic arrival time to the game approach. It is also demonstrated that lack of symmetries may arise naturally when players in a game represent nonequal size constituencies.     

Weighted multiple majority games with unions: Generating functions and applications to the European Union

An a priori system of unions or coalition structure is a partition of a finite set of players into disjoint coalitions which have made a prior commitment to cooperate in playing a game. This paper provides “ready-to-apply” procedures based on generating functions that are easily implementable to compute coalitional power indices in weighted multiple majority games. As an application of the proposed procedures, we calculate and compare coalitional power indices under the decision rules prescribed by the Treaty of Nice and the new rules proposed by the Council of the European Union.     

Partnership formation and binomial semivalues

Partnership formation in cooperative games is studied, and binomial semivalues are used to measure the effects of such a type of coalition arising from an agreement between (a group of) players. The joint effect on the set of involved players is also compared with that of the alternative alliance formation. The simple game case is especially considered, and the application to a real life example illustrates the use of coalitional values closely related to the binomial semivalues when dealing with partnership formation and coalitional bargaining simultaneously.     

A Note on the Private Core and Coalitional Fairness under Asymmetric Information

We study relations among Walrasian expectations allocations, coalitional fair allocations and the private core of economies with uncertainty and asymmetric information. Our analysis covers finite exchange models, as well as models of mixed markets consisting of some large traders and an ocean of small traders. The adopted notion of coalitional fairness requires that: 1. Under a “c-fair” allocation, no coalition could benefit from achieving the net trade of some other disjoint coalition; 2. Coalition bargaining takes place without information sharing among agents. We introduce a notion of restricted Walrasian expectations allocation and examine its relations with c-fairness.     

Bargaining and membership

In coalitional games in which the players are partitioned into groups, we study the incentives of the members of a group to leave it and become singletons. In this context, we model a non-cooperative mechanism in which each player has to decide whether to stay in her group or to exit and act as a singleton. We show that players, acting myopically, always reach a Nash equilibrium.     

排序对策的一个新的收益分配准则

针对一个机器的排序问题,给出了排序问题中成本增加量的表达式,提出了收益分配的不小于成本增加量准则。针对一类特殊的排序问题,给出一个符合不小于成本增加量分配准则的解,并证明了它满足有效性,哑元性和单调性。结合一个算例,对本文的提出的方法进行了分析验证。     

Conference structures and fair allocation rules

To describe how the outcome of a cooperative game might depend on which groups of players hold cooperative planning conferences, we study allocation rules, which are functions mapping conference structures to payoff allocations. An allocation rule is fair if every conference always gives equal benefits to all its members. Any characteristic function game without sidepayments has a unique fair allocation rule. The fair allocation rule also satisfies a balanced contributions formula, and is closely related to Harsanyi's generalized Shapley value for games without sidepayments. If the game is superadditive, then the fair allocation rule also satisfies a stability condition.     

图上合作博弈和图的边密度

1977年, Myerson建立了以图作为合作结构的可转移效用博弈模型(也称图博弈), 并提出了一个分配规则, 也即"Myerson 值", 它推广了著名的Shapley值. 该模型假定每个连通集合(通过边直接或间接内部相连的参与者集合)才能形成可行的合作联盟而取得相应的收益, 而不考虑连通集合的具体结构. 引入图的局部边密度来度量每个连通集合中各成员之间联系的紧密程度, 即以该连通集合的导出子图的边密度来作为他们的收益系数, 并由此定义了具有边密度的Myerson值, 证明了具有边密度的Myerson值可以由"边密度分支有效性"和"公平性"来唯一确定.     

A vertex oriented approach to the equal remaining obligations rule for minimum cost spanning tree situations

In this paper, we consider spanning tree situations, where players want to be connected to a source as cheap as possible. These situations involve the construction of a spanning tree with the minimum cost as well as the allocation of the cost of this minimum cost spanning tree among its users in a fair way. Feltkamp, Muto and Tijs 1994 introduced the equal remaining obligations rule to solve the cost allocation problem in these situations. Recently, it has been shown that the equal remaining obligations rule satisfies many appealing properties and can be obtained with different approaches. In this paper, we provide a new approach to obtain the equal remaining obligations rule. Specifically, we show that the equal remaining obligations rule can be obtained as the average of the cost allocations provided by a vertex oriented construct-and-charge procedure for each order of players.     

Games on fuzzy communication structures with Choquet players

Myerson (1977) used graph-theoretic ideas to analyze cooperation structures in games. In his model, he considered the players in a cooperative game as vertices of a graph, which undirected edges defined their communication possibilities. He modified the initial games taking into account the graph and he established a fair allocation rule based on applying the Shapley value to the modified game. Now, we consider a fuzzy graph to introduce leveled communications. In this paper players play in a particular cooperative way: they are always interested first in the biggest feasible coalition and second in the greatest level (Choquet players). We propose a modified game for this situation and a rule of the Myerson kind.