Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



On the Price of Anarchy for flows over time
Indexado
WoS WOS:000483848100066
Scopus SCOPUS_ID:85069042578
DOI 10.1145/3328526.3329593
Año 2019
Tipo proceedings paper

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



Dynamic network flows, or network flows over time, constitute an important model for real-world situations where steady states are unusual, such as urban traffic and the Internet. These applications immediately raise the issue of analyzing dynamic network flows from a game-theoretic perspective. In this paper we study dynamic equilibria in the deterministic fluid queuing model in single-source single-sink networks, arguably the most basic model for flows over time. In the last decade we have witnessed significant developments in the theoretical understanding of the model. However, several fundamental questions remain open. One of the most prominent ones concerns the Price of Anarchy, measured as the worst case ratio between the minimum time required to route a given amount of flow from the source to the sink, and the time a dynamic equilibrium takes to perform the same task. Our main result states that if we could reduce the inflow of the network in a dynamic equilibrium, then the Price of Anarchy is exactly e/(e-1) approximate to 1.582. This significantly extends a result by Bhaskar, Fleischer, and Anshelevich (SODA 2011). Furthermore, our methods allow to determine that the Price of Anarchy in parallel-link networks is exactly 4/3. Finally, we argue that if a certain very natural monotonicity conjecture holds, the Price of Anarchy in the general case is exactly e/(e-1).

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Sin Disciplinas
Scopus
Sin Disciplinas
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 CORREA-FONTECILLA, JOSE RAFAEL Hombre Universidad de Chile - Chile
2 Cristi, Andrés Hombre Universidad de Chile - Chile
3 Oosterwijk, Tim Hombre Maastricht Univ - Países Bajos
Maastricht University - Países Bajos
Universiteit Maastricht - Países Bajos
4 Assoc Comp Machinery Corporación

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
CONICYT
Comisión Nacional de Investigación Científica y Tecnológica

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
This work was partially supported by CONICYT under Grants PCI PII 20150140 and CONICYT-PFCHA/Doctorado Nacional/2018-21180347.
The authors would like to thank Dario Frascaria, Marcus Kaiser, Neil Olver, Leon Sering and Laura Vargas Koch for fruitful discussions. This work was partially supported by CONICYT under Grants PCI PII 20150140 and CONICYTPFCHA/ Doctorado Nacional/2018-21180347.

Muestra la fuente de financiamiento declarada en la publicación.