⚡ electrical engineering

Game-theoretic Regulated Decentralized Coordination for Airspace Sector Overload Mitigation

This paper proposes a game-theoretic, regulated decentralized protocol for air traffic management that models self-interested sector behaviors with a tunable cooperativeness factor, proving convergence to a Nash equilibrium and demonstrating through European flight data that it effectively mitigates sector overload with minimal cooperation while maintaining scalability comparable to centralized benchmarks.

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

Published 2026-07-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jaehan Im, Daniel Delahaye, 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 the sky above Europe is a giant, bustling dance floor divided into 28 different rooms (called "sectors"). Each room has a strict limit on how many dancers can fit inside at once—let's say 10 people. If too many dancers try to squeeze in, the room gets "overloaded," which is dangerous and chaotic.

For a long time, air traffic managers tried to solve this with a "Big Boss" approach: one central controller looking at the whole dance floor, telling every single dancer exactly when to start moving to keep everyone safe. But as the dance floor gets bigger and more complex, this central boss gets overwhelmed, and in some parts of the world, this central control just isn't possible.

So, the authors of this paper asked: What if we let each room manage its own dancers, but with a twist? They didn't want to assume everyone is a selfless hero who will sacrifice their own comfort to help others. Instead, they built a game where every room is a bit selfish, but willing to be just a tiny bit nice.

The "Selfish-but-Slightly-Nice" Game

The researchers created a system where each room (sector) acts like a player in a game. Their goal is to get their own room as empty as possible. They can do this by nudging the departure times of the flights they control—like telling a plane to wait 5, 10, or even 30 minutes before taking off.

Here is the clever part: They introduced a "cooperativeness knob" called $\kappa$ (kappa).

If you turn the knob to 0: The room is purely selfish. It only cares about its own crowd. It will delay flights to clear its own room, even if that makes a neighbor's room even more crowded.
If you turn the knob to 1: The room is a total altruist. It cares about the total crowd in the entire sky, even if it means its own room gets more crowded.
The Sweet Spot: The paper found that you don't need the knob at 1. You only need to turn it up a tiny bit (like $10^{-6}$ , which is practically zero but not quite). This represents a "self-prioritizing cooperative" behavior. It means a room will only help the neighbors if it doesn't hurt itself. It's like saying, "I'll help you move your luggage, but only if I don't drop my own suitcase."

The Rules of the Game

To make sure this game doesn't spiral out of control, the authors added one strict rule: No New Overloads.
A room can change its schedule to help itself, but it is strictly forbidden from making a move that creates a new overload in a room that was previously fine. It's like a rule in a game of musical chairs: you can shuffle your seat to get comfortable, but you can't push someone else out of their chair if they were sitting safely before.

The paper proves mathematically that if everyone follows this rule and adjusts their schedules one by one (using a "best response" strategy), the game will eventually stop. It won't go on forever; it will settle into a stable state where no one can improve their situation without breaking the rules. This is called reaching a "pure Nash equilibrium."

What the Experiments Showed

The team tested this idea using 24 hours of real flight data from July 27, 2023, covering 42,783 flights across 1,128 sectors in Europe. They focused heavily on a specific region called the BREST Flight Information Region, which had 1,247 flights moving through 28 sectors.

Here is what happened in their simulations:

The Selfish Approach ( $\kappa = 0$ ): The rooms tried to fix their own problems, but they left a huge mess. They only reduced the initial overload by about 47%. It was like everyone trying to fix their own room while accidentally kicking the problem down the hall.
The "Tiny Bit Nice" Approach ( $\kappa = 10^{-6}$ ): This was the magic moment. In the standard test where the room capacity was set to 10 aircraft, this microscopic amount of cooperation was enough to completely eliminate the overload. The rooms managed to coordinate just enough to clear the skies without anyone needing to be a saint. However, in a harder "stress test" where the capacity was lowered to just 7 aircraft, the system could not completely clear the skies, but it still drastically reduced the congestion.
The Comparison: They compared their method to two other ways of handling traffic:
1. The Centralized Solver: A super-computer trying to solve everything at once. It did a good job but often left a tiny bit of overload remaining and took a long time to compute.
2. First-Come-First-Served (FCFS): This is how things often work now—planes just wait in line. This was the worst performer, only reducing overload by 2.5% on average.

The Verdict

The paper suggests that you don't need a central boss or a group of selfless angels to keep the skies safe. You just need a system where everyone is allowed to be mostly selfish, as long as they agree to one simple rule: Don't make a neighbor's problem worse.

In their tests, this "regulated decentralized" approach was just as good at clearing the skies as the central computer in standard scenarios, but it was much faster for each individual room to do its own math. Even when they made the test harder by lowering the room capacity to 7 aircraft (a stress test), the "tiny bit nice" approach still reduced overload by 76.8%, outperforming the central computer's 60% reduction. While it didn't completely eliminate the remaining congestion in this difficult scenario, it achieved the lowest residual overload of all methods tested.

The authors are careful to note that these results come from computer simulations using real data, not from a live test in the sky. But the math proves the game works, and the simulations show that even a whisper of cooperation is enough to turn a chaotic dance floor into a smooth, safe flow of traffic.

Technical Summary: Game-theoretic Regulated Decentralized Coordination for Airspace Sector Overload Mitigation

1. Problem Statement

The paper addresses the challenge of sector overload in decentralized Air Traffic Management (ATM) systems. As air traffic complexity increases, centralized control faces scalability issues, prompting a shift toward decentralized approaches. However, existing decentralized models often rely on unrealistic assumptions of high cooperation and information sharing among stakeholders. In practice, airspace sectors operate independently, prioritizing local objectives over system-wide outcomes, which leads to coordination gaps and persistent overloads (where aircraft counts exceed sector capacity).

The core problem is formulated as a multi-agent decision-making challenge: how to mitigate sector overloads in a decentralized setting where agents (sectors) are self-interested, possess limited data exchange, and cannot rely on a central authority for joint optimization. The goal is to adjust flight departure times to eliminate overloads while ensuring the system converges to a stable, deterministic schedule without requiring full altruism from all agents.

2. Methodology

2.1. Game-Theoretic Formulation

The authors model the sector overload problem as a non-cooperative game where each sector is an agent.

Decision Variables: Each sector $i$ controls the departure times of its flights, selecting from a discrete set of adjustments (e.g., 0 to 30 minutes in 5-minute increments).
Cost Function: A tunable cost function $J_i(x)$ $J_{i} (x)$ is defined for each sector:
$J_i(x) = L_i(x) + \kappa \sum_{j \in M \setminus \{i\}} L_j(x)$
Where $L_i(x)$ $L_{i} (x)$ is the cumulative overload of sector $i$ $i$ , and $\kappa \in [0, 1]$ $κ \in [0, 1]$ is a cooperativeness factor.
- $\kappa = 0$ : Fully self-interested behavior (minimizing only local overload).
- $\kappa = 1$ : Fully cooperative behavior (minimizing total system overload).
- Intermediate values allow for "self-prioritizing cooperation," where a sector considers others' overload only if it does not worsen its own.

2.2. Update Mechanism: Best-Response Dynamics

The system evolves via best-response dynamics, where sectors sequentially update their schedules to minimize their local cost function given the current actions of others.

No-New-Overload Restriction: To ensure stability and convergence, a regulatory constraint is imposed: an agent is restricted from taking an action that creates a new overload in any sector-time pair that was previously feasible.
Algorithm: A decentralized algorithm (Algorithm 1) iterates through sectors. Each sector solves a local optimization problem (approximated via a Genetic Algorithm) to find a best response that reduces its cost without violating the no-new-overload constraint.

2.3. Theoretical Framework

The paper establishes the game's properties to guarantee convergence:

Potential Game Structure: For $\kappa = 1$ , the game is proven to be a potential game, where the potential function corresponds to the total system overload.
Convergence Guarantees:
- For $\kappa = 1$ , best-response dynamics unconditionally converge to a pure Nash equilibrium.
- For $0 \le \kappa < 1$ , convergence to a pure Nash equilibrium is guaranteed in finite time under the "no-new-overload" restriction. The proof relies on the monotonic decrease of the set of overloaded sector-time pairs.
Feasibility: A sufficient condition is identified where any feasible (overload-free) solution corresponds to a global minimizer of the potential function when $\kappa = 1$ .

3. Key Contributions

Regulated Decentralized Protocol: Proposes a mechanism that bridges the gap between fully centralized optimization and unconstrained decentralized decision-making by introducing a tunable cooperativeness factor and a minimal admissibility rule.
Theoretical Convergence: Provides rigorous proofs that the proposed best-response dynamics converge to a pure Nash equilibrium in finite time, even with limited cooperation ( $\kappa < 1$ ), provided the "no-new-overload" restriction is met.
Self-Prioritizing Cooperation: Demonstrates theoretically and empirically that full altruism is not required. A minimal degree of cooperation (where agents help others only if it doesn't hurt themselves) is sufficient to achieve system-wide overload mitigation.
Scalability and Performance: Validates the approach using 24 hours of real European flight data (42,783 flights), showing that the decentralized approach scales comparably to centralized solvers in total runtime while distributing the computational burden.

4. Experimental Results

The authors evaluated the algorithm using 24 hours of flight data from the European airspace (specifically the BREST Flight Information Region with 28 sectors and 1,247 flights).

Impact of Cooperativeness ( $\kappa$ ):
- $\kappa = 0$ (Self-interested): Failed to resolve overloads effectively, reducing initial overload by only ~47%.
- $\kappa > 0$ (Minimal to Full Cooperation): Even a minimal cooperativeness factor ( $\kappa = 10^{-6}$ ) was sufficient to eliminate all overloads in the standard capacity scenario ( $D=10$ ).
- $\kappa = 1$ (Full Cooperation): Consistently eliminated overloads, matching or exceeding the performance of a centralized genetic algorithm benchmark.
Comparison with Baselines:
- Centralized Solver: While effective, the centralized genetic algorithm benchmark (used for fair comparison) often failed to find strictly feasible solutions, leaving residual overload.
- First-Come-First-Served (FCFS): Performed poorly, reducing overload by only ~2.5%.
- Decentralized Algorithm: With $\kappa > 0$ , it consistently achieved overload-free solutions, outperforming both the FCFS heuristic and the centralized benchmark in finding feasible schedules.
Stress Tests: In a harder scenario with reduced capacity ( $D=7$ ), the decentralized algorithm with $\kappa > 0$ achieved the lowest residual overload (up to 78.3% reduction), outperforming the centralized solver (60% reduction).
Scalability: The total runtime of the decentralized algorithm scaled similarly to the centralized solver as the number of flights increased (up to 10,000). However, the per-agent computational load was significantly lower (approx. 4-6% of the centralized load), demonstrating the efficiency of distributing the computation.

5. Significance and Claims

The paper claims that effective decentralized coordination for ATM does not require full altruism or a central planner. The primary significance lies in demonstrating that minimal cooperation—specifically, a willingness to account for other sectors' overloads as long as one's own situation is not worsened—is sufficient to achieve near-centralized performance in mitigating sector overloads.

The authors emphasize that their approach offers a practical pathway for regulated decentralized ATM. By enforcing a "no-new-overload" protocol, the system guarantees convergence to a deterministic, stable equilibrium (pure Nash equilibrium) without requiring the high levels of trust and information sharing that often fail in real-world international or boundary airspace sectors. The results suggest that such a framework could be operationally meaningful in settings where agents retain local decision authority but adhere to a common, simple regulatory constraint.

The paper concludes modestly, noting that while the current formulation uses fixed capacities and occupancy metrics, future work should integrate dynamic sector configurations, rerouting, and uncertainty in demand forecasts. The authors also clarify that their use of a genetic algorithm for the centralized benchmark was a methodological choice for fair comparison, acknowledging that state-of-the-art integer programming solvers could likely find feasible solutions faster for the specific dataset used.