Bidding and sequential coalition formation with externalities

We study coalition formation games with externalities where each agent’s payoff depends on the entire partition. As in Bloch (Games Econ Behav 14:90–123, 1996) and Ray and Vohra (Games Econ Behav 26:268–336, 1999), we assume that coalitions form sequentially and agreements are irreversible. Instead of a fixed order protocol, we use a “bidding mechanism” (see Pérez-Castrillo and Wettstein in Am Econ Rev 92(5):1577–1587, 2002) to determine proposals and transfers among the agents. We show that such a mechanism facilitates the attainment of efficiency; in particular, our game admits a Markov perfect equilibrium with the property of full dynamic efficiency. In addition, the aggregate equilibrium payoffs of our game exhibit monotonicity in time. Nevertheless, inefficient equilibria can also emerge.     

Trading water along a river

A set of agents is located along a river. Each agent consumes certain amount of water he receives from his part of the river basin and may sell certain amount to his downstream agent if it is mutually beneficial. Water trading is restricted to two neighboring agents and an agent can only pass water to his downstream agent. We ask if this restricted trade to neighboring agents can implement an efficient allocation of water. We show that the efficient allocation of water can be achieved through the process of downstream bilateral trading. Specifically, we show that this one way “downstream” trading process implements the unique efficient allocation as well as a welfare distribution. We also show that the welfare distribution is in the core of the associated game of the problem. Moreover, we show that the coalition of agents upstream any agent obtains more welfare with the bilateral trading than with the downstream incremental distribution proposed by Ambec and Sprumont (2002) and less than with the upstream incremental distribution proposed by [Ambec and Ehlers, 2008a] and [Ambec and Ehlers, 2008b].     

Sequential Formation of Coalitions Through Bilateral Agreements in a Cournot Setting

We study a sequential protocol of endogenous coalition formation based on a process of bilateral agreements among the players. We apply the game to a Cournot environment with linear demand and constant average costs. We show that the final outcome of any subgame perfect equilibrium of the game is the grand coalition, provided the initial number of firms is high enough and they are sufficiently patient.This research was partially conducted while the first authors were visiting the Department of Economics of the Norwegien School of Economics and Business Administration (Bergen).     

Emergent learning behaviour in a simulated organization faced with tasks requiring team effort

We conceptualize organizational learning as a result of the collective learning behaviour of knowledge agents in an organization. Each agent provides a range of attributes that may be required to perform organizational tasks. We devised a computational model consisting of three processes to simulate an organization's response to performing repeated tasks: (1) Expert Selection Process for selecting the winner knowledge agent or lead agent; (2) Plan Formation Process for deciding what additional attributes are needed, but not possessed by the winner expert agent, and iteratively selecting further agents with the needed attributes until the task can be accomplished by the combined attributes of the ‘coalition of agents’ so formed; and (3) Capital Modification Process for rewarding participating agents according to the success of their combined organizational performance. We observed the simulated results for different combinations of three levels of task difficulty (requiring, respectively, 5, 10 and, 15 different attributes, each at a sufficient level in the coalition or team to complete the task), and three levels of selection, during plan formation, for knowledge agent performance (the extent to which selection favours knowledge agents with much capital or large strength versus knowledge agents without much capital or large strength). The simulated organization exhibited aspects of both single loop and double loop learning, in repeatedly performing the same task, and ‘learning to perform the task’ with the smallest possible team.     

Groupstrategyproofness of the egalitarian mechanism for constrained rationing problems

Motivated by applications in many economic environments, Bochet et al. (2010) generalize the classic rationing model (Sprumont 1991) as follows: there is a moneyless market, in which a non-storable, homogeneous commodity is reallocated between agents with single-peaked preferences. Agents are either suppliers or demanders. Transfers between a supplier and a demander are feasible only if they are linked, and the links form an arbitrary bipartite graph. Information about individual preferences is private, and so is information about feasible links: an agent may unilaterally close one of her links if it is in her interest to do so. For this problem they propose the egalitarian transfer solution, which equalizes the net transfers of rationed agents as much as permitted by the bilateral constraints. Furthermore, they show that the egalitarian mechanism elicits a truthful report of both preferences and links. In the variant where demanders are not strategic but demands need to be exactly met Bochet et al. (2013), they propose a similar mechanism for which truthfully reporting the peaks is a dominant strategy, but truthful reporting of links is not.The key contribution of the paper is a comprehensive study of the egalitarian mechanism with respect to manipulation by a coalition of agents. Our main result is that the egalitarian mechanism is group strategyproof : no coalition of agents can (weakly) benefit from jointly misreporting their peaks. Furthermore, we show that the egalitarian mechanism cannot be manipulated – by misreporting links or by misreporting peaks – by any coalition of suppliers (or any coalition of demanders) in the model where both the suppliers and demanders are agents. Our proofs shed light on the structure of the two models and simplify some of the earlier proofs of strategyproofness. An implication of our results is that the well known algorithm of Megiddo (1977) to compute a lexicographically optimal flow in a network is group strategyproof with respect to the source capacities and sink capacities.     

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.     

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

Sticks and carrots for the design of international climate agreements with renegotiations

This paper examines renegotiations of international climate agreements for carbon abatement. We explore coalition stability under ‘optimal transfers’ that have been suggested to stabilise international environmental agreements (e.g. McGinty in Oxford Economic Papers 59, 45–62, 2007). Such transfer schemes need to be refined when agreements are renegotiated. We determine the requirements that transfers between signatories of an international climate agreement must satisfy in order to stabilise the sequence of agreements that performs best in terms of provision of the public good ‘carbon abatement’. If these requirements are met, no country wants to change its membership status at any stage. In order to demonstrate the applicability of our result we use the STACO model, a 12-regions global model, to assess the impact of well-designed transfer rules on the stability of an international climate agreement. Although there are strong free-rider incentives, we find a stable grand coalition in the first commitment period in a game with one round of renegotiations if renegotations take place sufficiently early.     

Computational complexity in additive hedonic games

We investigate the computational complexity of several decision problems in hedonic coalition formation games and demonstrate that attaining stability in such games remains NP-hard even when they are additive. Precisely, we prove that when either core stability or strict core stability is under consideration, the existence problem of a stable coalition structure is NP-hard in the strong sense. Furthermore, the corresponding decision problems with respect to the existence of a Nash stable coalition structure and of an individually stable coalition structure turn out to be NP-complete in the strong sense.     

Individual and group stability in neutral restrictions of hedonic games

We consider a class of coalition formation games called hedonic games, i.e., games in which the utility of a player is completely determined by the coalition that the player belongs to. We first define the class of subset-additive hedonic games and show that they have the same representation power as the class of hedonic games. We then define a restriction of subset-additive hedonic games that we call subset-neutral hedonic games and generalize a result by Bogomolnaia and Jackson (2002) by showing the existence of a Nash stable partition and an individually stable partition in such games. We also consider neutrally anonymous hedonic games and show that they form a subclass of the subset-additive hedonic games. Finally, we show the existence of a core stable partition that is also individually stable in neutrally anonymous hedonic games by exhibiting an algorithm to compute such a partition.     

Negotiation,preferences over agreements,and the core

We analyze conditions under which negotiated agreements are efficient from the point of view of every possible coalition of negotiators. The negotiators have lexicographic preferences over agreements they reach. Their utility is the first criterion. The coalition reaching an agreement is the second criterion. In the analyzed non-cooperative discrete time bargaining game Γ the players bargain about the choice from the sets of utility vectors feasible for coalitions in a given NTU game (N, V). If Γ has a Markov perfect equilibrium, then the set of equilibrium utility vectors in Markov perfect equilibria in it equals the core of (N, V). I thank an anonymous referee, an anonymous Associate Editor, and the Editor for their comments that helped me to improve the paper. The research reported in this paper was supported by the Grant VEGA 1/1223/04 of the Ministry of Education of the Slovak Republic.     

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.     

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.     

A model of influence based on aggregation functions

The paper concerns a dynamic model of influence in which agents make a yes–no decision. Each agent has an initial opinion which he may change during different phases of interaction, due to mutual influence among agents. We investigate a model of influence based on aggregation functions. Each agent modifies his opinion independently of the others, by aggregating the current opinion of all agents. Our framework covers numerous existing models of opinion formation, since we allow for arbitrary aggregation functions. We provide a general analysis of convergence in the aggregation model and find all terminal classes and states. We show that possible terminal classes to which the process of influence may converge are terminal states (the consensus states and nontrivial states), cyclic terminal classes, and unions of Boolean lattices (called regular terminal classes). An agent is influential for another agent if the opinion of the first one matters for the latter. A generalization of influential agent to an irreducible coalition whose opinion matters for an agent is called influential coalition. The graph (hypergraph) of influence is a graphical representation of influential agents (coalitions). Based on properties of the hypergraphs of influence we obtain conditions for the existence of the different kinds of terminal classes. An important family of aggregation functions–the family of symmetric decomposable models–is discussed. Finally, based on the results of the paper, we analyze the manager network of Krackhardt.     

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.     

The Computer Simulation of Partnership Formation

This paper is intended to present and apply a formal dependence model to a simulation study of partnership formation. Although the emergence and evolution of coalitions is an issue of major concern in the study of organisations, a number of questions are still laid open. How do coalitions emerge? Which processes and mechanisms are responsible for their evolution? The agents&;#x2018; informal communications, commitments and negotiations are considered as &;#x201C;given&;#x201D;, and none or poor effort is done to ground them upon the agents&;#x2018; self-interests. The philosophy underlying this paper is that the objective relationships of dependence among heterogeneous agents provide a fundamental ground for the emergence of spontaneous coalitions. As long as agents are endowed with different goals and heterogeneous competencies, a structure of social relationships, namely dependence relations, is likely to occur among them. A formal model of dynamic dependence relationships based on the agents&;#x2018; individual properties will be used to derive a further agents&;#x2018; property, namely their negotiation powers. Through computer simulation, this property will be used to predict how likely each agent in a population will form rewarding partnerships.     

A BFGS-IP algorithm for solving strongly convex optimization problems with feasibility enforced by an exact penalty approach

This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of the iterates is progressively enforced thanks to shift variables and an exact penalty approach. Global and q-superlinear convergence is obtained for a fixed penalty parameter; global convergence to the analytic center of the optimal set is ensured when the barrier parameter tends to zero, provided strict complementarity holds. Received: December 21, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Coalitional unanimity versus strategy-proofness in coalition formation problems

This paper examines coalition formation problems from the viewpoint of mechanism design. We consider the case where (i) the list of feasible coalitions (those coalitions which are permitted to form) is given in advance; and (ii) each individual’s preference is a ranking over those feasible coalitions which include this individual. We are interested in requiring the mechanism to guarantee each coalition the “right” of forming that coalition at least when every member of the coalition ranks the coalition at the top. We name this property coalitional unanimity. We examine the compatibility between coalitional unanimity and incentive requirements, and prove that if the mechanism is strategy-proof and respects coalitional unanimity, then for each preference profile, there exists at most one strictly core stable partition, and the mechanism chooses such a partition whenever available. Further, the mechanism is coalition strategy-proof and respects coalitional unanimity if, and only if, the strictly core stable partition uniquely exists for every preference profile.     

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.