Many industries, including the NFL with the Rooney Rule and law firms with the Mansfield Rule, have adopted interview-stage diversity interventions requiring a minimum representation of disadvantaged groups in the interview set. However, the effectiveness of such policies remains inconclusive. In light of this, we develop a framework of a two-stage hiring process, where rational firms, with limited interview and hiring capacities, aim to maximize the match value of their hires. The labor market consists of two equally sized social groups, m and w, with identical ex-post match value distributions. Match values are revealed only post-interview, while interview decisions rely on partially informative pre-interview scores. Pre-interview scores are more informative for group m, while interviews reveal more for group w; as a result, if firms could interview all candidates, both groups would be equally hired. However, due to limited interview capacity and information asymmetry, we show that requiring equal representation in the interview stage does not translate into equal representation in the hiring outcome, even though interviews are more informative for group w. In certain regimes, with or without intervention, a firm may interview more group w candidates but still hire fewer. At an individual level, we show that strong candidates from both groups benefit from the intervention as the candidate-level competition weakens. For borderline candidates, only group w candidates gain at the expense of group w. To understand the impact of non-universal interview-stage interventions on the market, we study a model with two vertically differentiated firms, where only the top firm adopts the intervention. We characterize the unique equilibrium and demonstrate potentially negative effects: we show that in certain regimes the lower firm hires fewer group w candidates due to increased firm-level competition for them, and further find examples where overall fewer group w candidates are hired across the market. At an individual level, while superstar candidates in both groups benefit, surprisingly the impact on borderline candidates may reverse: the lower firm may replace borderline group w candidates with borderline group m candidates in its interview set, effectively reducing the chance of those borderline group w candidates being hired. Overall, our findings highlight challenges in diversifying the labor market at early hiring stages due to information asymmetry, filtering, and competition. Beyond our context, our natural framework of a market with two-stage hiring may be of independent interest.

Motivated by the challenges in last-mile delivery operations, we consider a natural dynamic staffing problem in which a decision-maker sequentially hires staff over a finite time horizon to meet an unknown target demand at the end. The decision-maker also receives a sequence of predictions about the demand that become increasingly more accurate over time. Consequently, the decision-maker prefers to delay hiring decisions to avoid overstaffing. However, workers' availability decreases over time, resulting in a fundamental trade-off between securing staff early (thus risking overstaffing) versus hiring later based on more accurate predictions (but risking understaffing).

Motivated by our collaboration with a major refugee resettlement agency in the U.S., we study a dynamic matching problem where each new arrival (a refugee case) must be matched immediately and irrevocably to one of the static resources (a location with a fixed annual quota). In addition to consuming the static resource, each case requires post-allocation services from a server, such as a translator. Given the uncertainty in service time, a server may not be available at a given time, thus we refer to it as a dynamic resource. Upon matching, the case will wait to avail service in a first-come-first-serve manner. Bursty matching to a location may result in undesirable congestion at its corresponding server. Consequently, the central planner (the agency) faces a dynamic matching problem with an objective that combines the matching reward (captured by pair-specific employment outcomes) with the cost for congestion for dynamic resources and over-allocation for the static ones. Motivated by the observed fluctuations in the composition of refugee pools across the years, we aim to design algorithms that do not rely on distributional knowledge. We develop learning-based algorithms that are asymptotically optimal in certain regimes, easy to interpret, and computationally fast. Our design is based on learning the dual variables of the underlying optimization problem; however, the main challenge lies in the time-varying nature of the dual variables associated with dynamic resources. Our theoretical development brings together techniques from Lyapunov analysis, adversarial online learning, and stochastic optimization. On the application side, when tested on real data from our partner agency, our method outperforms existing ones, making it a viable candidate for replacing the current practice upon experimentation.

Motivated by our collaboration with Food Rescue U.S. (FRUS), a food recovery organization that relies on volunteers to complete recurring tasks, we study how crowdsourcing platforms can use commitment to promote growth and engagement. Despite reducing match uncertainty, high levels of commitment can decrease the probability of forming new matches in the spot market, which in turn can suppress growth. To better understand this trade-off, we develop a model for two-sided random markets which repeatedly match volunteers with tasks. Our model incorporates match uncertainty as well as the negative impact of failing to match on future engagement. We study the optimal level of commitment to maximize the total discounted number of matches.

Two-sided platforms rely on their recommendation algorithms to help their visitors successfully find a match. However, on platforms such as VolunteerMatch - which has facilitated tens of millions of connections between volunteers and nonprofits - a sizable fraction of website traffic arrives directly to a nonprofit's volunteering page via an external link, thus bypassing the platform's recommendation algorithm. We study how such platforms should account for this external traffic in the design of their recommendation engines, given the goal of maximizing the total number of successful matches. We model the platform's problem as a special case of online matching with stochastic rewards, where (using VolunteerMatch as a motivating example) volunteers arrive sequentially and (probabilistically) match with one opportunity, each of which has finite need for volunteers. In our framework, external traffic is interested only in their targeted opportunity; in contrast, internal traffic may be interested in many opportunities, and the platform's online algorithm selects which opportunity to recommend. In evaluating the performance of different algorithms, we take a worst-case analysis approach, yet we refine the notion of the competitive ratio by parameterizing it based on the amount of external traffic. After demonstrating the shortcomings of a commonly-used algorithm which is optimal in the absence of external traffic, we introduce a new algorithm - Adaptive Capacity (AC) - which accounts for matches differently based on whether they originate from internal or external traffic. We establish a lower bound on AC's competitive ratio that is increasing in the amount of external traffic, and we compare our lower bound to a parameterized upper bound on the competitive ratio of any online algorithm. We find that (in certain parameter regimes) AC is near-optimal regardless of the amount of external traffic, even though it does not know this amount a priori. Our analysis utilizes a path-based, pseudo-rewards approach, which we further generalize to settings where the platform can recommend a ranked set of opportunities. Beyond our theoretical results, we demonstrate the strong performance of AC in a case study motivated by VolunteerMatch data.

In many online platforms, customers' decisions are substantially influenced by product rankings as most customers only examine a few top-ranked products. Concurrently, such platforms also use the same data corresponding to customers' actions to learn how these products must be ranked or ordered. These interactions in the underlying learning process, however, may incentivize sellers to artificially inflate their position by employing fake users, as exemplified by the emergence of click farms. Motivated by such fraudulent behavior, we study the ranking problem of a platform that faces a mixture of real and fake users who are indistinguishable from one another. We first show that existing learning algorithms---that are optimal in the absence of fake users---may converge to highly sub-optimal rankings under manipulation by fake users. To overcome this deficiency, we develop efficient learning algorithms under two informational environments: in the first setting, the platform is aware of the number of fake users, and in the second setting, it is agnostic to the number of fake users. For both these environments, we prove that our algorithms converge to the optimal ranking, while being robust to the aforementioned fraudulent behavior; we also present worst-case performance guarantees for our methods, and show that they significantly outperform existing algorithms. At a high level, our work employs several novel approaches to guarantee robustness such as: (i) constructing product-ordering graphs that encode the pairwise relationships between products inferred from the customers' actions; and (ii) implementing multiple levels of learning with a judicious amount of bi-directional cross-learning between levels. Overall, our results indicate that online platforms can effectively combat fraudulent users without incurring large costs by designing new learning algorithms that guarantee efficient convergence even when the platform is completely oblivious to the number and identity of the fake users.

We study the design of a decentralized two-sided matching market in which agents' search is guided by the platform. Each agent is of one of finitely many types and has (potentially random) preferences drawn from known type-specific distributions. Equipped with such distributional knowledge, the platform guides the search process by determining the meeting rate between each pair of types from the two sides. Meanwhile, agents strategically accept or reject the potential partners whom they meet. Focusing on when agents have symmetric pairwise preferences in a continuum model, we first characterize the unique stationary equilibrium that arises given a feasible set of meeting rates. We then introduce the platform's optimal directed search problem, which involves optimizing meeting rates to maximize equilibrium social welfare. We show that incentive issues arising from congestion and cannibalization make the design problem fairly intricate. Nonetheless, we develop an efficiently computable solution whose corresponding equilibrium achieves at least 1/4 of the optimal social welfare. Our directed search design is simple and easy-to-implement, as its corresponding bipartite graph consists of disjoint stars. Furthermore, our solution implies that, with careful search design, the platform can substantially limit choice and yet induce an equilibrium with approximately optimal welfare. Finally, we show that approximation is likely the best we can hope for by establishing that the problem of designing optimal directed search is NP-hard to approximate beyond a certain constant factor.

We study the allocative challenges that governmental and nonprofit organizations face when tasked with equitable and efficient rationing of a social good among agents whose needs (demands) realize sequentially and are possibly correlated. As one example, early in the COVID-19 pandemic, the Federal Emergency Management Agency faced overwhelming, temporally scattered, a priori uncertain, and correlated demands for medical supplies from different states. In such contexts, social planners aim to maximize the minimum fill rate across sequentially arriving agents, where each agent's fill rate is determined by an irrevocable, one-time allocation. For an arbitrarily correlated sequence of demands, we establish upper bounds on the expected minimum fill rate (ex-post fairness) and the minimum expected fill rate (ex-ante fairness) achievable by any policy. Our upper bounds are parameterized by the number of agents and the expected demand-to-supply ratio, yet we design a simple adaptive policy called projected proportional allocation (PPA) that simultaneously achieves matching lower bounds for both objectives (ex-post and ex-ante fairness), for any set of parameters. Our PPA policy is transparent and easy to implement, as it does not rely on distributional information beyond the first conditional moments. Despite its simplicity, we demonstrate that the PPA policy provides significant improvement over the canonical class of non-adaptive target-fill-rate policies. We complement our theoretical developments with a numerical study motivated by the rationing of COVID-19 medical supplies based on a standard SEIR modeling approach that is commonly used to forecast pandemic trajectories. In such a setting, our PPA policy significantly outperforms its theoretical guarantee as well as the optimal target-fill-rate policy.

Social services often face the challenge of congestion due to their limited capacity relative to their demand. The congestion partly stems from the inclusionary intent of such services: a toll-free road is available to everyone, even those able to afford alternative tolled ones. A broad range of low- and middle-income households are eligible to apply for public housing. How can a social service provider reduce congestion and thus the efficiency loss associated with service delay? In this context, the two controls commonly used for managing congestion, pricing and centralized admission control, are inapplicable due to fairness and implementation considerations. However, the service provider may have control over the information about the system state that it shares with the users. Local traffic managers and public housing authorities have accurate information about the level of congestion for their corresponding services. As such, the service provider can leverage this informational advantage to persuade some of those with lower needs to forgo the service and reduce congestion in the system. In this paper, we study how effective such an informational lever is.

On online platforms, consumers face an abundance of options that are displayed in the form of a position ranking. Only products placed in the first few positions are readily accessible to the consumer, and she needs to exert effort to access more options. For such platforms, we develop a two-stage sequential search model where in the first stage, the consumer sequentially screens positions to observe the preference weight of the products placed in them and forms a consideration set. In the second stage, she observes the additional idiosyncratic utility that she can derive from each product and chooses the highest-utility product within her consideration set. For this model, we first characterize the optimal sequential search policy of a welfare-maximizing consumer. We then study how platforms with different objectives should rank products. We focus on two objectives: (i) maximizing the platform's market share and (ii) maximizing the consumer's welfare. Somewhat surprisingly, we show that ranking products in decreasing order of their preference weights does not necessarily maximize market share or consumer welfare. Such a ranking may shorten the consumer's consideration set due to the externality effect of high-positioned products on low-positioned ones, leading to insufficient screening. We then show that both problems---maximizing market share and maximizing consumer welfare---are NP-complete. We develop novel near-optimal polynomial-time ranking algorithms for each objective. Further, we show that even though ranking products in decreasing order of their preference weights is suboptimal, such a ranking enjoys strong performance guarantees for both objectives. We complement our theoretical developments with numerical studies using synthetic data in which we show (1) that heuristic versions of our algorithms that do not rely on model primitives perform well and (2) that our model can be effectively estimated using a maximum likelihood estimator.

Nonprofit crowdsourcing platforms such as food recovery organizations rely on volunteers to perform time-sensitive tasks. Thus, their success crucially depends on efficient volunteer utilization and engagement. To encourage volunteers to complete a task, platforms use nudging mechanisms to notify a subset of volunteers with the hope that at least one of them responds positively. However, since excessive notifications may reduce volunteer engagement, the platform faces a trade-off between notifying more volunteers for the current task and saving them for future ones. Motivated by these applications, we introduce the online volunteer notification problem, a generalization of online stochastic bipartite matching where tasks arrive following a known time-varying distribution over task types. Upon arrival of a task, the platform notifies a subset of volunteers with the objective of minimizing the number of missed tasks. To capture each volunteer's adverse reaction to excessive notifications, we assume that a notification triggers a random period of inactivity, during which she will ignore all notifications. However, if a volunteer is active and notified, she will perform the task with a given pair-specific match probability that captures her preference for the task. We develop two online randomized policies that achieve constant-factor guarantees which are close to the upper-bounds we establish for the performance of any online policy. Our policies as well as hardness results are parameterized by the minimum discrete hazard rate of the inter-activity time distribution. The design of our policies relies on two modifications of an ex-ante feasible solution: (1) properly scaling down the notification probability prescribed by the ex-ante solution, and (2) sparsifying that solution. Further, in collaboration with Food Rescue U.S., a volunteer-based food recovery platform, we demonstrate the effectiveness of our policies by testing them on the platform's data from various locations across the U.S.

We study dynamic matching in an infinite-horizon stochastic networked market, in which some agents are a priori more difficult to match than others. Agents have compatibility-based preferences and can match either bilaterally, or indirectly through chains. We study the effect matching technologies and matching policies have on efficiency in markets with different compositions of hard and easy-to-match agents. First, we analyze myopic matching policies and identify a strong connection between market thickness and the efficiency driven by the matching technology. We show that when "hard-to-match" agents join the market more frequently than "easy-to-match" ones, moving from bilateral matchings to chains significantly increases efficiency. Otherwise, the difference between matching bilaterally or through a chain is negligible. Second, we show that the lack of thickness cannot be compensated by non-myopic matching policies implying that the only way to thicken the market fruitfully is by attracting more agents.

The need for kidney exchange arises when a healthy person wishes to donate a kidney but is incompatible with her intended recipient. Two main factors determine compatibility of a donor with a patient: blood-type compatibility and tissue-type compatibility. Two or more incompatible pairs can form a cyclic exchange so that each patient can receive a kidney from a compatible donor. In addition, an exchange can be initiated by a non-directed donor (an altruistic donor who does not designate a particular intended patient), and in this case, a chain of exchanges need not form a closed cycle.

We study the problem of node placement in a sensor network. We consider proximity-based communication models where each sensor can only communicate with the ones within a given distance from it and the quality of communication between two sensors decreases with their distance. Each sensor can move locally and our goal is to improve the network connectivity by locally relocating the sensors. We use tools from spectral graph theory to determine the criticality of each edge to the global network connectivity. Based on the criticality measure, we develop algorithms that iteratively move the sensors in directions that improve the communication along more critical edges. Our algorithms are fully decentralized and only use local information exchange which are essential features for the sensor network application due to lack of centralized control and access to information in such networks. We formulate our problem as a convex optimization and use techniques from proximal minorant methods to prove the convergence of our iterative algorithms. Further, to make the algorithms fully local we use ideas such as the alternating direction method of multipliers from the distributed optimization literature. We also quantitatively illustrate the effectiveness of our schemes using simulation on a few sample networks.

We study the evolution of cooperation in populations where individuals play prisoner's dilemma on a network. Every node of the network corresponds to an individual choosing whether to cooperate or defect in a repeated game. The players revise their actions by imitating those neighbors who have higher payoffs.

We consider the online stochastic matching problem proposed by Feldman et al. [4] as a model of display ad allocation. We are given a bipartite graph; one side of the graph corresponds to a fixed set of bins and the other side represents the set of possible ball types. At each time step, a ball is sampled independently from the given distribution and it needs to be matched upon its arrival to an empty bin. The goal is to maximize the size of the matching. We present an online algorithm for this problem with a competitive ratio of 0.702. Before our result, algorithms with a competitive ratio better than 1 − 1/e were known under the assumption that the expected number of arriving balls of each type is integral. A key idea of the algorithm is to collect statistics about the decisions of the optimum offline solution using Monte Carlo sampling and use those statistics to guide the decisions of the online algorithm. We also show that no online algorithm can have a competitive ratio better than 0.823.

A number of algorithms have been proposed in the literature for scheduling CIOQ switches. The algorithms which have been proven to provide strict performance guarantees on delay (via the emulation of an output-queued switch) have been too complicated to implement because they require the exchange of a large amount of information between inputs and outputs. With implementation as our primary focus, we consider scheduling algorithms that are "fully local." This means inputs and outputs must be able to make decisions regarding matchings using only local information (except requests, grants and accepts). This constraint, which is essentially necessary for high-speed implementations, appears too restrictive for designing algorithms which enable the emulation of an output-queued switch. Rather surprisingly, we find a very simple and fully local algorithm FLGS (for fully local Gale-Shapley) which, at a speedup of 2, emulates an output-queued switch implementing a number of different output link scheduling algorithms such as weighted round robin and strict priority. We explore the performance of the algorithm at speedups between 1 and 2 using simulations and find that it partitions the bandwidth nearly as well as an output-queued switch at speedups 1.2 or higher.

Using parallel processing, the execution time of wireless network simulations can be significantly decreased without compromising the fidelity of the simulation. However, incorporating details such as signal propagation, interference, and resource allocation schemes may add considerable complexity to the parallel simulation which may overshadow the gain of parallelization. This paper reports on a recent work on parallelizing a high fidelity mobile wireless network simulator where dynamic resource allocation schemes are incorporated and the physical layer characteristics are included in sufficient detail. The program was run on a modular super-computing platform with 32 processors interconnected by high-speed infiniband links. Simulation results indicate that parallelization can significantly improve the runtime performance of the simulation without simplifying the physical layer modeling; a runtime speedup of more than 11 was achieved using 16 processors for a set of simulation parameters. A set of quantitative results on the capacity of the simulated network is obtained using the parallel simulator.