Cooperation in dividing the cake

This paper defines models of cooperation among players partitioning a completely divisible good (such as a cake or a piece of land). The novelty of our approach lies in the players’ ability to form coalitions before the actual division of the good with the aim to maximize the average utility of the coalition. A social welfare function which takes into account coalitions drives the division. In addition, we derive a cooperative game which measures the performance of each coalition. This game is compared with the game in which players start cooperating only after the good has been portioned and has been allocated among the players. We show that a modified version of the game played before the division outperforms the game played after the division.     

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.     

The Myerson value for complete coalition structures

In order to describe partial cooperation structures, this paper introduces complete coalition structures as sets of feasible coalitions. A complete coalition structure has a property that, for any coalition, if each pair of players in the coalition belongs to some feasible coalition contained in the coalition then the coalition itself is also feasible. The union stable structures, which constitute the domain of the Myerson value, are a special class of the complete coalition structures. As an allocation rule on complete coalition structures, this paper proposes an extension of the Myerson value for complete coalition structures and provides an axiomatization.     

Common pool resources with support

We examine the role of support for coalition stability in common pool resource games such as fisheries games. Some players may not want to join a coalition that jointly manages a resource. Still, because they benefit from spillovers, they may want to support the coalition with a transfer payment to set incentives for others to join. We find that the impact of support on equilibria of this game is limited to games with three or five players. Recommendations for Resource Managers

• Coalitions may be able to effectively manage common pool resources such as fisheries but such coalitions are often not stable due to free-rider incentives.
• We explore the impact of a transfer scheme that can improve this coalition stability which would lead to larger and more effective coalitions.
• Our results show that this new transfer scheme works only for cases where the number of players is small.

     

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.     

Coalition formation in the presence of continuing conflict

This paper studies endogenous coalition formation in a rivalry environment where continuing conflict exists. A group of heterogeneous players compete for a prize with the probability of winning for a player depending on his strength as well as the distribution of strengths among his rivals. Players can pool their strengths together to increase their probabilities of winning as a group through coalition formation. The players in the winning coalition will compete further until one individual winner is left. We show that in any equilibrium there are only two coalitions in the initial stage of the contest. In the case of three players, the equilibrium often has a coalition of the two weaker players against the strongest. The equilibrium coalition structure with four players mainly takes one of the two forms: a coalition of the three weaker players against the strongest or a coalition of the weakest and strongest players against a coalition of the remaining two. Our findings imply that the rivalry with the possibility of coalition formation in our model exhibits a pattern of two-sidedness and a balance of power. We further study the impact of binding agreements by coalition members on equilibrium coalition structures. Our analysis sheds some light on problems of temporary cooperation among individuals who are rivals by nature.     

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

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

A coalition formation value for games in partition function form

The coalition formation problem in an economy with externalities can be adequately modeled by using games in partition function form (PFF games), proposed by Thrall and Lucas. If we suppose that forming the grand coalition generates the largest total surplus, a central question is how to allocate the worth of the grand coalition to each player, i.e., how to find an adequate solution concept, taking into account the whole process of coalition formation. We propose in this paper the original concepts of scenario-value, process-value and coalition formation value, which represent the average contribution of players in a scenario (a particular sequence of coalitions within a given coalition formation process), in a process (a sequence of partitions of the society), and in the whole (all processes being taken into account), respectively. We give also two axiomatizations of our coalition formation value.     

A relation-algebraic approach to simple games

Simple games are a powerful tool to analyze decision-making and coalition formation in social and political life. In this paper, we present relation-algebraic models of simple games and develop relational specifications for solving some basic problems of them. In particular, we test certain fundamental properties of simple games and compute specific players and coalitions. We also apply relation algebra to determine power indices. This leads to relation-algebraic specifications, which can be evaluated with the help of the BDD-based tool Rel View after a simple translation into the tool’s programming language. In order to demonstrate the visualization facilities of Rel View we consider an example of the Catalonian Parliament after the 2003 election.     

The Harsanyi paradox and the “right to talk” in bargaining among coalitions

We describe a coalitional value from a non-cooperative point of view, assuming coalitions are formed for the purpose of bargaining. The idea is that all the players have the same chances to make proposals. This means that players maintain their own “right to talk” when joining a coalition. The resulting value coincides with the weighted Shapley value in the game between coalitions, with weights given by the size of the coalitions. Moreover, the Harsanyi paradox (forming a coalition may be disadvantageous) disappears for convex games.     

Cooperative games of choosing partners and forming coalitions in the marketplace

Two games of interacting between a coalition of players in a marketplace and the residual players acting there are discussed, along with two approaches to fair imputation of gains of coalitions in cooperative games that are based on the concepts of the Shapley vector and core of a cooperative game. In the first game, which is an antagonistic one, the residual players try to minimize the coalition's gain, whereas in the second game, which is a noncooperative one, they try to maximize their own gain as a coalition. A meaningful interpretation of possible relations between gains and Nash equilibrium strategies in both games considered as those played between a coalition of firms and its surrounding in a particular marketplace in the framework of two classes of n-person games is presented. A particular class of games of choosing partners and forming coalitions in which models of firms operating in the marketplace are those with linear constraints and utility functions being sums of linear and bilinear functions of two corresponding vector arguments is analyzed, and a set of maximin problems on polyhedral sets of connected strategies which the problem of choosing a coalition for a particular firm is reducible to are formulated based on the firm models of the considered kind.     

Axiomatizations of the Shapley value for games on augmenting systems

This paper deals with cooperative games in which only certain coalitions are allowed to form. There have been previous models developed to confront the problem of unallowable coalitions. Games restricted by a communication graph were introduced by Myerson and Owen. In their model, the feasible coalitions are those that induce connected subgraphs. Another type of model is introduced in Gilles, Owen and van den Brink. In their model, the possibilities of coalition formation are determined by the positions of the players in a so-called permission structure. Faigle proposed another model for cooperative games defined on lattice structures. We introduce a combinatorial structure called augmenting system which is a generalization of the antimatroid structure and the system of connected subgraphs of a graph. In this framework, the Shapley value of games on augmenting systems is introduced and two axiomatizations of this value are showed.     

Subgroup additivity in the queueing problem

Subgroup additivity requires that a rule assigns the same expected ‘relative’ utility to each agent whether an agent’s expected relative utility is calculated from the problem involving all agents or from its sub-problems with a smaller number of agents. In this paper, we investigate its implications for the queueing problem. As a result, we present characterizations of five important rules: the minimal transfer rule, the maximal transfer rule, the pivotal rule, the reward based pivotal rule, and the symmetrically balanced VCG rule. In addition to some basic axioms and subgroup additivity, the characterization results can be obtained by additionally imposing either a strategic axiom or an equity axiom.     

The collective value: a new solution for games with coalition structures

In this study, we provide a new solution for cooperative games with coalition structures. The collective value of a player is defined as the sum of the equal division of the pure surplus obtained by his coalition from the coalitional bargaining and of his Shapley value for the internal coalition. The weighted Shapley value applied to a game played by coalitions with coalition-size weights is assigned to each coalition, reflecting the size asymmetries among coalitions. We show that the collective value matches exogenous interpretations of coalition structures and provide an axiomatic foundation of this value. A noncooperative mechanism that implements the collective value is also presented.     

Coalitions and payoffs in three‐person sequential games: Initial tests of two formal models

In this paper we develop two formal models predicting coalitions and payoffs among rank striving players in a sequential three‐person game. We test the models’ predictions with data from a laboratory study of eleven male triads. Each triad plays a sequence of games; in each game a two‐person coalition forms and divides the coalition's point value between the two coalition partners. Participants know that the sequence of games will end without warning at a randomly chosen time; at the sequence's end each player's monetary payoff is a linear function of the rank of his accumulated point score, relative to those of the other members of his triad. The complexity of this situation prevents players and analysts from representing it as a single game; thus they are unable to use n‐person game theory to identify optimal strategies. Consequently, we assume that players, unable to develop strategies that are demonstrably optimal in the long run, adopt certain bargaining heuristics and surrogate short run objectives.

The two models follow the same basic outline; they differ, however, in the planning horizon they assume players to use. Proceeding from a priori assumptions concerning each player's decision calculus and the bargaining process, the two models state the probability that each coalition forms and predict the point divisions in the winning coalition. The laboratory data provide consistently strong support for the predictions of both models.     

Self-enforcing coalitions with power accumulation

Agents endowed with power compete for a divisible resource by forming coalitions with other agents. The coalition with the greatest power wins the resource and divides it among its members. The agents’ power increases according to their share of the resource.We study two models of coalition formation where winning agents accumulate power and losing agents may participate in further coalition formation processes. An axiomatic approach is provided by focusing on variations of two main axioms: self-enforcement, which requires that no further deviation happens after a coalition has formed, and rationality, which requires that agents pick the coalition that gives them their highest payoff. For these alternative models, we determine the existence of stable coalitions that are self-enforcing and rational for two traditional sharing rules. The models presented in this paper illustrate how power accumulation, the sharing rule, and whether losing agents participate in future coalition formation processes, shape the way coalitions will be stable throughout time.     

Strong equilibria in claim games corresponding to convex games

This paper deals with a specific aspect of the problem of coalition formation in a situation described by a TU-game. First, we define a very simple normal form game which models the process of coalition formation. To define the payoff functions of the players we use an allocation rule for TU-games. The main objective of this paper is ascertain what conditions of the allocation rule lead to the grand coalition being a strong equilibrium of the normal form game, when the original TU-game is convex. Received January 1996/Revised version December 1996/Final version May 1997     

Characterization of the core in games with restricted cooperation

Games with restricted cooperation describe situations in which the players are not completely free in forming coalitions. The restrictions in coalition formation can be attributed to economic, hierarchical, political or ethical reasons. In order to manage these situations, the model includes a collection of coalitions which determines the feasible agreements among the agents. The purpose of this paper is to extend the characterization of the core of a cooperative game, made by Peleg [International Journal of Game Theory 15 (1986) 187–200; Handbook of Game Theory with Economic Applications, vol. I. Elsevier Science Publishers B.V., pp. 397–412] to the context of games with restricted cooperation. In order to make the approach as general as possible, we will consider classes of games with restricted cooperation in which the collection of feasible coalitions has a determined structure, and we will impose conditions on that structure to generalize the Peleg’s axiomatization.     

A sufficiency condition for coalitive pareto-optimal solutions

In ak-player, nonzero-sum differential game, there exists the possibility that a group of players will form a coalition and work together. If allk players form the coalition, the criterion usually chosen is Pareto optimality whereas, if the coalition consists of only one player, a minmax or Nash equilibrium solution is sought.In this paper, games with coalitions of more than one but less thank players are considered. Coalitive Pareto optimality is chosen as the criterion. Sufficient conditions are presented for coalitive Pareto-optimal solutions, and the results are illustrated with an example.     

An application of cooperative game among container terminals of one port

In this paper a two-stage game that involves three container terminals located in Karachi Port in Pakistan is discussed. In the first stage, the three terminals have to decide on whether to act as a singleton or to enter into a coalition with one or both of the other terminals. The decision at this stage should presumably be based on the predicted outcome for the second stage. The second stage is here modelled as a Bertrand game with one outside competitor, the coalition and the terminal in Karachi Port (if any) that has not joined the coalition. Furthermore, three partial and one grand coalition among the three terminals at Karachi Port are investigated. The concepts of “characteristic function” and “core” are used to analyse the stability of these coalitions and this revealed that one combination does not satisfy the superadditivity property of the characteristic function and can therefore be ruled out. The resulting payoffs (profits) of these coalitions are analysed on the basis of “core”. The best payoff for all players is in the case of a “grand coalition”. However, the real winner is the outsider (the terminal at the second port) which earns a better payoff without joining the coalition, and hence will play the role of the “orthogonal free-rider”.