数理解析研究所講究録
978 巻 1997 年 71-78

71$\mathrm{S}\mathrm{I}\mathrm{N}\mathrm{G}\mathrm{L}\mathrm{E}^{-}\mathrm{L}\mathrm{E}\mathrm{v}\mathrm{E}\mathrm{L}$STRATEGIES FOR FULL-INFORMATION$\dot{6}\mathrm{E}5\mathrm{T}-\mathrm{C}\mathrm{H}\mathrm{o}|\mathrm{C}\in$

PROBLEMS.

$*.\cdot+_{\llcornerarrow}’::arrow/^{-\dot{\mathrm{v}}}--\mathrm{d}\overline{\sim}\eta_{\overline{\mathrm{c}}}*\cdot\ovalbox{\tt\small REJECT} \mathrm{X}$$\overline{\mathrm{R}}^{\mathrm{U}}$$\mathrm{I}$$/\wedge\star(f]_{1}.n\mathrm{o}f\lambda$

LA;’$\mathrm{k}^{\lfloor)\{_{-}’\vdash}’||)$$*\mathrm{x}_{\dot{7}^{\backslash }y7\eta_{\mathcal{I}-}}|0.\backslash 1\dot{*}+\mathrm{X}\mathrm{k}^{\grave{\mathrm{r}}}.h3\eta_{\chi+}(\mathrm{K}rL\gamma\}z\mathrm{f}\dot{\mathit{0}}\hat{t}s’ \mathrm{z}\mathrm{A}\mathrm{J}Cws\kappa l^{\sim}’$

ABSTRACT. Some best choice problems with full information and imperfect observation and their extension to two .ayer competitive
are discussed. Players
observe one by one
a sequence of $iid$ random variables
a known
continuous distribution with the objective of choosing one of the largest. The observations of the random variables are imperfect and the player (or players) is (are)informed only of whether it is larger than or less than a previously determined decisionlevel. The problem is to find the optimal decision level that maximizes the probabilityof achieving his objective. The solution of this one person game is derived. In thetwo player competitive situation two typical types of the optimal stopping games forchoosing the best observation, transformed into continuous games
on the domain: solutions of them are given.
$\mathrm{p}1$$8\mathrm{i}\mathrm{t}_{\mathrm{U}\mathrm{a}}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{f}\mathrm{r}\dot{o}\mathrm{m}$$8\mathrm{e}\mathrm{q}_{\mathrm{U}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{y}$$k$$\mathrm{a}\Gamma P\mathrm{f}_{0}\mathrm{r}\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{d}$$\mathrm{T}\mathrm{F}|19\mathrm{k}|\iota 11\mathrm{I}\mathfrak{n}\mathrm{b}04^{\mathrm{p}}$$[0, \infty)^{2}\uparrow \mathrm{t}\mathrm{q}\eta \mathrm{d}$$\mathrm{o}_{\mathrm{f}^{\mathrm{f}_{?}^{\mathrm{J}}/}’}’ A\mathrm{s}\mathrm{t}\circ\rho \mathrm{p}^{\backslash }\mathrm{t}\eta\delta^{\iota^{\backslash }1}l$”Eve$es\alpha\gamma\not\in u\mathrm{d}f^{-\ulcorner_{\wedge}}\mathrm{O}-\mathrm{s}^{\gamma}\mathrm{a}k\mathrm{b}_{\mathrm{t}^{\llcorner}}\mathrm{T}\mathrm{b}t\lambda \mathrm{A}Xo->^{-}\mathrm{b}$1. INTRODUCTION
The subject of the paper is a class of optimal stopping problems for a sequence ofwith full-information
but imperfect observation to guarantee the maximal probability ofachieving some objects. In 1975 Enns [1] first considered and solved the problem where theobjective is to choose the best $rv$ . Some generalization are posed and solved by Porositski [8].
In Sakaguchi [. some more general problems are discussed. In Section 2 we formulate andsolve the optimal stopping problem for finding the optimal threshold strategy that maximizes
the probability
one of the largest
It is shown
optimal threshold strategy is to stop at the earliest $rv$ that is larger than
, whereisdetermined by the equation$iidrv’ \mathrm{s}$$(\mathrm{F}\mathrm{I})$$\mathfrak{l}\}|3\mathrm{J}$$\mathrm{o}\mathrm{f}_{\mathrm{S}\mathrm{e}}1\mathrm{e}\mathrm{C}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{g}$$k$$rv’ \mathrm{s}.$$\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}.\mathrm{t}\mathrm{h}\mathrm{e}.\mathrm{a}\mathrm{s}\mathrm{y}\mathrm{m}\mathrm{P}^{\mathrm{t}\mathrm{o}}\mathrm{t}\mathrm{i}_{\mathrm{C}}\mathrm{a}\mathrm{u}-\perp \mathrm{y}$$e\mathfrak{n}$$j \mathrm{B}_{-,-}^{\frac{a_{-}^{j}}{j(j+1)!}=}\infty\frac{1}{k}$$a_{k}$.

In the subsequent two sections the optimal stopping problem for selecting the best $rv,$ i.e.
the case $k=1$ , solved in Section 2, is extended to optimal stopping games where two players
compete in selecting the best $rv$ . Two typical types of the optimal stopping games, where
each player’s objective and information condition are, by the notation used in Sakaguchi,: Selecting-sum, with FI$[ \int\sigma]$$1^{0})$$\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}/\mathrm{P}\mathrm{l}\mathrm{a}\mathrm{y}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{y}/\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}\mathrm{o}\mathrm{n}/\mathrm{Z}\mathrm{e}\mathrm{r}\mathrm{o}$and$2^{0})$: Selecting$\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}/\mathrm{E}\mathrm{a}\mathrm{r}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{t}\mathrm{o}_{\mathrm{P}}/\mathrm{E}\mathrm{a}\mathrm{c}\mathrm{h}/\mathrm{N}_{\mathrm{o}\mathrm{n}- \mathrm{z}\mathrm{e}}\mathrm{r}\mathrm{o}$respectively in Section 3 and 4.

-sum, with$\mathrm{F}\mathrm{I}$,72, which are sampled one byIn ) Players 1 and 2 observe a common $iid$ sequence of
one sequentially. Facing each , each player should accept the earliest $rv$ that exceeds his
decision level. If one player accepts a $rv$ and the other rejects it, the game is left thereafteras the other player’s one person game. If both players stop simultaneously at a $rv$ , thenone person
Player 1 accepts it, by his priority, and the game is left, thereafter as Player
game. A single player who accepts the best is the winner, getting reward of one unit fromthe opponent. Player 1(2) wants to maximize (minimize) the expected payoff to Player 1.
Related interesting results can be found in Neumann, Porositski&Szajowski [7], Porositski&. The no-information case priority games have been considered
Szajowski [9] andby Enns&Ferenstein [2], Sakaguchi [12] and Szajowski $[|7]$ .
. Players observe the private $iid$ sequenceIn ) there are two independent $iid$ sets ofof. Facing each $rv$ , each player should accept the earliest $rv$ that exceeds his own decision
is the winner. The
level. A player who is the first to stop at the best one in his set of, is a draw. Players’ aims
case, where both players stop at the best one in each set of
are to maximize his own the winning probability. An interesting related work is Mazalov [6],where players’ objective are slightly different from the one in the present paper. Other related
works, but in the null information case, were done by Presman&Sonin [10], Fushimi [3] andSakaguchi [I2].
For both of cases, ) and ), the game is transformed into a continuous game on thedomain $[0, \infty)2$ . Numerical solutions of them are given.
The considered problems are related to theinformation best choice problem consideredby Enns [1], Sakaguchi [ , Porositski [8] and the game version of the problem considered by$1^{0}$$\Gamma v’ \mathrm{s}$$\mathrm{r}v$$2’ \mathrm{s}$$\mathrm{r}v$$\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{u}\mathrm{m}\mathrm{d}\mathrm{a}\dot{\mathrm{r}}[5]$$2^{0}$$rv’ \mathrm{s}$$\mathrm{r}v’ \mathrm{s}$$rv’ \mathrm{s}$$\mathrm{r}v’ \mathrm{s}$$2^{0}$$1^{0}$$\mathrm{f}\mathrm{u}\mathrm{U}$$11\rfloor$

Neumann, Porositski and Szajowski [7],$\alpha\wedge \mathrm{A}\mathrm{s}n\mathrm{k}_{\mathit{0}}f^{\mathfrak{U}}tt,$$a_{)t}’ 1\mathit{5}e$2. BEST CHOICE PROBLEMS FOR CHOOSING ON$\mathrm{E}$a$\mathrm{r}i\mathrm{o}[\dot{\mathrm{I}}\mathit{3}]$OF THE.

$k-\mathrm{B}\mathrm{B}\mathrm{s}\mathrm{T}\mathrm{S}$obeying uniform distribution on the unit
be a sequence ofare sequentially observed one by one, but the observation is imperfectinterval $[0,1]$ . The
is greater than or less than a prescribed level
and we can only know whether the observed
is observed, we have to either accept or reject the observation. Our aim$z\in[0,1]$ . After. Neither recall nor uncertainty of selection isis to accept one of the bests among all
lessallowed. In this paper we restrict ourselves to the strategies which reject thegreater than . We call a win the event in which we accept a
and accept the earliest
to accept any $rv$ or accept $rv$
satisfying the objective. The event in which either we
dissatisfying his objective is a loss. We are looking for the decision level which gives the
maximum probability of win.
Let $P^{(k)}(z)$ be the probability of win for selecting one of the bests under the strategy
with the decision level . Then since the winning event by accepting an $rv$ on or before the$(n-k)$ -th is

Let $x_{1},x_{2},$$iidrv’ \mathrm{s}$$x_{\hslash}$$\ldots,$$X’ \mathrm{s}$$-\gamma v$$X_{t}$$\mathrm{r}v’ \mathrm{s}$$k$$rv’ \mathrm{s}$$\mathrm{r}v$

$z$

$z$

$\oint \mathrm{a}\mathrm{i}\mathrm{l}$$\mathrm{r}v$

$z$

$k$

$z$

$\bigcup_{m=1}^{k}\bigcup_{j}^{k}\mathfrak{n}-=1$

we have[$\ldots,xj-1\leq z<X_{j}\}\cap\{\mathrm{e}\mathrm{x}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{l}\mathrm{y}m-1rv$$\{\mathrm{x}_{1},.X2,$

thereafter $>X_{j}\}$ ],

than.

73

(2.1)

$P^{(\dot{k})}(z)= \sum_{m=1}P(k,m)(Z)k+Z\hslash-k(1-Z^{k})$

where
(2.2)

$P^{(k,m)}(Z)$$\sum_{1}^{\hslash-k}z-\int^{1}j1’(1-x)m-1j-m+1dXX^{\hslash-}$

$=j=$
$=$

$Z^{\hslash} \sum_{=rk}^{n-}1Z^{-}(r+1)\int_{z}^{1}(1-x)m-1rx-m+1d_{X}$is the probability that the accepted $rv$ on or before the $(ri-k)$ -th is the m-th best with
$1\leq m\leq k$..

.

We use the following abbreviations in Theorem 1. is the probability of win with the decision level;a.d.l. (a.p.w.) is the asymptotic decision level (probability of win), whenlevel is such that $z=e^{-a/n}$ , with $a>0$ and $narrow\infty$ .

$\mathrm{p}.\mathrm{w}$$z$$\mathrm{t}\mathrm{h}\dot{\mathrm{e}}$decision

Let us define functions(2.3)$H_{n}(z)$$=$$\sum_{m=1}^{n}\frac{z^{-m}-1}{m}$(2.4)$G_{n}(z)$$=$$\sum_{j=n}^{\infty}\frac{z^{j}}{j(j+1)!}$

Theorem 1. (i) For $k=1$ ($i.e$ .
and the optimal strategy is to choose,.

the best) the probability of win is $P^{(1)}(z).=z^{n}H_{n}(Z)$, which is determined by the equation$select’|n\forall d$$z_{0}$(2.5)$H_{n}(z)= \frac{1}{n}\sum_{:=1}^{\hslash}\frac{1}{z^{i}}$and the maximum of probability of win is$a.d.l$.

$a.p.w$.

(2.6)

where $a_{1}\cong 1.5029$ is a unique root in
(2.7)
$i.e$

$n^{-1_{\sum_{=0}^{n}z_{\dot{0}}}}.\cdot-1$. Therefore$= \exp(-\frac{a_{1}}{n})$$= \frac{(1-e^{-a_{1}})}{a_{1}}\cong 0.5174$$(1, \infty)$of the equation$\int_{0}^{a}\frac{e^{t}-1}{t}dt=\frac{e^{a}-1}{a}$,. $G_{1}(a)=1$ .
(ii) For $k=2$ ($i.e$ . selecting one of the two best) the probability of win is(2.8)$P^{(2)}(z)$$=$and the optimal strategy is to choose(2.9)

The maximum of $P^{(2)}(z)|S$$z^{n}[2H_{n}(z)-n( \frac{1}{z}-1)],$$z_{0}$$n\geq 2$,

which is determined by the equation.

$H_{n}(z)= \frac{1}{n}\sum_{:=1}^{n}\frac{1}{Z^{1}}$$+ \frac{n-1}{r_{l}^{\underline{r_{\mathrm{I}}’}}2}s\backslash -\frac{n}{2}\backslash \backslash .\cdot$$\mathrm{Z}$

,

74

.

(2.10)$P^{(2)}(z \mathrm{o})=\frac{2}{n}\sum_{0:=}^{\hslash-}Z_{0}1|$$-Z_{0}n-1$.

Moreove we have$r$$a.d.l$(2.11)$a.p.w$.

$= \exp(-\frac{a_{2}}{n})$.
$=^{\mathfrak{U}_{\frac{1-e^{-a_{2}})}{a\sqrt[2]{-}}}},\mathrm{t}_{\sim}\epsilon\simeq \mathrm{o}.726\tilde{\ }\backslash 5$

where $a_{2}\cong 2.0177$ is a unique root in(2.12)$i.e$$(a_{1}, \infty)$of the equation$\int_{0}^{a}\frac{e^{\ell}-1}{t}dt=\frac{e^{a}-1}{a}+\frac{a-1}{2}$,. $2G_{2}(a)=1$ .
(iii) For $k=3(i.e$ . selecting one of the three(2.13)$bes\mathrm{v}^{\mathrm{s}\parallel}the$probability of win is$P^{(3)}(z)=z \hslash 13H_{n}(z)-\frac{n(n-1)}{2}\frac{- z^{-2}-1}{2}+\frac{n(n-5)}{2}(\frac{1}{z}-1)],$and the optimal strategy is to choose(2.14)$z_{0}$$n\geq 3$,

which is determined by the equation. $+ \frac{(n-1)(n-2)}{6}\frac{1}{z^{2}}-\frac{(n-1)(n-5)}{6}\frac{1}{z}-\frac{n+1}{3}$.

$H_{n}(z)= \frac{1}{n}\sum_{=:1}^{n}\frac{1}{Z^{1}}$The maximum of $P^{(3)}(z)$ is(2.15)$P^{(3)}(z_{0})= \frac{3}{n}.\cdot\sum^{n-1}z=00+\frac{(n-1)(n-4)}{4}(z_{0}^{\hslash}-2-Z)0+n\frac{n-5}{2}Z^{n}0^{-}1$.

Moreover we have$a.d.l$(2.16)$a.p.w$.

.

$= \exp(-\frac{a_{3}}{n})$$= \frac{(1-e^{-a}3)}{a_{3}}-(2+3\frac{a_{3}}{2})e^{-a_{\theta}}\cong 0.8355$

where $a_{3}\cong 2.4934$ is a unique root in(2.17)$i.e$$(a_{2}, \infty)$of the equation,$\int_{0}^{a}\frac{e^{\mathrm{t}}-1}{t}dt=\frac{e^{a}-1}{a}-\frac{2}{3}+\frac{a}{2}+\frac{a^{2}}{12}$. $3G_{3}(a)=1$ .
3. A$\mathrm{Z}$ERO-SU$\mathrm{M}$BEST$\mathrm{C}$HOICE GAM$\mathrm{E}$

WH ERE$\mathrm{P}$LAYERS’$\mathrm{P}$RIO RITY IS GIVEN

A zero-sum game version of the discrete-time, full information and imperfect observation
best choice problem is considered in this section. Two Players 1 and 2 observe sequentially asequence offrom uniform distribution on $[0,1]$ , with each objective of choosing theas long as they arelargest $rv$. Let Player 1(2) chose a single level $z(w)$ , and he rejects
$\geq
z(w)$
that is. If the earliest $rv$ that is $\geq zw$
less than $z(w)$ and accepts the earliest
appears, Player 1 is given the priority to accept it and drops. out from the game thereafter.
The player accepting the largest $rv$ wins the game and he is paid a unit reward from the
opponent. Player 1(2) wants to maximize (minimize) the player I’s expected payoff.
Let $M(z, w)$ stand for the payoff to Player 1 when the levels and are chosen. Then for$niidrv’ \mathrm{s}$$rv’ \mathrm{s}$$rv’ \mathrm{s}$

$z$

$w$

75

$z<w$ we have

(3.1)

$M(z, w)$$=$$\sum_{s=1}^{n}zS-1\int_{z}^{1}x^{n-s}d_{X}$$- \sum_{s=1}^{n-1}zS-1\ell=s+\sum_{1}^{\hslash}w^{\ell}-\cdot-1\mathrm{t}(w-Z)\int_{w}^{1}y-\mathrm{C}dny+\int^{1}wdX\int_{x}^{1},y^{n-\ell}dy\}$$=z^{n}.

\cdot\sum^{n}\frac{z^{-i}-1}{i}+w\sum_{=}=1nj1\hslash\{^{\hslash-}\sum_{s=1}|\frac{z}{w})j’\}\{j-1(w^{-}j-1)-\frac{w}{z}\frac{w^{-j-1}-1}{j+1}\}$.

.

Similarly for $z>w$ we have$(3.2)-.$$M(z, w)$$=$$\sum_{s=1}^{n}w^{i}-1\int_{z}1n\int_{z}^{1}XX+\sum_{=s1}^{\hslash-1}w-1\sum_{+}tz^{t-}-1(sZ-w)x^{n\vee}d\mathrm{t}xn-s_{d}t=*1$.

$– \sum_{*=1}^{n}w-1\int_{w}^{z}\prime n-\prime dy\sum_{s=1}^{\hslash-}wy-’-1\sum_{=\ell S+1}^{n}w-s-1\int_{z}^{1}1\ell d_{X}\int_{x}\mathrm{I}y-\ell d\hslash y$.

$=w^{n} \sum_{1i=}^{n}i-1w^{-}.(1-2z^{::}+|w)$$+z^{n}( \frac{z}{w}-1)j=1\sum n\{.\sum_{=1}^{n-j}(\frac{w}{z})^{s}\}\frac{z^{-j}-1}{j}$$+w^{\hslash} \sum_{j=1}n(n-j)(\frac{z}{w})j+1\mathrm{t}\frac{z^{-j}-1}{j}-\frac{z^{-j-1}-1}{j+1}\}$

Note that (3.12 andunit square $0\leq z,$ $w\leq 1$ .
Define the function for$(3.\zeta)$.

coincide at $z=w$ and so the game is a continuous game on the$a\in(\mathrm{O}, \infty)$,$\Phi(a)\cong\int_{0}^{1}\frac{e^{a\ell}-1}{t}dt=\sum \mathrm{j}=1\infty\frac{a^{j}}{j\cdot j!}$.

$\Phi’(a)=a^{-1}(e^{a}-1)$
This function is strictly increasing and convex function
and $\Phi’’(a)=a^{\vee}\{21-(1-a)e^{a}\}=\sum_{k=2}^{\infty}\frac{a^{k-2}}{k(k-2)!}>0$ .
, with $b>0$ and $narrow\infty$ . Then (3.1) (3.2) becomes a
Now letcontinuous game on $[0, \infty)2$ , with the payoff function$\mathrm{w}\mathrm{i}^{-}\mathrm{t}\mathrm{h}\Phi(0)=0,$$z=e^{-\frac{\mathrm{Q}}{n}},$$w=e^{-\frac{b}{\mathfrak{n}}}$

-

$a,$

$\frac{b}{a-b}(e^{-b}-e^{-a})+e^{-a}\Phi(a-b)$(3.3)$M(a, b)=\{$,$+.e^{-a}( \Phi(a)+1.)+\frac{a}{b}-1$,

if $0<a<b$ ,Note that (3.3) is a continuous function on $[0, \infty)2$ with value
and we have
(3.4)

if $0<b<a$ ,$e^{-b}[(b-a)( \Phi(b)-\Phi(b--a))-\Phi(b)-a(\frac{1}{b}-1)]$$ae^{-a}$$M(a, 0)=e^{-a_{\Phi}}(a)=e^{-}0 \int_{0}^{a}\frac{e^{t}-1}{t}dt$

on the halfline $a=b>0$,$M(0, b)=-e^{-b}\Phi(b)$ ,both of which are reasonable facts since setting
one-person game.

$z$

or $w=1$ means that the game is actually

76$\mathrm{G}n)\mathfrak{p}_{4}\mathrm{t}r\mathrm{r}Z\mathit{5}X,$$0^{\cdot}n$TA$e\mathrm{b}a\grave{\iota}^{\sim}’ s\rho+(\partial_{\sim^{J}}^{2})\sim \mathrm{C}3,b)\mathrm{g}.\mathrm{t}(\mathrm{e};\#" k4w_{an}\nu \mathrm{i}g$with the payoff function (33), a saddle point
Theorem 2. For the zero sum game on, with $0<a_{0}<b_{0}$ , exists and the saddle value is(,$e^{-b_{0}}[(b_{00}-a)( \Phi(b_{0})-\Phi(b0-a0)-\Phi(a_{0})-a\mathrm{o}(b-1-0)1]+e-a0(\Phi(a_{0})+1)+\frac{a_{0}}{b_{0}}-1\cong 0.3233$$[0, \infty)^{2}$$\cdot$$a_{0},b_{0)}$by a simultaneous equation

where $(a_{0}, b_{0})\cong(1.57205, 2.99628)$ is determined$e^{-a}(\Phi(a)-\Phi(ar))+e-b(\Phi(b)-\Phi’(b))=e^{-}\Phi b(b-a)$$(\mathrm{E}\langle b)-\Phi(b-a))+(\Phi(b)-\Phi(\prime b))=(b-a)\{\Phi(b)-\Phi’(b)-\Phi(b-a)+\Phi’(b-a)\}$(3.7)$+a^{-1}(e-b1-b+b2)$ .

$\urcorner\tau_{\iota\not\subset}\uparrow \mathrm{k}Por\mathrm{P}n’\sigma \mathrm{A}_{0\Phi}T[]_{\mathrm{d}}\backslash \mathrm{t}\ _{\mathit{7}}\mathrm{o}e_{\Gamma}\mathfrak{l}\wp \mathrm{b}p_{\mathrm{u}\grave{s}}*_{C(}\cdot\sigma\iota \mathrm{r}’-’\ \vee A\mathrm{z}_{o^{=}}2^{-}‘\dagger.\mathit{0}/\eta l_{1\mathscr{S}}\backslash \iota_{P\prime 7}t1a.ntl_{\mathrm{u}}\delta\prime p\mathit{0}nc_{/_{1}\mathrm{f}}-$$|\mathrm{h}-$tk$\mathrm{r}pt\mathrm{A}_{2}cf_{13}\mathrm{P}\ _{J^{l^{\rho}}}\mathrm{I}_{\mathit{5}}^{7}ad\nu aj_{1}\Psi \mathit{0}\nu er$$l\mathrm{O}\mathrm{P}^{+_{1}\iota\tau\prime d}r\ _{f\text{ノ^{}\phi}}\mathrm{A}\mathfrak{n}d1\mathfrak{u}td\ell \mathrm{t}\ \cup\iota^{\prime u}|.;- \mathrm{r}\mathrm{o}\mathrm{e}’\sigma_{\iota}\mathrm{e},$ih$\mathrm{k}_{\mathrm{t}\}}^{\backslash }0\uparrow_{\mathrm{Y}}\iota_{)}\mathrm{h}\{\mathfrak{n}^{\lfloor}-\mathrm{A}_{\mathfrak{U}}\prime \mathrm{t}_{0}\mathrm{M}\mathrm{k}^{r}\downarrow\psi\backslash e_{)}-\mathrm{P}^{r\mathrm{i}\mathit{0}\Gamma_{1}^{\backslash }}\mathrm{t}\gamma$

4. A NON-ZERO$\mathrm{S}\mathrm{U}\mathrm{M}$

BBST.CHOICE GAM$\mathrm{E}$$d_{\Lambda}1y\gamma^{\mathrm{M}}@\alpha me$,

WH ERE WIN NING REQUIRES EARLIER STO$\mathrm{P}$A non-zero-sum game version of the discrete time, full information and imperfect observation best choice problem is considered in this. We first state the problem as follows:$\sec\check{\mathrm{t}}\mathrm{i}\mathrm{o}\mathrm{n}$(1) There are two Players 1 and 2, and a sequence of $niid$ bivariate
from’independent uniform distribution on $[0,1]^{2}$ . Player 1(2) observes
sequentialy
one by one.
(2) Let Player 1(2) choose a single le $\gamma elz(w)$ . He rejects
as long as
are lessthan $z(w)$ and he accepts the earliest $rv$ that is, where and are
the stopping times of the players.
this fact and(3) If one of the players stops (accepts), the other player is not informed ofplaying. We call a “win” for each player the event in which he gets to be the. If the two players stop simultaneously
first to stop at the best one in his set of, both of them are the winners.
at the best one in each player’s set ofby which the(4) The aim of each player in the game is to determine his decision levelprobability that he becomes a si ngle winn er is maximized.
1(2) when the levels
Let $M_{1}(z, w)(M_{2}(z, w))$ stand for the probability of winning for Player
and are chosen. Then we have$rv’ \mathrm{s}\{(X.\cdot, \mathrm{Y}_{i})\}_{=1}^{n}.\cdot$$X_{\ell}(\mathrm{Y}_{t})_{\mathrm{S}}$$X_{2}(\mathrm{Y}_{\mathrm{t}})’ \mathrm{S}$$\mathrm{t}1_{1}\mathrm{e}\mathrm{y}$$X_{\sigma}\geq z(\mathrm{Y}_{\tau}\geq w)$$\sigma$$\tau$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{u}\mathrm{e}\dot{\mathrm{S}}$$rv’ \mathrm{s}$$rv’ \mathrm{s}$

$z$

$w$

(4.1)

$M_{1}(z, w)= \sum_{s=1}^{\hslash}Z-1\int_{z}Sx^{n-s}1d_{X}\{w^{s}+\sum^{S-}w\int_{w}2=11\ell-11(1-y^{n-})tdy\}$.

$=(zw)^{n} \sum_{\mathrm{j}=1}^{n}\frac{z^{-\mathrm{j}}-1}{j}\{w^{-\hslash}-w^{-}+w^{-j+}-\sum_{1}^{n}\frac{w^{-:}-1}{i}j1:=j+\}$is equal to $M_{1}(z, w)$ with and interchanged.
By letting $z=e^{-a/n},$ $w=e^{-b/n}$ , with $b>0$ and $narrow\infty$ , we obtain acontinuous game on $[0, \infty)2$ with payoff functions$M_{2}(z, w)$

$z$

.

$w$

$a,$

$\mathrm{n}\mathrm{o}11^{-}$

zero-sum77$M_{1}(a, b)=e^{-a}[ \Phi(a)-be^{-}\iota\int_{0}^{1}\Phi(at)\Phi’(bt)dt]$,$M_{2}(a,b)=e^{-b}[ \Phi(b)-ae-a\int_{0}^{1}\Phi^{J}(at)\Phi(bt)dt]$

,

(4.2)

We note that (4.2) gives(4.3)$M_{1}(a, 0)=e^{-a}\Phi(a),$$M_{1}(0, b)=0$$M_{2}(0, b)=e^{-b}\Phi(b),$$M_{2}(a, 0)=0$

and
(4.4)

$M_{1}(a, a)=M_{2}(a, a)=e^{-a} \Phi(a)-\frac{1}{2}(e^{-\Phi}\Phi(a))2=\frac{1}{2}[1-(1-e^{-a}\Phi(a))^{2}]$,on the halfline $a=b\geq 0$ . Again setting $z=1(w=1)$ means that Player 1(2) does not play
any role in the game. Furthermore we find that
(4.5)

$M_{1}(a, b)+M_{2}(a, b)=1-(1-e^{-a}\Phi(a))(1-e-b\Phi(b))$ ,by an evident identity.

$a \int_{0}^{1}\Phi’(at)\Phi(\mathrm{b}t)dt+b\int_{0^{-}}^{1}\Phi’(bt)\Phi(at)dt=\Phi(a)\Phi(b)$Now we find an equilibriu.m for a pair of payoff functions (4.2).

Theorem 3. For the non-zefo-sum gamewith the payoff functions (4.2) the equilibrium point exists and it is $(a, b)$ with $a=b=a_{0}\cong 1.6065$ whereis defined $by_{-}\varphi(c)=0$ .
The common equilibrium value is$\dot{o}n[0, \infty)2$$a_{0}$$e^{-a_{\mathrm{O}}} \Phi(a_{0)-}\frac{1}{2}(e^{-a_{0}}\Phi(a\mathrm{o}))^{2}\cong 0.3830$.

Therefore the probability of draw of the game is 0.2339.
$\emptyset^{\mathrm{r})}\mathrm{A}$$\psi(c)$

$=$

$=$

$e^{a} \frac{\partial M_{1}}{\partial a}|_{a=}b=\mathrm{c}$$e^{-t}[ \frac{1}{2}(\Phi(C))2-\frac{1}{c}(\Phi(2c)-2\Phi(C))]-\Phi(c)+\Phi(C)’$,78

REFERENCES
1. E.G. Enns, Selecting the maximum of a sequence with imperfect information, J. Amer. Statist.
Assoc. 70 (1975), 640–643.
. Ferenstein, The horse game, J. Oper. Res. Soc. Jap. 28 (1985), 51–62.
2. E.G. Enns and. $24$ (1981).
3. M. Fushimi, The secretary problem in a competitive situation, J. Oper. Res. Soc.
$\mathrm{E}.\mathrm{Z}$$\mathrm{J}\mathrm{a}\mathrm{p}$350-358.
7$\Lambda$$|\mathrm{b}$$\mathfrak{l}7$$1 \supset\bigcap_{-*}.\uparrow \mathrm{h}_{\mathrm{a}},$$\mathrm{b}.$},$\eta’ \mathrm{l}\mathrm{v}\mathrm{h}\mathrm{f}_{\cap\circ*}\rho 1|_{\partial}\gamma$

M. bamuels, An$R\rho \mathrm{r}$” $nniZ|nl$$exp\{\iota c\iota lj\mathit{0}fmulaJ^{O}f\mathrm{I}ne$the maximum of a sequence. J. Amer. Statist. Assoc.

timrung $opt’ ma\iota$ success probabtlrty $rn$ the full rnformation

best choice problem, Mimeograph series, Purdue Univ. Stat. Dept., 1980.
K. Szajowski, Double stopping by two decision makers, Adv. Appl. Probab. 25 (1993), 438–452.

OF

COM-

RESEARCH INSTITUTE FOR INFORMATION SYSTEMS, NAGOYA UNIVERSITYAICHI 470-01, JAPANNISSIIIN,
MERCE AND BUSINESS ADMINISTRATION,$\mathrm{r}$$\mathrm{K}\mathrm{o}\mathrm{M}\mathrm{E}\mathrm{N}\mathrm{O}\mathrm{K}\mathrm{I},$INSTITUTE OF MATHEMATICS, TECHNICAL UNIVERSITY OF WROCLAW,WYSPIAN’SKIEGO 27, PL-50-37o WROCLAW, POLAND-mail: szajow@im.pwr.wroc.pl

$**$

$E$

$\mathrm{w}\mathrm{v}\mathrm{B}\mathrm{R}\mathrm{Z}\mathrm{E}\dot{\mathrm{z}}\mathrm{E}$