Önző útválasztás és az anarchia ára

Olvasói vélemények

A könyv alaposan feltárja az önző útválasztást és az ebből eredő optimumvesztést, hidat képezve a matematika, az informatika és a gazdaságelmélet között. Jól felépített, világos definíciókkal, tételekkel és példákkal, amelyek a valós analízisben és optimalizálásban jártas olvasók számára is hozzáférhetővé teszik. A szerző olyan jelentős fogalmakat mutat be, mint az anarchia ára, a Braess-paradoxon és a Nash-egyensúly, miközben gyakorlati eszközöket nyújt a hálózattervezéshez.

Átfogó bevezetés az önző útválasztás matematikai és számítási alapjaiba.

Világos szerkezet, definíciókkal, tételekkel és példákkal, amelyek segítik a megértést.

(4 olvasói vélemény alapján)

Eredeti címe:

Selfish Routing and the Price of Anarchy

Könyv tartalma:

A hálózatokban az önző, koordinálatlan viselkedés okozta teljesítményveszteség elemzése.

Legtöbben közülünk inkább a legrövidebb elérhető útvonalon ingáznak, anélkül, hogy figyelembe vennék a másoknak okozott forgalmi torlódást. Sok hálózat, köztük a számítógépes hálózatok is, szenvednek ennek az "önző útválasztásnak" valamilyen fajtájától. Tim Roughgarden az Selfish Routing and the Price of Anarchy (Önző útválasztás és az anarchia ára) című könyvében a hálózatokban az önző, koordinálatlan viselkedés okozta társadalmi jólétveszteséget tanulmányozza. Számszerűsíti az anarchia árát - az önző útválasztásból eredő társadalmi jólét legrosszabb lehetséges veszteségét -, és számos módszert is tárgyal az anarchia árának központi irányítással történő javítására.

Roughgarden az önző útválasztás viszonylag nem technikai jellegű bevezetésével kezdi, és két fontos példát ismertet, amelyek a következő problémákat motiválják. Az első, a Pigou-példa azt mutatja be, hogy az önző viselkedésnek nem feltétlenül kell társadalmilag optimális eredményt hoznia. A második, az ellenérdekű Braess-paradoxon azt mutatja, hogy a hálózati fejlesztések ronthatják a hálózat teljesítményét. Ezután technikákat dolgoz ki az anarchia árának számszerűsítésére (a Pigou-példa központi szerepet játszik). Ezután elemzi a Braess-paradoxont és annak algoritmikus felderítésének számítási bonyolultságát, majd leírja a Stackelberg-útvonaltervezést, amely szerény mértékű központi irányítással javítja az anarchia árát. Végül számos nyitott problémát határoz meg, amelyek további kutatásokat inspirálhatnak. Roughgarden munkája nemcsak az elméleti informatika és az optimalizálás kutatói és végzős hallgatói számára lesz érdekes, hanem más informatikusok, valamint közgazdászok, villamosmérnökök és matematikusok számára is.