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.     

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.     

Equilibrium binding agreements under diverse behavioral assumptions

Summary. This paper extends the work of Ray and Vohra [3]. It ascertains which partitions of players will emerge and what actions will these players choose under each partition, when they can sign binding agreements and their actions have externalities. The emphasis, however, is placed on situations with multiple outcomes and how agents behave in the presence of such multiplicity. In particular, a deviating coalition considers all the likely outcomes that may prevail upon its deviation, and selects (if possible) a subset of them. Three augmentations of Ray and Vohra's [3] solution concept are defined, capturing three distinct behavioral assumptions. Efficiency of and the relation between the three notions are discussed. Received: October 9, 2001; revised version: April 22, 2002 RID="*" ID="*" I wish to thank Licun Xue, Joseph Greenberg and the participants of PET 2000 for very helpful suggestions. I am indebted to an anonymous referee for his/her valuable comments. The paper has been previously circulated under the title Binding Agreements.     

The supercore for normal-form games

This paper analyzes the supercore of a system derived from a normal-form game. For the case of a finite game with pure strategies, we define a sequence of games and show that the supercore coincides with the set of Nash equilibria of the last game in that sequence. This result is illustrated with the characterization of the supercore for the n-person prisoner's dilemma. With regard to the mixed extension of a normal-form game, we show that the set of Nash equilibrium profiles coincides with the supercore for games with a finite number of Nash equilibria.     

Linear efficient and symmetric values for TU-games: Sharing the joint gain of cooperation

Recently, Hermandez-Lamoneda et al. (2008) and independently Chameni and Andjiga (2008) gave an analytic formulation for all valued solutions to the n-person TU-games that satisfy linearity, efficiency and symmetry axioms. Our main purpose in this paper is to recast the proposed formulation to a more potentially interpretational one. We are focused on an interpretation based on the idea of marginal contribution, a concept already familiar in the Shapley value and the Solidarity value. A general null player axiom is introduced, and it turns out that any valued solution satisfying the three properties is characterized by a null player model.     

The computational complexity of random serial dictatorship

In social choice settings with linear preferences, random dictatorship is known to be the only social decision scheme satisfying strategyproofness and ex post efficiency. When also allowing indifferences, random serial dictatorship (RSD) is a well-known generalization of random dictatorship that retains both properties. RSD has been particularly successful in the special domain of random assignment where indifferences are unavoidable. While executing RSD is obviously feasible, we show that computing the resulting probabilities is #P-complete, and thus intractable, both in the context of voting and assignment.     

Coalitional stability under perfect foresight

Summary. We analyze strategic social environments where coalitions can form through binding or nonbinding agreements and actions of a coalition may impose externalities upon the welfare of the rest of the players. We define a solution concept that (1) captures the perfect foresight of the players that has been overlooked in the literature (e.g., Harsanyi [10] and Chwe [6]) and (2) identifies the coalitions that are likely to form and the “stable” outcomes that will not be replaced by any coalition of rational (and hence farsighted) players. The proposed solution concept thereby offers a notion of agreements and coalition formation in complex social environments. Received: February 12, 1996; revised version: March 3, 1997     

A comment on “School choice: An experimental study” [J. Econ. Theory 127 (1) (2006) 202-231]

We show that one of the main results in Chen and Sönmez (2006, 2008) [6] and [7] does no longer hold when the number of recombinations is sufficiently increased to obtain reliable conclusions. No school choice mechanism is significantly superior in terms of efficiency.     

Role of linking mechanisms in multitask agency with hidden information

We investigate the adverse selection problem where a principal delegates multiple tasks to an agent. We characterize the virtually implementable social choice functions by using the linking mechanism proposed by Jackson and Sonnenschein (2007) [20] that restricts the message spaces. The principal does not require any incentive wage schemes and can therefore avoid any information rent and welfare loss. We show the resemblance between the functioning of this message space restriction and that of incentive wage schemes. We also extend the results of the single-agent model to the multi-agent model.     

Null or nullifying players: The difference between the Shapley value and equal division solutions

A famous solution for cooperative transferable utility games is the Shapley value. Most axiomatic characterizations of this value use some axiom related to null players, i.e. players who contribute zero to any coalition. We show that replacing null players with nullifying players characterizes the equal division solution distributing the worth of the ‘grand coalition’ equally among all players. A player is nullifying if every coalition containing this player earns zero worth. Using invariance we provide similar characterizations of the equal surplus division solution assigning to every player its own worth, and distributing the remaining surplus equally among all players.     

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.     

Sorting equilibrium in a multi-jurisdiction model

This paper analyzes a general model of an economy with heterogeneous individuals choosing among two jurisdictions, such as towns or political parties. Each jurisdiction is described by its constitution, where a constitution is defined as a mapping from all possible population partitions into the (possibly multidimensional) policy space. This study is the first to establish sufficient conditions for existence of sorting equilibria in a two-jurisdiction model for a policy space of an arbitrary dimension.     

The premiss-based approach to judgment aggregation

In the framework of judgment aggregation, we assume that some formulas of the agenda are singled out as premisses, and that both Independence (formula-wise aggregation) and Unanimity Preservation hold for them. Whether premiss-based aggregation thus defined is compatible with conclusion-based aggregation, as defined by Unanimity Preservation on the non-premisses, depends on how the premisses are logically connected, both among themselves and with other formulas. We state necessary and sufficient conditions under which the combination of both approaches leads to dictatorship (resp. oligarchy), either just on the premisses or on the whole agenda. Our analysis is inspired by the doctrinal paradox of legal theory and is arguably relevant to this field as well as political science and political economy. When the set of premisses coincides with the whole agenda, a limiting case of our assumptions, we obtain several existing results in judgment aggregation theory.     

Majority voting on restricted domains

In judgment aggregation, unlike preference aggregation, not much is known about domain restrictions that guarantee consistent majority outcomes. We introduce several conditions on individual judgments sufficient for consistent majority judgments. Some are based on global orders of propositions or individuals, others on local orders, still others not on orders at all. Some generalize classic social-choice-theoretic domain conditions, others have no counterpart. Our most general condition generalizes Sen's triplewise value-restriction, itself the most general classic condition. We also prove a new characterization theorem: for a large class of domains, if there exists any aggregation function satisfying some democratic conditions, then majority voting is the unique such function. Taken together, our results support the robustness of majority rule.     

Introduction to judgment aggregation

This introduces the symposium on judgment aggregation. The theory of judgment aggregation asks how several individuals' judgments on some logically connected propositions can be aggregated into consistent collective judgments. The aim of this introduction is to show how ideas from the familiar theory of preference aggregation can be extended to this more general case. We first translate a proof of Arrow's impossibility theorem into the new setting, so as to motivate some of the central concepts and conditions leading to analogous impossibilities, as discussed in the symposium. We then consider each of four possible escape-routes explored in the symposium.     

On the universally beneficial manipulation conjecture

The universally beneficial manipulation conjecture of Campbell and Kelly states that for a social choice rule, if everyone gains as a result of any optimal manipulation, then the rule satisfies universally beneficial manipulation, i.e., everyone gains as a result of any manipulation, optimal or not. We prove the conjecture for three alternatives and any number of individuals. We also construct a counterexample in a general form with more than three alternatives and at least two individuals.     

Justifiable group choice

We study the judgment aggregation problem from the perspective of justifying a particular collective decision by a corresponding aggregation on the criteria. In particular, we characterize the logical relations between the decision and the criteria that enable justification of a majority decision through a proposition-wise aggregation rule with no veto power on the criteria. While the well-studied “doctrinal paradox” provides a negative example in which no such justification exists, we show that genuine possibility results emerge if there is a gap between the necessary and the sufficient conditions for the decision. This happens, for instance, if there is only a partial consensus about the appropriate criteria for the decision, if only a subset of these criteria can be elicited, or if the judgment on criteria is based on probabilistic acceptance thresholds.     

Factoring out the impossibility of logical aggregation

According to a theorem recently proved in the theory of logical aggregation, any nonconstant social judgment function that satisfies independence of irrelevant alternatives (IIA) is dictatorial. We show that the strong and not very plausible IIA condition can be replaced with a minimal independence assumption plus a Pareto-like condition. This new version of the impossibility theorem likens it to Arrow's and arguably enhances its paradoxical value.     

Iterated regret minimization: A new solution concept

For some well-known games, such as the Traveler?s Dilemma or the Centipede Game, traditional game-theoretic solution concepts—most notably Nash equilibrium—predict outcomes that are not consistent with empirical observations. We introduce a new solution concept, iterated regret minimization, that exhibits the same qualitative behavior as that observed in experiments in many games of interest, including Traveler?s Dilemma, the Centipede Game, Nash bargaining, and Bertrand competition. As the name suggests, iterated regret minimization involves the iterated deletion of strategies that do not minimize regret.     

Approximate cores of games and economies with clubs

We introduce the framework of parameterized collections of games with and without sidepayments and provide three nonemptiness of approximate core theorems. The parameters bound (a) the number of approximate types of players and the size of the approximation and (b) the size of nearly effective groups of players and their distance from exact effectiveness. Our theorems are based on a new notion of partition-balanced profiles and approximately partition-balanced profiles. The results are applied to a new model of an economy with clubs. In contrast to the extant literature, our approach allows both widespread externalities and uniform results. A fundamental new mathematical result, the partition-balancing effect of large numbers, which promises to have further applications, is contained in Appendix A.