Sebecké smerovanie a cena anarchie

Recenzie čitateľov

Kniha poskytuje hlboký prehľad matematických základov sebeckého smerovania a z toho vyplývajúcej straty optimality v sieťach. Zaoberá sa praktickými dôsledkami pre návrh siete, zdôrazňuje kompromisy medzi výkonnosťou a nákladmi a predstavuje príslušné koncepty na jasných príkladoch. Predpokladá však silné matematické zázemie, čo môže obmedziť jej prístupnosť širšiemu publiku, najmä manažérom sietí bez takéhoto zázemia.

Komplexný úvod do sebeckého smerovania a jeho dôsledkov pri návrhu siete.

Poskytuje praktické nástroje a stratégie pre návrhárov sietí.

(na základe 4 čitateľských recenzií)

Pôvodný názov:

Selfish Routing and the Price of Anarchy

Obsah knihy:

Analýza straty výkonnosti spôsobenej sebeckým, nekoordinovaným správaním v sieťach.

Väčšina z nás uprednostňuje dochádzanie najkratšou dostupnou trasou bez ohľadu na dopravné zápchy, ktoré spôsobuje ostatným. Mnohé siete vrátane počítačových sietí trpia určitým typom tohto "sebeckého smerovania". Tim Roughgarden v knihe Selfish Routing and the Price of Anarchy (Sebecké smerovanie a cena anarchie) skúma stratu spoločenského blahobytu spôsobenú sebeckým, nekoordinovaným správaním v sieťach. Kvantifikuje cenu anarchie - najhoršiu možnú stratu spoločenského blahobytu v dôsledku sebeckého smerovania - a tiež rozoberá niekoľko metód na zlepšenie ceny anarchie pomocou centralizovaného riadenia.

Roughgarden začína relatívne netechnickým úvodom do sebeckého smerovania a opisuje dva dôležité príklady, ktoré motivujú nasledujúce problémy. Prvý, Pigouov príklad, ukazuje, že sebecké správanie nemusí generovať spoločensky optimálny výsledok. Druhý, Braessov paradox, ukazuje, že vylepšenia siete môžu zhoršiť jej výkonnosť. Potom rozvíja techniky na kvantifikáciu ceny anarchie (pričom hlavnú úlohu zohráva Pigouov príklad). Ďalej analyzuje Braessov paradox a výpočtovú zložitosť jeho algoritmického zisťovania a opisuje Stackelbergovo smerovanie, ktoré zlepšuje cenu anarchie pomocou skromného stupňa centrálneho riadenia. Nakoniec definuje niekoľko otvorených problémov, ktoré môžu inšpirovať ďalší výskum. Roughgardenova práca bude zaujímavá nielen pre výskumníkov a postgraduálnych študentov teoretickej informatiky a optimalizácie, ale aj pre iných informatikov, ako aj pre ekonómov, elektrotechnikov a matematikov.