Two hardness results for core stability in hedonic coalition formation games

We establish NP-completeness of two problems on core stable coalitions in hedonic games. In the first problem every player has only two acceptable coalitions in his preference list, and in the second problem the preference structures arise from the distances in an underlying metric space.     

On 1-convexity and nucleolus of co-insurance games

The insurance situation in which an enormous risk is insured by a number of insurance companies is modeled through a cooperative TU game, the so-called co-insurance game, first introduced in Fragnelli and Marina (2004). In this paper we present certain conditions on the parameters of the model that guarantee the 1-convexity property of co-insurance games which in turn ensures the nonemptiness of the core and the linearity of the nucleolus as a function of the variable premium. Further we reveal conditions when a co-insurance game is representable in the form of a veto-removed game and present an efficient final algorithm for computing the nucleolus of a veto-removed game.     

Rooted-tree solutions for tree games

In this paper, we study cooperative games with limited cooperation possibilities, represented by a tree on the set of agents. Agents in the game can cooperate if they are connected in the tree. We introduce natural extensions of the average (rooted)-tree solution (see [Herings, P., van der Laan, G., Talman, D., 2008. The average tree solution for cycle free games. Games and Economic Behavior 62, 77–92]): the marginalist tree solutions and the random tree solutions. We provide an axiomatic characterization of each of these sets of solutions. By the way, we obtain a new characterization of the average tree solution.     

On the complexity of testing membership in the core of min-cost spanning tree games

LetN = {1,...,n} be a finite set of players andK _N the complete graph on the node setN∪{0}. Assume that the edges ofK _N have nonnegative weights and associate with each coalitionS∪N of players as costc(S) the weight of a minimal spanning tree on the node setS∪{0}. Using transformation from EXACT COVER BY 3-SETS, we exhibit the following problem to beNP-complete. Given the vectorxε?^itN withx(N) =c(N). decide whether there exists a coalitionS such thatx(S) >c(S).     

The gamma-core and coalition formation

This paper reinterprets the γ-core (Chander and Tulkens in Int Tax Pub Financ 2:279–293, 1995; in Int J Game Theory 26:379–401, 1997) and justifies it as well as its prediction that the efficient coalition structure is stable in terms of the coalition formation theory. The problem of coalition formation is formulated as an infinitely repeated game in which the players must choose whether to cooperate or not. It is shown that a certain equilibrium of this game corresponds to the γ-core assumption that when a coalition forms the remaining players form singletons, and that the grand coalition is an equilibrium coalition structure. An earlier version of this paper was presented at the conference on Game Theory and Its Applications held in Mumbai in 2003 and was subsequently circulated as CORE Discussion Paper 2003/46.     

Stability in coalition formation games

In the context of coalition formation games a player evaluates a partition on the basis of the set she belongs to. For this evaluation to be possible, players are supposed to have preferences over sets to which they could belong. In this paper, we suggest two extensions of preferences over individuals to preferences over sets. For the first one, derived from the most preferred member of a set, it is shown that a strict core partition always exists if the original preferences are strict and a simple algorithm for the computation of one strict core partition is derived. This algorithm turns out to be strategy proof. The second extension, based on the least preferred member of a set, produces solutions very similar to those for the stable roommates problem. Received August 1998/Final version June 20, 2000     

ON ASPIRATION SOLUTIONS IN PREDICTING COALITION FORMATION IN COOPERATIVE GAMES

This paper consists of two parts. The first part introduces the strict aspiration as a new aspiration solution concept, which is proved to be existent for any cooperative game. The second part deals with the unsolved problem put forward by Bennett [1] by showing that there is at least one payoff which is balanced, partnered and equal gains aspiration. The proof is algebraic and constructive, thus providing an algorithm for finding such aspirations.     

Highway games on weakly cyclic graphs

A highway problem is determined by a connected graph which provides all potential entry and exit vertices and all possible edges that can be constructed between vertices, a cost function on the edges of the graph and a set of players, each in need of constructing a connection between a specific entry and exit vertex. Mosquera (2007) introduce highway problems and the corresponding cooperative cost games called highway games to address the problem of fair allocation of the construction costs in case the underlying graph is a tree. In this paper, we study the concavity and the balancedness of highway games on weakly cyclic graphs. A graph G is called highway-game concave if for each highway problem in which G is the underlying graph the corresponding highway game is concave. We show that a graph is highway-game concave if and only if it is weakly triangular. Moreover, we prove that highway games on weakly cyclic graphs are balanced.     

Noncooperative formation of coalitions in hedonic games

We study a bargaining procedure of coalition formation in the class of hedonic games, where players’ preferences depend solely on the coalition they belong to. We provide an example of nonexistence of a pure strategy stationary perfect equilibrium, and a necessary and sufficient condition for existence. We show that when the game is totally stable (the game and all its restrictions have a nonempty core), there always exists a no-delay equilibrium generating core outcomes. Other equilibria exhibiting delay or resulting in unstable outcomes can also exist. If the core of the hedonic game and its restrictions always consist of a single point, we show that the bargaining game admits a unique stationary perfect equilibrium, resulting in the immediate formation of the core coalition structure.     

Weighted and roughly weighted simple games

In this paper we give necessary and sufficient conditions for a simple game to have rough weights. We define two functions f(n) and g(n) that measure the deviation of a simple game from a weighted majority game and roughly weighted majority game, respectively. We formulate known results in terms of lower and upper bounds for these functions and improve those bounds. We also investigate rough weightedness of simple games with a small number of players.     

Hedonic coalition formation games with variable populations: core characterizations and (im)possibilities

We consider hedonic coalition formation games with variable sets of agents and extend the properties competition sensitivity and resource sensitivity (introduced by Klaus, Games Econ Behav 72:172–186, 2011, for roommate markets) to hedonic coalition formation games. Then, we show that on the domain of solvable hedonic coalition formation games, the Core is characterized by coalitional unanimity and Maskin monotonicity (see also Takamiya, Maskin monotonic coalition formation rules respecting group rights. Niigata University, Mimeo, 2010, Theorem 1). Next, we characterize the Core for solvable hedonic coalition formation games by unanimity, Maskin monotonicity, and either competition sensitivity or resource sensitivity (Corollary 2). Finally, and in contrast to roommate markets, we show that on the domain of solvable hedonic coalition formation games, there exists a solution not equal to the Core that satisfies coalitional unanimity, consistency, competition sensitivity, and resource sensitivity (Example 2).     

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 value for mixed action-set games

We extend the Aumann-Shapley value to mixed action-set games, i.e., multilevel TU games where there are simultaneously two types of players: discrete players that possess a finite number of activity levels in which they can join a coalition, and continuous players that possess a continuum of levels. Received February 1999/Final version October 2000     

On non-transferable utility games with coalition structure

We introduce a solution function for Non-transferable Utility (NTU) games when prior coalition structure is given. This solution function generalizes both the Harsanyi solution function forNTU games and the Owen solution forTU games with coalition structure.I would like to thank Sergiu Hart, Bezalel Peleg and Shmuel Zamir for some conversations and constructive remarks on an earlier version of this paper. Part of this research was supported by the Sonderforschungsbereich 303 in the university of Bonn.     

Labor unions and Nash bargaining using coalition formation games

In this paper we examine the properties of stable coalitions under sequential and simultaneous bargaining by competing labor unions. We do this using the Nash bargaining solution and various notions of stability, namely, Nash, coalitional, contractual and core stability.     

Hedonic coalition formation games: A new stability notion

This paper studies hedonic coalition formation games where each player’s preferences rely only upon the members of her coalition. A new stability notion under free exit-free entry membership rights, referred to as strong Nash stability, is introduced which is stronger than both core and Nash stabilities studied earlier in the literature. Strong Nash stability has an analogue in non-cooperative games and it is the strongest stability notion appropriate to the context of hedonic coalition formation games. The weak top-choice property is introduced and shown to be sufficient for the existence of a strongly Nash stable partition. It is also shown that descending separable preferences guarantee the existence of a strongly Nash stable partition. Strong Nash stability under different membership rights is also studied.     

Two-step coalition values for multichoice games

We introduce and compare several coalition values for multichoice games. Albizuri defined coalition structures and an extension of the Owen coalition value for multichoice games using the average marginal contribution of a player over a set of orderings of the player’s representatives. Following an approach used for cooperative games, we introduce a set of nested or two-step coalition values on multichoice games which measure the value of each coalition and then divide this among the players in the coalition using either a Shapley or Banzhaf value at each step. We show that when a Shapley value is used in both steps, the resulting coalition value coincides with that of Albizuri. We axiomatize the three new coalition values and show that each set of axioms, including that of Albizuri, is independent. Further we show how the multilinear extension can be used to compute the coalition values. We conclude with a brief discussion about the applicability of the different values.     

A theory of liberal churches

There is a counterintuitive gap in the club theory of religion. While it elegantly accounts for the success of strict sectarian religious groups in recruiting members and maintaining commitment, it is less satisfactory when attempting to account for groups requiring neither extreme nor zero sacrifice. Moderate groups are always a suboptimal choice for rational, utility maximizing agents within the original representative agent model. The corner solutions of zero and absolute sacrifice, however, are rarely observed empirically compared to the moderate intermediate. In this paper, we extend the original model to operate within an agent-based computational context, with a distribution of heterogeneous agents occupying coordinates in a two dimensional lattice, making repeated decisions over time. Our model offers the possibility of successful moderate groups, including outcomes wherein the population is dominated by moderate groups. The viability of moderate groups is dependent on extending the model to accommodate agent heterogeneity, not just within the population of agents drawn from, but heterogeneity within groups. Moderate sacrifice rates mitigate member free riding and serve as a weak screening device that permits a range of agent types into the group. Within-group heterogeneity allows agents to benefit from the differing comparative advantages of their fellow members.     

On computational complexity of membership test in flow games and linear production games

Let Γ≡(N,v) be a cooperative game with the player set N and characteristic function v: 2^N→R. An imputation of the game is in the core if no subset of players could gain advantage by splitting from the grand coalition of all players. It is well known that, for the flow game (and equivalently, for the linear production game), the core is always non-empty and a solution in the core can be found in polynomial time. In this paper, we show that, given an imputation x, it is NP-complete to decide x is not a member of the core, for the flow game. And because of the specific reduction we constructed, the result also holds for the linear production game. Received: October 2000/Final version: March 2002     

On the core of routing games

A repairman makes a round-trip along a set of customers. He starts in his home location, visits each customer exactly once, and returns home. The cost of his trip has to be shared by the customers. A cooperative cost game, calledrouting game, is associated with this allocation problem, and anO(n ²) algorithm is given which computes a core element of a routing game if the core is non-empty. The non-emptiness of the core depends on the tour which is traversed by the repairman. Several procedures are given to construct tours which guarantee the non-emptiness of the core.