

\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{exms}{Examples} %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*{First type of question arising from 
Project 2: Reciprocity and the success of TFT strategies\\
Is there a pure NE for the IPD? }

In Project 2, the Iterated Prisoner Dilemma game is considered.
What is assumed that the two players choose a vector 
$\p=(p_1,\dots,p_4)$ resp. $\q=(q_1,\dots,q_4)$.
Here,  $p_i,q_i\in [0,1]$ and $p_1,\dots,p_4$
determine the probability of cooperation
following previous play of the two players of $xy\in (cc,cd,dc,dd)$
 (c=cooperation vs d=defection). Define the payoff vector
 $$\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)$. 

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_3 & f_3 \\
p_4q_4 & p_4 & q_4 & f_4 
\end{array} \right) 
$$  
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} 
Here $\v$ is the stationary measure associated to the Markov chain $$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_1) \\
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),$$ i.e., the
 left eigenvector of $M$ corresponding to eigenvalue $1$. 
This matrix has a unique stationary vector $\v$ if and only if $D(\p,\q,\1)\ne 0$. 

\newpage 

\begin{rem}
Note that even if $D(\p,\q,\1)=0$ the expressions (\ref{payoffX}),(\ref{payoffY}) remain bounded,
and so as $D(\p,\q,\1)\to 0$ there is a unique limit of these expressions. 
(There are quite a few, but perhaps only something like 20, choices for $\p,\q$ for which $D(\p,\q,\1)=0$.
The proof of a lemma from Wang-Lin's paper which shows that $D(\p,\q,\1\le 0$ is helpful for this.)
\end{rem} 
\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} 

\hrule 
\vskip 1cm 


\noindent 
\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. 
\end{question} 



\noindent 
\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}


%\medskip 
%
%If you consider non-pure actions, then you should 

\begin{question} Is there a mixed Nash equilibrium for this infinite dimensional
game, with payoffs determined by  (\ref{payoffX}),(\ref{payoffY}). 
\end{question}

\medskip 

\begin{rem} 
Perhaps in Question 1 the existence can be proved abstractly, or perhaps can be found by 
a computer search. 
\end{rem} 
\medskip 
\newpage 


\section*{Second type of question arising from 
Project 2: Reciprocity and the success of TFT strategies\\
The role of memory in IPD? }

In Press-Dyson it is shown that 
if one player uses a one memory strategy then 
the other player has no benefit of using a longer term strategy. 


Let us assume that an IPD tournament is played so that players do not know 
who they play in each round. So then perhaps this result is not so relevant. 


\begin{question} Does Press-Dyson's result apply if three players are involved? 
If not, show precisely in what way memory can be used. 
\end{question}

\begin{question} What is the role of memory in IPD tournaments. Can this be
used to determine the environment you are up against? 
\end{question}

\begin{question} If you do choose a stationary (pure action) but either 
draw actions according to some probability measure on $[0,1]^4$. 
What improvements can one use? How is this related to 
memory?
\end{question} 

\newpage 





In this project you are allowed to use books and the hand-outs,
but it is important that you write up your project 
by yourself and that you can explain what you have written
in detail during a short oral.


Attached to this project description are
\begin{itemize}
\item a section from the book of Sigmund (The calculus of selfishness),
\item a paper by W.H. Press and F.J. Dyson \url{http://www.pnas.org/cgi/doi/10.1073/pnas.1206569109}.
\item  You are also asked to look 
at various discussion of the paper of Press and Dyson on the internet, e.g.
\subitem 
\url{https://golem.ph.utexas.edu/category/2012/07/zerodeterminant_strategies_in.html},
\subitem \url{http://www.technologyreview.com/view/428920/the-emerging-revolution-in-game-theory/}
\subitem \url{https://plato.stanford.edu/entries/prisoner-dilemma/#ZeroDeteStra}. 
\item A good paper discussing Press and Dyson's paper is 
A. Stewart and J.B.  Plotkin, “Extortion and Cooperation in the Prisoner's
Dilemma,” Proceedings of the National Academy of Sciences, 109: 10134–10135: 
 \url{http://www.pnas.org/cgi/doi/10.1073/pnas.1208087109}.
\end{itemize} 
\medskip
\hrule 
\bigskip


\begin{enumerate}
\item  Submit your solutions of the selected exercises from the lecture notes (which are the same for all projects).
\item  As discussed in the lectures, over the last 40 years every year
tournaments were held, in  which an interative version of the prisoner dilemma (or donation game) (IPR)
was played. These tournaments are often called after its founder, Axelrod. In this project you are asked to explore the success
of the TFT strategies in these tournaments. In a few paragraphs, explain the rules of the Axelrod tournaments, 
the various strategies that were used, and the outcomes in the tournament.
\item Discuss in a few pages what arguments are given in Sigmund's book, based on evolutionary game theory
(and replicator dynamics), of the success of TFT games and explain
why in these arguments the success of TFT depends on the environment in 
which it is used (i.e. on which other strategies are used).
\item  Describe the results from the paper by Press and Dyson in detail. 
\item Explain why the paper of Press and Dyson has created so much excitement, 
and discuss to what extend this excitement was warranted. 
\item Run the Axelrod tournaments  through one of the following
\subitem{-}  \url{https://github.com/Axelrod-Python/Axelrod}, see also \\
\url{https://vknight.org/unpeudemath/code/2015/02/20/an-iterated-prisoners-dilemma-on-github.html}.
\subitem{-}   \url{https://github.com/cristal-smac/ipd}. 

Carefully document how you ran this code and your findings from these tournaments. 
Formulate your own strategy (for example some variant of TFT) and run this  strategy in these tournaments.
How does it do? 

\item

[{\bf Mastery question for 4th year and MSc students}]
Discuss the following two papers
\subitem[-]  C. Hilbe,  M.A. Nowak, and K. Sigmund, 2013, “Evolution of extortion in Iterated Prisoner's Dilemma games,” Proceedings of the National Academy of Sciences, 110 (17): 6913–6918. \url{https://doi.org/10.1073/pnas.1214834110}. 
\subitem[-] S. Wang and  F. Lin, 2020, "Nice Invincible Strategy for the Average-Payoff IPD", 
\url{https://aaai.org/ojs/index.php/AAAI/article/view/5604}

There are quite a few other recent papers on this topic, and you are also allowed to discuss any of those (instead), provided
your discussion goes into sufficient depth:
\subitem[-]  
E. Akin, 2013, “The Iterated Prisoner’s Dilemma: Good Strategies and Their Dynamics,” \url{https://arxiv.org/abs/1211.0969}.
\subitem[-] P.  Mathieu and J.P. Delahaye, 2017, "New Winning Strategies for the Iterated Prisoner's Dilemma", 
Journal of Artificial Societies and Social Simulation 20 (4) 12,  \url{http://jasss.soc.surrey.ac.uk/20/4/12.html}.
\subitem[-] Y. Murase, S.K. Baek, 2020: "Five rules for friendly rivalry in direct reciprocity", 
\url{https://arxiv.org/abs/2004.00261}
\subitem[-]  M. Harper, V. Knight  et al., 2017: "Reinforcement learning produces dominant strategies for the Iterated Prisoner’s Dilemma"
Plos One 12 (12) , e0188046. \url{https://doi.org/10.1371/journal.pone.0188046}

\end{enumerate} 



\end{document}

 