000K  utf8
1100  $c2010
1500  eng
2050  urn:nbn:de:gbv:8-diss-55231
3000  Kliemann, Lasse
4000  Networks and distributed operation: the price of anarchy in non-atomic routing and network formation$hChristian-Albrechts-Universität zu Kiel  [Kliemann, Lasse]
4000  Netzwerke und verteilte Operation: Der Preis der Anarchie in nicht-atomarem Routing und Netzwerkformierung$hChristian-Albrechts-Universität zu Kiel  [Kliemann, Lasse]
4030  Kiel$nChristian-Albrechts-Universität zu Kiel
4209  Der Preis der Anarchie ist ein Maß für den Leistungsverlust dadurch, dass Individuen in verteilter Weise operieren, d.h. dass sie nicht oder nur eingeschränkt koordiniert werden oder nicht oder nur eingeschränkt kooperieren. Im ersten Teil wird ein gegebenes Netzwerk in verteilter Weise genutzt, und zwar für Multicast-Routing, d.h. es möchte jeder Sender eine Mehrzahl Empfänger gleichzeitig erreichen. Wir beweisen nahezu scharfe obere und untere Schranken für den Preis der Anarchie und führen eine experimentelle Studie durch. Im zweiten Teil geht es um die Formierung von Netzwerken. Jeder Knoten des (zu formierenden) Netzwerkes hat die Wahl, in Verbindungen zu investieren. Bei uns findet die Netzwerkformierung unter dem Wissen statt, dass später genau eine Verbindung durch einen Gegner zerstört werden wird. Die Knoten streben an, trotzdem gut verbunden zu bleiben. Wir beweisen scharfe obere und obere Schranken für den Preis der Anarchie für zwei verschiedene Formen von Gegnern.
4209  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.
4950  https://nbn-resolving.org/urn:nbn:de:gbv:8-diss-55231$xR$3Volltext$534
4961  https://macau.uni-kiel.de/receive/diss_mods_00005523
5051  510
5550  Adversary Model
5550  bilaterale Formierung
5550  Bilateral Link Formation
5550  Distributed Network Formation
5550  Game Theory
5550  Gegnermodell
5550  Multicast Routing
5550  Multicast-Routing
5550  Nash Equilibrium
5550  Nash-Gleichgewicht
5550  Network Creation Game
5550  Netzwerkerzeugungspiele
5550  Nicht-atomare Auslastungspiele
5550  Non-Atomic Congestion Games
5550  paarweises Nash-Gleichgewicht
5550  paarweise Stabilität
5550  Pairwise Nash Equilibrium
5550  Pairwise Stability
5550  Preis der Anarchie
5550  Price of Anarchy
5550  Robustheit
5550  Robustness
5550  Spieltheorie
5550  unilaterale Formierung
5550  Unilateral Link Formation
5550  Verteilte Netzwerkformierung