Equilibria in Routing Games with Edge Priorities
| Autor: | Martin Strehler, Laura Vargas Koch, Robert Scheffler |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Computer Science::Computer Science and Game Theory
Mathematical optimization Class (computer programming) Computer science Connection (vector bundle) TheoryofComputation_GENERAL 0102 computer and information sciences 02 engineering and technology 01 natural sciences symbols.namesake 010201 computation theory & mathematics Nash equilibrium 0202 electrical engineering electronic engineering information engineering symbols Price of anarchy 020201 artificial intelligence & image processing Enhanced Data Rates for GSM Evolution Price of stability Routing (electronic design automation) Algorithmic game theory |
| Zdroj: | Web and Internet Economics ISBN: 9783030046118 WINE |
| Popis: | In this paper, we present a new routing model with edge priorities. We consider network users that route packages selfishly through a network over time and try to reach their destinations as fast as possible. If the number of packages that want to enter an edge at the same time exceeds the inflow capacity of this edge, edge priorities with respect to the preceding edge solve these conflicts. For this class of games, we show the existence of equilibrium solutions for single-source-single-sink games and we analyze structural properties of these solutions. We present an algorithm that computes Nash equilibria and we prove bounds both on the Price of Stability and on the Price of Anarchy. Moreover, we introduce the new concept of the Price of Mistrust and analyze the connection to earliest arrival flows. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|