Schedule for: 25w5464 - Dynamic Allocation and Matching

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

Our work introduces the effect of supply/demand imbalances into the literature on online matching with stochastic rewards in bipartite graphs. We provide a parameterized definition that characterizes the imbalance of an instance and show that higher competitive ratios against an offline clairvoyant algorithm are achievable, for both adversarial and stochastic arrivals, when instances are more imbalanced. The competitive ratio guarantees we obtain are the best-possible for the class of delayed algorithms we focus on (such algorithms may adapt to the history of arrivals and the algorithm’s own decisions, but not to the stochastic realization of each potential match). We then explore the real-world implications of our improved competitive ratios. First, we demonstrate analytically that the improved competitive ratios under imbalanced instances is not a one-way street by showing that a platform that conducts effective supply- and demand management should incorporate the effect of imbalance on its matching performance on its supply planning in order to create imbalanced instances. Second, we empirically study the relationship between achieved competitive ratios and imbalance using the data of a volunteer matching platform.

We study a dynamic non-bipartite stochastic matching problem, where nodes appear following a type-specific independent distribution and wait in the system for a given sojourn time. This problem is motivated by applications in ride-sharing and freight transportation marketplaces, and is related to other on-demand marketplaces. We study the asymptotic properties of two widely used policies, batching and greedy, by analyzing a single-pair case and then converting to the general counterpart using a fluid relaxation and randomization. We show that the batching policy is asymptotically optimal with respect to the sojourn time; similarly, while a straightforward greedy policy may not be optimal, a greedy policy with randomized modifications is asymptotically optimal. Perhaps more practically relevant, both policies converge exponentially fast to approximate optimality. Time permitting, we extend our results to an impatient setting in which each unmatched node leaves at the end of each period with a type-dependent probability, and present a computational study simulating a ride-sharing marketplace to assess the empirical effectiveness of the policies. Our results suggest that managers can achieve near-optimal performance by using simple greedy or batching policies, with only a reasonably small maximum waiting time guarantee, and even in the presence of potentially impatient nodes.

We study a two-sided network (platforms) where heterogeneous demand (customers) and supply (workers) arrive randomly over time to get matched. Customers and workers arrive with a randomly sampled patience time (also known as reneging time in the literature), and are lost without being matched if forced to wait longer than that time. There is an inherent tradeoff between making matches quickly and waiting to enable better matches. The system dynamics and performance depend on the matching policy, which determines the timing and number of matches between a particular customer class and a particular worker class. The issue in developing a matching policy is that model primitives (i.e., arrival rates and patience time distributions) are unknown. Our objective is to learn a policy from historical data that is asymptotically optimal (on fluid scale, as demand and supply rates grow large). A key challenge is that the fluid-scaled upper bound depends on the full patience time distributions, and may be different for different distributions even when the mean is the same. As a result, policy error can be large when the mean is learned well but the full distribution is not. Moreover, the amount of data required to achieve a given policy error level depends on the difficulty of learning the full distribution, which, in turn, is influenced by its density behavior.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in the PDC front desk for a guided tour of The Banff Centre campus.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

We will provide an overview of Stein’s method, which can be used to derive non-asymptotic central limit theorems for dependent random variables, including martingales and Markov chains. The talk will primarily focus on providing an introduction to Stein’s method which can be used to upper bound the Wasserstein distance between the distribution of a scaled sum of random variables and a Gaussian distribution. Time permitting, we will then discuss extensions to vector-valued martingales and vector-valued functions of Markov chains. The theory will be motivated using applications from graph sampling, stochastic gradient descent and TD learning. While the talk will be tutorial-style, the talk will draw upon some recent results from this paper: https://arxiv.org/pdf/2401.15719.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

This tutorial provides an overview of the graph alignment problem, also known as graph matching problem, network alignment problem, or noisy graph isomorphism problem. The main goal is to identify a correspondence between vertices or users across two or more correlated graphs. This challenge is relevant in a range of applications, such as domain adaptation for generalizing beyond the training distribution in machine learning, linking shared entities across complementary graphs for knowledge graph completion in data science, analyzing brain connectomes from correlated brain imaging in biomedical applications, and de-anonymizing keywords in searchable encryption. From a mathematical perspective, graph matching is a quadratic assignment problem, which is NP-hard in the worst case. Yet, in many practical networks that are effectively modeled by random graphs, a phase transition phenomenon is observed in the asymptotic limit. This motivates theorists to examine, in an average case scenario, the threshold at which this phase transition occurs and to assess whether polynomial-time algorithms can reach this threshold. This tutorial introduces key technical tools used in graph alignment and reviews the recent findings concerning the information-theoretic limits and the development of efficient algorithms. It also aims to spark discussions on open problems and future research avenues.

Heterogeneity poses a fundamental challenge for many real-world large-scale decision-making problems but remains largely understudied. In this paper, we study the fully heterogeneous setting of a prominent class of such problems, known as weakly-coupled Markov decision processes (WCMDPs). Each WCMDP consists of $N$ arms (or subproblems), which have distinct model parameters in the fully heterogeneous setting, leading to the curse of dimensionality when $N$ is large. We show that, under mild assumptions, a natural adaptation of the ID policy, although originally proposed for a homogeneous special case of WCMDPs, in fact achieves an $O(1/\sqrt{N})$ optimality gap in long-run average reward per arm for fully heterogeneous WCMDPs as $N$ becomes large. This is the first asymptotic optimality result for fully heterogeneous average-reward WCMDPs. Our techniques highlight the construction of a novel projection-based Lyapunov function, which witnesses the convergence of rewards and costs to an optimal region in the presence of heterogeneity.

Human-annotated preference data are playing an important role in aligning large language models (LLMs). In this talk, we discuss the questions of assessing the performance of human annotators and incentivizing them to provide high-quality annotations. The quality assessment of language/text annotation faces two challenges: (i) the intrinsic heterogeneity among annotators, which prevents the classic methods that assume the underlying existence of a true label; and (ii) the unclear relationship between the annotation quality and the performance of downstream tasks, which excludes the possibility of inferring the annotators' behavior based on the model performance trained from the annotation data. Next, we formulate a principal-agent model to understand the behaviors of and the interactions between the company and the human annotators. The model rationalizes a practical mechanism of a bonus scheme to incentivize annotators which benefits both parties and it underscores the importance of the joint presence of the assessment system and the bonus scheme. From a technical perspective, our analysis extends the existing literature on the principal-agent model by considering a continuous action space for the agent. We show the gap between the first-best and the second-best solutions (under the continuous action space) is of $\Theta(1/\sqrt{n \log n})$ for the binary contracts and $\Theta(1/n)$ for the linear contracts, where $n$ is the number of samples used for performance assessment; this contrasts with the known result of $\exp(-\Theta(n))$ for the binary contracts when the action space is discrete. Throughout the talk, we use real language preference data to accompany our discussion.

In a prophet inequality problem, n independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent value as a reward. We evaluate a stopping rule by the worst-case ratio between its expected reward and the expectation of the maximum variable. Because of its connections with resource allocation and posted-price mechanisms, this problem has been intensively studied, and several variants have been introduced. While most of the literature assumes that distributions are known to the gambler, recent work has considered the question of what is achievable when the gambler has access only to a few samples per distribution. We provide a unified proof that for all three major variants of the single-selection problem, a constant number of samples (independent of n) for each distribution is good enough to approximate the optimal ratios. Prior to our work, this was known to be the case only in the i.i.d. variant. Previous works relied on explicitly constructing sample-based algorithms that match the best possible ratio. Remarkably, the optimal ratios for the prophet-secretary and the free-order variants with full information are still unknown. Consequently, our result requires a significantly different approach than for the classic problem and the i.i.d. variant, where the optimal ratios and the algorithms that achieve them are known. We complement our result showing that our algorithms can be implemented in polynomial time.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

This tutorial will discuss the recent development of dynamic L_1 Interior point methods for combinatorial optimization. These methods, in strongest technical terms, can maintain whether the objective of a min-cost convex flow problem exceeds some threshold in sub-polynomial time per insertion (arXiv 2311.18295) /deletion (arXiv 2407.10830). Notable implications of them include optimal transport, online cycle/perfect matching detection, and matrix rescaling. The talk will focus on the second order method formulation and its interplay with dynamic approximations of undirected graphs. Attempts will be made to frame these results in the even more extensive literature of dynamic/streaming matchings.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

We generalize the problem of online submodular welfare maximization to incorporate various stochastic elements that have gained significant attention in recent years. We show that a non-adaptive Greedy algorithm, which is oblivious to the realization of these stochastic elements, achieves the best possible competitive ratio among all polynomial-time algorithms, including adaptive ones. This result holds even when the objective function is not submodular but instead satisfies the weaker submodular order property. Our results unify and strengthen existing competitive ratio bounds across well-studied settings and diverse arrival models, showing that, in general, adaptivity to stochastic elements offers no advantage in terms of competitive ratio. To establish these results, we introduce a technique that lifts known results from the deterministic setting to the generalized stochastic setting. The technique has broader applicability, enabling us to show that, in certain special cases, non-adaptive Greedy-like algorithms outperform the Greedy algorithm and achieve the optimal competitive ratio. We also apply the technique in reverse to derive new upper bounds on the performance of Greedy-like algorithms in deterministic settings by leveraging upper bounds on the performance of non-adaptive algorithms in stochastic settings. The talk will be based on the following preprint: https://arxiv.org/abs/2403.18059

We study a target-following variation of online resource allocation. As in classical resource allocation, the decision-maker must assign sequentially arriving jobs to one of multiple available resources. However, in addition to the assignment costs incurred from these decisions, the decision-maker is also penalized for deviating from exogenously given, nonstationary target allocations throughout the horizon. The goal is to minimize the total expected assignment and deviation penalty costs incurred throughout the horizon when the distribution of assignment costs is unknown. In contrast to traditional online resource allocation, in our setting the timing of allocation decisions is critical due to the nonstationarity of allocation targets. Examples of practical problems that fit this framework include many physical resource settings where capacity is time-varying, such as manual warehouse processes where staffing levels change over time, and assignment of packages to outbound trucks whose departure times are scheduled throughout the day. We first show that naive extensions of state-of-the-art algorithms for classical resource allocation problems can fail dramatically when applied to target-following resource allocation. We then propose a novel ``proxy assignment" primal-dual algorithm for the target-following online resource allocation problem that uses current arrivals to simulate the effect of future arrivals. We prove that our algorithm incurs the optimal $O(\sqrt{T})$ regret bound when the assignment costs of the arriving jobs are drawn i.i.d. from a fixed distribution. We demonstrate the practical performance of our approach by conducting numerical experiments on synthetic datasets, as well as real-world datasets from retail fulfillment operations.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

We study a dynamic model of interactions between a firm and job applicants to identify mechanisms that drive long-term discrimination. In each round, the firm decides which applicants to hire, where the firm's ability to evaluate applicants is imperfect. Each applicant belongs to a group, and central to our model is the idea that the firm becomes better at evaluating applicants from groups in which they have hired from in the recent past. We establish the firm's initial evaluation ability for each group to be a critical factor in determining long-term outcomes. We show that there is a threshold for which if the firm's initial evaluation ability for the group is below the threshold, the group's hiring rate decreases over time and eventually goes to zero. If the group starts above the threshold, then the hiring rate stabilizes to a positive constant. Therefore, even when two groups are identical in size and underlying skill distribution, a marginal difference in the firm's initial evaluation ability can lead to persistent disparities that exacerbate over time through a feedback loop. Importantly, the dynamic nature of our model allows us to assess the long-term impact of interventions. Our analysis highlights the importance of interventions that meaningfully alter evaluation ability, and our results imply that drastic short-term interventions are more effective compared to milder long-term interventions. Additionally, we show that smaller groups face inherent disadvantages, requiring a higher initial evaluation ability to achieve a favorable long-term hiring outcome and experiencing lower hiring rates even when they do. This paper provides a framework that formalizes how sequential decisions influence one another over time which allows us to evaluate long-term outcomes, and we believe this framework can be extended to applications beyond hiring.

A key feature of many real-world matching markets is congestion, i.e., market participants struggle to find match partners. We characterize congestion in a model of random matching markets where an agent pair must perform a mutual inspection to verify compatibility prior to matching with each other. We assume agents are only willing to inspect their current favorite agent and will do so only if, upon a successful inspection, that match is guaranteed. We ask when, in large random two-sided markets, will information deadlocks arise in which many agents delay inspections indefinitely awaiting a match guarantee. We find a phase transition between a deadlock-free regime (where a vanishingly small fraction of agents are stuck waiting) and an information deadlock regime as we vary model primitives. A number of market design insights emerge from our characterization. Our analysis is inspired by the machinery of message passing and density evolution from statistical physics, and the emergence of deadlock corresponds to a certain branching process being supercritical.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

In collaboration with VolunteerMatch (VM) --- the world's largest online platform for connecting volunteers with volunteering opportunities --- we designed and implemented a new display ranking algorithm. To incorporate VM's desire for equity (defined as the weekly number of opportunities with at least one connection) along with efficiency (defined as the total number of connections), we propose a modeling framework for online display ranking which combines these two objectives. We show that a simple class of algorithms that applies a penalty to opportunities after each connection provides a strong (and, in certain regimes, optimal) performance guarantee. Based on our theoretical development, we propose SmartSort, a simple online display ranking algorithm with a penalty term that we calibrated using VM's data and simulation. We implemented SmartSort in two experiments, covering Dallas-Fort Worth and all of Southern California. Using a difference-in-differences analysis, we find that the implementation of SmartSort led to an estimated 8% increase in the weekly average number of opportunities with at least one connection (consistent across both experiments) without any significant decrease in the total number of connections. If SmartSort has a similar distributional effect on a national scale, an additional 30,000 connections every year will go to opportunities that would have otherwise lacked access to volunteers.

5-day workshop participants are welcome to use BIRS facilities (TCPL ) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 11AM.