\documentclass{article}

\evensidemargin=0.15in \oddsidemargin=0.15in \textwidth=6.25in
\topmargin=0.0in \headheight=0.0in \headsep=0.0in
\textheight=8.75in
\renewcommand{\baselinestretch}{1.2}
%
\newcommand{\Sessiontitle}[1]
 {\noindent \textbf{\large Session Title: {#1} \\}}
\newcommand{\Presentingauthor}[1]
 {\noindent \textbf{{#1}}}
\newcommand{\Talktitle}[1]
 {\noindent \textbf{\large Title: {#1}} \\}
\newcommand{\Affiliation}[1]{{#1}}
\newcommand{\email}[1]{{#1} \\}
\newcommand{\Coauthor}[1]
 {\noindent {\textbf{#1}}}
\renewcommand{\abstract}[1]
 {\noindent \textbf{Abstract: }{#1} \\}
 \iftrue %%%%%%% If you do not have the "amsmath" or "amsfonts" package:
 % \iffalse %%%%   Comment out the "iftrue" line, uncomment the "iffalse" line
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{verbatim}
%
% Definitions in case you do have the ams packages
%
\newcommand{\field}[1]{\mathbb{#1}}
\DeclareMathOperator{\PR}{\field{P}}             % Probability
\DeclareMathOperator{\E}{\field{E}}              % Expectation
\def\N{\field{N}}                                % nonnegative integers
\def\R{\field{R}}                                % Blackboard R - Reals
\def\F{\field{F}}                                % Functions/stationary policies
\def\A{\field{A}}                                % Action space
\def\X{\field{X}}                                % State space

\def\Z{\field{Z}}
%
% Definitions in case you do not have the ams packages
%
\else
\def\PR{\mathop{\rm I\kern -0.20em P}\nolimits}  % Probability
\def\E{\mathop{\rm I\kern -0.20em E}\nolimits}   % Expectations
\def\N{\mathop{\rm I\kern -0.20em N}\nolimits}   % Nonnegative integers
\def\R{\mathop{\rm I\kern -0.20em R}\nolimits}   % Blackboard R - Reals
\def\F{\mathop{\rm I\kern -0.20em F}\nolimits}   % Functions/stationary polices
\def\A{{A}}                                      % Action space
\def\X{{X}}                                      % State space
\fi
\def\r{C}
% ----------------------------------------------------------------
\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small

%\documentclass[a4paper]{jsarticle}
%\usepackage{latexsym,amsmath,amssymb}
\usepackage{latexsym,amssymb}  % ansmath is another declarilation 
\usepackage{theorem}
%\usepackage[psamsfonts]{amssymb}
\usepackage{wrapfig}
%\begin{proof}[Proof of hogehoge]
%�藝�̏ؖ�\end{proof}
\usepackage{mathpazo}            
\usepackage{booktabs}
%\usepackage[dvips]{graphicx,color}

\newtheorem{prop}{Proposition}[section]%����
\newtheorem{defn}{Defnition}[section]%��`
\newtheorem{assm}{Assumption}[section]%����
%                       theorem ---> theorem
\newtheorem{theorem}{Theorem}[section]%�藝
\newtheorem{cory}{Cor.}[section]%�n
\newtheorem{lema}{Lemma}[section]%���
\newtheorem{remk}{Remark}[section]%����
\newcommand{\proof}{\textit{proof�F}}%�ؖ�
%\newtheorem{Toi}{��}[section]   %�₢ 

\renewcommand{\theequation}{%
\thesection.\arabic{equation}}
%\@addtoreset{equation}{section}

\title{
The best choice problem for random number of objects 
 with a refusal probability
%%
}
% 
%  \Presentingauthor{Masayuki Horiguchi}, 
%  \Affiliation{Kanagawa University, Japan}, 
%  \email{horiguchi@kanagawa-u.ac.jp}
%  \Coauthor{Masami Yasuda}, \email{yasuda@math.s.chiba-u.ac.jp}
\author{Masayuki Horiguchi, \\ Masami Yasuda}

\begin{document}
  %\Talktitle{
%%

\maketitle


  \abstract{
In this note, we will consider the best choice problem for random number of objects with a refusal probability. There are many papers and books on this subject from Chow/Robbibs/Siegmund(1971), Siryaev(1973) downward.  These problems has been close relations with the martingale theory, the potential theory, the optimality principle in the mathematical programming. And now it is derived the optimal rule by using the sum-the-odds theorem. Refer to Ferguson(2006), Bruss(2003), Tamaki(2001), Hsiau/Yang(2000) etc. It would be prefered to call it the odds-theorem rather than the secretary problem or the best choice nowdays.  Here we adapt a classical analysis to obtain its optimal value for the problem on Markov processes.

Firstly the formulation of stopping problem for Markov processes are given and its optimal equation of the value are designated. Since the secretary problem has a special transition probability, we show the optimal value is calculated as One-Look ahead policy or monotone stopping problem. Then it is treated asymptotically and solve the value in the explicitly form by a differential equation. Some equivalence relation is shown between the decision-theoretic form of the optimal equation and the transition probability with refusal. 

In the last, by a translation from the case of random number of objects to the standard form of optimal stopping problem, we could obtain the optimal value in the cited case of title. Also a variation for the selection is considered.
% (Not more than 250 words.)
}


\section{Formulation and Notations}
The optimal stopping problem is a special case of Markov decision processes 
and the decision maker can either select to stop so as receiveing rewards,
 or to pay costs and continue observing the state.
Let $x_n, n=0,1,2,\cdots$ be a Markov Chain 
with a transition probability $P=P(i,j), i,j \in S$ 
over a state space $S$ in $R^1$.
We assume that $S$ is countable, but this is inessential and 
for our discussion so that the scaling limit case of problems 
with the random numbers can be treated.
For a stopping time $\tau$, the aim is to maximize the expectation
of payoff $v(i;\tau)$ starting at $i$ and its optimal value $v(i)$ 
defined by
\begin{equation}
 v(i) = \sup_{\tau < \infty} v(i,\tau) 
      = \sup_{\tau < \infty} 
     E\left[ r(x_{\tau} - \sum_{n=0}^{\tau} c(x_n) \,\,\Big| \,\, x_0=i\right],
     i \in S
\end{equation}
where $r(i)$ and $c(i)$ $(i \in S)$ mean an immediate reward
and a paying cost respectively.
Refer to Chow/Robbibs/Siegmund(1971), Siryaev(1973) etc.

The relation between Markov potential theory and Dynamic 
Programming or Markov decision processes is well known.
The optimality equation is reduced as follows.
\begin{equation}
  v(i) = \max \{r(i), \, Pv(i) - c(i) \}, \, i \in S.
\end{equation}

Consider the set of states for which stopping immediately is at least
as gppd as stopping after exactly one more period. Denote this
set by
\begin{equation}\label{eq:1.3}
   B = \{ i \in S \,\, | \, \, r(i) \geq Pr(i) -c(i) \}
\end{equation}
where $Pr(i) = \sum_{j \in S } P(i,j) r(j)$. 
The policy, defined by hitting time of this set $B$,
is called a {\it One-stage Loog Ahead}(abridged as OLA) policy,
refer to Ross(1983).
It is sufficient that the OLA policy is optimal if
$B$ is closed and eventually hits to the set.
That the set is closed means if
\begin{equation}
  P(i,j) = 0 \quad \mbox{for} \quad i \in B, j \in \overline{B} 
\end{equation}
where $\overline{B}$ denotes the complement of the set $B$.

There are many discussions on Markov stopping theory excellently
as the excessive function, the martingale theory and so on,
however the general framework does not cover for specific solution
in the exploit structure or interesting features.
The aim of this note is to obtain the explicit optimal
value associated with OLA policy and various problems in the
asymptotic form. Firstly  the motivated case for the classical 
secreraly choise problem and then for the variation of the
case with the refusal probability. 
The odd-theorem by Bruss(2000) and Ferguson(2008) will be applied
also as the optimal stopping rule.



\section{Markov Potential}

Let $P_A$ denote the restriction to a subset $A$ of S
for the transition probability $P$, that is,
\begin{equation}
  P_A(i,j) = P(i,j) {\bf 1}_A(i)
\end{equation}
where the indicator of A is 
${\bf 1}_A(i) = 1/0 (i \in A)/(i \notin A)$. 
We shall use the notation of a potential as 
\[
   Nf(i) 
   = \lim_n \left[\{I + P + P^2 + \cdots + P^k \} f
            \right](i)
   \quad i \in S.
\]

\begin{theorem}
 If we assume that
 \begin{equation}
  \begin{array}{l}
   \lim_k \left[(P_{\overline{B}})^k r\right](i) = 0 \\[.5ex]
   \left[ N_{\overline{B}} (P_B r -c) \right] (i) < \infty 
  \end{array}
 \end{equation}
 for $i \notin B$, then
 \begin{enumerate}
  \item[(i)] the OLA policy $\tau_B$ is optimal,
  \item[(ii)]
   the optimal value $v(i), i \in S$ is given by
   \begin{equation}\label{eq:2.7}
    v(i) = r(i) + N(Pr -r -c)^+ (i)
    = \left\{ 
       \begin{array}{lll}
         r(i) & \mbox{on} & B  \\
         N_{\overline{B}} (P_B r -c)(i) 
              & \mbox{on} & \overline{B}
       \end{array}
     \right.
   \end{equation}
  \end{enumerate}
\end{theorem}
where $+$ is the positive part of the function,
and $N$ and $N_{\overline{B}}$ are potentials with 
respect to $P$ and $P_{\overline{B}}$ respectively.

\section{The best choice Problem}

 \subsection{Classical Problem}

 The secretary problem is an optimal stopping problem based on
relative ranks for objects for objects arriving in a random
fashion. The objective is to find the stopping rule
that maximizes the probability of stopping at the best object among
the sequence.
The formulation of the problem as Markov processes is given by
Dynkin/Yushkevitch(1969). 

The state space is $S=\{1,2,3,\cdots,n\}$ and the reward, 
its win of probability is $r(i) = i/n$,
the transition probability is $P(i,j) = \dfrac{i}{j(j-1)}$,
 $1 \le i < j \le n$.
 The optimal value $v(i)$, is 
\begin{equation}
  v(i) = \max \{i/n ,\, \sum_{j = i+1}^n \dfrac{i}{j(j-1)}v(j)\},
  \quad  i=1,2,\cdots, n-1, \qquad v(n) =1.
\end{equation}

Taking a scale limit of $i/n \to x$ as $i,n \to \infty$,
it becomes that
\begin{equation}
  v(x) = \max \{x ,\, x \int_{x}^1 \dfrac{v(y)}{y^2} \, dy\},
  \quad  x \in S=[0,1], \qquad v(1) =1.
\end{equation}
where the state space is $S = [0,1]$.
The solution is well known as
\begin{equation}
  v(x) = \left\{\begin{array}{lll}
            e^{-1} & on & [0,e^{-1}], \\
            x      & on & [e^{-1} ,1].
        \end{array}\right.
\end{equation}

By extending the reward $r(x)$ in general, that is,
\begin{equation}
  v(x) = \max \{r(x) ,\, x \int_{x}^1 \dfrac{v(y)}{y^2} \, dy\},
  \quad  x \in S=[0,1], \qquad v(1) =1.
\end{equation}
it is also the OLA policy is
still optimal.

\begin{assm}\label{ass:3.1}
The function
\[
   h(x) = r(x) - x \int_{x}^1 \dfrac{r(y)}{y^2} \, dy
\]
is finite on $[0,1]$ for a given $r(x)$ and
it changes its sign from $-$ to $+$ only once as $x$
increases $0$ to $1$.
\end{assm}
So there exists a unique solution $\alpha$ of 
the equation $h(x) = 0$.
\begin{theorem}
Using this solution, the assumption \ref{ass:3.1}
implies that 
\begin{equation}
  v(x) = \left\{\begin{array}{lll}
            r(\alpha) & on & [0, \alpha], \\
            r(x)      & on & [\alpha ,1].
        \end{array}\right.
\end{equation}
\end{theorem}
\noindent
Because
the result of the equation (\ref{eq:2.7})
is calculated as
\[
  P_Br(x) =r(\alpha) \dfrac{x}{\alpha},
\quad
  \bigl(P_{\overline{B}}\bigr)^nP_B r(x) =
    r(\alpha) \dfrac{x}{\alpha} 
    \log^n \left(\dfrac{\alpha}{x}\right) / n!,
\quad
  N_{\overline{B}}P_B r(x) =
    r(\alpha)
\]
by using the notation (\ref{eq:1.3}).

Note also that
\[
   -x \dfrac{d\,v(x)}{dx} = \bigl(r(x) - v(x)\bigr)^{+},
    \quad x \in[0,1].
\]

 \subsection{Problem with a refusal probability}
A variant for the classical best choice problem
is considered by Smith(1975) inducing a refusal
probability.
A given $p$ means the probability of {\it not}
refused case and the quality $1-p$ is a probability
of the refusal. When there occues no refusal, that is,
the usual standard problem corresponds to $p=1$.
The asymptotic form of the transition probability
is given as
\begin{equation}
 P(x, dy ) = 
   \left\{ 
    \begin{array}{ll}
      p y^{-1} (x/y)^p \, dy & 0 < x < y < 1, \\
      0 & otherwise
    \end{array}
   \right.  
\end{equation}

Similarly before
\begin{assm}\label{ass:3.2}
The function
\[
   h_p(x) = r(x) - p \int_{x}^1 \dfrac{r(y)}{y} (x/y)^p  \, dy
\]
is finite on $[0,1]$ for a given $r(x)$ and
it changes its sign from $-$ to $+$ only once as $x$
increases $0$ to $1$.
Its unique solution is denoted by $\alpha_p$ of 
the equation $h_p(x) = 0$.
\end{assm}

\begin{theorem}
Using this solution $\alpha_p$, 
the assumption \ref{ass:3.2}
implies that 
\begin{equation}
  v(x) = \left\{\begin{array}{lll}
            r(\alpha_p) & on & [0, \alpha_p], \\
            r(x)      & on & [\alpha_p ,1].
        \end{array}\right.
\end{equation}
\end{theorem}

It is also known the technique of using
a differential equation by Mucci(1973).
We could apply the case by this technique.
Let
\[
   V(x) =   p \int_x^1 \dfrac{r(y)}{y} (x/y)^p  \, dy,
\qquad x \in [0,1]
\]
which means a contditional optimal value. This 
satisfies
\begin{equation}
   \left\{ \begin{array}{ll}
    - x \dfrac{dV(x)}{dx} 
   = p \bigl(r(x) - V(x)\bigr)^+,
     & x \in [0,1], \\[2ex]
    V(1) = 0. & \\
   \end{array} \right.
\end{equation}
The optimal value at the begining $v^* = V(0) = r(\alpha_p)$.
Confirming that the case of $r(x)= x$, 
the equation $h_p(x) =0$  solves $x = \alpha_p = p^{1/(1-p)}$
which consist with the result by Smith(1975).





\section{Random number of objects}
\subsection{Formulation for random number of objects}
The discussion on the stopping choice problem with
a random number of objects is firstly by
Presman/Sonin(1972). Then Rasmussen/Robbins(1975),
Tamaki(1979),
Irle(1980), Petruccelli(1983) etc.

If we restrict ourselves that the support of distribution
for a number of objects is {\it bounded}, the technique of
the previous scaling limit could be applied.


\begin{assm}
A random number of objects $N$ is bounded and let
\[
   n = \inf\{ k \ge 1; P(N>k) = 0\}.
\]  
\end{assm}
By using the notation of 
$p_i = P(N=i)$ and $\pi_i = P(N \ge i) = \sum_{k \ge i} p_i$,
the transition probability matrix for this case
is as follows:
\begin{equation}
  \begin{array}{ll}
  p(i,j) = \dfrac{i \, \pi_j}{j(j-1)\, \pi_i}, & 1 \le i < j \le n,\\
  p(i,n) = \displaystyle\sum_{k=i+1}^n \dfrac{i\, p_k}{k\, \pi_i}, & 1 \le i < n, 
      \quad p(n,n) = 1,\\
  r(i) = \displaystyle\sum_{k=i}^n \dfrac{i\, p_k}{k\, \pi_i}, & c(i) =0, \, \forall i.
  \end{array}
\end{equation}
If we denote the distribution by $\Phi(x), x \in [0,1]$ 
of its random number for objects,
and taking the scale limit of $k,n \to \infty$ 
with $k/n =x$, then $v(i) \to V(x)$ and 
\[
\begin{array}{l}
p_k /\pi_k  \to d\Phi(x)/(1-\Phi(x)),\\[1.5ex]
r(k+1) 
  = \displaystyle\sum_{k=i}^n \dfrac{i\, p_k}{k\, \pi_i}
  = \displaystyle \dfrac{i}{\pi_i}\sum_{k=i}^n \dfrac{p_k}{k} 
\to R(x) =\dfrac{x}{1-\Phi(x)}\displaystyle \int_x^1 y^{-1}\, d \Phi(y),
\end{array}
\]
the resulting the differential
equation is given as
\begin{equation}\label{eq:4.17}
  \left\{
  \begin{array}{l}
   -x \, dV(x) + x\, \dfrac{V(x)}{1-\Phi(x)}\, d \Phi(x) 
    =  (R(x) - V(x))^{+}\, dx, \quad x \in [0,1] \\[2ex]
   V(1) = 0
  \end{array}
  \right.
\end{equation}
where 
\begin{equation}\label{eq:4.18}
       R(x) = \dfrac{x}{1-\Phi(x)} \int_x^1 y^{-1}\, d \Phi(y).
\end{equation}
The details refer to Yasuda(1984).
\begin{assm}
We assume that $d\Phi$ satisfies the conditions:
 \begin{enumerate}
  \item 
    \(
    (1-\Phi(x))^{-1} \displaystyle\int_x^1 y^{-1}d\Phi(y)
    \to 1 \quad as \quad x \to 1,
    \)
  \item
    \(
     x \displaystyle\int_x^1 y^{-1}d\Phi(y)
    \to 0 \quad as \quad x \to 0.
    \)
 \end{enumerate}
\end{assm}
This assumtion implies that
\(
   R(x) \to 0 \, (x \to 0)
\)  
and 
\( 
   \to 1 (x \to 1).
\)
In the usual non-random case, $R(x) = x$, 
these conditions are satisfied since
 $ \dfrac{1}{1-\Phi(x)} \displaystyle\int_x^1 y^{-1}\, d \Phi(y) =1$
for $x \neq 1$.


Typical example of a random number $N$ is 
the uniformly distributed case on a partial interval
$\{n-m, n-m +1,\cdots, n-1,n\}$ of 
$\{1,2,\cdots,n\}$ provided that $(1 \le m \le n)$. 
Letting $\theta = m/n$ is fixed for $n,m \to \infty$,
$\Phi(x) = 0, \, (0 < x <1-\theta) ,
\, \,  = (x - 1 +\theta)/\theta$, $(1-\theta < x < 1)$.

\begin{center}
\begin{tabular}{lll}
\hline
 case & $\alpha$: threshold & $v^*$:optimal value \\
\hline 
  $1 - \theta$ $\ge$ $e^{-2}$ & $\sqrt{1-\theta}e^{-1}$ 
  & $- \dfrac{\sqrt{1-\theta}}{\theta} \log(1-\theta) e^{-1}$ \\[1.5ex]
  $1 - \theta$ $\le$ $e^{-2}$ & $e^{-2}$ 
  & $2 e^{-2} /\theta$ \\
\hline
\end{tabular}
\end{center}
If $\theta \to 1$ it tend to $2e^{-2}$
as discussed in Presman/Sonin(1972) etc.
Alternatively, if $\theta \to 0$, this reduces to 
the non-random classical problem and it tend to $e^{-1}$ as is 
well known.
However it is interesting that the threshold $\alpha= e^{-2}$ 
does not depent on $\theta$ in case of 
$1-\theta \approx 0$, that is, case of the ambiguity
is being in spread.



\subsection{Random number of objects with refusal}

Here we would like to impose a refusal probability
for the model. As it had been shown that,
from the optimal equation of classical problem 
to one with a refusal in section 3, 


Instead of $V(x)$ in the optimality equation (\ref{eq:4.17}), 
%let $v(x) = $,
consider 
$dv(x) = dV(x) - \dfrac{V(x)}{1-\Phi(x)}\, d \Phi(x) $.
Then, it holds that
\begin{equation} \label{(eq:4.19)}
 v(x) = \max\left\{R(x) ,\,\, 
   \dfrac{x}{ 1-\Phi(x)}
   \int_x^1 (1-\Phi(y)) y^{-2} v(y) \, dy \right\}
\end{equation}
with $R(x)$ in (\ref{eq:4.18}).

In a general consideration of decision for "stop",
there exist some possibility of "continuity" in the 
refusal problem. So
for given transition matrix $P$ and reward $r$,
the optimality equation of stopping problem:
\(
  v(x) = \max\{R(x), Pv(x)\} , \, 0 \le x \le 1
\)
have a modification with a refusal probability
$p(x), 0 \le x \le 1$
becomes
\begin{equation} \label{eq:41}
  v(x) = \max\{p(x)\,R(x) + (1-p(x))\,Pv(x), \,\,Pv(x)\} , \quad 0 \le x \le 1.
\end{equation}
By letting 
\begin{equation}
  \begin{array}{l}
   Pv(x) = \dfrac{x}{ 1-\Phi(x)}
   \displaystyle\int_x^1 (1-\Phi(y)) y^{-2} v(y) \, dy, \\[1.5ex]
   q(x) = \exp\Big( \displaystyle\int_x^1 y^{-1} (1-p(x)) \, dy \Big)
\quad
and 
\quad
   h(x) = \displaystyle\int_x^1 y^{-1} \, d\Phi(y),
  \end{array}
\end{equation}
the following assumtion assures Theorem \ref{thrm:4}.
\begin{assm}
\label{assm:3}
Assume that
\begin{equation} \label{eq:42}
   H_p(x) = h(x) - q(x) \int_x^1 \dfrac{h(y)\, p(y)}{y\, q(y)} dy 
\end{equation}
changes its sign once from $-$ to $+$ as $x$ 
increase.
\end{assm}


\begin{theorem}\label{thrm:4}
If Assumption (\ref{assm:3}) is satisfies,
the solution is given as 
the value
\begin{equation}
  \alpha_p^* = \left\{ \begin{array}{l}
                 \inf\{ x ; H_p(x) \ge 0 \} \\ 
                 1 \quad {if \, empty} 
               \end{array} \right.
\end{equation}
determine its threshold policy and so the optimal 
value $v(0+)$ in (\ref{eq:41}) .
    

\end{theorem}

However in order to display the above assertion or
explicit form, it is not easy for us.  
Even the simplest case of $p(x) = p \, (0 < p <1)$ and
$\Phi(x) = x \,(0 \le x \le 1)$, 
it needs the discussion on
Lambert W function. 



\begin{thebibliography}{99}

\bibitem{br00}
Bruss,F.T.(2000); Sum the odds to one and stop, Ann.Prob. 28(3), 1384-1391.

\bibitem{br03}
Bruss,F.T.(2003); A note on Bounds for the Odds-Theorem of Optimal stopping,
Ann. Prob. 32, 1859-1861.

\bibitem{brsa87}
Bruss,F.T., Samuels,S.M.(1987); A unifies approcah to a class of optimal
selection problem s with an unknown number of options, Ann.Prob.15(2) 824-830.

\bibitem{chrosi71}
Chow,Y.S., Robbibs,H. and Siegmund,D.(1971): Great Expectations:
  The Theory of Optimal Stopping, Houghton Mifflin, Boston.

\bibitem{da85}
Darling,D.A.(1985):Contribution to the optimal stopping problem,
 Z. Wahr. verw.Gebiete 70, 525-533.

\bibitem{dusa65}
Dubins,L.E. and Savage,L.J.(1965): How to Gamble if you must: Inequalities for
Stochastic Processes, McGrow-Hill, New York.

\bibitem{dyyu69}
Dynkin,E.B. and Yushkevitch,A.A.(1969): Theorems and Problems on 
Markov Processes, Translation: Plenum Press, New York.

\bibitem{fe08}
Ferguson, T.S.(2008); The sum-the-Odds theorem with application to a stopping 
game of Sakaguchi, http://www.math.ucla.ucls.edu/~tom/

\bibitem{fe89}
Ferguson, T.S.(1989); Who solved the secretary problem? Statistical Science, 
4 ,282-296.

\bibitem{fe04}
Ferguson, T.S.(2004);Selection by Committee, in Advances in Dymnamic Games,
A.S.Nowak and K.Szajowski eds., 183-188, Birkhauser.

\bibitem{ho74}
Hordijk,A.(1974); Dynamic Programming and Markov Potential Theory, Mathematisch
Centrum, Amsterdam.

\bibitem{hsya00}
Hsiau, Shoou-Ren and Yang Jiing-Ru(2000);A natural variation of 
the standard secretary problem, Statistica Sinica, 10, 639-646.

\bibitem{ir80}
Irle,A.(1980);On the best choice problem with random population size,
Z.Oper.Res. 24, 177-190.

\bibitem{kata03}
Kawai,M. and Tamaki,M.(2003); Choosing either best or the second best when
number of applicants is random, Computers and Mathematics with Applications, 
46, 1065-1071.

\bibitem{mu73}
Mucci,A.G.(1973); Differential equations and optimal choice problem,
Ann.Statist.,1, 104-113.

\bibitem{pr74}
Prabhu,N.U.(1974); Stochasitic control of quequing systems, Nav. Res. Logist.Q.
21, 411-418. 

\bibitem{prso72}
Presman,E.L.,Sonin,I.M.(1972);
The best choice problem for a random number of objects,
Theo.Prob.Appli. 4 , 657-668.

\bibitem{prso72r}
Presman, E. L.; Sonin, I. M.(1972): The problem of best choice in the case 
of a random number of objects. (Russian) Teor. Verojatnost. i Primenen. 17 
(1972), 695--706.

\bibitem{ro83}
Ross,S.M.(1983); Introduction to Stochastic Dynamic Programming, 
Academic Press, New York.

\bibitem{raro75}
Rasmussen, W.T., Robbins,H.(1975); The candidate problem with unknown
 population size, J.Appl.Prob. 12, 692-701.

\bibitem{sa91}
Samuels,S.M.(1991);Secretary problem, in Handbook of Sequential Analysis,
 B.K.Ghosh and P.K.Sen, eds. Dekker, New York.

\bibitem{sh73}
Shiryaev,A.N.(1973); Statistical Sequential Analysis, Translation:
American Mathematical Society, Providence.

\bibitem{sm75}
Smith,M.H.(1975); A secretary problem with uncertain employment,
J.Appl.Prob., 12, 620-624.

\bibitem{ta79}
Tamaki,M.(1979);

\bibitem{ta01}
Tamaki,M.(2001);Optimal stopping on trajectories and the ballot problem,
J.Appl.Prob., 38, 946-959.

\bibitem{ta02}
Tamaki,M.(2002);Recent developments in the secretary problem. (Japanese) 
Development of the optimization theory for the dynamic systems and their 
applications (Japanese, Kyoto, 2002). RIMS No.1263, 131--150.

\bibitem{ya84}
Yasuda,M.(1984); Asymptotic results for the best-choice problem with
 a random number of objects, J.Appl.Prob. 21, 521-536.

\bibitem{ya88}
Yasuda,M.(1988); On the value for OLA-optimal stopping problem by potential
theoretic method, Lecture Notes in Math 1299 Springer-verlag, 517-580. 

\end{thebibliography}

\end{document}

% \subsection{A game Version of zero sum cases}

We note here that a game version of zero sum cases
are discussed.
There are several versions for zero sum cases. 

Refer to 
E. B. Dynkin, Game variant of a problem of optimal stopping, Soviet Math. Dokl., 10 (1969), pp. 16-19.
Erik Ekstrom and Goran Peskir, Optimal Stopping Games for Markov Processes
  SIAM J. Control Optim. Volume 47, Issue 2, pp. 684-702 (2008).
Ferenstein, Elzbieta Z. Randomized stopping games and Markov market games. Math. Methods Oper. Res. 66 (2007), no. 3, 531--544.


Let $f(x)$ and $g(x)$ be two functions of bounded variation
over $[0,1]$, right continuous and with left-hand limits, then,
by Fubini's theorem,
\[
 d(fg) (x) = f(x)dg(x) + g(x) df(x) -\{f(x) -f(x-)\}dg(x)
           = f(x-)dg(x) + g(x) df(x).
\]  

\end{document}

