Treffer: Selection and Ordering Policies for Hiring Pipelines via Linear Programming: Selection and ordering policies for hiring pipelines via linear programming

Title:

Selection and Ordering Policies for Hiring Pipelines via Linear Programming: Selection and ordering policies for hiring pipelines via linear programming

Authors:

Boris Epstein, Will Ma

Source:

Operations Research. 72:2000-2013

Publication Status:

Preprint

Publisher Information:

Institute for Operations Research and the Management Sciences (INFORMS), 2024.

Publication Year:

2024

Subject Terms:

FOS: Computer and information sciences, Labor markets, 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, stochastic probing, Linear programming, hiring, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), adaptivity gap, 0101 mathematics, Theory of organizations, manpower planning in operations research, approximation algorithm

Document Type:

Fachzeitschrift Article

File Description:

application/xml

Language:

English

ISSN:

1526-5463
0030-364X

DOI:

10.1287/opre.2023.0061

DOI:

10.48550/arxiv.2210.04059

Access URL:

http://arxiv.org/abs/2210.04059
https://zbmath.org/7960292
https://doi.org/10.1287/opre.2023.0061

Rights:

CC BY

Accession Number:

edsair.doi.dedup.....2541e256df0035d12eb8a19c4e3f3e6e

Database:

OpenAIRE

Weitere Informationen

Hiring the right person for the job is crucial for the success of any organization. In “Selection and Ordering Policies for Hiring Pipelines via Linear Programming,” Epstein and Ma study several problems motivated by a firm that is carrying out a recruitment process. Restricted to a finite time budget, the firm must decide who will be interviewed out of a pool of applicants and who will receive offers among the interviewed applicants. They develop approximation algorithms with constant factor guarantees that approach optimality when the number of vacant positions grows large. The algorithms they develop are nonadaptive: they fix a subset of candidates and an order to conduct the interviews and the order remains unchanged, independent of the outcomes of other interviews. Thus, they establish bounds on the adaptivity gap: a worst-case measure of how poorly non-adaptive algorithms can perform with respect to their adaptive counterparts.

AN0179946692;opr01sep.24;2024Nov14.08:04;v2.2.500

Selection and Ordering Policies for Hiring Pipelines via Linear Programming

Hiring the right person for the job is crucial for the success of any organization. In "Selection and Ordering Policies for Hiring Pipelines via Linear Programming," Epstein and Ma study several problems motivated by a firm that is carrying out a recruitment process. Restricted to a finite time budget, the firm must decide who will be interviewed out of a pool of applicants and who will receive offers among the interviewed applicants. They develop approximation algorithms with constant factor guarantees that approach optimality when the number of vacant positions grows large. The algorithms they develop are nonadaptive: they fix a subset of candidates and an order to conduct the interviews and the order remains unchanged, independent of the outcomes of other interviews. Thus, they establish bounds on the adaptivity gap: a worst-case measure of how poorly non-adaptive algorithms can perform with respect to their adaptive counterparts.

Motivated by hiring pipelines, we study three selection and ordering problems in which applicants for a finite set of positions are interviewed or sent offers. There is a finite time budget for interviewing/sending offers, and every interview/offer is followed by a stochastic realization of discovering the applicant's quality or acceptance decision, leading to computationally challenging problems. In the first problem, we study sequential interviewing and show that a computationally tractable, nonadaptive policy that must make offers immediately after interviewing is near optimal, assuming offers are always accepted. We further show how to use this policy as a subroutine for obtaining a polynomial-time approximation scheme. In the second problem, we assume that applicants have already been interviewed but only accept offers with some probability; we develop a computationally tractable policy that makes offers for the different positions in parallel, which can be used even if positions are heterogeneous, and is near optimal relative to a policy that can make the same total number of offers one by one. In the third problem, we introduce a parsimonious model of overbooking where all offers are sent simultaneously, and a linear penalty is incurred for each acceptance beyond the number of positions; we provide nearly tight bounds on the performance of practically motivated value-ordered policies. All in all, our paper takes a unified approach to three different hiring problems based on linear programming. Our results in the first two problems generalize and improve the existing guarantees in the literature that were between 1/8 and 1/2 to new guarantees that are at least 1−1/e≈63.2%. We also numerically compare three different settings of making offers to candidates (sequentially, in parallel, or simultaneously), providing insight into when a firm should favor each one. Supplemental Material: The online appendices are available at https://doi.org/10.1287/opre.2023.0061.

Keywords: Markets, Platforms, and Revenue Management; hiring; stochastic probing; approximation algorithm; adaptivity gap

1. Introduction

Hiring the right personnel is one of the most important factors in the success of an enterprise. That being said, carrying out an efficient and timely recruitment process can be challenging in practice. Several difficulties arise when hiring, such as (but not limited to) deciding when to carry out the process, dealing with imperfect information, and making operational decisions at the time that the process is being carried out. This last aspect of the recruitment process raises several questions that can be studied through an algorithmic lens.

A typical recruitment process starts with a firm making a call for applications. An application usually consists of a resume and potential complementary materials. Based on this (imperfect) information, the firm decides who is going to be interviewed and in which order are the interviews going to be conducted. Both these aspects are relevant because a recruitment process cannot go on forever. That is, there is not enough time to interview every single applicant, and the firm can choose who to interview next depending on the outcomes of past interviews.

Applicants become candidates once they are interviewed. After all interviews are conducted, the firm sends offers to the candidates it wishes to hire, given a limited set of positions. However, there are many possible ways to send offers to candidates. The first natural approach would be to sequentially send offers to candidates. By this we mean: send an offer, wait for the response of the candidate, and (if there is still a position available) carry on with the next offer. As in the interviewing process, the order in which the offers are sent becomes a relevant decision. A second approach, applicable only to a firm hiring more than one person, is to save time by sending offers in parallel. This means, for each position remaining to fill: send an offer, wait for the response of the candidate, and (if still unfilled) carry on with subsequent offers. The final approach, which may be desirable under a tight timeline or to avoid revealing preferences among the candidates sent offers, is to send all offers simultaneously. However, it runs the risk of hiring more people than positions available, which comes at a cost.

To answer these operational questions and compare the different modes of sending offers, we study three different models of hiring processes that build off existing work.

1.1. First Model: Sequential Interviewing, a.k.a. ProbeTop-k

In the first model, we assume that the firm has to hire up to k people from a pool of n applicants. Each applicant has a random value unknown to the firm carrying out the hiring process. The firm has access to distributional knowledge of these values coming from the applicants' resumes and complementary material submitted. The firm can interview applicants to find out the realization of their values, but there is a limit of T on the number of interviews conducted. The realization of the value of the applicant becomes known to the firm immediately after carrying out the interview. This realization should be interpreted as the applicant's expected value to the firm given the interview (and conditional on them accepting the offer). We treat this value as deterministic, which does not lose generality for a risk-neutral firm that maximizes its expectation. We further assume that realizations from interviews are independent across applicants. After all interviews are carried out, the firm can choose the best k interviewed candidates to be hired, who are assumed to accept their offers with probability 1. The goal of the firm is to maximize the expected sum of values of the hired personnel. This problem is exactly the ProbeTop-k problem, as described in [7].

In this problem, we can further distinguish between different classes of policies. First, we distinguish between adaptive and nonadaptive policies. Adaptive policies can decide the order of the interviews on the fly, choosing who to interview next depending on the outcomes of previous interviews. Nonadaptive policies, in contrast, have to fix an interview order before the process starts, which, although restrictive, is attractive from an ease-of-implementation perspective. We also distinguish between committed and noncommitted policies. Committed policies have to irrevocably decide whether to hire each candidate immediately after interviewing them and discovering their value. Noncommitted policies, in contrast, can carry out all interviews and choose the k highest realized values in hindsight. Using committed policies could be attractive from a practical point of view, as waiting until the end incurs the risk that candidates accept offers from competing firms in the meantime. We are interested in bounds on how costly it is to restrict the firm to use policies that are nonadaptive and committed. The former is quantified in the literature by the widely studied notion of adaptivity gap: the worst-case ratio between the performance of general policies versus algorithms that are restricted to be nonadaptive. Our results will bound the "adaptivity-commitment gap," in which the algorithm is restricted to be both nonadaptive and committed.

1.1.1. Relation to Free-Order Prophets.

The Free-Order Prophet Inequality problem is the special case of ProbeTop-k where T = n and only committed policies are allowed. (When T = n, the constraint of T interviews is not binding, and hence noncommitted policies can just trivially interview all applicants.) Typically, in prophet inequalities, the benchmark can see all applicants' values in advance and simply choose to interview and hire the k overall highest-valued candidates. Such a benchmark is too powerful to compare against in our more general problem if n is much larger than T because the benchmark sees all n realizations, whereas the algorithm can only interview T applicants. This is why in our general ProbeTop-k problem, we compare to an optimal (adaptive, noncommitted) algorithm that is still bound by T interviews that must be decided without any prophetic information, making our comparison different from prophet inequalities.

1.1.2. Relation to Sequential Offering.

In the Sequential Offering model of [19], applicants are assumed to have already been interviewed but have uncertainty about whether they accept an offer. The firm knows, for each candidate, how likely it is that they will accept an offer, and the value they add to the firm, should they accept. The firm has time to send at most T offers and wants to maximize the expected total value of up to k candidates who accept their offers. This setting is closely related to the special case of ProbeTop-k with weighted Bernoulli distributions, where the values take a positive realization with some probability (representing an acceptance) or zero with the remaining probability (representing a rejection). The subtle difference is that an accepted offer cannot be withdrawn by the firm in the Sequential Offering model, whereas in the ProbeTop-k model, the firm can turn down a candidate even if their value turns out to be positive. We will show that our algorithm satisfies properties that makes it admissible for this Sequential Offering problem too and improve on the results of [19].

1.2. Second Model: Parallel Offering

We also study a Parallel Offering model, in which a firm again has to hire people to fill k positions. However, we now allow for heterogeneous positions, where a candidate may have different potential values for different job positions. We assume that all interviews have already been conducted, leaving us with a pool of n desirable candidates. After conducting all interviews the firm learned, for each candidate, how valuable they are for each of the available positions and how likely it is for each candidate to accept an offer for each of the available positions. The firm must now decide how to send offers in T parallel offering rounds. At each round, the firm can send an offer for each of the positions that have not yet been filled by a candidate. When a candidate receives an offer, they can either accept or reject it, with the assumption that they cannot receive an offer for another position if they rejects it (and hence candidates do not try to anticipate offers they might receive later). The goal of the firm is to maximize the expected sum of values of hired candidates. We develop a nonadaptive algorithm that can be computed efficiently and performs competitively in comparison to adaptive and even relaxed sequential algorithms.

This model generalizes a parallel offering model also introduced in [19], which is similar but has k identical instead of heterogeneous positions. Our Parallel Offering model is not only more general, but we also derive stronger performance guarantees.

1.3. Third Model: Simultaneous Offering

Finally, we study the Simultaneous Offering model, again for a firm hiring to fill k positions. As in the Parallel Offering model, the firm has already conducted all interviews, resulting in a pool of n candidates for which it knows how valuable each candidate is to the firm and how likely each candidate is to accept an offer. The firm must decide on a subset of candidates who will receive an offer (all at the same time). This subset can be of any size, so a possible outcome is that more than k candidates accept an offer. If that is the case, the firm pays a penalty for each candidate who accepted an offer beyond the capacity k. This penalty can be thought of as the cost of withdrawing an offer, or the cost of creating a new position in the firm. We analyze the performance of value-ordered policies, which send offers to candidates above a value threshold (regardless of their probability of acceptance). We derive near-optimal approximation guarantees for these policies.

Table 1 contains a comparison of all the models studied/captured in this paper.

Table 1. Comparison Between Models

<table><thead valign="bottom"><tr><th align="left" rowspan="1" colspan="1">Model</th><th align="center" rowspan="1" colspan="1">Action performed</th><th align="center" rowspan="1" colspan="1">Result of action</th><th align="center" rowspan="1" colspan="1">Actions per time step</th><th align="center" rowspan="1" colspan="1">Moment of hiring</th><th align="center" rowspan="1" colspan="1">Bound on total hires</th></tr></thead><tbody valign="top"><tr><td rowspan="1" colspan="1">ProbeTop-<italic>k</italic></td><td align="center" rowspan="1" colspan="1">Interview</td><td rowspan="1" colspan="1">Observe value of candidate</td><td rowspan="1" colspan="1">One</td><td rowspan="1" colspan="1">After last interview</td><td rowspan="1" colspan="1">Hard</td></tr><tr><td rowspan="1" colspan="1">Free-Order Prophets</td><td align="center" rowspan="1" colspan="1">Interview</td><td rowspan="1" colspan="1">Observe value of candidate</td><td rowspan="1" colspan="1">One</td><td rowspan="1" colspan="1">After each interview (irrevocable)</td><td rowspan="1" colspan="1">Hard</td></tr><tr><td rowspan="1" colspan="1">Sequential Offering</td><td align="center" rowspan="1" colspan="1">Send offer</td><td rowspan="1" colspan="1">Observe accept/reject decision</td><td rowspan="1" colspan="1">One</td><td rowspan="1" colspan="1">Upon acceptance of offer</td><td rowspan="1" colspan="1">Hard</td></tr><tr><td rowspan="1" colspan="1">Parallel Offering</td><td align="center" rowspan="1" colspan="1">Send offer(s)</td><td rowspan="1" colspan="1">Observe accept/reject decision(s)</td><td rowspan="1" colspan="1">One per position remaining</td><td rowspan="1" colspan="1">Upon acceptance of offer</td><td rowspan="1" colspan="1">Hard</td></tr><tr><td rowspan="1" colspan="1">Simultaneous Offering</td><td align="center" rowspan="1" colspan="1">Send offer(s)</td><td rowspan="1" colspan="1">Observe accept/reject decision(s)</td><td rowspan="1" colspan="1"><italic>n</italic></td><td rowspan="1" colspan="1">Upon acceptance of offer</td><td rowspan="1" colspan="1">Soft (linear penalty)</td></tr></tbody></table>

1.4. Outline of Results

We will generally say that our algorithm is α-approximate if its expected total value collected is at least α times that of an optimal algorithm, from a larger class. We call <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>α</mi><mo>∈</mo><mo stretchy="false">[</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">]</mo></mrow></math> the approximation factor. Typically, this terminology is used when comparing to the optimal algorithm from the same class. Our results imply lower bounds on the approximation factor α under the typical terminology because we are comparing against a larger class. All our results assume that distributions have finite support and are explicitly input in the form of (value, probability) pairs with binary encoding. All of our algorithms are polynomial-time under this form of input.

For the problem of computing the optimal algorithm within a fixed class, no computational hardness results are known for any of the problems we study (ProbeTop-k, Parallel Offering, Simultaneous Offering), to our knowledge. Nonetheless, our algorithms still have some of the currently best-known approximation factors, which also hold when comparing to a larger class.

1.4.1. Sequential Interviewing a.k.a. ProbeTop-k Problem.

We develop a polynomial-time algorithm that is nonadaptive, committed, and achieves a <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>k</mi></mrow></msup><msup><mrow><mi>k</mi></mrow><mi>k</mi></msup><mo>/</mo><mi>k</mi><mo>!</mo><mo stretchy="false">)</mo></mrow></math> approximation factor relative to an optimal adaptive, noncommitted algorithm (Theorem 1, Section 4.4). The approximation factor of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>k</mi></mrow></msup><msup><mrow><mi>k</mi></mrow><mi>k</mi></msup><mo>/</mo><mi>k</mi><mo>!</mo><mo stretchy="false">)</mo></mrow></math> equals <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>−</mo><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo>/</mo><msqrt><mi>k</mi></msqrt><mo stretchy="false">)</mo></mrow></math> by Stirling's approximation and is always at least <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>−</mo><mn>1</mn><mo>/</mo><mi>e</mi><mo>≈</mo><mn>0.632</mn></mrow></math> (when k = 1). It is tight relative to the linear program (LP) benchmark we compare against (Online Appendix B6).

Our results for this problem, although simple and clean, have broad implications. First, we can combine our algorithm with the work of [7] to obtain a polynomial-time approximation scheme (PTAS) for ProbeTop-k (Corollary 1, Section 4.5). There exist PTAS's for ProbeTop-k restricted to nonadaptive algorithms ([21]) and ProbeTop-k restricted to committed algorithms ([7]), but a PTAS for the general (adaptive, non-committed) ProbeTop-k problem appears unknown, assuming that k is part of the input. Second, the best-known existing guarantee on the adaptivity gap for ProbeTop-k was 1/2 from [4] via an algorithm that is not necessarily polynomial time. We improve the lower bound on the adaptivity gap for ProbeTop-k from 1/2 to <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>−</mo><mn>1</mn><mo>/</mo><mi>e</mi></mrow></math> using a nonadaptive, polynomial-time algorithm, and moreover show asymptotic optimality when the number of positions grows to infinity. Third, our <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>k</mi></mrow></msup><msup><mrow><mi>k</mi></mrow><mi>k</mi></msup><mo>/</mo><mi>k</mi><mo>!</mo><mo stretchy="false">)</mo></mrow></math> -approximation algorithm can be directly applied to the Sequential Offering problem without loss (Corollary 2, Section 4.6), improving the previous-best approximation factor and adaptivity gap of 1/2 ([19]). As with [4], the adaptivity gap shown in [19] was achieved through a nonconstructive approach. Finally, our abstract treatment leads to an algorithm that works in the Free-Order Prophets setting (because it is committed); hence, our results extend to a free-order "prophet inequality" (comparing against a necessarily weaker benchmark) that allows an additional constraint of T on the number of interviews.

1.4.2. Parallel Offering Problem.

For the Parallel Offering model, we develop an algorithm that is nonadaptive and achieves a <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mn>1</mn><mo>/</mo><mi>e</mi><mo stretchy="false">)</mo></mrow></math> approximation factor relative to an optimal (adaptive) algorithm (Theorem 2, Section 5.3). This result also both improves and generalizes existing results, in this case, the 1/8-approximate algorithm of [19] that works in the special case where all positions are identical. It is also tight relative to the LP benchmark, we compare against (Online Appendix C5). We further show that our algorithm obtains at least <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mn>1</mn><mo>/</mo><mi>e</mi><mo stretchy="false">)</mo></mrow></math> times what an optimal algorithm would obtain in the Sequential Offering problem with kT time steps, establishing a lower bound on the value of batching offers (Corollary 3, Section 5.4).

1.4.3. Simultaneous Offering Problem.

We analyze the performance of value-ordered policies, which send offers to all candidates whose value is above a threshold. The idea of having a value threshold is practically motivated and the optimal value-ordered policy can be computed efficiently. We show that with no assumptions on the values of the candidates, value-ordered policies can have arbitrarily poor performance (Example 1, Section 6.1). Consequently, we assume that the valuations of candidates are lower bounded by a parameter <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>τ</mi><mo>∈</mo><mo stretchy="false">(</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> and provide a value-ordered policy that achieves at least a factor <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>α</mi></mrow><mi>k</mi><mi>τ</mi></msubsup></mrow></math> of what an optimal policy could achieve, where <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>α</mi></mrow><mi>k</mi><mi>τ</mi></msubsup></mrow></math> is an increasing function of k and τ (Theorem 3, Section 6.4) that satisfies <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>lim</mi></mrow><mrow><msub><mrow><mi>k</mi></mrow><mo>→</mo></msub><mi>∞</mi></mrow></msub><msubsup><mrow><mi>α</mi></mrow><mi>k</mi><mi>τ</mi></msubsup><mo>=</mo><mn>1</mn></mrow></math> for every <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>τ</mi><mo>∈</mo><mo stretchy="false">(</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> (Corollary 4, Section 6.4). We also provide an instance where no value-ordered policy can achieve a factor higher than <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>β</mi></mrow><mi>k</mi><mi>τ</mi></msubsup></mrow></math> of what an optimal policy could achieve, where <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>β</mi></mrow><mi>k</mi><mi>τ</mi></msubsup></mrow></math> is another increasing function of k and τ (Theorem 4, Section 6.4). We further characterize the region where <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>α</mi></mrow><mi>k</mi><mi>τ</mi></msubsup><mo>=</mo><msubsup><mrow><mi>β</mi></mrow><mi>k</mi><mi>τ</mi></msubsup></mrow></math> (Proposition EC.6, Section D.8). In particular, our bound is tight for all k if <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>τ</mi><mo>≤</mo><mn>1</mn><mo>/</mo><mn>2</mn></mrow></math> .

1.4.4. Numerical Study.

In Online Appendix E, we numerically simulate the three different models of sending offers (sequential, parallel, simultaneous) using the same candidate pool generation process as [19]. We illustrate the improved performances offered by our new policies and compare the performances attainable across the different models, providing insight into when the firm should favor sending offers sequentially, in parallel, or simultaneously. For instance, there is surprisingly little value to gain from an algorithm that sends offers in parallel, as opposed to sending single offers sequentially and being highly adaptive to the number of remaining positions, unless the horizon for making offers is extremely short. For Simultaneous Offering, we demonstrate that value-ordered policies are generally desirable unless there is both a small number of initial positions and a high cost of overage. In that case, it is better to identify the highest-valued "safe" candidates (with a high probability of acceptance) to reduce the variance in the number of accepted offers. We acknowledge that these insights are based on the specific generative model of [19], and they do not necessarily hold in general.

2. Related Work

2.1. Stochastic Probing and Matching

Our work is closely related to the general stochastic probing problem studied in [12] and [13]. These papers study the problem of sequentially probing elements to maximize the sum of the weights of a selected subset. In their setting they consider more general sets of "outer" constraints to be satisfied by the probed elements and "inner" constraints to be satisfied by the selected elements. In this language, ProbeTop-k considers the outer constraint to be the T-uniform matroid and the inner constraint to be the k-uniform matroid. Their work is different from ours in that it only allows the probe to have two outcomes (active or inactive) and active probes must be irrevocably included in the final subset. [4] introduce the multiple-type general stochastic probing problem. In this work, they only work with outer constraints and include the inner constraints by allowing submodular functions instead of modular functions.

In [4] they show that the adaptivity gap is exactly 1/2 for the stochastic probing problem with monotone submodular functions under prefix-closed probing constraints. Their proof is not constructive in the sense that the algorithm for their lower bound requires the optimal decision tree as an input. The best-known nonadaptive algorithm for which is known that it can be computed in polynomial time is due by [14], which achieves a 1/3 approximation for submodular and max-of-sum-of-singletons (XOS) functions under prefix-closed probing constraints.

2.2. PTAS-Type Results

[7] develop PTASs for a class of dynamic programs that includes ProbeTop-1 over general (adaptive, noncommitted) algorithms and ProbeTop-k over committed algorithms. They also provide a <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mi>ε</mi><mo stretchy="false">)</mo><mo>−</mo></mrow></math> approximation for ProbeTop-k over adaptive, noncommitted algorithms whose runtime is polynomial in <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>/</mo><mi>ε</mi></mrow></math> but exponential in k. [21] develop the improved notion of efficient polynomial-time approximation schemes (EPTASs) for several related problems, including ProbeTop-k over nonadaptive algorithms. Their EPTAS works differently when k is small or large. We use the same LP relaxation as theirs for the large k case, although our rounding scheme and analysis are very different. None of these PTAS-type results use nonadaptive, committed policies to approximate the best adaptive, noncommitted policies, as in our paper.

2.3. Prophet Inequalities

Our work has the flavor of Prophet Inequalities in that we are deciding online whether to accept values drawn from known distributions and comparing against a supernatural benchmark. Classical works in Prophet Inequalities ([17], [18]; [20]; [16]; [6]) assume that the order is adversarial or random, whereas we are studying the free-order variant where the order can be decided ([15], [1], [3]). However, because of the constraint of T time steps, as discussed earlier, it is important to emphasize that the benchmark we are comparing against is also bound by T time steps, so we are not comparing against (and it is impossible to compare against) the true prophet. For sequential interviewing, the approximation factor we derive of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>k</mi></mrow></msup><msup><mrow><mi>k</mi></mrow><mi>k</mi></msup><mo>/</mo><mi>k</mi><mo>!</mo><mo stretchy="false">)</mo></mrow></math> has also been established for free-order by [22] and extended in [2] to random-order but neither of these works allows for a constraint of T time steps.

2.4. Simultaneous Offering Model

Our Simultaneous Offering model and in particular the linear penalty cost is motivated by static overbooking models in revenue management ([9], chapter 3). However, our decision is different in that we are selecting a subset of candidates, whereas they are setting a single booking limit (possibly one for each fare class). The simple family of heuristics for which we provide an approximation guarantee also has no analog in overbooking. Our problem also shares many aspects with the one studied in [5], where a subset of customers are sent last-minute offers for a limited number of items. Their model differs from ours in that if more items than available inventory are sold, they only collect value from a random subset of size k, whereas our model collects the value of all acceptances but has to pay a linear penalty.

2.5. Concurrent Work

Parallel to our work, [8] have studied and obtained results for the ProbeTop-k problem. Although both works aim to derive nonadaptive algorithms for the problem, theirs is different from ours in several aspects. First, their models assume that the valuations of the candidates come from independent random variables with either general distributions or continuous distributions, whereas our work focuses on random variables with finite support. Although the bound they obtain for continuous random variables matches the <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>−</mo><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>k</mi></mrow></msup><msup><mrow><mi>k</mi></mrow><mi>k</mi></msup><mo>/</mo><mi>k</mi><mo>!</mo></mrow></math> bound we obtain for finitely-supported random variables, the bound they obtain for general random variables is 1/2. Another aspect that distinguishes our work from [8] is the relaxations used to benchmark the performance of algorithms. We use standard LP relaxations, whereas they introduce a novel benchmark consisting of a simple minimax problem.

3. Problem Formulations and Preliminaries

In this section, we formally state the problems studied in the paper. We first state the ProbeTop-k problem in Section 3.1. We then state the Parallel Offering problem in Section 3.2. We close by stating the Simultaneous Offering problem in Section 3.3.

3.1. ProbeTop-k Problem

In the ProbeTop-k ( <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></math> ) problem, a firm faces the challenge of filling k positions out of a pool of n applicants. Each applicant i has a random, nonnegative value <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>V</mi></mrow><mi>i</mi></msub><mo>∼</mo><msub><mrow><mi>F</mi></mrow><mi>i</mi></msub></mrow></math> , and F<subs>i</subs> is known to the firm. Before the firm hires an applicant, an interview must be conducted. When the firm interviews applicant i, the realization of V<subs>i</subs> becomes known to the firm. The firm can conduct at most T interviews in total and then can choose any k interviewed candidates to be hired. The goal of the firm is to maximize the sum of the values of the hired candidates. An instance of the problem is characterized by a tuple <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>=</mo><mo stretchy="false">(</mo><mi>k</mi><mo>,</mo><mi>T</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>F</mi><mo stretchy="false">)</mo></mrow></math> , where <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mi>T</mi><mo>≤</mo><mi>n</mi></mrow></math> , and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>F</mi><mo>=</mo><msub><mrow><mrow><mo stretchy="false">{</mo><msub><mrow><mi>F</mi></mrow><mi>i</mi></msub><mo stretchy="false">}</mo></mrow></mrow><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></msub></mrow></math> is a collection of probability distribution functions. In this work, we focus on distributions supported on a finite set of non-negative values <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mrow><mo stretchy="false">{</mo><msub><mrow><mi>r</mi></mrow><mi>j</mi></msub><mo stretchy="false">}</mo></mrow></mrow><mrow><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>J</mi><mo stretchy="false">]</mo></mrow></msub></mrow></math> and we use q<subs>ij</subs> to denote <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="double-struck">P</mi><mo stretchy="false">(</mo><msub><mrow><mi>V</mi></mrow><mi>i</mi></msub><mo>=</mo><msub><mrow><mi>r</mi></mrow><mi>j</mi></msub><mo stretchy="false">)</mo></mrow></math> . We use <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> to denote the set of all possible instances for the ProbeTop-k problem. We further use <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow><mi>k</mi></msubsup><mo>⊆</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> to denote the subset of instances where the number of positions is k.

For this problem, we define a policy as a function π that maps the remaining budget of interviews, the set of applicants that have not yet been interviewed and the realization of the values of the candidates that have already been interviewed to a decision of which applicant to interview next. Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi mathvariant="normal">Π</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msup></mrow></math> be the set of all policies for <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></math> . For a policy <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>π</mi><mo>∈</mo><msup><mrow><mi mathvariant="normal">Π</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msup></mrow></math> and an instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> , let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>R</mi></mrow><mi>π</mi></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> be the expected reward of using policy π on the instance in question. For an instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> define <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">OP</mtext><msub><mrow><mi mathvariant="sans-serif">T</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo><mo>≔</mo><msub><mrow><mi>sup</mi></mrow><mrow><mi>π</mi><mo>∈</mo><msup><mrow><mi mathvariant="normal">Π</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msup></mrow></msub><msub><mrow><mi>R</mi></mrow><mi>π</mi></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> as the expected reward of using the best possible policy on instance I. We call a policy <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>π</mi><mo>∈</mo><msup><mrow><mi mathvariant="normal">Π</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msup></mrow></math> an α-approximation if

We distinguish between adaptive and nonadaptive policies. A nonadaptive policy has to decide an order in which to conduct the interviews before the process starts. An adaptive policy, in contrast, conducts the interviews sequentially and can use the outcomes of previous interviews to decide which candidate to interview next. We also distinguish between committed and noncommitted policies. After each interview, committed policies must irrevocably decide whether to hire the candidate or not. Noncommitted policies, in contrast, can interview T applicants and then choose the k highest realizations among them. Among other questions, we are interested in how well can the firm perform when restricted to using nonadaptive policies, committed policies, or both. To quantify this, we are interested in how good an approximation factor can be achieved by restricting the firm to using policies that are both nonadaptive and committed.

3.2. Parallel Offering Problem

The second setting we study in this paper is the Parallel Offering problem ( <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">par</mtext></mrow></math> ). Again, consider the case of a firm that has to hire candidates to fill k positions. Instead of conducting interviews, the firm has to send offers to candidates. The positions of the firm are now not identical, and for each candidate <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> and position <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>k</mi><mo stretchy="false">]</mo></mrow></math> the firm knows v<subs>ij</subs>: the reward collected by the firm if candidate i accepts an offer for position j, and p<subs>ij</subs>: the probability that the candidate i accepts an offer for position j. The firm can carry out at most T offering rounds. At each round, the firm can send an offer for each unfilled position in parallel. Each candidate can receive at most one offer in total. The goal of the firm is to maximize the expectation of the sum of the values of the accepted offers. An instance for this problem is defined by a tuple <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>=</mo><mo stretchy="false">(</mo><mi>k</mi><mo>,</mo><mi>T</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi><mo>,</mo><mi>v</mi><mo stretchy="false">)</mo></mrow></math> , where <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mi>T</mi><mo>≤</mo><mi>n</mi><mo>,</mo><mo /><mi>p</mi><mo>∈</mo><msup><mrow><mo stretchy="false">[</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">]</mo></mrow><mrow><mi>n</mi><mo>×</mo><mi>k</mi></mrow></msup></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>v</mi><mo>∈</mo><msubsup><mrow><mi mathvariant="double-struck">R</mi></mrow><mo>+</mo><mrow><mi>n</mi><mo>×</mo><mi>k</mi></mrow></msubsup></mrow></math> . For this problem, we define a policy as a function π that maps the remaining number of time steps, the remaining set of unfilled positions, and the set of candidates that have not yet received an offer, to an assignment of a subset of not-yet-offered candidates to unfilled positions. Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> be the set of all instances and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi mathvariant="normal">Π</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msup></mrow></math> be the set of all policies for the Parallel Offering model. Again let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>R</mi></mrow><mi>π</mi></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> denote the expected reward of using policy <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>π</mi><mo>∈</mo><msup><mrow><mi mathvariant="normal">Π</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msup></mrow></math> on instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> . Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">OP</mtext><msub><mrow><mi mathvariant="sans-serif">T</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo><mo>≔</mo><msub><mrow><mi>sup</mi></mrow><mrow><mi>π</mi><mo>∈</mo><msup><mrow><mi mathvariant="normal">Π</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msup></mrow></msub><msub><mrow><mi>R</mi></mrow><mi>π</mi></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> be the best possible expected reward that can be obtained from an instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> . We say that a policy <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>π</mi><mo>∈</mo><msup><mrow><mi mathvariant="normal">Π</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msup></mrow></math> is an α-approximation if

For the purpose of analysis, we can imagine that before the offering rounds start, each candidate has already decided which offers they would accept. We allow for these decisions to be correlated across different positions for a single candidate, but we assume independence across candidates.

In this context, we define a nonadaptive policy as follows. For each position, a list of candidates is constructed in a way such that a candidate cannot appear in more than one list and that each list contains no more than T candidates. Each list must also have a specified fixed ordering of its candidates. For each position, offers are sequentially sent to the candidates in their corresponding list, in its corresponding order, until either one of the candidates accepts or the list ends without any acceptance (independent of what happens with the other positions). The algorithm we develop for this problem falls under this definition, and thus we establish a lower bound on how well such nonadaptive policies can perform.

3.3. Simultaneous Offering Problem

The third and last setting we study is the Simultaneous Offering problem ( <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">sim</mtext></mrow></math> ). As in the previous models we study, a firm faces the challenge of filling k positions out of a pool of n candidates. There are two aspects that make this problem different from <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">par</mtext></mrow></math> . First, all offers must be made at the same time, and only once (hence the name Simultaneous Offering). The second aspect making this problem different is that the firm can end up hiring over capacity, but pays a linear cost for each candidate hired beyond k.[1]

Formally, we have the following problem. There are n candidates. For each candidate <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> , we know p<subs>i</subs>: the probability that candidate i accepts an offer if sent, and v<subs>i</subs>: the value obtained if i accepts the offer. The firm must select a subset <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>S</mi><mo>⊆</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> of candidates to send offers to, which has no cardinality constraint. When the subset S is decided, an offer is sent to each of the candidates in S. Each candidate accepts the offer independently with probability p<subs>i</subs>, in which case they add value v<subs>i</subs> to the firm. For each candidate that exceeds the capacity k, the firm incurs a linear cost of c > 0. Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>A</mi><mo>⊆</mo><mi>S</mi></mrow></math> be the (random) subset of candidates that accepted their offers. The reward obtained by the firm is <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><mi>A</mi></mrow></msub><mrow><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub></mrow></mstyle><mo>−</mo><mi>c</mi><mo>·</mo><msup><mrow><mo stretchy="false">[</mo><mo stretchy="false">|</mo><mi>A</mi><mo stretchy="false">|</mo><mo>−</mo><mi>k</mi><mo stretchy="false">]</mo></mrow><mo>+</mo></msup></mrow></math> . By rescaling values v<subs>i</subs> by <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>/</mo><mi>c</mi></mrow></math> , we can assume without loss of generality that c = 1. The rescaled values v<subs>i</subs> can be interpreted as the value that a candidate adds to the firm, relative to the cost of hiring a candidate over capacity.

With this notation, an instance of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">sim</mtext></mrow></math> can be described by a tuple <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>=</mo><mo stretchy="false">(</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi><mo>,</mo><mi>v</mi><mo stretchy="false">)</mo></mrow></math> , where <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mi>n</mi><mo>,</mo><mo /><mi>p</mi><mo>∈</mo><msup><mrow><mo stretchy="false">[</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">]</mo></mrow><mi>n</mi></msup></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>v</mi><mo>∈</mo><msubsup><mrow><mi mathvariant="double-struck">R</mi></mrow><mo>+</mo><mi>n</mi></msubsup></mrow></math> . We define a policy as a function π that maps the problem instance I to a (possibly random) subset of candidates <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>S</mi><mo>⊆</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> . Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> denote the set of all instances and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi mathvariant="normal">Π</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msup></mrow></math> denote the set of all policies for the Simultaneous Offering problem. Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>R</mi></mrow><mi>π</mi></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> denote the expected reward of using policy <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>π</mi><mo>∈</mo><msup><mrow><mi mathvariant="normal">Π</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msup></mrow></math> on instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> . Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">OP</mtext><msub><mrow><mi mathvariant="sans-serif">T</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> be the best possible expected reward that can be obtained from an instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> . We call a policy π an α-approximation if

One thing worth noting is that, although the objective function of the problem is submodular, it is not monotone and can take negative values. Thus, we cannot use general results for approximating maximization problems with submodular objective functions.

4. ProbeTop-k Problem

In this section, we provide our algorithm and analysis for the ProbeTop-k problem, where applicants are sequentially interviewed. We develop a nonadaptive, committed policy that achieves a <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>k</mi></mrow></msup><msup><mrow><mi>k</mi></mrow><mi>k</mi></msup><mo>/</mo><mi>k</mi><mo>!</mo><mo stretchy="false">)</mo></mrow></math> approximation of any (adaptive, noncommitted) policy. The algorithm first solves an LP relaxation that upper bounds the performance of any (adaptive, noncommitted) policy and uses then the LP solution as an input to decide the applicants that will be interviewed, in which order, and whether to hire an interviewed applicant, given their value.

In Section 4.1, we state the LP in question. In Section 4.2, we introduce a simple dependent rounding scheme that will be used in our approximation algorithm. In Sections 4.3 and 4.4, we introduce and analyze our approximation algorithm. In Section 4.5, we explain how to use our approximation algorithm as a subroutine for obtaining a PTAS. In Section 4.6, we treat the special case where values are distributed as weighted Bernoulli random variables and extend our results to the Sequential Offering problem. The analyses in this section, as well as those in Section 5, make use of correlation gap results by [22] and dependent rounding schemes by [10]. We recommend readers who are not familiar with these papers to visit Online Appendix A, which contains a summary of the relevant technical results contained in the previously mentioned papers, before reading the proofs. Throughout this section (except for Section 4.6), we use the word applicant indistinctly from candidate to avoid any confusion, although we had previously distinguished that an applicant becomes a candidate after being interviewed.

4.1. Linear Program

Consider the linear program <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> , which for any instance of ProbeTop-k, upper bounds the performance of all possible policies. Linear programs in this spirit have been used exhaustively in the literature. Indeed, this relaxation is used to approach the same problem in [21], and it consists of a special case of the linear program used in [12]. In <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> , variable y<subs>i</subs> is to be interpreted as the probability that applicant i is interviewed. The variable x<subs>ij</subs> is to be interpreted as the probability that i is hired when V<subs>i</subs> = r<subs>j</subs>.

<math display="block" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext>s</mtext><mo>.</mo><mtext>t</mtext><mo>.</mo><mo /><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>≤</mo><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mtext /><mo>∀</mo><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo><mo>,</mo><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>J</mi><mo stretchy="false">]</mo></mrow></math> (1)

We first show that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> upper bounds the optimal (adaptive, noncommitted) algorithm.

Lemma 1.

For any instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> , we have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo><mo>≥</mo><mtext mathvariant="sans-serif">OP</mtext><msub><mrow><mi mathvariant="sans-serif">T</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> .

Although this result is not new, we provide a proof of the claim in Online Appendix B1 for completeness.

The following lemma establishes a convenient fact about the basic feasible solutions of the LP. This will let us develop a simple rounding scheme for selecting applicants to be interviewed.

Lemma 2.

Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> and let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>y</mi><mo>=</mo><msub><mrow><mrow><mo stretchy="false">(</mo><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></mrow><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></msub><mo>,</mo><mi>x</mi><mo>=</mo><msub><mrow><mrow><mo stretchy="false">(</mo><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo stretchy="false">)</mo></mrow></mrow><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo><mo>,</mo><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>J</mi><mo stretchy="false">]</mo></mrow></msub></mrow></math> be a basic feasible solution of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> . Then y has at most two noninteger components. If it has two noninteger components, they sum to one.

The proof of this lemma is deferred to Online Appendix B2.

4.2. Dependent Rounding

We develop a simple dependent rounding scheme (which we call <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext>DR</mtext></mrow></math> for short) that will be used as a subroutine of our approximation algorithm. <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext>DR</mtext></mrow></math> receives an optimal solution <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>y</mi><mo>=</mo><msub><mrow><mo stretchy="false">(</mo><mi>y</mi><mo stretchy="false">)</mo></mrow><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></msub></mrow></math> of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> as an input and returns a (possibly random) vector <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>Y</mi><mo>∈</mo><msup><mrow><mo stretchy="false">{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">}</mo></mrow><mi>n</mi></msup></mrow></math> . <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext>DR</mtext></mrow></math> works differently depending on the number of fractional components of the optimal solution y. In any case, for all i such that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub><mo>∈</mo><mo stretchy="false">{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">}</mo></mrow></math> , it sets Y<subs>i</subs> = y<subs>i</subs> with probability 1. If y is integral, then Y is deterministic. If there is exactly one fractional component <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>′</mo></mrow></math> , then it sets <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>Y</mi></mrow><mrow><mi>i</mi><mo>′</mo></mrow></msub><mo>=</mo><mn>1</mn></mrow></math> with probability <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>y</mi></mrow><mrow><mi>i</mi><mo>′</mo></mrow></msub></mrow></math> (and it sets <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>Y</mi></mrow><mrow><mi>i</mi><mo>′</mo></mrow></msub><mo>=</mo><mn>0</mn></mrow></math> otherwise). If there are exactly two fractional components i<subs>1</subs> and i<subs>2</subs>, then it sets <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>Y</mi></mrow><mrow><msub><mrow><mi>i</mi></mrow><mn>1</mn></msub></mrow></msub><mo>=</mo><mn>1</mn><mo>,</mo><msub><mrow><mi>Y</mi></mrow><mrow><msub><mrow><mi>i</mi></mrow><mn>2</mn></msub></mrow></msub><mo>=</mo><mn>0</mn></mrow></math> with probability <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>y</mi></mrow><mrow><msub><mrow><mi>i</mi></mrow><mn>1</mn></msub></mrow></msub></mrow></math> and sets <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>Y</mi></mrow><mrow><msub><mrow><mi>i</mi></mrow><mn>1</mn></msub></mrow></msub><mo>=</mo><mn>0</mn><mo>,</mo><msub><mrow><mi>Y</mi></mrow><mrow><msub><mrow><mi>i</mi></mrow><mn>2</mn></msub></mrow></msub><mo>=</mo><mn>1</mn></mrow></math> with probability <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>−</mo><msub><mrow><mi>y</mi></mrow><mrow><msub><mrow><mi>i</mi></mrow><mn>1</mn></msub></mrow></msub><mo>=</mo><msub><mrow><mi>y</mi></mrow><mrow><msub><mrow><mi>i</mi></mrow><mn>2</mn></msub></mrow></msub></mrow></math> . It is easy to see that the output of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext>DR</mtext></mrow></math> satisfies the following two properties: (P1) <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="double-struck">E</mi><mo stretchy="false">(</mo><msub><mrow><mi>Y</mi></mrow><mi>i</mi></msub><mo stretchy="false">)</mo><mo>=</mo><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub></mrow></math> for every <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> and (P2) <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></msub><mrow><msub><mrow><mi>Y</mi></mrow><mi>i</mi></msub></mrow></mstyle><mo>≤</mo><mi>T</mi></mrow></math> with probability 1.

4.3. Approximation Algorithm

We propose the following algorithm for the ProbeTop-k problem, which we call <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> . Given an instance, we first solve <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> . Let x, y be an optimal solution. Define

<math display="block" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub><mo>=</mo><mfrac><mrow><mstyle displaystyle="false"><msubsup><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>J</mi></msubsup><mrow><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow></mstyle></mrow><mrow><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub></mrow></mfrac><mo>,</mo><mo /><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub><mo>=</mo><mfrac><mrow><mstyle displaystyle="false"><msubsup><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>J</mi></msubsup><mrow><msub><mrow><mi>r</mi></mrow><mi>j</mi></msub></mrow></mstyle><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow><mrow><mstyle displaystyle="false"><msubsup><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>J</mi></msubsup><mrow><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow></mstyle></mrow></mfrac><mo>.</mo></mrow></math> (4)

If any of the denominators are zero, then define these values as zero.[2] For reasons that will soon become clear, p<subs>i</subs> is to be interpreted as the probability that we accept applicant i given that they get interviewed, and v<subs>i</subs> is to be interpreted as the expected value of i given that they get hired. Assume that after solving the LP, we relabel the applicants so that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>v</mi></mrow><mn>1</mn></msub><mo>≥</mo><msub><mrow><mi>v</mi></mrow><mn>2</mn></msub><mo>≥</mo><mo>⋯</mo><mo>≥</mo><msub><mrow><mi>v</mi></mrow><mi>n</mi></msub></mrow></math> .

The algorithm first chooses which applicant to interview and the order in which the interviews are going to take place. For the first task, we use the dependent rounding DR just introduced. Specifically, we feed vector y as an input to DR and obtain binary random variables <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mrow><mo stretchy="false">{</mo><msub><mrow><mi>Y</mi></mrow><mi>i</mi></msub><mo stretchy="false">}</mo></mrow></mrow><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></msub></mrow></math> . The algorithm will choose to interview applicants i with Y <subs>i</subs> = 1. For the second task, the algorithm will always interview applicants in decreasing order of v<subs>i</subs>. On interviewing applicant i and observing their value r<subs>j</subs>, the algorithm hires i with probability <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>/</mo><mo stretchy="false">(</mo><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo stretchy="false">)</mo></mrow></math> .

4.4. Analysis of ALGptk

To analyze the algorithm, let Y<subs>i</subs> be the indicator that applicant i is included in the list of applicants to receive an interview. Let Q<subs>ij</subs> be the indicator of V<subs>i</subs> = r<subs>j</subs>. Let P<subs>i</subs> be the indicator that applicant i would be hired if they were interviewed while still having unfilled positions. We colloquially refer to this event as i "making the cut." We have

Define <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>Z</mi></mrow><mi>i</mi></msub><mo>=</mo><msub><mrow><mi>Y</mi></mrow><mi>i</mi></msub><mo>·</mo><msub><mrow><mi>P</mi></mrow><mi>i</mi></msub></mrow></math> as the indicator that i is included in the list of applicants to receive an interview and that i makes the cut. Note that Y<subs>i</subs> is independent of P<subs>i</subs>. Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>N</mi></mrow><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>=</mo><mstyle displaystyle="false"><msubsup><mo>∑</mo><mrow><mi mathvariant="script">ℓ</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msubsup><mrow><msub><mrow><mi>Z</mi></mrow><mi mathvariant="script">ℓ</mi></msub></mrow></mstyle></mrow></math> be the number of applicants that are interviewed before applicant i that would be hired if there are still positions available. We can therefore write the (random) reward of our algorithm as <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mi>i</mi></msub><mrow><msub><mrow><mi>V</mi></mrow><mi>i</mi></msub></mrow></mstyle><mi mathvariant="normal" /><mo stretchy="false">{</mo><msub><mrow><mi>N</mi></mrow><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msub><mo><</mo><mi>k</mi><mo stretchy="false">}</mo><msub><mrow><mi>Z</mi></mrow><mi>i</mi></msub></mrow></math> . The following lemma allows us to write the expected reward of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> in a way that will allow us to relate it to weighted rank functions of k-uniform matroids.

Lemma 3.

For any <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> , we have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>R</mi></mrow><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo><mo>=</mo><mstyle displaystyle="false"><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mrow><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub></mrow></mstyle><mi mathvariant="double-struck">E</mi><mo stretchy="false">(</mo><mi mathvariant="normal" /><mo stretchy="false">{</mo><msub><mrow><mi>N</mi></mrow><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msub><mo><</mo><mi>k</mi><mo stretchy="false">}</mo><msub><mrow><mi>Z</mi></mrow><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></math> .

The proof of this lemma is deferred to Online Appendix B3. Because the applicants are labeled such that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>v</mi></mrow><mn>1</mn></msub><mo>≥</mo><msub><mrow><mi>v</mi></mrow><mn>2</mn></msub><mo>≥</mo><mo>⋯</mo><mo>≥</mo><msub><mrow><mi>v</mi></mrow><mi>n</mi></msub></mrow></math> , Lemma 3 implies that our algorithm has the same expected reward as an algorithm that would first sample <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>Z</mi></mrow><mi>i</mi></msub><mo>=</mo><msub><mrow><mi>Y</mi></mrow><mi>i</mi></msub><msub><mrow><mi>P</mi></mrow><mi>i</mi></msub></mrow></math> for all applicants and then collect the k highest values v<subs>i</subs> among those applicants with Z<subs>i</subs> = 1. This interpretation is only possible because <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> is committed. The same expressions can be derived for an algorithm that instead of sampling Y<subs>i</subs> using DR, samples <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mover accent="true"><mi>Y</mi><mo stretchy="false">˜</mo></mover></mrow><mi>i</mi></msub></mrow></math> with the same marginal probabilities as Y<subs>i</subs>, but independently. These expressions are useful for showing that our algorithm outperforms a hypothetical algorithm that decides to interview each applicant i using the independent indicators <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mover accent="true"><mi>Y</mi><mo stretchy="false">˜</mo></mover></mrow><mi>i</mi></msub></mrow></math> instead of the correlated indicators Y<subs>i</subs>, potentially interviewing T + 1 applicants. The correlation induced by the constraint of T interviews on the actual algorithm only works in our favor.

Lemma 4.

Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>y</mi><mo>=</mo><msub><mrow><mrow><mo stretchy="false">(</mo><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></mrow><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></msub><mo>,</mo><mi>x</mi><mo>=</mo><msub><mrow><mrow><mo stretchy="false">(</mo><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo stretchy="false">)</mo></mrow></mrow><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo><mo>,</mo><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>J</mi><mo stretchy="false">]</mo></mrow></msub></mrow></math> be a basic feasible solution of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> with two fractional components i <subs>1</subs> and i <subs>2</subs>. Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mover accent="true"><mi>Y</mi><mo stretchy="false">˜</mo></mover></mrow><mi>i</mi></msub></mrow></math> be independent Bernoulli random variables with mean y<subs>i</subs>. Define <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mover accent="true"><mrow><msub><mrow><mi>Z</mi></mrow><mi>i</mi></msub></mrow><mo stretchy="true">˜</mo></mover><mo>=</mo><msub><mrow><mi>P</mi></mrow><mi>i</mi></msub><msub><mrow><mover accent="true"><mi>Y</mi><mo stretchy="false">˜</mo></mover></mrow><mi>i</mi></msub></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mover accent="true"><mi>N</mi><mo stretchy="false">˜</mo></mover></mrow><mi>i</mi></msub><mo>=</mo><mtext>min</mtext><mrow><mo stretchy="false">{</mo><mrow><mi>k</mi><mo>,</mo><mstyle displaystyle="false"><msubsup><mo>∑</mo><mrow><mi mathvariant="script">ℓ</mi><mo>=</mo><mn>1</mn></mrow><mi>i</mi></msubsup><mrow><msub><mrow><mover accent="true"><mi>Z</mi><mo stretchy="false">˜</mo></mover></mrow><mi mathvariant="script">ℓ</mi></msub></mrow></mstyle></mrow><mo stretchy="false">}</mo></mrow></mrow></math> . Then

<math display="block" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mrow><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub></mrow></mstyle><mi mathvariant="double-struck">E</mi><mrow><mo>(</mo><mrow><msub><mrow><mi>Z</mi></mrow><mi>i</mi></msub><mi mathvariant="normal" /><mo>{</mo><msub><mrow><mi>N</mi></mrow><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msub><mo><</mo><mi>k</mi><mo>}</mo></mrow><mo>)</mo></mrow><mo>≥</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mrow><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub></mrow></mstyle><mi mathvariant="double-struck">E</mi><mrow><mo>(</mo><mrow><msub><mrow><mover accent="true"><mi>Z</mi><mo stretchy="false">˜</mo></mover></mrow><mi>i</mi></msub><mi mathvariant="normal" /><mo>{</mo><msub><mrow><mover accent="true"><mi>N</mi><mo stretchy="false">˜</mo></mover></mrow><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msub><mo><</mo><mi>k</mi><mo>}</mo></mrow><mo>)</mo></mrow><mo>.</mo></mrow></math> (5)

The proof of this lemma is deferred to Online Appendix B4.

To conclude our analysis, we relate the performance of the hypothetical algorithm (with independent indicators) and the objective function of the LP, through the weighted rank function of k-uniform matroids. For a set <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>S</mi><mo>⊆</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> we define the weighted rank function for the k-uniform matroid with weights v as <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi>v</mi></mrow><mo>*</mo></msup><mo stretchy="false">(</mo><mi>S</mi><mo stretchy="false">)</mo><mo>=</mo><msub><mrow><mtext>max</mtext></mrow><mrow><mi>R</mi><mo>⊆</mo><mo stretchy="false">[</mo><mi>S</mi><mo stretchy="false">]</mo><mo>,</mo><mtext /><mo stretchy="false">|</mo><mi>R</mi><mo stretchy="false">|</mo><mo>≤</mo><mi>k</mi></mrow></msub><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><mi>R</mi></mrow></msub><mrow><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub></mrow></mstyle></mrow></math> .

Both the reward of the hypothetical independent algorithm and the objective of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> can be expressed as expectations of weighted rank functions of k-uniform matroids. We use this together with the correlation gap results by [22] to show the main result of this section.

Theorem 1.

For any instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow><mi>k</mi></msubsup></mrow></math> , we have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>R</mi></mrow><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo><mo>≥</mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><mfrac><mrow><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>k</mi></mrow></msup><msup><mrow><mi>k</mi></mrow><mi>k</mi></msup></mrow><mrow><mi>k</mi><mo>!</mo></mrow></mfrac></mrow><mo>)</mo></mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> .

The proof of this theorem is deferred to Online Appendix B5. In Online Appendix B6, we show that the guarantee that our algorithm attains is tight.

It is worth noting that this algorithm can be de-randomized. Indeed, the algorithm will randomize between at most two fixed orders, so both of them can be evaluated and the best among them can be selected. Thus, we have a deterministic, nonadaptive, committed algorithm whose expected reward will be at least a <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>k</mi></mrow></msup><msup><mrow><mi>k</mi></mrow><mi>k</mi></msup><mo>/</mo><mi>k</mi><mo>!</mo><mo stretchy="false">)</mo></mrow></math> factor of the expected reward of the optimal algorithm. Because our algorithm is nonadaptive and committed, it establishes a lower bound on how good an approximation factor can be achieved by restricting to these classes of policies.

4.5. PTAS for ProbeTop-k

We now explain how to combine <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> with the (adaptive, noncommitted) approximation algorithm proposed by [7] to obtain a PTAS for ProbeTop-k. We know there is a <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mi>ε</mi><mo stretchy="false">)</mo></mrow></math> -approximation algorithm for ProbeTop-k whose runtime is exponential in k ([7], theorem 4.2). The idea behind the combined PTAS is that for k large enough, <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> obtains an approximation factor better than <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>−</mo><mi>ε</mi></mrow></math> , so for small values of k we would run the algorithm by [7], and for large values of k we would run our <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> . This essentially allows us to treat k as a constant in the algorithm of [7]. Our algorithm has runtime polynomial in k, but it is without loss to assume that k is input in unary because if k (capacity) exceeds the number of given distributions (applicants/candidates), then the problem is trivial.

Specifically, for <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>ε</mi><mo>∈</mo><mo stretchy="false">(</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>/</mo><mi>e</mi><mo stretchy="false">)</mo></mrow></math> , let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi>k</mi></mrow><mo>*</mo></msup></mrow></math> be the smallest <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>≥</mo><mn>1</mn></mrow></math> such that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>ε</mi><mo>></mo><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>k</mi></mrow></msup><msup><mrow><mi>k</mi></mrow><mi>k</mi></msup><mo>/</mo><mo stretchy="false">(</mo><mi>k</mi><mo>!</mo><mo stretchy="false">)</mo></mrow></math> .[3] For <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo><</mo><msup><mrow><mi>k</mi></mrow><mo>*</mo></msup></mrow></math> , the PTAS will run the algorithm by [7] to obtain a <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>−</mo><mi>ε</mi></mrow></math> approximation in polynomial time because <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi>k</mi></mrow><mo>*</mo></msup></mrow></math> is a constant. For <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>≥</mo><msup><mrow><mi>k</mi></mrow><mo>*</mo></msup></mrow></math> , the PTAS will run <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> and obtain, in polynomial time, an approximation factor of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>−</mo><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>k</mi></mrow></msup><msup><mrow><mi>k</mi></mrow><mi>k</mi></msup><mo>/</mo><mo stretchy="false">(</mo><mi>k</mi><mo>!</mo><mo stretchy="false">)</mo><mo>></mo><mn>1</mn><mo>−</mo><mi>ε</mi></mrow></math> .

Corollary 1.

There is a PTAS for ProbeTop-k.

4.6. Weighted Bernoulli Values and the Sequential Offering Problem

ProbeTop-k is closely related to the Sequential Offering problem ( <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">seq</mtext></mrow></math> ) studied by [19]. In this problem, the hiring firm has already interviewed n candidates and must decide the order in which to send offers to them. Each candidate i has a probability q<subs>i</subs> of accepting an offer and adds a value r<subs>i</subs> to the firm if they accept an offer. The firm can hire at most k candidates and send at most T offers in total. This model is closely related to ProbeTop-k when considering the special case where the value of applicant i takes value r<subs>i</subs> with probability q<subs>i</subs> (representing acceptance of an offer), and zero with probability <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>−</mo><msub><mrow><mi>q</mi></mrow><mi>i</mi></msub></mrow></math> (representing rejection of an offer). The subtlety making <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></math> different from <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">seq</mtext></mrow></math> is that policies for <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></math> can reject an applicant i even if they had a realization to value r<subs>i</subs>, which is not allowed in <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">seq</mtext></mrow></math> . We show, however, that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> can be forced to hire any applicant when their realized value is r<subs>i</subs> without loss, therefore making it an admissible algorithm for the Sequential Offering model with the same guarantee.

Indeed, we can rewrite <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> for this special case as

where x<subs>i</subs> is to be interpreted as the probability of hiring applicant i and V<subs>i</subs> = r<subs>i</subs> (we can omit the variable corresponding to V<subs>i</subs> = 0 because it has a zero coefficient in the objective). The following lemma will let us restrict <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> to be admissible for the Sequential Offering problem.

Lemma 5.

For weighted Bernoulli instances, <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> has an optimal solution with <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>x</mi></mrow><mi>i</mi></msub><mo>=</mo><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub><msub><mrow><mi>q</mi></mrow><mi>i</mi></msub><mo /><mo>∀</mo><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> .

The proof of this lemma is deferred to Online Appendix B7.

Recall that after interviewing i, <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> will hire them with probability <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>x</mi></mrow><mi>i</mi></msub><mo>/</mo><mo stretchy="false">(</mo><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub><msub><mrow><mi>q</mi></mrow><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></math> . Therefore, if we restrict to solutions with <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>x</mi></mrow><mi>i</mi></msub><mo>=</mo><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub><msub><mrow><mi>q</mi></mrow><mi>i</mi></msub></mrow></math> , then <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> will hire applicant i with probability 1 if V<subs>i</subs> = r<subs>i</subs>, making it admissible for the Sequential Offering problem.

For this specific family of instances, Equations (4) yield

We can use these expressions to further simplify the LP by removing variables x<subs>i</subs> and express it in terms of p<subs>i</subs> and v<subs>i</subs>, leading to <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">seq</mtext></mrow></msub></mrow></math> .

Being consistent with the previously introduced notation, let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">seq</mtext></mrow></msub></mrow></math> be the set of all instances for the Sequential Offering problem. Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">seq</mtext></mrow><mi>k</mi></msubsup></mrow></math> be the set of all instances of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">seq</mtext></mrow></math> that have exactly k positions to fill. Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">seq</mtext></mrow></msub></mrow></math> be the modified version of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> that, when faced with instances of weighted Bernoulli random variables, modifies the solution of the LP as in Lemma 5 such that the algorithm is admissible for <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">seq</mtext></mrow></math> . We then have the following corollary of Theorem 1.

Corollary 2.

For any instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">seq</mtext></mrow><mi>k</mi></msubsup></mrow></math> , we have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>R</mi></mrow><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">seq</mtext></mrow></msub></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo><mo>≥</mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><mfrac><mrow><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>k</mi></mrow></msup><msup><mrow><mi>k</mi></mrow><mi>k</mi></msup></mrow><mrow><mi>k</mi><mo>!</mo></mrow></mfrac></mrow><mo>)</mo></mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">seq</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> .

5. Parallel Offering

We turn to the Parallel Offering model defined in Section 3.2. We provide an algorithm that achieves a <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mn>1</mn><mo>/</mo><mi>e</mi><mo stretchy="false">)</mo></mrow></math> approximation of the optimal policy. The algorithm works by solving a LP relaxation and rounding its solution to decide who to offer which position, and in which order.

In Section 5.1, we introduce the LP in question. In Section 5.2, we present our algorithm, and in Section 5.3, we provide its analysis. In Section 5.4, we study the special case with identical positions introduced by [19] and establish a connection between the Parallel and Sequential Offering problems.

5.1. Linear Program

For an instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> , we introduce <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> , with LP variables y<subs>ij</subs> for <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>k</mi><mo stretchy="false">]</mo></mrow></math> . Variable y<subs>ij</subs> is to be interpreted as the probability that candidate i receives an offer for position j. As with <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">ptk</mtext></mrow></msub></mrow></math> , this LP only enforces that the problem's constraints are satisfied in expectation.

<math display="block" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext>s</mtext><mo>.</mo><mtext>t</mtext><mo>.</mo><mo /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mrow><msub><mrow><mi>y</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow></mstyle><mo>≤</mo><mi>T</mi><mo>∀</mo><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>k</mi><mo stretchy="false">]</mo></mrow></math> (6)

<math display="block" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>k</mi></munderover><mrow><msub><mrow><mi>y</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow></mstyle><mo>≤</mo><mn>1</mn><mo>∀</mo><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> (8)

We start by formally proving that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> upper-bounds the expected reward of any algorithm.

Lemma 6.

For any instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> , we have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo><mo>≥</mo><mtext mathvariant="sans-serif">OP</mtext><msub><mrow><mi mathvariant="sans-serif">T</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> .

The proof of this lemma is deferred to Online Appendix C1.

5.2. Approximation Algorithm

We now present our algorithm for the Parallel Offering model, which we refer to as <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> . The algorithm first solves <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> to produce an optimal solution y. With the solution at hand, the algorithm will round it to obtain a random binary matrix <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>Y</mi><mo>=</mo><msub><mrow><mrow><mo stretchy="false">(</mo><msub><mrow><mi>Y</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo stretchy="false">)</mo></mrow></mrow><mrow><mo stretchy="false">(</mo><mi>i</mi><mo>,</mo><mi>j</mi><mo stretchy="false">)</mo><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo><mo>×</mo><mo stretchy="false">[</mo><mi>k</mi><mo stretchy="false">]</mo></mrow></msub></mrow></math> . To round our solution here, we use the dependent rounding scheme developed by [10] that is described in Online Appendix A2. Specifically, the nodes of one side of the bipartite graph are the n applicants, and the nodes of the other side are the k positions. The weight of each edge <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>i</mi><mo>,</mo><mi>j</mi><mo stretchy="false">)</mo><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo><mo>×</mo><mo stretchy="false">[</mo><mi>k</mi><mo stretchy="false">]</mo></mrow></math> is the fractional value of y<subs>ij</subs> from the optimal solution of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> . After the solution is rounded, the algorithm uses the rounded solution to make a sequential offering list for each position so that candidate i is included in the list for position j if Y<subs>ij</subs> = 1. The properties of the dependent rounding scheme by [10] combined with the constraints of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> will ensure that (a) each list has at most T candidates, and (b) each candidate is included in at most one list. After the lists are formed, all lists are run in parallel, and the order in which candidates i for each position j are sent offers is in decreasing order of v<subs>ij</subs>.

5.3. Analysis of ALGpar

For the analysis, let L<subs>j</subs> denote the expected value of the candidate that ends up being hired for position j. Define <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>Z</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>=</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><msub><mrow><mi>Y</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mover accent="true"><mi>Z</mi><mo stretchy="false">˜</mo></mover></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>=</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><msub><mrow><mover accent="true"><mi>Y</mi><mo stretchy="false">˜</mo></mover></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow></math> , where <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mrow><mo stretchy="false">(</mo><msub><mrow><mover accent="true"><mi>Y</mi><mo stretchy="false">˜</mo></mover></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo stretchy="false">)</mo></mrow></mrow><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo><mo>,</mo><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>k</mi><mo stretchy="false">]</mo></mrow></msub></mrow></math> are independent Bernoulli random variables with <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="double-struck">E</mi><mo stretchy="false">(</mo><msub><mrow><mover accent="true"><mi>Y</mi><mo stretchy="false">˜</mo></mover></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo stretchy="false">)</mo><mo>=</mo><msub><mrow><mi>y</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow></math> . Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>D</mi></mrow><mi>j</mi></msub><mo>=</mo><mo stretchy="false">{</mo><mi>i</mi><mo>:</mo><msub><mrow><mi>Z</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>=</mo><mn>1</mn><mo stretchy="false">}</mo></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mover accent="true"><mi>D</mi><mo stretchy="false">˜</mo></mover></mrow><mi>j</mi></msub><mo>=</mo><mo stretchy="false">{</mo><mi>i</mi><mo>:</mo><msub><mrow><mover accent="true"><mi>Z</mi><mo stretchy="false">˜</mo></mover></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>=</mo><mn>1</mn><mo stretchy="false">}</mo></mrow></math> . Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>v</mi></mrow><mi>j</mi><mo>*</mo></msubsup><mo stretchy="false">(</mo><mi>S</mi><mo stretchy="false">)</mo><mo>=</mo><msub><mrow><mtext>max</mtext></mrow><mrow><mi>i</mi><mo>∈</mo><mi>S</mi></mrow></msub><mo /><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow></math> . It is clear to see that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>L</mi></mrow><mi>j</mi></msub><mo>=</mo><mi mathvariant="double-struck">E</mi><mo stretchy="false">(</mo><msubsup><mrow><mi>v</mi></mrow><mi>j</mi><mo>*</mo></msubsup><mo stretchy="false">(</mo><mi>D</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow></math> .

The first step for showing the guarantee of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> is to show that the reward collected by a list is not lower than what we would collect if we rounded each component of y independently. This is a consequence of the negative correlation property (P3) of the dependent rounding scheme by [10]. This result is formalized in the following lemma.

Lemma 7.

For all <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>k</mi><mo stretchy="false">]</mo></mrow></math> , we have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="double-struck">E</mi><mo stretchy="false">(</mo><msubsup><mrow><mi>v</mi></mrow><mi>j</mi><mo>*</mo></msubsup><mo stretchy="false">(</mo><mi>D</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo>≥</mo><mi mathvariant="double-struck">E</mi><mo stretchy="false">(</mo><msubsup><mrow><mi>v</mi></mrow><mi>j</mi><mo>*</mo></msubsup><mo stretchy="false">(</mo><mover accent="true"><mi>D</mi><mo stretchy="false">˜</mo></mover><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow></math> .

The proof of this lemma is deferred to Online Appendix C2. Lemma 7 analyzes each position in isolation, even if two or more positions are identical. In fact, our proof does not appear to extend to multiple identical positions. Indeed, our proof only makes use of properties (P1) and (P3) from the dependent rounding scheme of [10]. We prove in Online Appendix C3 that only using these properties is insufficient for proving an analogue of Lemma 7 for multiple positions.

Continuing with the main result, let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>L</mi></mrow><mi>j</mi><mo>*</mo></msubsup></mrow></math> denote <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mrow><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow></mstyle><msub><mrow><mi>y</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><msub><mrow><mi>p</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow></math> , so that the objective function of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> can be expressed as <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msubsup><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>k</mi></msubsup><mrow><msubsup><mrow><mi>L</mi></mrow><mi>j</mi><mo>*</mo></msubsup></mrow></mstyle></mrow></math> . The following lemma helps establish the desired bound for each separate list; at most, one candidate is hired from each list. Both the correlation gap results and the rounding scheme mentioned in Online Appendix A are used in our analysis.

Lemma 8.

For all <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>k</mi><mo stretchy="false">]</mo></mrow></math> , we have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="double-struck">E</mi><mo stretchy="false">(</mo><msubsup><mrow><mi>v</mi></mrow><mi>j</mi><mo>*</mo></msubsup><mo stretchy="false">(</mo><mover accent="true"><mi>D</mi><mo stretchy="false">˜</mo></mover><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo>≥</mo><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mn>1</mn><mo>/</mo><mi>e</mi><mo stretchy="false">)</mo><msubsup><mrow><mi>L</mi></mrow><mi>j</mi><mo>*</mo></msubsup></mrow></math> .

The proof of this lemma is deferred to Online Appendix C4.

By combining Lemmas 7 and 8 we obtain the main result of the section.

Theorem 2.

For any instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> , we have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>R</mi></mrow><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo><mo>≥</mo><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mn>1</mn><mo>/</mo><mi>e</mi><mo stretchy="false">)</mo><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> .

In Online Appendix C5, we establish that the bound achieved by our algorithm is tight.

5.4. Identical Positions and the Cost of Batching

We turn to the special case where all positions are identical (i.e., <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>=</mo><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>p</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>=</mo><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></math> for all <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>k</mi><mo stretchy="false">]</mo></mrow></math> ). For this case, we can obtain a connection between the Sequential Offering model and the Parallel Offering model through their respective LPs.

Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow><mo>=</mo></msubsup><mo>⊆</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></math> be the set of instances of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">par</mtext></mrow></math> in which all positions are identical. For a given instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow><mo>=</mo></msubsup></mrow></math> , construct <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>′</mo><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">seq</mtext></mrow></msub></mrow></math> with the same candidates as in I, but with a budget of kT sequential offers (instead of T parallel offering rounds). We obtain the following lemma.

Lemma 9.

For any <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow><mo>=</mo></msubsup></mrow></math> , we have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo><mo>=</mo><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">seq</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo>′</mo><mo stretchy="false">)</mo></mrow></math> .

The proof of this lemma is deferred to Online Appendix C6.

Lemma 9 implies the following corollary, which we refer to as the cost of batching.

Corollary 3.

For any <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow><mo>=</mo></msubsup></mrow></math> , we have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>R</mi></mrow><mrow><mtext mathvariant="sans-serif">AL</mtext><msub><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">par</mtext></mrow></msub></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo><mo>≥</mo><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mn>1</mn><mo>/</mo><mi>e</mi><mo stretchy="false">)</mo><mtext mathvariant="sans-serif">OP</mtext><msub><mrow><mi mathvariant="sans-serif">T</mi></mrow><mrow><mtext mathvariant="monospace">seq</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo>′</mo><mo stretchy="false">)</mo></mrow></math> .

This corollary helps us understand how costly it can be to send offers in batches instead of one by one like in the Sequential Offering problem. By reducing to T parallel offering rounds instead of kT sequential offering rounds, we know that we cannot be worse by more than a factor of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mn>1</mn><mo>/</mo><mi>e</mi><mo stretchy="false">)</mo></mrow></math> .

6. Simultaneous Offering

In this section, we study the Simultaneous Offering problem described in Section 3.3. We are interested in a class of "value-ordered" policies. We develop such a policy that, when faced with instances where all values of candidates are lower-bounded by some <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>τ</mi><mo>∈</mo><mo stretchy="false">(</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> , achieves an <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>α</mi></mrow><mi>k</mi><mi>τ</mi></msubsup></mrow></math> -approximation, where <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>α</mi></mrow><mi>k</mi><mi>τ</mi></msubsup></mrow></math> is an increasing function that maps the number of positions <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>∈</mo><mi mathvariant="double-struck">N</mi></mrow></math> and the lower bound τ to a real number between zero and one. Our algorithm first solves an LP relaxation. It then uses a modification of the optimal solution to decide which candidates will receive offers.

In Section 6.1, we define the class of value-ordered policies, which we show can perform arbitrarily poorly without the assumption of the lower bound τ. In Section 6.2, we introduce an LP relaxation that is used in our algorithm. In Sections 6.3 and 6.4, we introduce and analyze our algorithm, providing lower bounds on how well value-ordered policies can perform.

6.1. Value-Ordered Policies

For this problem, we focus on a natural class of policies, which we call value-ordered policies. Assume that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>v</mi></mrow><mn>1</mn></msub><mo>≥</mo><msub><mrow><mi>v</mi></mrow><mn>2</mn></msub><mo>≥</mo><mo>⋯</mo><mo>≥</mo><msub><mrow><mi>v</mi></mrow><mi>n</mi></msub></mrow></math> . A value-ordered policy is defined by an integer <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>m</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> and sends offers to the m candidates with the highest values (i.e., <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>S</mi><mo>=</mo><mo stretchy="false">{</mo><mn>1</mn><mo>,</mo><mo>...</mo><mo>,</mo><mi>m</mi><mo stretchy="false">}</mo></mrow></math> ). This family of policies is practically well motivated because a firm generally does not want to withhold sending offers to high-value candidates whom it deems "too good" for itself. The optimal value-ordered policy also can be obtained efficiently by solving a dynamic program (see Online Appendix D1 for details).

As natural as they seem, value-ordered policies can achieve an arbitrarily poor approximation factor. Consider the following simple example.

Example 1.

Consider an instance with k = 1 and n = 2. For small ε, candidate 1 has <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>v</mi></mrow><mn>1</mn></msub><mo>=</mo><msub><mrow><mi>p</mi></mrow><mn>1</mn></msub><mo>=</mo><mi>ε</mi></mrow></math> , while candidate 2 has <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>v</mi></mrow><mn>2</mn></msub><mo>=</mo><mi>ε</mi><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mi>ε</mi><mo stretchy="false">)</mo></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>p</mi></mrow><mn>2</mn></msub><mo>=</mo><mn>1</mn></mrow></math> . There are three possible policies for this instance: {1, 2}, {1}, and {2}. The two first are value-ordered policies. The reward for using {1, 2} is zero, for using {1} is <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi>ε</mi></mrow><mn>2</mn></msup></mrow></math> , and for using {2} is <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>ε</mi><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mi>ε</mi><mo stretchy="false">)</mo></mrow></math> . For <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>ε</mi><mo><</mo><mn>1</mn><mo>/</mo><mn>2</mn></mrow></math> , this means that the optimal policy is {2}, and the optimal value-ordered policy is {1}. The approximation factor achieved by value-ordered policies in this instance is equal to <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>ε</mi><mo>/</mo><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mi>ε</mi><mo stretchy="false">)</mo></mrow></math> , which can be made arbitrarily small by taking <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>ε</mi><mo>→</mo><mn>0</mn></mrow></math> .

A similar example can be constructed given any amount of positions k, as we show later in Theorem 4. The intuition behind the previous example is that when ε is small, adding a candidate over capacity provides negligible benefit compared to cost, making the capacity k almost a hard constraint. Although the difficulties of this specific example can be avoided by ordering the candidates in descending order of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></math> instead of v<subs>i</subs>, or using the greedy policy which starts with an empty set of candidates and iteratively adds the candidate with the highest marginal benefit to the set, we show that these alternate algorithmic ideas can also achieve an arbitrarily poor approximation in Online Appendix D2.

We hereafter aim for parametric guarantees for value-ordered policies under the assumption that the values of the candidates are lower-bounded by a parameter <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>τ</mi><mo>></mo><mn>0</mn></mrow></math> . Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mi>τ</mi></msubsup><mo>=</mo><mo stretchy="false">{</mo><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub><mo>:</mo><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub><mo>≥</mo><mi>τ</mi><mo /><mo /><mo>∀</mo><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo><mo stretchy="false">}</mo></mrow></math> be the set of τ-bounded instances. Because we normalized c (the cost of hiring each candidate over capacity) to be one, the value of τ can be interpreted as how hard or soft the capacity constraint of k is in practice. For example, if τ is close to one, then the capacity constraint can be viewed as soft because the cost of hiring over capacity would be almost fully compensated by the value of any candidate. If the capacity constraint is hard in practice, then τ could be close to zero.

We remark that if τ is only small because of "irrelevant" low-value candidates who would never receive an offer, then it does not negatively affect our results. More precisely, our guarantee depends on the lowest value of a candidate with positive mass in the solution of the LP introduced in Section 6.2. We ignore this distinction in our definition of τ-bounded instances for simplicity.

We say that a policy π is an α-approximation for τ-bounded instances if

If <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>τ</mi><mo>≥</mo><mn>1</mn></mrow></math> , then the problem is trivial: It is optimal to send an offer to every candidate. We will therefore restrict our attention to <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>τ</mi><mo>∈</mo><mo stretchy="false">(</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> .

Before we carry on, we define <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub><mo>=</mo><mo stretchy="false">{</mo><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo><mo>:</mo><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub><mo>></mo><mn>1</mn><mo stretchy="false">}</mo></mrow></math> to be the set of candidates whose value is greater than one. These are candidates that we would like to hire even if we know they would violate capacity, essentially making the number of positions random, as they will all receive offers but it is uncertain how many would accept. To our understanding, there is no easy way to reduce the problem to one where they do not exist, when both <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo><mo>∖</mo><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></math> are nonempty.

6.2. LP Relaxation

To obtain approximation factors for value-ordered policies, we introduce a linear programming relaxation of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">OP</mtext><msub><mrow><mi mathvariant="sans-serif">T</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> , which we call <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> :

As with the previous linear programs, y<subs>i</subs> is to be interpreted as the probability that candidate i receives an offer. This linear program optimizes over randomized policies that pay a penalty for the difference between the expected number of candidates hired and k rather than the realized number of candidates hired in excess of k. Thus, by applying Jensen's inequality we can show that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> is an upper bound of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">OP</mtext><msub><mrow><mi mathvariant="sans-serif">T</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> .

Lemma 10.

The proof of this lemma is deferred to Online Appendix D3.

We proceed to show a property about optimal solutions of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> that closely relates it to a value-ordered policy.

Lemma 11.

Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> . There exists an optimal solution (y, z) of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> with an index j such that y<subs>i</subs> = 1 for <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>≤</mo><mi>i</mi><mo>≤</mo><mi>j</mi><mo>−</mo><mn>1</mn><mo>,</mo><mo /><msub><mrow><mi>y</mi></mrow><mi>j</mi></msub><mo>></mo><mn>0</mn></mrow></math> , and y<subs>i</subs> = 0 for <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi><mo>+</mo><mn>1</mn><mo>≤</mo><mi>i</mi><mo>≤</mo><mi>n</mi></mrow></math> .

The proof of this lemma follows from the fact that, for any fixed z, <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> corresponds to an instance of the fractional knapsack problem. It is well known that optimal solutions to this problem satisfy the structure described in Lemma 11 ([11], chapter 5), so it is true for any optimal choice of z. Given Lemma 11, we can easily construct a randomized value-ordered policy from an optimal solution of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> . Indeed, we could simply send an offer to each candidate i independently with probability y<subs>i</subs>. This policy randomizes between two value-ordered policies: sending offers to candidates <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">{</mo><mn>1</mn><mo>,</mo><mo>...</mo><mo>,</mo><mi>j</mi><mo stretchy="false">}</mo></mrow></math> or to candidates <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">{</mo><mn>1</mn><mo>,</mo><mo>...</mo><mo>,</mo><mi>j</mi><mo>−</mo><mn>1</mn><mo stretchy="false">}</mo></mrow></math> . We will make use of this idea when constructing our actual approximation algorithm.

An important object in the definition and analyses of our policies is the "total mass" of a solution of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> . For a feasible solution y, its total mass is given by <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></msub><mrow><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub></mrow></mstyle><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></math> . This can be interpreted as the expected number of candidates that would be hired if we were to send an offer to each candidate i with probability y<subs>i</subs>. Lemma 11 also implies that an optimal solution is completely determined by its total mass. This is because the solution can be constructed by "filling" the components from smallest to largest index until we obtain the desired total mass.

The following lemma allows us to determine the total mass of optimal solutions of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> based on aggregate parameters of instances and will be useful later in the analysis.

Lemma 12.

Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> . Let (y, z) be an optimal solution of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> that satisfies the structure given in Lemma 11. Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>P</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub><mo>=</mo><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></msub><mrow><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></mstyle></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>P</mi></mrow><mrow><mtext mathvariant="monospace">total</mtext></mrow></msub><mo>=</mo><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></msub><mrow><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></mstyle></mrow></math> . The following holds:

If <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>P</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub><mo>></mo><mi>k</mi></mrow></math> , then y<subs>i</subs> = 1 for all <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>∈</mo><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></math> and y<subs>i</subs> = 0 otherwise. Therefore, <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></msub><mrow><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub></mrow></mstyle><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub><mo>=</mo><msub><mrow><mi>P</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></math> ;

If <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>P</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub><mo>≤</mo><mi>k</mi></mrow></math> , then <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></msub><mrow><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub></mrow></mstyle><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub><mo>=</mo><mtext>min</mtext><mo stretchy="false">{</mo><mi>k</mi><mo>,</mo><msub><mrow><mi>P</mi></mrow><mrow><mtext mathvariant="monospace">total</mtext></mrow></msub><mo stretchy="false">}</mo></mrow></math> .

The proof of this lemma is deferred to Online Appendix D4.

6.3. Approximation Algorithm

Let us introduce our approximation algorithm for <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="monospace">sim</mtext></mrow></math> , which we call <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msubsup><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mi>s</mi></msubsup></mrow></math> . The policy takes as input an optimal solution y of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub></mrow></math> and a parameter <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>s</mi><mo>∈</mo><mo stretchy="false">[</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">]</mo></mrow></math> . The idea of the policy is to truncate the optimal solution of the LP. This truncation is done by scaling down the total mass of the optimal LP solution by a factor s and then using this mass to "fill" the new variables from smallest to largest index. We then use this truncated solution to decide which candidates will receive offers.

Formally, the first step is to construct an alternative solution <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>y</mi><mo>′</mo></mrow></math> by truncating y the following way. Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>κ</mi><mo>=</mo><mi>s</mi><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></msub><mrow><msub><mrow><mi>y</mi></mrow><mi>i</mi></msub></mrow></mstyle><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></math> be the total mass of the optimal LP solution, scaled down by a factor s. Let j be the first index such that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>j</mi><mo>+</mo><mn>1</mn></mrow></msubsup><mrow><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></mstyle><mo>></mo><mi>κ</mi></mrow></math> . We let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>y</mi></mrow><mi>i</mi><mo>′</mo></msubsup><mo>=</mo><mn>1</mn></mrow></math> for <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>≤</mo><mi>i</mi><mo>≤</mo><mi>j</mi><mo>,</mo><mo /><msubsup><mrow><mi>y</mi></mrow><mi>i</mi><mo>′</mo></msubsup><mo>=</mo><mn>0</mn></mrow></math> for <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi><mo>+</mo><mn>2</mn><mo>≤</mo><mi>i</mi><mo>≤</mo><mi>n</mi></mrow></math> , and set <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>y</mi></mrow><mrow><mi>j</mi><mo>+</mo><mn>1</mn></mrow><mo>′</mo></msubsup></mrow></math> such that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>j</mi><mo>+</mo><mn>1</mn></mrow></msubsup><mrow><msubsup><mrow><mi>y</mi></mrow><mi>i</mi><mo>′</mo></msubsup></mrow></mstyle><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub><mo>=</mo><mi>κ</mi></mrow></math> . After solution <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>y</mi><mo>′</mo></mrow></math> is constructed, the offers are sent independently to each candidate i with probability <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>y</mi></mrow><mi>i</mi><mo>′</mo></msubsup></mrow></math> . Given the structure of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>y</mi><mo>′</mo><mo>,</mo><mo /><mtext mathvariant="sans-serif">AL</mtext><msubsup><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mi>s</mi></msubsup></mrow></math> clearly randomizes between two value-ordered policies: sending offers to candidates 1 through j, and sending offers to candidates 1 through j + 1. For any k and τ, parameter s can be optimized to maximize the algorithm's performance, and we let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi>s</mi></mrow><mo>*</mo></msup></mrow></math> denote the optimal value. Specifically, <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi>s</mi></mrow><mo>*</mo></msup></mrow></math> is defined as an optimal solution to the problem:

We will use <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi>s</mi></mrow><mo>*</mo></msup></mrow></math> only in our analysis to lower-bound the performance of the best value-ordered policy.

6.4. Analysis of ALGsim

The analysis of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msubsup><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mi>s</mi></msubsup></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msubsup><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mrow><msup><mrow><mi>s</mi></mrow><mo>*</mo></msup></mrow></msubsup></mrow></math> is done in two cases. One case is <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></msub><mrow><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></mstyle><mo>≤</mo><mi>k</mi></mrow></math> , in which sending an offer to all candidates in <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></math> hires an expected number of candidates less than or equal to k. The other case is <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></msub><mrow><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></mstyle><mo>></mo><mi>k</mi></mrow></math> .

<bold> Case 1: </bold> <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></msub><mrow><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></mstyle><mo>≤</mo><mi>k</mi></mrow></math> . In this case, we can show a lower bound for the performance of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msubsup><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mi>s</mi></msubsup></mrow></math> that depends on the choice of s.

Lemma 13.

For any <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>s</mi><mo>∈</mo><mo stretchy="false">[</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">]</mo><mo>,</mo><mo /><mi>τ</mi><mo>∈</mo><mo stretchy="false">(</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> , and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mi>τ</mi></msubsup></mrow></math> with <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></msub><mrow><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></mstyle><mo>≤</mo><mi>k</mi></mrow></math> , we have

The proof of this lemma is deferred to Online Appendix D5.

<bold> Case 2: </bold> <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></msub><mrow><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></mstyle><mo>></mo><mi>k</mi></mrow></math> . In this case, we can show that for an optimally chosen parameter <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi>s</mi></mrow><mo>*</mo></msup></mrow></math> , the guarantee obtained by <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msubsup><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mrow><msup><mrow><mi>s</mi></mrow><mo>*</mo></msup></mrow></msubsup></mrow></math> cannot be worse than the previous case where <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></msub><mrow><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></mstyle><mo>≤</mo><mi>k</mi></mrow></math> . A key observation for analyzing this new case is that as Lemma 12 states, all candidates i whose value y<subs>i</subs> in the optimal LP solution will have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub><mo>≥</mo><mn>1</mn></mrow></math> , so <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi>s</mi></mrow><mo>*</mo></msup><mo>=</mo><mn>1</mn></mrow></math> . Indeed, setting s < 1 can only decrease the chances of sending offers to candidates in <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></math> , and these are candidates that the firm would always want to hire (even over capacity). With this observation in hand, we prove the following, via the construction of an auxiliary instance in which the probabilities of acceptance are deflated.

Lemma 14.

Let <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>=</mo><mo stretchy="false">(</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi><mo>,</mo><mi>v</mi><mo stretchy="false">)</mo><mo>∈</mo><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mi>τ</mi></msubsup></mrow></math> be an instance with <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></msub><mrow><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></mstyle><mo>></mo><mi>k</mi></mrow></math> . Then there exists an instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>′</mo><mo>=</mo><mo stretchy="false">(</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi><mo>′</mo><mo>,</mo><mi>v</mi><mo stretchy="false">)</mo><mo>∈</mo><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mi>τ</mi></msubsup></mrow></math> such that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><msub><mrow><mi>V</mi></mrow><mrow><mtext mathvariant="monospace">high</mtext></mrow></msub></mrow></msub><mrow><msubsup><mrow><mi>p</mi></mrow><mi>i</mi><mo>′</mo></msubsup></mrow></mstyle><mo>=</mo><mi>k</mi></mrow></math> and

The proof of this lemma is deferred to Online Appendix D6.

By combining Lemmas 13 and 14 for an optimally chosen parameter <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi>s</mi></mrow><mo>*</mo></msup></mrow></math> , we obtain the main result of this section.

Theorem 3.

For any <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>τ</mi><mo>∈</mo><mo stretchy="false">(</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mi>τ</mi></msubsup></mrow></math> , we have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>R</mi></mrow><mrow><mtext mathvariant="sans-serif">AL</mtext><msubsup><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mrow><msup><mrow><mi>s</mi></mrow><mo>*</mo></msup></mrow></msubsup></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo><mo>≥</mo><msubsup><mrow><mi>α</mi></mrow><mi>k</mi><mi>τ</mi></msubsup><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> , where

The performance of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msubsup><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mrow><msup><mrow><mi>s</mi></mrow><mo>*</mo></msup></mrow></msubsup></mrow></math> clearly dominates that of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msubsup><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mn>1</mn></msubsup></mrow></math> , where <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msubsup><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mn>1</mn></msubsup></mrow></math> directly follows the LP solution. By Lemma 13, <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msubsup><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mn>1</mn></msubsup></mrow></math> has a guarantee of at least <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>−</mo><mfrac><mn>1</mn><mi>τ</mi></mfrac><mo>+</mo><mfrac><mrow><mi mathvariant="double-struck">E</mi><mo stretchy="false">[</mo><mtext>min</mtext><mo>{</mo><mtext>Pois</mtext><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo><mo>,</mo><mi>k</mi><mo>}</mo><mo stretchy="false">]</mo></mrow><mrow><mi>τ</mi><mi>k</mi></mrow></mfrac></mrow></math> , which equals <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>−</mo><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>k</mi></mrow></msup><msup><mrow><mi>k</mi></mrow><mi>k</mi></msup><mo>/</mo><mo stretchy="false">(</mo><mi>k</mi><mo>!</mo><mi>τ</mi><mo stretchy="false">)</mo></mrow></math> , as we derive in Online Appendix A3. By combining this last expression with Stirling's approximation, we obtain the following result about the asymptotic optimality of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msubsup><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mrow><msup><mrow><mi>s</mi></mrow><mo>*</mo></msup></mrow></msubsup></mrow></math> when the number of positions grows large and the values of candidates are bounded away from zero.

Corollary 4.

For any <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>τ</mi><mo>∈</mo><mo stretchy="false">(</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> and any instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mi>τ</mi></msubsup></mrow></math> , we have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mtext mathvariant="sans-serif">AL</mtext><msubsup><mrow><mi mathvariant="sans-serif">G</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mrow><msup><mrow><mi>s</mi></mrow><mo>*</mo></msup></mrow></msubsup><mo>≥</mo><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo>/</mo><msqrt><mi>k</mi></msqrt><mo stretchy="false">)</mo><mo stretchy="false">)</mo><msub><mrow><mtext>LP</mtext></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> , where k is the number of positions in the instance.

We now provide an upper bound for the guarantee that can be achieved using value-ordered policies. We construct an instance consisting of <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi><mo>=</mo><msup><mrow><mi>j</mi></mrow><mn>2</mn></msup><mo>+</mo><mi>k</mi></mrow></math> candidates[4], with j being a (large) integer. The first j<sups>2</sups> candidates are of type 1, who have <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub><mo>=</mo><mi>k</mi><mo>/</mo><mi>j</mi></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub><mo>=</mo><mi>τ</mi><mo>+</mo><mi>δ</mi></mrow></math> , where <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>δ</mi><mo>></mo><mn>0</mn></mrow></math> is small. The remaining k candidates are of type 2, who have p<subs>i</subs> = 1 and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub><mo>=</mo><mi>τ</mi></mrow></math> . The idea behind this result is that any optimal value-ordered policy will only send offers to type 1 candidates. Conversely, the optimal policy does not perform worse than a policy that sends offers to k type 2 candidates and zero type 1 candidates.

Theorem 4.

For any <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>ε</mi><mo>></mo><mn>0</mn></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>τ</mi><mo>∈</mo><mo stretchy="false">(</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> , there exists an instance <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>I</mi><mo>∈</mo><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow><mi>τ</mi></msubsup></mrow></math> such that no value-ordered policy can have an expected reward greater than <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mrow><msubsup><mrow><mi>β</mi></mrow><mi>k</mi><mi>τ</mi></msubsup><mo>+</mo><mi>ε</mi></mrow><mo stretchy="false">)</mo></mrow><mtext mathvariant="sans-serif">OP</mtext><msub><mrow><mi mathvariant="sans-serif">T</mi></mrow><mrow><mtext mathvariant="monospace">sim</mtext></mrow></msub><mo stretchy="false">(</mo><mi>I</mi><mo stretchy="false">)</mo></mrow></math> , where

The proof of this theorem is deferred to Online Appendix D7. In Online Appendix D8, we analyze the region in which our bounds coincide, together with plots showing <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>α</mi></mrow><mi>k</mi><mi>τ</mi></msubsup></mrow></math> and <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mrow><mi>β</mi></mrow><mi>k</mi><mi>τ</mi></msubsup></mrow></math> for several values of k and τ.

7. Future Directions

We close the paper by pointing out natural follow-up research questions that arise from our work. An interesting open direction is to combine the sequential interviewing problem with the offering problem. This can be done by generalizing the sequential interviewing problem to a setting where candidates are not assured to accept offers and instead have a probability of accepting which might depend on factors such as their realized value. The firm can, at the end of each period, decide to send offers to any candidate who has already been interviewed. Another open direction is to combine the Simultaneous Offering problem with the Parallel Offering problem, as implicitly suggested in [19]. In this setting, the firm could, at each round, send more offers than positions remaining and face the risk of hiring over capacity (at a cost). One last future direction on the modeling side is how the firm should behave when the problem parameters are inaccurate. In particular, acceptance probabilities can be very difficult to estimate, so developing algorithms that are robust to these parameters' misspecification could be of great interest to firms.

On the technical side, we believe the Simultaneous Offering problem introduced is a parsimonious new variant of overbooking. Although our focus was to analyze the performance of value-ordered policies, we do not know of any hardness or algorithmic results for finding the best offer set. It would be interesting if an optimal or near-optimal (i.e., PTAS) algorithm could be found. The question of whether we can improve on <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>−</mo><mn>1</mn><mo>/</mo><mi>e</mi></mrow></math> for the sequential offering problem (or maybe even obtain a PTAS) is also open.

Acknowledgments

The authors thank José Correa for insightful discussions about Sequential Offering, Rad Niazadeh for pointing us to the highly relevant reference ([4]), and Aravind Srinivasan for insightful discussions about negative association. The authors further thank anonymous reviewers for Operations Research who gave exceptionally detailed comments and identified the corollaries in Sections 4.5 and 6.4. A one-page abstract of this work appeared in the 18th conference on Web and Internet Economics 2022.

<bold>Boris Epstein</bold> is a doctoral candidate in the Decision, Risk, and Operations division of the Graduate School of Business at Columbia University. His research focuses on studying theoretical models of sequential decision making under uncertainty, with applications in revenue management and supply chain management.

<bold>Will Ma</bold> is an associate professor of Decision, Risk, and Operations at the Graduate School of Business in Columbia University. His research focuses on the theory of online algorithms and their applications in revenue management and e-commerce.

Footnotes

1 Requiring the firm to hire at most k candidates with probability 1 would make this problem trivial: the firm would send an offer to the k candidates with the highest expected value <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>v</mi></mrow><mi>i</mi></msub><msub><mrow><mi>p</mi></mrow><mi>i</mi></msub></mrow></math> .

2 If y<subs>i</subs> = 0, then <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle displaystyle="false"><msubsup><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>J</mi></msubsup><mrow><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow></mstyle><mo>=</mo><mn>0</mn></mrow></math> too. If y<subs>i</subs> = 0, then the algorithm will never interview applicant i, so the definition of these values is not relevant for the analysis.

3 We know that <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi>k</mi></mrow><mo>*</mo></msup></mrow></math> always exists because <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>k</mi></mrow></msup><msup><mrow><mi>k</mi></mrow><mi>k</mi></msup><mo>/</mo><mo stretchy="false">(</mo><mi>k</mi><mo>!</mo><mo stretchy="false">)</mo></mrow></math> is a decreasing function that equals <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>/</mo><mi>e</mi></mrow></math> when k = 1 and converges to zero as <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>→</mo><mi>∞</mi></mrow></math> .

4 We do not need exactly j<sups>2</sups> candidates of type 1 for showing the result. Any amount of candidates <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi mathvariant="script">ℓ</mi></mrow><mi>j</mi></msub></mrow></math> with <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi mathvariant="script">ℓ</mi></mrow><mi>j</mi></msub><mo>/</mo><mi>j</mi><mo>→</mo><mi>∞</mi></mrow></math> as <math display="inline" overflow="scroll" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi><mo>→</mo><mi>∞</mi></mrow></math> will suffice.

5 Corresponding author

References

Agrawal S, Sethuraman J, Zhang X. (2020). On optimal ordering in the optimal stopping problem. Biró P, Hartline J, eds. Proc. 21st ACM Conf. on Econom. and Comput. (Association for Computing Machinery, New York), 187–188.

Arnosti N, Ma W (2023). Tight guarantees for static threshold policies in the prophet secretary problem. Oper. Res. 71(5):1777–1788.

Beyhaghi H, Golrezaei N, Leme RP, Pál M, Sivan B. (2021). Improved revenue bounds for posted-price and second-price mechanisms. Oper. Res. 69 (6): 1805–1822.

Bradac D, Singla S, Zuzic G (2019). (Near) optimal adaptivity gaps for stochastic multi-value probing. Achlioptas D, Végh LA, eds. Approximation, Randomization, Combin. Optim. Algorithms Techniques, Leibniz International Proceedings in Informatics (LIPIcs), vol. 145 (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern), 1–49.

Cominetti R, Correa JR, Rothvoß T, Martín JS. (2010). Optimal selection of customers for a last-minute offer. Oper. Res. 58 (4-part-1): 878–888.

6 Esfandiari H, Hajiaghayi M, Liaghat V, Monemizadeh M. (2017). Prophet secretary. SIAM J. Discrete Math. 31 (3): 1685–1701.

7 Fu H, Li J, Xu P (2018). A PTAS for a class of stochastic dynamic programs. Chatzigiannakis I, Kaklamanis C, Marx D, Sannella D, eds. 45th Internat. Colloquium Automation, Languages, Programming (ICALP 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 107 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 1–56.

8 Gallego G, Segev D. (2022). A constructive prophet inequality approach to the adaptive probemax problem. Preprint, submitted October 14, https://arxiv.org/abs/2210.07556.

9 Gallego G, Topaloglu H. (2019). Revenue Management and Pricing Analytics, vol. 209 (Springer, Berlin).

Gandhi R, Khuller S, Parthasarathy S, Srinivasan A. (2006). Dependent rounding and its applications to approximation algorithms. J. ACM 53 (3): 324–360.

Goodrich MT, Tamassia R. (2001). Algorithm Design: Foundations, Analysis, and Internet Examples (John Wiley & Sons, Hoboken, NJ).

Gupta A, Nagarajan V (2013). A Stochastic probing problem with applications. Goemans M, Correa J, eds. Integer Programming and Combinatorial Optimization. IPCO 2013, Lecture Notes in Computer Science, vol. 7801 (Springer, Berlin, Heidelberg).

Gupta A, Nagarajan V, Singla S. (2016). Algorithms and adaptivity gaps for stochastic probing. Krauthgamer R, ed. Proc. 27th Annual ACM-SIAM Sympos. on Discrete Algorithms (Association for Computing Machinery, New York), 1731–1747.

Gupta A, Nagarajan V, Singla S. (2017). Adaptivity gaps for stochastic probing: Submodular and xos functions. Krauthgamer R, ed. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1688–1702.

Hill T. (1983). Prophet inequalities and order selection in optimal stopping problems. Proc. Amer. Math. Soc. 88 (1): 131–137.

Kleinberg R, Weinberg SM. (2012). Matroid prophet inequalities. Karloff H, ed. Proc. 44th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 123–136.

Krengel U, Sucheston L. (1977). Semiamarts and finite values. Bull. Amer. Math. Soc. (New Series) 83 (4): 745–747.

Krengel U, Sucheston L. (1978). On semiamarts, amarts, and processes with finite value. Probability Banach Spaces 4 : 197–266.

Purohit M, Gollapudi S, Raghavan M. (2019). Hiring under uncertainty. Chaudhuri K, Salakhutdinov R, eds. Proc. Internat. Conf. Machine Learn. (PMLR, New York), 5181–5189.

Samuel-Cahn E. (1984). Comparison of threshold stop rules and maximum for independent nonnegative random variables. Annals Probability 12(4):1213–1216.

Segev D, Singla S. (2021). Efficient approximation schemes for stochastic probing and prophet problems. Biró P, ed. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 793–794.

Yan Q. (2011). Mechanism design via correlation gap. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 710–719.

By Boris Epstein and Will Ma

Reported by Author; Author

Boris Epstein is a doctoral candidate in the Decision, Risk, and Operations division of the Graduate School of Business at Columbia University. His research focuses on studying theoretical models of sequential decision making under uncertainty, with applications in revenue management and supply chain management.

Will Ma is an associate professor of Decision, Risk, and Operations at the Graduate School of Business in Columbia University. His research focuses on the theory of online algorithms and their applications in revenue management and e-commerce.