数理解析研究所講究録
1068 巻 1998 年 75-86

75Multiple Choice Problems Related
to the Duration of the Secretary Problem
愛知大学経営学部 玉置光司 (Mitsushi Tam 止)The University of Adelaide, Charles. Pearce
Technical University of Wroclaw, Krzysztof Szajowski$\mathrm{E}.\mathrm{M}$

Abstract
A version of the multiple choice secretary problem called the
choice duration
problem, in which the objective is to maximize the time of possession of relatively best
objects, is treated. For the choice duration problem with a known number of objects, there
exists a sequence of critical numbers
such that, whenever there remain
choices yet to be made, then the optimal strategy immediately selects a relatively best object
if it appears after or on time
. A simple recursive formula for calculating thecritical numbers when the number of objects tends to infinity will be given. It can be shownthat the multiple choice duration problem with a known number of objects is related to themultiple choice (best-choice) secretary problem with an unknown number of objects having auniform prior on the actual number of objects. Extensions to models involving an acquisition
cost or a replacement cost are made.
’$\mathrm{m}\mathrm{u}\ddot{1}\mathrm{t}\mathrm{i}_{\mathrm{P}^{\mathrm{l}\mathrm{e}}}$$\mathrm{m}$$\mathrm{k}$$(\mathrm{s}_{1,2,\ldots,\mathrm{m}}\mathrm{S}\mathrm{s})$$1\leq \mathrm{k}\leq \mathrm{m}$$\mathrm{s}_{\mathrm{k}},$1. Introduction and summary
Though Ferguson, Hardwick and$\mathrm{T}\mathrm{a}\mathrm{m}\mathrm{a}\mathrm{k}\mathrm{i}[2]$considered the various duration moxlels

extensively, they confined themselves to the study of the one choice duration problems. In
this paper, we attempt to extend the one choice problems to the multiple choice problems.
For the$\mathrm{m}$choice duration problem, we are allowed to choose at most$\mathrm{m}$objects sequentially,

and receive each time a unit payoff as long as either of the chosen objects remains a

simplicity we refer to a relatively best object as a candidate). Obviously only
candidates can be chosen, the objective being to maximize the expected payoff.
candidate($\mathrm{r}\mathrm{o}\mathrm{r}$It can be shown in Section 2 that, for thesequence of integer-valued critical numbers$\mathrm{k}$$\mathrm{m}$choice duration problem, there exists a$(\mathrm{s}_{1},\mathrm{s}_{2,\ldots,\mathrm{m}}\mathrm{s})$such that, whenever there remain

choices yet to be made, then the optimal strategy immediately selects a candidate if itappears after or on time
converges to some definite value$1\leq \mathrm{k}\leq \mathrm{m}$$\mathrm{s}_{\mathrm{k}},$$\mathrm{s}_{1}^{*},$$\mathrm{S}_{2},..\mathrm{s}_{\mathrm{k}-\iota}*.,*$. It is also shown that is non-increasing in .
in terms ofand a recursive formula for calculating$\mathrm{k}$$\mathrm{s}_{\mathrm{k}}/\mathrm{n}$$\mathrm{s}_{\mathrm{k}}$$\mathrm{s}_{\mathrm{k}}^{*}$$\mathrm{s}_{\mathrm{k}}^{*}$

will be given by(1)$\mathrm{s}_{\mathrm{k}}^{*}=\mathrm{e}\mathrm{X}6-\}1+\sqrt{1- 2\sum\frac{[(\mathrm{k}- \mathrm{i}+2)+(\mathrm{k}- \mathrm{i}+1)\log \mathrm{s}^{*}\mathrm{i}]}{(\mathrm{k}- \mathrm{i}+2)!}(_{\mathrm{l}\mathrm{s}_{\mathrm{i}}^{*}}\mathrm{o}\mathrm{g})\mathrm{k}1\mathrm{k}\mathrm{i}+1}\mathrm{i}=1\{]$

It is also shown that, as$\mathrm{n}arrow\infty$, (the maximum expected$\mathrm{p}\mathrm{a}\mathrm{y}\mathrm{o}\mathrm{f}\mathrm{f}$)$/\mathrm{n}$converges$\mathrm{t}\mathrm{o}-\sum \mathrm{m}\mathrm{s}^{*}\mathrm{k}\log \mathrm{s}^{*}\mathrm{k}$The best-choice secretary problem is concemed with maximizing the$\mathrm{p}\mathrm{r}^{\mathrm{k}=}\mathrm{o}\mathrm{b}^{1}\mathrm{a}\mathrm{b}\mathrm{i}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{y}$.

ofchoosing the best object from among all. We show that the multiple choice duration problem

76

objects is equivalent to the multiple choice best-choice secretary.
problem with an unknown number of objects having a uniform distributlion onwith a known number of$\mathrm{n}$$\{1,2,\ldots,\mathrm{n}\}$In Sections 3 and 4, the multiple choice duration problem treated in Section 2 isgeneralized by introducing cost. In Section 3, we consider a problem in which a constantacquisition cost is incurred each time an object is chosen. Thus far we have assumed that theobjects, once chosen, are possessed until the process terminates. We consider in Section 4 a
problem which allows us to possess only one object at a time. A constant replacement cost isincurred each time we replace a previously chosen object with a new one. The objectives
are, in Sections 3 and 4, to maximize the expected net payoff. It can be shown that, under anappropriate cost condition, the optimal strategies have the same structure as that for the
problem involving no cost.

2. Multiple choice duration problem
We assume that all that can be observed are the relative ranks of the objects as they arepresented. Thus if Xi denotes the relative rank of the th object among those observed so far), the sequentially observed random variables are( th object is a candidate if. It is well known, under the assumption that the objects are put in random$\mathrm{i}$$\mathrm{X}_{\mathrm{i}}=1$$\mathrm{i}$$\mathrm{X}_{1},\mathrm{X}_{2,\ldots,\mathrm{n}}\mathrm{X}$order with all(a) the(b)$\mathrm{X}_{\mathrm{i}}$permutations equally likely, thatare independent random variables and$\mathrm{n}!$$\mathrm{P}\{\mathrm{X}_{\mathrm{i}^{=}}\mathrm{j}\}=1/\mathrm{i}$, for$1\leq \mathrm{j}\leq \mathrm{i},$$1\leq \mathrm{i}\leq \mathrm{n}$.

2.1 The finite horizon problem
choice duration problem as a Markovian decision process model.
We consider the
Since serious decision of either selection or rejection takes place only when a candidate
if the th object is a
, lsisn,appears, we describe the state of the process as$\mathrm{m}$$(\mathrm{i},\mathrm{k})$$(\mathrm{i},\mathrm{k})$,$\mathrm{W}_{\mathrm{i}}^{(\mathrm{k})}$$\mathrm{i}$more choices to be made.
be the expected additional payoff under an optimal strategy starting from statecandidate and there remainLet$1\leq \mathrm{k}\leq \mathrm{m}$$\mathrm{k}$be the expected additional payoff when weth object and then continues search in an optimal manner. Then thelsisn, lsksm, and also let

select(reject) the$\mathrm{i}$principle of optimality yields, for$_{i}\mathrm{k})1_{/}|$$\mathrm{W}_{\dot{\mathrm{t}}}^{(\mathrm{k})}=\max\{\mathrm{U}_{\mathrm{i}}^{(\mathrm{k})(}.,$$\mathrm{U}_{\mathrm{i}\mathrm{Y}\mathrm{i}}^{(\mathrm{k}})(\mathrm{k})$$1\leq \mathrm{k}\leq \mathrm{m}$$1\leq \mathrm{i}\leq \mathrm{n}$

’

,

(2)

where
$\mathrm{U}_{\mathrm{i}}^{(\mathrm{k})}=\frac{1}{\mathrm{n}}\mathrm{i}=\sum\frac{\mathrm{i}}{\mathrm{j}}+\mathrm{i}\mathrm{n}\mathrm{i}=\mathrm{i}\sum\frac{\mathrm{i}}{\mathrm{j}(|- 1)}\mathrm{W}_{\mathrm{i}}^{(}\mathrm{n}+1\mathrm{k}- 1)$

and

(3)

77
(4)

$\mathrm{v}_{\mathrm{i}}^{(\mathrm{k})}=.\sum_{+\mathrm{i}=\mathrm{i}1}\mathrm{n}\frac{\mathrm{i}}{\mathrm{j}(\underline{\mathrm{j}}- 1)}\mathrm{W}_{\mathrm{j}}^{(\mathrm{k})}$condition
Equations (2) $-(4)$ , combined with therecursively to yield the optimal strategy and the optimal value$\mathrm{b}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}\mathrm{a}13^{\gamma}$, can$\mathrm{w}_{i}^{(0)_{=}}0,1\leq \mathrm{i}\leq \mathrm{n}$$\mathrm{W}_{1}^{(\mathrm{m})}$be solved.

Theorem 2.1

For thenumbers$\mathrm{m}$choice duration problem, there exists a sequence of integer-valued criticalsuch that, whenever there remain choices yet to be made, i.e., we$\mathrm{k}$$(\mathrm{s}_{1},\mathrm{S}_{2},\ldots,\mathrm{s}_{\mathrm{m}})$objects, then the optimal strategy immediately selects a candidate
if it appears after or on time . Moreover, is non-increasing in and determined byhave already chosen m-$\mathrm{k}$$\mathrm{k}$$\mathrm{s}_{\mathrm{k}}$$\mathrm{s}_{\mathrm{k}}$$\mathrm{s}_{\mathrm{k}}=\min\{\mathrm{i}:\mathrm{G}^{(\mathrm{k})}\mathrm{i}\geq 0_{l}^{1}$

where$\mathrm{G}_{1}^{(\mathrm{k})}.,$$1\leq \mathrm{i}\leq \mathrm{n},$$1\leq \mathrm{k}\leq \mathrm{m}$(5),, is defined recursively as(6)$\mathrm{k}\geq 2$$\mathrm{G}_{\mathrm{i}}=\mathrm{G}+(\mathrm{k})(\mathrm{i}1)\mathrm{i}=\max(+\sum_{\mathrm{i}1,\mathrm{s}\mathrm{k}-1\rangle}^{\mathrm{n}}\frac{1}{\mathrm{j}- 1}\mathrm{G}^{(\mathrm{k}}\mathrm{i}- 1)$starting with.

(7)$\mathrm{G}_{\mathrm{i}}^{(1)}=\sum_{=\mathrm{J}\mathrm{i}}\mathrm{n}\frac{1}{\mathrm{j}}-\sum_{1\mathrm{j}=\mathrm{i}+}\frac{1}{\mathrm{j}- 1}\sum_{\mathrm{t}=_{\mathrm{i}}}^{\mathrm{n}}\frac{1}{\mathrm{t}}\mathrm{n}$Let$\mathrm{m}\geq 1$$\mathrm{q}_{\mathrm{m}},$, be the expected payoff for the$\mathrm{m}$choice problem, i.e.,$\mathrm{q}_{\mathrm{m}}\equiv \mathrm{W}^{(\mathrm{m})}\dagger$. Then,from the property of the optimal strategy, we have$\mathrm{q}_{\mathrm{m}}=\overline{\mathrm{V}}_{\mathrm{s}_{\mathrm{m}}-}1((\mathrm{m})\frac{\mathrm{s}_{\mathrm{m}^{-}}1}{\mathrm{n}}=)\sum\frac{1}{\mathrm{j}- 1}\sum_{\mathrm{t}=\mathrm{i}}\frac{1}{\mathrm{t}}+\sum \mathrm{j}=\mathrm{n}\mathrm{s}_{\mathrm{m}}\mathrm{n}\mathrm{i}=\mathrm{s}_{\mathrm{m}}\mathrm{n}\frac{\mathrm{s}_{\mathrm{m}^{-}}1}{\mathrm{j}(|- 1)}_{\mathrm{j}}(\mathrm{m}- 1)$

where

)

$\mathrm{V}_{i}^{(\mathrm{m}- 1},\mathrm{m}$$\geq 2$,, are calculated recursively as$\mathrm{v}_{\mathrm{i}}^{(\mathrm{m}1}=-)\int \mathrm{q}_{\mathrm{m}- 1}$,$\mathrm{i}<\mathrm{s}_{\mathrm{m}- 1^{-}}1\backslash$$|$$\mathrm{i}\geq \mathrm{s}_{\mathrm{m}- 1^{-}}1$$\int$$\frac{\mathrm{i}}{\mathrm{n}}\sum_{+\mathrm{i}=\mathrm{i}1}^{\mathrm{n}}\frac{1}{\mathrm{j}- 1}\sum\frac{1}{\mathrm{t}}+\sum_{\mathrm{j}\mathrm{t}=_{\mathrm{i}}=\mathrm{i}+1}^{\mathrm{n}}\frac{\mathrm{i}}{\mathrm{j}(_{-|- 1)}}\mathrm{n}\mathrm{V}_{\mathrm{j}}^{(-}\mathrm{m}2),$with the interpretation that.

$\mathrm{V}_{\mathrm{i}}^{(0)}\equiv 0$

2.2 Asymptotic results
It is of interest to investigate the asymptotic behaviors of$1\leq \mathrm{k}\leq \mathrm{m}$$\mathrm{s}_{\mathrm{k}},$, andas tends to$\mathrm{n}$$\mathrm{q}_{\mathrm{m}}$78
infinity. To do this, we here employ an intuitive approach of approximating the infinite sum
by the corresponding integral. Whenis a Riemann approximation to the integral$\mathrm{m}=1,$$\mathrm{G}_{\mathrm{i}}^{(1)}$.

(8)$\mathrm{G}^{(1)}(_{\mathrm{X})}=\int_{\mathrm{x}}^{1}\frac{\mathrm{d}\mathrm{y}}{\mathrm{y}}-\int_{\mathrm{x}}1\frac{\mathrm{d}\mathrm{y}}{\mathrm{y}}\int_{\mathrm{y}}1\underline{\mathrm{d}}\mathrm{z}\mathrm{Z}=-\frac{(2+\log \mathrm{x})\log \mathrm{x}}{2}$Thus, from (5),is obtained as a unique root$\mathrm{s}_{1}^{*}=\lim_{\mathrm{n}arrow\infty}\frac{\mathrm{s}_{1}}{\mathrm{n}}=\mathrm{e}^{-2}$.
Define in general$\mathrm{x}\in(\mathrm{O}, 1)$of the equation$\mathrm{G}^{(1)}(_{\mathrm{X}})=0$$\mathrm{s}_{\mathrm{k}}^{*}=\lim_{\mathrm{n}arrow\infty}\frac{\mathrm{s}_{\mathrm{k}}}{\mathrm{n}}$successively as a unique root$\mathrm{G}^{(\mathrm{k})}(\mathrm{X})=0$

if$\mathrm{G}^{(\mathrm{k})}(\mathrm{x}),$$0<\mathrm{x}<1$. Then, in a similar way, we can obtain$\mathrm{x}\in(\mathrm{O}, \mathrm{S}_{\mathrm{k}- 1})*$as$\mathrm{n}arrow\infty$for$\mathrm{k}\geq 2$of the equation,(9), are defined recursively as$\mathrm{G}^{(\mathrm{k})}(_{\mathrm{X})()+}=\mathrm{G}(1)\mathrm{x}\int_{\max(\mathrm{x}_{1_{- 1})}}^{1},*\frac{1}{\mathrm{y}}\mathrm{G}^{()}\mathrm{k}- 1(\mathrm{y})$starting with$\mathrm{s}_{\mathrm{k}}^{*}$$\mathrm{G}^{(1)}(\mathrm{x})$(note thatdy

is a Riemann approximation to$\mathrm{G}_{\mathrm{i}}^{(\mathrm{k})}$(10)$\mathrm{k}\geq 2$$\mathrm{G}^{(\mathrm{k})}(\mathrm{x})$if one lets$\mathrm{i}/\mathrm{n}arrow \mathrm{x}$).

From (9) and (10),$\mathrm{s}_{\mathrm{k}}^{*}$

is a root of the equation$\mathrm{G}^{(1)}(\mathrm{x})=-\int_{\star^{*}-1}^{1}\frac{1}{\mathrm{y}}\mathrm{G}^{(\mathrm{k}- 1})(\mathrm{y})\mathrm{d}\mathrm{y}$,or equivalently, from (8).

$\mathrm{s}_{\mathrm{k}}^{*}=\exp\}-\backslash \prime 1+\sqrt{1+2\int^{1}\frac{\mathrm{G}^{(\mathrm{k}1)}(\mathrm{y})}{\mathrm{y}}\mathrm{d}\mathrm{y}}\mathrm{t}- 1*1\mathrm{I}$

Lemma 2.1
Define, for a positive integer$\mathrm{k}\geq 1$,,$\mathrm{A}_{\mathrm{k},\mathrm{i}}=\int_{*- \mathrm{i}}^{1}*\mathrm{G}\frac{(\log \mathrm{x})^{\mathrm{i}}}{\mathrm{x}}(\mathrm{k}- \mathrm{i})(\mathrm{x})\mathrm{d}\mathrm{X}$$\mathrm{a}_{\mathrm{k},\mathrm{i}}=\int_{\mathrm{k}_{- \mathrm{i}}^{*}}^{1}\frac{(\log \mathrm{x})^{\mathrm{i}}}{\mathrm{x}}\mathrm{G}^{(1}\rangle(\mathrm{x})\mathrm{d}_{\mathrm{X}}$,$0\leq \mathrm{i}\leq \mathrm{k}- 1$$0\leq \mathrm{i}\leq \mathrm{k}- 1$

.

(11)

79
Then

$\mathrm{A}_{\mathrm{k},\mathrm{i}}$satisfies the following recursive relation$\mathrm{A}_{\mathrm{k},\mathrm{i}}=\mathrm{a}_{\mathrm{k},\mathrm{i}}+|\frac{1}{\mathrm{i}+1})[\mathrm{A}_{\mathrm{k},\mathrm{i}}+1-(\log \mathrm{s}_{\mathrm{k}-}^{*}\mathrm{i})\mathrm{i}+1]\mathrm{A}_{\mathrm{k}}-\mathrm{i}-1,0$

with the interpretation that
For simplicity, let$\mathrm{A}_{\mathrm{k},0}$$\mathrm{A}_{\mathrm{k},\mathrm{k}}=0,$$\mathrm{k}\geq 0$

(12)

.

be denoted by

gives the following recursive relation of,$\mathrm{A}_{\mathrm{k}}$$\mathrm{A}_{\mathrm{k}}$. Then the repeated use of (12) immediately.

Lemma 2.2
Ak, kzl satisfies the following recursive relation$\mathrm{A}_{\mathrm{k}^{=}}\sum_{\mathrm{i}=\iota}^{\mathrm{k}}[\frac{\mathrm{a}_{\mathrm{k},\mathrm{k}- \mathrm{i}}}{(\mathrm{k}- \mathrm{i})!}-\frac{(\log \mathrm{s}_{\mathrm{i}}^{*})\mathrm{k}- \mathrm{i}+1}{(\mathrm{k}- \mathrm{i}+1)!}\mathrm{A}_{\mathrm{i}- 1}]$Let$\mathrm{N}_{\mathrm{k}},$$\mathrm{k}\geq 1$

be defined as.

$\mathrm{N}_{\mathrm{k}}=-(1+\sqrt{1+2\mathrm{A}_{\mathrm{k}1^{1}}})$

Then, from (11)$\mathrm{s}_{\mathrm{k}}^{*}=\mathrm{e}\mathrm{x}\mathrm{r}\mathrm{N}_{\mathrm{k}})$and we have the following lemma.

Lemma 2.3$\mathrm{N}_{\mathrm{k}},$$\mathrm{k}\geq 1$

satisfies the following recursive relation$\mathrm{N}_{\mathrm{k}}=-[1+\sqrt{1- 2\sum^{1}\frac{\mathrm{t}(\mathrm{k}- \mathrm{i}+2)+(\mathrm{k}-\mathrm{i}+1)\mathrm{N}_{\mathrm{i}}/(\backslash \mathrm{N}_{\mathrm{i}})\mathrm{k}\mathrm{i}+1}{(\mathrm{k}-\mathrm{i}+2)!}\mathrm{k}}]\mathrm{i}=1$(13)

Recursive formula (1) is an immediate consequence from (13). From (1) we successively
have$\mathrm{s}_{1}^{*}=\mathrm{e}\mathrm{x}\mu-2_{/}^{\mathrm{t}}\approx 0.1353$$\mathrm{s}_{2}^{*}=\mathrm{e}\mathrm{x}_{\mathrm{I}}\{-(1+\sqrt{\frac{7}{3}})\}\approx 0.0799$

80$\mathrm{s}_{3^{=}}^{*}\mathrm{e}\mathrm{x}\oint-(1+\frac{1}{\sim 3}\sqrt{15+14\sqrt{\frac{7}{3}}})\{\approx 0.0493$.
Conceming the expected payoff, we have the following lemma.

See Table 1 for$\mathrm{s}_{5}^{*}$

and$\mathrm{s}_{10}^{*}(\mathrm{c}=0)$

Lemma 2.4
$1x \mathrm{t}\mathrm{q}_{\mathrm{m}}^{*}=\lim_{\mathrm{n}arrow\infty}\mathrm{q}_{\mathrm{m}}$for$\mathrm{m}\geq 1$. Then$\mathrm{q}_{\mathrm{m}}^{*}=-\sum_{\mathrm{k}=1}^{\mathrm{m}}\mathrm{s}^{*}\mathrm{k}\log \mathrm{s}^{*}\mathrm{k}$Numerical values of the first four
. See Table 2 for and$\mathrm{q}_{4}^{*}=0.7287$$\mathrm{q}_{-5}^{*}$

are$\mathrm{q}_{\mathrm{m}}^{*}$$\mathrm{q}_{10}^{*}(\mathrm{c}=0)$.

$\mathrm{q}_{1}^{*}=0.2707,$$\mathrm{q}_{2^{=0.4}}^{*}725,$$\mathrm{q}_{3}^{*}=0.6208$,.

2.3 Multiple choice secretary problem with a random number of objects
lt can be shown that the multiple choice duration problem with a known number ofobjects is equivalent to the multiple choice (best-choice) secretary problem with an unknown
in the sense that the optimal
number of objects having a uniform distribution on$\mathrm{n}$$\{1,2,\ldots,\mathrm{n}\}$strategies and the expected payoffs are the same.
3. Multiple choice duration problem with an acquisition cost
In this section, the multiple choice duration problem is generalized by imposing a constanteach time an object is chosen.
acquisition cost$\mathrm{c}(>0)$

3.1 The finite horizon problem
the state of the
choice duration problem with an acquisition cost .
We treat the
be defined similarly as theandprocess be defined as in Section 2, and let also,
expected additional net payoff under an optimal strategy starting from state$\mathrm{c}$$1x\mathrm{t}$$\mathrm{m}$$\mathrm{U}_{\mathrm{i}}\mathrm{k}(\mathrm{k})$$\mathrm{W}_{i}^{()},$$\mathrm{V}_{\mathrm{i}}^{(\mathrm{k})}$$(\mathrm{i},\mathrm{k}),$$1\leq \mathrm{k}\leq \mathrm{m}$. Then the optimality equations (2) $-(4)$ still hold if (3) is replaced by$\mathrm{U}_{\mathrm{i}}^{(\mathrm{k})}=- \mathrm{c}+\frac{1}{\mathrm{n}}\sum_{\mathrm{i}=\mathrm{i}}^{\mathrm{n}}\frac{\mathrm{i}}{\mathrm{j}}+\mathrm{i}=\mathrm{i}\sum_{+1}\mathrm{n}\frac{\mathrm{i}}{\mathrm{j}(|-1)}\mathrm{W}_{\mathrm{i}}^{(}\mathrm{k}- 1)$

It is easy to see that$\mathrm{U}_{\mathrm{i}}^{(1)}=- \mathrm{C}+\frac{1}{\mathrm{n}}\sum_{\mathrm{i}=\mathrm{i}}\mathrm{n}\mathrm{j}\mathrm{i}$is unimodal with mode at the value$\mathrm{K}(\mathrm{n})=\min\{\mathrm{i}$:$\sum_{\mathrm{i}=\mathrm{i}+1}\frac{1}{\mathrm{j}}\mathrm{n}\leq 1\backslash \int$,$1\leq \mathrm{k}\leq \mathrm{m}$.

$1\leq \mathrm{i}\leq \mathrm{n}$81Then, if$\mathrm{c}$is large so as to make$\mathrm{U}_{\mathrm{K}(\mathrm{n})}^{(1)}<0$

appears. Thus we consider only the case, we do not choose a candidate no matter when it, namely,$\mathrm{U}_{\mathrm{K}(\mathrm{n})}^{(1)}\geq 0$

.

(14)

$\mathrm{C}\leq\frac{\mathrm{K}(\mathrm{n})}{\mathrm{n}}\sum_{)\mathrm{i}=\mathrm{K}(\mathrm{n}}\frac{1}{\mathrm{j}}\mathrm{n}$Let. Then it goes without saying that the optimal strategy selects no, and hence our attention.. can be concentrated on the candidates that.

$\mathrm{b}(\mathrm{n})=\max_{\mathfrak{l}\dot{\iota}}^{l_{\mathrm{i}:\mathrm{U}^{(}})}1\geq 0_{1}^{\backslash }$object after time$\mathrm{b}(\mathrm{n})$appear no later than$\mathrm{b}(\mathrm{n})$Theorem 3.1

For the$\mathrm{m}$choice duration problem with the cost condition (14), there exists a sequence ofinteger-valued critical numbers$(\mathrm{s}_{1},\mathrm{s}_{2},\ldots,\mathrm{s}_{\mathrm{m}})$such that, whenever there remain$\mathrm{k}$choices yet

to be made, then the optimal strategy immediately selects a candidate if it appears after or ontime$\mathrm{s}_{\mathrm{l}\mathrm{c}}$, but no later than$\mathrm{b}(\mathrm{n})$. Moreover,$\mathrm{s}_{\mathrm{k}}=\min\{\mathrm{i}\leq \mathrm{b}(\mathrm{n}):\mathrm{G}_{\mathrm{i}}(\mathrm{k})\geq 0_{1}^{1}$

where$\mathrm{G}_{\mathrm{i}}^{(\mathrm{k})}$, lsisb(n),$1\leq \mathrm{k}\leq \mathrm{m}$$\mathrm{s}_{\mathrm{k}}$is non-increasing in$\mathrm{k}$and detemined by,, is defined recursively as$\mathrm{k}\geq 2$$\mathrm{G}_{\mathrm{i}}=\mathrm{G}+\sum_{-}^{)}(\mathrm{k})(1),\frac{1}{\mathrm{j}- 1}\mathrm{G}^{(\mathrm{k}}\mathrm{i}\mathrm{i}=\max(\mathrm{i}+1\mathrm{b}(\mathrm{n}\mathrm{S}\mathrm{k}1)\mathrm{i}- 1)$starting with$\mathrm{i}=\mathrm{i}+\mathrm{b}()\sum_{1}^{\mathrm{n}}\frac{1}{\mathrm{j}- 1}\iota=\sum_{\mathrm{i}-}^{\mathrm{n}}\frac{1}{\mathrm{t}}-\frac{\mathrm{c}\mathrm{n}}{\mathrm{b}(\mathrm{n})}$$\mathrm{G}_{\mathrm{i}}^{(1)}=\sum \mathrm{i}=\mathrm{i}\mathrm{n}\frac{1}{\mathrm{j}}.-$

..

.

.

3.2 Asymptotic results
Lemma 3.1
satisfies the following recursive relationWhen$\mathrm{s}_{\mathrm{k}}^{*}1$$\mathrm{c}\leq \mathrm{e}^{-},$

Let $\mathrm{Y}=1+\log\beta$ . Then from Lemma 3.1 we can calculate$\mathrm{s}_{1}^{*}=\mathrm{e}\mathrm{X}y-(1+_{\mathrm{v}})_{/}^{\iota}$$\mathrm{s}_{2}^{*}=\mathrm{e}\mathrm{X}\mathrm{i}-(1+\gamma\sqrt{1+\frac{4}{3}\gamma})\{$$\mathrm{s}_{\mathrm{k}}^{*}$

successively as follows.

82$\mathrm{S}_{3^{=\mathrm{e}}}^{*j-}\mathrm{X}[1+\mathrm{v}\sqrt{1+\frac{2}{3}\gamma\{1+|1+\frac{4}{3}\mathrm{Y})3/2||}]_{l}^{\iota}$Let$\mathrm{q}_{\mathrm{m}}^{*},$$\mathrm{m}\geq 1$.

, be the expected net payoff for the$\mathrm{m}$choice duration problem when$\mathrm{n}$tends

to infinity. Then we have

Lemma 3.2
When$\mathrm{c}\leq \mathrm{e}^{-1}$, we have for$\mathrm{m}\geq 1\mathrm{q}_{\mathrm{m}}^{*}=-(\sum_{\mathrm{k}=\rceil}^{\mathrm{m}}\mathrm{s}^{*}\mathrm{k}\log \mathrm{s}^{*}\mathrm{k}+\mathrm{m}\mathrm{c})$.

Table 1
The asymptotic critical number$\mathrm{s}_{\mathrm{m}}^{*}\mathrm{r}\mathrm{o}\mathrm{r}$some values of$\mathrm{m}$and$\mathrm{c}$’$\mathrm{s}_{\infty}^{*(_{=\beta})}$0.0

1.00000.1

0.2

0.89420.77170.3

0.6130$\mathrm{s}_{2}^{*}$$\mathrm{s}_{1}^{*}$$\beta$$\mathrm{c}$0.13530.15130.17540.22080.07990.04930.09900.12940.06980.18980.10470.1761$\mathrm{s}_{10}^{*}$$\mathrm{s}_{5-}^{*}$$\mathrm{s}_{3\sim}^{*}$

0.01990.04160.08390.16900.0000.0024
0.02810.0787$()$0.02800.07870.16840.1684

Table 2
The asymptotic expected net payoff$\mathrm{q}_{2}^{*}$$\mathrm{q}_{1}^{\mathrm{x}}$$\mathrm{q}_{3}^{*}$$\mathrm{q}_{\mathrm{m}}^{*}$

for some values of$\mathrm{q}_{5}^{*}$$\mathrm{m}$$\mathrm{q}_{10}^{*}$

and$\mathrm{c}$$\mathrm{q}_{\infty}^{*}$$\mathrm{c}$0.00.27070.1

0.18580.10530.03350.2
0.3

0.47250.31470.17000.04890.62080.40050.20620.05470.8066
0.48710.2322
0.0569

Lemma 3.3$\mathrm{q}_{\infty}^{*}=(_{\beta\beta’}-)$

4. Multiple choice duration problem with a replacement cost

0.96560.51950.23630.05701.00000.5197
0.23630.057083
Thus far we have implicitly assumed that the objects, once chosen, are possessed until theprocess terminates. Instead, in this section, we are allowed to possess only one object at atime and a constant costis incurred each time replacement takes place.
$\mathrm{d}(>0)$

4.1 The finite horizon problem
We treat therefeITed to as theto m-l times,$\mathrm{U}_{\mathrm{i}}^{(\mathrm{k})}$and$\mathrm{v}_{\dot{\mathrm{t}}}^{(\mathrm{k})}$choice duration problem with a replacement cost$\mathrm{m}$$\mathrm{m}$$\mathrm{m}\geq 2$$\mathrm{d}$(the problem is here

choice problem if we are allowed to make replacement of the objects up). Let the state of the process be defined as in Section 2, and let also$\mathrm{W}_{\mathrm{i}}^{(\mathrm{k})}$,be defined similarly as the expected additional net payoff under an optimal

strategy starting from state$1\leq \mathrm{i}\leq \mathrm{n}$$(\mathrm{i},\mathrm{k}),$,lsksm. Then the optimality equations (2) $-(4)$ still

hold if (3) is replaced by$\mathrm{U}_{\mathrm{i}}^{(\mathrm{k}\rangle}=- \mathrm{d}+\frac{1}{\mathrm{n}}\mathrm{i}=\sum\frac{\mathrm{i}}{\mathrm{j}}+\mathrm{i}\mathrm{n}\mathrm{i}=\mathrm{i}\sum\frac{\mathrm{i}}{\mathrm{j}(|- 1)}\mathrm{W}_{\mathrm{i}}^{(}\mathrm{n}+1\mathrm{k}- 1)$$\mathrm{U}_{\mathrm{i}}^{(\mathrm{m})}=\frac{1}{\mathrm{n}}\sum_{\mathrm{i}=\mathrm{i}}\mathrm{n}\frac{\mathrm{i}}{\mathrm{j}}+\sum_{+\mathrm{i}=\mathrm{i}1}^{\mathrm{n}}\frac{\mathrm{i}}{\mathrm{j}\zeta|- 1)}\mathrm{W}_{\mathrm{j}}^{(}\mathrm{m}-1)$,$1\leq \mathrm{k}\leq \mathrm{m}-1$.

ObseIve that, once the first choice is made, our problem reduces to the m-l choice problem
with an acquisition cost . Thus the main concem of this problem is to determine when to$\mathrm{d}$make the first choice.
If$\mathrm{d}>\frac{\mathrm{K}(\mathrm{n})}{\mathrm{n}}\sum_{(i=\mathrm{K}\mathrm{n})}\frac{1}{\mathrm{j}’}\mathrm{n}$hence the$\mathrm{m}$where$\mathrm{K}(\mathrm{n})$is as defined in Section 3, no replacement takes place andchoice problem reduces to the one choice problem treated in Section 2.

In the case(15)$\mathrm{d}\leq\frac{\mathrm{K}(\mathrm{n})}{\mathrm{n}}\sum_{\mathrm{i}=\mathrm{K}(\mathrm{n})}\frac{1}{\mathrm{j}’}\mathrm{n}$the optimal strategy can be summarized as follows
Theorem 4.1

For the$\mathrm{m}$choice duration problem with the cost condition (15), there exists a sequence ofinteger-valued critical numbers$(\mathrm{s}_{1},\mathrm{s}_{2},\ldots,\mathrm{s}_{\mathrm{m}}\iota)- 1,\mathrm{m}$candidate that appears after or on time$\mathrm{t}_{\mathfrak{n}}$such that the optimal strategy first selects aand then it replaces the previously chosen object

with a new candidate that appears after or no time

replacements are available,$\mathrm{c}(\mathrm{n})=\max_{\mathfrak{l}}^{(}\mathrm{i}$Moreover,$\mathrm{t}_{\mathrm{n}}\leq \mathrm{s}_{\mathrm{m}1}-$and:$1\leq \mathrm{k}\leq \mathrm{m}-1$$\mathrm{U}_{\mathrm{i}}^{(1)}\geq 0_{1}^{\backslash }$’but no later than$\mathrm{c}(\mathrm{n})$if, where.

is non-increasing in and these values are determined by$\mathrm{k}$$\mathrm{s}_{\mathrm{k}}$$\mathrm{s}_{\mathrm{k}}.$$\mathrm{k}$

more

84

$\mathrm{t}_{\mathrm{m}}=\min(\mathrm{i}\leq \mathrm{c}(\mathrm{n})$:$\mathrm{G}_{\mathrm{i}}^{(\mathrm{m})}\geq \mathrm{i}=\mathrm{C}(\sum_{\mathrm{n})+1}\frac{1}{\mathrm{j}- 1}\mathrm{n}\mathrm{t}\sum_{=\mathrm{i}}^{\mathrm{n}}\frac{1}{\mathrm{t}}-\frac{\mathrm{d}\mathrm{n}}{\mathrm{c}(\mathrm{n})}\{$$\mathrm{s}_{\mathrm{k}}=\min\{\mathrm{i}\leq \mathrm{c}(\mathrm{n}):\mathrm{G}^{()}\mathrm{i}\mathrm{k}\geq 0_{l}^{1}$

where$\mathrm{G}_{\mathrm{i}}^{(\mathrm{k})},$$1\leq \mathrm{i}\leq \mathrm{c}(\mathrm{n}),$$1\leq \mathrm{k}\leq \mathrm{m}$,$1\leq \mathrm{k}\leq \mathrm{m}- 1$, is defined recursively as$\mathrm{k}\geq 2$$\mathrm{G}^{(\mathrm{k})}=\mathrm{G}\mathrm{i}\mathrm{i}(1)+\sum_{\mathrm{i}\mathrm{i}=\max(+1,\mathrm{s}\mathrm{k}-1)}^{()}\frac{1}{\mathrm{j}- 1}\mathrm{c}\mathrm{n}\mathrm{G}^{(\dot{\mathrm{k}}}\mathrm{i}- 1)$starting with.

$\mathrm{G}_{\mathrm{i}}^{(1)}=\sum_{\mathrm{i}=\mathrm{i}}^{\mathrm{n}}\frac{1}{\mathrm{j}}- \mathrm{i}1\sum_{=\mathrm{i}+}^{\mathrm{c}(\mathrm{n}}\frac{1}{\mathrm{j}- 1})\mathrm{t}\mathrm{i}\sum_{=}^{\mathrm{n}}\frac{1}{\mathrm{t}}-\frac{\mathrm{d}\mathrm{n}}{\mathrm{c}(\mathrm{n})}$

4.2 Asymptotic results
The cost condition (15) is reduced, as$\mathrm{d}\leq \mathrm{e}^{-1}$Let$6= \lim_{\mathrm{n}arrow\infty}\frac{\mathrm{c}(\mathrm{n})}{\mathrm{n}}$equation -xlog$\mathrm{s}_{\mathrm{k}}^{*}=\lim_{\mathrm{n}arrow\infty}\frac{\mathrm{s}_{\mathrm{k}}}{\mathrm{n}},$$\mathrm{n}arrow\infty$

, to

.

(16)

. Then, under the condition (16), 6 is a unique rootof the. We have the following result conceming the limiting values
and.
$\mathrm{x}\in[\mathrm{e}^{-1},1)$$\mathrm{x}=\mathrm{d}$$\mathrm{k}\geq 1$$\mathrm{t}_{\mathrm{m}}^{*}=\lim_{\mathrm{n}arrow\infty}\frac{\mathrm{t}_{\mathrm{m}}}{\mathrm{n}}$Lemma 4.1
When$\mathrm{d}\leq \mathrm{e}^{-1},$$\mathrm{t}_{\mathrm{m}}^{*}$

is expressed in terms of$\mathrm{s}_{\mathrm{m}}^{*}$

as$\mathrm{t}_{\mathrm{m}}^{*}=\mathrm{e}\mathrm{X}\mathrm{d}-\{_{1}\ulcorner\sqrt{(_{1+\log \mathrm{s}_{\mathrm{m}}}*)^{2}-\{2+\log 6)_{\mathrm{l}\mathrm{o}}\mathrm{g}6}+]|\backslash |l$where$\mathrm{s}_{\mathrm{k}}^{*},$$1\leq \mathrm{k}\leq \mathrm{m}$,, satisfies the following recursive relation$\mathrm{s}_{\mathrm{k}^{=\mathrm{e}}}^{*l(\sqrt{(_{1+\mathrm{l}\mathrm{o}}\mathrm{g}6)^{2}-2\sum\frac{[(\mathrm{k}- \mathrm{i}+2)\mathrm{B}_{\mathrm{k}1\mathrm{i}^{+(\mathrm{k}}}+-\mathrm{i}+1)\mathrm{B}\mathrm{k}+2\mathrm{i}]}{(\mathrm{k}- \mathrm{i}+2)!}\mathrm{k}1}\{]}\mathrm{X}-1+\mathrm{i}=1$

’

where
$\mathrm{B}_{\mathrm{k},\mathrm{i}}=(\log \mathrm{s}_{\mathrm{i}}^{*})^{\mathrm{k}- \mathrm{i}}-|_{\log}8)^{\mathrm{k}- \mathrm{i}}$$1x\mathrm{t}\lambda=1+\log 6$. Then from Lemma 4. 1$\mathrm{t}_{2}=\mathrm{e}\mathrm{X}*q-(1+\sqrt{1+\frac{4}{3}\lambda^{3}})\}$

85$\mathrm{t}_{3^{=\mathrm{e}}}^{*}\mathrm{x}\oint-[1+\sqrt{1+\frac{2}{3}\lambda^{3}\{1+\mathfrak{l}^{1+\frac{4}{3}}\lambda)3/21(}]_{(}^{1}$Let$\mathrm{m}\geq 2$$\mathrm{r}_{\mathrm{m}}^{*},$, be the expected net payoff for the$\mathrm{m}$.
choice duration problem when

to infinity. Then we have

Lemma 4.2.

(i) When$\mathrm{d}>\mathrm{e}^{-1},$$\mathrm{r}_{\mathfrak{m}}^{*}=2\mathrm{e}^{-2}$(ii) When$\mathrm{d}\leq \mathrm{e}^{-1},$$\mathrm{r}_{\mathrm{m}}^{*}=-(=\sum_{\mathrm{k}1}^{\mathrm{m}-1}\mathrm{S}_{\mathrm{k}\mathrm{g}}^{**}\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{k}+\mathrm{t}_{\mathrm{n}}^{*}\log \mathrm{h}^{*}+(\mathrm{m}- 1)\mathrm{d})$.

Table 3
The asymptotic critical number$\iota_{2}^{*}$$\mathrm{d}$$\mathrm{t}_{\mathrm{m}}^{*}$$\iota_{3}^{*}$

for some values ofand$\mathrm{m}$$\mathrm{d}$$\mathrm{t}_{\infty}*$$\mathrm{t}_{10}^{*}$$\mathrm{t}_{5-}^{*}$

.

0.1
0.2

0.3

0.09160.10630.12430.06560.08850.11860.03970.07250.11540.02700.06840.11510.02680.06840.1151

Table 4
The asymptotic expected net payoff$\mathrm{d}$

0.1
0.2
0.3

$\mathrm{r}_{2}^{*}$

0.40470.34350.2927$\mathrm{r}_{3}^{*}$$\mathrm{r}_{\mathrm{m}}^{*}\mathrm{f}\mathrm{o}\Gamma$some values of

0.58280.41460.3056

and

0.6166
0.41980.3059$\mathrm{d}$$\mathrm{r}_{\infty}^{*}$$\mathrm{r}_{10}^{*}$$\mathrm{r}_{5}^{*}$

0.49340.38450.3017$\mathrm{m}$0.61680.41980.3059

Lemma 4.3
Let 6 be the unique root$\mathrm{x}\in(0, \mathrm{e}^{1}-]$of the equation -x$\mathrm{r}_{\infty}^{*()_{(\begin{array}{l}1-\underline{\mathrm{d}^{2}}\delta\delta\end{array})}}=6-6’-\iota_{\infty}**\log \mathrm{t}_{\infty}$

where

,

$\log \mathrm{x}=\mathrm{d}$for$\mathrm{d}\leq \mathrm{e}^{-1}$. Then$\mathrm{n}$

tends

86
References[1]

Ferguson,$\mathrm{T}.\mathrm{S}$. (1989) Who solved the secretary problem ? Statistical Science 4,282-289.
[2] Ferguson, T.S., Hardwich,. and Tamaki, M. (1992) Maximizing the duration ofowning a relatively best object. Contemporary Mathematics 125, 37-57.
[3] Gilbert, J. and Mosteller, F. (1966) Recognizing the maximum of a sequence. J. Amer.
Statist. Assoc. 61, 35-73.
[4] Lehtinen, A. (1993) The best choice problem with an unknown number of objects. Z.
Oper. Res. 37, 97-106.
[5] Petruccelli,. (1983) On the best-choice problem when the number of observations ia$\mathrm{J}.\mathrm{P}$$\mathrm{J}.\mathrm{D}$random. J. Appl. Probab. 20, 165-171.

. and Sonin,.
The best choice problem for a random number ofobjects. Theor. Probab. Appl. 17, 657-668.
(1978)[7] Sakaguchi,
problems and OLA policies. Rep. Statist. Appl. Res.
JUSE 25, 124-128.
[8] Samuels,. Ghosh. (1991) Secretary problems, in: Handbook of Sequential Analysis(.Sen,), Marcel Decker, New York, 381-405.
and[6] Presman,$\mathrm{E}.\mathrm{L}$$\mathrm{M}$$\mathrm{I}.\mathrm{M}$$(197_{\sim}9)$$\mathrm{D}\mathrm{o}\mathrm{w}\mathrm{I}\gamma$$\mathrm{S}.\mathrm{M}$$\mathrm{P}.\mathrm{K}$[9]$\mathrm{B}.\mathrm{K}$$\mathrm{e}\mathrm{d}\mathrm{s}$Tamaki, M. (1979) OLA policy and the best choice problem with random number ofobjects. Math. Japonica 24, 451-457.