\documentclass{amsart}
\usepackage{amssymb,harvard}
%\usepackage{showkeys}

\newtheorem{theorem}{\indent Theorem}
\newtheorem{proposition}{\indent Proposition}
\newtheorem{lemma}{\indent Lemma}
\newtheorem{corollary}[theorem]{\indent Corollary}
\newtheorem{conjecture}[theorem]{\indent Conjecture}
\theoremstyle{definition}
\newtheorem{definition}{\indent Definition}
\newtheorem{assumption}{\indent Assumption}
%%
%\def\bibindent{\hangindent=3pc \hangafter=1 \noindent}
\newcommand{\fignumber}[1]{\refstepcounter{figure} \bigskip
\begin{center} Figure \thefigure \end{center} \label{fig:#1} }
\newcommand{\figref}[1]{\ref{fig:#1}}
\newcommand{\lar}{\longrightarrow }

\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\veps}{\varepsilon}

%%
%%end of definitions
%%

\begin{document}

\title{On the Finiteness of Stable Sets}

%\thanks{}

\author{John Hillas}
\address{Institute for Decision Sciences
and Department of Economics \\
SUNY at Stony Brook \\
Stony Brook, NY 11794-4384 USA}
\email{John.Hillas@sunysb.edu}
\author{Dries Vermeulen}
\address{Department of Quantitative Economics, University of Limburg,
      P.O. Box 616, 6200 MD Maastricht, The Netherlands}
\email{a.vermeulen@ke.rulimburg.nl}
\author{Mathijs Jansen}
\address{Department of Quantitative Economics, University of Limburg,
      P.O. Box 616, 6200 MD Maastricht, The Netherlands}
\email{m.jansen@ke.rulimburg.nl}



\date{June, 1996}

\begin{abstract}
For two person games, stable sets in the sense of Kohlberg and Mertens
and quasi-stable sets in the sense of Hillas are finite. In this paper
we present an example to show that these sets are not necessarily finite
in games with more than two players.
\end{abstract}

\maketitle
\renewcommand{\thepage}{}%\roman{page}}

\tableofcontents

\newpage
\renewcommand{\thepage}{\arabic{page}}

\setcounter{page}{1}

\section{Introduction}
\label{sec:intro}


In their seminal paper, \citeasnoun{KM-Econ} defined a number of
solutions of noncooperative games in which the solution of a game is a
collection of closed subsets of equilibria. Formally this means that a
solution is a map assigning to a game a collection of closed subsets of
its strategy space. As well as defining a number of particular solutions
Kohlberg and Mertens  gave a list of properties such solutions should
satisfy. Because these definitions were all based on the idea that a
``solution set'' must be stable against certain perturbations of the
game, they called the solutions sets stable sets.

To differentiate it from other definitions that have appeared in the
literature we shall  call KM-stable sets the solution that they
called ``stable sets.'' None of the solutions defined by Kohlberg and
Mertens actually satisfies all of the properties they proposed.  A
number of those properties already imply that stable sets must in some
games be infinite.  In many games it is clear that  sets satisfying the
requirements cannot be singletons.  Thus if the solution were to be a
connected set (one of the requirements) it must be infinite.  Two other
requirements are that the stable set should contain a sequential
equilibrium of the game and that the solution depend only on the
reduced normal form of the game and not on other ``irrelevant'' details
of the game.  Kohlberg and Mertens give an example in which, as the
game is changed in a manner that leaves the reduced normal form
unchanged, the unique sequential equilibrium of the game traces out an
interval of equilibria.  Thus any solution satisfying the requirements
of Kohlberg and Mertens must necessarily be infinite valued in this game.
Nevertheless \citeasnoun{JJB-strict} showed that for a two
person game all KM-stable sets are finite.

\citeasnoun{JF-reform1} and \citeasnoun{hillas-definition} defined
solutions that do satisfy all of the properties of Kohlberg and Mertens.
Hillas also introduced an intermediate concept, not satisfying the
requirements, that he called quasi-stable sets. \citeasnoun{VPJ-quasi}
proved that for two person games these sets are also finite.

In this paper we will show that these results cannot be extended to
normal form games with more than two players. We will present a
three-player normal form game whose unique KM-stable set includes a line
segment (so it is clearly not a finite set). Since each quasi-stable set
contains a KM-stable set, this example is also a counterexample for the
finiteness of quasi-stable sets for games with more than two players.


\section{Preliminaries}

In this section we give a brief and informal description of the
concepts with which we are concerned.  More formal and precise
treatments are to be found in \citeasnoun{KM-Econ}, and in the other
references.  We assume that the reader is familiar with the basic
notions of a game and of a strategic equilibrium.

A KM-perturbation (or a Selten-perturbation) of a game associates with
each pure strategy of each player a positive number representing the
minimum probability with which that strategy may be played.  A
perturbation is small if each of these minimum probabilities is small.
The game in which each player is required to play each strategy with
that minimum probability is called the perturbed game.  A closed set $S$
of strategy profiles is  KM-stable if it is minimal with respect to the
following property: every neighborhood of $S$ contains at least one
equilibrium of any sufficiently small perturbation of the game.

A strategy profile is a perfect equilibrium \cite{selten-perfect}
if there is a sequence of KM-perturbations converging to zero and a
sequence of equilibria of the perturbed games that converge to the
perfect equilibrium.

\section{The Counterexample}

Consider the three player game of Figure~\figref{example}. Here Player~I
chooses rows, Player~II columns, and Player~III matrices. We shall show
that any KM-stable set of this game contains a line segment of
equilibria.  Let $ \eta = \bigl( (\gamma_1, \gamma_2), (\delta_1,
\delta_2), (\varepsilon_1, \veps_2, \veps_3) \bigr)$ be a
KM-perturbation for this game and let $\bigl( (x_1, x_2), (y_1, y_2),
(z_1, z_2, z_3) \bigr)$ be an equilibrium of the perturbed game. Because
the pure strategies $C$ and $E$ of Player III are strictly dominated by
$W$, Player~III will play those two strategies with minimum weight in
any equilibrium, that is, $(z_1, z_2, z_3) = (1 - \veps_2 - \veps_3,
\veps_2, \veps_3)$. And so $\bigl( (x_1, x_2), (y_1, y_2) \bigr)$ must
be an equilibrium of the $\bigl((\gamma_1, \gamma_2), (\delta_1,
\delta_2) \bigr)$-perturbation of the game of Figure~\figref{subgame}.


\begin{figure}[htbp]
{\renewcommand{\arraystretch}{1.5}
\[
\begin{array}{c|c|c|c|c|c|c|c|c|}
\multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} &
\multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} &
\multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R}
\\ \cline{2-3} \cline{5-6} \cline{8-9}
T & 1,0,1 & 0,0,1 && 1,0,0 & 0,0,0 && 1,0,0 & 0,1,0 \\ \cline{2-3}
\cline{5-6} \cline{8-9}
B & 0,0,1 & 1,0,1 && 0,1,0 & 1,0,0 && 0,0,0 & 1,0,0 \\ \cline{2-3}
\cline{5-6} \cline{8-9}
\multicolumn{1}{c}{} & \multicolumn{2}{c}{W} & \multicolumn{1}{c}{}   &
\multicolumn{2}{c}{C} & \multicolumn{1}{c}{} & \multicolumn{2}{c}{E}
\end{array}
\]
}
\fignumber{example}
\end{figure}


\begin{figure}[htbp]
{\renewcommand{\arraystretch}{1.5}
\[
\begin{array}{c|c|c|}
\multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R}
\\ \cline{2-3}
T & 1,0 & 0,\veps_3 \\ \cline{2-3}
B & 0,\veps_2 & 1,0 \\ \cline{2-3}
\end{array}
\]
}
\fignumber{subgame}
\end{figure}

For $\gamma_1,\gamma_2 < \frac{1}{2}$, the perturbations may be divided into
the following five mutually exclusive and completely exhaustive sets.
\begin{align*}
S_2 &= \left \{ \eta \mid \veps_2 < \gamma_1(\veps_2 + \veps_3)  \right \} \\
T_2 &= \left \{ \eta \mid \veps_2 = \gamma_1(\veps_2 + \veps_3) \right \} \\
S_{23} &= \left \{ \eta \mid \veps_2 > \gamma_1(\veps_2 + \veps_3)
\mbox{ and } \veps_3 > \gamma_2(\veps_2 + \veps_3)  \right \} \\
T_3 &= \left \{ \eta \mid \veps_3 = \gamma_2(\veps_2 + \veps_3) \right \} \\
S_3 &= \left \{ \eta \mid \veps_3 < \gamma_2(\veps_2 + \veps_3)  \right \}
\end{align*}
On these five sets we now calculate the equilibria of the perturbed
games.
\begin{description}
\item[$S_2$] $x_2 \veps_2 \leq (1-\gamma_1)\veps_2 < \gamma_1\veps_3 \leq
x_1 \veps_3$. Thus Player~II strictly prefers $R$ to $L$, and so $(y_1,y_2) =
(\delta_1,1-\delta_1)$. Then Player~I strictly prefers $B$ to $T$, and so
$(x_1,x_2) = (\gamma_1,1-\gamma_1)$.
\item[$T_2$] If $x_1> \gamma_1$ then, as in the previous case (changing only
the location of the strict inequality), $x_1 = \gamma_1$, a contradiction.
Thus $(x_1,x_2) = (\gamma_1,1-\gamma_1)$, and so $B$ must be at least as good
as $T$ for Player~I. Thus $(y_1,y_2)$ is an element of the set
$\left \{ (y,1-y) \mid \delta_1 \leq y \leq \frac{1}{2} \right \}$.
\item[$S_{23}$] There is a unique equilibrium. In it $(x_1,x_2) = \left (
\veps_2/(\veps_2 + \veps_3),\veps_3/(\veps_2 + \veps_3) \right )$ and
$(y_1,y_2) = \left (\frac{1}{2},\frac{1}{2} \right )$.
\item[$T_3$] Similarly to $T_2$, $(x_1,x_2) = (1-\gamma_2,\gamma_2)$ and
$(y_1,y_2)$ is an element of the set \linebreak
$\left \{ (y,1-y) \mid \frac{1}{2} \leq y \leq 1 - \delta_2 \right \}$.
\item[$S_3$] Similarly to $S_2$, $(x_1,x_2) = (1-\gamma_2,\gamma_2)$ and
$(y_1,y_2) = (1-\delta_2,\delta_2)$.
\end{description}

The behavior of the equilibrium correspondence on $S_{23}$ means that any
KM-stable set must include $\left \{ \left( (s,1-s),(\frac{1}{2},
\frac{1}{2}), (1,0,0)\right) \mid 0 \leq s \leq 1 \right \}$; on $S_2$ that
it must include $\left( (0,1),(0,1), (1,0,0)\right) $; and on $S_3$ that it
must include $\left( (1,0),(1,0), (1,0,0)\right) $. Moreover any set that
contains all of these points \emph{is} a KM-stable set, and so, since
KM-stability includes a minimality requirement, this is the unique KM-stable
set.  Since any quasi-stable set contains a KM-stable set, any
quasi-stable set of this game must also be infinite.
     
For completeness we note that the set of perfect equilibria also includes the
sets
\[
\left \{ \left ( (0,1),(t,1-t),(1,0,0)\right) \mid 0\leq t \leq {\textstyle
\frac{1}{2}} \right \}
\]
and
\[\left \{ \left ( (1,0),(t,1-t),(1,0,0)\right) \mid {\textstyle \frac{1}{2}}
\leq t \leq 1 \right \}.
\]
Since any stable set in the sense of
\citeasnoun{JF-reform1} or of \citeasnoun{hillas-definition} is a
connected set of perfect equilibria containing a KM-stable set, in this game
the unique stable set in either of these senses coincides with the set of all
perfect equilibria.


\nocite{JF-reform2}
\nocite{nash-equil1}
\nocite{selten-perfect}

\bigskip

%\newpage

\bibliographystyle{hillas}

\bibliography{steq}


\end{document}