PT Unknown
AU Kliemann, L
TI Networks and distributed operation: the price of anarchy in non-atomic routing and network formation
PY 2010
PU Christian-Albrechts-Universität zu Kiel
WP https://macau.uni-kiel.de/receive/diss_mods_00005523
LA en
DE Game Theory; Nash Equilibrium; Price of Anarchy; Non-Atomic Congestion Games; Multicast Routing; Distributed Network Formation; Network Creation Game; Pairwise Nash Equilibrium; Pairwise Stability; Unilateral Link Formation; Bilateral Link Formation; Adversary Model; Robustness; Spieltheorie; Nash-Gleichgewicht; Preis der Anarchie; Nicht-atomare Auslastungspiele; Multicast-Routing; Verteilte Netzwerkformierung; Netzwerkerzeugungspiele; paarweises Nash-Gleichgewicht; paarweise Stabilität; unilaterale Formierung; bilaterale Formierung; Gegnermodell; Robustheit
AB The price of anarchy is a measure for performance loss due to individuals operating in a distributed manner, i.e., without or with only limited central control or without or with only limited cooperation.
In the first part, a network is given and used in a distributed manner, namely for multicast routing, i.e., each sender wishes to transmit a message to multiple receivers simultaneously. We prove almost tight upper and lower bounds on the price of anarchy and conduct an experimental study. 
In the second part, a network is formed. Each vertex of the (to-be-built) network may invest in the building of links. The formation takes place under the knowledge that an adversary will later delete exactly one link. Vertices wish to maintain good connectivity. We prove tight upper and lower bounds on the price of anarchy for two different adversaries.
PI Kiel
ER