License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2018.13
URN: urn:nbn:de:0030-drops-97186
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9718/
Go to the corresponding OASIcs Volume Portal

Peis, Britta ; Tauer, Bjoern ; Timmermans, Veerle ; Vargas Koch, Laura

Oligopolistic Competitive Packet Routing

pdf-format:
OASIcs-ATMOS-2018-13.pdf (0.5 MB)

Abstract

Oligopolistic competitive packet routing games model situations in which traffic is routed in discrete units through a network over time. We study a game-theoretic variant of packet routing, where in contrast to classical packet routing, we are lacking a central authority to decide on an oblivious routing protocol. Instead, selfish acting decision makers ("players") control a certain amount of traffic each, which needs to be sent as fast as possible from a player-specific origin to a player-specific destination through a commonly used network. The network is represented by a directed graph, each edge of which being endowed with a transit time, as well as a capacity bounding the number of traffic units entering an edge simultaneously. Additionally, a priority policy on the set of players is publicly known with respect to which conflicts at intersections are resolved. We prove the existence of a pure Nash equilibrium and show that it can be constructed by sequentially computing an integral earliest arrival flow for each player. Moreover, we derive several tight bounds on the price of anarchy and the price of stability in single source games.

BibTeX - Entry

@InProceedings{peis_et_al:OASIcs:2018:9718,
  author =	{Britta Peis and Bjoern Tauer and Veerle Timmermans and Laura Vargas Koch},
  title =	{{Oligopolistic Competitive Packet Routing}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation  Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{13:1--13:22},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Ralf Bornd{\"o}rfer and Sabine Storandt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9718},
  URN =		{urn:nbn:de:0030-drops-97186},
  doi =		{10.4230/OASIcs.ATMOS.2018.13},
  annote =	{Keywords: Competitive Packet Routing, Nash Equilibrium, Oligopoly, Efficiency of Equilibria, Priority Policy}
}

Keywords: Competitive Packet Routing, Nash Equilibrium, Oligopoly, Efficiency of Equilibria, Priority Policy
Collection: 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)
Issue Date: 2018
Date of publication: 28.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI