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


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


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


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.


  Do you need Missouri Payday Loans as soon as possible? Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.