Inefficiency of pure Nash equilibria in series-parallel network congestion games

We study the inefficiency of pure Nash equilibria in symmetric unweighted network congestion games defined over series-parallel networks. We introduce a quantity y(D) to upper bound the Price of Anarchy (PoA) for delay functions in class D. When D is the class of polynomial functions with highest degree p, our upper bound is 2^{p+1} − … Read more

The Price of Anarchy in Series-Parallel Network Congestion Games

We study the inefficiency of pure Nash equilibria in symmetric network congestion games defined over series-parallel networks with affine edge delays. For arbitrary networks, Correa (2019) proved a tight upper bound of 5/2 on the PoA. On the other hand, for extension-parallel networks, a subclass of series-parallel networks, Fotakis (2010) proved that the PoA is … Read more

Vanishing Price of Anarchy in Large Coordinative Nonconvex Optimization

We focus on a class of nonconvex cooperative optimization problems that involve multiple participants. We study the duality framework and provide geometric and analytic character- izations of the duality gap. The dual problem is related to a market setting in which each participant pursuits self interests at a given price of common goods. The duality … Read more

Price of Anarchy for Non-atomic Congestion Games with Stochastic Demands

We generalize the notions of user equilibrium and system optimum to non-atomic congestion games with stochastic demands. We establish upper bounds on the price of anarchy for three different settings of link cost functions and demand distributions, namely, (a) affine cost functions and general distributions, (b) polynomial cost functions and general positive-valued distributions, and (c) … Read more

Preferences for Travel Time under Risk and Ambiguity: Implications in Path Selection and Network Equilibrium

In this paper, we study the preferences for uncertain travel time in which the probability distribution may not be fully characterized. In evaluating an uncertain travel time, we explicitly distinguish between risk, where probability distribution is precisely known, and ambiguity, where it is not. In particular, we propose a new criterion called ambiguity-aware CARA travel … Read more

Efficiency and Fairness of System-Optimal Routing with User Constraints

We study the route-guidance system proposed by Jahn, Möhring, Schulz and Stier-Moses (2004) from a theoretical perspective. This approach computes a traffic pattern that minimizes the total travel time subject to user constraints, which ensure that routes suggested to users are not much longer than shortest paths. We show that when distances are measured with … Read more