Invariance and randomness in the Nash program for coalitional games

Nir Dagan and Roberto Serrano

[Summary] [Abstract] [Get the full paper] [Introduction] [Cited by]


We define coalitional games having physical outcomes, rather than only utility profiles. This makes it clear that coalitional games and social choice problems are equivalent, and that so are the theory of implementation and the Nash program.

This clarifies some misunderstandings in regard to invariance and randomness, sometimes found in the literature about the Nash program. In particular a solution concept for coalitional games that is implemented by a scale invariant equilibrium concept (for example, mixed strategy Nash equilibrium) must be scale invariant. By the same token, if a solution concept is implemented by an ordinally invariant equilibrium concept, than it must be ordinally invariant.

This implies that certain solution concepts of coalitional games cannot be implemented in a completely "randomness free" mechanism. For example, the Shapley value and the pre-kernel require that some form of randomness in the implementing non-cooperative game, either in the game itself or in the equilibrium concept.


By introducing physical outcomes in coalitional games we note that coalitional games and social choice problems are equivalent (implying that so are the theory of implementation and the Nash program). This clarifies some misunderstandings (in regard to invariance and randomness), sometimes found in the Nash program.

Keywords: Nash program, implementation, scale invariance, ordinal invariance, randomness.

JEL: C70, C71, C72

Economics Letters 58:43-49 (1998)

Get the full paper


The standard definition of a coalitional game does not include physical outcomes, but only feasible utility profiles. This abstract framework may sometimes lead to basic misunderstandings. The purpose of this note is to dispel two such misconceptions, found in the Nash program. Generalizing the model in Serrano (1997), we extend the definition of a coalitional game to include physical outcomes. This will prove helpful to our purpose.

If players are Von Neumann-Morgenstern expected utility maximizers, the different properties of invariance of a utility scale to transformations must play a central role. We present two results. Both are simple corollaries of invariance and they are well understood (especially the first one) by the practitioners of the abstract theory of implementation. Unfortunately, the same cannot be said for the Nash program, both in its folklore and in its printed material. One could attribute this to the "black box" of the characteristic function, entangled with the view that "the Nash program is not implementation."

The first result asserts that a coalitional solution concept can be arrived at from the noncooperative theory only if it is scale invariant. By the same token, if a solution is not scale invariant its normative appeal is also very restricted, since an uninformed planner cannot implement it. Essentially, if there is a noncooperative game related to such a solution, the game must change with the underlying environment (see Bossert and Tan, 1995 for a game related to the egalitarian bargaining solution).

We shall consider a solution concept to coalitional games as being independent of any randomization if it can be implemented by a strategic game and a strategic equilibrium concept that do not include any random element. Our second result says that if a solution concept is independent of randomizations, it must be ordinally invariant (like the core, bargaining sets or Walrasian equilibria). This implies that major solution concepts in coalitional games (e.g. the Nash bargaining solution, the NTU-Shapley value) can be derived strategically only by considering the possibility of random outcomes: either chance moves, mixed strategies, or pure strategy equilibrium refinements based on trembles must be part of the analysis. Mechanisms that support these solution concepts cannot be criticized for introducing random devices, since they are essential to the implementation results. We can dispel now numerous comments (received in seminars over the years) present in the folklore, like "the fair coin again?," "an implementation of the Shapley value would be much nicer without randomness, which already gives it away," or "Can't you think of more realistic and natural mechanisms? When have you seen people randomizing in the real world?" Thus, our second result stresses the major role that risk plays in much of the theory of coalitional games.

Cited by

  1. Jörg Naeve, Nash implementation of the Nash bargaining solution using intuitive message spaces, Economics Letters 62:23-28 (1999)
  2. Walter Trockel, Implementations of the Nash solution based on its Walrasian characterization, Economic Theory 16:277-294 (2000)
  3. David Pérez-Castrillo and David Wettstein, Bidding for the surplus : a non-cooperative approach to the Shapley value, Journal of Economic Theory 100:274-294 (2001)
  4. Walter Trockel, A universal meta bargaining implementation of the Nash solution, Social Choice and Welfare 19:581-586 (2002)
  5. Walter Trockel, Integrating the Nash program into mechanism theory, Review of Economic Design 7:27-43 (2002)
  6. Walter Trockel, Can and should the Nash program bo looked at as a part of mechanism theory? in Murat R Sertel and Semih Koray (Eds), Advances in Economic Design, pp. 153-174, Springer (2003)
  7. Werner Güth, Klaus Ritzberger, and Eric van Damme, On the Nash bargaining solution with noise, European Economic Review 48:697-713 (2004)
  8. Peter J Hammond, Utility invariance in non-cooperative games, in Ulrich Schmidt and Stefan Traub (Eds), Advances in Public Economics: Utility, Choice and Welfare: A Festschrift in honor of Christian Seidl, pp. 31-50, Springer, (2005)
  9. Roberto Serrano, Fifty years of the Nash program, 1953-2003 Investigaciones Económicas 29:219-258 (2005)
  10. Claus-Jochen Haake, Two support results for the Kalai-Smorodinsky solution in small object division markets, Mathematical Social Sciences 57:177-187 (2009)