Extensive form games with coalitional actions

Nir Dagan

This version: January 1999.
First draft was disributed in 17 December 1995

The latest version of this article is permanently available at <http://www.nirdagan.com/research/199502/>


I introduce a model of extensive form games with coalitional actions, which provides a formal framework for analyzing situations in which coalitions of players may take joint actions sequentially. I present an equilibrium concept that generalizes subgame-perfect equilibrium, and is closely related to the core. The new theory provides insights into the theory of sequential economies.

Keywords: Extensive form games with coalitional actions, backward induction, recontracting equilibrium, core, subgame perfect equilibrium.

JEL: C71 and C72.

1. Introduction

There are many economic situations that have both a sequential nature and the possibility of forming coalitions. A major example is multi-period economies which are traditionally analyzed within the Walrasian price-equilibrium paradigm. As the theory of coalitional games is very successful in the analysis of one-period economies, it seems natural to extend it to sequential situations in order to enable a game theoretic analysis of sequential economies.

Section 2 of this paper provides a new game-theoretic tool that may be useful in studying sequential economies. Section 3 reviews previous literature which is concerned with extending the theory of the core to economies in which markets are opened over time. Section 4 provides a preliminary analysis of sequential economies using our new game-theoretic framework. Section 5 concludes.

2. Extensive Form Games with Coalitional actions

2.1 Basic Definitions

I consider only games with complete and perfect information. I follow the notation of Osborne and Rubinstein (1994) as much as possible.

Definition 2.1
An extensive form game with coalitional actions (hence a game) consists of:
  1. A nonempty finite set of players N={1,...,n}.
  2. A set of histories H (each history h≠∅ is a finite or infinite sequence) that has the following structure:
    • The empty history ∅ is a member of H.
    • If (ak)k=1,...,K∈H (where K can be infinite) and L<K then (ak)k=1,...,L∈H.
    • If an infinite sequence (ak)k=1,... satisfies (ak)k=1,...,L∈H for every positive integer L, then (ak)k=1,...∈H. A history (ak)k=1,...,K∈H is terminal if it is infinite or if it is finite and there does not exist an element aK+1 such that (ak)k=1,...,K+1∈H. The set of terminal histories is denoted by Z. For all h∈H\Z let A(h)={a|(h,a)∈H}. The set A(h) is called the set of actions after the history h.
  3. A function P that assigns to every element of ∪h∈H\ZA(h) a coalition S∈C={S|S⊂N, S≠∅}.
  4. A list of utility functions u=(ui)i∈N, such that for all i∈N ui:Z→R.

There is a natural analogy between articles 1,2 and 4 to the elements that constitute an extensive-form game in the older sense. Note that the function P in article 3 is different from the player function in traditional extensive form games in two aspects. First, each action is assigned to a coalition, rather than a player; second, different actions that follow a certain history may be assigned to different coalitions. That is, it could be that after a given history different coalitions are allowed to move. However, coalitions do not move simultaneously, but can "jump" before each other.

Remark: Consider a game that has the following property: For every history h∈H\Z there exists a player i∈N such that for all a∈A(h) P(a)={i}. A game like that may be called a classical extensive-form game.

The analysis below is analogous to considering only "pure strategies." At the end of this section we discuss the possibility of "mixed" outcomes. Before going to examples that motivate the definition, another definition is needed.

Definition 2.2
A behavior in a game is a function σ that assigns to every nonterminal history h a unique action in A(h).
For each behavior σ, denote by O(σ) the unique terminal history that would result if the players were to follow σ. Call O(σ) the outcome of σ. Let h∈H\Z; donate by O(h;σ) the unique terminal history that will result if the players reached h and afterwards follow σ.

Example 2.3: Consider a coalitional game (N,V) where N is a nonempty finite set of players, and V is a correspondence that assigns to every coalition S∈C a nonempty set V(S) of utility profiles (to the members of S). If the coalition S is formed, its members may implement any outcome in V(S); however, the utility levels of other players are not specified. This incomplete description may not matter if we understand V(S) as the utility profiles the members of S can achieve independently of the behavior of other. In order to represent a coalitional game as an extensive form game with coalitional actions, one must make assumptions about what happens after a coalition forms. A natural assumption is that after a coalition forms, its members become inactive and the rest of the players can go on forming coalitions. This leads to the following definition:

  1. The set of Players N={1,...,n} is the same as in (N,V).
  2. The set of histories is described as follows: The empty history, ∅, and all sequences of the form (Sk,xk)k=1,...,K such that for all k=1,...,K Sk⊂N, xk∈V(Sk), and for all i,j∈{1,...,K} with i≠j, Si∩Sj=∅.
  3. The utility functions u=(ui)i∈N, are defined as follows. Let h=(Sk,xk)k=1,...,K be a terminal history, and i∈Sj,j∈{1,...,K}. Define ui(h)=xij.

2.2 Solution Concepts: Finite Horizon Games

Backward induction can be defined in finite horizon games. This concept is defined recursively on the length of the game-tree. The backward induction solution defined below extends the concept from extensive form games with individual actions to those with coalitional actions, and is closely related to the core of a static coalitional game.

Definition 2.4
Let Δ=(N,H,P,u) be a game. The subgame of Δ that follows the history h is Δ(h)=(N,H|h,P|h,u|h), where H|h is the set of sequences h' for which (h,h')∈H; P|h(h')=P(h,h'); and for all i∈N ui|h(h') = ui(h,h').
Definition 2.5
Let Δ=(N,H,P,u) be a game. A behavior σ is a backward induction solution of Δ if:
  1. In games Δ of length 1: there does not exist an action a∈A(∅) such that P(a)=S and ui(O(a))>ui(O(σ)) for all i∈S.
  2. In games Δ of length n: the behavior σ|h is a backward induction solution in all strict subgames Δ(h), and there does not exists an action a∈A(∅) such that P(a)=S and ui(O(a;σ))>ui(O(σ)) for all i∈S.
Proposition 2.6
If an outcome of a static coalitional game is supported by a backward induction solution of the corresponding extensive form given in Example 2.3, then this outcome is a core outcome.
Proposition 2.7
If all subgames of a coalitional game have nonempty cores, then every core outcome of the static game can be supported by a backward induction solution of the extensive form given in Example 2.3.

The proofs of the above two propositions are omitted. By a static-subgame I mean the static game obtained by restricting the static game to a subset of the players. In Example 2.3 the continuation of the game after a coalition formed does not matter for the forming coalition. This is not the case in Example 2.8 below.

Example 2.8: The set of players is N={1,2}; the set of histories is H={∅,L,R,(L,l),(L,r)}; the player function is P(a)=N for all actions a; and the utility functions u1(R)=1, u1((L,l))=3, u1((L,r))=2; u2(R)=1, u2((L,l))=0, u2((L,r))=2.

|     R       (1,1)
|     r       (2,2)
| l

Note that all three terminal histories can be supported as backward induction solutions. In particular, the outcome R, together with the action l after L. Thus, "cooperation" or the ability to make binding agreements is restricted to the joint actions specified by the game. No further level of cooperation is assumed through the solution concept. Clearly, refinements of the type of "renegotiation-proof" may be considered here as in classical extensive form games. Following the reasoning of renegotiation proof equilibrium, the players can improve upon the payoff (1,1) by renegotiating the equilibrium that they will play if they were to take the action L. Gale's (1981) weak sequential core contains such reasoning. (See Section 3 below for more details).

2.3 Solution Concepts: Infinite (and Finite) Horizon Games

In order to define an equilibrium concept for infinite horizon games, it will be useful to define a concept similar to a "strategy of a player," that will allow for a non-recursive definition of equilibrium. The major difference between the concept defined here and strategies is that here the "strategy sets" are endogenously determined.

Definition 2.9
Let Δ=(N,H,P,u) be a game and σ a behavior. An action a∈A(h) is available for player i (with respect to σ) at history h if: P(a)=T, i∈T, and for all j∈T\{i} uj[O((h,a);σ)]>uj[O(h;σ)].

An action is available to a player, either if he can take it on his own, or he "can convince" the other players involved in the action to take it. The "passive" players are assumed to believe that the equilibrium behavior will prevail after the deviation.

Definition 2.10
Let A(h) donate the set of all available actions of player i at history h with respect to σ. The recontracting set of player i with respect to σis:
Zi(σ)={g:H*→∪h∈H\ZA(h)| H*⊂H\Z and for all h∈H* g(h)∈A(h)}

The recontracting set describes all possible deviations available to an individual given a behavior.

Let σ be a behavior, H* be a set of non-terminal histories, and g be a function that assigns each history h∈H* a unique action in A(h). The behavior σ|g (σ modified by g) is defined by σ|g(h)=g(h) if h∈H*, and σ|g(h)=σ(h) otherwise.

Definition 2.11
Let Δ=(N,H,P,u) be a game. A behavior σ is a recontracting equilibrium if there does not exist a player i∈N, and a function g∈Zi(σ) such that ui(O(σ|g))>ui(O(σ)).
Definition 2.12
Let Δ=(N,H,P,u) be a game. A behavior σ is a subgame perfect recontracting equilibrium if its restriction to every subgame is a recontracting equilibrium.
Proposition 2.13
In finite horizon games the set of subgame-perfect recontracting equilibria coincides with the set of backward induction solutions.

The proof is essentially identical to the analogous proposition for classical extensive form games, and is therefore omitted.

Remark: A possible extension of the set of recontracting equilibria would be to consider mixed behaviors. A mixed behavior is a function that assigns every non terminal history a probability distribution on the set of actions the follow this history. The utility functions should be extended to evaluate lotteries over outcomes. There should be no other modification in the other definitions. Note that in a recontracting equilibrium with a mixed behavior, if more than one action after a certain history have positive probabilities, it does not imply that all players involved in those actions are indifferent between them.

3. Previous Literature Reconsidered

Several concepts were proposed by various authors as generalizations of the core to sequential markets. These include Gale (1978, 1981), Bester (1984), Repullo (1988), and Koutsougeras (1995, 1996). All of this literature did not consider a general model of extensive form games with coalitional actions, but attempted to define the core of a sequential economy directly.

I concentrate on examples of pure exchange economies with two stages of trade and complete information. First, let us informally describe an example of Douglas Gale (1978). There are two agents, and trade takes place at two dates. In the first date, the apple season, both agents are endowed with certain amounts of apples. They may agree on trades that include a transfer of apples from one agent to another, and the exchange of "IOUs" in the form "agent i will provide the bearer on demand the amount of x bananas in the banana season". Each agent may decide unilaterally not to trade. The apples must be consumed in the first date. In the next date, the banana season, the agents are endowed with certain amounts of bananas; in addition they carry the IOUs that they received in the apple season. Now, the agents may agree on any reallocation of the bananas. Each agent may decide unilaterally not to trade; in particular, an agent who wrote an IOU can simply disregard it. The agents have preferences on their own (intertemporal) consumption plans.

The above description is sufficient in order to apply backward induction. In all subgames in the beginning of the banana season the outcome must be that no trade takes place. Now, it is clear that also in the apple season the players will end up with their endowments, since a transfer of apples from one agent to another will be followed by consuming the banana endowments in the next season.

Now consider two-stage exchange economies, like in Gale's example, but that may include more than two agents. The different "cores" were defined with respect to these kind of economies without specifying a game tree or any other structure or assumptions. All authors in this literature defined an outcome as a redistribution of the endowments in both periods. In other words, outcomes and equilibria were described as paths, rather than a complete description that includes behavior "off the path".

Note that for every reallocation of the endowments in the first period, there is an induced static exchange economy in the second period. The first part of the definition of all these "cores" is that the reallocation of commodities in the second period is a core allocation in the second period induced economy. The second part of the definition requires that no coalition can improve upon the allocation in the first period. At this point different papers came up with different definitions.

Douglas Gale (1978) was the first who addressed the problem of regarding a sequential economy as a coalitional game. In order to define the concept of improving upon in the first date, Gale (1978) considered the complete-markets Arrow-Debreu economy associated with the two stage economy, and required the outcome to be a member of the core of this economy as well. In other words, a coalition can improve upon in the first date, by an intertemporal transaction that is not implementable in the two stage economy. Gale (1978) called this solution concept the "sequential core," and applied it to finite horizon economies. Note that the sequential core of the economy described in the example given in the beginning of this section is empty, since any Pareto optimal allocation involves a transfer (in both periods and in particular) in the second period. Becker and Chakrabarti (1995) applied the "sequential core" to an infinite horizon economy with a recursive structure. They did not introduce any new solution concept.

Gale (1981) noted that the sequential core exhibits a certain inconsistency: contracts that are not self enforcing are excluded in equilibrium but are valid for "improving upon" a candidate for equilibrium. Thus, he proposed an alternative. He defined an intertemporal plan to be consistent if in the second period the reallocation is in the core of the induced second period economy. Then he defined the "weak sequential core" as those intertemporal allocations such that no coalition S can improve upon with a consistent intertemporal S-allocation.

Koutsougeras (1995) defined the concept of "improve upon" in the first period as follows: A coalition can improve upon in the first period if it can reach a higher intertemporal utility level than the core-outcome by reallocating its members' endowments in the first period, and each member consuming his endowment in the second period.

Bester (1984), Repullo (1988), and Koutsougeras (1996) considered another definition (which Repullo called the "segregated core") in which a coalition can improve upon in the first period by reallocating their endowments in the first period, and assuming that their net trades of the second period will be identical to the ones assigned by the "core-outcome." In this solution concept the players conceive past trades and future trades as given, and cannot consider to change their future plan of net trades. In the "segregated core" the off equilibrium path after the initial deviation must be identical to the equilibrium path.

In other words, the "segregated core" is a solution concept of a sequential economy in which agents do not face sequential decision problems and is probably inconsistent with game theoretic models that assume that the players are rational. Players do not optimize when choosing a consumption plan, but consider partial optimization problems induced from their "equilibrium" behavior.

Koutsougeras (1996) noted that Repullo's (1988) segregated core has another problem. When there are commodities that can be transferred over time, the assumption of keeping future net trades fixed while considering a deviation may be inconsistent with feasibility. Koutsougers (1996) analyzed the segregated core of an economy with a continuum of agents in which only finite coalitions can form; in this situation the feasibility problem does not occur.

In my view, the surveyed literature made arbitrary implicit assumptions on off equilibrium behavior, due to the fact that it insisted to avoid a formal and complete description of the off equilibrium path.

Moreover, a great deal of the above mentioned work is obsessed with proving "equivalence theorems" that provide "foundations" or "justifications" for the Walrasian paradigm. In my view, the core can be understood as a more basic concept than Walrasian equilibrium since it is defined for all coalitional games (although it may be empty), while Walrasian equilibria are defined only in a special class of coalitional games: those which are characterized by a commodity space. Within this view, the surveyed literature cannot provide a foundation for anything, as the concepts were defined for a subset of games of those in which Walrasian equilibrium is defined.

Indeed, among the papers that I discussed above, Gale (1981) was the only paper that addresses the issue in a consistent game theoretic manner. However it was hardly mentioned in following literature as it didn't establish any equivalence theorem. In my view, one first has to set up a reasonable model with a sensible equilibrium concept, and only then check for equivalence results. It seems that some of the surveyed literature did the converse. It was first decided to prove an equivalence result, and then an ad-hoc "core" concept was invented to "get it right."

There are two additional groups of papers related to sequential economies and coalitional games. One studies the core of overlapping generations economies (see Chae and Esteban, 1993, and the references therein). However, it refers to the static economy in which agents who are not present in the market at the same time can freely trade with each other. The other consists of extensive-form matching and bargaining models in which the exact bargaining procedure between matched pairs of agents is not modeled, and is solved by the Nash bargaining solution to the endogenously derived bargaining problem. A discussion of this kind of models can be found in Osborne and Rubinstein (1990, Chapter 6).

4. Further analysis of Sequential Economies

In this section I consider an exchange economy in which there exists a unique allocation associated with price equilibrium. The game associated with the economy allows agents to trade as many times as they wish before they leave the market to consume. It is shown that the game has no subgame perfect recontracting equilibrium. This example shows that in a dynamic setting the formation of large coalitions is incompatible with the intuitive notion of perfect competition. The reason for this outcome is that the underlying exchange economy is exposed to the so-called reallocation paradox. The economy is a continuum replica of the economy in the example of David Gale (1974). Gale's (1974) example consists of a static exchange economy with three agents and two goods. The economy has a unique price equilibrium. Gale (1974) showed that if a small fraction of one of the agent's endowment is transferred to another agent, then the resulting unique price equilibrium allocation corresponding to the new endowments is preferred by the two agents involved in the transfer to the equilibrium allocation of the original endowments.

The example I consider involves a three type continuum economy that corresponds to Gale's (1974) three agent economy. The set of core allocations of this continuum economy consists of the unique Walrasian equilibrium. Similarly, it holds for the economy in which the endowments are those after the transfer in Gale's (1974) example.

The coalitional game in extensive form is as follows. In each period any coalition with positive measure can form with a pair of a reallocation and a decision "Stay" or "Leave." If a coalition decided to leave, its members cannot trade anymore. The payoffs correspond to the utilities of the bundles with which the agents leave the market. The game ends if a measure zero of agents is left in the market. The utilities of the agents of this zero measure set is that of the bundles they hold as the game ended. If some positive measure of agents never leaves the market, their utilities are are fixed to something lower than those of their initial endowments. The following lemma applies to the recontracting equilibria of the above described game that corresponds to an arbitrary exchange economy.

Lemma 4.1
Let σ be a recontracting equilibrium. Then there exists a core allocation of the static economy in which for almost all players i their utility level is ui(O(σ)).
If equilibrium payoffs do not correspond to payoffs of a core allocation, then there exists an improving coalition, and each member of this improving coalition has at the beginning of the game the action "form the improving coalition, with the improving allocation decide 'Leave' " in his recontracting set. And thus we reached a contradiction.

Now, consider the game corresponding to the continuum replica of Gale's (1974) example. In this continuum replica the core coincides with the set of Walrasian equilibria.

Proposition 4.2
The set of subgame-perfect recontracting equilibria in game corresponding the continuum replica of Gale's (1974) example is empty.
By Lemma 4.1, the outcome must correspond to the unique Walrasian equilibrium. Now consider the action of the two type coalition forming and doing Gale's transfer, and choosing to stay. In the subgame that follows, by Lemma 4.1, the outcome is the unique Walrasian equilibrium of the economy with the new endowments, which is better for the agents involved in the transfer than the Walrasian equilibrium of the initial endowments. Thus, this action is available to all these agents and improves their payoffs. A contradiction.

One may claim that the above example implies that the Walrasian theory cannot be game-theoretically explained in a dynamic setting. I disagree. Douglas Gale (1986) presented a sequential bargaining game in a continuum economy in which its game theoretic equilibria coincide with the Walrasian ones. In his model only two person coalitions can form, and since these coalitions are of measure zero the players cannot "manipulate" their future trading opportunities. Also Koutougeras (1996) considers only finite agent coalitions, because of this reason among others. Dagan (1997) considers perfectly competitive sequential economies, in which only finite coalitions can form; in his model Walrasian outcomes are supported by an equilibrium concept closely related to subgame perfect recontracting equilibrium. Both the results of Koutsougeras (1996) and Dagan (1997) apply previous results of Hammond, Kaneko, and Wooders (1989) on continuum economies in which only finite coalitions can form.

5. Conclusion

I claim that a proper application of coalitional games to sequential economies can be made only after creating a certain game theoretic framework that has the potential of modeling a large variety of problems. This framework should be based on game theoretic reasoning, rather than on the equivalence theorems that one hopes to prove.

This paper takes an approach, that for most part, based on extensive form games as viewed in the so-called "non-cooperative" branch of game theory. The model and the equilibrium concept are motivated by the view that the possibilities of cooperation are part of the description of the game, rather than an assumption on the equilibrium concept. Although coalitions can take joint actions, the solution concept emphasizes the rationality of individuals when considering deviations.