Selection and Ordering Policies for Hiring Pipelines via Linear Programming Boris Epstein

2025-05-03 0 0 1.02MB 62 页 10玖币

侵权投诉

Selection and Ordering Policies for Hiring Pipelines

via Linear Programming

Boris Epstein

Graduate School of Business, Columbia University, New York, NY 10027, bepstein25@gsb.columbia.edu

Will Ma

Graduate School of Business, Columbia University, New York, NY 10027, wm2428@gsb.columbia.edu

Motivated by hiring pipelines, we study three selection and ordering problems in which applicants for a

ﬁnite set of positions must be interviewed or sent oﬀers. There is a ﬁnite time budget for interviewing/sending

oﬀers, and every interview/oﬀer is followed by a stochastic realization of discovering the applicant’s quality

or acceptance decision, leading to computationally challenging problems. In the ﬁrst problem, we study

sequential interviewing and show that a computationally tractable, non-adaptive policy that must make oﬀers

immediately after interviewing is near-optimal, assuming oﬀers are always accepted. We further show how

to use this policy as a subroutine for obtaining a PTAS. In the second problem, we assume that applicants

have already been interviewed but only accept oﬀers with some probability; we develop a computationally

tractable policy that makes oﬀers for the diﬀerent 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 oﬀers

one by one. In the third problem, we introduce a parsimonious model of overbooking where all oﬀers must

be 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 uniﬁed approach to three diﬀerent hiring problems, based on linear program-

ming. Our results in the ﬁrst two problems generalize and improve the existing guarantees due to Purohit

et al. (2019) 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 diﬀerent settings of making oﬀers to candidates (sequentially, in parallel, or si-

multaneously), providing insight into when a ﬁrm should favor each one.

arXiv:2210.04059v3 [cs.DS] 27 Oct 2023

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 eﬃcient and timely recruitment process can be challenging in practice.

Several diﬃculties 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 ﬁrm making a call for applications. An application

usually consists of a resume and potential complementary materials. Based on this (imperfect)

information, the ﬁrm 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. That is, there is not enough time to interview every single applicant, and the

ﬁrm 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

ﬁrm must send oﬀers to the candidates it wishes to hire, given a limited set of positions. However,

there are many possible ways to send oﬀers to candidates. The ﬁrst natural approach would be

to sequentially send oﬀers to candidates. By this we mean: send an oﬀer, wait for the response

of the candidate, and (if there is still a position available) carry on with the next oﬀer. As in the

interviewing process, the order in which the oﬀers are sent becomes a relevant decision. A second

approach, applicable only to a ﬁrm hiring more than one person, is to save time by sending oﬀers

in parallel. This means, for each position remaining to ﬁll: send an oﬀer, wait for the response

of the candidate, and (if still unﬁlled) carry on with subsequent oﬀers. The ﬁnal approach, which

may be desirable under a tight timeline or to avoid revealing preferences among the candidates

sent oﬀers, is to send all oﬀers 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 diﬀerent modes of sending oﬀers, we

study three diﬀerent models of hiring processes that build oﬀ existing work.

First model: sequential interviewing, a.k.a. ProbeTop-k.In the ﬁrst model, we assume

that the ﬁrm has to hire up to kpeople from a pool of napplicants. Each applicant has a random

value unknown to the ﬁrm carrying out the hiring process. The ﬁrm has access to distributional

knowledge of these values coming from the applicants’ resumes and complementary material sub-

mitted. The ﬁrm can interview applicants to ﬁnd out the realization of their values, but there is

a limit of Ton the number of interviews conducted. The realization of the value of the applicant

becomes known to the ﬁrm immediately after carrying out the interview. We note that this re-

alization should be interpreted as the applicant’s expected value to the ﬁrm given the interview

(and conditional on them accepting the oﬀer). We treat this value as deterministic, which does

not lose generality for a risk-neutral ﬁrm that maximizes its expectation. We further assume that

realizations from interviews are independent across applicants. After all interviews are carried out,

the ﬁrm can choose the best kinterviewed candidates to be hired, who are assumed to accept their

oﬀers with probability 1. The goal of the ﬁrm is to maximize the expected sum of values of the

hired personnel. This problem is exactly the ProbeTop-kproblem, as described in Fu et al. (2018).

In this problem, we can further distinguish between diﬀerent classes of policies. First, we distin-

guish between adaptive and non-adaptive policies. Adaptive policies can decide the order of the

interviews on the ﬂy, choosing who to interview next depending on the outcomes of previous inter-

views. Non-adaptive policies, in contrast, have to ﬁx an interview order before the process starts,

which although restrictive, is attractive from an ease-of-implementation perspective. We also dis-

tinguish between committed and non-committed policies. Committed policies have to irrevocably

decide whether to hire each candidate immediately after interviewing them and discovering their

value. Non-committed policies, in contrast, can carry out all interviews and choose the khighest

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 oﬀers from competing ﬁrms in

the meantime. We are interested in bounds on how costly it is to restrict the ﬁrm to use policies that

are non-adaptive and committed. The former is quantiﬁed in the literature by the widely studied

notion of adaptivity gap: the worst-case ratio between the performance of general policies vs. algo-

rithms 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.

Relation to Free-Order Prophets. The Free-Order Prophet Inequality problem is the special case

of ProbeTop-kwhere T=nand only committed policies are allowed. (When T=n, the constraint

of Tinterviews is not binding, and hence non-committed 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 koverall highest-valued candidates. We note

that such a benchmark is too powerful to compare against in our more general problem if nis much

larger than Tsince the benchmark sees all nrealizations while the algorithm can only interview T

applicants. This is why in our general ProbeTop-kproblem, we compare to an optimal (adaptive,

non-committed) algorithm that is still bound by Tinterviews that must be decided without any

prophetic information, making our comparison diﬀerent from prophet inequalities.

Relation to Sequential Oﬀering. In the Sequential Oﬀering model of Purohit et al. (2019), ap-

plicants are assumed to have already been interviewed but have uncertainty about whether they

accept an oﬀer. The ﬁrm knows, for each candidate, how likely it is that they will accept an oﬀer,

and the value they add to the ﬁrm, should they accept. The ﬁrm has time to send at most Toﬀers

and wants to maximize the expected total value of up to kcandidates who accept their oﬀers. This

setting is closely related to the special case of ProbeTop-kwith 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 subtle diﬀerence is that an

accepted oﬀer cannot be withdrawn by the ﬁrm in the Sequential Oﬀering model, whereas in the

ProbeTop-kmodel, the ﬁrm can turn down a candidate even if their value turns out to be positive.

We will show that our algorithm satisﬁes properties that makes it admissible for this Sequential

Oﬀering problem too, and improve upon the results of Purohit et al. (2019).

Second model: Parallel Oﬀering. We also study a Parallel Oﬀering model, in which a ﬁrm

again has to hire people to ﬁll kpositions. However, we now allow for heterogeneous positions,

where a candidate may have diﬀerent potential values for diﬀerent job positions. We assume that

all interviews have already been conducted, leaving us with a pool of ndesirable candidates. After

conducting all interviews the ﬁrm 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 oﬀer for each of the

available positions. The ﬁrm must now decide how to send oﬀers in Tparallel oﬀering rounds.

At each round, the ﬁrm can send an oﬀer for each of the positions that have not yet been ﬁlled

by a candidate. When a candidate receives an oﬀer, they can either accept or reject it, with the

assumption that they cannot receive an oﬀer for another position if they rejects it (and hence

candidates do not try to anticipate oﬀers they might receive later). The goal of the ﬁrm is to

maximize the expected sum of values of hired candidates. We develop a non-adaptive algorithm

that can be computed eﬃciently and performs competitively in comparison to adaptive and even

relaxed sequential algorithms.

This model generalizes a parallel oﬀering model also introduced in Purohit et al. (2019), which

is similar but has kidentical instead of heterogeneous positions. Our Parallel Oﬀering model is not

only more general, but we also derive stronger performance guarantees.

Third model: Simultaneous Oﬀering. Finally, we study the Simultaneous Oﬀering model,

again for a ﬁrm hiring to ﬁll kpositions. As in the Parallel Oﬀering model, the ﬁrm has already

conducted all interviews, resulting in a pool of ncandidates for which it knows how valuable each

candidate is to the ﬁrm and how likely each candidate is to accept an oﬀer. The ﬁrm must decide

on a subset of candidates who will receive an oﬀer (all at the same time). This subset can be of

any size, so a possible outcome is that more than kcandidates accept an oﬀer. If that is the case,

the ﬁrm must pay a penalty for each candidate who accepted an oﬀer beyond the capacity k. This

penalty can be thought of as the cost of withdrawing an oﬀer, or the cost of creating a new position

in the ﬁrm. We analyze the performance of value-ordered policies, which send oﬀers 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.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

SelectionandOrderingPoliciesforHiringPipelinesviaLinearProgrammingBorisEpsteinGraduateSchoolofBusiness,ColumbiaUniversity,NewYork,NY10027,bepstein25@gsb.columbia.eduWillMaGraduateSchoolofBusiness,ColumbiaUniversity,NewYork,NY10027,wm2428@gsb.columbia.eduMotivatedbyhiringpipelines,westudythreeselecti...

展开>> 收起<<

Selection and Ordering Policies for Hiring Pipelines via Linear Programming Boris Epstein.pdf

共62页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Selection and Ordering Policies for Hiring Pipelines via Linear Programming Boris Epstein

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: