

\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=2cm,marginparwidth=10cm]{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{q}{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}
\setcounter{page}{1}
\section*{Dynamics of games\\
Project 3: Regret minimisation learning, a computer implementation}

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.

This project considers regret learning in the context of the Blotto games, which often 
is associated to two candidates for an election, who each can allocate money in different states.
For a useful description see 
\begin{itemize} 
\item 
\url{https://www.wikiwand.com/en/Blotto_game} 
\item
\url{https://en.wikipedia.org/wiki/Blotto_game}.  
\end{itemize} 
Attached to this this project description is a  paper by 
\begin{itemize}
\item T. W. Neller and Marc Lanctot, {\em An Introduction to Counterfactual Regret Minimization}, 
\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 Explain the captain Blotto game described in the paper by Neller and Lanctot.
\item This game is not described in matrix form. Outline how many actions each player
has, and how {\em in principle} to convert this game into game in matrix form. 
\item  Explain why this game must have a Nash equilibrium. 
\item  Describe the set of NE for one of the following cases:
\subitem[-]  in the case when there are $N=2$ battle fields with equal {\lq}armies{\rq}
, but the allocation to each battle field does not need to be an integer. 
For this you can consult  S. T. Macdonell and  N. Mastronardi, {\em Waging simple wars: a complete characterization of two-battlefield Blotto equilibria}, 
Economic Theory, 2015) 58:183--216.  \url{https://scottmacdonell.files.wordpress.com/2014/04/wagingsimplewars.pdf}. 
\subitem[-]  in the corresponding case  with equal {\lq}armies{\rq} when there are $N=3$ battle fields and again the allocation to each battle field does 
not need to be an integer.  For this you can consult D. Kvasov, {\em Contests with limited resources}, Journal of Economic Theory 136 (2007) 738 – 748, \url{https://www.sciencedirect.com/science/article/pii/S0022053106001244}. 
%Alternatively you can consult 
%the last part of \url{https://www.rand.org/pubs/research_memoranda/RM408.html}.  
\subitem[-]   assuming that the allocation to each battle field is an integer.
For this you can consult S. Hart, {\em Discrete Colonel Blotto and General Lotto games}, 
Internat. J. Game Theory 36 (2008), no. 3-4, 441–460.  \url{http://www.ma.huji.ac.il/hart/abs/blotto.html}
\item Outline the idea the regret learning algorithm, and explain to what set
this algorithm is guaranteed to converge. 
\item Implement regret learning to solve Exercise 2.6 in the paper by Neller and Lanctot.
Also address the two following issues:  Does you algorithm converge and to what set/point? If it converges, with what speed? 
%\item 
%Next implement a 
%\item 
\item ({\bf Mastery question for 4th year and MSc students})
Explain the theoretical arguments behind the regret learning algorithm (discussing for example
speed of convergence). Also code up a 
reinforcement learning algorithm of your choice for this game.  Compare the results you get with what
you discussed in question 5. 


\end{enumerate} 



\end{document}

 