betaFeedback

WorksMathematics

On a Secretary Problem with Two Equal-Sized Pools of Candidates

Abstract

This paper presents the solution of a secretary type problem where the decision maker observes a sequence of offers of two types. There are N objects of both types and these objects appear to the decision maker in random order. Objects can only be compared when they are of the same type. The objects of a given type that have already appeared can be ranked according to a complete order. Objects of different types are not comparable. On the appearance of an object, the decision maker must decide whether to accept that object (and thus stop searching) or irrevocably reject it (and thus continue searching). The goal of the decision maker is to accept an object that is the best of its type. The authors present the general form of the optimal policy and the asymptotical solution. The authors give a strong result describing whether an object of relative rank one should be accepted when the same number of objects of both types have been seen.

Introduction

A lot of research concerning the optimal stopping of processes with discrete time involves generalizations or extensions of the so called secretary problem. In the classical secretary problem [8] a decision maker (DM) sequentially observes a set of NN objects whose values are comparable according to a linear ordering. The DM is allowed to select only one object and selection can only occur at the moment when that object appears. The goal of the DM is to maximize the probability of accepting the absolute best object (of absolute rank one). The objects appear in random order. From the definition of the problem, at moment nn the DM only observes the rank of the current object relative to the first nn objects to appear. The sequence of absolute ranks is a random permutation of the integers from 1 to NN. The sequence of the relative ranks of the first nn objects is the corresponding permutation based on comparing the first nn objects. Hence, these relative ranks form a random permutation of the integers from 1 to nn. The DM should only consider objects that have a relative rank of 1 and given that the current object has relative rank one, the probability that it is the best of all the objects (has absolute rank one) is equal to the proportion of objects that have already appeared. Since decisions are made sequentially, it is natural to apply dynamic programming to solve such a problem [16].

Key words and phrases. Secretary problem, optimal stopping, dynamic programming, partial order, discrete time stochastic processes.

The authors acknowledge support from the NCN grant: DEC-2015/17/B/ST6/01868.

Some authors have considered analogous problems in which the DM has greater room for manoeuvre, for example the DM could return to a previously observed object, which is still available with some probability [25, 28]. Some authors have considered similar problems with different objectives, for instance the DM wishes to maximize the expected value of the chosen number, or to choose one of the best kk objects [24, 26]. In other cases, the DM has a richer source of information, for example she can observe the precise values of objects from a known distribution, rather than just comparing values [21]. Game theoretic versions of the secretary problem have also been considered [18], [20].

Another direction of research considers sequential decision problems in which the DM can only compare objects according to a partial ordering and the aim of the DM is to choose one of the maximal elements. In such problems one might consider the optimal policy for specific types of partial orders (e.g. binary trees [11], [12], [17]) or efficient universal algorithms for more general partial orders [4], [6], [7], [13], [19], [23]. Similar problems can be defined by assuming that objects have multivariate attributes [9], [10].

A natural extension of the classical secretary problem is to consider two linearly ordered pools of objects of the same cardinality, equal to NN. Thus we deal here with a partial ordering consisting of two independent linear orders. It is assumed that these 2N2N objects appear in random order. The DM can only accept an object at the moment of its appearance. The goal of the DM is to choose either of the two best ranked objects. This problem has turned out to be much more difficult that the original secretary problem and it seems that its full solution has been an open problem for a long time. A number of similar problems have been solved. According to one such model, the pools are interpreted as copies of each other. For example, when there are two pools of NN objects, these objects can be interpreted as NN sets of identical twins. In such problems, each object is comparable to all of the other objects and only its twin is seen to be equivalent. If the DM has not previously seen a copy of the current object, then she knows that a copy of that object will appear later. Hence, the DM should only ever accept the second copy of an object to appear. Such an object should also be the best of those to have appeared so far [5]. This model has been extended to problems in which there are kk copies of each object [1]. According to another such model, there are kk such pools of objects. First, the objects from pool one all appear in random order, before the objects from successive pools appear [14], [15]. The model considered in this paper differs from those according to which copies of objects appear, since according to the model presented here an object from one pool cannot be compared with any object from the other pool. It differs from models according to which the pools appear in sequence, since according to the model presented here the probability that the next object to appear is from a given pool equals the proportion of the objects that have not appeared so far which come from that pool. In this paper we give the form of the solution to this problem for finite NN, a procedure to derive this solution and the asymptotic form of the solution as N→∞N \to\infty. A (perhaps surprisingly) strong result is presented defining whether an object of relative rank one should be accepted when the same number of objects of both types have been seen.

§ 2 presents the model. A procedure for deriving the optimal strategy based on dynamic programming is given in § 3. This section also gives intuitive arguments regarding the general form of the optimal strategy. § 4 presents the concept of a one step look ahead rule (OSLAR), see [22], in the framework of the model presented. The general form of the optimal solution, a threshold rule, is derived in § 5, which includes a (perhaps surprisingly) strong result regarding the threshold rule for all N≥3N \ge3. The asymptotic form of the solution is presented in § 6. Conclusions and directions for future research are presented in § 7. A number of the proofs and lemmas are technical. For this reason they are presented in an appendix. The appendix also contains a table describing the notation used throughout the paper.

A Mathematical Description of the Model

A decision maker (DM) observes a sequence of objects of two types, such that there are NN objects of both types. These objects appear in random order and the nn-th object appears at moment nn, n=1,2,…,2Nn = 1,2,\ldots,2N. The current object can be ranked in comparison to all of the previous objects of the same type, but cannot be compared to any of the objects of the other type.

The DM can only accept one object and an object can only be accepted at the moment of its appearance. Suppose that the DM is still searching at moment nn, she can either reject that object (and continue observing the sequence) or accept that object (and thus stop searching). The goal of the DM is to accept one of the two objects that is the absolute best of its type. Hence, we define the reward of the DM to be 1 when such an object is chosen and 0 otherwise. The absolute rank of an object is defined to be its rank in comparison to all the objects of its type (the best has absolute rank 1, the worst has absolute rank NN). The relative rank of an object is defined to be its rank in comparison to the objects of its type that have already appeared. It follows that the DM should only consider objects that have relative rank 1. Such objects will be referred to as candidates.

Suppose that ii objects of type 1 and jj objects of type 2 have appeared by moment nn, where i+j=ni+j=n. Let αi,j\alpha_{i,j} denote the probability that the next object is of type 1. From the assumption that the objects appear in random order, it follows that αi,j=N−i2N−i−j\alpha_{i,j}=\frac{N-i}{2N-i-j}, i.e. the number of remaining objects of type 1 divided by the total number of objects remaining. Given that the next object is of type 1 (2), then the probability that it has relative rank 1 is 1i+1\frac{1}{i+1} (1j+1\frac{1}{j+1}, respectively). Define a sequence of 2N+12N+1 four-tuples Tn=(Un,Vn,Kn,Rn)T_n=(U_n,V_n,K_n,R_n), such that

  • i: T0=(0,0,0,0)T_0=(0,0,0,0),

  • ii: P[(Un+1,Vn+1,Kn+1)=(Un+1,Vn,1)]=αUn,VnP[(U_{n+1},V_{n+1},K_{n+1})=(U_n+1,V_n,1)]=\alpha_{U_n,V_n},

  • iii: P[(Un+1,Vn+1,Kn+1)=(Un,Vn+1,2)]=1−αUn,VnP[(U_{n+1},V_{n+1},K_{n+1})=(U_n,V_n+1,2)]=1-\alpha_{U_n,V_n}.

  • iv: P(Rn=r∣Un=i,Kn=1)=1iP(R_n=r\mid U_n=i,K_n=1)=\frac{1}{i}, r=1,2,…,ir=1,2,\ldots,i.

  • v: P(Rn=r∣Vn=j,Kn=2)=1jP(R_n=r\mid V_n=j,K_n=2)=\frac{1}{j}, r=1,2,…,jr=1,2,\ldots,j.

Hence, KnK_n denotes the type of the nn-th object to appear, while UnU_n and VnV_n denote the number of type 1 and type 2 objects, respectively, to have appeared among the first nn objects. Analogously, RnR_n denotes the relative rank of this object with respect to the objects of the same type that have already appeared. By definition U2N=V2N=NU_{2N}=V_{2N}=N. A realization of the sequence of 4-tuples (Un,Vn,Kn,Rn)(U_n,V_n,K_n,R_n), 0≤n≤2N0\leq n\leq2N, will be referred to as a trajectory of the search process.

Given Un=iU_n=i and Vn=jV_n=j, the relative ranks of future objects are independent of the remaining information from the trajectory. Hence, it suffices to define the current state of the process at moment nn to be S(n)=(i,j,k)S(n)=(i,j,k) where i=i(n)i=i(n) and j=j(n)j=j(n) are the numbers of objects that have appeared of type 1 and 2, respectively. Define kk such that k=k(n)=0k=k(n)=0 if the current object is not the best of its type seen so far, k=k(n)=wk=k(n)=w if the current object is the best seen so far (a candidate) of type ww, w=1,2w=1,2. We may assume that when the DM rejects a candidate in state (i,j,k)(i,j,k), k=1,2k=1,2, then the state immediately switches to (i,j,0)(i,j,0) before the next object appears.

Denote by τm\tau_m the moment at which the mm-th candidate appears, i.e. this is the mm-th smallest value of nn for which k(n)≠0k(n)\neq0. Let Xm=1X_m=1 when the object observed at time τm\tau_m is the best of all objects of its type, otherwise Xm=0X_m=0. Let Ym=E(Xm∣Fτm)Y_m=E(X_m\mid\mathcal{F}_{\tau_m}), where Fτm\mathcal{F}_{\tau_m} represents the information given by the states observed at moments τ1,τ2,…,τm\tau_1,\tau_2,\ldots,\tau_m. The sequence YmY_m is adapted to the filtration $(\mathcal{F})_m and is not affected by additional information, e.g. the relative rank of other objects that have appeared so far. Note that when S(τm)=(i,j,k)S(\tau_m)=(i,j,k), then Ym=i/NY_m=i/N if k=1k=1 and Ym=j/NY_m=j/N if k=2k=2. If τM\tau_M is the time of the appearance of the final candidate, we formally define that k(τM+1)=k(τM+2)=⋯=0k(\tau_{M+1})=k(\tau_{M+2})=\cdots=0 and YM+1=YM+2=⋯=0Y_{M+1}=Y_{M+2}=\cdots=0. Thus (Ym)m(Y_m)_m may be considered as a process with infinite time horizon and absorbing state 0. Based on this formulation, the DM obtains a reward of 1 by stopping at either the last decision point at which Kτm=1K_{\tau_m}=1 or the last decision point at which Kτm=2K_{\tau_m}=2.

Derivation of the Optimal Strategy by Dynamic Programming

Dynamic programming is a well-known method of solving sequential decision problems when the total reward can be written as a linear combination of intermediate payoffs, see [2]. This approach can be used to derive the optimal reward and strategy for any particular realization of the problem considered. It will also be useful in the derivation of general results regarding the general form of the optimal strategy and its asymptotic form. Intuitively, given that jj objects of type 2 have been seen, then a candidate of type 1 should be accepted if and only if the number of type 1 objects to have appeared is equal to or exceeds some threshold iN∗(j)i_N^*(j), i.e. a candidate should be accepted in state (i,j,1)(i,j,1) if and only if i≥iN∗(j)i \ge i_N^*(j). It is expected that this threshold is non-increasing in jj. This result will be proved in § 5. By symmetry, a candidate should be accepted in state (i,j,2)(i,j,2) if and only if j≥iN∗(i)j \ge i_N^*(i).

Let vi,jv_{i,j} denote the optimal probability of choosing one of the maximal elements when ii objects of type 1 and jj objects of type 2 have already been rejected, 0≤i,j≤N0 \le i,j \le N. This will be called the value function. From the symmetry between the two types, vi,j=vj,iv_{i,j}=v_{j,i}. By definition vN,N=0v_{N,N}=0.

Given that the present state is (i,j,0)(i,j,0), the next observation is of type 1 with probability αi,j=N−i2N−i−j\alpha_{i,j}=\frac{N-i}{2N-i-j}. In this case, it will be a candidate with probability 1i+1\frac{1}{i+1} and should be accepted if and only if the probability of such a candidate being the best of all objects of type 1, i+1N\frac{i+1}{N}, is greater than the expected reward from future search vi+1,jv_{i+1,j}. Analogously, the next observation is of type 2 with probability 1−αi,j1-\alpha_{i,j}. In this case, it will be a candidate with probability 1j+1\frac{1}{j+1} and should be accepted if and only if the probability of such a candidate being the best of all objects of type 2, j+1N\frac{j+1}{N}, is greater than the expected reward from future search vi,j+1v_{i,j+1}. If an object does not have relative rank 1, then the DM continues searching. Hence, the recursion equation for the value function is given by

vi,j=αi,j[ivi+1,ji+1+max⁡{1N,vi+1,ji+1}]+(1−αi,j)[jvi,j+1j+1+max⁡{1N,vi,j+1j+1}].(1)v_{i,j}=\alpha_{i,j}\left[\frac{i v_{i+1,j}}{i+1}+\max\left\{\frac{1}{N},\frac{v_{i+1,j}}{i+1}\right\}\right]+(1-\alpha_{i,j})\left[\frac{j v_{i,j+1}}{j+1}+\max\left\{\frac{1}{N},\frac{v_{i,j+1}}{j+1}\right\}\right]. \tag*{(1)}

Using this equation, the optimal strategy for a given NN can be derived recursively. When the present state is (i,j,1)(i,j,1), the current object should be accepted if and only if iN≥vi,j\frac{i}{N}\ge v_{i,j}. Similarly, when the present state is (i,j,2)(i,j,2), the current object should be accepted if and only if jN≥vi,j\frac{j}{N}\ge v_{i,j}. Note that, by symmetry, if the current object should be accepted in state (i,j,1)(i,j,1), then the current object should be accepted in state (j,i,2)(j,i,2). Also, when i≥ji\ge j, if a candidate should be accepted in state (i,j,2)(i,j,2), then it should be accepted in state (i,j,1)(i,j,1).

Example

References

  1. [24]K. Szajowski. Optimal choice of an object with a-th rank (in polish). Mathematyka Stosowana (Mathematica Applicanda), 19:51–65, 1982.
  2. [25]M. Tamaki. Secretary problem with uncertain employment when backwards solicitation is permitted. Mathematica Japonica, 24:439–450, 1979.
  3. [26]R. J. Vanderbei. The postdoc variant of the secretary problem. url-http://www.princeton.edu/rvdb/tex/PostdocProblem/PostdocProb.pdf, 1983.
  4. [27]R. Varadhan and P. Gilbert. BB: An R package for solving a large system of nonlinear equations and for optimizing a high-dimensional nonlinear objective function. Journal of Statistical Software, 32:1–26, 2010.DOI
  5. [28]M. C. Yang. Recognizing the maximum of a random sequence based on relative rank with backward solicitation. Journal of Applied Probability, pages 504–512, 1974.DOI

Paper details

vlnc:W_e22zdjzs
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents