Sobecké směrování a cena anarchie

Recenze čtenářů

Kniha nabízí důkladné zkoumání sobeckého směrování a z něj vyplývající ztráty optimality a propojuje matematiku, informatiku a ekonomickou teorii. Je dobře strukturovaná, obsahuje jasné definice, teorémy a příklady, které ji zpřístupňují čtenářům obeznámeným s reálnou analýzou a optimalizací. Autor představuje významné koncepty, jako je cena anarchie, Braessův paradox a Nashova rovnováha, a zároveň poskytuje praktické nástroje pro návrh sítí.

Komplexní úvod do matematických a výpočetních základů sobeckého směrování.

Přehledná struktura s definicemi, tvrzeními a příklady, které usnadňují pochopení.

(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.