Queueing Problems with Exit Option

A set of agents with possibly different waiting costs and different service valuations may receive a common service sequentially. Unlike in the existing queueing literature, we equip agents with an exit option: each agent may opt out of the queue entirely, receiving no service and possibly a monetary transfer. This seemingly small departure has striking consequences for what is achievable. Efficiency requires maximizing total welfare, fairness requires treating equal agents equally, and incentive compatibility requires agents to report their private waiting costs truthfully. Without the exit option, these three goals can all be met simultaneously. With the exit option, they cannot — at least not on the full domain. We make three contributions. First, we introduce a dynamic-programming algorithm that computes all Pareto-efficient queues. Second, on the domain of problems in which Pareto-efficiency requires serving all agents (the all-serve domain), we prove that the equally distributed pairwise pivotal family is the unique class of rules satisfying Pareto-efficiency, equal treatment of equals in welfare, and strategy-proofness; and each rule also satisfies individual rationality (Theorem 1). Third, we prove that on the full domain no rule satisfies these three axioms (Theorem 2). This impossibility is in striking contrast to the positive result of Kayı and Ramaekers (2010) for queueing problems without an exit option, and illustrates how the exit option fundamentally reshapes what is achievable in mechanism design for queues.