Chamsi Hssaine

RESEARCH + PUBLICATIONS

• End-of-Horizon Load Balancing Problems: Algorithms and Insights

  Abstract

  Effective load balancing is at the heart of many applications in operations. Frequently tackled via the balls-into-bins paradigm, seminal results have shown that alimited amount of (costly) flexibility goes a long way in order to maintain (approximately) balanced loads throughout the decision-making horizon. This paper is motivated by the fact that balance across time is too stringent a requirement for someapplications; rather, the only desideratum is approximate balance at the end of thehorizon. Thus motivated, in this work we design “limited-flexibility” algorithms forthree instantiations of the end-of-horizon balance problem: the canonical balls-into-bins problem, opaque selling strategies for inventory management, and parceldelivery for e-commerce fulfillment. For the balls-into-bins model, we show that asimple policy which begins exerting flexibility toward the end of the time horizon suffices to achieve an approximately balanced load. Moreover, with just a smallamount of adaptivity, a threshold policy achieves the same result, while only exertingflexibility in the least possible number of periods. We then adaptthese algorithms to develop order-wise optimal policies for the opaque selling problem.Finally, we show via a data-driven case study on the 2021 Amazon Last Mile RoutingResearch Challenge that the adaptive policy designed for the simpler balls-into-binsmodel can be carefully modified to (i) achieve approximate balance at the end of thehorizon and (ii) yield significant cost savings relative to policies which either neverexert flexibility, or exert flexibility aggressively enough to always maintain balancedloads. The unifying motivation behind our algorithms for these three vastly differentapplications is the observation that exerting flexibility at the beginning of the horizonis likely wasted when system balance is only evaluated at the end.
  

  Author[s]

  • Chamsi Hssaine
  • Daniel Freund
  • Jiayu (Kamessi) Zhao

  CLOSE

• Online Fair Allocation of Perishable Resources

  Abstract

  We consider a practically motivated variant of the canonical online fair allocation problem: a decision-maker has a budget of resources to allocate over a fixed number of rounds. Each round sees a random number of arrivals, and the decision-maker must commit to an allocation for these individuals before moving on to the next round. In contrast to prior work, we consider a setting in which resources are perishable and individuals' utilities are potentially non-linear (e.g., goods exhibit complementarities). The goal is to construct a sequence of allocations that is envy-free and efficient. We design an algorithm that takes as input (i) a prediction of the perishing order, and (ii) a desired bound on envy. Given the remaining budget in each period, the algorithm uses forecasts of future demand and perishing to adaptively choose one of two carefully constructed guardrail quantities. We characterize conditions under which our algorithm achieves the optimal envy-efficiency Pareto frontier. We moreover demonstrate its strong numerical performance using data from a partnering food bank.

  Author[s]

  • Chamsi Hssaine
  • Sean Sinclair
  • Siddhartha Banerjee

  Publication

  ACM SIGMETRICS Performance Evaluation Review, 51(1), 55-56

  CLOSE

• Plan Your System and Price for Free: Fast Algorithms for Multimodal Transit Operations

  Abstract

  We study the problem of jointly pricing and designing a smart transit system, where the transit agency (the platform) controls a fleet of demand-responsive vehicles (cars) and a fixed line service (buses). The platform offers commuters a menu of options to travel between origin and destination (e.g., a direct car trip, a bus ride, or a hybrid combination of the two), and commuters make the utility-maximizing choice within this menu, given the price of each trip option. The goal of the platform is to determine the optimal set of trip options (modes) to display to commuters, the prices for these modes, and the design of the transit network in order to maximize the social welfare of the system. In this work, we tackle the commuter choice aspect of this problem, traditionally approached via computationally intensive bi-level programming techniques. In particular, we develop a framework that efficiently decouples the pricing and network design problem: given an efficient (approximation) algorithm for centralized network design without prices, there exists an efficient (approximation) for decentralized network design with prices and commuter choice. We demonstrate the practicality of our framework via extensive numerical experiments on a real-world dataset, in which we show the efficiency of pricing algorithm. We moreover explore the dependence of system welfare, revenue, and demand on transfer costs, as well as the cost of contracting with the on-demand service provider, and exhibit the welfare gains from a fully integrated mobility system.

  Author[s]

  • Chamsi Hssaine
  • Qi Luo
  • Samitha Samaranayake
  • Siddhartha Banerjee

  CLOSE

• Fair Incentives for Repeated Engagement

  Abstract

  We study a decision-maker’s problem of finding optimal monetary incentive schemeswhen faced with agents whose participation decisions (stochastically) depend on theincentive they receive. Our focus is on policies constrained to fulfill two fairness properties that preclude outcomes wherein different groups of agents experience differenttreatment on average. We formulate the problem as a high-dimensional stochasticoptimization problem, and study it through the use of a closely related deterministic variant. We show that the optimal static solution to this deterministic variant isasymptotically optimal for the dynamic problem under fairness constraints. Thoughsolving for the optimal static solution gives rise to a non-convex optimization problem,we uncover a structural property that allows us to design a tractable, fast-convergingheuristic policy. Traditional schemes for stakeholder retention ignore fairness constraints; indeed, the goal in these is to use differentiation to incentivize repeated engagement with the system. Our work (i) shows that even in the absence of explicitdiscrimination, dynamic policies may unintentionally discriminate between agents ofdifferent types by varying the type composition of the system, and (ii) presents anasymptotically optimal policy to avoid such discriminatory outcomes.
  

  Author[s]

  • Chamsi Hssaine
  • Daniel Freund

  Publication

  19th Conference on Web and Internet Economics (WINE 2023)

  CLOSE

• Real-Time Approximate Routing for Smart Transit Systems

  Abstract

  We study real-time routing policies in smart transit systems, where the platform has a combination of cars and high-capacity vehicles (e.g., buses or shuttles) and seeks to serve a set of incoming trip requests. The platform can use its fleet of cars as a feeder to connect passengers to its high-capacity fleet, which operates on fixed routes. Our goal is to find the optimal set of (bus) routes and corresponding frequencies to maximize the social welfare of the system in a given time window. This generalizes the Line Planning Problem, a widely studied topic in the transportation literature, for which existing solutions are either heuristic (with no performance guarantees), or require extensive computation time (and hence are impractical for real-time use). To this end, we develop a 1-1/e approximation algorithm for the Real-Time Line Planning Problem, using ideas from randomized rounding and the Generalized Assignment Problem. Our guarantee holds under two assumptions: (i) no inter-bus transfers and (ii) access to a pre-specified set of feasible bus lines. We moreover show that these two assumptions are crucial by proving that, if either assumption is relaxed, the Real-Time Line Planning Problem does not admit any constant-factor approximation. Finally, we demonstrate the practicality of our algorithm via numerical experiments on real-world and synthetic datasets, in which we show that, given a fixed time budget, our algorithm outperforms Integer Linear Programming-based exact methods.

  Author[s]

  • Chamsi Hssaine
  • Noémie Périvier
  • Samitha Samaranayake
  • Siddhartha Banerjee

  Publication

  Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(2), 1-30

  CLOSE