

\documentclass[12pt]{article}
\usepackage{amsmath,amsthm, amssymb,latexsym,enumitem,hyperref}
%\usepackage{amssymb}\usepackage{txfonts}\usepackage{amsfonts}
%\documentclass[notheorems]{beamer}
%\documentclass{beamer}

%\usepackage[landscape,top=2cm, bottom=2cm,left=2.4cm, right=15cm,marginparwidth=10cm]{geometry}
\usepackage[landscape,top=3cm, bottom=3cm,left=3cm, right=3cm,marginparwidth=4cm]{geometry}
\usepackage[title,titletoc,toc]{appendix}
\usepackage{graphics}
\usepackage[english]{babel}

%\usepackage[latin1]{inputenc}
\usepackage{multicol}
\usepackage{times}
%\usepackage{hyperref}
%\PassOptionsToPackage{hyphens}{url}
\usepackage{hyperref}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}

\newcommand{\bbfamily}{\fontencoding{U}\fontfamily{bbold}\selectfont}
\DeclareMathAlphabet{\mathbbold}{U}{bbold}{m}{n}

\def\pound{\mbox{£}}
%\renewcommand\appendix{\par
%  \setcounter{section}{0}
%  \setcounter{subsection}{0}
%  \setcounter{figure}{0}
%  \setcounter{table}{0}
%  \renewcommand\thesection{Appendix \Alph{section}}
%  \renewcommand\thefigure{\Alph{section}\arabic{figure}}
%  \renewcommand\thetable{\Alph{section}\arabic{table}}
%}

%\beamerdefaultoverlayspecification{<+->}

\usepackage{xcolor}
\usepackage{amsthm}
\theoremstyle{definition}
%\setbeamertemplate{footline}[page number]{}

%\setbeamertemplate{footline}[text line]{%
%  \parbox{\linewidth}{\vspace*{-8pt}Differential Equations MA2AA1 \,\,\, {\bf \insertsection} \hfill\insertshortauthor\hfill\insertpagenumber}}
%\setbeamertemplate{navigation symbols}{}
%\setbeamertemplate{section}[numbered]

%\def\blue{\bf}
\def\R{\mathbb R}
\def\C{\mathbb C}
\def\ZZ{\mathbb Z}
\def\interior{\mbox{int\,}}
\newcommand\nm[1]{|| #1 ||}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}

%
\def\LC{}

\def\minpt{\tilde x}
\def\minpty{\tilde y}

%%% SSS added lines below
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\setbeamertemplate{theorem begin}
%{%
%{%
%\textup{{\large \structure{%
%\inserttheoremname %. \,
%\inserttheoremnumber
%%\ifx\inserttheoremaddition\@empty\else\ (\inserttheoremaddition)\fi%
%\inserttheorempunctuation \,
%}}}%
%}%
%}%
%\setbeamertemplate{theorem end}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\setbeamertemplate{proof begin}
%{%
%{%
%\textup{{\large {\bf Proof:} %\structure{%
%%\inserttheoremname %. \,
%%\inserttheoremnumber
%%\ifx\inserttheoremaddition\@empty\else\ (\inserttheoremaddition)\fi%
%%\inserttheorempunctuation \,
%}}%}%
%}%
%}%
%\setbeamertemplate{proof end}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
\def\frame#1{}
\newtheorem{rem}{Remark}
%\newtheorem*{definition}{Definition}
\newtheorem*{dfn}{Definition}
\newtheorem*{definition}{Definition}
\newtheorem*{dfns}{Definition}
\newtheorem*{fct}{Fact}
\newtheorem{exm}{Example}
\newtheorem{exercise}{Exercise}
\newtheorem{example}{Example} %QQQQ
\newtheorem{prp}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{question}{Question}
\newtheorem{ans}{Answer}
\newtheorem{wans}{\it Wrong Answer}
\def\R{\mathbb R}
\def\marginparr#1{\marginpar{#1}}
%\def\marginparr#1{}
%\def\llink{\href}


%\author{Sebastian van Strien (Imperial College)}
%\title{M?PA48  Games and Dynamics: Lecture Notes}
%\date{Autumn 2015}

\begin{document}
\pagenumbering{roman}
%\setcounter{page}{-1}

\pagestyle{empty}

%\maketitle






%\tableofcontents
%\newpage 
\pagestyle{plain}
%%{Contents}
%{\tiny %\frametitle{Contents}
%\begin{multicols}{2}
%\tableofcontents
%\end{multicols} }
%


%

%\setcounter{section}{-1}
\def\v{\mathbf{v}}
\def\p{\mathbf{p}}
\def\q{\mathbf{q}}
\def\S{\mathbf{S}}
\def\1{\mathbf{1}}
\setcounter{page}{1}
\section*{Is there a {\em pure} NE for the IPD? }

Let us first consider a two player Iterated Prisoner Dilemma game and
that both players use a one-memory strategy. 
This means that the two players choose vectors
$\p=(p_1,\dots,p_4)$ resp. $\q=(q_1,\dots,q_4)$, where 
$p_i,q_i\in [0,1]$ and $p_1,\dots,p_4$ resp. $q_1,\dots,q_4$
determine the probability of cooperation
following previous play of the two players of $xy\in (cc,cd,dc,dd)$ (for player $X$) 
resp. $xy=(cc,dc,cd,dd)$ (for player $Y$) 
 (c=cooperation and d=defection).  Define the payoff vectors
 $$\S_X=(R,S,T,P) \mbox{ and }\S_Y=(R,T,S,P).$$ Here R=reward, S=sucker, T=temptation , P=punishment,  
and a common choice is $(T,R,P,S)=(5,3,1,0)$. Here $2R>T+S>2P$
so cooperation pays in the long run. 
So in this case 
 $$\S_X=(3,0,5,1) \mbox{ and }\S_Y=(3,5,0,1).$$ 

This means that we have a Markov chain with transition matrix
$$M=  \left( \begin{array}{cccc} 
p_1q_1  & p_1(1-q_1) & (1-p_1)q_1 & (1-p_1)(1-q_1) \\ 
p_2q_3 & p_2(1-q_3)  & (1-p_2)q_3 &(1-p_2)(1-q_3) \\
p_3q_2 & p_3(1-q_2) & (1-p_3)q_2 &(1-p_3)(1-q_2) \\
p_4q_4 & p_4(1-q_4) & (1-p_4)q_4 & (1-p_4)(1-q_4)
\end{array} \right).$$ 
Also assume for the moment that $M$ is transitive and so 
has a unique stationary eigenvector 
$\v$,  i.e., $\v$ is the
 left eigenvector of $M$ corresponding to eigenvalue $1$. 
 Note that $\v$ is unique if  $\p,\q\in (0,1)^4$ because in that case the 
 Markov chain is transitive. In fact, it is even transitive if $p_i,q_j\in (0,1)$
 for all $i,j=1,2,3$. 

In Press-Dyson's paper it is shown that 
if we define 
$$D(\p,\q,f)=\det \left( \begin{array}{cccc} 
p_1q_1 -1 & p_1-1 & q_1-1 & f_1 \\ 
p_2q_3 & p_2-1 & q_3 & f_2 \\
p_3q_2 & p_3 & q_2-1 & f_3 \\
p_4q_4 & p_4 & q_4 & f_4 
\end{array} \right) 
$$  
and assume that the asymptotic distribution vector $\v$ is unique, then the asymptotic expected score is
\begin{equation} s_X=\v\cdot \S_X = \dfrac{\v\cdot \S_X}{\v\cdot \1} = \dfrac{D(\p,\q,\S_X)}{D(\p,\q,\1)}
\label{payoffX} \end{equation} 
\begin{equation} s_Y=\v\cdot \S_Y = \dfrac{\v\cdot \S_Y}{\v\cdot \1} = \dfrac{D(\p,\q,\S_Y)}{D(\p,\q,\1)}
\label{payoffY} \end{equation} 


Obviously, the above formula can only be correct if $\v$ is unique. 
\begin{example} 
Suppose both players do TFT. This corresponds  to 
 $p=q=(1,0,1,0)$.
Then there are three stationary vectors (left eigenvectors of $M$ corresponding to the eigenvalue $1$), namely 
$(1,0,0,0)$ (always coorporate), $(0,1,1,0)$ (out of sync), $(0,0,0,1)$ (always defect)
depending on the initial distribution and this gives
$S_X$ can be $3$,  $5/2$  and $1$ (given the above  values of $T,R,P,S$).
A calculation shows that if we let $\p\in (0,1)^4, \q\in (0,1)^4$ both tend to $(1,0,1,0)$
then $s_X=s_Y=2.25$. In Lemma~\ref{lem:cont} below it is shown that this limit exists 
and is unique.  
\end{example} 

As  mentioned, $\v$ is unique if $p,q\in (0,1)^4$. 


\begin{question} Is it true that 
the  matrix $M$ has a unique stationary vector $\v$ if and only if $D(\p,\q,\1)\ne 0$?
\end{question} 

\begin{lemma}  $D(\p,\q,\1)\le 0$ and $D(\p,\q,\1)<0$ if $\p,\q\in (0,1)^4$. 
\end{lemma}
\begin{proof} That $D(\p,\q,\1)\le 0$ is proved in Wang-Lin's paper. We repeat their argument for completeness. 
$ D(\p,\q,\1)$ depends linearly on each $p_i$ and each $q_j$ separately. So the extrema are attained when $p_i,q_j\in \{0,1\}$. 
A simple check of the $2^8=256$ possibilities shows that   $D(\p,\q,\1)\le 0$  when all $p_i\in \{0,1\},q_j\in \{0,1\}$.
% and  $D(\p,\q,\1)<0$. %  when one of the $p_i$ or $q_j$ switches. 
This gives the result. %That $D(\p,\q,\1)<0$ if $\p,\q\in (0,1)^4$ follows. 
\end{proof} 


Even though the expressions for $s_X$ and $s_Y$ are invalid when $\v$ is unique, 
one has the following 

\begin{lemma} \label{lem:cont} The functions 
$ \dfrac{D(\p,\q,\S_X)}{D(\p,\q,\1)}$ and $\dfrac{D(\p,\q,\S_Y)}{D(\p,\q,\1)}$ 
on $(0,1)^4\times (0,1)^4$ 
extend continuously to $[0,1]^4\times [0,1]^4$. 
In particular, the above expressions for 
$s_X,s_Y$ extends  continuously to $[0,1]^4\times [0,1]^4$ 
(but may take different values from $\v \cdot \S_X$ and $\v\cdot \S_Y$
when $\v$ is not unique). 
\end{lemma} 
\begin{proof} $ D(\p,\q,\1)$ depends linearly on each $p_i$ and each $q_j$ separately, 
so each zero of $D(\p,\q,\1)$ is a product of simple zeros  $p_i$, $q_j$. 
On the other hand $ \dfrac{D(\p,\q,\S_X)}{D(\p,\q,\1)}$ and $\dfrac{D(\p,\q,\S_Y)}{D(\p,\q,\1)}$ 
do not have poles, so this means that the poles of these expressions are removable. 
QQQQ Is this argument correct???? QQQQ
\end{proof} 




 



\begin{rem}
There are quite a few, but perhaps only something like 40, choices for pairs of vectors $\p,\q\in \{0,1\}^4$ 
for which $D(\p,\q,\1)=0$. However, there are also  zeros of $D$ of the following form: 
$\q=(1,1,0,0)$ then $D(\p,\q,\1)=0$ when either $p_1=p_3$ or $p_2=p_4$. 
\end{rem} 



\begin{lemma} Varying $p_i$ in the interval $[0,1]$ and letting the other variables 
remain constant, the expression  (\ref{payoffX}),(\ref{payoffY}) has a maximum 
either at $p_i=0$ or at $p_i=1$.
\end{lemma} 
\begin{proof} Since the fractions in (\ref{payoffX}),(\ref{payoffY})  give the average payoff, 
these fractions remain bounded even if $D(\p,\q,\1)\to 0$. 
Therefore  a cancelation in these fractions occurs when $D(\p,\q,\1)= 0$.
Hence  the expression $\dfrac{D(\p,\q,\S_Y)}{D(\p,\q,\1)}$ is a Moebius transformation 
with bounded values for $\p=(p_1,\dots,p_4),\q=(q_1,\dots,q_4)\in [0,1]^4$.
The lemma follows. 
\end{proof} 


In the lemma below we compute $BR_p(q)$ (using the computer):



\begin{lemma} Based on the continuous extension 
of $s_X,s_Y$ one has:
$$BR_p(q)=\begin{cases}\{(0,0,0,0),(0,0,1,0),(1,0,0,0),(1,0,1,0)\} & q=(0,0,0,0)\\
\{(0,0,0,0),(1,0,0,0)\} & q=(0,0,0,1) \\
\{(0,0,1,1),(1,0,1,1)\} & q=(0,0,1,0) \\
\{(0,0,0,0),(0,1,0,0),(1,0,0,0)\} & q=(0,0,1,1) \\
\{(0,0,0,0),(1,0,0,0)\} & q=(0,1,0,0) \\
\{(0,0,0,0),(0,1,0,0),(1,0,0,0)\} & q=(0,1,0,1) \\
\{(0,0,0,1),(1,0,0,1)\} & q=(0,1,1,0) \\
\{(0,0,0,0),(0,1,0,0),(1,0,0,0),(1,0,0,1)\} & q=(0,1,1,1) \\
\{(0,0,0,0),(0,0,1,0),(1,0,0,0),(1,0,0,1),(1,0,1,0),(1,0,1,1),(1,1,0,0),(1,1,0,1),(1,1,1,0),(1,1,1,1)\} & q=(1,0,0,0) \\
\{(0,0,0,0),(0,0,0,1),(1,0,0,0),(1,0,0,1),(1,0,1,1)\} & q=(1,0,0,1) \\
\{(1,1,0,1),(1,1,1,0),(1,1,1,1)\} & q=(1,0,1,0) \\
\{(0,0,0,0),(0,0,0,1),(0,1,0,0),(0,1,0,1),(1,0,0,0),(1,0,0,1),(1,1,0,0),(1,1,0,1),(1,1,1,0),(1,1,1,1)\} & q=(1,0,1,1) \\
\{(0,0,0,0)\} & q=(1,1,0,0) \\
\{(0,0,0,0),(0,0,0,1),(0,1,0,0),(0,1,0,1)\} & q=(1,1,0,1) \\
\{(0,0,0,1),(0,1,0,1)\} & q=(1,1,1,0) \\
\{(0,0,0,0),(0,0,0,1),(0,1,0,0),(0,1,0,1)\} & q=(1,1,1,1) \\
\end{cases} $$
Note that only $p\in BR_p(q),q\in BR_q(p)$ with $p=q$
if and only if $(p,q)=(0,0,0,0)$ and QQQ



$$A(BR_p(q))=\begin{cases}1 & q=(0,0,0,0)\\
3 & q=(0,0,0,1) \\
2.5 & q=(0,0,1,0) \\
3 & q=(0,0,1,1) \\
2.333 & q=(0,1,0,0) \\
5 & q=(0,1,0,1) \\
5 & q=(0,1,1,0) \\
5& q=(0,1,1,1) \\
1 & q=(1,0,0,0) \\
3 & q=(1,0,0,1) \\
3 & q=(1,0,1,0) TFT \\
3 & q=(1,0,1,1) \\
3& q=(1,1,0,0)  \\
5 & q=(1,1,0,1) \\
5 & q=(1,1,1,0) \\
5 & q=(1,1,1,1) \\
\end{cases} $$
 \end{lemma}


\begin{question} Is there a pure Nash equilibrium for this infinite dimensional
game, with payoffs determined by (\ref{payoffX}),(\ref{payoffY}) where we take the 
limit values.  (Of course one should check when $D(\p,\q,\1)=0$.)
\end{question} 


\begin{question} Work out precisely what happens when $D(\p,\q,\1)=0$. I guess 
$s_X,s_Y$ are then multivalued (depend on the initial choice of play). 
\end{question}



\begin{rem} $\p,\q\in [0,1]^4$ can be viewed as pure actions. Mixed actions 
would correspond to probability measures in this space.   
\end{rem} 

\end{document}

 