Samolubne wyznaczanie tras i cena anarchii

Opinie czytelników

Książka zapewnia wnikliwą eksplorację matematycznych podstaw samolubnego routingu i wynikającej z tego utraty optymalności w sieciach. Odnosi się do praktycznych implikacji dla projektowania sieci, kładzie nacisk na kompromisy między wydajnością a kosztami i wprowadza odpowiednie koncepcje z jasnymi przykładami. Zakłada jednak silne zaplecze matematyczne, co może ograniczyć jego dostępność dla szerszego grona odbiorców, w szczególności menedżerów sieci bez takiego zaplecza.

Kompleksowe wprowadzenie do samolubnego routingu i jego implikacji w projektowaniu sieci.

Zawiera praktyczne narzędzia i strategie dla projektantów sieci.

(na podstawie 4 opinii czytelników)

Oryginalny tytuł:

Selfish Routing and the Price of Anarchy

Zawartość książki:

Analiza spadku wydajności spowodowanego samolubnym, nieskoordynowanym zachowaniem w sieciach.

Większość z nas woli dojeżdżać do pracy najkrótszą dostępną trasą, nie biorąc pod uwagę korków, które powodujemy dla innych. Wiele sieci, w tym sieci komputerowych, cierpi z powodu pewnego rodzaju "samolubnego routingu". W książce Selfish Routing and the Price of Anarchy Tim Roughgarden bada utratę dobrobytu społecznego spowodowaną samolubnym, nieskoordynowanym zachowaniem w sieciach. Określa on cenę anarchii - najgorszą możliwą utratę dobrobytu społecznego z powodu samolubnego routingu - a także omawia kilka metod poprawy ceny anarchii za pomocą scentralizowanej kontroli.

Roughgarden rozpoczyna od stosunkowo nietechnicznego wprowadzenia do samolubnego routingu, opisując dwa ważne przykłady, które motywują kolejne problemy. Pierwszy z nich, przykład Pigou, pokazuje, że samolubne zachowanie nie musi generować społecznie optymalnego wyniku. Drugi, kontrintuicyjny paradoks Braessa, pokazuje, że ulepszenia sieci mogą obniżyć jej wydajność. Następnie rozwija techniki kwantyfikacji ceny anarchii (z przykładem Pigou odgrywającym kluczową rolę). Następnie analizuje paradoks Braessa i złożoność obliczeniową algorytmicznego wykrywania go, a także opisuje routing Stackelberga, który poprawia cenę anarchii przy użyciu niewielkiego stopnia centralnej kontroli. Na koniec definiuje kilka otwartych problemów, które mogą zainspirować dalsze badania. Praca Roughgardena będzie interesująca nie tylko dla badaczy i absolwentów informatyki teoretycznej i optymalizacji, ale także dla innych informatyków, a także ekonomistów, inżynierów elektryków i matematyków.