%Paper: ewp-game/9503001
%From: m.agastya@ucl.ac.uk (Murali Agastya)
%Date: Thu, 09 Mar 1995 21:04:29 +0000

\documentstyle[12pt,emlines,bezier,a4]{article}
\input tcilatex 
\newtheorem{definition}{Definition} 
\newtheorem{corollary}{Corollary}[section]
\newtheorem{assumption}{Assumption}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{fact}{Fact}
\parskip=.06in 

 \begin{document} 
\baselineskip=18pt
\begin{titlepage} \title{An Evolutionary Bargaining Model} 
\author{Murali Agastya\thanks{ I thank Phil Reny, Arthur Robson and Myrna 
Wooders for helpful comments. Of course, the usual disclaimer applies.} \\ 
Center for Rationality and \\ \hspace{.4 in} Interactive Decision Theory \\ 
Feldman Building \\ Hebrew Univ., Givat Ram \\ Jerusalem 91904 \\ ISRAEL \\ 
\vspace{.12 in} Email: murali@math.huji.ac.il}

\date{May 20, 1994}
 \maketitle

\begin{abstract} 
Varying quantities of a single good can be produced using at 
least two and at most $n$ factors of production. 
The problem of allocating the surplus among the factors is studied in a 
dynamic model with adaptive behavior. Representatives for the factors (called 
players) make wage demands based on precedent and ignorant of each other's 
utilities for this good. Necessary and sufficient conditions are provided 
under which the long-run equilibria coincide with the core allocations.  
A global convergence result is proved to show that players do learn to reach a
core allocation in the long run. 
Moreover, allowing for the possibility of mistakes by the players, all the 
{\em stochastically stable outcomes}  are characterized.  The main result 
shows that in the limit, these stable allocations  for a particular set of 
players converges to the allocation that maximizes the product of all the 
players' utilities over all core allocations. 
\end{abstract} 
\thispagestyle{empty} 
\end{titlepage} 

\section{Introduction}


The problem of allocating the surplus among various factors of production,  
or equivalently characteristic function bargaining  has been 
been studied in a variety of non-cooperative and/or axiomatic models.
While there can hardly be anything  indeterminate in the predictions of
axiomatic 
models, the story is quite different for the non-cooperative models with three
or more players. Many natural adaptations of the Rubinstein (1982) result in 
a variety of folk theorems\footnote{
See Sutton(1985) for a survey.
See also Perry and Reny (1991), Serrano and Vohra(1993), Chatterjee {\em et.al}
(1993),
Winter(1992).}. A problem of considerable interest then is as to which of
the many equilibria is (are) most likely to be played.

Analysis of strategic interaction places great demands on the knowledge and
rationality of the players. These demands are magnified when there are
several possible equilibria to choose from. Although it is true for more
general games, this problem is especially severe in bargaining situations 
where there are several pareto-optimal equilibria\footnote{ For example, in
Perry and Reny 
(1991), every core allocation is a subgame-perfect equilibrium of the 
negotiation process described therein.}. For, there is a paucity of 
eductive explanations to select between several pareto-optimal equilibria. 
Consequently, and only recently, the study of explicit dynamic learning 
processes through which agents learn the way to play a game has commanded 
greater attention. The idea is to see which equilibrium, if any, the players 
will learn to play under simple rules of behavior and minimal assumptions on 
their knowledge. 



 In this paper, I study the allocation problem in the 
context of a simple dynamic learning model. At each date a single good can be 
produced. 
The production possibilities in a period 
are described by a characteristic function $f$ defined on the class of all 
subsets of a finite set of factors. Here, $f(S)$ is the quantity of a single 
output that can be produced using the resources of the subset  $S$ alone.  At 
each date, one representative for each factor, henceforth referred to as a 
player, demands a certain amount of the surplus as a wage for his services.  
Demands are made simultaneously  and players are committed to these demands 
for the period. There is no assumption of common knowledge of players' 
utilities. Players use statistical data from a random sample from  recent 
history to demand a wage for the current period. 
Demands are made only in integral multiples of $\delta$, a smallest money 
unit. Moreover, players are myopic and play a best response by maximizing the 
one period expected utility. The best response rules of the above dynamic 
process, induce a stationary Markov Process referred to as Evolutionary 
Bargaining Process (EBP). This dynamic process itself is due to Young(1993a) 
and is a variation  on fictitious play. 



There is a one to one correspondence between the set of absorbing states of 
the EBP, referred to as conventions,  and the Strict Nash equilibria of a
simultaneous move demand commitment game. In this game, 
players simultaneously demand a part of the 
surplus and are committed to their demands. This is of course the original 
Nash demand commitment game. 
The difference and difficulty 
arises from the fact that unlike in Nash's original demand game where a pie is
to be split between several players, here players make demands over a general 
characteristic function. Consequently a given set of demands can perhaps be met
in several coalitions. This uncertainty regarding coalition formation coupled 
with the fact that we are dealing with {\em individual demands } and {\em not 
proposals directed towards coalitions} makes the problem interesting and 
somewhat more complex. In section~\ref{demandgame}, the game is analyzed. It 
is shown that if the technology displays increasing returns to scale in the 
{\em number of factors \footnote{Notice that this does not necessarily require
increasing returns in the extent of use of particular factor(s)}}, 
then core allocations coincide with the (strict) Nash equilibria. Needless to 
say, certain assumptions regarding coalition formation are also required. 

Section~\ref{dynamicprocess} studies the dynamics of the EBP. 
Theorem 1 presents sufficient conditions under which the only persistent 
states are absorbing. In other words, under the hypotheses of Theorem 1, 
players learn to reach a core allocation regardless of the starting point. 





Section~\ref{ssb} then studies the dynamics of the EBP by allowing for the
possibility of the players making {\em mistakes}. Players play a best
response with a very high probability but with a small but positive
probability, they commit errors. Consequently there are no longer any
absorbing states. It is possible to move from one convention to another.
However, some conventions are harder to displace than others. When the
probability of making errors is small, those conventions that are
hardest to displace that will be observed most often. These conventions are
referred to as {\em Stochastically Stable Conventions}, hereafter SSC, and
constitute the main notion of refinement of equilibria.

Theorem 3 characterizes the set of all SSCs.  There may be several such 
allocations. However, (Theorem 4) when the 
size of the smallest money unit $\delta$ shrinks to zero, the allocations in 
the SSCs,  for a particular subset of players, converge to the allocation that
maximizes the product of all the players' utilities over core allocations, a 
seeming generalization of the Nash Bargaining solution.  For the three player 
case however, one has uniqueness. 

Young (1993b) is the closest relative of this paper. Young considers a very
special technology and restricts attention to the case of two players. With
three or more players, the possibility of cycles in the dynamic process
makes analysis here much more complex. To obtain a tractable proof, I assume 
that players only make 'small mistakes'. But this in turn creates a different
technical problem. The perturbed EBP is no longer strongly ergodic. Since
the refinements in models that study naive behavior \footnote{
See for e.g., Foster and Young (1990), Kandori {\em et.al} (1993), Young
(1993a and 1993b)} are based on the convergence properties of the invariant
distributions of the perturbed process, their techniques are not immediately
applicable.


Binmore (1987) and Carlsson (1991) analyze perturbations of the original
Nash demand game and study the properties of non-cooperative equilibria of
the perturbed game as the perturbations become very small. They show that
the Pareto optimal Nash equilibria of the perturbed game converge to the
original Nash Bargaining solution. The model presented below (as does Young
(1993b)) differs from the above models in that they presuppose the
equilibrium of both the original as well as the unperturbed game. In this
model on the other hand, players reach  long-run equilibria as the
likelihood of mistakes becomes very small, without any knowledge of the
utilities of other players.

The paper is organized as follows. Section 2 presents the one shot demand
game and characterizes the set of equilibria. Section 3 studies the EBP.  
Section 4 concludes with a few examples.  Most formal proofs appear in 
Appendix A and Appendix B. 

\section{ The Demand Game}~\label{demandgame}
Let $N=\{1,2,\ldots n\}$ denote the set of factors of production. I will 
assume $n \geq 3$. The
technological possibilities are described by a non-negative function $f$
defined on the class of all coalitions of $N$. By way of interpretation, 
$f(S)$ is the total quantity of a single good that can be produced using the
services of the factors in $S$ alone. I will assume that the function is
normalized so that $f(i) = 0$ for all $i \in N$. 

Let $\Delta$ be the  half open interval $(0,f(N)]$. One representative for each
factor of production demands a wage from $\Delta $.  We will 
refer to these representatives as players. Let $\omega_i$ denote a typical 
wage demand of player $i$. Given a vector of wage demands $W$, let $W(S)$ 
denote the total wages demanded by the coalition $S$ . The demands of $S$ are 
said to be {\em \underline{compatible}} at $W$, if $W(S) \leq f(S)$. The 
demands are {\em \underline{strictly} \underline{compatible}} if the 
inequality is strict.  Let $\beta(W)$ ( $\hat{\beta}(W)$ ) denote the set of
all coalitions in 
whose demands are compatible ( strictly compatible). 

Players are assumed to make their demands simultaneously and are committed to 
their demands.  A 
player' demand is not met unless his services are used.  By the assumption of 
commitment, a player cannot have his demand met unless there is a coalition 
$S$ to which he belongs and the demands of the coalition as a whole are 
compatible. However, a particular  $W$ may be compatible in  several
coalitions. 
Thus 
even under the reasonable hypothesis that only compatible coalition(s) will 
eventually form, there is still some uncertainty whether a player's demand 
$\omega_i$ will be met. To capture this uncertainty, let 
$p_i(\omega_i|W_{-i})$ denote the probability belief that player i's demand 
$\omega_i$ is met if others demand $W_{-i}$.  This probability may be thought 
of as the result of an exogenous matching process. By allowing for $p$ to 
depend on $i$ and making assumptions directly on the $p_i$, we allow for 
possibility a certain amount of subjective uncertainty on the part of the 
players regarding this matching process. The following will be assumed of the 
matching process (or beliefs) at the very outset.           


\begin{assumption}~\label{as1} 
 Fix $W$. Then for each $i \in N$, 
\begin{enumerate}
\item If $i$  is not the member of \underline{any} coalition whose demands 
are compatible, then $p_i(\omega_i|W_{-i}) =0$. 
\item For all $\omega > \hat{\omega}$, $p_i(\hat{\omega}|W_{-i}) \geq
p_i(\omega|W_{-i}))$. 
\end{enumerate}
\end{assumption} 

Assumption~\ref{as1} is natural  enough and requires no  further comment.
Now, assuming that a player obtains zero if his demand is not met, the 
expected utility of player $i$ if he demands $\omega_i$ when others have
demanded 
$W_{-i}$ is \begin{equation} \label{nasheqblm}U_i(\omega_i|W_{-i}) =
p_i(\omega_i|W_{-
i})v_i(\omega_i) + [1-p_i(\omega_i|W_{-i})]v_i(0) \end{equation} where the
function 
$v_i$ determines the utility derived from consuming $\omega_i$. I will assume
that 
$v_i$ is a strictly increasing, continuously differentiable and concave 
function. Finally, assuming that players maximize expected utility  and 
normalizing $v_i(0) = 0$, we have the following usual definition of a strict 
Nash equilibrium: 

\begin{definition}
A vector of wage demands $W^*$ is a strict Nash  equilibrium iff
$$
U_i(\omega_i^*|W_i^*) > p_i(\omega_i|W_{-i}^*)v(\omega_i). 
$$
if $\omega_i^* \neq \omega_i$, for all $i \in N$.
\end{definition}

In this paper, Nash equilibrium will always be taken to mean the equilibrium
defined above. 

\begin{definition}
A vector of wage demands $W$ belongs to the core of the technology $f$, 
\begin{enumerate}
\item  $f(N) = W(N)$. {\em ({\em Feasibility})} 
\item  For all $S \subseteq N$, $W(S) \geq f(S)$. {\em ({\em No blocking sub-
coalitions.})}
\end{enumerate}
Let ${\cal C}(f)$ denote the set of all core allocations. 
\end{definition}

At a first glance it seems somewhat intuitive that the core and the set of
Nash equilibria are related. However, recall that in this model, players
make demands and not proposals directed towards a particular coalition. When
a player makes a proposal, not only does he seek a payoff for himself, but
also specifies a payoff for a subset of other players as well. Hence,
implicitly he also suggests which coalition is to form. In the present
model, however, players independently and simultaneously make their demands.
Hence it it possible that individual players may make demands that are not 
pareto-optimal. At this point it may not pay for any of them to deviate by 
responding with higher demands as it will, by Assumption 1, will reduce the 
likelihood with which it is met. Similarly, it may also be the case that the 
players may demand wages much higher than what the grand coalition can afford 
but expect to obtain these in smaller coalitions. 

\begin{example}
{}~\label{eg1a}{\em Let $N = \{1,2,3\}$, $f (ij)=1$ for all $i,j$ and $f
(123)=2$.  Let $v_i=v$ for all $i$. Assume that the matching process is 
such that for a given $W$, all coalitions in $\beta(W)$ are equally likely. 
It may be checked, that this matching process is consistent with 
Assumption 1. Now consider 
$W^*=(\frac{1}{2},\frac{1}{2},\frac{1}{2})$.  Since the demands of all the 
three two player coalitions are compatible as well as those of the grand 
coalition, the payoff of player $i$ on demanding $\frac{1}{2}$ at $W^*$ is 
\begin{equation}
U_i(\frac{1}{2}|W^*_{-i}) = \frac{3}{4}v(\frac{1}{2}) 
\end{equation}}

{\em Now consider a deviation $\hat{\omega_1}$ by $1$. Clearly, since the set
of 
compatible coalitions does not change, a demand strictly less than $1/2$ is 
strictly dominated by $1/2$. Furthermore, any demand $\hat{\omega} > 1/2$, 
is strictly dominated by a demand of 1, unless $\hat{\omega}=1$. 
Indeed, if he responds with $1$, the new set of demands are compatible in the 
$\{2,3\}$ coalition and $N$. Since each is equally likely to form, the payoff 
is 
\begin{equation} 
U_i(1|W^*_{-i}) = \frac{1}{2}v(1)
\end{equation}} 

{\em For an appropriately concave $v$, the demand  $1$ can be seen to be 
strictly dominated by $1/2$. Since all players are symmetric, we have shown 
that on the one hand $(1/2,1/2,1/2)$ that is not in the core is a Nash 
equilibrium while on the other hand, $(1,1/2,1/2)$, an element of the core is

not a Nash equilibrium. } \end{example} 

The above example demonstrates two things. First, there
is no immediate relation between core allocations and Nash equilibria.
Second, Assumption 1 is not sufficient to rule out rather unintutive
outcomes. Note that in the above example, every feasible coalition is assumed 
to form with a strictly positive probability. Thus, the problem is not one of 
beliefs which assign probability zero to coalitions that can form. In the 
example, players believe that the two player coalitions form although no 
player is "hurt" by the formation of the grand coalition. Since the players 
are assumed to be committed to their demands, it does not seem unreasonable to
assume that ties will be broken if favor of the larger coalition. Assumption 2
below is a weaker statement of this intuition. 

\begin{assumption}
\label{as2} Fix $W$. Suppose that there is a set $S^*$ such that
\begin{itemize}
\item The demands of $S^*$ are compatible, 
\item For every coalition $T$ whose demands are compatible, the demands of 
$T \cup S^*$ are also compatible. 
\end{itemize}
Then, $p_i(\omega_i|W_{-i}) =1$ for all $i \in S^*$. 
\end{assumption}

The demands of $S^*$ are compatible. However, the demands of a different 
coalition $T$ may also be compatible and this might in fact require the 
services of a subset of players in $S^*$. 
Assumption~\ref{as2} then requires that if it never "hurts" anyone to
accommodate 
the demands of the remaining players in $S^*$, then all the players in $S^*$ 
will be matched. 


\begin{proposition}
Under Assumption~\ref{as1} and Assumption~\ref{as2}, every element of the core
is a Nash equilibrium. 
\end{proposition} 

{\bf Proof: }Let $W^*$ be an element of the core. Hence $W^*(N) = f(N)$.
Take $S^* = N$ in Assumption 2. It then follows that $p_i(\omega_i^*|W_{-i}^*)
=
1 $ for all $i \in N$. A deviation by any player $i$ by demanding $\omega_i >
\omega^*_i$, implies the demands are not compatible in any coalition
containing
him. Consequently, $p_i(\omega_i|W_{-i}^*) = 0$. Hence, it is not profitable
to
ask for more than $\omega^*_i$.

The only reason that a player may ask for less than $\omega^*_i$ 
if it can be met with a higher probability than $\omega^*_i$. But since $
p_i(\omega^*_i|W^*_{-i}) = 1$, $\omega^*_i$ is the unique best response.
$\Box$

The following example shows that the converse of Proposition 1 does not hold 
without further restrictions.

\begin{example}
\label{eg1}
{\em Let $f (12)=f(13)=300, \ f (123)=302$.  Assume that $v_i(\omega) =\omega$.
 Under the 
hypotheses of Proposition 1, all core allocations are Nash equilibria.  In any
core allocation, neither player $2$ nor $3$ gets more than $2$. 

Now note that for all $\omega > 4$, all demands of the form $(300-\omega,
\omega,\omega)$ 
are compatible in exactly the $\{1,2\}$ or $\{1,3\}$ coalitions. Assume that 
each of these are equally likely to form.  Again, this is consistent 
with Assumptions 1 and 2. It is straightforward to check that the above demands
constitute a 
Nash equilibrium.  Indeed, the highest payoff of either player 2 (or 3) can 
get from deviation is $2$ which is strictly smaller than his expected 
payoff with the current demands. } 
\end{example} 



\begin{proposition}
Under Assumption~\ref{as1} and ~\ref{as2}, if the technology is convex, i.e., 
$$
f(S) + f(T) \leq f(S \cup T) + f(S \cap T) \mbox{\hspace{0.5 in} for all $S,T
\subseteq N$.}
$$
then a Nash equilibrium demand vector $W^*$ is in the core of the technology.
\end{proposition}


\proof The proof involves showing that if the demands of a  certain coalition 
are strictly compatible at $W$, then it is possible to find a coalition 
$S^*$ such that whenever $T$ is compatible, $S^* \cup T$ is strictly 
compatible.  Thus, a player in this coalition can increase his demand by a 
positive amount and yet ensure that it is met with probability one, by virtue 
of Assumption~\ref{as2}. 
Hence, at a Nash equilibrium, no coalition's demands are strictly 
compatible. However, for each player, there must be at least one coalition in 
which his demands are compatible. This is sufficient to now conclude that the 
demands must be feasible in the grand coalition.  Details appear in Appendix 
A. 

\section{ Dynamic Adjustment Process: Adaptive Play}~\label{dynamicprocess}

In this section I describe a dynamic
process. I consider the case where the
demand game of section 2 is played repeatedly at discrete dates. Players are
assumed to be myopic, have a bounded memory and make demands based on
precedent.

More precisely, time is denoted by, $t = 1,2, \ldots $. At each date $t$,
players simultaneously demand a wage. To steer clear of the complications
that arise from infinite dimensional strategy spaces, the strategy spaces
are discretized. Towards this end, I first assume that each $f(S)$ is a
rational 
number, say $p_S/q_S$. Let $M = \prod_{S \subseteq N} q_S$.  For a given 
positive integer $p$, the number let $\delta = 1/ (10^pM)$ is the 
precision\footnote{ The dependence of $\delta$ on $p$ is suppressed for 
conserving on notation.} 
of the model. Players will be assumed to demand in integral multiples of 
$\delta$.   Let $\Delta_{\delta}$ denote the subset of $\Delta$ consisting of 
integral multiples of $\delta$.  A central concern of the paper is the behavior
of 
model as $\delta \rightarrow 0$ (or equivalently large values of $p 
\rightarrow \infty$). 

Let ${\cal C}_{\delta}(f)$ denote the set 
of core allocations with each $\omega_i \in \Delta_{\delta}$. It is important 
to note that with the above method of discretization, ${\cal 
C}_{\delta}(f)$ can be defined exactly like ${\cal C}(f)$. That is, we do not 
encounter problems of demands in ${\cal C}_{\delta}(f)$ being strictly 
compatible in coalition because players are allowed to demand from 
$\Delta_{\delta}$ only. 

In the sequel, $\omega_i \in \Delta_{\delta}$ unless specified otherwise. 

Let $\omega_{it}$ and $W^t$ denote a typical demand of a player $i$ and the
vector of wage demands at date $t$ respectively. The complete {\em history}
up to and including period $t$ is a sequence of demands $W^1, W^2,\ldots W^t$.
Consider a typical player $i$ who has to make a demand at date $t$. Players
have no knowledge or a prior regarding the utility of the other players. To
determine an optimal response, they have to rely on the historical records.

Fix $\alpha_1 \leq \alpha_2 \leq \dots \alpha_n$ where each $\alpha_i$ is a 
rational number. An integer $m$ is said to be {\em admissible} if $\alpha_im$ 
is an integer for all $i$. Let $k_i = \alpha_im$

Fix an admissible $m$. Player $i$ samples at random  a fraction of at most
$\alpha_i$  of the last $
m $ records, {\bf s}$= (W^{t-m+1},W^{t-m+2},\ldots W^t)$. It is important
for this model that every subsample at most of size $\alpha_im$ is sampled 
with a positive probability. However one need make no assumptions on the 
relative probabilities with which different parts of the history are sampled. 
The variable $\alpha_i$ is a measure of player i's {\em information}. 


Recall that the history up to date $t$ consisted of only past demands. In
particular, the history was silent as to which coalition has formed when
similar demands were in place. Consider a player who has picked the sample
$\sigma_i = (W^1,W^2,\ldots
W^{k_i})$. Player $i$ believes that his demand $\omega$ is met with probability
$F_i(\omega|\sigma_i)$ where 
$$
F_i (\omega|\sigma_i)=\frac{1}{k_i}[p_i (\omega|W^1_{- i})+p_i
(\omega|W^2_{-i})+ \dots
+p_i (\omega|W_{-i}^{k_i})]. 
$$

The expected payoff of player $i$ upon demanding $\omega$ following the sample
$\sigma_i$ is 
\begin{equation}
\label{convention}F_i (\omega|\sigma_i)v_i(\omega)
\end{equation}

Hence if the state at time $t$ is {\bf s}, the wage demand at $t+1$ must
satisfy 
\begin{equation}
\label{br}\omega_{i(t+1)} = \arg\max F (\omega|\sigma_{it})v_i(\omega)
\end{equation}
for some sample $\sigma_{it}$ of size $k_i$ from the state {\bf s}. If there
are several values of $\omega$ that solve Eq. (~\ref{br}) above, then each of
them is
played with a strictly positive probability.

The above model is similar to fictitious play in the sense that players make
their demands naively based on empirical distributions. Unlike in fictitious
play, where a player samples the entire history, in the above process, a
player samples only a fraction of the most recent history. This process has
been termed {\em adaptive play} by Young (1993a). Since players are
sophisticated enough to actually play a best response at each date, it seems
that the above behavioral process, as is fictitious play, makes sense only
if one assumes that players do not know each other's utility functions.

The response rules of the players (determined by Eq.~\ref{br}), determine a
stationary Markov chain. The state space $\Omega$ consists of
all sequences {\bf s} of length $m$. Each entry of {\bf s}, is a vector of
wage demands by the agents. 

Let $p^*_i (\omega_i|\mbox{{\bf s}})$ denote the probability with which player
$i$ 
demands $\omega_i$ in the state {\bf s}. For each $i$, $p^*_i$ is a best
response 
distribution, i.e., $p^* (\omega_i| \mbox{ {\bf s}})>0$ iff $\omega_i$ solves 
equation~\ref{br} for some sample $ \sigma_i$ in {\bf s}. 

For a state {\bf s}$= (W^1, W^2, \ldots W^m)$, a state {\bf s$^{^{\prime}}$}$
= (W^2,W^3,\ldots,W^m,W)$ is said to be its successor. The probabilities are

$$
P^0_{\mbox{{\bf ss$^{^{\prime}}$}}}= \left\{
                           \begin{array}{ll}
                            \prod_{i \in N}p_i^* (\omega_i|\mbox{{\bf s}}) &  
                           \mbox{if {\bf s$^{'}$} is a successor of {\bf s}} \\
                           0 & \mbox{otherwise.}
                           \end{array}
                           \right.
$$


Let $P^0$ denote the matrix of the above transition probabilities. As in
Young (1993b), the above Markov process, with the state space $\Omega$, and
transition probability matrix $P^0$ is said to be an {\em evolutionary
bargaining process} ( EBP) with memory $m$, precision $\delta$,
information parameters $\{\alpha_i\}$ and best reply distributions
$\{p^*_i\}$.

\subsection{ Conventions}

\begin{definition}
{\em (Convention)} A state {\bf s} is said to be a convention iff
it is an absorbing state of the evolutionary bargaining process, {\em i.e.,} 
$P^0_{\mbox{{\bf ss}}} = 1$.
\end{definition}

{}From a given state, there is a positive probability of reaching only an
immediate successor. Thus, if {\bf s } is a convention and is the state at
time $t$, then {\bf s } is the state at time $t+1$ as well. For this to be
true, it is clear that {\bf s } must be a sequence of $m$ identical demands.
Now, let {\bf w} denote the state in which each entry is the vector of
demands $W$. Suppose that the process is in state {\bf w} at time $t$. Then
regardless of which sample player $i$ picks, the probability with which his
demand will be met is given by 
\begin{equation}
F_i (\omega|\sigma)=p_i (\omega_i|W_{-i}) 
\end{equation}

An easy application of Eqs.~\ref{nasheqblm}, \ref{convention}, ~\ref{br} and
yields Proposition 3 below.

\begin{proposition}
A state {\bf w} is a convention iff  $W$ is a Nash equilibrium of
the demand game.
\end{proposition}

Proposition 3 identifies the isomorphism between the conventions and Nash
equilibria of the one shot demand game. Once the players reach a convention,
they are locked into playing the game in a particular way. Thus, by
establishing the global convergence from an arbitrary initial state to a
convention, we describe a particular way in which players learn to play the
Nash equilibrium of the demand game. This is the object of the next
subsection.

\subsection{Convergence of the EBP}

In a Markov Process the set of all aperiodic states are either transient or
persistent. If the set of all persistent states are absorbing, then the EBP
converges from an arbitrary state to some absorbing state, with probability 
one. Theorem~\ref{thm1} below presents sufficient conditions under which the 
only persistent states are conventions. 

\begin{theorem} 
\label{thm1} Suppose that $\alpha_i \leq \frac{2}{(n^2-n+4)}$ for all $i$. 
Then the EBP converges with probability one to a convention.
\end{theorem}

It is useful to point out that the bound in the Theorem is only a sufficient 
condition that is independent of $f$. For particular cases it is possible to 
give a much sharper bound. For example, for the standard Nash Bargaining game 
where $f(N) = 1$ and $f(S) = 0$ if $S \neq N$, $\frac{k_i}{m}\leq \frac{1}{3}$
is 
sufficient. The same bound is also sufficient for the three player case with 
an arbitrary $f$. This is proved below. However, for all subsequent results 
I assume that  the hypothesis of Theorem 1 is met.  The proof of the general 
case appears in Appendix B. 


\proof Assume, for ease of exposition, that $\alpha_i=\alpha \leq 1/3$ for all
$i$. Let
the process be in state {\bf s} at date t. Let $\sigma$ denote the last $
k$ elements of this state. Let $W^1$ denote a best-response vector to the
sample $\sigma$. Since every sample of size $k$ has a positive probability
of being sampled, there is a positive probability of observing $W^1$ at date 
$t+1$. In fact, there is a positive probability of observing a run of $W^1$
between $t+1$ and $t+k$. If {\bf w$^1$} is a convention, we are done. For,
between $t+1$ and $t+2k$ all the players will sample the records containing $
W^1$ alone and respond with $\omega^1_i$. Hence there is a positive probability
$
p $ of reaching a convention in $m+2k$ periods. So the probability of not
reaching a convention in $r (m+2k)$ periods at most $(1-p)^r$, which goes to
zero as $r \rightarrow\infty$. Suppose that $W^1$ is not in the core but is
compatible in at least one of the three two player coalitions say $\{12\}$.
Then, between $t+k+1$ and $t+2k$, there is a positive probability that
players 1 and 2 will continue to sample $\sigma$, while player three will
sample the records consisting of $W^1$ alone. His best response \footnote{
It may be verified that since the technology is convex, $f (123)-\omega_i$ is
not
feasible in either of the smaller coalitions that contain player 3.}, by
virtue of Assumption~\ref{as2} is $f (123) - \omega_1 - \omega_3$. Hence,
between
period $t+k+1$ and $t+2k$, there is a positive probability of seeing a run
of $W^2= (\omega_1,\omega_2,f (123)-\omega_1-\omega_2)$.

It is useful to note that until now we needed a history of length at most $
3k $. From now on will make use of samples of size $k$ that appear from
dates $t+k+1$ onwards.

Now between $t+2k+1$ and $t+3k$, there is a positive probability all the
three players will sample demand $W^2$. The best response of player $3$
continues to be $f (123)-\omega_1-\omega_2$ while player $1$ and player $2$
must
demand $f (12) - \omega_2$ and $f (12)- \omega_1$ respectively. Hence we will
see a
run of $W^3= (f (12)- \omega_2,f (12)-\omega_1, f (123)-\omega_1-\omega_2)$ for
$k$ periods with
a positive probability.

Between $t+3k+1$ and $t+4k$, there is a positive probability of players 2
and 3 continuing to sample demands of $W^2$ alone while player 1 samples $
W^3 $. The best responses of players 2 and 3 remain unchanged while that of
player 1 is now $\omega_1$. Hence, there is a positive probability of seeing a
run of $W^4= (\omega_1,f (12)-\omega_1, f (123)-\omega_1-\omega_2)$.

Finally, there is a positive probability of all three players sampling the
most recent $k$ records consisting of $W^4$ alone. The best response of
players 1 and 2 continue to be $\omega_1$ and $f (12)-\omega_1$ respectively
while
player three must now demand $f (123)-f (12)$. It may be verified that the
demands $W^5= (\omega_1,f (12)-\omega_1,f (123)- f (12))$ is an element of the
core.
Now we repeat arguments similar to those found in the first paragraph of
this proof to conclude that we the EBP converges with probability one to a
convention if the information is less than or equal to $1/3$.

The only other case to consider is when $W^1$ is feasible and is strictly
compatible in the grand coalition but is not compatible in any of the
smaller coalitions. In this case, it is clear that $W^2$ above is in the
core.



\subsection{ Stochastically Stable Conventions}

\label{ssb}

This section studies the same dynamic process as in the previous section but
allows for the possibility of players making  mistakes, much in the spirit of
the models in Kandori, et. al (1993), Young (1993a) and Young (1993b). The aim
of this section is to introduce the notion of stochastic stability and provide
a characterization of such states. I start with a few definitions. 
Fix the sample sizes $k_i$ and the memory $m$.

\begin{definition}
{\em (Mistake)} Suppose that the EBP is in state {\bf s}$=
(W^{t-m+1},W^{t-m+2},\ldots,W^{t})$ at time $t$ and {\bf s$^{^{\prime}}$}$=
(W^{t-m+2},W^{t-m+3}, \ldots W^t,W)$. The transition {\bf s} to {\bf s$
^{^{\prime}}$} is said to involve exactly one mistake, if there is exactly 
one player, say $i$, for whom there is no sample in {\bf s} of size $k_i$ for 
which $\omega_i$ is a best-response, i.e., $p_i^* (\omega_i|\mbox{{\bf s}})=0$.
 \end{definition} 

Clearly  the number of mistakes involved in a transition from a state to its
successor 
is between zero and $n$, depending on the number of players that have made 
errors.

Suppose that the probability with which player $i$ makes a mistake is given
by $\epsilon \lambda_i >0$. Conditional on the fact that player i has made a
mistake, let $q_i (\omega_i|\mbox{{\bf s}})$ be the probability with which he
demands the wage $\omega_i$ in state {\bf s}. Clearly, $q_i$ is different from
$
p^*_i$. The parameter $\epsilon$ is the absolute probability with which
players make mistakes and $\lambda_i/\lambda_j$ is the relative probability
of players $i$ and $j$ making mistakes. The event that player $i$ makes a
mistake is assumed to be independent of the event $j$ makes a mistake.

Now suppose that the process is in state {\bf s} at time $t$. The
probability that exactly the members in the coalition $S$ make mistakes is $
\epsilon^s (\prod_{i\in S }\lambda_i) (\prod_{i \not\in S}
(1-\epsilon\lambda_i))$. Conditional on this event, the transition
probability of moving from a state {\bf s} to a state {\bf s$^{^{\prime}}$}
is

$$
Q_{ss^{^{\prime }}}^S=\left\{ 
\begin{array}{ll}
\prod_{i\in S}q_i(\omega_i|\mbox{{\bf s}})\prod_{i\not \in S}p_i^{*}(\omega_i|
\mbox{
{\bf s}}) & \mbox{ if {\bf s$^{^{\prime }}$} is a successor of {\bf s}} \\  
& \mbox{and the demands to the far right are $W$} \\ 
  &  \\
0 & \mbox{otherwise.} 
\end{array}
\right. 
$$

If none of the players make mistakes, then the transition probability of
moving from state {\bf s} to a state {\bf s$^{^{\prime}}$} is given by the
earlier transition probabilities $P^0_{ss^{^{\prime}}}$. This event has the
probability $\prod_{i =1,2,3} (1-\epsilon\lambda_i)$.

Allowing for the possibility of mistakes, we now obtain a new Markov process
with the same state space $\Omega$ as before but with the transition
function: 
$$
P^{\epsilon}_{ss^{^{\prime}}}= \left (\prod_{i\in N} (1-
\epsilon\lambda_i)\right)P^0_{ss^{^{\prime}}} + \sum_{S \subseteq
N}\epsilon^{|S|} (\prod_{i\in S }\lambda_i) (\prod_{i \not\in S}
(1-\epsilon\lambda_i))Q_{ss^{^{\prime}}}^S. 
$$

Let $P^{\epsilon}$ denote the above matrix of transition probabilities. In
most models similar to the one presented here, including Kandori, et. al.
(1993) and Young (1993a) and Young (1993b), it is assumed that when players
make mistakes, every feasible strategy is played with a strictly positive
probability. Mistakes then, constantly perturb the process away from a
convention. Now there are no absorbing states. However, since the transition
probabilities of the perturbed process converge to those of the unperturbed
process as $\epsilon$ converges to zero, for small values of $\epsilon$, the
perturbed process continues to be attracted to conventions, without actually
settling down. Which of the conventions that the process stays at for the
most part depends on the number of mistakes that are required to move it far
enough to a state from which it would gravitate toward a different another
convention. Hence, in the long run, if when the probability of mistakes is
very small, the convention that is observed most of the time will be the one
that requires the largest number of mistakes to displace.

The asymptotic (or long run) behavior of a Markov Process is captured
completely by its invariant distributions. When one assumes that there is a
positive probability of {\em every} strategy being played, the perturbed
process is irreducible. It is easy to show that each of the states is
aperiodic as well. Hence there is a unique invariant distribution $
\mu^{\epsilon}$ for the perturbed process, for each $\epsilon > 0$. For a
state {\bf s}, $\mu^{\epsilon}_s$ is the limit of the the relative frequency
with 
it is  observed in the first $t$ periods as $t \rightarrow \infty$. Since
the invariant distributions (perhaps along a subsequence), converge to the
invariant distribution of the unperturbed process, the conventions that are 
observed most often, when the probability of mistakes is small, are those in 
the support of the limit of the invariant distributions of the perturbed 
process (which is of course an invariant distribution of the unperturbed
process).   
This motivates the following refinement of the set of conventions, first
introduced by Foster and Young (1990).

\begin{definition}
{\em (Stochastically Stable Convention)} A convention {\bf s} is
stochastically {\em stable} if $\lim_{\epsilon \rightarrow
0}\mu^{\epsilon}_{s}$ exists and is positive. A state is strongly stable, if 
$\lim_{\epsilon \rightarrow 0}\mu^{\epsilon}_{s} =1$.
\end{definition}

Identification of the SSC(s) is considerably simplified by a certain 
equivalence theorem initially due to Friedlin and Wentzell (1984) and adapted 
for finite processes by Young (1993a). In order to introduce this, certain 
definitions are required. 

\begin{definition} {\em ({\bf w-}tree) } Fix a convention {\bf w}. A {\bf 
w}-tree is a directed graph with the set of conventions as its vertices such
that from 
each convention {\bf w$^{'} \neq$ w}, there is a unique path directed to {\bf 
w } and there are no cycles. 

\end{definition} 

\begin{definition}
{\em (Resistance)} Let {\bf s$^{^{\prime}}$} be a successor of {\bf s}.
The resistance between these two states, denoted by {\bf 
r(s,s$^{^{\prime}}$)}, is the minimum number of mistakes required in the one
period
transition {\bf s $\longrightarrow$ s$^{^{\prime}}$}. 
Similarly, for any two states {\bf s$^1$} and {\bf s$^2$}, {\bf r(s$^1 $,s$ 
^{2}$)} is the minimum number of mistakes required to reach {\bf s$^2$} from 
{\bf s$^1$} through a sequence of one period transitions. 
\end{definition} 

The resistance of a {\bf w}-tree  is naturally defined as the total 
resistance of each of its edges.  Let ${\cal T}_w$ denote the set of all {\bf 
w}-trees. 

\begin{definition} {\em (Stochastic Potential)}  The  stochastic potential of 
a convention {\bf w } is the least resistance among all {\bf w}-trees:
$$
\gamma(\mbox{{\bf w }}) = \min_{T \in {\cal T}_w} 
\sum_{\mbox{{\bf(w$^1$,w$^2$)}} \in T}   \mbox{{\bf r(w$^1$,w$^2$)}}.
$$
\end{definition}


\noindent {\bf Theorem A} (Young (1993a)) {\em The sequence of stationary
distributions 
$\mu^{\epsilon}$ converge to a stationary distribution $\mu^0$ of $P^0$ as 
$\epsilon \rightarrow 0$. Moreover, a state {\bf s } is stochastically stable 
iff {\bf s = w } is a convention and has the minimum stochastic potential 
amongst all conventions. } \\ 


In order to allow for a parsimonious construction of the tree of minimum 
stochastic potential, I make the following assumption.

\begin{assumption}\label{as3} 
Players only make mistakes that are a distance $\delta$ away from a best 
response.  That is, if {\bf s } is the state at time $t$, then for every $i$, 
$q_i(\omega_{i,t+1}|\mbox{ {\bf s }}) > 0$ iff there is a $\hat{\omega}$ such
the 
\begin{itemize}
\item $p_i^*(\hat{\omega}|\mbox{{\bf s }}) >0$ 
\item $|\hat{\omega} -\omega_i| \leq \delta$. 
\end{itemize}
\end{assumption}

Young (1993b) constructs a tree of minimum stochastic potential without 
resorting to any assumptions on players' mistakes in the two player case. With
three or more players, however, the allocation space has is at least two 
dimensional. Consequently, one has to contend with the possibility of cycles 
that do not arise in Young's compact, one dimensional space. 

Two further remarks are in order. First, note that Assumption~\ref{as3} is 
made on the players' strategies  rather than the payoffs. However, when in a 
convention, say {\bf w$^*$}, the unique best-response is $\omega_i^*$. With the
above assumption, player $i$ is assumed to demand for $\omega^*_i + \delta$ and
$\omega^*_i-\delta$ as well as $\omega_i^*$ with a positive probability. In
terms of 
payoffs, $\omega^*_i -\delta$ will constitute as "small mistake" as it will be
met 
for sure while $\omega^*+\delta$ which will be rejected for sure is a "large 
mistake". So, in a sense, Assumption~\ref{as3} allows only for extremes in 
terms of payoffs. Of course, nothing is implied in states that are not 
conventions as the payoff functions in this model are not continuous in 
strategies.


Second, recall that the definition of stochastic stability was based on the 
assumption 
that the perturbed transition probability matrix had a unique invariant 
distribution. With the above assumption, it is no longer clear that the 
$P^{\epsilon}$ is irreducible. Consequently, it is now not immediate that a 
unique invariant distribution exists and hence stochastic stability may be an 
ill-defined concept. Theorem 2 below, which uses a special bound on the 
extent of players' information establishes the validity of the solution 
concept. 



\begin{theorem}~\label{thm2} Under Assumption~\ref{as3},  $P^{\epsilon}$ admits
a unique invariant distribution  for every $\epsilon >0$ if $\alpha_i \leq 1/4$
for 
all $i$. Moreover, the 
support of this invariant distribution contains the set of all conventions. 
\end{theorem} 

\proof See Appendix B. \\ 



The following notation is useful: $$ g(W)  =  \sum_{i 
\in N} \alpha_i\log(v_i(\omega)) $$ $$ g_i(\omega)  = \frac{\partial \alpha_i 
\log(v_i(\omega))}{\partial \omega} $$ $$ r_i(\omega,\delta) = \alpha_i[1-
\frac{v_i(\omega -\delta)}{v_i(\omega)}] $$ $$ r(W,\delta) = \min_{i \in N} \ 
r_i(\omega_i,\delta). $$ 

\begin{theorem}\label{thm3} 
There exists a level of precision $\delta^*$ 
such that for all  $ 0 < \delta \leq \delta^*$ a  convention {\bf w}$^{\delta}$
is stochastically stable for every
admissible $m$ iff $W^{\delta}$ maximizes the function $r(.,\delta)$ over all

$W \in {\cal C}_{\delta}(f)$. 
\end{theorem} 

\proof (Sketch) Starting from a convention {\bf w}, The function 
$[mr(W,\delta)]$ is the minimum number of mistakes that are required before 
some player has a best response that is different from that in the convention 
( Corollary B.1 ). Hence {\bf r(w,w$^{'}$)} cannot fall below  
$[mr(W,\delta)]$.  The proof then involves showing that one can construct a 
{\bf w}$^{\delta}$-tree that involves exactly $[mr(W,\delta)]$ mistakes at 
each edge, $\mbox{{\bf w}} \rightarrow \mbox{{\bf w}}^{'}$. The resistance of 
any other {\bf w}-tree must then exceed that of this particular {\bf
w}$^{\delta}$ tree by at 
least $[mr(W^{\delta},\delta)] - [mr(W,\delta)]$. For large enough m, if $W$ is
not 
another maximum of $r(.,\delta)$, then by Theorem A,  {\bf w} cannot be 
stochastically stable. Details appear in Appendix B. 


Theorem~\ref{thm3} extends the results obtained by Young (1993b). The 
result here is weaker than in Young (1993) in two ways. First, an upper bound 
on $\delta$ is required. Second, there can be several stochastically stable 
conventions leading to an indeterminacy in the allocation for a subset of 
players even when $\delta$ converges to zero. 

\begin{example}{\em Let $N = \{1,2,3,4\}$, $f(12)= 100, f(N) =101$ and $f(S) =
0$ otherwise.  
In every core allocation, $\omega_1 + \omega_2 \geq 100$. Hence, 
$r(W,\delta) = \min \{ r_1(\omega_1,\delta),r_2(\omega_2,\delta)\}$ for  a 
core allocation $W$ and attains a maximum when $\omega_1 = \omega_2 = 50$. By 
Theorem~\ref{thm3}, every convention {\bf w} with $W= (50,50,\omega,1-\omega)$
with $ \delta \leq  \omega \leq 1 - \delta$ is stochastically stable.  } 
\end{example}



\begin{theorem}
 Let $W^*$  maximize  $g(.)$ over ${\cal C}(f)$.  Let $K \subset N$ be 
the set of players such that $i \in K$ implies $g_i(\omega_i^*) \leq 
g_j(\omega_j^*)$ for all $j \in N$.   For every every $\epsilon > 0$, there is
a $\delta^* > 0$ such that for all $0 < \delta < \delta^*$, if {\bf 
w}$^{\delta}$ is stochastically stable, then  
$$
\mid \omega^{\delta}_i - \omega^*_i \mid < \epsilon,
$$
for all $i \in K$. 
 \end{theorem} 

\proof See Appendix B.





 





\section{Some examples}


\subsection{Non-Convex Technology}

Even when the technology is not convex, it is still relatively easy to
compute the minimum number of mistakes that are required before some player
has a best response different from the conventional one. These turn out to
be functions that look like $r(.,\delta)$. But now, this minimum number of
mistakes is no longer sufficient to lead one out of the domain of attraction 
of the convention as the following example demonstrates.  

Note that the following 
example  may appear somewhat terse for the reader who has skipped Appendix B. 


\begin{example}
\label{eg2} {\em In Example~\ref{eg1}, set $\alpha_i = 1/4$ for all $i$. The
minimum number of mistakes $\hat{r}_{\delta} (\mbox{{\bf w}})$ before which
some player has a best response different from the conventional demand in a
convention {\bf w} is
$$
\frac{4}{\delta}\hat{r} (W,\delta) =  \left\{ 
\begin{array}{ll}
\min_{i=1,2,3} \frac{1}{\omega_i} & \mbox{ if  $W$ is in the core} \\  &  \\ 
\min \{ \frac{2}{\omega},\frac{1}{300-\omega}\} & 
\mbox{for a convention such as $W=  (300-\omega,\omega,\omega)$ } 
\end{array}
\right.
$$
\noindent where $\omega > 4$. This bound may be obtained by
constructing arguments similar to those found in Appendix B. For elements in 
the core, $\hat{r}(.,{\delta})$ coincides with $r(.,\delta)$ that appears in 
Theorem 3. Among the set of conventions that are not in the core, the fewest 
number of mistakes required before player 1 demands a $\delta$ less is 
$2/\omega_1$, whereas for players 2 and 3 the minimum number of mistakes 
continues to be $1/\omega_i$. This is because for player 1 to demand $\delta$ 
less as a best response in a convention such as $(300-\omega,\omega,\omega)$ ,
we require both player 2 and player 3 to make the mistake of asking for  
$\omega +\delta$. Hence, the correction of 2 for player 1.  

The least player 1 obtains in the core is in the allocation $(298,2,2)$. 
In the convention involving these demands, player 1 requires the minimum 
number of mistakes to be the first player to have a best response different 
from 298. This corresponds to the case where both players 2 and 3 have 
demanded $298 -\delta$ for some $L^*$ periods, determined by 
$\hat{r}_{\delta}$. To this, the best response of player 1 is to ask for 
$298+\delta$.  Suppose now, that from this point on, say $T$, no further 
mistakes occur. Assume, without loss of generality, that all mistakes actually
occurred in the last $T-L^*$ dates. 

 It is easy to see, that from this point onwards, the demands of player 1 will
not be anything other than $298$ or $298-\delta$ while those of players 2 and 
3, will not be anything other than $2$ or $2+\delta$. 

Now, consider a sample of m/4 in which every demand of player 1 is $298-
\delta$, while that of player 3 is $2$ in $m/4-1$ entries. The one demand is 
$2+\delta$. To this sample, a demand of 2 by player 2 will be a unique best 
response if 

\begin{eqnarray*}
2 & > & \frac{ (m/4 - 1)}{m/4} (2+\delta) +
\frac{1}{m/4} (2+\delta)/2 \mbox{\hspace{  .2in} or}  \\ 
2 & > &  (1 - 2/m) (2+\delta) 
\end{eqnarray*}



The last inequality holds for an appropriate $\delta$. Thus, the only sample 
for which $2+\delta$ is a best-response is if player 3 always has asked for 
$2$ and player 1 always has asked for $2-\delta$. Since $(298-\delta, 
2+\delta,2)$ is not a convention, the process eventually returns to 
$(298,2,2)$ in the absence of further mistakes. }
\end{example}

The problem in this example appears due to the fact that the set of
conventions is not connected. When $\delta$ is small, the minimum number of 
mistakes required to lead to a best response is not sufficient to lead away to
a different convention. Indeed, the number of mistakes required to 
required to reach a convention involving demands of the form
$(300-\omega,\omega,\omega)$, 
starting from a demand in the core, turns out to be very large. This is 
because we require a series of mistakes on the part of players 2 and 3 each of

them demanding a $\delta$ higher at each instant. On the other hand, the 
number of mistakes required to reach an element of the core from the 
convention with demands $(296,4,4)$ is at least $298m/[4 (298+\delta)]$. For a
fixed $\delta$, this is a large number. Hence, one cannot obtain a bound 
independent of $\delta$ and $m$. Questions of existence and characterization 
of stochastically stable conventions for examples such as these are left open 
as possibilities for future research. 

\subsection{Competition and Evolution}

The competitive allocations of an economy continue to be the benchmark for
comparing those obtained under other mechanisms. A frequent criticism of the
Walrasian mechanism is the absence of a dynamic story of adjustment 
\footnote{See Gale (1987a and 1987b) however.} The function $f$ can be thought
of as
being the game generated by an endowment economy in which agents have
quasilinear preferences for money. The EBP can then be thought of a process
of adjustment to equilibrium in such an economy. Hence it is of interest to
compare the competitive outcomes with the SSC conventions.

\begin{example}
\label{eg3}{\em Let $N = \{1,2,3\}$, $\alpha_i=1/4$, $v_i(x)=x$, 
$f(12)=f(13)= f(123)=300$ and $f(S) = 0$, otherwise. The technology 
corresponds to the well-known representation of a game with two sellers and 
one buyer. When one does not allow for zero demands, the core of this 
technology is empty. But the set of absorbing states corresponds to $m$ 
repetitions of the form $ (300-\omega,\omega,\omega)$, where $\delta \leq
\omega \leq 300-\delta$. 
Player 1 obtains $300-\omega$ in one of the two smaller coalitions while 2 and
3 
obtain $\omega$ with some probability. It can also be shown that, with the same
bound as in Theorem~ \ref{thm1}, all other states are transient. Of course, it
is being assumed that both the two player coalitions are equally likely. 

As mentioned before, the problem in Example~\ref{eg2} appears because
the set of absorbing states is not a connected set. However, when the set of
absorbing states is a connected set, as it is here, the techniques in the
proof of Theorem~\ref{thm3} can still be applied. A stochastically stable
convention maximizes the function $\hat{r}_{\delta}$ over  $\delta \leq 
\omega \leq 300 - \delta$ where . 
$$
\hat{r}_{\delta} (\mbox{{\bf w }}) = \frac{\delta}{4}\min \left\{ \frac{2}{
300-\omega},\frac{1}{\omega}\right\}.
$$


 The competitive outcome on the other hand, is one in which player 1
yields the least amount to either player 2 or 3. In the present case this
corresponds to $(300- \delta,\delta,\delta)$. 

 When $\delta \rightarrow 0$, the stochastically stable outcomes
converge to $(200,100,100)$ whereas the competitive outcome is the one in
which player 1 gets the whole surplus, i.e., $(300,0,0)$. In expected terms,
players 2 and 3 obtain $50$ in the bargained outcome while the competitive
outcome gives them 0. }
\end{example}

\subsection{Does the Utility function matter?}

As in Young(1993b), let $(v_i,\alpha_i)$ denote the type of a player. An
interesting result of Young(1993b) is emergence of a fifty-fifty split as the
SSC regardless of the types of the players. In the model above, the result
continues to hold in the sense that a particular division will be observed
regardless of the utilities. However, if the technology is not convex, as it
is in the earlier example, this is not the case.

\begin{example}
\label{eg4}{\em In Example~\ref{eg3}, suppose that the utility that player $i
$ derives from consuming $\omega$ is given by $v_i(\omega) = 1-e^{-\omega}$.
Conduct the
entire analysis as before to deduce that the minimum number of mistakes that
are required before some player has a best response different from the
conventional one is given by }

{\em 
$$
\hat{r}_{\delta} (\mbox{{\bf w }}) = \frac{e^{\delta}-1}{4}\min \left\{ 
\frac{2}{e^{300-\omega}-1},\frac{1}{e^\omega-1}\right\}.
$$}

{\em The stochastically stable outcome is the convention that maximizes the
above function. When $\delta \rightarrow 0$, the stochastically stable
outcome converge to $(300-\omega^*,\omega^*,\omega^*)$ where $\omega^*$ solves
$$
2 (e^{\omega^*}-1) = (e^{300-\omega^*}-1).
$$
It may be checked that $\omega^* > 100$. }

{\em The competitive outcome on the other hand, converges to be $(300,0,0)$.
Relative to the competitive outcome, player 1 continues to fare worse in the
stochastically stable outcome. In fact, he does worse in the stochastically
stable outcomes with constant absolute risk-aversion than he did with under
similar outcomes when all the players had linear utilities in Example~\ref
{eg3}. } \end{example}

\begin{thebibliography}{99}
\bibitem{}  BINMORE, K.G: "Nash Bargaining Theory II, and Nash bargaining
theory and incomplete information," in {\em The Economics of Bargaining}
(K.G.Binmore and P. Dasgupta, Eds.), Basil Blackwell, Oxford, 1987

\bibitem{}  CARLSSON, H. (1991): A bargaining model where parties make
errors, {\em Econometrica}, 59, 1487-1496

\bibitem{}  CHATTERJEE, K., B.DUTTA, D.RAY, AND K.SENGUPTA (1993): "A Non-
Cooperative Theory of Coalitional Bargaining," {\em Review of Economic
Studies}, 60, 463-477             

\bibitem{}  FELLER, W. {\em An Introduction to Probablity Theory and Its 
Applications}, Vol 1., 3rd Ed., John Wiley, New York, 1968.

\bibitem{}  FOSTER, D. AND YOUNG, H.P.(1990): "Stochastic Evolutionary game
dynamics," {\em Theoretical Population Biology.}, 38, 219-232.

\bibitem{}  FRIEDLIN, M. AND WENTZELL, A. {\em Random Perturbations of
Dynamical Systems}, Springer Verlag, New York,1984.

\bibitem{}  KANDORI, M., MALAITH, G. AND ROB, R. (1993): "Learning,
mutation and long-run equilibrium in games," {\em Econometrica,} 61, 29-56

\bibitem{}  PERRY, M. and RENY, P. (1991) "A Non-Cooperative View of
Coalition Formation," (Mimeo), University of Western Ontario, London, Canada

\bibitem{} RUBINSTEIN, A. (1982) "Perfect Equilibrium in a Bargaining Model," 
{\em Econometrica}, 50, 97-109. 

\bibitem{}  SERRANO, R. and VOHRA, R. (1993): " Non-Cooperative
Implementation Of The Core," Working Paper No. 93-41, Brown University,
Providence, Rhode Island 02912

\bibitem{}  STAHL, I. (1972) {\em Bargaining Theory.} Stockholm: Economics
Research Institute

\bibitem{}  YOUNG, H.P. (1993a): "The evolution of conventions," {\em 
Econometrica}, 61, 57-84.

\bibitem{}  YOUNG, H.P (1993b): "An evolutionary model of bargaining," 
{\em Journal of Economic Theory,} 59,1, 145-168


\bibitem{}  WINTER, E. (1992): "Non-Cooperative Bargaining in Natural
Monopolies," Discussion Paper, Center for Rationality and Interactive
Decision Theory, Hebrew University, Jerusalem, 91904 Israel

\end{thebibliography}



\appendix
\section{Appendix}

For the sake of clarity, the proof of Proposition 2 will be preceded by a
couple of lemmas. Recall that $\beta(W)$ was the set of all coalitions in 
which the demands were just compatible (at $W$) and $\hat{\beta}(W)$, the set 
of all coalitions in which the demands are strictly compatible. 
$$ 
\beta(W) = \{S \subseteq N:W(S) \leq f(S)\}
$$
$$
\hat{\beta}(W) = \{S \subseteq N: W(S) < f(S)\}.
$$


\begin{lemma}~\label{l1}
Fix $W$. If the demands of $S$ and $T$  are compatible, then 
$$
W(S \cap T) - f(S \cap T)  \leq f(S \cup T)  - W(S \cup T).
$$
Moreover, the above inequality is strict if the demands of either $S$ or $T$
are strictly 
compatible. 
\end{lemma}

\proof Immediate from covexity and the fact the for every $W$, 
$$
W(S \cup T) + W(S \cap T) \equiv W(S) + W(T).
$$ 

\begin{corollary}~\label{cr1}
Suppose that the demands of $S$ and $T$ are compatible but there is no 
coalition whose demands are strictly compatible. Then the demands of $S \cap 
T$ and $S \cup T$ are also compatible. 
\end{corollary} 


\begin{corollary}\label{l2} 
If there are no coalitions whose demands are strictly compatible at $W$, then 
there can be at most one largest coalition whose demands are compatible. 
\end{corollary}

\proof Immediate from the Corollary~\ref{cr1}.

\begin{lemma}~\label{l3}
Fix $W$ and let $W(S) < f(S)$.   Then, there is an $S^* \subseteq S$ such that
\begin{enumerate}
\item  The demands of $S^*$ are strictly compatible.
\item For every compatible coalition $T$ that does not contain $S^*$,
  $T \cup S^*$ is strictly compatible. 
\end{enumerate}
\end{lemma} 

\proof Let  $S_1 \equiv S$. 
If the Lemma holds with $S_1 = S^*$, we are done. Otherwise there is a 
compatible coalition $T$ that does not contain $S_1$ such that $W(S \cup T) 
\geq f(S \cup T)$. Then $S_2 = S_1 \cap T$ is a strict, non-empty subset of 
$S_1$. Furthermore, a straightforward application of Lemma~\ref{l1} reveals
that,  $S_2 = 
W(S_2) < f(S_2)$. If the Lemma holds with $S_2 = S^*$, we are 
done. If not, we can repeat the above process finitely many times to obtain  
an $S_k = \{i\}$ such that $\omega_i < f(i) = 0$. This contradicts the fact
that 
$\omega_i >0$. $\Box$ 

\begin{corollary}\label{c1}
Under the hypotheses of  Lemma~\ref{l3},  for all $i \in S^*$, 
\begin{enumerate}
\item $\hat{\omega}_i > \omega_i$, where \( \hat{\omega}_i = \arg\max
p_i(\omega|W_{-i})v_i(\omega)\).
\item $\hat{\beta}(\hat{W})$ is a strict subset of $\hat{\beta}(W)$, where 
$\hat{W}_{-i} = W_{-i}$ and $\hat{\omega}_i$ is as defined above. 
\end{enumerate}
\end{corollary}

\proof  Let $i \in S^*$.  By 
virtue of Part 2 of Lemma~\ref{l3}, player $i$ can increase his demand by  a  
positive amount say to $\hat{\omega}$ and still ensure that if  a coalition 
$T$ continues to be compatible, then $T \cup S^*$ is also compatible. Hence, 
by Assumption~\ref{as2},  $p(\hat{\omega}|W_{-i}) =1$.  This proves Part 1. 
Part 2 is must hold since player $i$ must increase his demand until one of the
coalitions in which the demands were strictly compatible is just compatible. 
$\Box$



\begin{corollary}~\label{c2}
Let  $W^{*}$ be a Nash equilibrium. Then, $\hat{\beta}(W^*) = \phi$. 
\end{corollary}
\proof Immediate from the definition of a Nash equilibrium and Part 
1 of Corollary~\ref{c1}. $\Box$

\vspace{.25 in} \noindent \proof (Proposition 2) Let $W^*$ be a Nash 
equilibrium. Given Corollary~\ref{c2}, we need only show that  $W^*(N) = 
f(N)$. It is clear that for $W^*$ to be a Nash equilibrium, 
for every player  $i$, there is at least one $S \in \beta(W^*)$ that contains 
$i$. Now use Lemma~\ref{l2} to conclude that $W^*(N) = f(N)$. $\Box$ 

\section{Appendix B} 


In this Appendix, players' demands are in $\Delta_{\delta}$, unless stated 
otherwise. All the results from the Appendix A continue to hold with this 
restriction on players demands because of our assumption the each $f(S)$ 
is a rational number and the particular method of discretization employed. 
  
Given $W, W^{'}$, we will write $W \stackrel{S}{\rightarrow}W^{'}$ if 
$$
\omega^{'}_i= \left\{
                 \begin{array}{ll}
                      \arg\max p_i(\omega|W_{-i})v_i(\omega)& \mbox{if $i\in
S$}\\  
        \omega_i & \mbox{if $i \not\in S$} 
      \end{array}
           \right. 
$$


\begin{lemma}~\label{bl1} 
Suppose $\beta(W^0) \neq \phi$. If there is a set $T$ such that whenever 
$W(S) < f(S)$, $S $ contains a player not in $T$, then there is a sequence 
$$
W^0 \stackrel{i_1}{\rightarrow} W^1 \stackrel{i_2}{\rightarrow} \dots 
\stackrel{i_{L-1}}{\rightarrow} W^{L-1} \stackrel{i_L}{\rightarrow}W^L
$$
such that 
\begin{enumerate} 
\item The demands of no coalition are \underline{strictly} compatible at 
$W^L$ but there is a unique largest coalition whose demands are 
compatible.
\item Furthermore,  the sequence of players above can be  chosen so that $i_l 
\not\in T$ for all $l = 1, 2, \dots L$.
\end{enumerate} 
\end{lemma} 

\proof Assume that $\hat{\beta}(W^0) \neq \phi$ (otherwise there is nothing 
to prove).  We can find an $S^*$ as in Lemma~\ref{l3}.  By hypothesis, $S^*$ 
contains a player not in $T$, say $i_1$. $W^1$ is obtained by $W^0 
\stackrel{i_1}{\rightarrow} W^1$. By Corollary~\ref{c1}, $\hat{beta}(W^1)$ is 
a strict subset of $\hat{\beta}(W^0)$.  Clearly $\beta(W^1) \neq \phi$ because
there must be at least one coalition in which player $i_1$'s demand is 
compatible.  Now repeat the above procedure to obtain $W^1$ to obtain 
$i_2$ and $W^2$ and so on. In finitely many steps, $\hat{\beta} (W^L) = \phi$.
Now use Corollary~\ref{l2} to conclude that there is a unique largest coalition
at $W^L$ in which the demands are compatible. 
$\Box$



\begin{lemma}\label{bl2}
Suppose $\beta(W^0) \neq \phi$. Then, there is a 
sequence $\{W^{l},S_l\}$, $l = 1,2 \dots L_1, L_1 + 1 \dots L_2, L_2+1 \dots, 
L_{Q-1}+ 1, \dots,L_Q$ such that; 
\begin{enumerate} 
\item For all $W^l\stackrel{S_{l+1}}{\rightarrow}W^{l+1}$, for all $0 \leq l 
\leq L_{Q-1}$.
\item $S_{L_k+1} = N$, for all $k = 1,2,\dots Q-1$. 
\item  The demand vector $W^{L_Q}$ is in the core. 
\end{enumerate}
\end{lemma} 

\proof Set $T = \phi$ in Lemma~\ref{bl1} and obtain the sequence up to 
$W^{L_1}$. Let $T_1$ be the unique largest coalition in which the demands are 
compatible.  If $T_1 = N$, we are done. Otherwise,
consider $W^{L_1} \stackrel{N}{\rightarrow} W^{L_1+1}$. Since the 
demands of no coalition are strictly compatible at $W^{L_1}$, no player will 
increase his demand. Moreover, by Assumption~\ref{as2}, 
$p_i(\omega^{L_1}_i|W^{L_1}_{-i}) = 1$ for all  $i \in  T_1$. Hence, 
$\omega^{L_1+1}_i =\omega^{L_1}_i$, 
for all $i \in T_1$. Furthermore, a player  not in  $T_1$ 
will reduce his demand so that at $W^{L_1+1}$, 
every player will have his demand met in at least one  coalition.  If now 
$\hat{\beta}(W^{L_1+1}) = \phi$, we are done as $W^{L_1 + 1}$ is in the core. 

Suppose $\hat{\beta}(W^{L_1 +1}) \neq \phi$. 
Set $T_1\equiv T$, $W^0 \equiv W^{L_1+1}$ in Lemma~\ref{bl1} 
to obtain the sequence leading to $W^{L_2}$. Again we have a unique largest 
coalition $T_2$ whose demands are compatible but the demands of no coalition 
are strictly compatible. Since the demands of the players in $T_1$ have not 
changed, and at least one more player's demand is now being met, it follows 
that $T_2$ is a strict superset of $T_1$.  If $W^{L_2}$ is in the core, we 
are done. Otherwise we need repeat the above process only finitely many times 
to reach a situation where $T_Q =N$. $\Box$ \\ 



\proof (Theorem 1) Again, assume, for the sake of exposition, that $\alpha_i 
= \alpha_j$. Let {\bf s} be the state at time $t$ and let $\sigma$ 
denote the sample consisting of the $k$ most recent records. Let $W^0$ be the 
demand vector resulting from every player sampling $\sigma$.  Assume that 
$\beta(W^0)$ is not empty. The other case will be dealt with shortly. 
Now, let $\{W^l,S_l\}$ be the sequence as in Lemma~\ref{bl2}. 

Let {\bf  A} be the following event:
\begin{enumerate}
\item Between $t$ and $t+k$, all players sample $\sigma$. 
\item Between $t+lk+1$ and $t+(l+1)k$, all players except those in $S_l$ 
continue to sample what they were sampling between $t+(l-1)k+1$ and $t+lk$. 
Players in  $S_l$ sample the $k$ most recent demands, $1 \leq l \leq L_{Q-1}$.
\end{enumerate} 


It is easy to verify that if the {\bf A}  were to occur,  it will lead to $k$ 
repetitions of $W^0$ between $t+1$ and $t+k$, followed successively by $k$ 
repetitions of $W^1$ between $t+k+1$ and $t+2k$ and so on finally ending with 
$k$ repetitions of $W^{L_Q}$ between $t+{L_{Q-1}}k +1$ and $t+L_Qk$. Indeed,
given our 
assumptions that each player samples every $k$ sample with a positive 
probability, the event {\bf A} would occur with a positive probability if the 
initial sample $\sigma$ were available in its entirety between until date 
$t+k(L_1+1)$ and since $S_{L_q} = N$, for the next $k(L_q+1)$ periods $W^{L_q}$
were available.  This would be possible if $m \geq \max_q\{(L_q+2)k\}$. 
Note that $L_q$'s depend only on the number of coalitions in which the demands
were strictly compatible. Hence, $L_q \leq \frac{n(n-1)}{2}$, which is the 
number of two player coalitions with $n$ players. 

Now, assuming that the bound on $k/m$ is met, there is then  a positive 
probability of observing $k$ repetitions of $W^{L_Q}$, which is a core 
allocation, in finitely many stages. Furthermore, now there is a positive 
probability that all the players sample this $k$-run of $W^{L_Q}$ to achieve 
another $k$-run of $W^{L_Q}$ and so on to finally obtain the convention {\bf 
w$^{L_Q}$} in some $M$ periods altogether. 

Thus, there is a positive probability $p$, bounded away from zero by our 
assumption of stationarity, and an integer $M$, such that a convention is 
established in $M$ periods. Hence the probability of not reaching a convention
in $rM$ periods is $(1-p)^r$, which goes to zero as $r \rightarrow \infty$. 

 Now suppose $\hat{\beta}(W^0) = \phi$. If $W^0$ is in the core, we are 
done. If the demands of no coalition are compatible at $W^0$, then consider
$W^0 \stackrel{N}{\rightarrow} \hat{W}^0$ and conduct the above analysis 
starting from somewhere in the middle of the sequence obtained in 
Corollary~\ref{bl1}. $\Box$

\begin{lemma}~\label{nooftrembles} Fix a convention  {\bf w}$^{*}$. Starting 
from this convention, the minimum number of mistakes required for player $i_0$
to be the \underline{first player} to have a best response 
different from $\omega^*_i$ for the \underline{first time} is given by 

 $$ 
\min\left\{\frac{k_{i_0}v_i(\omega_{i_0}^{*})}{v_{i_0}(\omega_{i_0}^{*}+(n-
1)\delta )},k_{i_0}[1-\frac{ v_{i_0}(\omega_{i_0}^{*}-\delta 
)}{v_{i_0}(\omega_{i_0}^{*})}]\right\} $$ \end{lemma} 

\noindent \proof Starting from a convention {\bf w}$^*$, let {\bf s} be the
first
state in which player $i_0$  is the first player to have a best-response
different from the conventional demand. For concreteness, set $i_0=1$. Note 
that  by the definition of {\bf s }, every $W_{-1}$  in {\bf s } that is not 
$W^*_{-1}$ involves at least one mistake.  Let there be $L$ such demands that 
differ from $W^*_{-1}$. In fact, without loss of generality assume that these

are be the $L$ most recent demands. Let $\hat{\omega}$ denote the best 
response of player 1. 
 
{\em \underline{Case 1:}} ($\hat{\omega} < \omega^*_i$) Now consider a sample
of size 
$k_1$ from {\bf s } that includes the $L$ demands.  Thus $(k_1 -L)$  of the 
demands in this sample are $W^*_{-1}$ while the last $L$ demands are $W^l_{-
1}$, $l = 1,2, \dots L$. By playing $\omega^*_1$ player $1$'s expected utility
is 
\begin{equation} \label{e1} 
(1-\frac{L}{k_1})v_1(\omega^*_1) + \sum_{L =
k_1-L+1}^{k_1}p_1(\omega^*_1|W_{-1}^l)v_1(\omega^*), 
\end{equation}
which is no larger than \begin{equation}
 \label{e2}(1-\frac{L}{k_1})v_1(\hat{\omega}) + \sum_{l =
k_1-L+1}^{k_1}p_1(\hat{\omega} 
|W_{-1}^l)v_1(\hat{\omega}), \end{equation} the payoff if he plays
$\hat{\omega}$. 

Define 
\begin{equation}~\label{eqS1}
S_1  = \bigcap_{S \in \beta(W^*), 1 \in S} S.
\end{equation}

Since there are no strictly compatible coalitions at $W^*$, 
Corollary~\ref{cr1} applies and, $W^*(S_1) = f(S_1)$.
Without loss of generality, assume that $2 \in S_1$. Consider a new demand 
vector $\overline{W}$ that differs from $W^*$ only in the demand of player 2. 
Player 2 demands $\omega^*_2+(\omega^*_1-\hat{\omega})$. 

Now consider the new sample constructed from the original sample with the last
L entries as  $\overline{W}$. Note well that this new 
sample has exactly $L$ mistakes, no more than those in the original sample. 
These are of course the $L$ demands of player 2 that differ from $w^*_2$. 
I will now show that  given $\hat{\omega}$ is a best-response to the original 
sample, $\hat{\omega}$ is a best-response to this new sample. 

Note that by our choice of player 2,  player 1's demand $\omega^*_1$ is not 
compatible in any coalition when 2 demands $\omega^*_2
+(\omega^*_1-\hat{\omega})$.  
The payoff of player 1, then on playing $\omega^*_1$ is by 
$$
(1-\frac{L}{k_1})v_1(\omega^*_1). 
$$

However on demanding $\hat{\omega}$, he obtains it for sure and hence achieves
a payoff of $v_i(\hat{\omega})$. Since the expression in Eq. ~\ref{e2} is at 
least as large as that in Eq. ~\ref{e1}, 
it is easy to see that 
$$
v_1(\hat{\omega})  \geq  (1-\frac{L}{k_1})v_1(\omega^*_1). 
$$
Hence, if $\hat{\omega}$ was a best response to the initial sample, it 
continues to be a best response to the new sample. Thus, 
\begin{eqnarray}
   L     \geq  k_1[1-\frac{v_1(\hat{\omega})}{v_1(\omega^*_1)}] \nonumber \\
        &  \geq  & m r_1(\omega^*_1, \delta).
\end{eqnarray}

\noindent {\em \underline{Case 2:}} ($\hat{\omega} > \omega^*_1$) As before
consider a
sample of size $k_1$ from the state {\bf s } for which $\hat{\omega}$ is a
best
response. Now as in the earlier case the payoff on demanding $\omega^*_1$ is
given by Eq. ~\ref{e1}. However on demanding $\hat{\omega}$, the payoff is 
\begin{equation}
\label{e3} \sum_{l=n+1}^{k_1}p_1(\hat{\omega}|W_{-1}^l)v_1(\hat{\omega}). 
\end{equation}
Since $\hat{\omega}$ is a best response, Eq. (~\ref{e3}) is at least as large
as 
Eq.(~\ref{e1}). 

As in the earlier case, construct a new sample from the initial sample 
by replacing the last $L$ demands of every player except 2 with $\omega^*_j$. 
Replace those of player 2 with $\overline{\omega}_2 = \omega^*_2 -
(\hat{\omega} - \omega^*_1)$. 
In this new sample, there are exactly $L$ mistakes, no larger than those in 
the initial sample. 

Now, it remains to show that $\hat{\omega}$ continues to be a best response for
player $1$ in this new sample. That is, we need to show that 
 $$ \frac{L}{k_1} v_1(\hat{\omega}) \geq v_1(\omega^*_1). $$ 
The above follows from the following sequence of inequalities.
\begin{eqnarray}
\frac{L}{k_1}v_1(\hat{\omega}) - v_1(\omega^*_1) & = &
\frac{L}{k_1}[v_1(\hat{\omega})-v_1(\omega^*)] -
(1-\frac{L}{k_1})v_1(\omega^*_1)  \nonumber \\
                                    & \geq & \sum_{l = k_1-L+1}^{k_1}
p_1(\hat{\omega}|W^l_{-1})[v_1(\hat{\omega}) -v_1(\omega^*_1)]  -
(1-\frac{L}{k_1})v_1(\omega^*_1) 
\nonumber \\                    
                                  & \geq   &\sum_{l = k_1-
L+1}^{k_1}p_1(\hat{\omega}|W^l_{-1})v_1(\hat{\omega})- \nonumber \\
\label{uas1}                                  &  &  \;\; \sum_{l=k_1-
L+1}^{k_1}p_1(\omega^*_1|W^l_{-1})v_1(\omega^*_1) -
(1-\frac{L}{k_1})v_1(\omega^*_1) \\  
& \geq & 0 \nonumber.  \end{eqnarray} 


Eq. (~\ref{uas1}) follows from Assumption~\ref{as1} and the non-negativity 
follows from the fact that the expression in Eq. (~\ref{e3}) is at least as 
large as that in Eq. (~\ref{e1}). 
 Hence, the number of mistakes is given by
$$ 
L \geq k_1v_1(\omega^*_1)/v_1(\hat{\omega}).
$$

The minimum number occurs when $\hat{\omega}$ takes the maximum value. But
since we 
allow only for small mistakes, it follows that the largest value of
$\hat{\omega}$ 
cannot be  more than $\omega^*_1 + (n-1)\delta$.  So, the number of mistakes
cannot 
fall below         
$$ 
k_1\frac{v_1(\omega^*)}{v_1(\omega^*+(n-1)\delta)} .
$$

The proof is complete on taking the minimum of the two lower bounds obtained 
in the two different cases above. $\Box$ 

\begin{lemma}\label{min}
Let $0 < \delta < \alpha_1f(N)/(\alpha_nn^2)$. If  {\bf w} is a  
convention, then 
$$ 
\alpha_i\frac{v_i(\omega_i)}{v_i(\omega_i+(n-1)\delta)} \ \geq \ r(W,\delta).
$$ 
\end{lemma} 

 \proof Using concavity of $v_i$ and the fact that $\omega_i \geq \delta$, we 
have 
\begin{eqnarray*} 
\alpha_i\frac{v_i(\omega_i)}{v_i(\omega_i+(n-1)\delta)} & \geq &
\alpha_i\frac{\omega_i}{\omega_i+(n-
1)\delta} \\ & \geq &\frac{\alpha_1}{n} 
\end{eqnarray*} 

Again by concavity of $v_i$ and the fact that there is at least one $\omega_i 
\geq f(N)/n$, we have 
\begin{eqnarray*}
r(W,\delta)  & \leq &  r_i(\omega_i,\delta) \\ 
              & \leq & \frac{\alpha_i\delta}{\omega_i} \\
               & \leq & \frac{\delta n\alpha_n}{f(N)}
\end{eqnarray*} 

The rest of the proof is immediate upon comparing the above two inequalities. 
$\Box$

\begin{corollary}~\label{b1}
Let  $0 < \delta \leq \alpha_1f(N)/(\alpha_nn^2)$. At a convention {\bf w} 
and for any state {\bf s}, 
$$
\mbox{{\bf r(w,s)}} \geq [mr(W,\delta)]
$$ 
 \end{corollary} 

\proof  By virtue of the previous two lemmas, $[mr_i(\omega_i,\delta)]$ is the
minimum number of mistakes for player $i$ to be the first player to have a 
best response different from $\omega_i$  in the convention {\bf w}. Hence, 
{\bf r(w,s)} cannot fall below $[mr(W,\delta)]$, the minimum number of 
mistakes required before {\em some} player has a different best response for 
the first time.  $\Box$



 
Now, let $e_{ij}$ denote the vector in $R^n_+$ where the $i$th component is $
-\delta$, the $j$th component is $\delta$ and every other component is zero.
Given a convention {\bf w},   the convention {\bf w}$+e_{ij}$ (if it is a 
convention) involves a transfer of $\delta$ from player $i$ to $j$. 


\begin{lemma}~\label{resistance} Let  $\delta \leq \alpha_1f(N)/(\alpha_n 
n^2)$ and  $W, \  W+e_{ij} \in  {\cal C}_{\delta}(f)$. Suppose that
$r(W,\delta) 
= r_{i_0}(\omega_{i_0},\delta).$ Then 
\begin{enumerate} 
\item $\mbox{{\bf r(w,w$+e_{ij}$)}} = [mr(W,\delta)] = 
[mr_{i_0}(\omega_{i_0},\delta)]$, if $j \neq i_0$ and 
\item $\mbox{{\bf 
r(w,w$+e_{ij}$)}} \leq  \min_{i \neq i_0}[r_i(\omega_i,\delta)]$, if $j = i_0$.
\end{enumerate} 
\end{lemma} 

\proof  I will prove only Part 1 of the Lemma. Part 2 can be proved by 
constructing arguments almost identical to those of provided for Part 1 below.

For concreteness, take  $i_0=1$ and pick  $2 \in S_1$ where $S_1$ is obtained 
as in Eq.~\ref{eqS1}. Now consider the following three demand vectors: 

\begin{enumerate}
\item  $W^{1}$ differs from $W^*$ only in player 1's demand: $\omega^{1}_1 =
\omega^*_1 - \delta$.
\item  $W^{j}$ differs from $W^*$ only player j's demand: $\omega^{j}_j =
\omega^*_j+\delta$.
\end{enumerate}

By Corollary~\ref{b1}, it suffices to exhibit a  path between {\bf w} 
and {\bf w$+e_{ij}$} that involves exactly $[mr(W,\delta)$ mistakes. 

Suppose the EBP is in state {\bf w } at time t. Now, suppose that between
time $t+1$ and $t^*=t+[mr(W,\delta)]$ player
2 plays $\omega^*_2+\delta$ instead of $\omega^*_2$. Each of these demands is a
mistake. 
Let $\sigma$ denote the sample consisting of the $k = \max_{i\in N}k_i$  most 
recent demands. By our choice of player 1, $\sigma$ contains a subsample for 
which the best response of every player other than 1 continues to be
$\omega^*_i$. 
For player 1, given our choice of player 2, the best response is $\omega^*_1-
\delta$. 

Now there is a positive probability between  $t^*+1$ and $t^*+k$ 
all the players will sample from $\sigma$ leading to a run of $k$ repetitions 
of $W^{1}$. It is useful to remind the reader, that the entire sample $\sigma$
will be available until date $t^*+3k$ by our assumption that $k \leq m/4$. 

Following this run of $W^{1}$, there is a positive probability that between $
t^*+ k +1$ and $t^*+2k$ all the players except $1$ and $j$ will continue to
sample $\sigma$ while $1$ and $j$  sample from the $k$ most recent
records consisting of $W^{1}$. It is straightforward to check that this
should lead to a run of $k$ demands of $W^{j}$.

Between $t^*+2k+1$ and $t^*+3k$, there is a positive probability that all the
players except players $1, i$ and $j$ will sample $\sigma$; players $1$ and $j$
continue to sample $W^{1}$ as before and player $i$ samples the $k$
most recent records consisting of $W^{j}$. It may be checked that this
will lead to a run of $W+e_{ij}$.

Finally, from $t^*+3k$ onwards, there is a positive probability that all the
players will sample the $k$ most records consisting of $W+e_{ij}$
thereby establishing the convention {\bf w$+e_{ij}$} 
in due course. Since the above
path involved a best response by the players at every stage following the
first $t^*-t$ mistakes by player $2$, the proof is complete. $\Box$

\proof (Theorem~\ref{thm2})\footnote{In this proof, I use, without providing
formal 
definitions and proofs certain terminology and assertions that are rather 
standard in the theory of finite Markov Processes. See for e.g. Feller (1957)}
Consider an aperiodic Markov Chain with state space $\Omega$. A state can 
either be persistent or transient. Now, we know from that the persistent 
states of a finite Markov chain can be uniquely decomposed into disjoint 
closed sets, $C_1, C_2, \dots C_K$ such that  {\em from any state of a given 
set $C_k$,  
all states of this set and no other can be reached}.  In particular, if we 
show that the decomposition must involve a unique closed set,  say $\Omega^*$,

it then follows that all the states $\Omega \setminus \Omega^*$ are transient 
and that the states corresponding to  $\Omega^*$ form an irreducible sub-
chain. This  sub-chain admits a unique stationary distribution. Since a 
transient state cannot be in the support of a stationary distribution of the 
original Markov Chain, it then follows that there is a unique stationary 
distribution of the original chain; this is of course the invariant 
distribution corresponding to the the states in $\Omega^*$ extended with zeros
corresponding to the states in $\Omega \setminus \Omega^*$. 


That the perturbed EBP is aperiodic is obvious; from an arbitrary state, a 
convention can be reached following which a return to the original state if 
possible, can be achieved in either an even number or an odd number of 
periods.  I now claim that there is a unique closed set of recurrent states, 
say  $\Omega^*$, for the perturbed EBP and this contains all conventions.  
Indeed, let $C_1, C_2, \dots C_K$ the decomposition. Let {\bf s} be a state in
$C_k$. By Theorem 1, there is a positive probability of reaching a convention 
in finitely many steps. Hence, $C_k$ must contain at least one convention, say
{\bf w}.  Moreover, by virtue of Lemma~\ref{resistance}, from a given 
convention {\bf w}, there is a positive probability of reaching every 
convention of the form {\bf w}$+e_{ij}$. Since the core is a convex set, it 
follows that any convention {\bf w$^{ '}$} can be reached from an arbitrary 
convention {\bf w}.   Hence $C_k$ must in fact contain all the conventions. 
Since $C_k$ was arbitrarily chosen, it follows that the decomposition must 
involve a unique closed set of persistent states.  The proof is now complete 
by the arguments of the preceding paragraph. 

                                                                             
\begin{lemma}~\label{minimizer}
Suppose that $W^{\delta}$ maximizes $r(.,\delta)$ over ${\cal C}_{\delta}(f)$.
Let $W \in {\cal C}_{\delta}(f)$ be such that $\omega_i < \omega^{\delta}_i$.
Then 
$r(W,\delta) < r_i(\omega_i,\delta)$. 
\end{lemma} 

\proof Suppose, by way of contradiction, that $r(W,\delta) = 
r_i(\omega_i,\delta)$. Since  $r_i(.,\delta)$ is a strictly decreasing 
function, $r(W,\delta) > r_i(\omega^{\delta}_i,\delta) \geq 
r(W^{\delta},\delta)$, thereby contradicting the fact that $W^{\delta}$ 
maximizes $r(.,\delta)$. 





\proof (Theorem 3) 
Let $W^{\delta}$ be a maximum of $r(.,\delta)$.  Now construct a {\bf 
w$_{\delta}$}-tree by placing a directed edge from each {\bf w} ($\neq$ {\bf 
w$_{\delta}$}) to a convention {\bf w}$+e_{ij}$, where $\omega_i > 
\omega^{\delta}_i$ and $\omega_j < \omega^{\delta}_j$.  Intuitively, this 
procedure involves transferring $\delta$ at each stage from player $i$ who is 
demanding "too much" to a player $j$ who is demanding "too little".  Since the
core is a convex set, this "equalizing" principle can be followed to obtain a 
{\bf w$^{\delta}$}-tree.  Let $T^*$ denote this tree. 

At an edge {\bf w}$\rightarrow$ {\bf w}$+e_{ij}$, $\omega_j < 
\omega^{\delta}_j$. Hence by Lemma~\ref{minimizer}, $r(W,\delta) < 
r_j(W,\delta)$. Hence, by Part 1 of Lemma~\ref{resistance},  the resistance of
each edge in the tree $T^*$ is $$ \mbox{{\bf r(w,w$+ e_{ij}$)}} = r(W,\delta).
$$ So, the resistance of the tree  $T^*$ is 
\begin{equation}~\label{rofT} 
 \sum_{W \neq W^*} [mr(W,\delta)]. 
\end{equation}
For any other convention, say $\hat{\mbox{{\bf w}}}$, the resistance of a  
$\hat{\mbox{{\bf w}}}$-tree, say $T$ is 
\begin{eqnarray*} 
 \sum_{\mbox{{\bf (w$^1$,w$^2$)}}\in T} \mbox{{\bf r(w$^1$,w$^2$)}} & \geq &  
\sum_{ W \neq \hat{W }} [mr(W,\delta)] \\ 
 & \geq & \sum_{ W \neq W^{\delta}} [mr(W,\delta)].
\end{eqnarray*} 
The first inequality follows from Corollary~\ref{b1} and the second 
inequality is strict if $\hat{W}$ does not maximize $r(.,\delta)$.  

Hence, {\bf w$^{\delta}$} has the least stochastic potential with the
resistance 
given Eq. (~\ref{rofT}). By Theorem A, it is then a Stochastically stable 
state. 

If there are several maxima of $r(.\delta)$, each of them is a SSC. 


\proof (Theorem 4) Let $W^* \in C(f)$ be the maximum of $g$ and let 
$K$ be as in the statement of the Theorem. 
For a player $i$, let $S_i$ denote the smallest coalition $S$ that contains 
$i$ and  
$W^*(S) = f(S)$. Such an $S_i$ is well defined by Corollary~\ref{cr1}. 

For concreteness, suppose that $1 \in K$. 
Since, $g_1(\omega^*_1)  \leq g_j(\omega^*_j)$ for all $j \in 
N$, it is easy to show\footnote{Using continuity and the fact that $g_i$'s  
are strictly decreasing} that  for every $\epsilon_1 > 0$, there exists an
$\epsilon_2$ in the open interval $ (0,\epsilon_1)$ such that 
\begin{equation}~\label{minimum}
g_1(\omega_1^* + \epsilon_1)  <  g_j(\omega_j^* + \epsilon_2).
\end{equation} 


Now, suppose that there is a player $j \neq 1$ such that $1 \in S_j$.  
 (The case when no such $j$ exists will be analyzed shortly.)  At $W^*$ then, 
we can reduce the demand of $j$ by an arbitrarily small 
$\epsilon > 0$ and correspondingly increase the demand of $1$ and yet remain 
in the core. Hence for all $0 < \epsilon_2 < \epsilon_1 < 
\epsilon/(n+1)$, there exists a $W \in {\cal C}(f)$ such that 
$\omega_1^*+\epsilon_1 < \omega_1 < 
\omega_1^*+\epsilon/(n+1)$ and $\omega_j < \omega^*_j + \epsilon_2$, for all $j
\neq 1$.  
Note that with our method of discretization, $ {\cal C}_{\delta}(f) \subset 
{\cal C}_{\delta^{'}}(f)$ when $\delta < \delta^{'}$ and $\cup_{\delta} {\cal 
C}_{\delta}(f) = {\cal C}(f)$. Hence, we can find  a $\delta^* > 0$ and a $W 
\in {\cal C}_{\delta^*}(f)$ so that for all $\delta < \delta^*$, 
$\omega_1^*+ \epsilon_1 \leq \omega_1 - \delta < \omega_1 
\leq \omega^*_1 + \epsilon/(n+1)$  and  for $j (\neq 1) \in N$, $\omega_j \leq
\omega^*_j + \epsilon_2$. In fact, pick $\epsilon_1$ and $\epsilon_2$ such 
that Eq.~\ref{minimum} is satisfied. Then, 
\begin{eqnarray} 
r_1(\omega_1,\delta) & \leq & g_1(\omega_1^*+\epsilon_1) \nonumber \\ 
                     & < & g_j(\omega^*_j+\epsilon_2)  \nonumber\\ 
                     & \leq & r_j(\omega_j,\delta),       
\end{eqnarray}
for all $j \in N$. Hence,  $r(W,\delta) = r_1(\omega_1,\delta)$.  Now apply 
Lemma~\ref{minimizer} to conclude that if 
$W^{\delta}$ maximizes $r(.,\delta)$ over ${\cal C}_{\delta}(f)$, then 
\begin{equation}~\label{upperinq} 
\omega^{\delta}_1  \leq  \omega^*_1 + \frac{\epsilon}{n+1}.
\end{equation}

Now if $1 \not\in S_1$ for every $j \neq 1$, then $ S_j \subseteq 
N \backslash 1$.  Apply Corollary~\ref{cr1} to conclude 
that $ W^*(N \setminus 1) =f(N \setminus 1) $ 
and hence $\omega^*_1 = f(N) - f(N \setminus 1)$, the largest payoff that 
player $1 $ can obtain in the core. Hence, Eq.~\ref{upperinq} follows 
immediately.





To obtain a lower bound on $\omega^{\delta}_1$, first note that there in no 
loss in generality in assuming that Eq.~\ref{upperinq} holds for all players 
in $K$ for the same $\epsilon$. Second, I claim that $W^*(K) = f(K)$. 
To see this, consider a player $j \in S_1$. If  $g_1(\omega_1^*) < 
g_j(\omega_j^*)$, we can increase the demand of player $j$ by a small amount 
while decreasing the demand of player $1$ while remaining in the core. 
By\footnote{A formal argument involves a standard application of Taylor's 
theorem} doing this, we increase the value 
of $g$ and this contradicts the fact that $g$ is maximized at $W^*$.  
Hence, $g_j(\omega_j^*) \leq g_1(\omega^*_1)$. But this implies $S_1 \subseteq
K$. Hence $\cup_{i \in K} S_i = K$ and using Corollary~\ref{cr1}, $W^*(K) = 
f(K)$.  

It is now easy to verify that if $\omega^{\delta}_1 < \omega^*_1 - 
\frac{n}{n+1} \epsilon$,  then there must be a player $j \in K$ such 
that $\omega_i^{\delta} >  \omega^*_j + \frac{\epsilon}{n+1}$, thereby
violating 
Eq.~\ref{upperinq}. 

Hence, for all $i \in K$, and for all $0 < \delta \leq \delta^*$,
$$ \mid \omega^{\delta}_i - \omega^*_i \mid <  \epsilon. 
$$ 


\end{document}

