%Paper: ewp-game/9709001
%From: hart@math.huji.ac.il
%Date: Sun, 28 Sep 97 15:55:41 CDT

%% This document created by Scientific Word (R) Version 2.5


\documentclass[12pt,thmsa,a4paper]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{sw20lart}

%TCIDATA{TCIstyle=article/art4.lat,lart,article}

%TCIDATA{Created=Mon Jun 02 15:01:17 1997}
%TCIDATA{LastRevised=Tue Sep 02 14:46:46 1997}
%TCIDATA{Language=American English}

\input{tcilatex}
\begin{document}

\title{Efficiency Does Not Imply Immediate Agreement\thanks{%
Research conducted in 1993-1994.}}
\author{Sergiu Hart\thanks{%
Department of Economics; Department of Mathematics; and Center for
Rationality and Interactive Decision Theory, The Hebrew University of
Jerusalem. \emph{e-mail:} hart@\protect\nolinebreak math.huji.ac.il.
Research partially supported by grants of the U.S.-Israel Binational Science
Foundation and the Israel Academy of Sciences and Humanities.} \and Zohar
Levy\thanks{%
Department of Computer Science, The Hebrew University of Jerusalem. \emph{%
e-mail: }zohar@cs.huji.ac.il.}}
\date{July 1997}
\maketitle

\begin{abstract}
Gul [1989] introduces a non-cooperative bargaining procedure and claims that
the payoffs of the resulting efficient stationary subgame perfect equilibria
are close to the Shapley value of the underlying transferable utility game
(when the discount factor is close to $1$). We exhibit here an example
showing that efficiency, even for strictly super-additive games, does \emph{%
not} imply that all meetings end in agreement. Thus efficiency does not
suffice to get Gul's result. \emph{Journal of Economic Literature}
Classification Numbers: C71, C72, C78, D4.
\end{abstract}

%TCIMACRO{\TeXButton{setlength}{\setlength{\baselineskip}{.25in}}}
%BeginExpansion
\setlength{\baselineskip}{.25in}%
%EndExpansion
%TCIMACRO{
%\TeXButton{References Without Numbers}{
%\def\@biblabel#1{#1\hfill}
%\def\thebibliography#1{\section*{References}\list
%{}{
%   \labelwidth 0pt
%   \leftmargin 1.8em
%   \itemindent -1.8em
%   \usecounter{enumi}}
%\def\newblock{\hskip .11em plus .33em minus .07em}
%\sloppy\clubpenalty4000\widowpenalty4000
%\sfcode`\.=1000\relax\def\baselinestretch{1}\large \normalsize}
%\let\endthebibliography=\endlist}}
%BeginExpansion

\def\@biblabel#1{#1\hfill}
\def\thebibliography#1{\section*{References}\list
{}{
   \labelwidth 0pt
   \leftmargin 1.8em
   \itemindent -1.8em
   \usecounter{enumi}}
\def\newblock{\hskip .11em plus .33em minus .07em}
\sloppy\clubpenalty4000\widowpenalty4000
\sfcode`\.=1000\relax\def\baselinestretch{1}\large \normalsize}
\let\endthebibliography=\endlist%
%EndExpansion

In a most interesting and important paper, Gul [1989] provides a bargaining
procedure leading to the Shapley [1953] value for games with transferable
utility.\footnote{%
For other bargaining models generating the Shapley value, see: Harsanyi
[1981]; Mas-Colell [1988]; O. Hart and Moore [1990]; Winter [1994]; S. Hart
and Mas-Colell [1996].} The main result there (Theorem 1) states that the
payoffs of efficient stationary subgame perfect Nash equilibria are close to
the Shapley value, when the discount factor is close to $1$.

The non-cooperative game proceeds as follows: At every period, there is a
meeting between two randomly chosen players: a ``proposer'' $i$ and a
``responder'' $j$. The proposer makes an offer to ``buy out'' the responder
(for a certain amount); the responder may either accept or reject the offer.
In the former case, $j$ ``leaves'' the game and $i$ ``represents'' $j$ in
all subsequent periods. At the end of each period, each player which is
still in the game gets a payoff equal to the worth of the coalition of
players that he represents. Let $Q_{t}$ denote the resulting partition of
the set of players at time $t$ (i.e., $Q_{t}:=\{M_{t}^{i}:i$ is in the game
at time $t\},$ where $M_{t}^{i}$ is the set of all players represented by $i$
at stage $t$), then the sum of payoffs of all players is 
\[
W\equiv W(N,v;\delta ):=(1-\delta )\sum_{t=0}^{\infty }\sum_{M_{t}^{i}\in
Q_{t}}\delta ^{t}v(M_{t}^{i}), 
\]
where $(N,v)$ is the given coalitional game and $\delta $ is the (common to
all players) discount factor.

A strategy profile (i.e., an $N-$tuple of strategies) $\sigma $ is \emph{%
efficient} if there is no other strategy profile $\tau $ such that the
expected sum of payoffs of all players is higher for $\tau $ than for $%
\sigma $; that is, $E_{\sigma }(W)=\max_{\tau }E_{\tau }(W).$

The underlying coalitional game $(N,v)$ is assumed to be \emph{strictly
super-additive}, i.e. 
\[
v(L)+v(M)<v(L\cup M) 
\]
for all non-empty $L,M\subset N$ with $L\cap M=\emptyset $.

Efficiency is used in Gul's proof in order to guarantee that every meeting
ends in agreement. The intuition is that, by strict super-additivity, there
will otherwise be a loss in total utility.\footnote{%
This is claimed without proof in Gul's paper; it was considered to be clear
and trivially true (F. Gul, private communication, 1993).}

However, this is not so. Consider the following example $(N,v_{1})$: There
are 8 players, $N:=\{1,2,3,4,5,6,7,8\}.$ Each one of the last six players ($%
3,...,8$) initially owns one unit of a raw material (that yields no direct
utility to any player). As for the first two players, $1$ and $2,$ each one
owns a constant returns to scale technology that transforms the raw material
into utils, in the ratio 1-to-1. The coalitional function $v_{1}$ is thus%
\footnote{%
The game $v_{1}$ is super-additive but not \emph{strictly} super-additive;
we will modify it slightly below. Notation: $\left| S\right| $ is the number
of elements of the finite set $S.$} 
\[
v_{1}(S)=\left\{ 
\begin{tabular}{lll}
$0,$ &  & if $S\cap \{1,2\}=\emptyset ;$ \\ 
$\left| S\right| -1,$ &  & if $\left| S\cap \{1,2\}\right| $ $=1;$ and \\ 
$\left| S\right| -2,$ &  & if $S\supset \{1,2\};$%
\end{tabular}
\right. 
\]
for all $S\subset N.$ Clearly, $1$ and $2$ are perfect substitutes.
Moreover, putting them together in the same coalition is the same as
eliminating one of them: $v_{1}(S\cup \{1,2\})=v_{1}(S\cup
\{1\})=v_{1}(S\cup \{2\})$ for any $S.$ Therefore, in a ``meeting
procedure'' where, at each step, two existing coalitions are chosen at
random, it is easier for the inputs (of players $3,$ ...$,8)$ to find a
matching ``technology'' (i.e., players $1,2$) if $1$ and $2$ are kept apart
as long as possible. This way each one of the two has a chance to form a
separate productive coalition. In short, it is more efficient to have two
separate ``factories'' rather than one.

This argument fits well Gul's pairwise meeting procedure. Indeed, it turns
out that \emph{if }$1$\emph{\ and }$2$\emph{\ meet in the first round}
(which happens with probability $1/28$), then it is \emph{more efficient}
that this meeting should \emph{not end in agreement}. It is better to wait
for the next round, where there is a high probability (of $27/28)$ that they
will not meet again. This increases the chance that $1$ and $2$ will be able
to form separate coalitions (with the other players) before they eventually
meet again---which increases the total payoff. A precise computation%
\footnote{%
See the Appendix.} shows that:

\begin{itemize}
\item  For any strategy profile $\sigma $ where all meetings end in
agreement 
\begin{equation}
E_{\sigma }(W(N,v_{1};\delta ))=\frac{3}{7}\delta +\frac{51}{98}\delta ^{2}+%
\frac{9}{14}\delta ^{3}+\frac{198}{245}\delta ^{4}+\frac{36}{35}\delta ^{5}+%
\frac{9}{7}\delta ^{6}+\frac{9}{7}\delta ^{7}.  \label{sigma}
\end{equation}

\item  For any strategy profile $\tau $ where all meetings end in agreement,
except for first round meetings between $1$ and $2$ 
\begin{eqnarray}
E_{\tau }(W(N,v_{1};\delta )) &=&\frac{3}{7}\delta +\frac{103}{196}\delta
^{2}+\frac{5333}{8232}\delta ^{3}+\frac{955}{1176}\delta ^{4}+\frac{3529}{%
3430}\delta ^{5}  \label{tau} \\
&&+\frac{937}{735}\delta ^{6}+\frac{727}{588}\delta ^{7}+\frac{9}{196}\delta
^{8}.  \nonumber
\end{eqnarray}
\end{itemize}

It may now be checked that $E_{\tau }(W(N,v_{1};\delta ))>E_{\sigma
}(W(N,v_{1};\delta ))$ for all $0<\delta <1.$ The strict inequality is
preserved if we modify $v_{1}$ slightly so as to make it strictly
super-additive. Specifically, let $\varepsilon >0$ and define $%
v_{2}:=v_{1}+\varepsilon v_{0}$, where $v_{0}(S):=\left| S\right| ^{2}$ for
all $S.$ The game $v_{2}$ is strictly super-additive (since $v_{0}$ is
such), and satisfies 
\begin{equation}
E_{\tau }(W(N,v_{2};\delta ))>E_{\sigma }(W(N,v_{2};\delta ))\text{ for all }%
\delta \in (\delta _{0},1),  \label{eq1}
\end{equation}
whenever $\varepsilon >0$ is chosen appropriately small.\footnote{%
Precisely: For every $\delta _{0}>0$ there exists $\varepsilon _{0}\equiv
\varepsilon _{0}(\delta _{0})>0$ such that (\ref{eq1}) is satisfied by any
game $v_{2}=v_{1}+\varepsilon v_{0}$ with $\varepsilon \in [0,\varepsilon
_{0});$ see the Appendix.}

\bigskip We conclude with a number of remarks:

\begin{enumerate}
\item  The example was generated as follows: For any game with at most $4$
players, it can be shown that $\sigma $ Pareto dominates $\tau .$ For $5$
players, the difference $\Delta :=E_{\tau }(W)-E_{\sigma }(W)$ is a linear
combination of the worths $v(S),$ with those coalitions $S$ that contain
exactly one of $1$ and $2$ having positive coefficients, and the other
coalitions---that contain neither $1$ nor $2,$ or contain both---having
negative coefficients. In order to make the difference $\Delta $ positive,
one therefore takes the worths of the first kind of coalitions as large as
possible, and the worths of the others as small as possible. Together with
super-additivity, it leads to the game $v_{1}.$ It then turns out that $\tau 
$ Pareto dominates $\sigma $ for all $\delta $ in a neighborhood of $0$
(specifically: $\delta \in (0,\delta _{0})$ where $\delta _{0}\approx 0.37$%
). Finally, to get the same result also for $\delta $ close to $1,$ we need
to increase the number of players to $8.$

\item  We do not claim that $\tau $ is efficient (only that $\sigma $ is
not). In particular, if $1$ and $2$ meet in the first as well as in the
second round, then of course they should not agree in the second round
either (actually, they should not agree as long as the partition is still
the trivial partition into singletons).

\item  The statement in Gul's paper refers to equilibrium points. The
example above does not rule out the possibility that efficient stationary
subgame perfect equilibria entail agreement at every meeting. (But at this
point there is neither a proof nor any intuitive reason why this should be
so.)

\item  The results in Gul's paper thus need to be restated, replacing
``efficient'' by ``such that all meetings end in agreement''.
\end{enumerate}

\appendix

\section{Appendix}

Let $N=\{1,2,...,n\}$ be the set of players$.$ The computations proceed as
follows: Denote by $A$ the event that $1$ and $2$ meet in the first round,
and write $E(W)=E(W|A)P(A)+E(W|A^{C})P(A^{C})$, where $A^{C}$ is the
complement of $A;$ note that the probability $P(A)$ of $A$ is $1/\binom{n}{2}
$. The second term is the same for both $\sigma $ and $\tau .$ As for the
first term, 
\begin{eqnarray*}
E_{\tau }(W(N,v;\delta )|A) &=&(1-\delta )\sum_{i\in N}v(i)+\delta E_{\sigma
}(W(N,v;\delta ))\text{ and} \\
E_{\sigma }(W(N,v;\delta )|A) &=&(1-\delta )\sum_{i\in N}v(i)+\delta
E_{\sigma }(W(N_{12},v;\delta )),
\end{eqnarray*}
where $N_{12}:=\{\{1,2\},3,4,...,n\}.$ Thus, denoting $\Delta (v):=E_{\tau
}(W(N,v;\delta )-E_{\sigma }(W(N,v;\delta ),$we get 
\[
\Delta (v)=\delta \frac{1}{\binom{n}{2}}\left( E_{\sigma }(W(N,v;\delta
))-E_{\sigma }(W(N_{12},v;\delta ))\right) .
\]
At this point we use MAPLE:
\begin{verbatim}
####
# strategy profiles:
#   sigma = 'always agreement'
#   tau = 'no agreement between 1,2 in first round'
# EW(v,Q) := expected sum of payoffs starting from
#   partition Q for sigma
# total(v,Q) := contribution to EW of Q in the
#   current round, together with all future rounds
#   (recursively), up to (and not including)
#   the grand coalition
# sumv(v,Q) := sum of v(S) over S in partition Q
# n := number of players
# single(n) := {{1},{2}, ... , {n}}
# double(n) := {{1,2},{3},{4},...,{n}}
# DEW(n,v) := difference between tau and sigma
#   when positive: counterexample!
####
sumv := proc(v, Q) local S, result; option remember;
  result := 0;
  for S in Q do  result := result + v(S)  od;
  result;
end;
####
total := proc(v, Q) local result, i, j, c, Q1;
  option remember;
  if nops(Q) = 1 then RETURN(0) fi;
  result := sumv(v, Q);
  c := delta*2/(nops(Q)*(nops(Q) - 1));
  for i to nops(Q) - 1 do
  for j from i + 1 to nops(Q) do
    Q1 := (Q minus {op(i,Q),op(j,Q)})
            union {op(i,Q) union op(j,Q)};
    result := result + c*total(v, Q1);
  od; od;
  result;
end;
####
EW := (v, Q) -> (1 - delta)*(total(v, Q)
   + v(`union`(op(Q)))*sum(delta^t,t=nops(Q)-1..infinity));
####
single := n -> {{i} $ i=1..n};
double := n -> single(n) minus {{1},{2}} union {{1,2}};
DEW := (n, v) ->
     (EW(v,single(n)) - EW(v,double(n)))*delta*2/(n*(n-1));
####
# the games v1 and v0
####
v1 := proc(S) local m; option remember;
  m:=nops (S intersect {1,2});
  if m = 0 then 0 else nops(S)-m fi;
end;
v0 := S -> nops(S)^2;
####
for n from 3 to 8 do
  'E[sigma](W(v[1]))' = EW(v1, single(n));
  'E[tau](W(v[1]))' = EW(v1, single(n)) + DEW(n, v1);
  'E[tau](W(v[1]))-E[sigma](W(v[1]))' = DEW(n, v1);
  'E[tau](W(v[0]))-E[sigma](W(v[0]))' = DEW(n, v0);
od;
####
\end{verbatim}

For $n=8,$ this yields the formulas (\ref{sigma}) and (\ref{tau}). The
difference $\Delta (v_{1})=E_{\tau }(W(N,v_{1};\delta ))-E_{\sigma
}(W(N,v_{1};\delta ))$ equals 
\[
\Delta (v_{1})=\delta ^{2}(1-\delta )\left[ \frac{1}{196}+\frac{83}{8332}%
\delta +\frac{24}{1715}\delta ^{2}+\frac{1}{70}\delta ^{3}+\frac{1}{294}%
\delta ^{4}-\frac{9}{196}\delta ^{5}\right] . 
\]
The polynomial $p(\delta )$ in the square brackets $\left[ \quad \right] $
has one root between $1$ (where it is positive) and $2$ (where it is
negative), which is moreover its unique non-negative root (by Descartes'
Rule of Signs). Therefore there is $c>0$ such that $p(\delta )\geq c$ for all%
\footnote{%
A precise computation shows that we may take $c=13/13720$ (the minimal value
of $p$ in the interval $[0,1]$ is at $1$).} $\delta \in [0,1]$. Hence $%
\Delta (v_{1})\geq c\delta ^{2}(1-\delta )>0$ for all $\delta \in (0,1).$

Considering now $v_{0},$ we get $\Delta (v_{0})=-\delta (1-\delta
)(35+45\delta +60\delta ^{2}+84\delta ^{3}+126\delta ^{4}+210\delta
^{5}+420\delta ^{6})/490$, which is $\geq -2\delta (1-\delta )$ for all $%
\delta \in [0,1].$ This yields for $v_{2}:=v_{1}+\varepsilon v_{0}$%
\[
\Delta (v_{2})\geq c\delta ^{2}(1-\delta )-2\varepsilon \delta (1-\delta
)=\delta (1-\delta )\left( c\delta -2\varepsilon \right) . 
\]
To make this difference positive for all $\delta \in (\delta _{0},1),$ take $%
\varepsilon $ $<c\delta _{0}/2.$\pagebreak

\begin{thebibliography}{9}
\bibitem{}  Gul, F. [1989], ``Bargaining Foundations of Shapley Value'', 
\emph{Econometrica} 57, 81--95.

\bibitem{}  Harsanyi, J.C. [1985], ``The Shapley Value and the Risk
Dominance Solutions of Two Bargaining Models for Characteristic-Function
Games'', \emph{Essays in Game Theory and Mathematical Economics}, R.J.
Aumann \emph{et al }(eds.), Bibliographisches Institut Mannheim, 43--68.

\bibitem{}  Hart, O. and J. Moore [1990], ``Property Rights and the Nature
of the Firm'', \emph{Journal of Political Economy} 98, 1119--1157.

\bibitem{}  Hart, S. and A. Mas-Colell [1996], ``Bargaining and Value'', 
\emph{Econometrica} 64, 357--380.

\bibitem{}  Mas-Colell, A. [1988], ``Algunos Comentarios sobre la Teoria
Cooperativa de los Juegos'', \emph{Cuadernos Economicos} 40, 143--161.

\bibitem{}  Shapley, L.S. [1953], ``A Value for $n$-Person Games'', \emph{%
Contributions to the Theory of Games} II (\emph{Annals of Mathematics Studies%
} 28), H.W. Kuhn and A.W. Tucker (eds.), Princeton University Press,
307--317.

\bibitem{}  Winter, E. [1994], ``The Demand Commitment Bargaining and
Snowballing Cooperation'', \emph{Economic Theory} 4, 255--273.
\end{thebibliography}

\end{document}