## 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**

**Abstract:**

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**

**Abstract:**

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**

**Abstract:**

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.