Improving Evacuation Plans Through Game Theory

Evacuation planning is a key part of managing disasters. When a danger, such as a hurricane or wildfire, threatens a community, it is vital to safely relocate people to avoid harm. While officials may suggest specific routes and times for leaving, individuals often make their own choices based on personal preferences. This self-interested behavior can lead to chaos and inefficiency during the evacuation process. It is important to study how these individual decisions affect the overall evacuation.

Existing research usually looks at how people choose their routes. However, we need to consider both the routes and the timing of leaving. In this work, we introduce a new game called the Evacuation Planning Game. This game allows players to select both their evacuation route and when to leave. We focus on situations where multiple routes converge, meaning that if two routes meet at a point, the remainder of their paths is the same.

#The Importance of Evacuation Planning

Effective evacuation plans are crucial for ensuring the safety of people living in areas at risk of natural or human-made disasters. Past hurricanes in states like Florida and Texas have shown that large-scale evacuations are necessary to protect lives. In 2022, for example, millions evacuated from Florida ahead of Hurricane Ian. Similar actions were taken during other significant hurricanes over the years.

It's essential for communities to have plans that make evacuations smooth and efficient. Local governments often provide routes and schedules to facilitate orderly evacuations. However, individuals tend to act based on their interests. Research has shown that many people do not follow official instructions and instead choose familiar paths that they believe are faster or less crowded.

Understanding how this behavior impacts evacuation becomes crucial. This work aims to present a game-theoretic approach to evacuation planning that factors in how individuals choose their routes and departure times.

#Game Theory in Evacuation Planning

In the Evacuation Planning Game, each player aims to minimize their time taken to reach safety. Players can choose their route and the time they leave. We also include a feature known as Dynamic Flows, which means that traffic on roads can change over time due to various factors, such as how many people are traveling on those routes.

We focus specifically on confluent evacuation plans. This means that once evacuees reach an intersection, they will take the same outgoing road. Following this structure can help reduce confusion and delays that typically occur in evacuation scenarios.

Our work builds on existing research but adds new dimensions by allowing players to make both routing and timing decisions. We prove that every instance of our game has at least one stable outcome, known as a pure strategy Nash equilibrium. Moreover, we provide a quick method to find these equilibria in the game.

#The Structure of Evacuation Networks

An evacuation network consists of roads that connect different locations, including sources of evacuees and safe places. Each road has specific characteristics, like how many vehicles it can support at any time and how long it takes to travel.

Players in our game represent different groups of evacuees coming from various locations. They need to choose both their route and a time to leave. The outcome of the game is determined by the combined choices made by all players.

To make sure every player reaches safety without exceeding capacity limits on the roads, we define utility functions for the players. A utility function indicates how satisfied each player is with the outcome based on how quickly and smoothly they can evacuate.

#Connections to Existing Research

Research in game theory has extensively examined routing and congestion games. In these studies, researchers have focused mainly on how to minimize delays when multiple players are trying to navigate through a network.

In earlier models, players only chose routes, but our game expands by allowing players to consider when to leave as well. This additional choice of departure time is critical in evacuation scenarios, primarily since the flow of traffic can vary significantly.

Past studies have also focused on the fact that players don’t move instantly through the network. Instead, they travel along their routes over time, creating dynamic traffic conditions.

Although some previous works explored converging routes, they did not do so from a game-theoretic standpoint. Our study makes this connection, emphasizing the need to incorporate game strategies into evacuation planning.

#Contributions of This Study

Our contributions to the field of evacuation planning include several key points:

1. We introduced the Evacuation Planning Game, allowing players to choose routes and times of departure while incorporating dynamic flows.
2. We demonstrated that every instance of the game has at least one stable outcome, which is an essential finding for evacuation dynamics.
3. We developed a quick algorithm for finding these stable outcomes, recognizing the complexity of optimizing evacuation routes and schedules.
4. We explored the effectiveness of our game by constructing a specific instance based on real-world data from Harris County, Texas.

The results from this game indicate that we can achieve outcomes that significantly align with socially optimal standards.

#Problem Statement and Formulation

In our game, the evacuation network is represented as a directed graph with roads that connect different nodes. Each node represents a specific location, such as evacuation sources, safe zones, and transitional points.

Players can choose from various paths from their starting points to safe places while considering how many evacuees they have and the maximum time allowed for evacuation. The goal is to ensure that all players reach their destinations without breaching the maximum capacity of the roads.

We define a valid dynamic flow as one that allows all evacuees to arrive at safe places without any road exceeding its vehicle capacity. A confluent evacuation schedule ensures that evacuees follow uniform routes after reaching intersections.

#Theoretical Analysis

We explored several theoretical questions about our game, such as whether a stable outcome exists in every situation, how quickly we can find it, and what bounds exist on how inefficient these outcomes may be.

To answer whether stable outcomes always exist, we proved that each instance of our game indeed contains at least one pure strategy Nash equilibrium. This finding is crucial since it guarantees that players can coordinate effectively under the framework established by our game.

We also presented a method to find these equilibria efficiently, knowing that optimal evacuation schedules can become complex quickly. Our analysis shows promising results, especially concerning how far from optimal solutions the equilibria might be.

#Price Of Anarchy

The concept of Price of Anarchy refers to how much worse the outcomes can be when individuals act selfishly compared to when they cooperate for a collective goal. Understanding this price helps determine how well our evacuation game performs.

By analyzing the upper and lower bounds of Price of Anarchy for our evacuation game, we can estimate the potential inefficiencies of the equilibria derived from individual choices.

Through our theoretical work, we demonstrate that the Price of Anarchy is manageable, meaning that although individual choices may lead to suboptimal outcomes, the discrepancies are limited, leading to reasonably efficient evacuations.

#Empirical Evaluation in Harris County

To analyze the practical applications of our game, we chose Harris County, Texas, as a case study. This region is especially vulnerable to hurricanes and necessitates effective evacuation strategies.

Using data from local road networks and population datasets, we constructed a game instance that mimics real evacuation conditions. By applying our game, we observed how different player permutations led to various equilibrium outcomes.

Results showed that the equilibria reached through our game had social objective values close to optimal ones, supporting the effectiveness of our approach in practical scenarios.

#Conclusion

This work presents a meaningful advancement in evacuation planning by introducing a game-theoretic framework that accounts for individual decision-making. Recognizing how players navigate both routes and timing offers insight into the complexities of evacuation dynamics.

We proved every instance of our Evacuation Planning Game has a stable outcome, providing a quick method to determine these outcomes. The analysis of practical implementations in areas like Harris County demonstrates that our game can lead to effective planning in real-world situations.

While our game addresses several pressing questions in evacuation planning, limitations remain. Future research could look at variables such as load-dependent travel times or relaxing certain constraints, which would further refine the model.

The work contributes to understanding how to develop better evacuation strategies that ultimately enhance community resilience in facing disasters.