Bargaining, Coalitions, and Competition

Nir Dagan

Roberto Serrano and Oscar Volij Department of Economics, Brown University, Providence, RI 02912, USA

Abstract:We study a decentralized matching model in a large exchange economy, in which trade takes place through non-cooperative bargaining in coalitions of finite size. Under essentially the same conditions of core equivalence, we show that the strategic equilibrium outcomes of our model coincide with the Walrasian allocations of the economy. Our method of proof makes use of the theory of the core. With respect to previous work, our model relaxes differentiability and convexity of preferences, and also admits indivisible goods.

Keywords: Finite coalitions; strategic bargaining; core; Walrasian equilibrium.

JEL: D51; D41; C78.

This version: July 1998

1. Introduction

The Walrasian or competitive equilibrium is the central solution concept in economics. However, from its definition it is not clear what trading procedures lead to Walrasian outcomes. In contrast to what many economists may think, the original account of the theory (Walras, (1874)) does not rely on the existence of the so-called Walrasian auctioneer.1 Nonetheless, the usual formal presentation of the model includes the auctioneer implicitly due to a lack of explanation for the formation of equilibrium prices.

Negishi (1989) distinguishes two major schools in the analysis of markets. One of them considers prices as part of the economic mechanism in and out of equilibrium. This school is attributed to Cournot (1838) and Walras (1874). A second school, associated with Jevons (1879) and Edgeworth (1881), attempts to consider decentralized trading mechanisms and answer the question of whether equilibrium prices will emerge as the consequence of agents' trading actions.

We can distinguish at least two major approaches in the Jevons-Edgeworth school of decentralized trading. One of them, which today is referred to as the core equivalence literature, has its origins in Edgeworth (1881). This approach finds conditions under which core and Walrasian allocations are equivalent. If one conceives the core as a decentralized mechanism, these results give insights about the Walrasian allocations that were not provided by Walras. The shortcoming of this approach is that, although the core captures a natural idea of coalitional stability, it does not specify the trading procedure either. Here is relevant the work on the non-cooperative implementation of the core in finite games and economies (see, for example, Perry and Reny (1994), Serrano (1995) and Serrano and Vohra (1997)).

A second approach models the trading procedure more explicitly and studies its strategic equilibria. As part of a recent literature that starts with Rubinstein (1982) and Rubinstein and Wolinsky (1985) [henceforth, RW], many researchers have turned to models where a decentralized trading procedure is made explicit in a bargaining extensive form.2 RW (1985) analyze an assignment market and claim that in a frictionless economy the strategic equilibria need not be Walrasian. This claim was challenged later by the classic paper of Gale (1986a), who constructed an alternative bargaining procedure in a continuum economy in which strategic and Walrasian equilibria coincide. Gale's work was generalized in some respects by McLennan and Sonnenschein (1991) [McLS in the sequel].

Combining the above strands of the literature, in this paper we study a decentralized matching model in a large exchange economy, in which trade takes place through non-cooperative bargaining in coalitions of finite size. Under essentially the conditions of core equivalence, we show that the strategic equilibrium outcomes of our model coincide with the Walrasian allocations of the economy. Our model relaxes differentiability and convexity of preferences, and also admits indivisible goods.3 By considering multilateral meetings in which trade takes place, we are able to use the full power of the theory of the core. In doing so, it becomes apparent that the driving force behind core equivalence and Gale-like results is similar: core equivalence takes now a non-cooperative dimension.

From an implementation theoretic point of view, we construct a mechanism that fully implements the Walrasian allocations of an economy with a continuum of agents. In contrast to all previous work, though, implementation is achieved over a substantially larger class of economies. Moreover, our mechanism can be seen as an ε-perturbation of Gale's, since meetings involving more than two agents can be assumed to have negligible probability.

Free of the differentiability assumption, our model differs from the preceding ones in allowing for trade to take place in coalitions with any finite number of participants, as opposed to only pairwise meetings. This trade-off in the modelling choice leads to two distinct methods of proof and captures different insights. The proofs of the existing results (Gale (1986a, c), McLS (1991)) rely crucially on the existence of the marginal rate of substitution at every bundle in order to get the unique (to that bundle) supporting price. Since in the strategic equilibrium of these models there cannot be any pair of agents with positive gains from trade, by differentiability, at the equilibrium bundles every two agents have the same marginal rate of substitution. Consequently, this must hold for all agents. Feasibility of the equilibrium outcome (zero aggregate excess demand) and some extra technical assumptions then take care of the rest of the argument.4 In contrast to this method of proof, Theorem 1 uses the theory of the core to show that every strategic equilibrium yields a Walrasian allocation. The existence of marginal rates of substitution is not necessary. Since we allow for finite coalitions to meet, in our strategic equilibria there cannot be any such coalition with positive gains from trade. Then, a powerful lemma due to Hammond, Kaneko and Wooders (1989) and core equivalence take us the rest of the way without the intermediate aid of differentiability.

Unlike our first result just referred to, its converse, Theorem 2, does not use the theory of the core. That is, although we allow for finite coalitions, it turns out that all equilibrium outcomes of our game can be supported by strategies according to which all trade takes place in pairs. In this sense, pairwise trade arises as an endogenous feature of the procedure instead of being imposed as an exogenous restriction. On the other hand, our trading procedure is indeed decentralized, since finite coalitions are negligible in the continuum. Moreover, if all gains from trade in the economy can be exhausted in coalitions bounded by a given finite size k (e.g. assignment markets, like in RW (1985) in which k=2), one can restrict the matching process to meetings of size k+1.

The paper is organized as follows: Section 2 describes the underlying economic model. The non-cooperative bargaining game is described in Section 3. The main result is presented in Section 4. In Section 5 we show that every Walrasian allocation can be supported by a strategic equilibrium of the game, and Section 6 concludes and compares our results with the previous literature.

2. Description of the Economy

Let (A, A*, μ) be a measure space, where A is the set of agents, A* is the set of measurable subsets of A and μ is an atomless measure. We denote by C the set of agents' characteristics. An element c∈C is a pair c=(u,e), where u:X→ℜ is a utility function, X is the consumption set and e∈X is an endowment. The consumption set X is assumed to be identical for all agents and is of the form +D×NI, where N is the set of non-negative integers. The consumption set includes |D| divisible goods and |I| indivisible goods; we assume that |D|≥1.

An economy E is a measurable map E:A→C. Let S⊆A be a coalition. An S-allocation f is a measurable map f:S→X that satisfies Sf(a)dμ≤∫Se(a)dμ. Allocations are A-allocations. We denote by F the set of allocations of the economy.

From now on, and whenever there is no danger of confusion, the domain of integration A of the set of all agents will be omitted.

A coalition S can improve upon an allocation f if S has a positive measure and there exists an S-allocation g:S→X such that almost everywhere in S ua(g(a))>ua(f(a)). The core of an economy is the set of all allocations that no coalition can improve upon (see Aumann (1964)).

We shall make the following assumptions on the utility functions of the agents. The assumptions can be grouped into two classes. First, we need the assumptions of Hammond, Kaneko and Wooders (1989) that guarantee the validity of their core equivalence theorem.

A0 All the commodities are present in the economy: ∫e(a)dμ>>0.
For all c=(u,e)∈C:
A1 The utility function u is continuous, strictly increasing in the divisible commodities, and non-decreasing in the indivisible commodities;
A2 for all (xD,xI)∈ℜ+D×NI, there exists yD∈ℜ+D such that u(yD,0I)>u(xD,xI); and
A3 for all xINI, u(e)>u(0D,xI).

In addition, we need assumptions that are necessary to deal with the possibly random outcome of the strategic bargaining process.

A4 The utility functions are bounded: For all c=(u,e)∈C: there exists a number ku such that u(x)≤ku for all x∈X.
A5 The economy satisfies strong aggregate risk aversion in the individually rational domain (defined in the following paragraphs.)

Aggregate Risk Aversion

Gale (1986a, b, c) assumes that all individuals have strictly concave utility functions. This assumption is used in order to prove that the outcome of a strategic equilibrium of the market is a degenerate lottery. This assumption excludes the possibility that the consumption sets include indivisible goods. This makes the comparison of his model with the earlier ones (e.g. RW (1985)) difficult. The work of McLS (1991) dispenses with the convexity assumption, but requires differentiability. Therefore, also in their framework indivisible goods cannot be studied. On the other hand, one should expect that the convexification effects of large numbers may help relax the assumption of individual risk aversion of preferences. These arguments motivate our assumption of aggregate risk aversion.

A lottery on allocations is a probability measure on the Borel σ-algebra of allocations. We shall say that the economy satisfies weak aggregate risk aversion if for every lottery L on allocations there exists an allocation g such that for almost all agents ua(g(a))≥∫Fua(f(a))dL.

We say that the economy satisfies weak aggregate risk aversion in the individually rational domain if it satisfies weak aggregate risk aversion when considering only lotteries that assign an expected utility at least as high as the utility of the endowment.

A lottery L is degenerate if for almost every agent a there exists a constant ka such that ua(f(a))=ka for L-almost all f∈F. The economy satisfies strong aggregate risk aversion if it satisfies weak aggregate risk aversion and for every lottery which is not degenerate there exists an allocation g that satisfies for almost all a∈A ua(g(a))≥∫Fua(f(a))dL, and there exists a set of agents of positive measure for whom the inequality is strict.

Strong aggregate risk aversion in the individually rational domain is defined just like its weak counterpart. Aggregate risk aversion means that society cannot gain from lotteries over allocations. The strong version of the property means that if the lottery is non-degenerate, society actually will lose from having the lottery.

Although this is a property on the aggregate, we find conditions on individual preferences that are weaker than concavity of the utility functions that imply the corresponding aggregate risk aversion properties.

First we consider an individual with a utility function u:X→ℜ. We define the quasiconcave cover of u as u:X→ℜ, where X is the convex hull of X:

u(x)=max{u(y): x∈R(y)}

where R(y) is the convex hull of the set of all bundles that are weakly preferred to y. The assumption that the consumption set X is bounded below and assumption A1 on the utility function u ensure the existence of u, as shown in Einy and Shitovitz (1997, Lemma 3.3). See also Starr (1969, Appendix 3) for an early treatment of non-convex preferences.

The first condition we consider is simply that u is concave for almost all agents.

Proposition 1
If the quasiconcave covers of the utility functions of almost all agents are concave, then the economy satisfies weak aggregate risk aversion.

A slightly stronger assumption on individual preferences is that the quasiconcave cover of the utility function is almost strictly concave. A function v:X→ℜ is almost strictly concave if for all x1,x2∈X such that v(x1)≠v(x2) and for all λ∈(0,1) we have that v(λx1+(1-λ)x2) > λv(x1)+(1-λ)v(x2). The difference between almost strict concavity and strict concavity is that the former requires that v(x1)≠v(x2) and not simply that x1≠x2. This difference is crucial for our purposes, because if a cover is strictly concave, the original function is strictly concave as well, whereas functions that are not even quasiconcave may have an almost strictly concave cover.

Proposition 2
If the quasiconcave covers of the utility functions of almost all agents are almost strictly concave, then the economy satisfies strong aggregate risk aversion.

The two propositions are proved in the appendix. It follows that if the quasiconcave covers (restricted to the individually rational domain) of the utility functions of almost all agents are almost strictly concave, then the economy satisfies strong aggregate risk aversion in the individually rational domain, which is the assumption we need.

Example An example will be useful to clarify our last assumption A5. Consider an individual who may consume two goods: one of them is perfectly divisible and the other is indivisible, (like in an assignment market of RW (1985)). The agent wants to consume at most one unit of the indivisible good and his reservation price in terms of the divisible commodity for the first unit of the indivisible good is 1. More formally, the commodity space is +×N. His utility function is u(x1,x2)= v(x1+I(x2)) where I(x2)=1 if x2≥1 and I(x2)=0 otherwise, and v is a strictly increasing, strictly concave and bounded function from + to . Suppose agents differ only in their endowments, i.e., each buyer holds only one unit of x1 and each seller holds one unit of x2. Since the consumption set contains indivisible goods, there is no clear notion of risk aversion of preferences in this setting. However, the quasiconcave cover of u, restricted to the individually rational domain, is almost strictly concave: u(x1,x2)=v(x1+min{x2,1}). This implies, for example, that if there is a continuum of such agents with the same preferences, the economy cannot gain from introducing lotteries over bundles.

3. Description of the Game

The set A of all agents is present from the outset. Time runs discretely from 1 to infinity. In each round the agents are matched at random into coalitions of finite size. At every round t there is a proportion α∈(0,1) that is left unmatched. For each round t and each size n≥1, there is a positive probability p(n) of being matched in an n-person coalition. Thus, p(1)=α. Matches are made randomly and for a fixed n≥2 the probability of being matched to any n-1 agents chosen from n-1 sets is proportional to the product of the measures of these sets.5

When a coalition S meets, there is a 'cheap talk' phase in which every agent announces a bundle.6 In addition, an order is chosen at random with equal probability. Denote by xj the bundle held by agent j∈S at the beginning of this meeting. The first agent in the order becomes the proposer, who makes a public offer consisting of a trade (zj)j∈S in which j∈Szj=0 and for all j∈S, xj+zj∈X. Responses are also public and occur sequentially following the order. They can be one of two possible actions: 'yes,' and 'no.' The trade proposed to the coalition takes place if and only if every responder agrees to it. Every agent who is matched in round t can, if he so wishes, leave the market and consume his bundle after the bargaining session ends. Agents who are not matched in round t cannot leave the market in that round. In the next round, all agents who chose to leave abandon the market place and consume their current bundle. All other agents continue as active traders ready to be matched again.

In each round each agent recognizes the economic characteristics of the agents with whom he is matched. These consist of the current bundle each of them holds and their utility functions. However, they do not have information about their histories: each agent remembers only his own, but not the others'. They do not know anything about meetings that do not include them.

The restrictive information available to traders requires us to endow agents with beliefs about what happens elsewhere in the market. This must be done in order to have well defined expected utility computations. We will take care of these details in the next section, where we present our equilibrium notion.

The payoff to a typical trader in this market is the utility of the bundle with which he leaves the market. Thus, there is no discounting. On the other hand, if an agent never leaves the market, his utility is the utility corresponding to the zero bundle. All agents are expected utility maximizers when evaluating lotteries over bundles.

4. The Equilibrium Notion and the Main Result

A strategic equilibrium is a particular type of perfect Bayesian equilibrium (see Fudenberg and Tirole (1991) for the general notion of PBE), i.e., it is a profile of strategies, one for each agent, such that, given the beliefs explained below, every agent plays a best response to the others at every information set. On the equilibrium path, we shall assume that beliefs are derived from the equilibrium strategies using Bayes' rule. On the other hand, off the equilibrium path we shall assume that each agent believes that a full measure of the agents continues to play according to the equilibrium. This equilibrium concept is motivated and formally defined in the sequel.

Since each agent is an entity of measure 0 in the continuum and since each of them has met only a finite number of agents in all the rounds up to round t, we can define the variable of the "state of the market." That is, a fixed profile of strategies played by the continuum of agents determines the state of the market in round t as a distribution over characteristics. This happens with independence of the actions of a set of measure 0 (the history of an agent at a given point). Notice that the distribution over characteristics that we refer to as the 'state of the market' need not be supported by an allocation of the economy. Such an example can be constructed following the one found in Kannai (1970). However, a distribution is all an expected utility maximizing agent needs in order to make his calculations.7

Now we can state more formally the equilibrium concept based on Osborne and Rubinstein (1990) as follows:

A strategic equilibrium is a pair of functions (σ,β), that assign to each agent a strategy and a belief, respectively, such that:
  1. The beliefs β are the "state of the market" beliefs induced by σ both on and off the equilibrium path,
  2. For each agent a and for each of his information sets, σ(a) prescribes a best response to σ(A\a) given the beliefs β(a).

Our main result follows.

Theorem 1
Suppose that the economy satisfies assumptions A0-A5. In every strategic equilibrium there exists a core allocation f such that almost every agent a eventually leaves the market with a bundle g(a) such that u(g(a))=u(f(a)).

Note that in equilibrium an agent may receive a lottery over different bundles (due to the random matching process and possibly to mixed strategies, the same equilibrium comprises different paths). However, all of these bundles belong to the same indifference surface. If there were several core allocations that assign the same utility to almost every agent, then the outcome could be a lottery over these core allocations.

Proof Consider a strategic equilibrium. All of our statements are relative to this equilibrium and to histories in which at most a set of agents of measure 0 has deviated. Since each agent's history is private information and as the matching process treats all agents alike, two agents with the same characteristics and beliefs must get the same payoff regardless of their histories. If not, the agent with the lower payoff would simply imitate the behavior of the other and get the same probability distribution over outcomes. Recall that all agents have the same beliefs about the "state of the market" independent of their histories.

All agents at the beginning of round t before their match has been determined believe that the "state of the market" corresponds to the equilibrium. Thus in the equilibrium all such agents that in addition share the same characteristics have the same expected utility. We denote this utility by V(c,t). For each c=(u,e), we define w(c)=u(e).

Step 1: V(c,t)≥w(c) for all values c and t.

To see this, notice that every agent with characteristics c in period t can adopt the following strategy: whenever matched, propose the zero trade, reject any trade, and leave the market. Since with probability 1 he will be matched in finite time, this strategy guarantees him a payoff of w(c).

Step 2: V(c,t)≥V(c,t+1) for all values of c and t.

This assertion follows from the fact that by proposing the null trade and rejecting every offer and staying in the market, any agent in the market in round t is sure to be in the market in round t+1 with the same bundle as in round t.

We shall say that an agent is 'about to leave the market' if he has already reached an information set at which his strategy tells him to leave.

Step 3: For an agent of characteristic c who is about to leave the market in round t, we have that V(c,t+1)=w(c).

By Step 1, we have that V(c,t+1)≥w(c). If V(c,t+1)>w(c) and given that this agent is about to leave the market, he would be better off by deviating and staying in the market until round t+1.

Step 4: At some round t there is a positive measure of agents who are about to leave the market.

We argue by contradiction. Suppose that no positive measure of agents ever leaves the market. In this case the utility of almost all agents is that of the zero bundle. On the other hand, at any point in time there is a positive measure of agents who hold a bundle different from the zero bundle. This contradicts Step 1.

At this point our method of proof separates crucially from Gale's. Instead of proceeding through a sequence of lemmas based on the existence of the marginal rates of substitution, we employ the insights of the theory of the core.

Step 5: There does not exist a coalition S∈A* with μ(S)>0, that has an S-allocation g for which ua(g(a))>V(c(a),1) for almost all a∈S, where c(a) is the initial characteristics of agent a.

Assume there exist such a coalition and such an allocation. Then, by Hammond, Kaneko and Wooders (1989, Claim 1) there exists a partition of this coalition into h+1 coalitions S0,S1,…,Sh such that μ(S1)=μ(S2)=…=μ(Sh)>0 and a list of trades z1,…,zh such that for all a∈Sm, m=1,…,h  ua(e(a)+zm)>ua(g(a)) and mzm≤0. Informally, this means that there are 'many' h-person (finite) coalitions that can improve upon the S-allocation g.

By step 4, at some round t a positive measure of agents is about to leave the market. We will show now that, under the contradiction hypothesis we are making, i.e., the existence of the improving coalition S, Step 3 would be violated. Recall that in every round t a positive measure of agents did not trade yet and thus keep their initial endowment. In particular, there is a positive measure of agents that can be chosen from each of the above coalitions S1,…,Sh. It follows from Step 2 that in every round t the probability of an agent to be matched in an h+1-person coalition such that his h partners constitute an improving coalition is positive. Now each person who is about to leave the market can adopt the following strategy: to stay in the market and whenever being a proposer in such an improving coalition, to offer them an improving trade z which gives the proposer higher amounts of some divisible goods without giving away any amount of the others; in all other situations, he holds on to his bundle and leaves the market at some finite date. The proposal z will be unanimously accepted by the members of the improving coalition since for each of them with characteristic c=(u,e) we have that:
where the first inequality follows from Step 1, the second from the existence of the improving trade z for the group of responders and the third from step 2. Clearly, this deviation gives the deviating agent a higher expected utility than the utility of his current bundle, which contradicts Step 3.

Step 6: In a strategic equilibrium, there exists a core allocation f such that almost every agent a eventually leaves the market with a bundle g(a) such that u(g(a))=u(f(a)).

By the previous step applied to the set of all agents A, it is not true that A can improve upon the strategic equilibrium outcome. In addition, this must be such that almost every agent is receiving a degenerate lottery over bundles. Otherwise, since the economy satisfies strong aggregate risk aversion, Step 5 would be violated. In addition, the equilibrium outcome satisfies all the core conditions. In order to choose the core allocation that is utility equivalent to the equilibrium outcome, note that almost every path in the extensive form associated with the equilibrium strategies constitutes a core allocation. Thus, it suffices to choose any such path.

Corollary 1
Suppose that the economy satisfies assumptions A0-A5. In every strategic equilibrium there exists a Walrasian price p such that almost all agents eventually leave the market with a bundle that maximizes their utility on the budget set corresponding to the price p and to their initial endowment e.

Proof: By Hammond, Kaneko and Wooders (1989, Theorem 2), A0-A3 imply that core allocations are Walrasian.

Remark: If agents are allowed to observe the state of the market every period, Theorem 1 and its proof go through without change when the solution concept used is the unrestricted set of perfect Bayesian equilibria.

5. Supporting Walrasian Allocations by Strategic Equilibria

In Corollary 1 we have shown that all strategic equilibrium outcomes are Walrasian. Next we show the converse. That is, for every Walrasian outcome we find strategies that support it as a strategic equilibrium. In the proof below, no use will be made of the fact that the Walrasian allocation f is also a core allocation. This departs from the papers on implementation of the core in finite games and economies (e.g., Perry and Reny (1994), Serrano (1995) and Serrano and Vohra (1997)). There, the strategies that support each core allocation are of the following form: the allocation in question is proposed to the grand coalition, and it is unanimously accepted. Obviously, such a construction is not possible in a decentralized model of trade among a continuum of agents.

Theorem 2
Let f be a Walrasian allocation corresponding to an equilibrium price p and suppose that all agents have a maximizer over every budget set corresponding to the price vector p. Then, there exists a strategy profile that supports f as a strategic equilibrium outcome of the game.

The assumption in Theorem 2 is needed in our model as we can have Walrasian equilibria with some prices equal to 0. In this case, it could be that some agents (that constitute a set of measure 0) do not have an optimal bundle in their budget sets even in the equilibrium allocation. Of course, if equilibrium prices are all positive, or the model is a standard assignment market, (e.g. like in RW (1985)), the assumption in Theorem 2 is satisfied. In the models of Gale (1986a, b, c) and McLS (1991), such an assumption is also needed since they work with open consumption sets.

Proof: For each agent a let h(a,e) be a function that assigns to each agent a with holdings e a bundle selected from the agents' demand correspondence with respect to the price p and the income pe. The selection h is restricted so that h(a,e)=f(a) if pe=pe(a). Now consider the following strategy profile:

  1. In all meetings every trader announces during the 'cheap talk' phase the bundle assigned to him by the selection h.
  2. In multilateral meetings (those with at least three agents), the proposer offers the 0 trade.
  3. In bilateral meetings, the proposer offers a trade according to the trading rule g defined below (which is based on Gale (1986b)).
  4. In all meetings, every responder a who currently holds e that did not achieve the bundle h(a,e) accepts a trade if and only if his income (the value of his holdings evaluated at the prices p) does not decrease. If he already achieved the bundle h(a,e), then he accepts if and only if his income increases.
  5. Every agent leaves the market as soon as he achieves the bundle h(a,e).

On the equilibrium path and as in Gale (1986b), we shall distinguish between the behavior of one of the divisible commodities (say, commodity 1) and that of the other |D|+|I|-1 goods. While according to the trading rule g an agent's excess demand in commodities other than 1 is non-increasing, commodity 1 serves to balance the budget whenever there is no pure coincidence of wants.

In order to define the trading rule g, we shall denote the proposer by a0 and the responder by a1. Subscripts denote agents and superscripts denote commodities. Let z0 be h(a0,e(a0,t))-e(a0,t), where e(a0,t) are the holdings of a0 in round t, and similarly let z1 be h(a1,e(a1,t))-e(a1,t). Define the set B(z0,z1) as the set of vectors x∈ℜD×ZI satisfying the following conditions (where Z denotes the set of integers):

  1. |xk|≤|zki|,   i=0,1,  k≥2
  2. 0≤(-1)ixkzki,   i=0,1,  k≥2
  3. e(ai)+(-1)ix∈ℜ+D×NI and px=0  i=0,1.

If the net trade x is proposed and accepted, the proposer's new endowment e(a0,t+1)=e(a0,t)+x and the responder's e(a1,t+1)=e(a1,t)-x.

Now we are ready to present the trading rule proposed in all bilateral meetings. The trade proposed is denoted by:

g(z0,z1)=argmax{-∑k≥2exp(-|xk|):  x∈B(z0,z1)}.

Denote by u*(c,p) the maximum utility that an agent with characteristics c can achieve over the budget set determined by his endowment and the prices p. We will show that if every agent behaves according to the specified strategies, almost every agent of characteristic c achieves a bundle (corresponding to the allocation f) that yields u*(c,p) in finite time.

Notice first, as in Gale (1986b), that if agents follow the specified strategies, it is not possible for an agent to increase his income as evaluated by the prices p. Next we will show that an agent a ends up at the bundle f(a) in finite time with probability 1. This will show that the proposed strategies are a strategic equilibrium. That is, given that there is no way to increase one's income, the proposed strategies induce a random path that takes each agent to his chosen maximizer f(a) over the budget set determined by e and p.

For each agent a and for prices p define the excess demand as follows (for convenience and given that the Walrasian prices p are fixed throughout, we shall drop p from the expressions below): φ(a,t)=f(a)-e(a,t), where e(a,t) are the holdings of agent a at round t. Notice that, given the strategies specified above, every agent travels along the frontier of his budget set which means that f(a) continues to be a utility maximizer for agent a.

As we said above, we shall distinguish between the behavior of commodity 1 and that of the others. The trading rule g is constructed so that the absolute value of the excess demand of every agent in all goods but 1 does not increase. On the other hand, good 1 serves to balance the budget whenever there is no pure coincidence of wants. Thus we define for each agent a the following number: β(a,t)=∑k≥2k(a,t)|. That is, for each agent a the statistic β(a,t) indicates the sum of absolute values of excess demands in all goods but 1 in round t. We will next show that over time the distribution of β(a,t) converges weakly in measure to a degenerate distribution concentrated on 0.

Recall that μ denotes the measure of characteristics in the economy, i.e., the measure of characteristics of all agents who are active in the market plus that of the agents who already left the market. The random matching process and the specified strategies lead to new distributions of characteristics at every round, and hence to new distributions of the statistic β(a,t). We shall concentrate on an arbitrary path determined by a particular realization of the different random variables at play (the coalitions that meet and the roles of each agent in each meeting). We show then that, along this path, the distribution of β(a,t) converges in measure to the degenerate distribution concentrated on 0.

The space of characteristics C at each round t is the Cartesian product of a fixed space of utility functions with +D×NI. The evolution of the economy is thus described by a sequence of measurable maps from the set of agents A to the set C. Given that the set of utility functions is fixed throughout the model, any Cauchy sequence of such measurable maps must converge to a measurable map from A to C. To see this, notice that, after having fixed the utility functions, the marginal of characteristics c on agents' endowments e allows us to consider a Cauchy sequence of integrable maps from A to +D×NI. Endowing this space of integrable maps with the topology induced by the supremum norm, it is easy to see that such a sequence converges to an integrable map into +D×NI as this is a complete space. Notice that the marginal of the measure μt on utility functions is constant. We can then abuse notation slightly and denote by μt round t's measure on the agents' endowments and not on characteristics. Thus, using Hildenbrand (1974, p.50) the sequence of measures t} is tight and has a convergent subsequence to μ*. Without loss of generality, suppose the sequence itself converges to μ*.

By the properties of the trading rule g, we must have that for a given constant τ>0, β(a,t)≥τμ(a,t) converges to 0 as time goes to infinity. To see this, we argue by contradiction. Suppose that the limiting measure μ* is not the one concentrated at 0. Since μ* is the limiting measure, it must be the case that the measure of agents trading positive amounts of goods when the distribution of β(a,t) is approximately mu;* must be arbitrarily close to 0: For all ε>0 there exists a T such that for all t>T we have that ∫[μt*]<ε. If μ* is not the one concentrated at 0, there must exist a positive measure of agents whose characteristics satisfy that φk(c)>0 for some good k. By Walras' law which holds at each step of this time path, there must also exist a positive fraction of agents whose characteristics satisfy that φk(c)<0. Since the matching process is random, there exists a positive probability that agents in these two situations will meet. Finally, given the trading rule g, these agents will trade at least in good k, which is a contradiction, i.e., there exists ε>0 such that for all T there exists t>T with ∫[μt*]>ε as g(z0,z1) stays bounded away from 0 for a positive fraction of meetings.

As for convergence in finite time, the arguments are identical to those in Gale (1986b, section 7).

6. Discussion

By using the insights of the theory of the core, this paper presents a model of decentralized trade through bargaining in coalitions of finite size. This allows us to obtain equivalence results among core, Walrasian and strategic equilibrium allocations for a wide class of large exchange economies, including non-differentiable non-convex preferences and indivisible goods.

Our results are robust to several extensions of the model. First, we could allow for any entry process (not necessarily one time entry) as long as the measure of the total entering population is finite. Second, different bargaining procedures in the coalitional meetings could be adopted: for example, veto power can be given only to those responders who are offered a non-zero trade vector. Third, we only need to assume that an agent's probability of meeting a coalition of size n be positive. In particular, we could assume that the probability of meeting a coalition of more than two agents be arbitrarily small and all our results would go through. Thus, Gale's model can be viewed as the "limit" of ours as the probabilities of multilateral meetings vanish. This poses the important open question of lower hemicontinuity of the equilibrium payoff correspondence, i.e., which of the extra assumptions made by Gale are really needed to obtain the result using only trade in pairs.

A separate dimension along which our results are more robust than the previous ones found in the literature is the class of economies to which they apply. We discuss this in length in the following paragraphs, especially comparing our results to the important works of Gale (1986a, b, c) and McLS (1991).

Existence of equilibrium Thanks to considering finite coalitions in the procedure, our paper yields the equivalence between strategic and Walrasian equilibria under essentially the same assumptions as those needed for the core equivalence theorem. Moreover, our assumptions also guarantee the existence of a Walrasian equilibrium, as opposed to Gale (1986a, b, c) and McLS (1991), which deal with open consumption sets.

Limited applicability of the previous models As discussed in the introduction, we regard the relaxation of differentiability as a crucial conceptual departure from Gale's and McLS's work. From an applied view-point, the differentiability assumption by itself that Gale (1986a, c) and McLS (1991) make is not very restrictive: many models in economics incorporate it in order to allow for a closed solution and for the performance of comparative statics exercises. However, the proofs of the above mentioned authors rely on additional strong assumptions, that exclude most applied models. Gale (1986a) assumes that for each utility function the support of the endowments compatible with it is the entire consumption set. This assumption excludes the possibility of a finite type economy. Gale (1986c), who assumes a finite number of types, uses a bounded curvature assumption, thereby excluding, for example, Cobb-Douglas utility functions on the non-negative orthant or its interior. McLS (1991) make either a bounded curvature assumption similar to Gale's (1986a) or a restriction on the equilibrium which seems to require an assumption similar to Gale's (1986a) on the primitives of the economy. In contrast, our model, which applies to very general economies, also applies to these standard cases.

Feasibility in and out of equilibrium We assume, like Gale (1986a, b, c), that the flow of agents entering the market constitutes an economy, i.e., they sum up to a finite measure. In addition, we also assume that short sales are not allowed. These two assumptions together ensure that the flow of agents out of the market is consistent with the feasibility constraint of the economy. Suppose, like McLS (1991), that the total measure of agents is finite, but short sales are allowed. In this case, nothing assures that feasibility is met. Consider an arbitrary assignment of bundles to agents, and the following strategies (that do not constitute an equilibrium in McLS's game with short sales). Each proposer asks for the bundle assigned arbitrarily to him and each responder accepts any proposal; agents leave the market as soon as they reach their assigned bundle. Clearly, these strategies guarantee that each agent will get with probability 1 the assigned bundle. The problem stays even if we restrict attention to the equilibria of their game. Indeed, the strategic equilibrium that McLS propose (pp. 1395-1396) to support a Walrasian equilibrium is a strategic equilibrium for any prices. That is, for an arbitrary price vector, their strategic equilibrium gives the outcome that every agent maximizes over the corresponding budget set, but the market clearing conditions may be violated. This casts doubt on the validity of such a model as a foundation of Walrasian outcomes, since the IOUs are eventually consumed by the agents. As we perceive market clearing conditions as an essential part of the Walrasian concept, we do not allow for short sales and adopt Gale's approach, which ensures feasibility in and out of equilibrium. See Dagan, Serrano and Volij (1998) for other related criticisms of the McLS model.

In the case where the sum of the measures does not constitute an economy, it is not clear what are the feasibility constraints. McLS's Theorem 3 deals with the case when the inflow and the outflow of agents have long run averages. Following this approach, we can define the flow of agents out of the market to be 'feasible' if it is consistent with the long run average of the inflow of agents. However, it is not clear to us how one can construct a model in which this kind of constraint is met in and out of equilibrium. Therefore, interpreting the result of RW (1985) as consistent with Walrasian allocations (as done by McLS's Theorem 3) is not sound: the outcome of their strategic equilibrium is consistent with a notion of feasibility, but behavior different from this equilibrium may violate the same feasibility notion.

Strict concavity and indivisible goods McLS (1991) note the restrictiveness of Gale's (1986a, b, c) assumption of strictly concave utility functions in a continuum setting. One should expect that the convexifying effects of large numbers could be helpful to relax this assumption. However, we believe that McLS's solution to the problem is inadequate and provide an alternative treatment of the issue. One difference between the underlying economy and the strategic model is that in the latter the outcome (at least for an individual agent) may be random and thus preferences on random outcomes must be specified. McLS do not make any assumption regarding the concavity of utility functions; instead, they allow for short sales, which enables them to prove that outcomes of the strategic equilibria are not random. As explained above, assuming short sales in this framework may be problematic. In addition, a separate shortcoming of their treatment of non-convexities is that they maintain the differentiability assumption, which precludes non-convexities arising from the existence of indivisible commodities.

Gale (1986a) uses the strict concavity assumption only to ensure that the introduction of lotteries does not enlarge the set of possible utilities of the agents. Thus, what is needed is a property of risk aversion in the aggregate. We impose a condition on the quasiconcave covers of the utility functions that ensures the sufficient degree of aggregate risk aversion. This assumption is compatible with having indivisible commodities as well as other kinds of non-convexities. Thus, our assumptions allow for a unified treatment of assignment markets à la RW (1985) and classical exchange economies à la Gale (1986a, b, c). We should stress that our assumption of aggregate risk aversion is sufficient to obtain Gale's results as well (of course, within his restrictive subdomain).


This appendix contains the proofs of Propositions 1 and 2.

Proof of Proposition 1 Let L be a lottery on allocations. We define EUa(L)=∫Fua(f(a))dL. We also define Ea(L)=&intFf(a)dL and h:A→ℜ+D∪I as the function that assigns to each agent a the bundle Ea(L). It is easy to see that h is integrable. Now let $φ(a)={x∈ℜ+D∪I:ua(x)≥ua(h(a))}. Clearly, ∫h(a)∈∫φ(a) since it is true for every a. Let ψ(a)={x∈X:ua(x)≥ua(h(a))}. It follows from the definition of u that ψ(a)=φ(a), where ψ(a) is the convex hull of ψ(a). Now consider ∫ψ(a). It follows from Liapunov's theorem that this integral is convex, and thus ∫ψ(a)=∫φ(a). Therefore, ∫h(a)∈∫ψ(a). Thus, there exists an allocation g such that ua(g(a))≥ua(h(a)) for almost all a∈A. It follows from the fact that all the covers u are concave that almost all agents weakly prefer the allocation g to the lottery L.

Proof of Proposition 2 Let L be a non-degenerate lottery over allocations. First it follows from Proposition 1 that there exists an allocation g that satisfies that ua(g(a))≥ua(h(a)) for almost all a∈A. Since the lottery is non-degenerate, there is a positive measure of agents such that each of them is not indifferent among almost all bundles in the support of L. Now for each agent a in this set, we can have two cases:

1. There does not exist k such that for L-almost all f∈F, ua(f(a))=k. In this case, it follows from almost strict concavity of u that ua(h(a))>EUa(L).

2. There existsk such that for L-almost all f∈F, ua(f(a))=k. Since the agent is not indifferent among almost all bundles, there exists a set of allocations that are assigned positive probability by L such that ua(f(a))>ua(f(a)). Thus, ua(h(a))=k>EUa(L).



"The markets which are best organized from a competitive standpoint are those in which purchases and sales are made by auctions ... Besides these markets, there are others, such as the fruit, vegetables and poultry markets, where competition, though not so well organized, functions fairly effectively and satisfactorily. City streets with their stores and shops of all kinds ---baker's, butcher's, grocer's, taylor's, shoemaker's, etc.--- are markets where competition, though poorly organized, nevertheless operates quite adequately... ".

(Walras, 1874, pp.83-84).
Osborne and Rubinstein (1990, chapter 6) and the references therein for earlier models of decentralized trade in pairwise meetings where each pair uses the Nash bargaining solution to split the gains from trade.
We will need an additional assumption beyond those needed for core equivalence to guarantee that the outcome of a strategic equilibrium is not a lottery over allocations. This extra assumption is weaker than Gale's strict concavity and is compatible with the presence of indivisible goods.
These assumptions are either uniformly bounded curvature or dispersed endowments. See our final section for details.
The problem of existence of such random matching processes is already present in models with only pairwise meetings. For possible treatments of this problem, see McLS (1991, footnote 4) and the references therein.
The arguments in the characterization theorem (Theorem 1) are entirely independent from this phase. However, its introduction simplifies greatly the proof of Theorem 2, which could be complicated due to the fact that our model allows for demand correspondences.
Alternatively, we could take the approach based on distributions like in Hart, Hildenbrand and Kohlberg (1974) instead of the name-based approach. We should then assume (like Gale (1986a, b, c), Osborne and Rubinstein (1990) and McLS (1991) that any two agents with identical characteristics and histories play the same strategy. This would enable us to employ the machinery developed by McLS (1991, section 3.3) in order to establish that for any given strategies the "state of the market" in round t in the sense of distribution of agents' characteristics is deterministic. See also Osborne and Rubinstein (1990, pp. 160-161), who show this for the finite type pure strategy case.

Nir Dagan / Contact information / Last modified: July 28, 1998.