Networks and distributed operation : the price of anarchy in non-atomic routing and network formation

Kliemann, Lasse

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.

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.

Preview

Quote

Citation style:

Kliemann, Lasse: Networks and distributed operation : the price of anarchy in non-atomic routing and network formation.

Rights

Use and reproduction:
No CC License (german copyright law applies)

Export