Strategic arrivals to queues offering priority service

Rajat Talak, D. Manjunath, Alexandre Proutière

TL;DR

This paper models how strategic customers choose arrival times and service priorities to minimize their costs in systems like airline boarding. It characterizes the resulting Nash equilibria and analyzes how service providers can set prices and priority levels to maximize revenue, finding that a few priority levels can capture most of the potential revenue.

What Problem Does This Paper Address?

Imagine an airline boarding a plane. Passengers want good seats and to board without too much hassle. Arriving too early means a long wait, while arriving too late means fewer good seats and more crowded overhead bins. This paper tackles how heterogeneous customers, with different valuations for their time and money, strategically decide when to arrive and which boarding group (priority level) to join to minimize their personal costs. For the airline, the challenge is to design a system of priority queues and pricing that maximizes its revenue while accounting for these strategic customer choices. The paper extends previous work on single-queue games to multi-queue systems with priority pricing, a more realistic scenario for many service industries.

Methods

The core of the paper's methodology lies in game theory, specifically analyzing Nash equilibria.

  • Single Queue (FCFS): The authors first model a single First-Come, First-Served (FCFS) queue where customers with different "types" (representing their cost valuations) strategically choose their arrival times to minimize a cost function that includes waiting time and "boarding cost" (related to their queue position). They derive the unique Nash equilibrium arrival strategy.
  • Multiple Priority Queues: The model is then extended to a system with $L$ FCFS queues, each offering a different priority level and associated price. Customers now make two strategic choices: arrival time and which priority queue to join. The paper characterizes the Nash equilibrium where customer types are segmented into intervals, with each interval choosing a specific priority level.
  • Revenue Maximization: The authors then shift to the service provider's perspective, analyzing how to set prices for each priority level to maximize revenue, given the customers' strategic behavior. This involves solving a dynamic programming problem.

Datasets

Not discussed in the paper. The paper uses theoretical models and numerical examples to illustrate its findings.

Key Insights and Ideas

  • Strategic Segmentation: In a multi-priority system, customers naturally segment themselves. Different "types" of customers will gravitate towards specific priority levels based on their cost valuations and the associated prices.
  • Price vs. Quality Trade-off: Customers are willing to pay more for higher priority, but this is balanced against their waiting costs and the actual quality of service offered by that priority level.
  • Revenue Maximization with Few Queues: Surprisingly, a service provider doesn't need a vast number of priority levels to capture most of the potential revenue. Two or three priority levels can often yield revenue close to the theoretical maximum.
  • "Quantization Effect": The revenue from a continuous range of service options (perfect discrimination) is higher than from a discrete set of priority levels. This "quantization effect" means some revenue is left on the table with a finite number of queues, but the loss is manageable with a small number of levels.
  • Arrival Time Dynamics: Customers with higher valuations for their time (higher "type") tend to arrive later in a single-queue system. In a multi-queue system, arrival times can become more complex, with higher priority customers sometimes arriving earlier than lower priority customers, depending on the price and their type.

Key Results

  • Unique Nash Equilibria: The paper proves the existence and uniqueness of Nash equilibria for both the single-queue and multi-queue scenarios, characterizing the strategic arrival and queue-joining strategies of customers.
  • Revenue Independence (Single Queue): In a single-queue system with a continuum of service grades, the server's revenue is independent of the specific pricing function, as long as it's monotonically increasing.
  • Numerical Findings: Numerical examples demonstrate that for a system with three queues, revenue is nearly maximized. The paper also shows that greater diversity in customer types generally leads to higher potential revenue.

Limitations and Future Work

  • Assumptions: The model relies on specific assumptions about cost functions (e.g., linear waiting costs, specific forms for boarding costs) and customer type distributions. The robustness of the results to different functional forms is not fully explored.
  • No Balking: The current model assumes all customers will join a queue and receive service. Future work could incorporate "balking" (customers choosing not to join a queue if their cost exceeds a threshold).
  • Learning Algorithms: The authors suggest developing learning algorithms for revenue-maximizing prices, especially for repeated games where prices can be adapted over time.
  • Dynamic Pricing: The current pricing is static. Exploring dynamic pricing strategies could be a valuable extension.

Summary updated

Abstract

We consider strategic arrivals to a FCFS service system that starts service at a fixed time and has to serve a fixed number of customers, for example, an airplane boarding system. Arriving early induces a higher waiting cost (waiting before service begins) while arriving late induces a cost because earlier arrivals take the better seats. We first consider arrivals of heterogenous customers that choose arrival times to minimize the weighted sum of waiting cost and cost due to expected number of predecessors. We characterize the unique Nash equilibria for this system. Next, we consider a system offering L levels of priority service with a FCFS queue for each priority level. Higher priorities are charged higher admission prices. Customers make two choices—time of arrival and priority of service. We show that the Nash equilibrium corresponds to the customer types being divided into L intervals and customers belonging to each interval choosing the same priority level. We further analyze the net revenue to the server and consider revenue maximizing strategies—number of priority levels and pricing. Numerical results show that with only a small number of queues (two or three) the server can obtain nearly the maximum revenue.
BibTeX
@article{talak2019strategic,
  author = {Rajat Talak and D. Manjunath and Alexandre Proutière},
  title = {{Strategic arrivals to queues offering priority service}},
  journal = {Queueing Syst. Theory Appl.},
  year = {2019},
  doi = {10.1007/s11134-019-09604-3},
}
Figure