Cooperative games in permutational structure

Summary. By a cooperative game in coalitional structure or shortly coalitional game we mean the standard cooperative non-transferable utility game described by a set of payoffs for each coalition being a nonempty subset of the grand coalition of all players. It is well-known that balancedness is a sufficient condition for the nonemptiness of the core of such a cooperative non-transferable utility game. In this paper we consider non-transferable utility games in which for any coalition the set of payoffs depends on a permutation or ordering upon any partition of the coalition into subcoalitions. We call such a game a cooperative game in permutational structure or shortly permutational game. Doing so we extend the scope of the standard cooperative game theory in dealing with economic or political problems. Next we define the concept of core for such games. By introducing balancedness for ordered partitions of coalitions, we prove the nonemptiness of the core of a balanced non-transferable utility permutational game. Moreover we show that the core of a permutational game coincides with the core of an induced game in coalitional structure, but that balancedness of the permutational game need not imply balancedness of the corresponding coalitional game. This leads to a weakening of the conditions for the existence of a nonempty core of a game in coalitional structure, induced by a game in permutational structure. Furthermore, we refine the concept of core for the class of permutational games. We call this refinement the balanced-core of the game and show that the balanced-core of a balanced permutational game is a nonempty subset of the core. The proof of the nonemptiness of the core of a permutational game is based on a new intersection theorem on the unit simplex, which generalizes the well-known intersection theorem of Shapley. Received: October 31, 1995; revised version: February 5, 1997     

On the Least Core and the Mas-Colell Bargaining Set

We show that the least core of a TU coalitional game with a finite set of players is contained in the Mas-Colell bargaining set. This result is extended to games with a measurable space of players in which the worth of the grand coalition is at least that of any other coalition in the game. As a consequence, we obtain an existence theorem for the Mas-Colell bargaining set in TU games with a measurable space of players. Journal of Economic Literature Classification Number: C71.     

Information transmission in coalitional voting games

A core allocation of a complete information economy can be characterized as one that would not be unanimously rejected in favor of another feasible alternative by any coalition. We use this test of coalitional voting in an incomplete information environment to formalize a notion of resilience. Since information transmission is implicit in the Bayesian equilibria of such voting games, this approach makes it possible to derive core concepts in which the transmission of information among members of a coalition is endogenous. Our results lend support to the credible core of Dutta and Vohra [Incomplete information, credibility and the core, Math. Soc. Sci. 50 (2005) 148-165] and the core proposed by Myerson [Virtual utility and the core for games with incomplete information, Mimeo, University of Chicago, 2005] as two that can be justified in terms of coalitional voting.     

Coalitions, agreements and efficiency

If agents negotiate openly and form coalitions, can they reach efficient agreements? We address this issue within a class of coalition formation games with externalities where agents’ preferences depend solely on the coalition structure they are associated with. We derive Ray and Vohra's [Equilibrium binding agreements, J. Econ. Theory 73 (1997) 30-78] notion of equilibrium binding agreements using von Neumann and Morgenstern [Theory of Games and Economic Behavior, Princeton University Press, Princeton, 1944] abstract stable set and then extend it to allow for arbitrary coalitional deviations (as opposed to nested deviations assumed originally). We show that, while the extended notion facilitates the attainment of efficient agreements, inefficient agreements can nevertheless arise, even if utility transfers are possible.     

Theories of coalitional rationality

This paper generalizes the concept of best response to coalitions of players and offers epistemic definitions of coalitional rationalizability in normal form games. The (best) response of a coalition is defined to be an operator from sets of conjectures to sets of strategies. A strategy is epistemic coalitionally rationalizable if it is consistent with rationality and common certainty that every coalition is rational. A characterization of this solution set is provided for operators satisfying four basic properties. Special attention is devoted to an operator that leads to a solution concept that is generically equivalent to the iteratively defined concept of coalitional rationalizability.     

Convex Games and Stable Sets

It is well known that the core of a convex coalitional game with a finite set of players is the unique von Neumann–Morgenstern stable set of the game. We extend the definition of a stable set to coalitional games with an infinite set of players and give an example of a convex simple game with a countable set of players which does not have a stable set. But if a convex game with a countable set of players is continuous at the grand coalition, we prove that its core is the unique von Neumann–Morgenstern stable set. We also show that a game with a countable (possibly finite) set of players which is inner continuous is convex iff the core of each of its subgames is a stable set.Journal of Economic LiteratureClassification Numbers: C70, C71.     

Bargaining under Uncertainty and the Monotone Path Solutions

Uncertainty with respect to the feasible set of utility vectors is introduced in an axiomatic bargaining model. Given a criterion for nonprobabilistic decision-making under uncertainty, a natural efficiency requirement can be imposed on a bargaining solution. Using the maximin ordering, thestrictly monotone pathsolutions (generalizations of theegalitariansolution) to the bargaining problem are characterized as the only continuous solutions that satisfy this efficiency axiom. If the maximin criterion is replaced by the maximax ranking or a strict convex combination of the maximin and the maximax criterion, imposing our efficiency axiom and continuity leads to thedictatorialsolutions.Journal of Economic LiteratureClassification Number: C78.     

Pillage and property

This paper introduces a class of coalitional games, called pillage games, as a model of Hobbesian anarchy. Any coalition can pillage, costlessly and with certainty, any less powerful coalition. Power is endogenous, so a pillage game does not have a characteristic function, but pillage provides a domination concept that defines a stable set, which represents an endogenous balance of power. Every stable set contains only finitely many allocations, and can be represented as a farsighted core. Additional results are obtained for particular games, including the game in which the power of each coalition is determined by its total wealth.     

The Network of Weighted Majority Rules and Weighted Majority Games

The network organizes in space the weighted majority rules (WMR) and weighted majority games (WMG). The WMRs are the potentially optimal decision rules in uncertain dichotomous choice situations. The WMGs are the well-known subgroup of coalitional games. The nodes are the WMRs or the WMGs, and the directed edges are the decision profiles of the decision makers or the coalitions among the players, respectively. For any group of decision makers, the network yields the ranking of all the WMRs by their efficiency; for any group of players, it yields the differences among the WMGs in terms of winning and losing coalitions.Journal of Economic LiteratureClassification Numbers: C45, C70, C71, D81.     

Coalition formation as a dynamic process

We study coalition formation as an ongoing, dynamic process, with payoffs generated as coalitions form, disintegrate, or regroup. A process of coalition formation (PCF) is an equilibrium if a coalitional move to some other state can be “justified” by the expectation of higher future value, compared to inaction. This future value, in turn, is endogenous: it depends on coalitional movements at each node. We study existence of equilibrium PCFs. We connect deterministic equilibrium PCFs with unique absorbing state to the core, and equilibrium PCFs with multiple absorbing states to the largest consistent set. In addition, we study cyclical as well as stochastic equilibrium PCFs.     

Core tâtonnement

Two discrete time tâtonnement processes—one featuring successive tâtonnement, the other featuring simultaneous tâtonnement—for the core of coalitional games with transferable utility are introduced. For totally balanced games, the successive core tâtonnement process corresponds to the standard simultaneous price tâtonnement process of competitive equilibrium theory via the Shapley-Shubik (market game-direct market) correspondence. The simultaneous core tâtonnement process is based entirely on the intuition behind the definition of the core for games with transferable utility, and it does not correspond to any evident competitive equilibrium tâtonnement process. Both processes are proven to be globally stable. The two processes offer easily implementable algorithms for approximately computing core points.     

Axiomatizations of two types of Shapley values for games on union closed systems

A situation in which a finite set of players can obtain certain payoffs by cooperation can be described by a cooperative game with transferable utility, or simply a TU-game. A (single-valued) solution for TU-games assigns a payoff distribution to every TU-game. A well-known solution is the Shapley value. In the literature various models of games with restricted cooperation can be found. So, instead of allowing all subsets of the player set N to form, it is assumed that the set of feasible coalitions is a subset of the power set of N. In this paper, we consider such sets of feasible coalitions that are closed under union, i.e. for any two feasible coalitions also their union is feasible. We consider and axiomatize two solutions or rules for these games that generalize the Shapley value: one is obtained as the conjunctive permission value using a corresponding superior graph, the other is defined as the Shapley value of a modified game similar as the Myerson value for games with limited communication.     

Competitive outcomes and the inner core of NTU market games

We consider the inner core as a solution concept for cooperative games with non-transferable utility (NTU) and its relationship to payoffs of competitive equilibria of markets that are induced by NTU games. An NTU game is an NTU market game if there exists a market such that the set of utility allocations a coalition can achieve in the market coincides with the set of utility allocations the coalition can achieve in the game. In this paper, we introduce a new construction of a market based on a closed subset of the inner core which satisfies a strict positive separability. We show that the constructed market represents the NTU game and, further, has the given closed set as the set of payoff vectors of competitive equilibria. It turns out that this market is not uniquely determined, and thus, we obtain a class of markets. Our results generalize those relating to competitive outcomes of NTU market games in the literature.     

Subjective evaluations of n-person games

Using an axiomatization of subjective expected utility due to Fishburn, we characterize a class of utility functions over a set of n-person games in characteristic-function form. A probabilistic value is defined as the expectation of some player's marginal contribution with respect to some probability measure on the set of coalitions of other players. We decribe conditions under which a utility function on the set of n-person games is a probabilistic value; we prove as well an analogous result for simple games. We present additional axioms that characterize the semivalues and, in turn, the Shapley and Banzhaf values.     

Cores of combined games

This paper studies the core of combined games, obtained by summing different coalitional games when bargaining over multiple independent issues. It is shown that the set of balanced transferable utility games can be partitioned into equivalence classes of component games to determine whether the core of the combined game coincides with the sum of the cores of its components.     

Core-stable rings in auctions with independent private values

We propose a semi-cooperative game theoretic approach to check whether a given coalition is stable in a Bayesian game with independent private values. The ex ante expected utilities of coalitions, at an incentive compatible (noncooperative) coalitional equilibrium, describe a (cooperative) partition form game. A coalition is core-stable if the core of a suitable characteristic function, derived from the partition form game, is not empty. As an application, we study collusion in auctions in which the bidders? final utility possibly depends on the winner?s identity. We show that such direct externalities offer a possible explanation for cartels? structures (not) observed in practice.     

ANTI‐DUAL OF ECONOMIC COALITIONAL TU GAMES*

Some well‐known coalitional TU (transferable utility) games applied to specific economic problems are shown to be connected through the relation defined as the anti‐dual. Solutions such as the core, the Shapley value and the nucleolus of anti‐dual games are obtained straightforwardly from original games.     

A bargaining approach to the Owen value and the Nash solution with coalition structure

The mechanism by Hart and Mas-Colell (1996) for non-transferable utility (NTU) games is generalized so that a coalition structure among players is taken into account. The new mechanism yields the Owen value for transferable utility (TU) games with coalition structure as well as the consistent value (Maschler and Owen 1989, 1992) for NTU games with trivial coalition structure. Furthermore, we obtain a solution for pure bargaining problems with coalition structure which generalizes the Nash (1950) bargaining solution.     

Two remarks on the inner core

For the case of smooth concave exchange economies, we provide a characterization of the inner core as the set of feasible allocations such that no coalition can improve on it, even if coalitions are allowed to use some random plans. For the case of compactly generated games, we discuss Myerson's definition of the inner core, and we characterize it using lexicographic utility weight systems.     

A strategy-proofness characterization of majority rule

Summary. A feasible alternative x is a strong Condorcet winner if for every other feasible alternative y there is some majority coalition that prefers x to y. Let (resp., denote the set of all profiles of linear (resp., merely asymmetric) individual preference relations for which a strong Condorcet winner exists. Majority rule is the only non-dictatorial and strategy-proof social choice rule with domain , and majority rule is the only strategy-proof rule with domain . Received: August 29, 2000; revised version: November 13, 2002 RID="*" ID="*"We are grateful to Wulf Gaertner and our two referees for insightful comments on a previous draft. Correspondence to: D. E. Campbell