Selection and Ordering Policies for Hiring Pipelines via Linear Programming

Boris Epstein Graduate School of Business, Columbia University, New York, NY
10027<EMAIL_ADDRESS>
Will Ma Graduate School of Business, Columbia University, New York, NY 10027,
<EMAIL_ADDRESS>
Motivated by hiring pipelines, we study three selection and ordering problems
in which applicants for a finite set of positions must be interviewed or made
offers to. There is a finite time budget for interviewing or making offers,
and a stochastic realization after each decision, leading to computationally-
challenging problems. In the first problem, we study sequential interviewing
and show that a computationally-tractable, non-adaptive policy that must make
offers immediately after interviewing is approximately optimal, assuming
offerees always accept their offers. 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 approximately optimal relative to a policy that can
make the same amount of offers not in parallel. In the third problem, we
introduce a model where the hiring firm is tightly time constrained and must
send all offers simultaneously in a single time step, with the possibility of
hiring over capacity at a cost; we provide nearly-tight bounds for 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 guarantees from Purohit et al. (2019) that were
between 1/8 and 1/2 to new guarantees that are at least $1-1/e\approx 63.2\%$.
We also numerically compare three different settings of making offers to
candidates (sequentially, in parallel, or simultaneously), providing insight
on when a firm should favor each one.

##  1 Introduction

Hiring the right personnel is arguably the most determining factor in the
success of an enterprise. That being said, carrying out an efficient and
timely recruitment process results 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 recruitment processes 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 must
decide who is going to be interviewed and in which order are the interviews
going to be conducted. Both of these aspects are relevant because a
recruitment process cannot go on forever. Thus, not all applicants are going
to be able to receive an interview, and depending on the outcomes of past
interviews the firm could have different preferences on who to interview next.

When applicants are interviewed they become candidates. After all interviews
are conducted, the firm must send offers to the candidates it wishes to hire.
Again, who to send an offer is the central decision to make here. 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 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 carry on with the next 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 must come 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.

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; there is a limit of $T$ on the number of interviews conducted.
The realization of the value of the candidate becomes known to the firm
immediately after carrying out the interview. We note that 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. 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,111The case where $k=1$ is called the ProbeMax problem. as described
in Fu et al. (2018), which is computationally challenging because the state
space is exponential in the number of applicants (one has to track the subset
that has been interviewed and their values).

In this problem, we can further distinguish between different classes of
policies. First, we distinguish between adaptive and non-adaptive policies.
Adaptive policies can decide the order of the interviews on the go, choosing
who to interview next depending on the outcomes of previous interviews. Non-
adaptive policies, in contrast, have to fix an interview order before the
process starts, which although restrictive, is attractive from an easy-of-
implementation perspective. We also distinguish between committed and non-
committed policies. Committed policies have to, after each interview, make an
irrevocable decision of whether to hire a candidate or not (given her value).
Non-committed 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 for all interviews to
be conducted allows candidates to 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 non-adaptive and committed.222The latter is
quantified in the literature by the widely studied notion of adaptivity gap:
the worst-case ratio between the performance of general policies vs.
algorithms that are restricted to be non-adaptive. Our results will bound the
“adaptivity-commitment gap”, in which the algorithm is restricted to be both
non-adaptive and committed.

Related model: 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 only committed policies are interesting to study (non-committed policies
can interview all $n$ candidates and the order does not matter). Typically in
prophet inequalities, one compares to a benchmark that can see all candidates’
values and does not need to commit (i.e. they can hire the $k$ highest-valued
candidates in hindsight). We note that such a benchmark is too powerful to
compare against in our more general problem if $n$ is much larger than $T$
since the benchmark sees all $n$ realizations while the algorithm can only
interview $T$ applicants. This is why in our general ProbeTop-$k$ problem, we
compare to an optimal (adaptive, non-committed) algorithm that is still bound
by $T$ interviews that must be decided without any prophetic information,
making our comparison different from prophet inequalities. However, our
algorithm for ProbeTop-$k$, being non-committed, implies an algorithm for
free-order prophets that has the same guarantee relative to the prophet
benchmark in the special case of free-order prophet inequalities (where
$T=n$).

Related model 2: sequential offering. In the sequential offering model of
Purohit et al. (2019), 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 she will accept an offer, and the value
she adds to the firm should she 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. We show that this setting can be captured by the
ProbeTop-$k$ problem with weighted Bernoulli distributions, where the values
take a positive realization with some probability (representing an acceptance)
or 0 with the remaining probability (representing a rejection). The subtlety
is that an accepted offer cannot be turned down 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 make it admissible for the sequential
offering problem too.

Second model: parallel offering. We also study a parallel offering model, in
which a firm again has to hire people to fill $k$ job 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, she can either accept or reject it, with the assumption
that they will not receive another offer if they reject 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 non-adaptive algorithm that can be computed efficiently and performs
competitively in comparison to adaptive and even sequential algorithms (we
formalize these concepts in the sequel).

This model generalizes a parallel offering model also introduced in Purohit et
al. (2019), 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. T

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 a subset of candidates who will receive an offer (all at
the same time). This subset has no constraints, so a possible outcome is that
more than $k$ candidates accept an offer. If that is the case, the firm must
pay a penalty for each candidate that 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.

Model |  Action
performed |  Result of action |  Actions per time step |  Moment of
hiring |  Bound on
total hires
---|---|---|---|---|---
ProbeTop-$k$ |  Interview |  Observe value of
candidate |  One |  After last interview |  Hard
Free-order Prophets |  Interview |  Observe value of
candidate |  One |  After each interview (irrevocable) |  Hard
Sequential
Offering |  Send offer |  Observe accept/reject decision |  One |  Upon acceptance of offer |  Hard
Parallel
Offering |  Send offer(s) |  Observe accept/reject decision(s) |  One per position |  Upon acceptance of offer |  Hard
Simultaneous Offering |  Send offer(s) |  Observe accept/reject decision(s) |  $n$ |  Upon acceptance of offer |  Soft (linear penalty)

Table 1: Comparison between models. Each model comes with $n$
applicants/candidates, $k$ positions to fill, and $T$ time steps to perform
actions (in Simultaneous offering, $T=1$). The Free-order prophets problem
typically is additionally constrained to have $T=n$, but our results hold
without this assumption

.

In Section 7, we numerically simulate the three different models of sending
offers (sequential, parallel, simultaneous) using the same candidate pool
generation process as Purohit et al. (2019). We illustrate the improved
performances offered by our new policies, and compare the performances
attainable across the different models, providing insight on 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 going over. In
that case, it is better to identify the highest-valued “safe” candidates (with
a large probability of acceptance) to reduce the variance in the number of
accepted offers.

##  2 Our Results and Literature Review

In this section, we provide an overview of our results and their connection to
the existing literature. In Subsection 2.1 we give a summary of our results
and their relevance with respect to existing work. In Subsection 2.2 we
provide a broader list of literature that surrounds our work.

###  2.1 Our Results

For $\alpha\leq 1$, we say that an algorithm is $\alpha$-approximate if its
expected total value collected is at least $\alpha$ times that of an optimal
algorithm. $\alpha$ is referred to as the approximation factor.

Sequential interviewing a.k.a. ProbeTop-$k$ problem. For the ProbeTop-$k$
problem, we develop a polynomial-time, non-adaptive, and committed algorithm
that achieves a $(1-e^{-k}k^{k}/k!)$ approximation factor relative to an
optimal (adaptive, non-committed) algorithm (Theorem 4.5, Section 4). We note
that the approximation factor of $(1-e^{-k}k^{k}/k!)$ is always at least
$1-1/e\approx 0.632$ (when $k=1$), and increases to 100% as $k\to\infty$. We
also note that it is tight relative to the LP benchmark we compare against
(Appendix LABEL:sec:tight). Our results are significant for the following
reasons. First, the previously best-known approximation factor was 1/2,
obtained by both Purohit et al. (2019) and Bradac et al. (2019), so our lower
bound is not only stronger for all values of $k$, but demonstrates asymptotic
optimality in $k$. Second, the $1/2$-approximate algorithm in Bradac et al.
(2019) is not polynomial-time and not committed, while the polynomial-time
$1/2$-approximate algorithm in Purohit et al. (2019) needs to be adaptive,
only compares against policies that are committed, and also focuses on the
special case of sequential offering (we elaborate on this in Section 4.4).
Finally, our abstract treatment leads to an algorithm that works in the free-
order prophets setting (because it is committed), hence our result extends to
a free-order prophet inequality that allows an additional constraint of $T$ on
the number of interviews.

Parallel offering problem. For the parallel offering model, we develop an
algorithm that is non-adaptive and achieves a $(1-1/e)$ approximation factor
relative to an optimal (adaptive) algorithm (Theorem 5.4, Appendix 5). This
result also both improves and generalizes existing results, in this case, the
1/8-approximate algorithm of Purohit et al. (2019) that works in the special
case where all positions are identical. It is also tight relative to the LP
benchmark we compare against (Appendix LABEL:sec:parTight). We further show
that our algorithm obtains at least $(1-1/e)$ times what an optimal algorithm
would obtain in the sequential offering problem with $kT$ time steps,
establishing a lower bound on the value of a batched solution (Corollary 5.6,
Section 5.3).

Simultaneous offering problem. We analyze the performance of value-ordered
policies, which send offers to candidates above a value threshold. This means
that if the policy wants to send an offer to the candidate with the $m$-th
highest value, then it is obliged to send an offer to the $m-1$ candidates
with a higher value as well. 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 6.1,
Subsection 6.1). Then, we assume that the valuations of candidates are lower
bounded by a parameter $\tau\in(0,1)$ and provide a value-ordered policy that
achieves at least a factor $\alpha_{k}^{\tau}$ of what an optimal policy would
achieve (Theorem 6.7, Subsection 6.3). We also provide an instance where no
value-ordered policy can achieve a factor higher than $\beta_{k}^{\tau}$ of
what an optimal policy could achieve (Theorem 6.8, Subsection 6.3) and
characterize the region where $\alpha_{k}^{\tau}=\beta_{k}^{\tau}$
(Proposition 6.10, Subsection 6.3). In particular, the bound is tight for all
$k$ if $\tau\leq 1/2$.

###  2.2 Further Related Work

Stochastic probing and matching. Our work is closely related to the general
stochastic probing problem studied in Gupta and Nagarajan (2013) and Gupta et
al. (2016). These papers study the problem of sequentially probing elements in
order 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. Bradac et al. (2019) 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 Bradac et al. (2019) they show that the adaptivity gap333This is defined as
the worst-case ratio between the performance of adaptive and non-adaptive
policies. 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 non-adaptive
algorithm that can be computed in polynomial time is due by Gupta et al.
(2017), which achieves a 1/3 approximation for submodular and XOS functions
under prefix-closed probing constraints.

We note that these stochastic probing problems were heavily inspired by the
stochastic matching problem with patience constraints, originally studied in
Chen et al. (2009) and Bansal et al. (2012). Our parallel offering problem has
the flavor of a stochastic matching problem, although it is heavily
constrained and simpler.

PTAS-type results. Fu et al. (2018) develop several PTASs for a class of
dynamic programs that includes the ProbeTop-$k$ problem. They propose an
adaptive PTAS for ProbeTop-$k$ and another one for the committed version of
the problem.444The committed version is where only committed policies are
allowed. Adaptive policies are still allowed. Segev and Singla (2021) develop
EPTASs for several related problems, also including the non-adaptive version
of the ProbeTop-$k$ problem.555In this paper they call it the Top-$r$ ProbeMax
problem. Their EPTAS works differently when $k$ is small or large. They
actually use the same LP relaxation for the large $k$ case, although their
rounding scheme and analysis are substantially different. We note that none of
these PTAS-type results use non-adaptive, committed policies to approximate
the best adaptive, non-committed policies, as in our paper.

Prophet inequalities. Our work has the flavor of prophet inequalities in that
we are trying to decide online whether to accept values drawn from known
distributions, and comparing against a supernatural benchmark. Classical works
in prophet inequalities (Krengel and Sucheston 1977, 1978, Samuel-Cahn 1984,
Kleinberg and Weinberg 2012, Esfandiari et al. 2017) assume that the order is
beyond our control, while we are studying the free-order variant where the
order can be decided (Hill 1983, Beyhaghi et al. 2021, Agrawal et al. 2020).
However, due to the constraint of $T$ time steps, as discussed earlier, it is
important 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 $(1-e^{-k}k^{k}/k!)$ has also been established for free-
order by Yan (2011) and extended in Arnosti and Ma (2021) to random-order
prophets, but neither of these works allows for a constraint of $T$ time
steps.

Simultaneous offering model. Our simultaneous offering model and in particular
the linear penalty cost is motivated by static overbooking models in revenue
management (see e.g. Gallego and Topaloglu 2019, Ch. 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 Cominetti et al. (2010), where a subset of customers are sent last-
minute offers for a limited amount 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.

Concurrent work. Parallel to our work, Gallego and Segev (2022) have studied
and obtained results for the ProbeTop-$1$ problem. Although both works aim to
derive non-adaptive algorithms for the problem, theirs is different from ours
in several aspects. On one hand, 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. On the other hand, the bounds they achieve are
1/2 for general random variables and $1-1/e$ for continuous random variables,
which also hold for the ProbeTop-$k$ problem, but they do not improve as $k$
grows. Our bounds, in contrast, grow from $1-1/e$ when $k=1$, to 1 when
$k\to\infty$. One last aspect that distinguishes our work from Gallego and
Segev (2022) is the relaxations used to measure the performance of their
algorithms. While we use standard LP relaxations, 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 throughout 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 with by stating the
Simultaneous Offering problem in Subsection 3.3.

###  3.1 ProbeTop-k Problem

Consider the ProbeTop-$k$ ($\mathtt{ptk}$) problem. In this problem, a firm
faces the challenge of filling $k$ positions out of a pool of $n$ candidates.
Each candidate $i$ has a random, non-negative value $V_{i}\sim F_{i}$, and
$F_{i}$ is known to the firm. Before the firm hires a candidate, an interview
must be conducted. When the firm interviews candidate $i$, the realization of
$V_{i}$ 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 $I=(k,T,n,F)$, where
$1\leq k\leq T\leq n$, and $F=\\{F_{i}\\}_{i\in[n]}$666We use $[n]$ to denote
$\\{1,\dots,n\\}$. is a collection of probability distribution functions. In
this work, we focus on distributions supported on a finite set
$\\{r_{1},\dots,r_{J}\\}$ of polynomial size and we use $q_{ij}$ to denote
$\mathbb{P}(V_{i}=r_{j})$. We use $\mathcal{I}_{\mathtt{ptk}}$ to denote the
set of all possible instances for the ProbeTop-$k$ problem. We further use
$\mathcal{I}_{\mathtt{ptk}}^{k}$ to denote
$\\{I\in\mathcal{I}_{\mathtt{ptk}}:$ amount of positions is $k\\}$. Let
$\Pi^{\mathtt{ptk}}$ be the set of all policies for $\mathtt{ptk}$. For a
policy $\pi\in\Pi^{\mathtt{ptk}}$ and an instance
$I\in\mathcal{I}_{\mathtt{ptk}}$ let $R_{\pi}(I)$ be the expected reward of
using policy $\pi$ on the instance in question. For an instance
$I\in\mathcal{I}_{\mathtt{ptk}}$ define
$\mathsf{OPT}_{\mathtt{ptk}}(I):=\sup_{\pi\in\Pi^{\mathtt{ptk}}}R_{\pi}(I)$ as
the expected reward of using the best possible policy on instance $I$. We call
a policy $\pi\in\Pi^{\mathtt{ptk}}$ an $\alpha$-approximation if

$\inf_{I\in\mathcal{I}_{\mathtt{ptk}}}\frac{R_{\pi}(I)}{\mathsf{OPT}_{\mathtt{ptk}}(I)}\geq\alpha.$

We distinguish between adaptive and non-adaptive policies. A non-adaptive
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 non-
committed policies. After each interview, committed policies must irrevocably
decide whether to hire the candidate or not. Non-committed policies, in
contrast, can interview $T$ candidates and then choose the $k$ highest
realizations among them. We are interested in how well can the firm perform
when restricted to using non-adaptive 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 non-adaptive
and committed.

###  3.2 Parallel Offering Problem

The second setting we study in this paper is the Parallel Offering problem
($\mathtt{par}$). Again consider the case of a firm that has to hire
candidates in order 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 $i\in[n]$ and position $j\in[k]$ the
firm knows $p_{ij}$: the probability that the candidate accepts an offer for
the position, and $v_{ij}$: the reward collected by the firm if the candidate
accepts an offer for the position. The firm can carry out at most $T$ offering
rounds. At each offering round the firm can send an offer for each position
that is yet to be occupied by a candidate (hence the name parallel offering).
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 $I=(k,T,n,p,v)$, where
$1\leq k\leq T\leq n$, $p\in[0,1]^{n\times k}$ and
$v\in\mathbb{R}_{+}^{n\times k}$. Let $\mathcal{I}_{\mathtt{par}}$ denote the
set of all instances and $\Pi^{\mathtt{par}}$ denote the set of all policies
for the parallel offering model. Again let $R_{\pi}(I)$ denote the expected
reward of using policy $\pi\in\Pi^{\mathtt{par}}$ on instance
$I\in\mathcal{I}_{\mathtt{par}}$. Let
$\mathsf{OPT}_{\mathtt{par}}(I):=\sup_{\pi\in\Pi^{\mathtt{par}}}R_{\pi}(I)$ be
the best possible expected reward that can be obtained from an instance
$I\in\mathcal{I}_{\mathtt{par}}$. We say that a policy
$\pi\in\Pi^{\mathtt{par}}$ is an $\alpha$-approximation if

$\inf_{I\in\mathcal{I}_{\mathtt{par}}}\frac{R_{\pi}(I)}{\mathsf{OPT}_{\mathtt{par}}(I)}\geq\alpha.$

In this model, we assume that before the offering rounds start, each candidate
has already decided which offers she 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, it is not clear how to define non-adaptive policies. A
natural class of policies that could be considered non-adaptive are the ones
that construct one list with a fixed order for each position and runs the
lists in parallel. The algorithm we develop for this problem falls in this
class of non-adaptive policies, establishing a lower bound on how well these
algorithms can perform.

###  3.3 Simultaneous Offering Problem

The third and last setting we study is the Simultaneous Offering problem
($\mathtt{sim}$). 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 $\mathtt{ptk}$ and
$\mathtt{par}$. 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, paying a linear
cost for each candidate hired over $k$.777Requiring 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
$v_{i}p_{i}$.

Formally, we have the following problem. There are $n$ candidates. For each
candidate $i\in[n]$, we know $p_{i}$: the probability that candidate $i$
accepts an offer if sent, and $v_{i}$: the value obtained if $i$ accepts the
offer. The firm must select a subset $S\subseteq[n]$ 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_{i}$, in which case they
add value $v_{i}$ to the firm. For each candidate that exceeds the capacity
$k$, the firm incurs a linear cost of $c>0$. Let $A\subseteq S$ be the
(random) subset of candidates that accepted their offers. The reward obtained
by the firm is $\sum_{i\in A}v_{i}-c\cdot\max\\{|A|-k,0\\}$. By re-scaling
values $v_{i}$ by $1/c$, we can assume without loss of generality that $c=1$.
The re-scaled values $v_{i}$ can be interpreted as the value that a candidate
adds to the firm, relative to the cost of hiring that same candidate over
capacity.

With this notation, an instance of $\mathtt{sim}$ can be described by a tuple
$I=(k,n,p,v)$, where $1\leq k\leq n$, $p\in[0,1]^{n}$ and
$v\in\mathbb{R}_{+}^{n}$. Let $\mathcal{I}_{\mathtt{sim}}$ denote the set of
all instances and $\Pi^{\mathtt{sim}}$ denote the set of all (possibly
randomized) policies for the simultaneous offering problem. Let $R_{\pi}(I)$
denote the expected reward of using policy $\pi\in\Pi^{\mathtt{sim}}$ on
instance $I\in\mathcal{I}_{\mathtt{sim}}$. Let
$\mathsf{OPT}_{\mathtt{sim}}(I)$ be the best possible expected reward that can
be obtained from an instance $I\in\mathcal{I}_{\mathtt{sim}}$. We call a
policy $\pi$ an $\alpha$-approximation if

$\inf_{I\in\mathcal{I}_{\mathtt{sim}}}\frac{R_{\pi}(I)}{\mathsf{OPT}_{\mathtt{sim}}(I)}\geq\alpha.$

##  4 ProbeTop-k Problem

In this section, we provide our algorithm and analysis for the ProbeTop-$k$
problem, where candidates are sequentially interviewed. We develop a non-
adaptive, committed policy that achieves a $(1-e^{-k}k^{k}/k!)$ approximation
of any policy (adaptive, non-committed). The algorithm first solves a LP
relaxation that upper bounds the performance of any (adaptive, non-committed)
algorithm, and uses the LP solution as an input to decide the candidates that
will be interviewed, in which order, and whether to hire an interviewed
candidate, given her value.

In Section 4.1 we introduce the LP in question. In Section 4.2 we introduce a
simple dependent rounding scheme that will be used in our approximation
algorithm. In Section 4.3 we introduce our approximation algorithm and show
that it attains the mentioned approximation guarantee. In Section 4.4 we treat
the special case when values are distributed as weighted Bernoulli random
variables. The proofs and complementary material of this section are presented
in Appendix 10. The analyses in this section, as well as those in Section 5
make use of correlation gap results by Yan (2011) and dependent rounding
schemes by Gandhi et al. (2006). We recommend readers who are not familiar
with these papers to visit Appendix 9 before reading the proofs.

###  4.1 Linear program

Consider the linear program $\textsc{LP}_{\mathtt{ptk}}$, which for any
instance of ProbeTop-$k$, upper bounds the performance of all possible
policies. In $\textsc{LP}_{\mathtt{ptk}}$, variable $y_{i}$ is to be
interpreted as the probability that candidate $i$ is interviewed. Variable
$x_{ij}$ is to be interpreted as the probability that candidate $i$ is hired
and $V_{i}=r_{j}$.

$\displaystyle LP_{\mathtt{ptk}}(I)=\max\quad$
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{J}r_{j}x_{ij}$ $\displaystyle
s.t.\quad$ $\displaystyle x_{ij}\leq y_{i}q_{ij}$ $\displaystyle\forall
i\in[n],j\in[J]$ (1) $\displaystyle\sum_{i=1}^{n}y_{i}\leq T$ (2)
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{J}x_{ij}\leq k$ (3) $\displaystyle
x_{i,j}\geq 0$ $\displaystyle\forall i\in[n],j\in[J]$ $\displaystyle 0\leq
y_{i}\leq 1$ $\displaystyle\forall i\in[n].$

We first show that $\textsc{LP}_{\mathtt{ptk}}$ upper bounds the optimal
(adaptive, non-committed) algorithm.

###### Lemma 4.1

For any instance $I\in\mathcal{I}_{\mathtt{ptk}}$,
$\textsc{LP}_{\mathtt{ptk}}(I)\geq\mathsf{OPT}_{\mathtt{ptk}}(I)$.

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 candidates to be interviewed.

###### Lemma 4.2

Let $I\in\mathcal{I}_{\mathtt{ptk}}$ and let
$y=(y_{i})_{i\in[n]},x=(x_{ij})_{i\in[n],j\in[J]}$ be a basic feasible
solution of $\textsc{LP}_{\mathtt{ptk}}(I)$. Then $y$ has at most 2 non-
integer components. If it has 2 non-integer components, then they add up to 1.

###  4.2 Dependent rounding

We develop a simple dependent rounding scheme (which we call DR for short)
that will be used as a subroutine of our approximation algorithm. DR receives
an optimal solution $y=(y)_{i\in[n]}$ of $\textsc{LP}_{\mathtt{ptk}}$ as an
input and returns a (possibly random) vector $Y\in\\{0,1\\}^{n}$. DR works
differently depending on the number of fractional components of the optimal
solution $y$. In any case, for all $i$ such that $y_{i}\in\\{0,1\\}$, it sets
$Y_{i}=y_{i}$ with probability 1. If $y$ is integral, then $Y$ is
deterministic. If there is exactly one fractional component $i^{\prime}$, then
it sets $Y_{i^{\prime}}=1$ with probability $y_{i^{\prime}}$ (and it sets
$Y_{i^{\prime}}=0$ otherwise). If there are exactly two fractional components
$i_{1}$ and $i_{2}$, then it sets $Y_{i_{1}}=1,Y_{i_{2}}=0$ with probability
$y_{i_{1}}$ and sets $Y_{i_{1}}=0,Y_{i_{2}}=1$ with probability
$1-y_{i_{1}}=y_{i_{2}}$. It is easy to see that the output of DR satisfies the
following two properties: (P1) $\mathbb{E}(Y_{i})=y_{i}$ for every $i\in[n]$,
and (P2) $\sum_{i\in[n]}Y_{i}\leq T$ with probability 1. As a remark, the
output of DR will also satisfy the negative correlation property of the
dependent rounding developed by Gandhi et al. (2006), although we do not make
use of it explicitly.

###  4.3 Approximation algorithm

We propose the following algorithm for the ProbeTop-$k$ problem, which we call
$\mathsf{ALG}_{\mathtt{ptk}}$. Given an instance, we first solve
$\textsc{LP}_{\mathtt{ptk}}(I)$. Let $x,y$ be an optimal solution. Define

$p_{i}=\frac{\sum_{j}x_{ij}}{y_{i}},\quad
v_{i}=\frac{\sum_{j}r_{j}x_{ij}}{\sum_{j}x_{ij}}.$

If any of the denominators is 0, define these values as 0.888If $y_{i}=0$,
then $\sum_{j}x_{ij}=0$ too. If $y_{i}=0$ then the algorithm will never
interview applicant $i$, so the definition of these values is not relevant for
the analysis. For reasons that will soon become clear, $p_{i}$ is to be
interpreted as the probability that we accept candidate $i$ given that she
gets interviewed, and $v_{i}$ is to be interpreted as the expected value of
candidate $i$ given that she gets hired. Assume that we relabel the candidates
after solving the LP so that $v_{1}\geq v_{2}\geq\cdots\geq v_{n}$.

The algorithm first chooses which candidates 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 and the order in which the offers are
sent is decreasing in $v_{i}$. After deciding on the candidates to interview
and the order, the interviews are conducted. Upon interviewing candidate $i$
and observing her value $r_{j}$, we hire the candidate with probability
$x_{ij}/(y_{i}q_{ij})$. A pseudo-code for this algorithm can be found in
Appendix LABEL:ap:pseudo.

As we are using DR to decide which candidates get interviews we have that if
the optimal solution $y$ has zero or one fractional component, candidates are
independently selected for receiving interviews. If there are two fractional
components, then the two corresponding candidates have a perfect negative
correlation (meaning that one is selected for interviewing if and only if the
other one is not). We show that the algorithm performs better with this
negative correlation than it would if each candidate was selected to be
interviewed independently with probability $y_{i}$.999Selecting candidates
this way could lead to unfeasible solutions where more than $T$ applicants
receive interviews. Our algorithm with negative correlation outperforms the
independent version even if it happens to violate this constraint.

To analyze the algorithm let $Y_{i}$ be the indicator that candidate $i$ is
included in the list of candidates to receive an interview. Let $Q_{ij}$ be
the indicator of $V_{i}=r_{j}$. Let $P_{i}$ be the indicator that candidate
$i$ would be hired if she was interviewed while still having unfilled
positions. We colloquially refer to this event as candidate $i$ ‘making the
cut’. We have

$\mathbb{E}(P_{i})=\sum_{j=1}^{J}\mathbb{E}(P_{i}|Q_{ij})q_{ij}=\sum_{j=1}^{J}\frac{x_{ij}}{q_{ij}y_{i}}q_{ij}=p_{i}.$

Define $Z_{i}=Y_{i}\cdot P_{i}$ as the indicator that $i$ is included in the
list of candidates to receive an interview and that the algorithm would
respond with a hire decision upon revealing $i$’s value. Note that $Y_{i}$ is
necessarily independent of $P_{i}$. Let $N_{i-1}=\sum_{\ell=1}^{i-1}Z_{\ell}$
be the number of candidates that are interviewed before candidate $i$ that
would be hired if there are still positions available. We can therefore write
the (random) reward of our algorithm as
$\sum_{i}V_{i}\mathbbm{1}\\{N_{i-1}<k\\}Z_{i}$. The following Lemma allows us
to write the expected reward of $\mathsf{ALG}_{\mathtt{ptk}}$ in a way that
will allow us to relate it to weighted rank functions of $k$-uniform matroids.

###### Lemma 4.3

For any $I\in\mathcal{I}_{\mathtt{ptk}}$,
$R_{\mathsf{ALG}_{\mathtt{ptk}}}(I)=\sum_{i=1}^{n}v_{i}\mathbb{E}(\mathbbm{1}\\{N_{i-1}<k\\}Z_{i})$.

Since the candidates are labeled such that $v_{1}\geq v_{2}\geq\cdots\geq
v_{n}$, Lemma 4.3 implies that our algorithm has the same expected reward as
an algorithm that would first sample $Z_{i}=Y_{i}P_{i}$ for all candidates and
then collect the $k$ highest values $v_{i}$ among those candidates with
$Z_{i}=1$. This interpretation is only possible because
$\mathsf{ALG}_{\mathtt{ptk}}$ is committed. The same expressions can be
derived for an algorithm that instead of sampling $Y_{i}$ using DR, samples
$\tilde{Y}_{i}$ with the same marginal probabilities as $Y_{i}$, but
independently. These expressions are useful for showing that our algorithm
outperforms a hypothetical algorithm that decides to interview each candidate
$i$ using the independent indicators $\tilde{Y}_{i}$ instead of the correlated
indicators $Y_{i}$, potentially interviewing $T+1$ candidates. The correlation
induced by the constraint of $T$ interviews on the actual algorithm only works
in our favor.

###### Lemma 4.4

Let $y=(y_{i})_{i\in[n]},x=(x_{ij})_{i\in[n],j\in[J]}$ be a basic feasible
solution of $\textsc{LP}_{\mathtt{ptk}}(I)$ with two fractional components
$i_{1}$ and $i_{2}$. Let $\tilde{Y}_{i}$ be independent Bernoulli random
variables with mean $y_{i}$. Define $\tilde{Z_{i}}=P_{i}\tilde{Y}_{i}$ and
$\tilde{N}_{i}=\min\\{k,\sum_{i=1}^{j}\tilde{Z}_{i}\\}$. Then

$\displaystyle\sum_{i=1}^{n}v_{i}\mathbb{E}\left(Z_{i}\mathbbm{1}\\{N_{i-1}<k\\}\right)\geq\sum_{i=1}^{n}v_{i}\mathbb{E}\left(\tilde{Z}_{i}\mathbbm{1}\\{\tilde{N}_{i-1}<k\\}\right).$
(4)

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
$S\subseteq[n]$ we define the weighted rank function for the $k$-uniform
matroid with weights $v$ as

$v^{*}(S)=\max_{R\subseteq[S],\,|R|\leq k}\sum_{i\in R}v_{i}.$

Both the reward of the independent version of our algorithm and the objective
of $\textsc{LP}_{\mathtt{ptk}}$ can be expressed as expectations of weighted
rank functions of $k$-uniform matroids. We use this together with the
correlation gap results by Yan (2011) to show the main result of the section.

###### Theorem 4.5

For any instance $I\in\mathcal{I}_{\mathtt{ptk}}^{k}$,

$R_{\mathsf{ALG}_{\mathtt{ptk}}}(I)\geq\left(1-\frac{e^{-k}k^{k}}{k!}\right)\textsc{LP}_{\mathtt{ptk}}(I).$

In Section LABEL:sec:tight 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, non-adaptive, committed algorithm whose expected reward will be
at least a factor $(1-e^{-k}k^{k}/k!)$ of the expected reward of the optimal
algorithm. Since the algorithm is non-adaptive and committed, it establishes a
lower bound on how good an approximation factor can be achieved by restricting
to these classes of policies.

###  4.4 Weighted Bernoulli Values and Sequential Offering Problem

ProbeTop-$k$ is closely related to the Sequential Offering problem
($\mathtt{seq}$) studied by Purohit et al. (2019). 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_{i}$ of
accepting an offer and adds a value $r_{i}$ to the firm if she accepts an
offer. The firm can hire at most $k$ candidates and send at most $T$ offers in
total. This model can be captured by ProbeTop-$k$ by considering the special
case of $\mathtt{ptk}$ where the value of candidate $i$ takes value $r_{i}$
with probability $q_{i}$ (representing acceptance of an offer), and 0 with
probability $(1-q_{i})$ (representing a rejection of an offer). The subtlety
making $\mathtt{ptk}$ different from $\mathtt{seq}$ is that policies for
$\mathtt{ptk}$ can reject a candidate $i$ even if they had a realization to
value $r_{i}$, which is not allowed in $\mathtt{seq}$. We show, however, that
$\mathsf{ALG}_{\mathtt{ptk}}$ can be made to hire any candidate when her
realized value is $r_{i}$ without sacrificing performance, therefore making it
an admissible algorithm for the sequential offering model with the same
guarantee.

We can rewrite $\textsc{LP}_{\mathtt{ptk}}$ for this special case as

$\displaystyle\max\quad$ $\displaystyle\sum_{i=1}^{n}r_{i}x_{i}$
$\displaystyle s.t.\quad$ $\displaystyle x_{i}\leq y_{i}q_{i}\,\,\,\,\forall
i\in[n],\quad\sum_{i=1}^{n}y_{i}\leq T,\quad\sum_{i=1}^{n}x_{i}\leq k,\quad
x_{i}\geq 0\,\,\,\,\forall i\in[n],\quad 0\leq y_{i}\leq 1\,\,\,\,\forall
i\in[n].$

where $x_{i}$ is to be interpreted as the probability of hiring the candidate
and $V_{i}=r_{i}$. (We can omit the variable corresponding to $V_{i}=0$ since
it does not weigh in the objective and it can only make the constraints
tighter.) The following lemma will let us restrict
$\mathsf{ALG}_{\mathtt{ptk}}$ to be admissible for the Sequential Offering
problem.

###### Lemma 4.6

There is an optimal solution for $\textsc{LP}_{\mathtt{ptk}}$ in the special
weighted Bernoulli instance with $x_{i}=y_{i}q_{i}$ for all $i\in[n]$.

Recall that after interviewing candidate $i$, $\mathsf{ALG}_{\mathtt{ptk}}$
will hire her with probability $x_{i}/(y_{i}q_{i})$. Therefore, if we restrict
to solutions with $x_{i}=y_{i}q_{i}$, then $\mathsf{ALG}_{\mathtt{ptk}}$ will
hire candidate $i$ with probability 1 if $V_{i}=r_{i}$, making it admissible
for the sequential offering problem.

We can compute

$p_{i}=\frac{x_{i}}{y_{i}}=x_{i}\frac{q_{i}}{x_{i}}=q_{i},\quad
v_{i}=\frac{r_{i}x_{i}}{x_{i}}=r_{i}.$

We can further simplify the LP by removing variables $x_{i}$ and express it in
terms of $p_{i}$ and $v_{i}$, leading to $\textsc{LP}_{\mathtt{seq}}$:

$\displaystyle\textsc{LP}_{\mathtt{seq}}(I)=\max\quad$
$\displaystyle\sum_{i=1}^{n}v_{i}y_{i}p_{i}$ $\displaystyle s.t.\quad$
$\displaystyle\sum_{i=1}^{n}y_{i}\leq T,\quad\sum_{i=1}^{n}y_{i}p_{i}\leq
k,\quad 0\leq y_{i}\leq 1\,\,\,\,\forall i\in[n].$

Being consistent with the previously introduced notation, let
$\mathcal{I}_{\mathtt{seq}}$ be the set of all instances for the sequential
offering problem. Let $\mathcal{I}_{\mathtt{seq}}^{k}$ be the set of all
instances of $\mathtt{seq}$ that have exactly $k$ positions to fill. Let
$\mathsf{ALG}_{\mathtt{seq}}$ be the modified version of
$\mathsf{ALG}_{\mathtt{ptk}}$ that, when faced with instances of Weighted
Bernoulli random variables, modifies the solution of the LP such that the
algorithm is admissible for $\mathtt{seq}$. We have the following corollary of
Theorem 4.5.

###### Corollary 4.7

For any instance $I\in\mathcal{I}_{\mathtt{seq}}^{k}$,
$R_{\mathsf{ALG}_{\mathtt{seq}}}(I)\geq\left(1-\frac{e^{-k}k^{k}}{k!}\right)\textsc{LP}_{\mathtt{seq}}(I)$.

##  5 Parallel Offering

We now turn our focus to the parallel offering model defined in Section 3.2.
We provide an algorithm that achieves a $(1-1/e)$ 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 Subsection 5.2 we present
and analyze our algorithm. In Section 5.3 we study the special case with
identical positions introduced by Purohit et al. (2019) and establish a
connection between the parallel and sequential offering problems. The proofs
and complementary materials from this section can be found in Appendix
LABEL:ap:paral.

###  5.1 Linear program

For an instance $I\in\mathcal{I}_{\mathtt{par}}$, we introduce
$\textsc{LP}_{\mathtt{par}}(I)$, with LP variables $y_{ij}$ for $i\in[n]$ and
$j\in[k]$. Variable $y_{ij}$ is to be interpreted as the probability that
candidate $i$ receives an offer for position $j$. As with
$\textsc{LP}_{\mathtt{ptk}}$, this LP only enforces that the problem’s
constraints are satisfied in expectation.

$\displaystyle\textsc{LP}_{\mathtt{par}}(I)=\max\quad$
$\displaystyle\sum_{j=1}^{k}\sum_{i=1}^{n}v_{ij}y_{ij}p_{ij}$ $\displaystyle
s.t.\quad$ $\displaystyle\sum_{i=1}^{n}y_{ij}\leq T$ $\displaystyle\forall
j\in[k]$ (5) $\displaystyle\sum_{i=1}^{n}y_{ij}p_{ij}\leq 1$
$\displaystyle\forall j\in[k]$ (6) $\displaystyle\sum_{j=1}^{k}y_{ij}\leq 1$
$\displaystyle\forall i\in[n]$ (7) $\displaystyle 0\leq y_{ij}\leq 1$
$\displaystyle\forall(i,j)\in[n]\times[k].$

We start by formally proving that $\textsc{LP}_{\mathtt{par}}$ upper bounds
the expected reward of any algorithm.

###### Lemma 5.1

For any instance $I\in\mathcal{I}_{\mathtt{par}}$,
$\textsc{LP}_{\mathtt{par}}(I)\geq\mathsf{OPT}_{\mathtt{par}}(I)$.

###  5.2 Approximation algorithm

We now present our algorithm for the parallel offering model, which we refer
to as $\mathsf{ALG}_{\mathtt{par}}$. The algorithm first solves
$\textsc{LP}_{\mathtt{par}}$ to produce an optimal solution $y$. With the
solution at hand, the algorithm will round it to obtain a random binary matrix
$Y=(Y_{ij})_{(i,j)\in[n]\times[k]}$. To round our solution here, we use the
dependent rounding scheme developed by Gandhi et al. (2006) that is described
in Appendix 9.2. After the solution is rounded, the algorithm uses the rounded
solution to make a sequential offering list for each position. Specifically,
candidate $i$ is included in the list for position $j$ if $Y_{ij}=1$. The
properties of the depending rounding scheme by Gandhi et al. (2006) combined
with the constraints of $\textsc{LP}_{\mathtt{par}}$ 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, each list is run in parallel, and
the order in which the offers are sent for position $j$ is decreasing in
$v_{ij}$. A pseudo-code for this algorithm can be found in Appendix
LABEL:ap:pseudo.

For the analysis, let $L_{j}$ denote the expected reward collected from list
$j$. Let $L^{*}_{j}=\sum_{i=1}^{n}v_{ij}y_{ij}p_{ij}$, so that the objective
function of $\textsc{LP}_{\mathtt{par}}$ can be expressed as
$\sum_{j=1}^{k}L^{*}_{j}$. We will show that for each position $j$ it holds
that $L_{j}\geq(1-1/e)L^{*}_{j}$. Define $Z_{ij}=P_{ij}Y_{ij}$ and
$\tilde{Z}_{ij}=P_{ij}\tilde{Y}_{ij}$, where $\tilde{Y}_{ij}$ are independent
Bernoulli random variables with mean $y_{ij}$. Let $D_{j}=\\{i:Z_{ij}=1\\}$
and $\tilde{D}_{j}=\\{i:\tilde{Z}_{ij}=1\\}$. Let $v_{j}^{*}(S)=\max_{i\in
S}v_{ij}$. It is clear to see that $L_{j}=\mathbb{E}(v_{j}^{*}(D))$.

The first step for showing the guarantee of $\mathsf{ALG}_{\mathtt{par}}$ 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 Gandhi et al. (2006). The result is formalized in the
following lemma.

###### Lemma 5.2

For all $j\in[k]$,
$\mathbb{E}(v_{j}^{*}(D))\geq\mathbb{E}(v^{*}_{j}(\tilde{D}))$.

In the proof of Lemma 5.2 we only use (P1) and (P3) from the rounding scheme
by Gandhi et al. (2006). These properties are not enough if we want to show
that the dependent rounding outperforms the independent rounding when
selecting the $k\geq 2$ elements with the highest weights (which holds, for
instance, in Lemma 4.4). See LABEL:eg:negCorrelWorseThanIndep in Appendix
LABEL:app:counterexample for a counterexample.

Continuing with the main result, the following lemma will help establish the
desired bound for each list, in which only the single candidate ($k=1$) with
the highest weight will be hired. Both the correlation gap results and the
rounding scheme mentioned in Appendix 9 are used in the analysis.

###### Lemma 5.3

For all $j\in[k]$, $\mathbb{E}(v^{*}_{j}(\tilde{D}))\geq(1-1/e)L_{j}^{*}$.

By combining lemmas 5.2 and 5.3 we obtain the main result of the section.

###### Theorem 5.4

For any instance $I\in\mathcal{I}_{\mathtt{par}}$,
$R_{\mathsf{ALG}_{\mathtt{par}}}(I)\geq(1-1/e)\textsc{LP}_{\mathtt{par}}(I)$.

In Section LABEL:sec:parTight we establish that the bound achieved by our
algorithm is tight.

###  5.3 Identical Positions and Cost of Batching

We now turn our focus to the special case where all positions are identical
(i.e. $v_{ij}=v_{i}$ and $p_{ij}=p_{i}$ for all $i\in[n]$ and $j\in[k]$). For
this case, we can obtain a connection between the sequential offering model
and the parallel offering model through their respective LPs.

Let $I\in\mathcal{I}_{\mathtt{par}}$ be an instance for the parallel offering
model in which all $k$ positions are identical, we have $n$ candidates, and
there are $T$ offering rounds. Construct
$I^{\prime}\in\mathcal{I}_{\mathtt{seq}}$ to be the same instance as $I$
except $kT$ sequential offers can be sent in total. We obtain the following
lemma.

###### Lemma 5.5

$\textsc{LP}_{\mathtt{par}}(I)=\textsc{LP}_{\mathtt{seq}}(I^{\prime})$.

This lemma implies the following corollary, which we refer to as the cost of
batching.

###### Corollary 5.6

For any $I\in\mathcal{I}_{\mathtt{par}}$,
$\mathsf{ALG}_{\mathtt{par}}(I)\geq(1-1/e)\mathsf{OPT}_{\mathtt{seq}}(I^{\prime})$.

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 are not going to be worse than a factor of $(1-1/e)$
from the optimal sequential policy.

##  6 Simultaneous Offering

In this section, we provide our algorithms and analyses for the Simultaneous
Offering problem described in Subsection 3.3. We develop a value-ordered
policy that, when faced with instances where all the values of the candidates
are lower bounded by some $\tau\in(0,1)$, achieves an $\alpha_{k}^{\tau}$
approximation of what any policy could achieve. The algorithm first solves an
LP relaxation, modifies the optimal solution, and uses this modified solution
to decide which candidates will receive offers.

In Subsection 6.1 we introduce value-ordered policies and show that they can
perform arbitrarily poorly if no further assumptions on instances are made. In
Subsection 6.2 we introduce an LP relaxation that is used in our algorithm. In
Subsection 6.3 we introduce our value-ordered policy and its lower bound,
provide an upper bound for how well value-ordered policies can perform, and
characterize the region where these two bounds coincide. The proofs and
complementary materials of this section are located in Appendix
LABEL:ap:simul.

###  6.1 Value-ordered policies

For this problem, we focus on a natural class of policies, which we call
value-ordered policies. Assume that $v_{1}\geq v_{2}\geq\cdots\geq v_{n}$. For
a given $m$, value-ordered policies will send offers to the $m$ candidates
with the highest value (i.e. $S=\\{1,\dots,m\\}$). This family of policies is
practically-motivated, as firms ideally want to make offers to the $m$
highest-value candidates without considering their probabilities of
acceptance. The optimal value-ordered policy also can be obtained efficiently.

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

###### Example 6.1

Consider an instance with $k=1$ and $n=2$. For small $\varepsilon$, candidate
1 has $v_{1}=p_{1}=\varepsilon$, while candidate 2 has
$v_{2}=\varepsilon(1-\varepsilon)$ and $p_{2}=1$. 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 0, for
using $\\{1\\}$ is $\varepsilon^{2}$, and for using $\\{2\\}$ is
$\varepsilon(1-\varepsilon)$. For $\varepsilon<1/2$ 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 $\varepsilon/(1-\varepsilon)$, which can be made arbitrarily small
by making $\varepsilon\to 0$.

This example can be extended to an arbitrary amount of positions $k$, as we do
so in the sequel. The intuition behind the previous example is that when
$\varepsilon$ is small, it means that the value of adding a candidate over
capacity is negligible compared to the cost it will bring, making the capacity
$k$ almost a hard constraint. And although this specific example can be
assuaged by ordering the candidates in descending order of $v_{i}p_{i}$
instead of $v_{i}$, we show that policies based on this alternate ordering
also achieve an arbitrarily poor approximation (see LABEL:eg:sim_EV_ordered in
Appendix LABEL:app:EO_example).

We hereafter focus on analyzing the practically-motivated class of value-
ordered policies under an additional assumption. In order to obtain constant
factor guarantees, we further assume that the values of the candidates are
lower bounded by a parameter $\tau>0$. Let
$\mathcal{I}_{\mathtt{sim}}^{\tau}=\\{I\in\mathcal{I}_{\mathtt{sim}}:v_{i}\geq\tau\,\,\forall
i\in[n]\\}$ be the set of $\tau$-bounded instances. We say that a policy $\pi$
is an $\alpha$-approximation for $\tau$-bounded instances if

$\inf_{I\in\mathcal{I}_{\mathtt{sim}}^{\tau}}\frac{R_{\pi}(I)}{\mathsf{OPT}_{\mathtt{sim}}(I)}\geq\alpha.$

Notice that if $\tau\geq 1$ then the problem is trivial: it is optimal to send
an offer to every candidate. We will therefore restrict our attention to
$\tau\in(0,1)$.

Before we carry on, we define $V_{\mathtt{high}}=\\{i\in[n]:v_{i}>1\\}$ to be
the set of candidates whose value is greater than 1. These are candidates that
we would like to hire even if we know they would violate capacity. We believe
it is important to model such candidates, and to our understanding, there is
no easy way to reduce the problem to one where they do not exist. Allowing for
such candidates essentially makes the number of positions random, as they will
all receive offers but it is uncertain how many would accept.

###  6.2 LP relaxation

In order to obtain approximation factors for value-ordered policies, we
introduce a linear programming relaxation of $\mathsf{OPT}_{\mathtt{sim}}$
which we call $\textsc{LP}_{\mathtt{sim}}$.

$\displaystyle\textsc{LP}_{\mathtt{sim}}(I)=\max_{y,z}\quad$
$\displaystyle\sum_{i\in[n]}v_{i}p_{i}y_{i}+z$ $\displaystyle s.t.\quad$
$\displaystyle z\leq k-\sum_{i\in[n]}p_{i}y_{i},\quad z\leq 0,\quad 0\leq
y_{i}\leq 1\,\,\,\,\forall i\in[n]$

By applying Jensen’s inequality we can show that $\textsc{LP}_{\mathtt{sim}}$
is an upper bound of $\mathsf{OPT}_{\mathtt{sim}}$.

###### Lemma 6.2

For any $I\in\mathcal{I}_{\mathtt{sim}}$,
$\textsc{LP}_{\mathtt{sim}}(I)\geq\mathsf{OPT}_{\mathtt{sim}}(I)$.

For a feasible solution $y$, we say that $\sum_{i\in[n]}y_{i}p_{i}$ is the
“total mass” of the solution. This can be interpreted as the expected amount
of candidates that would be hired if we were to send an offer to each
candidate $i$ with probability $y_{i}$. We proceed to show a property about
optimal solutions of $\textsc{LP}_{\mathtt{sim}}$ that closely relates it to a
value-ordered policy.

###### Lemma 6.3

Let $I\in\mathcal{I}_{\mathtt{sim}}$. There exists an optimal solution $(y,z)$
of $\textsc{LP}_{\mathtt{sim}}(I)$ with an index $j$ such that $y_{i}=1$ for
$1\leq i\leq j-1$, $y_{j}>0$, and $y_{i}=0$ for $j+1\leq i\leq n$.

This lemma allows us to use an optimal solution of
$\textsc{LP}_{\mathtt{sim}}$ to very simply construct a randomized value-
ordered policy. For instance, one could send an offer to each candidate $i$
independently with probability $y_{i}$. This policy randomizes between two
value-ordered policies: sending offers to candidates $\\{1,\dots,j\\}$ or to
candidates $\\{1,\dots,j-1\\}$. Therefore, a lower bound on its performance
immediately implies a lower bound on the performance of the optimal value-
ordered policy. In the following subsection, we introduce
$\mathsf{ALG}_{\mathtt{sim}}^{s}$, a policy that follows the same idea as the
policy just described, but allows a parameter $s\in[0,1]$ to further tune and
improve its performance.

Lemma 6.3 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. The following Lemma also sheds
light on the structure of optimal solutions of $\textsc{LP}_{\mathtt{sim}}$ by
identifying the total mass of an optimal solution depending on the instance
parameters. Since the total mass completely determines an optimal solution,
this result is useful for computing optimal solutions and also for
establishing the guarantees of $\mathsf{ALG}_{\mathtt{sim}}^{s}$.

###### Lemma 6.4

Let $I\in\mathcal{I}_{\mathtt{sim}}$. Let $(y,z)$ be an optimal solution of
$\textsc{LP}_{\mathtt{sim}}(I)$ that satisfies the structure given in Lemma
6.3. Let $P_{\mathtt{high}}=\sum_{i\in V_{\mathtt{high}}}p_{i}$ and
$P_{\mathtt{total}}=\sum_{i\in[n]}p_{i}$. The following holds.

  1. 1.

If $P_{\mathtt{high}}>k$, then $y_{i}=1$ for all $i\in V_{\mathtt{high}}$ and
$y_{i}=0$ otherwise. Therefore, $\sum_{i\in[n]}y_{i}p_{i}=P_{\mathtt{high}}$.

  2. 2.

If $P_{\mathtt{high}}\leq k$, then
$\sum_{i\in[n]}y_{i}p_{i}=\min\\{k,P_{\mathtt{total}}\\}$.

This Lemma gives us a simple way of computing an optimal solution for
$\textsc{LP}_{\mathtt{sim}}$. If $P_{\mathtt{high}}>k$, then set $y_{i}=1$ for
all $\in V_{\mathtt{high}}$, and 0 otherwise. If $P_{\mathtt{high}}\leq k$,
then we can simply “fill” the solution from smallest to largest index, until
either $\sum_{i\in[n]}y_{i}p_{i}=k$ or $y_{i}=1$ for all $i\in[n]$. In either
case, we set $z=\min\\{0,k-\sum_{i\in[n]}y_{i}p_{i}\\}$. This way, there is no
need to solve the LP when implementing $\mathsf{ALG}_{\mathtt{sim}}^{s}$.

###  6.3 Approximation Algorithm and Analysis

Let us introduce our approximation algorithm for $\mathtt{sim}$, which we call
$\mathsf{ALG}_{\mathtt{sim}}^{s}$. The policy takes as input an optimal
solution $y$ of $\textsc{LP}_{\mathtt{sim}}$ and a parameter $s\in[0,1]$. 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 $y^{\prime}$
by truncating $y$ the following way. Let $\kappa=s\sum_{i\in[n]}y_{i}p_{i}$ be
the total mass of the optimal LP solution, scaled down by a factor $s$. Let
$j$ be the first index such that $\sum_{i=1}^{j+1}p_{i}>\kappa$. We let
$y_{i}^{\prime}=1$ for $1\leq i\leq j$, $y_{i}^{\prime}=0$ for $j+2\leq i\leq
n$, and set $y_{j+1}^{\prime}$ such that
$\sum_{i=1}^{j+1}y_{i}^{\prime}p_{i}=\kappa$. After solution $y^{\prime}$ is
constructed, the offers are sent independently to each candidate $i$ with
probability $y_{i}^{\prime}$. Given the structure of $y^{\prime}$,
$\mathsf{ALG}_{\mathtt{sim}}^{s}$ clearly randomizes between two value-ordered
policies: sending offers to candidates 1 through $j$, and sending offers to
candidates 1 through $j+1$. A pseudo-code for this algorithm can be found in
Appendix LABEL:ap:pseudo.

The analysis of $\mathsf{ALG}_{\mathtt{sim}}^{s}$ is done in two cases. One
case is when $\sum_{i\in V_{\mathtt{high}}}p_{i}>k$; that is, if by sending an
offer to all candidates in $V_{\mathtt{high}}$ then we would hire more than
$k$ candidates in expectation. The other case is when $\sum_{i\in
V_{\mathtt{high}}}p_{i}\leq k$. We start by analyzing the latter and then show
that the former case is not harder than the latter for an optimally chosen
parameter $s$.

###### Lemma 6.5

For any $s\in[0,1]$, $\tau\in(0,1)$ and
$I\in\mathcal{I}_{\mathtt{sim}}^{\tau}$ with $\sum_{i\in
V_{\mathtt{high}}}p_{i}\leq k$,

$R_{\mathsf{ALG}_{\mathtt{sim}}^{s}}(I)\geq\left(s-\frac{s}{\tau}+\frac{\mathbb{E}[\min\\{\mathrm{Pois}(sk),k\\}]}{\tau
k}\right)\textsc{LP}_{\mathtt{sim}}(I).$

Setting $s=1$ (i.e. blindly following the LP solution) in the previous Lemma
implies a guarantee of
$1-\frac{1}{\tau}+\frac{\mathbb{E}[\min\\{\mathrm{Pois}(k),k\\}]}{\tau
k}=1-e^{-k}k^{k}/(k!\tau)$. For any $k$ and $\tau$, parameter $s$ can be
optimized to maximize this guarantee, and we let $s^{*}$ denote the optimal
value.

Before stating the main result of the section, we need to take care of the
remaining case where $\sum_{i\in V_{\mathtt{high}}}p_{i}>k$. We show that in
this case, the guarantee obtained by $\mathsf{ALG}^{s^{*}}_{\mathtt{sim}}$
cannot be worse than the previous case where $\sum_{i\in
V_{\mathtt{high}}}p_{i}\leq k$, in which Lemma 6.5 held. A key observation for
analyzing this new case is that as Lemma 6.4 states, all candidates $i$ whose
value $y_{i}$ in the optimal LP solution will have $v_{i}\geq 1$, so
$s^{*}=1$. Indeed, setting $s<1$ can only decrease the chances of sending
offers to candidates in $V_{\mathtt{high}}$, 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 6.6

Let $I=(k,n,p,v)\in\mathcal{I}_{\mathtt{sim}}^{\tau}$ be an instance with
$\sum_{i\in V_{\mathtt{high}}}p_{i}>k$. Then there exists an instance
$I^{\prime}=(k,n,p^{\prime},v)\in\mathcal{I}_{\mathtt{sim}}^{\tau}$ such that
$\sum_{i\in V_{\mathtt{high}}}p_{i}^{\prime}=k$ and

$\frac{R_{\mathsf{ALG}_{\mathtt{sim}}^{s^{*}}}(I)}{\textsc{LP}_{\mathtt{sim}}(I)}\geq\frac{R_{\mathsf{ALG}_{\mathtt{sim}}^{s^{*}}}(I^{\prime})}{\textsc{LP}_{\mathtt{sim}}(I^{\prime})}$

By combining lemmas 6.5 and 6.6 we obtain the main result of this section.

###### Theorem 6.7

For any $\tau\in(0,1)$ and $I\in\mathcal{I}_{\mathtt{sim}}^{\tau}$ we have
$R_{\mathsf{ALG}_{\mathtt{sim}}^{s^{*}}}(I)\geq\alpha_{k}^{\tau}\textsc{LP}_{\mathtt{sim}}(I)$,
where

$\alpha_{k}^{\tau}=\sup_{0\leq s\leq
1}\left(s-\frac{s}{\tau}+\frac{\mathbb{E}[\min\\{\mathrm{Pois}(sk),k\\}]}{\tau
k}\right).$

A remark about our lower bounds is that they hold in a stronger setting.
Indeed, all of our algorithms and analyses only consider candidates $i$ whose
value of $y_{i}$ in the optimal LP Solution is positive. Define
$\mathcal{I}_{\mathtt{sim}}^{\tau,\textsc{LP}}$ as the set of instances for
which all of the candidates with positive LP solution have value bounded from
below by $\tau$. All of our results hold if we change
$\mathcal{I}_{\mathtt{sim}}^{\tau}$ by
$\mathcal{I}_{\mathtt{sim}}^{\tau,\textsc{LP}}$, and clearly
$\mathcal{I}_{\mathtt{sim}}^{\tau}\subseteq\mathcal{I}_{\mathtt{sim}}^{\tau,\textsc{LP}}$.
This illustrates that the guarantee of our algorithms is not damaged by low-
value candidates who are irrelevant because they are never going to be
considered.

We now provide an upper bound for the guarantee that can be achieved by using
value-ordered policies. For this, we construct an instance consisting of
$n=j^{2}+k$ candidates101010We don’t need exactly $j^{2}$ candidates of type 1
for showing the result. Any amount of candidates $\ell_{j}$ with
$\ell_{j}/j\to\infty$ as $j\to\infty$ will suffice., with $j$ being a (large)
integer. The first $j^{2}$ candidates are of type 1, who have $p_{i}=k/j$ and
$v_{i}=\tau+\delta$, where $\delta>0$ is small. The remaining $k$ candidates
are of type 2, who have $p_{i}=1$ and $v_{i}=\tau$. The idea behind this
result is that any optimal value-ordered policy will only send offers to type
1 candidates. On the other hand, the optimal policy does not perform worse
than a policy that send offers to $k$ type 2 candidates and zero type 1
candidates.

###### Theorem 6.8

For any $\varepsilon>0$ and $\tau\in(0,1)$ there exists an instance
$I\in\mathcal{I}_{\mathtt{sim}}^{\tau}$ such that no value-ordered policy can
have an expected reward greater than
$\left(\beta_{k}^{\tau}+\varepsilon\right)\mathsf{OPT}_{\mathtt{sim}}(I)$,
where

$\beta_{k}^{\tau}=\sup_{s\geq
0}\left(s-\frac{s}{\tau}+\frac{\mathbb{E}[\min\\{\mathrm{Pois}(sk),k\\}]}{\tau
k}\right).$

The only difference between the optimization problems defining
$\alpha^{\tau}_{k}$ and $\beta^{\tau}_{k}$ is that the former has the
constraint $s\leq 1$. Neither set of constants has a closed-form value, but
since their objective functions are concave, we can characterize their optimal
solutions using first-order conditions.

###### Proposition 6.9

For $\tau\in(0,1)$, let $s^{*}_{\alpha}$ and $s^{*}_{\beta}$ be optimal
solutions for $\alpha_{k}^{\tau}$ and $\beta_{k}^{\tau}$, respectively. Then
$s^{*}_{\alpha}=\min\\{s^{*}_{\beta},1\\}$ and $s^{*}_{\beta}$ is the solution
of

$\tau=1-e^{-sk}\sum_{j=0}^{k-1}\frac{(sk)^{j}}{j!}.$

The form of $s^{*}_{\alpha}$ is implied by the concavity of the objective
function combined with the constraint that $s\leq 1$. We characterize the
region where $s^{*}_{\beta}\leq 1$, in which $s^{*}_{\alpha}=s^{*}_{\beta}$
and our guarantee is tight.

###### Proposition 6.10

For any $k\in\mathbb{N}$ and $\tau\in(0,1)$ we have we have
$s^{*}_{\alpha}=s^{*}_{\beta}$ if and only if

$\tau\leq 1-e^{-k}\sum_{j=0}^{k-1}\frac{k^{j}}{j!}.$

This condition holds for all $k$ if $\tau\leq 1/2$.

In Appendix LABEL:app:simil:plots we provide plots showing $\alpha_{k}^{\tau}$
and $\beta_{k}^{\tau}$ for several values of $k$ and for $\tau\in(0,1)$.

##  7 Numerical Experiments

In this section, we provide numerical experiments that complement our theory
and allow us to compare the rewards obtained under the three different models
of hiring: $\mathtt{seq}$, $\mathtt{par}$ and $\mathtt{sim}$.

Our experimental setting is based on the one by Purohit et al. (2019). In our
experiments, we sample 50 randomly generated pools of $n=100$ candidates. As
in Purohit et al. (2019), we generate candidates such that there is a negative
correlation between each candidate’s value and their probability of
acceptance, motivated by there being more market competition for the high-
valued candidates. For details about the sampling of candidate pools, see
Appendix LABEL:ap:num_sampling. We also provide results where the sampling of
values and acceptance probabilities is independent in Appendix
LABEL:ap:num_indep.

We implement four heuristics for $\mathtt{seq}$ and one heuristic for
$\mathtt{par}$. The first sequential heuristic is
$\mathsf{ALG}_{\mathtt{seq}}^{\prime}$, a slight variant of
$\mathsf{ALG}_{\mathtt{seq}}$ which is de-randomized, and in the case that the
original algorithm would send less than $T$ offers, it fills those gaps with
candidates with high $v_{i}$. The second heuristic was introduced by Purohit
et al. (2019) and we call it ‘Adaptive sequential’. It corresponds to the
optimal adaptive algorithm that sends offers in decreasing order of $v_{i}$.
Since any non-adaptive algorithm can be improved by sending offers in
decreasing order of $v_{i}$, Adaptive sequential serves as an upper bound for
the performance of any non-adaptive algorithm, including our
$\mathsf{ALG}_{\mathtt{seq}}$. The other two heuristics that we implement for
$\mathtt{seq}$ are what we call the naive non-adaptive policies: ‘Value-
ordered’ ($\mathsf{VO}_{\mathtt{seq}}$) and ‘Expected-value-ordered’
($\mathsf{EO}_{\mathtt{seq}}$). These policies greedily send offers to the
next candidate with the highest $v_{i}$ and $v_{i}p_{i}$, respectively. For
reference, we include the value of $\textsc{LP}_{\mathtt{seq}}$. For
$\mathtt{par}$ we implement $\mathsf{ALG}_{\mathtt{par}}^{\prime}$, a de-
randomized heuristic based on $\mathsf{ALG}_{\mathtt{par}}$.

For $\mathtt{sim}$ we implement three heuristics. The first one is ‘Value-
ordered’ ($\mathsf{VO}_{\mathtt{sim}}$), corresponding to the optimal value-
ordered policy that sends offers to the first $m$ candidates with the highest
$v_{i}$ (and $m$ is optimized). Similarly, ‘Expected-value-ordered’
($\mathsf{EO}_{\mathtt{sim}}$) corresponds to the optimal policy that sends
offers to the first $m$ candidates with the highest $v_{i}p_{i}$ (and $m$ is
optimized). We also implement a greedy heuristic and include the valule of
$\textsc{LP}_{\mathtt{sim}}$ for reference. For implementation details of all
heuristics, see Appendix LABEL:ap:num_algo_description.

Figure 1: Numerical results for negatively correlated $v_{i}$ and $p_{i}$,
averaged over the 50 random candidate pools. The left column shows how the
expected reward changes as the number of offering rounds $T$ increases in the
sequential and parallel offering settings. The right column shows how the
expected reward changes as $1/c$ varies in the simultaneous
setting.121212Recall that $c$ is the penalty for hiring each candidate over
capacity $k$. We make the $x$-axis $1/c$ instead of $c$ so that the plots are
more comparable to the sequential/parallel setting. The top row shows the
results for $k=5$ positions and the bottom row shows the results for $k=10$
positions.

Footnote 12 shows the results obtained for the implemented heuristics.

###  7.1 Insights about Sequential and Parallel Offering

The plots for $\mathtt{seq}$ and $\mathtt{par}$ show how the expected reward
of different heuristics grow as $T$ increases.

##### Difficult values of $T$ for sequential hiring.

A first observation is that intermediate values of $T$ are harder to
approximate, both for the adaptive heuristic and the non-adaptive heuristics.
This can be concluded by observing a higher gap between the heuristics and the
benchmark upper bounds. It comes with no surprise, since extreme values of $T$
have trivial solutions. On one hand, if $T=n$, then the optimal policy is to
send offers to all candidates in decreasing order of $v_{i}$. If $T=k$, then
the optimal policy is to send offers to the $k$ candidates with the highest
$v_{i}p_{i}$. Consequently, $\mathsf{VO}_{\mathtt{seq}}$ is (near-)optimal
when $T$ is large, and $\mathsf{EO}_{\mathtt{seq}}$ is (near-)optimal when $T$
is small. The intermediate values produce more separation in the performance
of different algorithms.

##### Virtue of our non-adaptive sequential policy.

We observe that $\mathsf{ALG}_{\mathtt{seq}}^{\prime}$ outperforms both naive
policies for all values of $T$. Given the constraints in
$\textsc{LP}_{\mathtt{seq}}$, our heuristic
$\mathsf{ALG}_{\mathtt{seq}}^{\prime}$ will behave like Expected-value-ordered
when $T=k$. There is a value of $T$ where the constraint
$\sum_{i\in[n]}y_{i}\leq T$ stops binding, so the LP solution would remain
constant for higher values of $T$, and the output of our algorithm would make
less than $T$ offers. At this point, $\mathsf{ALG}_{\mathtt{seq}}^{\prime}$
includes candidates in decreasing order of $v_{i}$ until $T$ offers are to be
sent, and the policy starts behaving like $\mathsf{VO}_{\mathtt{seq}}$. This
non-adaptive policy based on our LP correctly transitions from
$\mathsf{EO}_{\mathtt{seq}}$ to $\mathsf{VO}_{\mathtt{seq}}$ as $T$ grows, and
strictly dominates them on the difficult, intermediate values of $T$.

##### More positions help the heuristics.

As $k$ becomes larger, our heuristics achieve better performance with respect
to the available benchmarks: a smaller gap can be observed between
$\mathsf{ALG}_{\mathtt{seq}}^{\prime}$ and either the Adaptive heuristic or LP
upper bound. A smaller gap can also be observed between the Adaptive heuristic
and the LP upper bound. This is consistent with our theoretical results, where
the approximation guarantee of our algorithm grows with $k$.

##### Parallel vs. sequential offering.

There is value in the ability to send more offers by sending them in parallel,
and this value increases with $k$. This is natural since parallel algorithms
are allowed to send as many offers as positions available, so the more
available positions in the beginning, the more potential offers there are to
be sent. In fact, when $k$ is small (there are two or three positions) the
firm can gain more value by using a sequential and adaptive policy than by
using a parallel, non-adaptive policy, even with the same amount of allowed
offering rounds $T$. There is a point where $T$ becomes large enough such that
the Adaptive heuristic, $\mathsf{ALG}_{\mathtt{seq}}^{\prime}$ and
$\mathsf{VO}_{\mathtt{seq}}$ outperform our parallel heuristic. This is
because our parallel heuristic balances out the good candidates along $k$
lists, so when a candidate accepts (and no other candidate in her list
receives an offer) many good candidates are left out. With $T$ large enough,
the sequential policies (except $\mathsf{EO}_{\mathtt{seq}}$) are hedged
against this because they have enough time to send offers to all the good
candidates. An interesting direction is to design parallel algorithms that
adaptively choose the next candidates.

###  7.2 Insights about Simultaneous hiring

In the plots for $\mathtt{sim}$ we show how the expected reward of the
implemented heuristics as $1/c$ grows.131313The choice of showing the results
with respect to $1/c$ instead of $c$ is because it allows showing large values
of $c$ while keeping the scale of the graph reasonable. We can use
$1/c\in(0,2]$ to concisely show $c\in[1/2,\infty)$, a range that allows us to
compare the performance of $\mathsf{VO}_{\mathtt{sim}}$ against the
performance of the sequential heuristics.

##### Best policy depends on $c$.

For small values of $c$, $\mathsf{VO}_{\mathtt{sim}}$ outperforms Greedy and
$\mathsf{EO}_{\mathtt{sim}}$, while for large values of $c$, the opposite
occurs. This is natural since a very large value of $c$ is analogous to having
a hard constraint of $k$ on the number of candidates hired. As $c$ becomes
smaller, $\mathsf{VO}_{\mathtt{sim}}$ becomes better since there is room for
error, and sending offers to candidates with high value with the risk of going
over capacity becomes more valuable than hiring lower value candidates with a
lower chance of not going over capacity. There is a value of $c$ low enough
(namely $\min_{i\in[n]}v_{i}$) when all policies agree to send an offer to
every candidate $i\in[n]$.

##### Larger $k$ helps Value-ordered.

We see that if $k=10$, $\mathsf{VO}_{\mathtt{sim}}$ outperforms the other two
heuristics even for larger values of $c$. This can be explained by the fact
that when $k=10$, there is more margin to capture all the high-value
candidates without too much risk of going over capacity.

##### Simultaneous vs. Sequential Offering.

This experiment allows us to compare which values of $T$ and $c$ achieve a
comparable expected reward. For instance, if $k=10$,
$\mathsf{ALG}_{\mathtt{seq}}$ and $\mathsf{VO}_{\mathtt{seq}}$ with $T=30$
time steps achieve rewards comparable to $\mathsf{VO}_{\mathtt{sim}}$ and
Greedy in the simultaneous setting with $c\approx 0.6$. A finer mapping from
$T$ to $c$ can be done if one fixes a specific policy for each setting. Note
that as $c\to\infty$, $\mathsf{EO}_{\mathtt{sim}}$ converges to the same value
as $\mathsf{EO}_{\mathtt{seq}}$ when only $T=k$ offers can be sent, as having
a large value of $c$ is equivalent to $k$ being a hard constraint.

##  8 Conclusions and Future Directions

In this paper, we study several problems motivated by a firm’s hiring
pipelines. For sequential interviewing, sequential offering and parallel
offering we develop LP-based policies that improve the state of the art in
both approximation guarantees, adaptivity gaps and costs of batching. We also
introduce the Simultaneous Offering problem and characterize the performance
of practically motivated value-ordered policies. We provide numerical
experiments that give insights on the factors a firm should take into
consideration when deciding which offering procedure to adopt.

An interesting open direction is to combine the sequential interviewing
problem with the offering problem. This can 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 that has already been interviewed.
Another open direction is to combine the simultaneous offering problem with
the parallel offering problem, as it is implicitly suggested in Purohit et al.
(2019). In this setting, the firm could, at each round, send more offers than
positions remaining and face the risk to hire over capacity (at a cost). One
last future direction to be explored is how the firm should behave in the
different settings when the problem parameters are inaccurate. In particular,
acceptance probabilities can result very difficult to estimate, so developing
algorithms that are robust to these parameters’ misspecification could be of
great interest to firms.

#### Acknowledgements.

The authors thank Rad Niazadeh for pointing us to the highly relevant
reference (Bradac et al. 2019). The authors also thank Aravind Srinivasan for
insightful discussions about negative association and José Correa for
insightful discussions about sequential offering.

## References

  * Agrawal et al. (2010) Agrawal S, Ding Y, Saberi A, Ye Y (2010) Correlation robust stochastic optimization. _Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms_ , 1087–1096 (SIAM).
  * Agrawal et al. (2020) Agrawal S, Sethuraman J, Zhang X (2020) On optimal ordering in the optimal stopping problem. _Proceedings of the 21st ACM Conference on Economics and Computation_ , 187–188.
  * Arnosti and Ma (2021) Arnosti N, Ma W (2021) Tight guarantees for static threshold policies in the prophet secretary problem. _arXiv preprint arXiv:2108.12893_ .
  * Bansal et al. (2012) Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2012) When lp is the cure for your matching woes: Improved bounds for stochastic matchings. _Algorithmica_ 63(4):733–762.
  * Beyhaghi et al. (2021) Beyhaghi H, Golrezaei N, Leme RP, Pál M, Sivan B (2021) Improved revenue bounds for posted-price and second-price mechanisms. _Operations Research_ 69(6):1805–1822.
  * Bradac et al. (2019) Bradac D, Singla S, Zuzic G (2019) (near) optimal adaptivity gaps for stochastic multi-value probing. _arXiv preprint arXiv:1902.01461_ .
  * Chen et al. (2009) Chen N, Immorlica N, Karlin AR, Mahdian M, Rudra A (2009) Approximating matches made in heaven. _International Colloquium on Automata, Languages, and Programming_ , 266–278 (Springer).
  * Cominetti et al. (2010) Cominetti R, Correa JR, Rothvoß T, Martín JS (2010) Optimal selection of customers for a last-minute offer. _Operations research_ 58(4-part-1):878–888.
  * Esfandiari et al. (2017) Esfandiari H, Hajiaghayi M, Liaghat V, Monemizadeh M (2017) Prophet secretary. _SIAM Journal on Discrete Mathematics_ 31(3):1685–1701.
  * Fu et al. (2018) Fu H, Li J, Xu P (2018) A ptas for a class of stochastic dynamic programs. _arXiv preprint arXiv:1805.07742_ .
  * Gallego and Segev (2022) Gallego G, Segev D (2022) A constructive prophet inequality approach to the adaptive probemax problem. _arXiv preprint arXiv:2210.07556_ .
  * Gallego and Topaloglu (2019) Gallego G, Topaloglu H (2019) _Revenue management and pricing analytics_ , volume 209 (Springer).
  * Gandhi et al. (2006) Gandhi R, Khuller S, Parthasarathy S, Srinivasan A (2006) Dependent rounding and its applications to approximation algorithms. _Journal of the ACM (JACM)_ 53(3):324–360.
  * Gupta and Nagarajan (2013) Gupta A, Nagarajan V (2013) A stochastic probing problem with applications. _International Conference on Integer Programming and Combinatorial Optimization_ , 205–216 (Springer).
  * Gupta et al. (2016) Gupta A, Nagarajan V, Singla S (2016) Algorithms and adaptivity gaps for stochastic probing. _Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms_ , 1731–1747 (SIAM).
  * Gupta et al. (2017) Gupta A, Nagarajan V, Singla S (2017) Adaptivity gaps for stochastic probing: Submodular and xos functions. _Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms_ , 1688–1702 (SIAM).
  * Hill (1983) Hill T (1983) Prophet inequalities and order selection in optimal stopping problems. _Proceedings of the American Mathematical Society_ 88(1):131–137.
  * Kleinberg and Weinberg (2012) Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. _Proceedings of the forty-fourth annual ACM symposium on Theory of computing_ , 123–136.
  * Krengel and Sucheston (1977) Krengel U, Sucheston L (1977) Semiamarts and finite values. _Bulletin of the American Mathematical Society_ 83(4):745–747.
  * Krengel and Sucheston (1978) Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. _Probability on Banach spaces_ 4:197–266.
  * Mitzenmacher and Upfal (2017) Mitzenmacher M, Upfal E (2017) _Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis_ (Cambridge university press).
  * Purohit et al. (2019) Purohit M, Gollapudi S, Raghavan M (2019) Hiring under uncertainty. _International Conference on Machine Learning_ , 5181–5189 (PMLR).
  * Samuel-Cahn (1984) Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. _the Annals of Probability_ 1213–1216.
  * Segev and Singla (2021) Segev D, Singla S (2021) Efficient approximation schemes for stochastic probing and prophet problems. _Proceedings of the 22nd ACM Conference on Economics and Computation_ , 793–794.
  * Yan (2011) Yan Q (2011) Mechanism design via correlation gap. _Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms_ , 710–719 (SIAM).

##  9 Useful Known Results

In this section we provide some concepts and known results that will be used
in our algorithms and analyses. We start by defining weighted rank functions
for $k$-uniform matroids, which have a close connection to both the expected
rewards of our algorithms and our LP benchmarks. We use correlation gaps for
this family of functions to relate these two quantities. We also review the
dependent rounding scheme developed by Gandhi et al. (2006), which we use both
in the implementation of our algorithms and as a tool for analysis.

###  9.1 Weighted rank functions and Correlations Gaps

Let $\\{w_{i}\\}_{i\in[n]}$ be a set of weights and $D\subseteq[n]$. Define
the weighted rank function for the $k$-uniform matroid
$w^{*}:2^{[n]}\to[0,\infty)$ as

$w^{*}(D):=\max_{R\subseteq D,|R|\leq k}\sum_{i\in R}w_{i}.$

Loosely speaking, the reward obtained by our algorithms can be expressed as
weighted rank functions of $k$-uniform matroids. Here, $D$ is to be
interpreted as the set of candidates eligible for hire, the weights are to be
interpreted as the expected reward collected from each candidate conditional
on being eligible, and the weighted rank function selects the $k$ highest
rewards from the set $D$.

Let $D\sim\mathcal{D}$, with $\mathcal{D}$ a distribution over $2^{[n]}$, and
$q_{i}=\mathbb{P}(i\in D)$. Let $\tilde{D}\sim\mathcal{I}(\mathcal{D})$, where
$\mathcal{I}(\mathcal{D})$ is a distribution over $2^{[n]}$ in which each
$i\in D$ independently with probability $q_{i}$. The correlation gap of a set
function $f:2^{[n]}\to[0,\infty)$ is defined by

$\sup_{\mathcal{D}}\frac{\mathbb{E}_{D\sim\mathcal{D}}(f(D))}{\mathbb{E}_{D\sim\mathcal{I}(\mathcal{D})}(f(D))}.$

This concept was first formalized by Agrawal et al. (2010). In words, it
quantifies how much we can win by correlating the outcome of $\\{i\in D\\}$
for $i\in[n]$ while maintaining the marginal probabilities. We use a result
from Yan (2011) concerning the correlation gap of weighted rank functions for
$k$-uniform matroids.

######  Proposition 9.1 (Lemma 4.4 from (Yan 2011))

For any $n,k\geq 1$, the correlation gap of the weighted rank function of a
$k$-uniform matroid of size $n$ is at most $(1-\frac{e^{-k}k^{k}}{k!})^{-1}$.

###  9.2 GKPS dependent rounding

Gandhi et al. (2006) developed a dependent rounding scheme that we use for
establishing our results. This dependent rounding scheme receives as an input
a bipartite graph $(A,B,E)$ with weights $x_{ij}\in[0,1]$ for all edges
$(i,j)\in E$. The output is, for each edge, a rounded binary number
$X_{ij}\in\\{0,1\\}$. For any vertex $i\in A$, define the fractional degree
$\ell_{i}=\sum_{j:(i,j)\in E}x_{ij}$. Analogously, for $j\in B$ define
$\ell_{j}=\sum_{i:(i,j)\in E}x_{ij}$. The outputs satisfy the following three
properties:

  * (P1)

Marginal distribution: $E(X_{ij})=x_{ij}$ for every $(i,j)\in E$,

  * (P2)

Degree preservation: with probability 1 it holds that $\sum_{j:(i,j)\in
E}X_{ij}\in\\{\lfloor\ell_{i}\rfloor,\lceil\ell_{i}\rceil\\}$ for all $i\in A$
and $\sum_{i:(i,j)\in
E}X_{ij}\in\\{\lfloor\ell_{j}\rfloor,\lceil\ell_{j}\rceil\\}$ for all $j\in
B$,

  * (P3)

Negative correlation: For any vertex $i\in A\cup B$, any subset $S$ of edges
incident in $i$ and any $b\in\\{0,1\\}$, it holds that

$\mathbb{P}\left(\underset{e\in
S}{\bigcap}\\{X_{e}=b\\}\right)\leq\underset{e\in
S}{\prod}\mathbb{P}(X_{e}=b).$

For the special case when the bipartite graph is a star graph (i.e.
$A=[n],|B|=1$) the input are simply weights $x_{i}\in[0,1]$ for all $i\in[n]$,
and the negative correlation property can be stated as: for any subset
$M\subseteq[n]$ and any $b\in\\{0,1\\}$ it holds that

$\mathbb{P}\left(\underset{i\in
M}{\bigcap}\\{X_{i}=b\\}\right)\leq\underset{i\in
M}{\prod}\mathbb{P}(X_{i}=b).$

##  10 Proofs of Section 4

###  10.1 Proof of Lemma 4.1

###### Proof 10.1

Proof. Consider any algorithm and let $Y_{i}$ be the indicator of candidate
$i$ getting an interview and $X_{ij}$ the indicator of $i$ being hired and
$V_{i}=r_{j}$. Also let $Q_{ij}$ be the indicator of $V_{i}=r_{j}$. We will
show that $x_{ij}=\mathbb{E}(X_{ij})$ and $y_{i}=\mathbb{E}(Y_{i})$ is
feasible, and that the objective function is equal to the expected reward of
the algorithm.

In order to hire a candidate $i$ with $V_{i}=r_{j}$, we need to interview the
candidate and that the candidate has value $r_{j}$. This translates to
$X_{ij}\leq Y_{i}Q_{ij}$, and by taking expectation and using that $Y_{i}$ and
$Q_{ij}$ are independent we get constraint (1). The algorithm can interview at
most $T$ candidates, so $\sum_{t}Y_{i}\leq T$. Again taking expectation we get
constraint (2). The algorithm can hire at most $k$ candidates, so
$\sum_{ij}X_{ij}\leq k$, by taking expectation we get constraint (3). The
remaining constraints are clearly satisfied.

Finally, we have that the reward of the algorithm equals
$\sum_{i,j}X_{ij}r_{j}$, so the expected reward of the algorithm is equal to
the objective function of the linear program.∎

###  10.2 Proof of Lemma 4.2