Invited Session Fri.2.MA 005

Friday, 13:15 - 14:45 h, Room: MA 005

Cluster 8: Game theory [...]

Competition on networks


Chair: Nicolas Stier-Moses and Jose Correa



Friday, 13:15 - 13:40 h, Room: MA 005, Talk 1

Evdokia Nikolova
A mean-risk model for the stochastic traffic assignment problem

Coauthor: Nicolas Stier-Moses


We embark on an agenda to investigate how stochastic travel times and risk aversion transform the traditional traffic assignment problem and its corresponding equilibrium concepts. Moving from deterministic to stochastic travel times with risk-averse users introduces non-convexities that make the problem more difficult to analyze. For example, even computing a best response of a user to the environment is still of unknown complexity. This paper focuses on equilibrium existence and characterization in the different settings of infinitesimal (non-atomic) vs. atomic users and fixed (exogenous) vs. congestion-dependent (endogenous)
variability of travel times. Because cost functions are non-additive, solutions need to be represented as path flows. Nevertheless, we show that succinct representations of equilibria and optimal solutions always exist. We also obtain that under exogenous variability of travel times, the worst-case inefficiency of equilibria (the price of anarchy) is exactly the same as when travel time functions are deterministic, meaning that in this case risk-aversion under stochastic travel times does not further degrade a system in the worst-case.



Friday, 13:45 - 14:10 h, Room: MA 005, Talk 2

Nicolas Stier-Moses
The competitive facility location problem in a duopoly: Advances beyond trees

Coauthor: Yoni Gur


We consider a competitive facility location game on a network where consumers located on vertices wish to connect to the nearest facility. Knowing this, competitors place facilities on vertices to maximize market share. Focusing in the two-player case, we study conditions that guarantee the existence of pure-strategy Nash equilibria for progressively more complicated networks. The case of trees, which extends the classic Hotelling model, is well-studied: equilibria are characterized by centroids of the tree. We find that cycles admit equilibria when there are vertices with sufficiently big demands. For a general graph, we construct a tree of maximal bi-connected components and apply the results for trees and cycles to get sufficient conditions for equilibrium existence. This provides a complete and efficient characterization of equilibria for networks where the central bi-connected component is a vertex or a cycle. We quantify the maximum inefficiency of equilibria with bounds that depend on topological parameters of the network. These bounds rely on trees, which are worst instances because for these games removing an edge from a graph always increases consumer cost.



Friday, 14:15 - 14:40 h, Room: MA 005, Talk 3

Fernando Ordonez
Stackelberg security games on networks

Coauthor: Tomas Spencer


Stackelberg games have recently been used in security applications to decide optimal patrolling strategies in the presence of strategic adversaries that can monitor the security actions prior to deciding on how and where to attack. By using column generation and other decomposition methods we have been able to solve large enough problems to consider interesting real world situations.
These methods, however, break down as the number of adversary actions grows. In this work we consider the problem of patrolling a network where we decide the optimal location of fixed guards and the adversaries select a feasible path to attack. We develop decomposition algorithms to solve this problem and study the conditions for this algorithm to be exact. In particular we show that in the non zero sum case this standard decomposition method can get stuck on a sub-optimal solution.


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.