Sobecké trasování a cena anarchie

Recenze čtenářů

Kniha poskytuje hluboký pohled na matematické základy sobeckého směrování a z toho vyplývající ztrátu optimality v sítích. Zabývá se praktickými důsledky pro návrh sítí, zdůrazňuje kompromisy mezi výkonem a náklady a představuje příslušné koncepty na jasných příkladech. Předpokládá však silné matematické zázemí, což může omezit její přístupnost širšímu publiku, zejména správcům sítí bez takového zázemí.

Komplexní úvod do sobeckého směrování a jeho důsledky pro návrh sítě.

Poskytuje praktické nástroje a strategie pro návrháře sítí.

(na základě 4 hodnocení čtenářů)

Původní název:

Selfish Routing and the Price of Anarchy

Obsah knihy:

Analýza ztráty výkonnosti způsobené sobeckým, nekoordinovaným chováním v sítích.

Většina z nás dává přednost dojíždění nejkratší dostupnou trasou, aniž by brala v úvahu dopravní zácpy, které způsobuje ostatním. Mnoho sítí, včetně počítačových, trpí určitým typem tohoto "sobeckého směrování". Tim Roughgarden v knize Selfish Routing and the Price of Anarchy (Sobecké směrování a cena anarchie) studuje ztrátu společenského blahobytu způsobenou sobeckým, nekoordinovaným chováním v sítích. Vyčísluje cenu anarchie - nejhorší možnou ztrátu společenského blahobytu způsobenou sobeckým směrováním - a také se zabývá několika metodami zlepšení ceny anarchie pomocí centralizovaného řízení.

Roughgarden začíná relativně netechnickým úvodem do sobeckého směrování a popisuje dva důležité příklady, které motivují následující problémy. První z nich, Pigouův příklad, ukazuje, že sobecké chování nemusí vést ke společensky optimálnímu výsledku. Druhý, Braessův paradox, ukazuje, že vylepšení sítě může zhoršit její výkonnost. Poté rozvíjí techniky pro kvantifikaci ceny anarchie (přičemž Pigouův příklad hraje ústřední roli). Dále analyzuje Braessův paradox a výpočetní složitost jeho algoritmického odhalení a popisuje Stackelbergovo směrování, které zlepšuje cenu anarchie pomocí mírného stupně centrálního řízení. Nakonec definuje několik otevřených problémů, které mohou inspirovat další výzkum. Roughgardenova práce bude zajímavá nejen pro výzkumné pracovníky a postgraduální studenty teoretické informatiky a optimalizace, ale i pro ostatní informatiky, stejně jako pro ekonomy, elektroinženýry a matematiky.