Sebecké smerovanie a cena anarchie

Recenzie čitateľov

Kniha ponúka dôkladné preskúmanie sebeckého smerovania a z neho vyplývajúcej straty optimality, pričom prepája matematiku, informatiku a ekonomickú teóriu. Je dobre štruktúrovaná s jasnými definíciami, tvrdeniami a príkladmi, ktoré ju sprístupňujú čitateľom oboznámeným s reálnou analýzou a optimalizáciou. Autor predstavuje významné pojmy, ako je cena anarchie, Braessov paradox a Nashova rovnováha, a zároveň poskytuje praktické nástroje na návrh siete.

Komplexný úvod do matematických a výpočtových základov sebeckého smerovania.

Prehľadná štruktúra s definíciami, tvrdeniami a príkladmi, ktoré pomáhajú porozumieť.

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