
%Explicit Dynamic Quadratic Programming  creating Fibonacci number and
%Golden ratio
%Seiichi Iwamoto (Emeritus Professor of Kyushu University) 
%Yutaka Kimura (Akita Prefectural University)
%Masami Yasuda (Chiba University)

% Abstract:
%      We list several classes of Dynamic Programming, especially,
% Linear Quadratic Control problem.  These are simple optimizations
% but interesting since they are related to famous subjects:
% (1) Division of numbers with quadratic criterion.
% (2) Golden optimal solution in quadratic programming.
% (3) Matrix of threefold diagonal form with Fibonacci components.
% (4) Multi-variate stopping with a monotone rule
%     for three persons.
% These are basically connected with Fibonacci Number and
% Golden Ratio, which means recurrence, iterative structure,
% duality and so on. 


\documentclass[11pt,dvipdfm,cjk]{beamer}
%\documentclass[11pt,dvipdfm,cjk,handout]{beamer}
\mathversion{bold}
%%%%%%%%%
%\usepackage{txfonts}
\usepackage{comment}
\usepackage{epic}
\usepackage{eepic}
\usepackage{pgf}
\usepackage{ulem}
\usepackage{latexsym,amssymb,amsmath,amsfonts,amscd}
\usepackage{graphicx,color}
\usepackage{verbatim}
\usepackage{ascmac}
\usepackage{bm}
\usepackage{multimedia}
%\usepackage{beamerthemesplit}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\usetheme{JuanLesPins}%Madrid,Rochester,Antibes,JuanLesPins,Bergen,Pittsburgh,Berkeley,Pittsburgh,Darmstadt,Berlin,Frankfurt,Singapore,Szeged,Ilmenau,Dresden,Copenhagen,Luebeck,Malmoe,Warsaw,Boadilla,CambridgeUS,Goettingen,Hannover,Montpellier
%%%%%%%%%%%%%%%%%%%%%%%%%%
\usecolortheme{orchid}%albatross,beaver,beetle,crane,default,dolphin,dove,fly,lily,orchid,rose,seagull,seahorse,sidebartab,structure,whale,wolverine
\usefonttheme{serif}%serif,structurebold,structureitalicserif,structuresmallcapsserif,professionalfonts
%%%%%%%%%%%%%%%%%%%%%%%%%%
\usefonttheme{serif}%serif,structurebold,structureitalicserif,structuresmallcapsserif,professionalfonts, default
\useinnertheme{rounded}%rounded,circles,rectangles,inmargin
\useoutertheme{shadow}%smoothtree,infolines,miniframes,smoothbars,split,tree,default
\setbeamertemplate{caption}[numbered]
\newcommand{\realfield}{\mbox{\boldmath $R$}}
\let\R\realfield
%%%%%%%%%%%%%%%%%%%%%%%%%%
\setbeamertemplate{blocks}[rounded][shadow=true]
\setbeamercolor{block title}{bg=blue!60!black, fg=white}
\setbeamercolor{block body}{bg=blue!20!white}
\setbeamercolor{block title alerted}{bg=red!60!black, fg=white}
\setbeamercolor{block body alerted}{bg=red!20!white}
\setbeamercolor{block title example}{bg=green!60!black, fg=white}
\setbeamercolor{block body example}{bg=green!20!white}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setbeamertemplate{navigation symbols}{}
\setbeamerfont{title}{size=\Large,series=\bfseries}
\setbeamercolor{title}{fg=white}
\setbeamerfont{frametitle}{size=\Large, series=\bfseries}
%\setbeamerfont{frametitle}{size=\large, series=\bf}
\setbeamercolor{frametitle}{fg=white}
\setbeamertemplate{footline}[frame number]
%\setbeamercovered{transparent=10} % 隠蔽されている要素の透明度を設定変更でき 
%%%%%%%%%%%%%%%%%%%% newcommand %%%%%%%%%%%%%%%%%%%%%%%%%%
%\renewcommand{\familydefault}{\sfdefault}	%英語をsfに設定する。
\renewcommand{\kanjifamilydefault}{\gtdefault}	%日本語フォントをゴシック。
\renewcommand{\rmdefault}{ppl}	
\renewcommand{\sfdefault}{ppl}	
\newcommand{\RED}[1]{\textcolor{red}{#1}}
\newcommand{\BLUE}[1]{\textcolor{blue}{#1}}
\newcommand{\GREEN}[1]{\textcolor{green}{#1}}
\newcommand{\YELLOW}[1]{\textcolor{yellow}{#1}}
\newcommand{\CYAN}[1]{\textcolor{cyan}{#1}}
\newcommand{\MAGENTA}[1]{\textcolor{magenta}{#1}}
\newcommand{\WHITE}[1]{\textcolor{white}{#1}}
\newcommand{\BLACK}[1]{\textcolor{black}{#1}}
\newcommand{\GRAY}[1]{\textcolor{gray}{#1}}
\def\dsum{\displaystyle\sum}
\def\dfrac{\displaystyle\frac}
%\newcommand{\realfield}{\mbox{\boldmath $R$}}
%\let\R\realfield
\newcommand\bmath[1]{\mbox{\boldmath $#1$}}
\newcommand{\RedBlackframebox}[3]{\textcolor{red}{\framebox(#1,#2){\textcolor{black}{#3}}}}
\newcommand{\MagRedframebox}[3]{\textcolor{magenta}{\framebox(#1,#2){\textcolor{red}{#3}}}}
\newcommand{\MagBlueframebox}[3]{\textcolor{magenta}{\framebox(#1,#2){\textcolor{blue}{#3}}}}
\newcommand{\CyanRedframebox}[3]{\textcolor{cyan}{\framebox(#1,#2){\textcolor{red}{#3}}}}
\newcommand{\CyanBlueframebox}[3]{\textcolor{cyan}{\framebox(#1,#2){\textcolor{blue}{#3}}}}

%%%%%%%%%%%%%%%%%%%% def %%%%%%%%%%%%%%%%%%%%%%%%%%
\def\Max{\displaystyle\mathop{\rm Max}}
\def\min{\displaystyle\mathop{\rm min}}
\def\dsum{\displaystyle\sum}
\def\dfrac{\displaystyle\frac}
\newcommand{\hs}[1]{\hspace*{#1mm}}
\newcommand{\vs}[1]{\vspace*{#1mm}}
%
\def\tdef{\stackrel{\triangle}{=}}
\def\ddef{\stackrel{def}{\Longleftrightarrow}}
\def\minus{\hspace{-0.6mm} - \hspace{-0.6mm}}
\def\plus{\hspace{-0.6mm} + \hspace{-0.6mm}}
\def\stimes{\hspace{-1.35mm} \times \hspace{-1.05mm}}
\def\sstimes{\hspace{-0.45mm} \times \hspace{-0.15mm}}
\def\bspace{\hspace{10mm}}
\def\mspace{\hspace{7mm}}
\def\sspace{\hspace{4mm}}
\def\backsp#1{\hspace*{-#1mm}}
\newcommand{\tabtopsp}[1]{\vbox{\vbox  to#1{}\vbox to1zw{}}}
%
\def\ndot{\hspace{-0.35mm}\cdot\hspace{-0.48mm}}
\def\eql{\hspace{-1.46mm}&=&\hspace{-1.46mm}}
\def\dql{\hspace{0.49mm}=\hspace{0.49mm}}
\def\nge{\hspace{-1.46mm}&\ge&\hspace{-1.46mm}}
\def\nle{\hspace{-1.46mm}&\le&\hspace{-1.46mm}}
%
\def\proof{{\it \noindent Proof.} \hspace{2ex}}
\def\boxend{ \hspace*{\fill} $\Box$	 \\ }
%
%
\newtheorem{thm}{定理}%[section]%
\newtheorem{cor}{系}%[section]%
\newtheorem{lem}{補題}%[section]%
\newtheorem{defi}{定義}%
\newtheorem{ex}{例}%
\newtheorem{pr}{問題}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%frame option
%plain, containsverbatim, shrink, squeeze, allowframebreaks, 
%label=favorite_slide
%%%%%%%%%%%%%%%%%%%
\title{Explicit Dynamic Quadratic Programming \\
         creating \\
       Fibonacci number and Golden ratio
}%\vspace{10mm}}
\subtitle{}
\author{Seiichi ~IWAMOTO\\[0mm]
Yutaka ~KIMURA\\[2mm]
\hspace*{-2mm}Masami ~YASUDA
}
\vspace{15mm}
\institute{}
\date{{\footnotesize 
Workshop on Games and MDP at WUT\\[1mm]
July,~2011\\[1mm]}}
\begin{document}
\frame{\titlepage}
%%%%%%%%%%%%%%%%%%%%
\begin{frame} \frametitle{Contents}
\bf
 Abstract:\\
      We list several classes of Dynamic Programming, especially,
 Linear Quadratic Control problem.  These are simple optimizations
 but interesting since they are related to famous subjects:

\begin{itemize}
 \item  Division of numbers with quadratic criterion. \pause
 \item  Golden optimal solution in quadratic programming. \pause
 \item  Matrix of threefold diagonal form with Fibonacci components. \pause
 \item  Multi-variate stopping with a monotone rule
     for three persons.
\end{itemize}
 These are basically connected with Fibonacci Number and
 Golden Ratio, which means recurrence, iterative structure,
 duality and so on. 
\end{frame}

%\section{Number partition}


\begin{frame} \frametitle{Rules and criterion}
\begin{itemize}
 \item[(1)] Given $c$, divide it into two.
 \item[(2)] By selection a $x$, one is $x$ and the other is $c-x$ .
 \item[(3)] Criterion is the each of quadratics; $x^2+(c-x)^2$.
 \item[(4)] Next is consider $c-x$ and so divide it until the final stop.
 \item[(5)] Aim is to minimize the total sum of division
\end{itemize}
\end{frame}




\begin{frame}
\frametitle{Start number is "5"}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	図1:~~2段階2分割問題 （でたらめ）
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\thicklines
\unitlength=0.8mm
\begin{picture}(90,100)
\put(30,85){\vector(0,-1){20}}
\put(30,90){\oval(14,9)}
\put(28,89){5}
%
\put(30,75){\line(1,0){30}}
\put(60,75){\vector(0,-1){10}}
\put(60,60){\oval(15,9)}
\put(59,59){\uncover<2->{1}}
%
%
\put(30,55){\vector(0,-1){20}}
\put(30,60){\oval(14,9)}
\put(29,59){\uncover<2->{4}}
%
\put(30,45){\line(1,0){30}}
\put(60,45){\vector(0,-1){10}}
\put(60,30){\oval(15,9)}
\put(59,29){\uncover<3->{3}}
%
%
%\put(30,25){\vector(0,-1){20}}
\put(30,30){\oval(14,9)}
\put(29,29){\uncover<3->{1}}
\end{picture}\\
%図1:~~でたらめ分割（非交互）
\end{center}
\vspace{-20mm}
%
\uncover<4->{
\[
1^{2} + 4^{2} + 3^{2} + 1^{2} \dql  27 \text{\RED{(Try another!)}}
\]
}
\end{frame}



%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{}
\RED{Optimal} partition is
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	図2:~~2段階2分割問題 （最適分割）
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\thicklines
\unitlength=0.8mm
\begin{picture}(90,100)
\put(30,85){\vector(0,-1){20}}
\put(30,90){\oval(14,9)}
\put(28,89){5}
%
\put(30,75){\line(1,0){30}}
\put(60,75){\vector(0,-1){10}}
\put(60,60){\oval(15,9)}
\put(59,59){\uncover<2->{\RED{3}}}
%
%
\put(30,55){\vector(0,-1){20}}
\put(30,60){\oval(14,9)}
\put(29,59){\uncover<2->{\RED{2}}}
%
\put(30,45){\line(1,0){30}}
\put(60,45){\vector(0,-1){10}}
\put(60,30){\oval(15,9)}
\put(59,29){\uncover<3->{\RED{1}}}
%
%
%\put(30,25){\vector(0,-1){20}}
\put(30,30){\oval(14,9)}
\put(29,29){\uncover<3->{\RED{1}}}
\end{picture}\\
%図1:~~でたらめ分割（非交互）
\end{center}
\vspace{-20mm}
%
\uncover<4->{
\[
3^{2} + 2^{2} + 1^{2} + 1^{2} \dql 15 \text{\RED{(Optimal Partition!)}}
\]
}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Start number is "13"}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	図5:~~3段階2分割問題 （c > 0）でたらめ分割
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\thicklines
\unitlength=0.75mm
\begin{picture}(90,90)
\put(30,85){\vector(0,-1){20}}
\put(30,90){\oval(14,9)}
\put(28,89){13}
%
\put(30,75){\line(1,0){30}}
\put(60,75){\vector(0,-1){10}}
\put(60,60){\oval(15,9)}
\put(59,59){\uncover<2->{3}}
%
%
\put(30,55){\vector(0,-1){20}}
\put(30,60){\oval(14,9)}
\put(28,59){\uncover<2->{10}}
%
\put(30,45){\line(1,0){30}}
\put(60,45){\vector(0,-1){10}}
\put(60,30){\oval(15,9)}
\put(59,29){\uncover<3->{6}}
%
%
\put(30,25){\vector(0,-1){20}}
\put(30,30){\oval(14,9)}
\put(29,29){\uncover<3->{4}}
%
\put(30,15){\line(1,0){30}}
\put(60,15){\vector(0,-1){10}}
\put(60,00){\oval(15,9)}
\put(59,-1){\uncover<4->{1}}
%
%
\put(30,00){\oval(14,9)}
%\put(30,00){\circle{10}}
\put(29,-1){\uncover<4->{3}}
%
\end{picture}\\[13mm]
%図5:~~3段階2分割問題 : でたらめ分割
\end{center}
\vspace{-8mm}
\uncover<5->{
\[
3^{2} + 10^{2} + 6^{2} + 4^{2} +1^{2} + 3^{2} \dql 171 \text{\RED{(Try another!)}}
\]
}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Start number is "13"}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	図5:~~3段階2分割問題 （c > 0）でたらめ分割
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\thicklines
\unitlength=0.75mm
\begin{picture}(90,90)
\put(30,85){\vector(0,-1){20}}
\put(30,90){\oval(14,9)}
\put(28,89){13}
%
\put(30,75){\line(1,0){30}}
\put(60,75){\vector(0,-1){10}}
\put(60,60){\oval(15,9)}
\put(59,59){\uncover<2->{7}}
%
%
\put(30,55){\vector(0,-1){20}}
\put(30,60){\oval(14,9)}
\put(28,59){\uncover<2->{6}}
%
\put(30,45){\line(1,0){30}}
\put(60,45){\vector(0,-1){10}}
\put(60,30){\oval(15,9)}
\put(59,29){\uncover<3->{3}}
%
%
\put(30,25){\vector(0,-1){20}}
\put(30,30){\oval(14,9)}
\put(29,29){\uncover<3->{3}}
%
\put(30,15){\line(1,0){30}}
\put(60,15){\vector(0,-1){10}}
\put(60,00){\oval(15,9)}
\put(59,-1){\uncover<4->{2}}
%
%
\put(30,00){\oval(14,9)}
%\put(30,00){\circle{10}}
\put(29,-1){\uncover<4->{1}}
%
\end{picture}\\[13mm]
%図5:~~3段階2分割問題 : でたらめ分割
\end{center}
\vspace{-8mm}
\uncover<5->{
\[
7^{2} + 6^{2} + 3^{2} + 3^{2} +2^{2} + 1^{2} \dql 108 \text{\RED{(Try another!)}}
\]
}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Start number is "13"}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	図5:~~3段階2分割問題 （c > 0）でたらめ分割
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\thicklines
\unitlength=0.75mm
\begin{picture}(90,90)
\put(30,85){\vector(0,-1){20}}
\put(30,90){\oval(14,9)}
\put(28,89){13}
%
\put(30,75){\line(1,0){30}}
\put(60,75){\vector(0,-1){10}}
\put(60,60){\oval(15,9)}
\put(59,59){\uncover<2->{8}}
%
%
\put(30,55){\vector(0,-1){20}}
\put(30,60){\oval(14,9)}
\put(28,59){\uncover<2->{5}}
%
\put(30,45){\line(1,0){30}}
\put(60,45){\vector(0,-1){10}}
\put(60,30){\oval(15,9)}
\put(59,29){\uncover<3->{3}}
%
%
\put(30,25){\vector(0,-1){20}}
\put(30,30){\oval(14,9)}
\put(29,29){\uncover<3->{2}}
%
\put(30,15){\line(1,0){30}}
\put(60,15){\vector(0,-1){10}}
\put(60,00){\oval(15,9)}
\put(59,-1){\uncover<4->{1}}
%
%
\put(30,00){\oval(14,9)}
%\put(30,00){\circle{10}}
\put(29,-1){\uncover<4->{1}}
%
\end{picture}\\[13mm]
%図5:~~3段階2分割問題 : でたらめ分割
\end{center}
\vspace{-8mm}
\uncover<5->{
\[
8^{2} + 5^{2} + 3^{2} + 2^{2} +1^{2} + 1^{2} \dql 104 = 13 \times 8 
\text{\RED{(Optimal !!)}}
\]
}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Start number is "13"}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	図5:~~3段階2分割問題 （c > 0）でたらめ分割
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\thicklines
\unitlength=0.75mm
\begin{picture}(90,90)
\put(30,85){\vector(0,-1){20}}
\put(30,90){\oval(14,9)}
\put(28,89){13}
%
\put(30,75){\line(1,0){30}}
\put(60,75){\vector(0,-1){10}}
\put(60,60){\oval(15,9)}
\put(59,59){\uncover<2->{9}}
%
%
\put(30,55){\vector(0,-1){20}}
\put(30,60){\oval(14,9)}
\put(28,59){\uncover<2->{4}}
%
\put(30,45){\line(1,0){30}}
\put(60,45){\vector(0,-1){10}}
\put(60,30){\oval(15,9)}
\put(59,29){\uncover<3->{2}}
%
%
\put(30,25){\vector(0,-1){20}}
\put(30,30){\oval(14,9)}
\put(29,29){\uncover<3->{2}}
%
\put(30,15){\line(1,0){30}}
\put(60,15){\vector(0,-1){10}}
\put(60,00){\oval(15,9)}
\put(59,-1){\uncover<4->{1}}
%
%
\put(30,00){\oval(14,9)}
%\put(30,00){\circle{10}}
\put(29,-1){\uncover<4->{1}}
%
\end{picture}\\[13mm]
%図5:~~3段階2分割問題 : でたらめ分割
\end{center}
\vspace{-8mm}
\uncover<5->{
\[
9^{2} + 4^{2} + 2^{2} + 2^{2} +1^{2} + 1^{2} \dql 107 > 104=13 \times 8 
\text{\RED{(Not Optimal)}}
\]
}
\end{frame}





%\end{document}

\begin{comment}
%%%%%%%%%%%%%%%%%%%%
\frame{\titlepage}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Contents}
\begin{itemize}
\item \textcolor<2,8>{red}{多段分割問題}
\item \textcolor<3>{red}{\color<8>{gray} 交互フィボナッチ（4 : 6型）}
\item \textcolor<4>{red}{\color<8>{gray} 交互フィボナッチ相補双対性}
\item \textcolor<5>{red}{\color<8>{gray} 交互フィボナッチ（6 : 4型）}
\item \textcolor<6>{red}{\color<8>{gray} 交互フィボナッチ・シフト双対性}
\item \textcolor<7>{red}{\color<8>{gray} 交互ダ・ヴィンチ・コード}
\end{itemize}
\end{frame}
\end{comment}




%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Change Sign}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	図5:~~3段階2分割問題 （c > 0）最適分割
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\thicklines
\unitlength=0.75mm
\begin{picture}(90,125)
\put(30,115){\vector(0,-1){20}}
\put(30,120){\oval(14,9)}
\put(29,119){$c$}
%
\put(30,105){\line(1,0){30}}
\put(60,105){\vector(0,-1){10}}
\put(61.5,90){\oval(19,9)}
\put(55.5,89){\uncover<1>{$c - x_{1}$}}
\put(55.5,89){\uncover<2->{\RED{$c + x_{1}$}}}
%
%
\put(30,85){\vector(0,-1){20}}
\put(30,90){\oval(14,9)}
\put(28,89){\textcolor<2->{red}{$x_{1}$}}
%
\put(30,75){\line(1,0){30}}
\put(60,75){\vector(0,-1){10}}
\put(61.5,60){\oval(19,9)}
\put(53.5,59){\uncover<1>{$x_{1} - x_{2}$}}
\put(53.5,59){\uncover<2->{\RED{$x_{1} + x_{2}$}}}
%
%
\put(30,55){\vector(0,-1){20}}
\put(30,60){\oval(14,9)}
\put(28,59){\textcolor<2->{red}{$x_{2}$}}
%
\put(30,45){\line(1,0){30}}
\put(60,45){\vector(0,-1){10}}
\put(61.5,30){\oval(19,9)}
\put(53.5,29){\uncover<1>{$x_{2} - x_{3}$}}
\put(53.5,29){\uncover<2->{\RED{$x_{2} + x_{3}$}}}
%
%
%\put(30,25){\vector(0,-1){20}}
\put(30,30){\oval(14,9)}
\put(28,29){\textcolor<2->{red}{$x_{3}$}}
%
\end{picture}
%図5:~~3段階2分割問題 : 最適分割 $(c > 0)$
\end{center}
\uncover<1>{
\vspace{-22mm}
\begin{eqnarray*}
& & \mbox{minimize}~~~ (c - x_{1})^{2} + x_{1}^{2} + ( x_{1} - x_{2})^{2} 
+ x_{2}^{2} + ( x_{2} - x_{3})^{2} + x_{3}^{2}  \\[2.06mm]
& & \mbox{subject~ to}~~~( x_{1}, x_{2}, x_{3}) \in R^{3}
\end{eqnarray*}
}
\uncover<2->{
\vspace{-21mm}
\begin{eqnarray*}
& & \RED{\mbox{minimize}~~~ (c + x_{1})^{2} + x_{1}^{2} + ( x_{1} + x_{2})^{2} 
+ x_{2}^{2} + ( x_{2} + x_{3})^{2} + x_{3}^{2}}  \\[2.06mm]
& & \RED{\mbox{subject~ to}~~~( x_{1}, x_{2}, x_{3}) \in R^{3}}
\end{eqnarray*}
}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Alternative sign Positive/Negative}
\RED{Optimal} partition:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	図2:~~2段階2分割問題 （交互：最適割当）
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\thicklines
\unitlength=0.8mm
\begin{picture}(90,95)
\put(30,85){\vector(0,-1){20}}
\put(30,90){\oval(14,9)}
\put(28,89){5}
%
\put(30,75){\line(1,0){30}}
\put(60,75){\vector(0,-1){10}}
\put(60,60){\oval(15,9)}
\put(59,59){\uncover<2->{3}}
%
%
\put(30,55){\vector(0,-1){20}}
\put(30,60){\oval(14,9)}
\put(27,59){\uncover<2->{$-2$}}
%
\put(30,45){\line(1,0){30}}
\put(60,45){\vector(0,-1){10}}
\put(60,30){\oval(15,9)}
\put(57,29){\uncover<3->{$-1$}}
%
%
%\put(30,25){\vector(0,-1){20}}
\put(30,30){\oval(14,9)}
\put(29,29){\uncover<3->{1}}
%
\put(15, 89){$c$}
\put(15,59){$x_{1}$}
\put(15,29){$x_{2}$}
%\put(15,-1){$x_{3}$}
%
\put(72,59){$(c + x_{1})$}
\put(72,29){$(x_{1} + x_{2})$}
%\put(72,-1){$(x_{2} + x_{3})$}
%
\end{picture}\\
%図1:~~でたらめ分割（非交互）
\end{center}
\vspace{-20mm}
%
\uncover<4->{
\[
3^{2} + (-2)^{2} + (-1)^{2} + 1^{2} \dql 15 \text{\RED{Optimal}}
\]
}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Three steps}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	図5:~~3段階2分割問題 （c > 0）交互：最適分割
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\thicklines
\unitlength=0.75mm
\begin{picture}(90,90)
\put(30,85){\vector(0,-1){20}}
\put(30,90){\oval(14,9)}
\put(28,89){13}
%
\put(30,75){\line(1,0){30}}
\put(60,75){\vector(0,-1){10}}
\put(60,60){\oval(15,9)}
\put(59,59){\uncover<2->{8}}
%
%
\put(30,55){\vector(0,-1){20}}
\put(30,60){\oval(14,9)}
\put(27,59){\uncover<2->{$-5$}}
%
\put(30,45){\line(1,0){30}}
\put(60,45){\vector(0,-1){10}}
\put(60,30){\oval(15,9)}
\put(57,29){\uncover<3->{$-3$}}
%
%
\put(30,25){\vector(0,-1){20}}
\put(30,30){\oval(14,9)}
\put(29,29){\uncover<3->{2}}
%
\put(30,15){\line(1,0){30}}
\put(60,15){\vector(0,-1){10}}
\put(60,00){\oval(15,9)}
\put(59,-1){\uncover<4->{1}}
%
%
\put(30,00){\oval(14,9)}
%\put(30,00){\circle{10}}
\put(27,-1){\uncover<4->{$-1$}}
%
\put(15, 89){$c$}
\put(15,59){$x_{1}$}
\put(15,29){$x_{2}$}
\put(15,-1){$x_{3}$}
%
\put(72,59){$(c + x_{1})$}
\put(72,29){$(x_{1} + x_{2})$}
\put(72,-1){$(x_{2} + x_{3})$}
\end{picture}\\[13mm]
%図5:~~3段階2分割問題 : 最適割当 $(c > 0)$
\end{center}
\vspace{-8mm}
\uncover<5->{
\[
8^{2} + (-5)^{2} + (-3)^{2} + 2^{2} +1^{2} + (-1)^{2} \dql 104 \,\text{\RED{Optimal}}
\]
}
\end{frame}



%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Lucas Formula}
\begin{block}{\textbf{（Lucas formula）}}
\begin{eqnarray*}
\dsum_{k=1}^{n} F_{k}^{2} \eql F_{n}F_{n+1}
\end{eqnarray*}
\end{block}
\vspace{3mm}

\begin{table}[htbp]
%
\begin{center}
% \begin{tabular}{c|cccccccccccccccccc} \hline
\begin{tabular}{c|ccccccccccccc} \hline
$ n $     &  $ 0 $  &  $ 1 $  &  $ 2  $ &  $ 3 $ &  $ 4 $ &  $ 5 $  & $ 6 $ & $ 7 $ & $ 8 $ & $ 9 $ & $ 10 $ & $ 11 $ & $ 12 $ \\ \hline
%& $ 13 $ & $ 14 $ & $ 15 $ & $ 16 $   \\ \hline 
$ F_{n} $ &  $ 0 $  &  $ 1 $  &  $ 1 $ &  $ 2 $ &  $3 $ &  $ 5  $  & $ 8 $ & $ 13 $  & $ 21 $ & $ 34 $ & $ 55 $ & $ 89 $ & $ 144 $ \\ \hline
%& $ 233 $ & $ 377 $ & $ 610 $ & $ 987 $   \\ \hline
\end{tabular}
\end{center}
%\caption{stop reward} \label{tab:h1}
\end{table}
\vspace{-5mm}
\begin{center}
Table 1:~~Fibonacci sequence $ \{F_{n}\} $
%表 1 ~~フィボナッチ数列 $ \{F_{n}\} $
\end{center}

\pause
For exapmle, $n \dql 5$
\begin{eqnarray*}
& & F_{1}^{2} + F_{2}^{2} + F_{3}^{2} + F_{4} ^{2} + F_{5}^{2} \\[0.56mm]
& = & 1^{2} + 1^{2} + 2^{2} + 3^{2} + 5^{2} \\[0.56mm]
& = & 40 \\[0.56mm]
& = & F_{5} F_{6}
\end{eqnarray*}

\end{frame}






%%%%%%%%%%%%%%
\begin{frame}
\frametitle{}
%\frametitle{Lucas Formula}
%\begin{block}{\textbf{リュカの公式（Lucas formula）}}
%\begin{eqnarray*}
%\dsum_{k=1}^{n} F_{k}^{2} \eql F_{n}F_{n+1}
%\end{eqnarray*}
%\end{block}
%

Optimal value $V9$ of Number division problem is given by
\begin{eqnarray*}
V9 \eql 
 \left[(F_{9} - F_{7})^{2} 
+ (-F_{7})^{2} \right] + 
\left[(-F_{7} + F_{5})^{2} + F_{5}^{2} \right] \\[1.16mm]
 & & \ \ \ \ \ \ \ \ \ \ + \left[(F_{5} - F_{3})^{2} + (-F_{3})^{2} \right] 
	+ \left[(-F_{3} + F_{1})^{2} + F_{1}^{2} \right] \\[1.56mm]
\end{eqnarray*}
\pause
Clearly this leads to 
\begin{eqnarray*}
%
\eql  F_{8}^{2} + F_{7}^{2} + F_{6}^{2} + F_{5}^{2} + F_{4}^{2} 
+ F_{3}^{2} + F_{2}^{2} + F_{1}^{2} \\[1.56mm]%
\eql  F_{8} \ndot F_{9} = 104 \\
\end{eqnarray*}
by Lucas formula.
\end{frame}



%%%%%%%%%%%%%%
\begin{frame}
%\frametitle{Lucas Formula}
\frametitle{Quasi-cubic sum}
\begin{block}{\textbf{Lemma（quasi-cubic sum）}}
For $\{F_{k}\}$, we have
\begin{eqnarray*}
2 \dsum_{k=1}^{n} F_{k}^{2}F_{k+1} \eql F_{n}F_{n+1}F_{n+2}. 
\end{eqnarray*}
\end{block}
\begin{table}[htbp]
%
\begin{center}
% \begin{tabular}{c|cccccccccccccccccc} \hline
\begin{tabular}{c|ccccccccccccc} \hline
$ n $     &  $ 0 $  &  $ 1 $  &  $ 2  $ &  $ 3 $ &  $ 4 $ &  $ 5 $  & $ 6 $ & $ 7 $ & $ 8 $ & $ 9 $ & $ 10 $ & $ 11 $ & $ 12 $ \\ \hline
%& $ 13 $ & $ 14 $ & $ 15 $ & $ 16 $   \\ \hline 
$ F_{n} $ &  $ 0 $  &  $ 1 $  &  $ 1 $ &  $ 2 $ &  $3 $ &  $ 5  $  & $ 8 $ & $ 13 $  & $ 21 $ & $ 34 $ & $ 55 $ & $ 89 $ & $ 144 $ \\ \hline
%& $ 233 $ & $ 377 $ & $ 610 $ & $ 987 $   \\ \hline
\end{tabular}
\end{center}
%\caption{stop reward} \label{tab:h1}
\end{table}
\vspace{-3mm}
\begin{center}
Table 1:~~Fibonacci sequence $ \{F_{n}\} $
%表 1 ~~フィボナッチ数列 $ \{F_{n}\} $
\end{center}
%
\pause
%
This relates with a tiling problem in a plan 
or a space by using the unit of fibonacci 
square or cubes.
\end{frame}

\begin{comment}
\vspace{-3mm}
For example, $n \dql 4$
\begin{eqnarray*}
& & 2 \times \left(F_{1}^{2} F_{2} + F_{2}^{2} F_{3} +  F_{3}^{2} F_{4} 
+ F_{4}^{2} F_{5} \right)\\[0.56mm]
& = &  2 \times \left(1^{2} \cdot 1 + 1^{2} \cdot 2 + 2^{2} \cdot 3 
+ 3^{2} \cdot 5 \right) \\[0.56mm]
& = & 120 =  F_{4}F_{5}F_{6} \\[0.56mm]
\end{eqnarray*}
\end{comment}




%\begin{frame}
\begin{frame}[allowframebreaks]
\frametitle{References}

{\footnotesize 
\noindent
\ S.~Iwamoto, 
The Golden optimum solution in quadratic programming, 
%Ed. W. Takahashi and T. Tanaka, 
Nonlinear Analysis and Convex Analysis (NACA05), 
%Yokohama Publishers, 
Yokohama, 2007, pp. 199--205.\\[.7zw]

\noindent
\ S.~Iwamoto and Y.~Kimura, 
The Alternately Fibonacci Complementary Duality in 
Quadratic Optimization Problem, 
Journal of Nonlinear Analysis and Optimization, Vol.2, No.1, 2011, pp.93--103.
\\[.7zw]

\noindent 
\ S.~Iwamoto and M.~Yasuda, 
Golden optimal path in discrete-time dynamic optimization processes, 
%Ed. S.~Elaydi, K.~Nishimura, M.~Shishikura and N.~Tose,  
Advanced Studies in Pure Mathematics 53, June 2009, 
%Advances in Discrete Dynamic Systems, 
pp.77--86. 
%Proceedings of The International Conference on Differential Equations 
%and Applications (ICDEA2006), Kyoto University, Kyoto, Japan, July, 2006. 
\\[.7zw]
}% end of size
\end{frame}


%\section{Matrix form}


%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Matrix form for recurrsiveness}

Object function 
\[
I_3(x)=
   \sum_{i=0}^3 \{x_i^2 + (x_i - x_{i+1})^2\} \
\]
 is a quadratic of  $ x = (x_0, x_{1}, ~x_{2}, ~x_{3}) $, $x_0= c$:
\begin{eqnarray*}
I_3(x) = (x, B x) + 2(b, x) + c^{2}
\end{eqnarray*}
\[
b \dql (c, 0, 0, 0)^{T}
\] provided starting number equals $c$. Expanding it, 4 $\stimes$ 4 matrix
\[
B = \left(
\begin{array}{cccc}
 3 &  1  & 0 &  0     \\[1.26mm]
 1 &  3 & 1 & 0     \\[1.26mm]
    0 & 1  & 3 & 1      \\[1.26mm]
     0 & 0 & 1 & 2
\end{array}
\right) 
\]
becomes a posive definite
and \RED{threefold diagonal} form.
\end{frame}




%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{}
Its inverse is
$$ B^{-1} = \dfrac{1}{\,34\,}\left(
\begin{array}{rrrr}
    13 & -5  & 2 & -1 \\[1.26mm]
   -5 &  15  & -6  & 3   \\[1.26mm]
2 &  -6 &  16  & -8   \\[1.26mm]
-1 &  3 &  -8  & 21  
\end{array}
\right) ,
$$

%\begin{equation*}
\begin{eqnarray*}
\hat{x} \eql -B^{-1}b = -B^{-1}
\left(
\begin{array}{c}
c \\[1.26mm]
0  \\[1.26mm]
0 \\[1.26mm]
0 
\end{array}
\right) 
=
\dfrac{c}{\,34\,}
\left(
\begin{array}{r}
-13 \\[1.26mm]
5  \\[1.26mm]
-2 \\[1.26mm]
1  
\end{array}
\right).
\end{eqnarray*}

%Note that each element is one of the 
%"fibonacci" numbers.
%\end{equation*}
\end{frame}


%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{}
That is,
\[
\hat{x} \dql 
\dfrac{c}{\,34\,}
\left(
\begin{array}{r}
-13 \\[1.26mm]
5  \\[1.26mm]
-2 \\[1.26mm]
1  
\end{array}
\right) 
\dql
\dfrac{c}{\,F_{9}\,}
\left(
\begin{array}{r}
-F_{7} \\[1.26mm]
F_{5}  \\[1.26mm]
-F_{3} \\[1.26mm]
F_{1}  
\end{array}
\right) .
\]
The minimum value $m_4$ is given by
\begin{eqnarray*}
m_{4} \eql c^{2} - (b, B^{-1}b) \\[1.56mm]
\eql c^{2} - \dfrac{\,13\,}{\,34\,}\,c^{2} = \dfrac{\,21\,}{\,34\,}\,c^{2} \\[1.56mm]
\eql \dfrac{\,F_{8}\,}{F_{9}}\, c^{2}.
\end{eqnarray*}
When we \RED{starting with} $c=F_9$, these becomes
simple ones.


\end{frame}





%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{}
Its inverse equals
\begin{eqnarray*}
C^{-1} \dql  \dfrac{1}{\,34\,} \left(
\begin{array}{rrrr}
 21 & -8 & 3 & -1      \\[1.26mm]
 -8 & 16 & -6 & 2     \\[1.26mm]
 3 & -6 & 15 & -5     \\[1.26mm]
 -1 & 2 & -5 & 13  
\end{array}
\right)
\end{eqnarray*}
Thus 
%\begin{eqnarray*}
\[
\mu^{*} = C^{-1}b = 
\dfrac{c}{\,34\,}
\left(
\begin{array}{r}
21 \\[1.26mm]
-8 \\[1.26mm]
3 \\[1.26mm]
-1  
\end{array}
\right) 
=
\dfrac{c}{\,F_{9}\,}
\left(
\begin{array}{r}
F_{8} \\[1.26mm]
-F_{6}  \\[1.26mm]
F_{4} \\[1.26mm]
-F_{2}  
\end{array}
\right) 
\]
%\end{eqnarray*}
the maximum value is
\[
M_{4} = (b, C^{-1}b) = \dfrac{21}{\,34\,}c^{2}=\dfrac{\,F_{8}\,}{F_{9}}\,c^{2}
\]
\end{frame}

\begin{frame}
\frametitle{Notes}

These are easyly extended in $n \times n$ 
form.

The symmetric matrix $A_n$ of the objective:
\[
I_n(x)=
   \sum_{i=0}^n \{x_i^2 + (x_i - x_{i+1})^2\} \
\]
 is a quadratic of  $ x = (x_0, x_{1}, ~x_{2},\cdots, ~x_{n+1}) $, $x_0= c$:

\begin{block}{\textbf{Theorem}}
The determinant satisfies that
\begin{enumerate}
\item 
 \[
 |A_n| -3 |A_{n-1}| +|A_{n-2}| = 0, 
  |A_1| = 1 , |A_2|= 2
 \]
\item \[ |A_n| = F_{2n-1} 
   \text{($2n-1$-th fibonacci number)}
\]
\end{enumerate}
\end{block}

Details are omitted.
\end{frame}

\begin{frame}
\frametitle{Notes}

Refer to 

S.Iwamoto, A.Kira and M.Yasuda;
" Golden Duality in Dynamic Optimization ",
Proceeding of Kosen Workshop, MTE2008, 2008,
 1-13. 
\end{frame}

%\section{MDP}

\begin{frame}
\frametitle{MDP model}

MDP $(S,A,P,R)$:

$S; \{x_n\} \in R^1$,
$A; \{u_n\} \in R^1$,
$P: x_{n+1}=  x_n + u_n, x_0= c$,
$R: $
$$
\dsum_{n=0}^{\infty} \left( x_{n}^{2} + u_{n}^{2} \right)
~~~\mbox{and}~~~
 \dsum_{n=0}^{\infty} \left( u_{n}^{2} + x_{n+1}^{2} \right)
$$
with a given initial state  $x_0=c$.

This section minimizes two quadratic cost functions.
\end{frame}

\begin{frame}\frametitle{MDP}
Both problems are solved as a control process with criterion: 
$$
\dsum_{n=0}^{\infty}\left[x_{n}^{2} + (x_{n} - x_{n+1})^{2} \right] 
~~~\mbox{and}~~~
 \dsum_{n=0}^{\infty}\left[(x_{n} - x_{n+1})^{2} + x_{n+1}^{2} \right].
$$

\end{frame}

\begin{frame}
\frametitle{MDP model}

Let $ v(c) $ be the minimum value with initial value $c$. Then the value function $ v=v(x) $ satisfies Bellman equation: 
\begin{equation*}
 v(x) \dql \min_{-\infty < u < \infty}\left[x^{2} + u^{2} + v(x + u) \right]. \label{eqn:cp1} 
\end{equation*}
This has a quadratic form $ v(x) $. 

A quadratic minimum value function $ v(x) = \phi x^{2} $, where 
\begin{eqnarray*}
 \phi \eql \dfrac{\, 1 + \sqrt{5 \,} \,}{2},~~~~~~
 u \dql -\,\dfrac{\,\phi \,}{\, 1 + \phi \,} x .
\end{eqnarray*} 
%\end{frame}
Since 
%\begin{frame}\frametitle{}
\[
\min_{0\leq a \leq x}
\{A a^2 + B (x - a)^2\} =
\dfrac{x^2}{1/A + 1/B}
\]
hold,
so the continued fraction leads to Golden number.
\end{frame}

%\section{optimal stopping with a monotone rule }

%\section{Monotone Stopping Game.}           \label{sec:MonoStop}


\begin{frame}
\frametitle{monotone rule}

A monotone rule is introduced to sum up individual declarirations in 
a multi-variate stopping problem. The rule is defined 
by a monotone logical function and is equivalent to the winning class 
of Kadane('78).
There given $p$-dimensional random process $\{X_n; n=1,2,\cdots \}$ 
and a stopping rule $\pi$ by which the group decision determined
from the declararion of $p$ players at each stage.
The stopping rule is $p$-variate $\{0,1\}$-valued monotone 
logical function.  We consider two cases of rules with $p = 3$ 
as follows:
\begin{equation}                                 \label{rule(a)}
  \pi(x_1,x_2,x_3) = x_1 + x_2
\end{equation}
and
\begin{equation}                                 \label{rule(b)}
  \pi(x_1,x_2,x_3) = x_1 x_2 + x_1 x_3.
\end{equation}
\end{frame}


\begin{frame}
\frametitle{monotone rule}

Monotone stopping rule:

%
%  \begin{center}
%  \begin{minipage}{.5\textwidth}
  \begin{center}
  \begin{tabular}[t]{|ll|c|} \hline               \label{fig:1}
  $x_1$ &  $x_2$ &  $\pi(x_1,x_2,x_3)$ \\ \hline
    0   &    0   &   0 \\
    0   &    1   &   1 \\
    1   &    0   &   1 \\
    1   &    1   &   1 \\ \hline
  \end{tabular}

  {$\pi(x_1,x_2,x_3) = x_1+x_2$ for any $ x_3$}
  \end{center}
%  \end{minipage}
\end{frame}
%
%
\begin{frame}
\frametitle{monotone rule}
%  空白行なし
%  \begin{minipage}{.5\textwidth}
  \begin{center}
  \begin{tabular}[t]{|lll|c|} \hline               \label{fig:2}
  $x_1$ &  $x_2$ & $x_3$ &  $\pi(x_1,x_2,x_3)$ \\ \hline
    0   &    0   &   0   &    0 \\
    0   &    0   &   1   &    0 \\
    0   &    1   &   0   &    0 \\
    0   &    1   &   1   &    0 \\
    1   &    0   &   0   &    0 \\
    1   &    0   &   1   &    1 \\
    1   &    1   &   0   &    1 \\
    1   &    1   &   1   &    1 \\ \hline
  \end{tabular}

  {$\pi(x_1,x_2,x_3) = x_1x_2 + x_1x_3$}
  \end{center}
%  \end{minipage}
\end{frame}


\begin{frame}
\frametitle{monotone rule}
%
Without loss of generality, we can assume that each $X_n$ takes
the uniformly distribution on $[0,1]$. 
Then equilibrium expected values for each player is given as
\begin{center}
 {\doublerulesep=\arrayrulewidth  % 罫線の太さを2倍に \hline*2
 \begin{tabular}{l|ccc} \hline\hline \hline \\[-2ex]    
      & Player 1 & Player 2 & Player 3 \\[1.5ex] \hline \hline\hline 
   \\[-1.5ex]
   $\pi(x_1,x_2,x_3) = x_1 + x_2$ & $\dfrac{\sqrt{5}-1}{2}$ & 
       $\dfrac{\sqrt{5}-1}{2}$ & $0.5$     \\[2ex] \hline \\[-1.5ex]
   $\pi(x_1,x_2,x_3) = x_1 x_2 + x_1 x_3$ &  $1$   &  $\dfrac{\sqrt{5}-1}{2}$    
       & $\dfrac{\sqrt{5}-1}{2}$    \\[2ex] \hline\hline 
 \end{tabular}
 } %doublerule
 \\[1.5ex] 
 {Table 1. The equilibrium expected value for each players.}
\end{center}
\end{frame}


\begin{frame}
\frametitle{monotone rule}
In order to derive the value $ \phi^{-1} = \dfrac{\sqrt{5}-1}{2}$ , 
we consider an equilibrium stopping strategy of threshold type 
in the form $\{X_n > a\}$ for some $a$.
Bellman type equation for this game version will be given as 
YNK('82).
That is, each player declares  ^^ ^^ stop" or ^^ ^^ continue" 
if the observed value exceeds some $a$ or not. 
The event of the occurence is denoted by 
$D_n^{i} = \{ \mbox {Player $i$ declares stop}\}$.
Two trivial cases are the whole event $\Omega $ and the empty event 
$\emptyset$. 
\end{frame}


\begin{frame}
\frametitle{monotone rule}

In generally a logical function is assumed ^^ ^^ monotone" so
its function can be written as
$$
\begin{array}{ll}
     &\pi(x^1,\cdots, x^p ) \\
   = &x^i \cdot \pi(x^1,\cdots , \stackrel{i}{1} , 
       \cdots x^p) \\
     &+ \overline{ x^i} 
       \cdot \pi(x^1,\cdots , \stackrel{i}{0} , \\
     &
       \cdots x^p)  \quad x^i \in \{ 0, 1\} \,\, \,  \forall i
\end{array}
$$ 
where $\overline{ x^i} = 1-  x^i$.  
Corresponding to this expression,
$$ 
\begin{array}{ll}
    & \Pi(D^1,\cdots, D^p ) \\
  = & D^i \cdot \Pi(D^1,\cdots , \stackrel{i}{\Omega } , 
       \cdots D^p) \\
    &+ \overline{ D^i} \cdot 
       \Pi(D^1,\cdots , \stackrel{i}{\emptyset } , \cdots D^p) 
\end{array}
$$ 
where $\overline{ D^i} $ is the complement of the event $D^i$.
\end{frame}


\begin{frame}
\frametitle{monotone rule}

The general equation for the expected for player $i$ equals
\begin{equation}                                    \label{eq:101}
   E\left[(X_n^i - v^i)^{+} 
      {\bf 1}_{\Pi(D_n^1,\cdots , \stackrel{i}{\Omega}, \cdots D_n^p)}\right]
   + E\left[(X_n^i - v^i)^{-} 
      {\bf 1}_{\Pi(D_n^1,\cdots , \stackrel{i}{\emptyset}, 
      \cdots D_n^p)}\right]
\end{equation}
where $D_n^i = \{ X_n^i \geq v^i\}$ and 
$(x)^+ = \max\{x,0\}, (x)^- = \min\{x,0\}$. 
\end{frame}

\begin{frame}
\frametitle{monotone rule}

If we assume an independence case 
between player's random variable $X_n^i$ for each $i$. The equation
(\ref{eq:101}) becomes as
\begin{equation}                                    \label{eq:102}
   \beta_n^{\Pi(i) } E\left[(X_n^i - v^i)^{+}\right]
   - \alpha_n^{\Pi(i) } E\left[(X_n^i - v^i)^{-} \right]
\end{equation}
where
{rule(a)}Our objection is to find an equilibrium strategy and values of playes 
for a given monotone rule as the rule (\ref{rule(a)}) and (\ref{rule(b)}).
\end{frame}


\begin{frame}
\frametitle{monotone rule}
A sequence of expected value (a net gain) under the situation formulated 
in the section is obtained as 
\begin{equation}                                    \label{eq:103}
   v_{n+1}^i = v_n^i + \beta_n^{\Pi(i) } E\left[(X_n^i - v_n^i)^{+}\right]
   - \alpha_n^{\Pi(i) } E\left[(X_n^i - v_n^i)^{-} \right]
\end{equation}
for player $ i = 1, \cdots, p$ and $n$  denotes a time-to-go.
The details refer to Theorem 2.1 in YKN\cite{YNK82}.
%
Under these derivation, now we are able to calculate the optimal (equilibrium) 
value $ v^i = \lim_{n } v_n^i$ for player $i= 1,2,3$ for the rule.
\end{frame}

\begin{comment}
\begin{frame}
\frametitle{monotone rule}
A value function $ v(x) $ of the multivariate optimal stopping where three persons and
the rule is as
\[
  \phi(x_1,x_2,x_3) = x_1 \cdot x_2 + x_3
\]
of the logical operation.

Then the first and second player's gain for 
uniform distribution $[0,1]$ is the Golden number since it is by solving $x^2 = x+1$ and the third is $1$. 

\end{frame}
\end{comment}


%\section{optimal stopping with a monotone rule }
\begin{frame}
\frametitle{monotone rule}

Refer to

 S.Iwamoto , Masami Yasuda;
" Dynamic programming creates the Golden ratio, too ",  Kyoto RIMS Kokyuroku 1477, 2006, pp.136-140. 


M.Kurano, M.Yasuda and J.Nakagami;
"Multi-variate stopping problems with a monotone rule",  J Oper Res Soc Japan, Vol.25, pp.334-350(1982)  . 

\end{frame}

\end{document}



\bibitem{YNK82}
  M.~Yasuda, J.~Nakagami, M.~Kurano;
  ``Multi-variate stopping problems with a monotone rule'',
  J.~Oper.~Res.~Soc.~Japan, vol.~25, No.~4, 334-349, (1982).



