## Invited Session Thu.1.H 0106

#### Thursday, 10:30 - 12:00 h, Room: H 0106

**Cluster 13: Logistics, traffic, and transportation** [...]

### Analysis of decentralized network systems

**Chair: Ozlem Ergun and Luyi Gui**

**Thursday, 10:30 - 10:55 h, Room: H 0106, Talk 1**

**Daniela Saban**

The competitive facility location game: Equilibria and relations to the 1-median problem

**Coauthor: Nicolas E. Stier-Moses**

**Abstract:**

We consider a competitive facility location problem on a network in which consumers are located on the vertices and wish to connect to the nearest facility. Knowing this, competitive players locate their facilities on vertices that capture the largest-possible market share. The competitive facility location problem was first proposed by Hotelling in 1929, where two ice-cream sellers compete on a mile of beach with demand uniformly distributed among the shore. It is well-known that a generalization of that game on a tree always admits an equilibrium. Furthermore, a location profile is an equilibrium if and only if both players locate their facilities in a 1-median of the tree. In this work, we further

explore the relationship between the 1-median problem and the

equilibria in competitive facility location games with two players. We generalize the previous result to the class of strongly chordal graphs, which strictly contains trees. In addition, we show that for certain classes of graphs in which an equilibrium does not always exist (such as cycles), if there is an equilibrium, it must satisfy that both players select vertices that solve the 1-median problem.

**Thursday, 11:00 - 11:25 h, Room: H 0106, Talk 2**

**Luyi Gui**

A robustness analysis of a capacity exchange mechanism in multicommodity networks under demand uncertainty

**Coauthor: Ozlem Ergun**

**Abstract:**

We study the coordination of a decentralized multicommodity network system with individually-owned capacities by designing a capacity exchange mechanism under which capacity is traded according to predetermined unit prices. The goal is to maximize the social efficiency, measured by the total routing revenue, of the flow composed by individual playersâ€™ selfish routing of their own commodities motivated by the mechanism. A practical challenge to do this arises from uncertainties in demand, as in many cases the mechanism is designed before the demand is revealed. Hence, it is desirable that the capacity exchange mechanism is robust, i.e., it can effectively coordinate the network under all potential demand scenarios using a fixed set of exchange prices. In this paper, we perform the following two studies on the robustness of the capacity exchange mechanism under demand uncertainty. First, we characterize how network structure affects the robustness of the

mechanism. Second, we investigate the computational side of designing a robust capacity exchange mechanism

in any given network. We propose a general pricing algorithm and quantify the routing

performance under the prices computed.

**Thursday, 11:30 - 11:55 h, Room: H 0106, Talk 3**

**Douglas Fearing**

Managing air traffic disruptions through strategic prioritization

**Coauthor: Ian Kash**

**Abstract:**

In the U.S., air traffic congestion places a tremendous financial burden on airlines, passengers, and the economy as a whole. Outside of capacity increases, there are, broadly, two approaches to address congestion. The first is to manage existing capacity more effectively, while the second is to incentivize airlines to schedule fewer flights. In our work, we show how to accomplish both through *strategic prioritization*, a competitive scheme that allows airlines to make flight priority decisions in advance of operations. When there is a disruption, the specified priorities allow the regulator to ration capacity more effectively. Additionally, making these trade-offs causes more of the congestion-related costs to be internalized by each airline, thus reducing over-scheduling. Specifically, our approach requires airlines to bid for a proportional allocation of a fixed pool of prioritization minutes at each airport. We then modify the existing capacity rationing scheme by treating prioritized flights as if they had been scheduled earlier than their actual time. We demonstrate the benefits of this approach through both simulation and theoretical results.