Parallel Search and Information Gathering
研究决策者在多个项目中并行选择的问题，每个项目有随机回报和时滞，目标是最大化收益函数。适用于研发、求职、价格搜索等场景，提出简单排序规则以优化并行选择。
Many microeconomic problems fall into the following category. A decision maker has a number (n) of opportunities or projects. Each project yields an unknown reward at an uncertain time, and is characterized by an independent joint probability distribution. Once a project is selected, its reward is revealed after a random time lag when it is collected. The projects are selected sequentially in any order desired. Furthermore, at any time, a number m (1 < m < n) of projects may be explored simultaneously, that is, in parallel. The decision problem is to determine the sequential strategy for choosing the projects to maximize an objective which is a function of the rewards collected. Most of the problems in search theory, dynamic allocation problems, and many information-gathering problems fall into this class. A firm's problem of choosing technologies to develop products, job search decision of workers, price search of consumers, development of resource pools, exploration problems of mines and wells, investment decisions, and marketing strategies are but a few examples where the problem stated above is naturally applicable. Indeed, the problem is basic to many imperfect information contexts, and its analysis reveals useful insights into the nature of information acquisition and structures of markets. The motivation for the study of parallel search and information-gathering models is obvious. In problems where information acquisition is costly and time consuming, the returns to parallel effort are higher than when undertaking a single project at a time. For example, in research and development contexts, if large improvements in information are possible at low cost in early stages of development, then it becomes efficient to run several projects in parallel. In scheduling and dynamic allocation applications, where all projects must be undertaken, parallel operation substantially reduces the overall completion time. The instance of the problem when only one project can be chosen at a time (m =1) has been studied extensively in recent economic literature. In contrast, there has been no significant attempt to study parallel selection of projects. Unfortunately, the elegant results that may be derived for singleproject selection do not readily generalize to the parallel project case. Furthermore, this problem, in principle, may be formulated in a dynamic programming framework, and solved through standard techniques (such as backward induction or fixed-point methods). However, in most actual cases, this approach, besides shedding little economic insight, would be a combinatorially complex task of formidable proportions unless n and m are small. Hence, there is a need to study the effectiveness of meaningful operational rules. The purpose of this paper is to point out that simple ordering rules are obtained for the optimal parallel selection of projects, under reasonably general and meaningful conditions. These conditions may be stated in terms of risks and stochastic orderings of the distributions associated with the projects. The problem of single project selection (m = 1), falls into the general class of bandit processes (see the works of J. C. Gittens, 1979, and others), the solution for which is usually characterized by a reservation rule. Each project is assigned a reservation number or an index (analogous to internal rate of return) depending only on the features of that project and independent of all other projects. At each decision instant, the project with the highest reservation number is selected. These reservation numbers, as* Department of Economics, and Center for Urban Affairs and Policy Research, Northwestern University, Evanston, IL 60201. Research supported by NSF grant SES-8708325.