

\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=3cm, right=4cm,marginparwidth=4cm]{geometry}
\usepackage[title,titletoc,toc]{appendix}
\usepackage{graphics}
\usepackage[english]{babel}

%\usepackage[latin1]{inputenc}
\usepackage{multicol}
\usepackage{times}
\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}

\section*{Questions on\\
Project 1: permanent replicator dynamics}


\begin{question} 
Numerical integration leaving simplex. Can this be resolved? 
For example, by using an implicit Runge Kutta method. 
\end{question} 

\begin{question}
It turns out that for hyper cycles, when $n\ge 5$, solutions not only remain {\lq}permanent{\rq}
but even converge to a periodic solution. Explain this result. 
\end{question} 

\begin{question}
What do Sato’s result tell us for learning, and make the connection with q-learning more formal.  
\end{question}


\newpage 


\setcounter{page}{1}
\section*{Dynamics of games\\
Project 1: permanent replicator dynamics}

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 the short oral.

Attached to this this project description are  
\begin{itemize}
\item pages 146-149,  pages 149-151 and pages 162, 44-45 and 79 of the book 
by Hofbauer and Sigmund, Evolutionary Games and Population Dynamics
\item  Y. Sato , E. Akiyama and J. P. Crutchfield, {\em Stability and diversity in collective adaptation}, Physica D 210 (2005) 21--57,
\url{https://www.sciencedirect.com/science/article/pii/S0167278905002708}.


\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 Prove the following theorem. 

\begin{thm}Assume that $P$ is continuous, $P>0$ on the interior of $\Delta$ and 
for $x$ in the interior of $\Delta$ define
$$\Psi(x):=\frac{\dot P(x)}{P(x)}$$
Assume that $\Psi$ extends continuously to the boundary 
and that $x\in \partial \Delta$,
$$\int_0^T \Psi(x(t))\, dt>0\mbox{ for some }T>0.$$
Then the corresponding dynamical system is permanent. More precisely, show that there exists $\delta>0$ so that
for each $x$ in the interior $\Delta$ there exists $T>0$ so that 
for $t\ge T$, 
we have $x_i(t)\ge \delta$ for all $t\ge T$ and $i=1,\dots,n$.
\end{thm}

\item Show Theorem 1 implies that the hypercycle system 
from section 1.5 in the lecture notes is permanent for all $n\ge 5$. 
You may assume that $k_i=1$ for all $i$. 

(Note that in the notes the function $P(x)=x_1 \cdots x_{n-1}$ was
chosen, and that 
$$\Psi(x)=\frac{\dot P(x)}{P(x)}=\sum_{i=1}^n \dfrac{\dot x_i}{x_i}=1-n\sum_{j=1}^n x_j x_{j-1}.$$
Note that for $n\ge 5$ it is  NOT true that $\Psi(x)>0$ for all $x$ close to the boundary of $\Delta$ (but $P>0$
near $e_i$). What does this imply for $t\mapsto P(x(t))$ for a solution of $x(t)$ of the replicator dynamics. 

%\item Show that if the replicator system has a unique interior Nash equilibrium $\bar x$ and the system is permanent
%then for each $x$ in the interior of $\Delta$ we have
%$$\dfrac{1}{T} \int_0^T x(t) \, dt \to \bar x.$$ 

%\item Sketch the solutions of the replicator dynamics associated to the matrices
%$$
%A = \left( \begin{array}{ccc}
%0 & 1 & -1 \\
%-1 & 0 & 1 \\
%-1 & 1 & 0
%\end{array} \right), \quad 
%B = \left( \begin{array}{ccc}
%0 & 6 & -4 \\
%-3 & 0 & 5 \\
%-1 & 3 & 0
%\end{array} \right) 
%\quad 
%C = \left[
%\begin{array}{ccc}
%\varepsilon & 1 & -1 \\
%-1 & \varepsilon & 1 \\
%1 & -1 &\varepsilon
%\end{array}
%\right], \epsilon \in (-1,1).
%$$
%Also sketch the solutions of the BR dynamics of these systems.  There is a theorem 
%which states that the time average $\dfrac{1}{t} \int_0^t x(s)\, ds$ of a RD system solution converges in some 
%{\lq}weak sense{\rq} to a solutions of a BR system . Check for which solutions this statement holds literarily 
%in these three examples. 
\item 
Write Matlab code or python code in order to produce solutions
of the following two replicator dynamics for single population games:
$$A_0= \left( \begin{array}{ccc}
0 & 1 & -1 \\
-1 & 0 & 1 \\
-1 & 1 & 0
\end{array} \right), \quad A_1=\left( \begin{array}{ccccccc}
0 & 0 & 0 & . & . & . & k_1 \\
k_2 & 0 & 0 & . & . & . & 0 \\
0 & k_3 & 0 & . & . & . & 0 \\
. & . & . & . & . & . & . \\
0 & 0 & 0 & . & . &  k_n & 0 \end{array}\right)$$
with $k_i=1$ and $n=5$. Compute the NE's for these systems. Analyse the $\omega$-limit 
of orbits for these systems. Discuss in detail in what 
 way you think the system associated to $A_1$ has {\lq}chaotic{\rq} solutions
for $n\ge 5$ and  non-chaotic solutions for $n\le 4$.  Do the solutions associated to $A_1$ for $n\ge 5$ tend
to the NE?  Also consider the two player game
$$A=\left( \begin{array}{ccc}
 \epsilon_x & -1 & 1  \\ 
 1 & \epsilon_x & -1 \\
 -1 & 1 & \epsilon_x \end{array}\right) \mbox{ and } 
B=\left( \begin{array}{ccc}
 \epsilon_y & -1 & 1  \\ 
 1 & \epsilon_y & -1 \\
 -1 & 1 & \epsilon_y \end{array}\right)
 $$ where we use the 1st notation. Show the output for a few values of $\epsilon_x.\epsilon_y\in (-1,1)$
 replicating the figures from the paper of Sato et al.  
\item 

[{\bf Mastery question for 4th year and MSc students}]
In Sections 2.1 and 2.2 of the paper of Sato et al,  reinforcement adaptation is introduced. 
Discuss this model focussing on
\begin{enumerate}
\item its relationship to replicator dynamics (see Section 2.4 of that paper).
\item the dynamics of the examples discussed in Section 4 of that paper. Compute the NE's for these examples. Do solutions
tend to these Nash equilibria? Compute the average of payoff over time along orbits, and compare this with 
the payoff players would receive it they chose to play their  NE solution at every step. 
\end{enumerate} 
You are not required to cover all aspects of this paper (for example, you can 
skip the discussion about the Hamiltonian structure and Section 3 of this paper.  




% Consider the replicator dynamics of 
% $$A=\left( \begin{array}{ccccccc}
%0 & 0 & 0 & . & . & . & k_1 \\
%k_2 & 0 & 0 & . & . & . & 0 \\
%0 & k_3 & 0 & . & . & . & 0 \\
%. & . & . & . & . & . & . \\
%0 & 0 & 0 & . & . &  k_n & 0 \end{array}\right)$$
%with $k_i=1$. Prove that this system is 
%permanent. Using Matlab, Maple or similar, show that this system has {\lq}chaotic{\rq} solutions
%for $n\ge 5$ and is non-chaotic for $n\le 4$.  Discuss in what way solutions are chaotic. 
\end{enumerate} 



\end{document}

 