Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-26T12:56:59.672Z Has data issue: false hasContentIssue false
  • English
  • Français

The job-search problem with competition: an evolutionarily stable dynamic strategy

Part of: Sequential methods

Published online by Cambridge University Press:  01 July 2016

E. J. Collins  and
J. M. Mcnamara
E. J. Collins
Affiliation:
University of Bristol
J. M. Mcnamara*
Affiliation:
University of Bristol
*
∗Postal address for both authors: School of Mathematics, University of Bristol, University Walk, Bristol BS8 1TW, UK.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a game-theoretical solution for an optimal stopping problem which we describe in terms of a job-search problem with an infinite population of candidates and an infinite population of posts of varying value. Each candidate finds posts from the post population at unit rate. If a post found is still vacant, a candidate can either accept it or reject it. The reward to a candidate is the value of the post if one is accepted and zero if he never accepts a post. There are no costs for searching, no discounting of future rewards and no recall of previously found posts. The only pressure on a candidate to accept a post comes from the changing rate at which he finds vacant posts (and the values associated with them) as a result of the actions of the other candidates. It is not possible to define optimality for a single candidate without reference to the policies followed by the other candidates. We say a policy π is an evolutionarily stable strategy (ESS) if it has the following property: if all candidates used π and an individual candidate was given the option of changing his policy, then it would not be to his advantage to do so. We first find the optimal value function and optimal policy for the case of a single candidate operating in an environment where the distribution of posts on offer and the chance of finding one both vary with time in a known way. We then show that for the infinite population there is a unique ESS given by a control-limit policy π c, where the control-limit function c is the solution of a given differential equation with a given initial condition. This function c also gives the expected future reward function for any single candidate when all candidates use π c.

Keywords

SEQUENTIAL CHOICESECRETARY PROBLEMOPTIMAL STOPPING

MSC classification

Primary: 62L15: Optimal stopping
Secondary: 92D15: Problems related to evolution
Type
Research Article
Information
Advances in Applied Probability , Volume 25 , Issue 2 , June 1993 , pp. 314 - 333
Copyright
Copyright © Applied Probability Trust 1993 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Chow, Y. S. and Robbins, H. (1963) On optimal stopping rules. Z. Wahrscheinlichkeitsth. 2, 33–49.CrossRefGoogle Scholar
Elfving, G. (1967) A persistency problem connected with a point process. J. Appl. Prob. 4, 77–89.CrossRefGoogle Scholar
Enns, E. G. and Ferenstein, E. Z. (1990) A competitive best-choice problem with Poisson arrivals. J. Appl. Prob. 27, 333–342.Google Scholar
Ferguson, T. S. (1989) Who solved the secretary problem? Statist. Sci. 4, 282–296.Google Scholar
Freeman, P. R. (1983) The secretary problem and its extensions: a review. Internat. Statist. Rev. 51, 189–206.CrossRefGoogle Scholar
Gilbert, J. and Mosteller, F. (1966) Recognising the maximum of a sequence. J. Amer. Statist. Assoc. 61, 35–73.CrossRefGoogle Scholar
Guttman, I. (1960) On a problem of L. Moser. Canad. Math. Bull. 3, 35–59.Google Scholar
Hille, E. (1969) Lectures on Ordinary Differential Equations. Addison-Wesley, Reading, MA.Google Scholar
Karlin, S. (1962) Stochastic models and optimal policy for selling an asset. In Studies in Applied Probability and Management Science , ed. Arrow, K. J., Karlin, S. and Scarf, H., pp. 148–158. Stanford University Press.Google Scholar
Lippman, S. A. and Mccall, J. J. (1976) The economics of job-search: a survey. Econ. Inquiry 14, 155–189.Google Scholar
Majumdar, A. A. K. (1987) Optimal stopping for a full-information bilateral sequential game related to the secretary problem. Math. Japan. 32, 63–74.Google Scholar
Maynard Smith, J. (1982) Evolution and the Theory of Games. Cambridge University Press.CrossRefGoogle Scholar
Maynard Smith, J. and Price, G. R. (1973) The logic of animal conflict. Nature 246, 15–18.CrossRefGoogle Scholar
Mcnamara, J. M., Merad, S. and Collins, E. J. (1991) The hawk–dove game as an average cost problem. Adv. Appl. Prob. 23, 667–682.CrossRefGoogle Scholar
Moser, L. (1956) On a problem of Cayley. Scripta Math. 22, 289–292.Google Scholar
Neveu, J. (1974) Discrete-Parameter Martingales , North-Holland, Amsterdam.Google Scholar
Presman, E. L. and Sonin, I. M. (1975) Equilibrium points in a game related to the best choice problem. Theory Probab. Appl. 20, 770–781.Google Scholar
Sakaguchi, M. (1961) Dynamic programming of some sequential sampling designs. J. Math. Anal. Appl. 2, 446–466.CrossRefGoogle Scholar
Sakaguchi, M. (1984) Bilateral sequential games related to the no-information secretary problem. Math. Japon. 29, 961–973.Google Scholar
Sakaguchi, M. (1985) Non-zero sum games related to the secretary problem. Math. Japon. 30, 585–603.Google Scholar
Sakaguchi, M. (1989) Some two-person bilateral games in the generalized secretary problem. Math. Japon. 34, 637–654.Google Scholar
Siegmund, D. (1967) Some problems in the theory of optimal stopping rules. Ann. Math. Statist. 38, 1627–1640.Google Scholar
Snell, J. L. (1952) Applications of martingale system theorems. Trans. Amer. Math. Soc. 73, 293–312.Google Scholar