⚡ electrical engineering

Noncooperative Virtual Queue Coordination via Uncertainty-Aware Correlated Equilibria

This paper proposes a scalable, uncertainty-aware noncooperative coordination mechanism based on chance-constrained correlated equilibria to optimize airport surface congestion management by providing airlines with incentive-compatible pushback recommendations that respect their autonomy while reducing accumulated delays.

Original authors: Jaehan Im, David Fridovich-Keil, Ufuk Topcu

Published 2026-02-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jaehan Im, David Fridovich-Keil, Ufuk Topcu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a busy airport as a giant, high-stakes game of musical chairs, but instead of chairs, the "seats" are slots on the runway for planes to take off.

In the current system, airlines are like independent families arriving at the party. They all want to get their kids (planes) to the dance floor (runway) as fast as possible. To manage the crowd, the airport controller (the coordinator) puts a limit on how many people can enter the hallway (taxiway) at once. However, the controller cannot tell Family A which specific child to send first; they just say, "You can send two kids."

The problem? Each family has their own secret rules. Family A might send their slowest kid first to save energy, while Family B sends their fastest kid to beat a schedule. Because they aren't talking to each other, they often end up creating a traffic jam in the hallway, causing everyone to wait longer.

This paper proposes a new way to run the party: The "Uncertainty-Aware Correlated Equilibrium."

Here is how it works, broken down into simple concepts:

1. The "Secret Note" Strategy (Correlated Equilibrium)

Instead of the controller just saying, "Send two kids," the controller acts like a referee with a magic deck of cards.

The referee looks at the whole situation.
The referee secretly writes a note to Family A: "Send your slow kid first."
The referee secretly writes a note to Family B: "Send your fast kid first."
The Catch: The referee doesn't force them to listen. But, the notes are written in a way that makes it in the family's best interest to listen. If Family A ignores the note and sends the fast kid anyway, they might accidentally cause a crash or a longer delay for themselves. So, they voluntarily follow the advice because it's the smartest move for them.

This is called a Correlated Equilibrium. It's a way to coordinate strangers without a dictator.

2. The "Foggy Crystal Ball" (Uncertainty & Chance Constraints)

Here is the tricky part: The referee doesn't know exactly how much each family hates waiting. Maybe Family A is in a huge rush today, or maybe they are relaxed. The referee only has a guess (a model) of their costs.

If the referee gives a note based on a bad guess, the family might say, "No way, that's a terrible idea for us!" and ignore the note.

To fix this, the authors added a "Foggy Crystal Ball" (Chance Constraints).

Instead of saying, "I am 100% sure this is the best move," the referee says, "I am 90% confident this is the best move."
The referee builds a safety buffer into the notes. They account for the "fog" (uncertainty) in the families' schedules.
This ensures that even if the families' internal costs are slightly different than the referee guessed, they will still likely follow the advice. It's like wearing a seatbelt: you hope you don't need it, but it guarantees safety if things go wrong.

3. The "Shortcut" (Reduced-Rank Algorithm)

Calculating the perfect secret notes for every possible combination of families and kids is a math nightmare. If there are 20 families and 100 planes, the number of combinations is bigger than the number of stars in the galaxy. A computer would take years to figure it out.

The authors found a shortcut.

Instead of calculating every single possibility, they looked for the "obvious good moves" (Pure Nash Equilibria) where everyone is already happy.
They realized they could mix and match these "obvious good moves" to create a new, complex strategy that is almost as good as the perfect one, but much faster to calculate.
It's like solving a giant puzzle by first finding the corner pieces and the edge pieces, then filling in the middle, rather than trying to place every single piece randomly.

The Results: Why It Matters

The team tested this idea with computer simulations of a super-busy airport (like Atlanta or London Heathrow).

Less Waiting: Compared to the current "First-Come, First-Served" method, this new system reduced total waiting time by about 8.9%. That's huge when you have thousands of flights a day.
Scalable: The "shortcut" algorithm was fast enough to work in real-time, even with 210 planes waiting to push back in an hour.
Robust: Even when the "fog" (uncertainty) was thick, the system kept the planes moving smoothly because the "safety buffer" in the notes prevented families from ignoring the advice.

The Big Picture

This paper is about teaching a chaotic crowd of independent players (airlines) to play nicely together without a boss forcing them to. By using smart, probabilistic hints that account for the fact that "we don't know everything," the airport can clear the runway faster, save fuel, and get passengers to their destinations sooner—all while letting the airlines keep their freedom to make their own choices.

It turns a traffic jam into a well-choreographed dance, even when the music is a little fuzzy.

1. Problem Statement

The paper addresses the challenge of managing airport surface congestion through Collaborative Virtual Queue (CVQ) systems.

Context: In CVQ, a central coordinator regulates the aggregate number of aircraft allowed to push back from gates per airline to prevent taxiway and runway congestion. However, individual airlines retain autonomy over which specific aircraft to push back within their allocated slots.
The Gap: Existing CVQ approaches treat airlines' internal aircraft selection policies as a "black box." Because airlines have private, time-varying, and uncertain cost functions (e.g., specific passenger connections, crew schedules), a central coordinator cannot directly enforce system-optimal decisions without violating airline autonomy.
The Core Challenge: How can a coordinator steer system-level performance (minimizing total delay) by influencing specific aircraft-level decisions, while respecting airline autonomy and accounting for the uncertainty in airlines' internal cost assessments?

2. Methodology

The authors propose a Noncooperative Coordination Mechanism based on Correlated Equilibrium (CE), extended to handle uncertainty.

A. Game-Theoretic Formulation

Players: Airlines acting as noncooperative agents.
Coordinator: A central entity that observes the surface state (runway queues, eligible aircraft) and provides recommendations.
Mechanism: Instead of enforcing a deterministic action, the coordinator samples a joint action profile from a probability distribution and privately recommends an action to each airline.
Incentive Compatibility: The distribution is designed such that, given the recommendation, it is rational for each airline to follow it rather than deviate, based on their own cost structure.

B. Uncertainty-Aware Correlated Equilibrium (CC-CE)

Recognizing that the coordinator does not know the exact cost functions of airlines, the authors introduce Chance Constraints:

Uncertainty Model: The true deviation cost difference is modeled as a nominal cost difference plus a stochastic noise term ( $\eta_i$ ).
Chance-Constrained CE (CC-CE): A distribution is a CC-CE if the probability that following the recommendation is better than deviating is at least a user-specified confidence level ( $\alpha$ $α$ ).
- Mathematically: $P(\text{Expected Cost of Deviation} \geq \text{Cost of Recommendation}) \geq \alpha$ .
Trade-off: Higher $\alpha$ provides stronger guarantees against deviation but shrinks the feasible set of equilibria, potentially limiting cost efficiency.

C. Scalable Computation via Reduced-Rank Structure

Direct computation of CE is intractable for large-scale problems because the joint action space grows exponentially with the number of aircraft.

Solution: The authors exploit a Reduced-Rank Correlated Equilibrium (RRCE) framework.
Approach: Instead of solving for the full CE polytope, they compute a finite set of Chance-Constrained Pure Nash Equilibria (CC-PNE) and construct the CC-CE as a convex combination of these equilibria.
Benefit: Since Nash equilibria are a subset of correlated equilibria and are computationally easier to find, this approach significantly reduces the computational burden, making real-time deployment feasible.

3. Key Contributions

Noncooperative Coordination Mechanism: Reformulated the CVQ problem to allow a coordinator to influence which specific aircraft are pushed back (not just how many) while preserving airline autonomy through incentive-compatible recommendations.
Uncertainty-Aware Formulation: Introduced the Chance-Constrained Correlated Equilibrium (CC-CE) framework. This provides explicit probabilistic guarantees on incentive compatibility, allowing the coordinator to tune the confidence level ( $\alpha$ ) regarding airlines' adherence to recommendations under uncertain cost realizations.
Scalable Algorithm: Developed a reduced-rank algorithm that approximates the CC-CE feasible set using convex combinations of CC-PNEs. This enables tractable computation for realistic traffic volumes.

4. Experimental Results

The authors evaluated the method using numerical experiments simulating a busy airport environment (up to 210 eligible pushbacks per hour).

Scalability:
- The Full-CCCE solver (solving the full linear program) becomes intractable as the number of eligible aircraft exceeds 9 per epoch (exceeding the 4-minute decision window).
- The RR-CCCE (reduced-rank) solver remains computationally efficient (well under 4 minutes) even with 14 eligible aircraft per epoch, demonstrating suitability for real-time operations.
Performance (Delay Reduction):
- Compared to the standard First-Come-First-Served (FCFS) baseline, the proposed methods reduced accumulated delay by 6.0% to 8.9%.
- In low-uncertainty scenarios, the uncertainty-aware methods performed comparably to an idealized centralized benchmark (CENT).
Robustness and Deviation:
- Deviation Rates: Uncertainty-aware methods (Full-CCCE and RR-CCCE) showed significantly lower deviation rates compared to nominal methods (RR-Nominal) when cost uncertainty was high.
- Confidence Level ( $\alpha$ ): Increasing $\alpha$ reduced the empirical deviation rate but occasionally reduced the number of available equilibrium profiles, creating a trade-off between robustness and cost efficiency.
- RR-CCCE vs. Full-CCCE: RR-CCCE exhibited near-zero deviation rates across various noise levels, suggesting the reduced-rank approximation implicitly increases robustness, though with a slight performance gap in cost efficiency compared to the full formulation.

5. Significance

Bridging Theory and Practice: The paper successfully bridges the gap between theoretical game theory (Correlated Equilibrium) and practical airport operations by addressing the critical issue of cost uncertainty and computational scalability.
Autonomy Preservation: It offers a viable path for improving system-wide efficiency without requiring airlines to surrender control of their specific flight schedules, a major political and operational hurdle in current aviation management.
Risk Management: The introduction of chance constraints allows operators to explicitly manage the risk of airlines ignoring recommendations, providing a tunable parameter ( $\alpha$ ) to balance system performance against the reliability of compliance.
Real-World Applicability: The demonstrated ability to handle traffic levels comparable to the world's busiest airports (e.g., Atlanta) suggests this framework is ready for integration into next-generation Collaborative Decision Making (CDM) systems.