Regulating Wait-Driven Requests in Queues

Abstract

The study of rational queueing has a long and distinguished history focused on individuals' preference to avoid waiting. Surprisingly, there are settings in which some potential arrivals (which we also refer to as requests) derive utility from waiting and disutility from service. Our primary example is the U.S. affirmative asylum process. In this context, applicants obtain a work permit while waiting for an asylum interview; hence, if the (expected) wait is long enough, then even an applicant who knows that their application will be denied and lead to deportation proceedings, may find it in their interest to apply and thus benefit from legally working during the wait. Similar dynamics could occur in other settings like content moderation in social networks. The common thread of these examples is the potentially self-exciting queue: when wait times are long, many arrivals are incentivized to join, and wait times become even longer. However, the system designer usually wants to avoid a large backlog. Indeed, the US Citizenship and Immigration Services (USCIS) mostly schedules asylum interviews in a Last-In-First-Out (LIFO) manner with the explicit goal of dissuading applicants with non-meritorious cases trying to exploit the long backlog. Despite this interesting scheduling choice in practice, and the potential prevalence of similar settings in other applications, the existing literature on rational queueing lacks frameworks to study the impact of wait-driven requests. Motivated by this gap in the literature, we formalize a dynamical system where in each round, a given scheduling policy and a realized request rate determine the wait time distribution in a fluid queueing system. Observing the expected benefit from waiting in one round, requests update their decisions, setting the request rate for the next round. Assuming a concave benefit function from waiting, alongside general conditions, we prove that, for minimizing the backlog, LIFO is most effective while First-In-First-Out (FIFO) is least effective among all work-conserving policies. Moreover, we show that the dynamical system exhibits metastability: for either FIFO or LIFO, the system converges to either a zero-wait or a congested equilibrium. Although some asylum practitioners support the use of LIFO, critics often admonish the real-world use of LIFO for its failure to maintain FIFO's order fairness: earlier requests should get earlier service. Our results demonstrate this trade-off between LIFO and FIFO. But we also show limitations of hybrid policies, which probabilistically follow either LIFO or FIFO, in navigating the trade-off between LIFO's efficiency and FIFO's fairness. Our work formalizes the concept of order fairness in queueing systems with abandonment and demonstrates that hybrid policies can be Pareto-dominated by LIFO: they may have both longer backlog and worse order fairness. Finally, we use real-world data on the scheduling of affirmative asylum applications to evaluate the change in fairness over the past 20 years under different policies.