Az internet korai szakaszában nem számoltak azzal, hogy az interneten megjelenő szereplők (szolgáltatók, felhasználók stb.) saját érdekei­ket szem előtt tartva cselekszenek, és ezzel jelentős mértékben rontják az erőforrások hatékony felhasználását. Ennek a nagyvonalúságnak egyik oka, hogy a katonai, illetve tudományos célokat szolgáló hálózatok szereplői követték a számukra előírt magatartást, azaz nem önérdekkövetően, hanem központilag előírt szabályokat betartva viselkedtek. Az internet egy későbbi szakaszában belépő újabb szereplők, a technika bűvöletében, jellemzően altruista magatartást követtek. Ezért a kezdetben kialakított internetes forgalmat szabályozó protokollok biztosították a hálózat hatékony működését. Ez az ideális helyzet már régóta megváltozott, mivel az interneten jelenlevő profitorientált szolgáltatók, valamint a különböző fájlokat fel- és letöltő felhasználók önérdeket követő szereplőkként viselkednek.

Az interneten megjelenő szereplők tulajdonképpen, e cikkgyűjtemény Forgó Ferenc által írt játékelméleti bevezetőjében ismertetett fogalommeghatározás szerint, egy sokszereplős játékban vesznek részt. Mivel az internet működése során számos zavarral − például túlzsúfoltsággal, az erőforrások pazarló felhasználásával, a költségek igazságtalan felosztásával stb. − szembesülünk, ezért a jelenlegi Border Gateway Protocol (BGP) által teremtett játékszabályok távolról sem optimálisak az internetező társadalom számára. E problémák kezelésére alkalmas eszköznek bizonyul az ugyancsak e számban Csekő Imre által ismertetett mechanizmustervezés, melynek éppen az a célja, hogy a közösség számára egy valamilyen értelemben jónak mondható eredményt érjen el, az egyének önérdekkövető magatartása alapján, a megfelelő játékszabályok kialakításával. Ez az internet esetében az alkalmas protokollok megválasztását jelenti. A mechanizmustervezés eredendően közgazdasági irodalma azonban nem foglalkozik a mechanizmusok számításigényével, ami meggátolja az eredmények közvetlen alkalmazását az internet modellezésére. E hiányosságot oldja fel az algoritmikus mechanizmustervezés, amely az algoritmusok elmélete és a mechanizmustervezés ötvözeteként született meg Noam Nisan és Amir Ro­nen (2001) úttörő munkájának köszönhetően.

Tanulmányom az algoritmikus mechanizmustervezés irodalmának néhány problémáját mutatja be. Egyrészt megvilágítja a játékelmélet hálózatokon történő alkalmazását, másrészt rámutat a mechanizmusok bonyolultságelméleti oldalról jelentkező nehézségeire. Az első problémánk egy csomagnak a feladótól a címzettig minimális költséggel történő eljuttatása egy olyan hálózaton keresztül, amelyben az egyes összeköttetéseket biztosító szolgáltatók valóságos költségeit csak az adott szolgáltató ismeri. Tehát a cél egy minimális költségű útvonal meghatározása önérdeket követő szolgáltatók mellett, amelynek példája mechanizmustervezési környezetben Nisan és Ronen (2001) cikkében jelent meg. A második problémánál az interdomain routing már nemcsak két szereplő közötti csomagküldéssel, hanem a teljes hálózat forgalmával foglalkozik. A világháló méretéből adódóan a forgalomirányítás kezeléséhez egy decentralizált modell alkalmazása célszerű. A harmadik részben egy, a hálózaton belüli zsúfoltság vizsgálatára is alkalmas modellel ismerkedünk, amely már nem az internetező társadalom számára optimális megoldást célozza meg, hanem az önérdekkövetésből eredő jóléti veszteséget igyekszik behatárolni. A negyedik rész a tudományterülettel kapcsolatos záró gondolatokat tartalmaz.

Minimális költségű útvonalak

A hálózatot a G=(V,E) irányított gráffal reprezentáljuk, ahol a V csúcshalmaz az internet szereplőit, az E élek halmaza pedig a csúcsok közötti kapcsolatokat reprezentálják. Ha az u szereplő közvetlenül továbbíthat egy csoma­got a v szereplőnek, akkor ezt (u,v)ÎE-vel jelöljük. Továbbá egy csomag továbbításának közvetlen költségei a C:E→R+ függvénnyel adottak. Ilyen hálózatot mutat az 1. ábra.

1. ábra

Feladatunk, hogy a hálózat egy sÎV csúcsából a tÎV csúcsába egy csomagot jut­tassunk el a lehető legkisebb költséggel. Az 1. ábrán jelzett hálózatban a minimális költségű útvonal a vastagon jelzett s,u,x,t útvonal, amely összesen 4 egységnyi költséggel jár. A két pont közötti legrövidebb útvonalat gyorsan megkapjuk például Edsger Dijkstra algoritmusával (lásd Rónyai et al., 1999). A problémát az okozza, hogy az élek költségei az összeköttetést biztosító szereplők privát információi, és ezért Dijkstra algoritmusát csak a közölt és nem feltétlenül valós költségekre futtathatjuk le. A mechanizmustervezés eszköztárát használva el szeretnénk érni, hogy a szereplők (az egyes élek, illetve összeköttetések birtokosai, a továbbiakban játékosok) a valós költségeiket önként közöljék egy játék segítségével, és ezáltal a csomag valóban a legkisebb költségű útvonalon jusson s-ből t-be. A játékosok tehát az élek birtokosai és a stratégiahalmazuk az általuk birtokolt él lehetséges költségeinek halmaza, jelen esetben a nem negatív valós számok halmaza. A közölt költségek alapján a mechanizmus meghatározza a minimális költségű útvonalat, a csomagot a legrövidebb útvonalon keresztül juttatja el s-ből t-be, a legrövidebb útvonalon szereplő játékos megkapja a bemondott költségeit, a többi játékos pedig nem részesül kifizetésben. Mivel a játékosok csak saját költségeiket ismerik, előfordulhat, hogy például az (s,u) él birtokosa − röviden (s,u) játékos − a valóságos 1 költsége helyett 5-öt közöl profitjának növelése érdekében. Ekkor azonban a mechanizmus az s,v,z,t útvonalat határozza meg, feltéve, hogy a többi szereplő az ábrában látható valós költségét közli. Ha az (s,u) játékos csak 2-re emelte volna állítólagos költségét, akkor továbbra is a minimális költségű útvonalon maradna, és profitot realizálhatna, a többi szereplő változatlan viselkedését feltételezve.

Vázoltunk tehát egy hálózat felett értelmezett játékot, és feledkezzünk meg egyelőre arról, hogy milyen egyensúlyi koncepció (például Nash-egyensúly, domináns egyensúly stb.) mellett kívánjuk meghatározni a játék kimenetelét. Tegyük fel, hogy a tervező azt kívánja elérni, hogy a csomag mindenképpen a valódi − de számára ismeretlen − költségek melletti minimális költségű útvonalon jusson el a feladótól a címzettig. Ha esetleg több minimális költségű útvonal is létezne, akkor ezek egyikén haladjon a csomag. A tervező céljai elérése érdekében transzferkifizetésekkel él, azaz a kinyilvánított költségek függvényében eltérő összegeket juttathat, illetve vonhat el a játékosoktól céljának elérése érdekében. Ezért a tervező „értékeket” rendel a hálózat egyes éleihez. Ha például az 1. ábrában kiesne az (s,u) él − ami úgy is reprezentálható, hogy az (s,u) él költségét végtelenül nagyra vesszük −, akkor ezzel az s,v,z,t útvonal válna minimális költségű útvonallá, méghozzá 7 összköltséggel, ami 3-mal több a teljes hálózat minimális összköltségénél. Tehát (s,u) a valódi 1 költségén felül legfeljebb további 3 egysé­get tudna elismertetni, és így összesen 4 egységet kinyilvánítani úgy, hogy még továbbra is egy minimális költségű útvonalon maradjon. Ezt a 4 egységet nevezzük az (s,u) játékos marginális hozzájárulásának, amellyel a tervező honorálja az (s,u) játékos jelenlétét.

Általánosan az E=(u,v)ÎE játékos MC_c(e) marginális hozzájárulását a c:E→R+ kinyilvánított költségek − azaz a játékosok stratégiaprofilja − alapján úgy határozzuk meg, hogy kiszámoljuk a c|c(e)=∞ minimális összköltségű útvonal költségét az e játékos hálózatból történő kiiktatása esetén, majd kiszámoljuk a c|c(e)=0 minimális összköltségű útvonal költségét abban az esetben, ha az e játékos élköltsége nulla volna. Így megkapjuk az e játékos által maximálisan elkérhető össze­get, feltéve, hogy minimális összköltségű útvonal mentén kíván maradni, ha ez számára egyáltalán lehetséges a c:E→R+ kinyilvánított költségek mellett. Végül a marginális hozzájárulása a két érték különbségeként adódik. A minimális összköltségű útvonalon nem szereplő játékosok marginális hozzájárulásait nullának tekintjük. A tervező céljának érdekében az egyes játékosoknak a kinyilvánított c:E→R+ költségek alapján számított marginális hozzájárulásukat juttatja. Vegyük észre, hogy a tervező által kitalált mechanizmus mellett a játékosok bevételei nem függnek a saját költségeiktől. Egy, a minimális összköltségű útvonalon elhelyezkedő játékos nyeresége a transzferkifizetésként kapott összeg és a csomag továbbításával járó költségének különbségeként adódik. A csomag továbbításában részt nem vevő játékosok profitjai mind nullák. Tegyük fel: a játékosok egymástól függetlenül szimultán módon közlik a tervezővel a kinyilvánított költségeiket.

Tétel. A fenti módon definiált hálózati játékban a szereplők a valódi költségeik kinyilvánításában érdekeltek.

A tétel bizonyítása nagyon egyszerű. Gondoljuk meg, hogy mi történne, ha egy e játékos valódi költségénél kisebb értéket adna meg. Ekkor a többi játékos költségeit és kinyilvánított költségeit nem ismervén megkockáztatja, hogy egy minimális összköltségű útvonalon elhelyezkedve a transzferkifizetései nem fedezik a valódi költségeit. Ez a helyzet akkor állhat elő, ha a kinyilvánított c:E→R+ költségek mellett e csak a túl alacsonyan megállapított c(e) költségének köszönhetően vehet részt a csomag továbbításában, és a (többiek által kinyilvánított költségektől függő) marginális hozzájárulása kisebb a valódi költségénél, azaz MC(e)<c(e). Ha pedig egy e játékos valódi költségénél nagyobb értéket ad meg, akkor elképzelhető, hogy a megtévesztése miatt lekerül egy neki előnyös minimális összköltségű útvonalról. Tehát bármely játékosnak a valódi költségét érdemes megadnia.

Az eddigiek alapján könnyen ellenőrizhető, hogy minden játékos domináns stratégiája az igazmondás, azaz a valódi költségek kinyilvánítása, amely a többi játékos költségkinyilvánításaitól függetlenül optimális, és ennek következtében a mechanizmus domináns stratégiákban implementálja a bemutatott minimális összköltségű útvonaltervezés problémát.

A probléma domináns stratégiákban való implementálhatósága az internet tekintetében nagyon kedvező, mivel a hálózat nagy és egyben változó mérete miatt nem várható el, hogy a szereplők ismerjék egymás költségeit. Viszont a mechanizmus kellemetlen tulajdonsága a transzferek igénye. Nézzük meg, hogy az 1. ábrán látható hálózat esetében mennyibe kerül a tervezőnek a kitűzött cél elérése. Az (s,u) játékosnak, mint már megállapítottuk, 4 egységet kell juttatni, míg az (u,x) és (x,t) játékosoknak hasonló megfontolásból rendre 5 és 4 egységet kell juttatni. Tehát a mechanizmus fenntartása 13 egységet igényel, amelyet a mechanizmus tervezőjének vagy a csomag küldőjének kell viselnie.

Megjegyzendő, hogy az ismertetett mechanizmus az úgynevezett Vickrey–Clarke–Groves-mechanizmusok, röviden VCG-mechanizmusok (lásd például Mas-Colell et al., 1995, 879.) családjába tartozik, amely pénzben kifejezhető hasznossági függvényű játékosokat, továbbá a mechanizmus és a játékosok között pénzügyi transzfereket igényel. Pontosabban a VCG-mechanizmusok úgynevezett kvázi­lineáris hasznossági függvények alkalmazását teszik szükségessé, melyek u(a,m)=v(a)+m alakúak, ahol v(a) a társadalmilag megvalósuló a alternatíva pénzbeni értéke és m a já­tékos pénzösszege. Jelölje A az alternatívák és {1,2,…,n} a játékosok halmazát. Ek­kor a VCG mechanizmus egy (f,p₁,p₂,…,p_n) struktúra, ahol f(v₁,v₂,…v_n) egy, a v₁(a)+v₂(a)+…+v_n(a) kifejezést maximalizáló alternatíva − azaz az f társadalmi választási függvény egy olyan a alternatívát választ, amely maximalizálja a játékosok által az alternatíva pénzben kifejezett értékeinek összegét −, p_i pedig a mechanizmus által az i játékosnak jutatott transzfer (lehet negatív is), amely független az i játékos hasznossági függvényétől. A VCG-mechanizmusok segítségével a tervező domináns stratégiákban igazsághűen implementálhatja céljait. Érdemes az olvasó figyelmét felhívni arra, hogy a Gibbard–Satterthwaite-tétel (lásd e számban Csekő Imre szavazáselméleti és mechanizmustervezési ismertetőjét) szerint legalább három alternatíva és tetszőleges pre­ferenciasorrendek esetén az igazsághű domináns implementálhatóság csak a diktatúrát jellemzi. Ilyen értelemben a hasznossági függvények kvázilinearitása egyfajta menekvést jelent a Gibbard–Satterthwaite-féle lehetetlenségi tétel alól. Ráadásul az internet példáját tekintve egy elfogadható feltevésről van szó, mivel a szereplők a bevételeiket és költségeiket pénzben fejezik ki. Ezért az algoritmikus mechanizmustervezés területén előszeretettel használnak VCG-mechanizmusokat. Az algoritmikus szempontokat egyelőre figyelmen kívül hagyva a minimális összköltségű útvonal-problémánál és általában a VCG-mechanizmusoknál is gondot okoznak a transzferrendszeren keresztüli többletkifizetések a játékosok részére (emlékeztetőül a példánkban ez 13-4=9 egységet jelentett). Az internet-gráfra vonatkozóan megnyugtató, hogy mérete miatt léteznek közel azonos összköltségű útvonalak, és ezért a többletkifizetések mértéke a minimális összköltségű útvonal-problémánál nem jelentős (Karger − Nikolova, 2006).

A minimális összköltségű útvonal problémája algoritmikus szempontból jól kezelhe­tő, mivel a játékosok saját típusaikat és optimális stratégiáikat könnyen meghatározhatják, valamint stratégiájukat a tervezőközpont felé gyorsan (az élek számában lineáris időben) továbbíthatják. Végül a beérkezett információk alapján a központ, például Dijkstra algoritmusával, gyorsan meghatározhatja az eredményt.

Interdomain routing

Az előző részben közölt minimális költségű útvonal meghatározása feltételezi egy központi tervező jelenlétét, aki képes a hozzá beérkező információ alapján a transzferek kiszámítására. Mivel az internet önszerveződő hálózat, ilyen erős szerepkörrel felruházott központi csomóponttal nem számolhatunk. Ráadásul egy esetleges központi tervező beiktatása bonyolultsági szempontból lehetetlen az internetgráf méretéből adódóan. Ezért a mechanizmustervezőnek céljait egy decentralizált elosztott rendszeren keresztül kell megvalósítania.

Az internet egy primitív modelljének bemutatása előtt szükségünk lesz néhány fogalomra. Az internet

autonóm rendszereket − például egyetemi hálózatokat, államigazgatási szervek hálózatait, vállalati hálózatokat − köt össze, amelyek belső adatforgalmát vezérlő protokolljait az autonóm rendszerek saját maguk alakíthatják ki, míg az autonóm rendszerek közötti kommunikáció szabványa az ún. Border Gateway Protocol (BGP). Az autonóm rendszeren belüli forgalomirányítást intradomain routingnak, az ilyen rendszerek közötti forgalomirányítást interdomain routingnak nevezik. A továbbiakban kizárólag az interdomain routinggal foglalkozunk.

Mielőtt továbbhaladunk, vázlatosan ismertetjük a BGP-t. Ehhez az internetet egy G=(V, E) irányítatlan gráffal reprezentáljuk, amelynek a csúcsai az autonóm rendszerek és az élei az autonóm rendszerek közötti össze­köttetések. Tegyük fel, hogy egy tÎV csúcsába kívánunk egy csomagot eljuttatni, és jelölje P_v a v csúcsból a t-be vezető körmentes útvonalak halmazát. A protokollnak az összes lehetséges utak halmazából kell egy lehetséges p_vÎP_v utat választania. A rendszer robusztus­sága, mérete és változó szerkezete miatt elvárjuk, hogy egy protokoll segítségével az útvonalak meghatározását decentralizált módon az autonóm rendszerek maguk végezzék. A számítások egyszerűsítése érdekében pedig a protokoll szerint a v csúcs a t-be vezető útvonalon található, valamilyen szempont alapján választott szomszédjának továbbítja a csomagot, amely ettől kezdve átveszi a csomag továbbításának további feladatait, és maga választ következő szomszédot. A protokollnak természetesen az idő, a kommunikáció és a tár szempontjából erőforrás-hatékonynak kell lennie. A BGP − amely kielégíti az interdomain routing protokollokkal szemben támasztott felsorolt elvárásokat − a szomszédok egymás közötti információcseréje révén határozza meg, és változás esetén frissíti a t-be vezető útvonalakat. Kicsit pontosabban: a v csúcs egy szomszédtól kapott információ alapján frissíti az útvonal táblázatát, amely akár több t-be vezető útvonalat is tartalmazhat. Ezek után, ha v a frissítéskor jobb útvonalat talált, akkor az erre vonatkozó információt továbbítja a szomszédjainak. Az információcsere során teljes útvonalinformációt továbbítanak egymásnak a csúcsok a körmentesség biztosítása érdekében. A v csúcs egy csomag továbbításakor valamilyen meghatározott szempont alapján választ egy legjobb útvonalat a saját útvonaltáblázata alapján. Itt megjegyzendő, hogy a minimális költségű útvonal egy lehetséges választási kritérium, azonban a BGP több választási kritériumot is megenged (például bizonytalannak tekintett országok elkerülése stb.). Természetes követelmény, hogy a protokoll biztosítsa az útvonalak konvergenciáját, azaz újabb csúcs belépése és kiesése esetén viszonylag hamar záruljon le a szomszédok kommunikációján keresztül megvalósuló frissítési folyamat. A BGP önmagában azonban még nem garantálja az útvonalak konvergenciáját, de lehetővé teszi a lehetséges választási kritériumok megszorításával.

Lixin Gao és Jennifer Rexford (2001) az autonóm rendszerek között megkülönböztet fogyasztói-szolgáltatói és egyenrangú (peer-to-peer) kapcsolatokat. A fogyasztó a forgalomért cserébe pénzzel fizet a szolgáltatónak, míg az egyenrangú felek közötti forgalom ingyenes. Gao és Rexford korlátozásai a következők:

1. A GCP fogyasztói-szolgáltatói irányított gráf legyen irányított körmentes, ahol a GCP a G internetgráfból úgy adódik, hogy kizárólag a fogyasztók és szolgáltatók közötti éleket vesszük át, méghozzá fogyasztóktól szolgáltatókba mutató irányított élekként. A feltevés közgazdasági szempontból elfogadható, hiszen egy irányított kör esetén egy szolgáltató közvetetten önmaga fogyasztója volna.

2. A választási kritérium részesítse előnyben a fogyasztókat az egyenrangú felekkel, az egyenrangú feleket pedig a szolgáltatókkal szemben. Ez utóbbi feltételt az a gazdasági racionalitás indokolja, hogy a fogyasztók fizetnek a szolgáltatóknak az adatok továbbításáért.

3. Az autonóm rendszerek nem végeznek tranzitszolgáltatásokat egyenrangú feleknek és szolgáltatóknak, mivel az ilyen típusú csomagközvetítés nem jár bevétellel.

A Gao–Rexford-kritériumok biztosítják a BGP-protokoll konvergenciáját.

A BGP vázlatos ismertetése után térjünk vissza a minimális összköltségű adatforgalom biztosításának kérdésére. Az 1. ponttal ellentétben a c:V→R+ költségfüggvény a csúcsokhoz rendel adattovábbítási költségeket, és már nemcsak két csúcs közötti hatékony adatátvitelben vagyunk érdekeltek, hanem az internetgráf egészét tekintve az összes csúcspár közötti összforgalom hatékony lebonyolítását tűzzük ki célul. A probléma megoldását csak vázlatosan ismertetjük, a részletek iránt érdeklődő olvasók figyelmébe Joan Feigenbaum és munkatársai (2005, 2006), valamint − Jeffrey Shneidman és David C. Parkes (2004) munkáit ajánljuk.

A BGP alapján az autonóm rendszerek (a továbbiakban játékosok) maguk állítják elő a minimális költségű útvonalakat, a szomszédokkal történő iteratív információcsere révén, amelyek eredményeit táblázatokban tárolják. Előbb-utóbb az összes játékos ismerni fogja az összes játékos kinyilvánított költségét, és meghatározhatja csúcspáronként a minimális költségű útvonalakat. A forgalomtovábbítással kapcsolatos követeléseiket és tartozásaikat pedig időközönként egy banknak jelentik. Megjegyzendő, hogy az interneten egy ilyenfajta bank bevezetése problematikusnak tűnhet, hiszen mégiscsak egyfajta központi szervezet megjelenését tételezi fel. Shneidman és Parkes (2004) eredményei alapján, bonyolultságelméleti szempontból, ez nem jelent olyan nehézséget, mint egy centralizált modell megvalósítása, amelyben a központ határozza meg a kinyilvánított költségek alapján a minimális költségű útvonalakat, és folyamatosan ellenőrzi a tényleges adatforgalmat.

Az interdomain routingban részt vevő játékosok három szinten manipulálhatnak:

1. hamis költségeket adhatnak meg, azaz a vÎV játékos a c(v) költségétől eltérő költséget közölhet szomszédjaival,

2. befolyásolhatják az internet társadalmi összköltségfüggvényének meghatározását, mivel pl. a szomszédoktól kapott információkat megmásítva is továbbíthatják, és

3. mint tranzitcsúcs, megmásíthatják a kapott információt és annak mennyiségét.

Shneidman és Parkes (2004) egy VCG-alapú mechanizmust alkalmaz az 1. manipulációs lehetőség meggátolására, míg a 2. és 3. manipulációs lehetőségnek, többek között kriptográfiai eszközökkel is, elejét lehet venni.

Feigenbaum és munkatársai (2006) a BGP egy finomításával elérik, hogy egy úgynevezett ex-post Nash-egyensúlyban − amely a domináns egyensúlynál valamivel erősebb, de a Nash-egyensúlynál jóval gyengébb egyen­súlyi koncepció − még autonóm rendszerek koalícióinak összehangolt manipulációival szemben is csalásbiztosan elérhető a társadalmi összköltségek minimalizálása, ráadásul monetáris transzferek nélkül. Ehhez a Gao–Rexford-kritériumon kívül lényegében még azt feltételezik, hogy bármely uÎV csúcs és annak bármely vÎV szomszédja esetében u-ból v-n átmenő útvonalaknál egyezzen meg az u és v útvonal választása.

Az anarchia ára

Az interdomain routing modelljénél nem vet­tük figyelembe, hogy két autonóm rendszer közötti összeköttetések mentén túlzsúfoltság léphet fel, ha az adott összeköttetés sok küldemény minimális összköltségű útvonalán helyezkedik el. Az előző két pont modelljei a lebonyolított forgalomtól független él­költ­ségekkel dolgoznak. A most ismertetésre kerülő modellben, amelyet Tim Rough­gar­den és Tardos Éva (2002) dolgozott ki, a G=(V, E) gráf eÎE élének c_e(x) költsége az x lebonyolított forgalomtól függ. Nyilván e feltevéssel a mechanizmustervezési feladat jóval nehezebbé válik. Roughgarden és Tardos (2002) munkájukban nem is egy társadalmilag jó mechanizmust keresnek, hanem a hálózat önző szereplőinek viselkedése révén kialakuló Nash-egyensúlyi megoldás és a társadalmilag optimális megoldás közötti jóléti veszteséget határolják be. Ez utóbbira vonatkozó mérőszám az anarchia ára (az elnevezést Christos Papadimitriou (2001) vezette be), amely az optimális megoldás és a játék legrosszabb egyensúlyi értékeinek hányadosa.

Adottak a gráfban egymástól különböző (s_i,t_i)ⁿ_i=1ÎV²ⁿ feladó (forrás) és címzett (nyelő) párok, ahol az s_i feladó a t_i címzettnek r_i adatmennyiséget kíván eljuttatni a hálózaton keresztül. Jelölje P_i az s_i feladótól a t_i címzetthez vezető útvonalak halmazát és P ezen útvonalak összességét, azaz P=P1ÈP2È…ÈPn. Feltesszük, hogy a feladók a címzetthez vezető útvonalakat maguk határozzák meg, megengedve, hogy a küldeményüket több részre bontva akár különböző útvonalakon keresztül is eljuttathassák a címzettig. Tehát az útvonaltervezést a küldő végzi, azaz úgynevezett source-routingról van szó. Megmutatható, hogy amennyiben a hálózat összes autonóm rendszere minimális költségű útvonalakat jelöl ki, akkor a tranzitcsúcsok maguk is a forrás által meghatározott útvonalak mentén továbbítják a csomagot. Ilyen értelemben feltehető, hogy a továbbiakban csak a feladókat tekintjük döntéshozóknak, azaz játékosoknak. A hálózaton folyó adatáramlást folyamnak hívjuk. Az f(e) érték megadja az e él mentén átáramló adatmennyiséget, amely az összes s_i feladótól a ti címzetthez az e élen áthaladó forgalmat figyelembe veszi. A költségek a feladóknál jelentkeznek, és az si feladó költsége a küldéshez használt összes útvonal mentén (emlékeztetőül: egy küldemény elosztható több útvonalra is) felmerülő költségeinek összege, ahol egy útvonal költsége az útvonalon található élek összköltsége szorozva az útvonal mentén küldött adatmennyiséggel. Tehát az s_i játékos stratégiahalmaza az r_i adatmennyiség P_i -beli útvonalakra való elosztása, és a hasznossága az útvonalak mentén felmerülő költségek ellentettje. Egy folyam egyensúlyinak tekinthető, ha egyik játékosnak sem érdemes egyoldalúan forgalmat átcsoportosítania egyik útvonaláról egy másikra. Ezt az egyensúlyt az irodalomban Wardrop-egyensúlynak is hívják, mivel a bemutatott folyamirányítási modell közlekedési hálózatokra is alkalmazható, amelyeket John Glen Wardrop (1952) vizsgált.

Az egyensúly létezése viszonylag általános feltételek mellett biztosított, és ismert, hogy ugyanazon feltételek mellett az összes egyensúlyi megoldás ugyanakkora összköltséggel jár. Az optimális, azaz a minimális összköltségű megoldás egy nemlineáris programozási feladat segítségével határozható meg. Roughgarden és Tardos (2002) megmutatták, hogy affin, azaz c_e(x)=ax+b alakú költségfüggvények esetén az anarchia ára 4/3. Költségekről lévén szó, ez azt jelenti, hogy az önérdekek követése a rendszerben akár 33%-os hatékonyságveszteséget is okozhat (de nem többet) a tökéletesen koordinált megoldással szemben. Tim Roughgarden (2005) munkája további költségfüggvényekre vonatkozó eredményeket is tartalmaz. Polinomok esetében az anarchia ára növekvő a polinom fokában, méghozzá n/ln n nagyságrendben, ahol n a polinom foka. Tehát az anarchia ára tetszőlegesen naggyá válhat.

Roughgarden (2005) azzal a helyzettel is foglalkozik, amikor a hálózaton központilag tervezett és önérdekkövető forgalom egyidejűleg van jelen. Ekkor elképzelhető, hogy a központilag tervezett forgalom segítségével csökkenthető az anarchia ára. Az alkalmazott módszer a Stackelberg-routing, mely esetén párhuzamos összeköttetések meglétekor a forgalom β hányadának központi irányíthatósága mellett az anarchia ára 1/β val korlátozható felülről a költségfüggvénytől függetlenül. E pozitív eredmény használhatóságát korlátozza, hogy a központi tervező által alkalmazandó stratégia meghatározása még lineáris költségfüggvények esetében is egy NP-nehéz feladat, azaz jelenlegi számítástudományi ismereteink alapján, kis méretű problémáktól eltekintve, az optimális Stackelberg-routing nem határozható meg.

Záró gondolatok

Az algoritmusok elméletének a játékelmélettel történő összekapcsolása viszonylag új. A jelen tanulmányban bemutatott irodalom Nisan és Ronen (2001) úttörő munkájából nőtte ki magát. A terület azóta számtalan új eredménnyel gazdagodott, és a jelenleg folyó kutatások spektruma nehezen áttekinthető. A területet feldolgozó első könyv a közelmúltban jelent meg (Nisan et al., 2007), amelynek egyes fejezeteit az eredményeket elért vezető kutatók írták, elsősorban a területen dolgozó szakemberek számára. Az első rövidebb bevezető jellegű könyv, amely akár egyetemi hallgatói szinten is használható, német nyelven jelent meg (Steimle, 2008). A terület előtt olyan kihívások állnak, mint például a fájlcserélő rendszerek és a mobilhálózatok specialitásainak játékelméleti modellezése.
 

Kulcsszavak: algoritmikus mechanizmustervezés, minimális költségű útvonalak, elosztott mechanizmusok, internet modellezése
 

IRODALOM

Feigenbaum, Joan − Papadimitriou, C. − Sami, R. − Shenker, S. (2005): A BGP-Based Mechanism for Lowest-cost Routing. Distributed Computing. 18, 61–72.

Feigenbaum, Joan − Ramachandran, V. − Schapira, M. (2006): Incentive-Compatible Interdomain Routing. In: Proceedings of the 7th Conference on Electronic Commerce. ACM Press, New York

Gao, Lixin − Rexford, Jennifer (2001): Stable Internet Routing without Global Coordination. IEEE/ACM Transactions on Networking. 9, 681–692.

Karger, David − Nikolova, Evdokia (2006): VCG Over­payment in Random Graphs. In: Conference on Decision and Control (CDC '06), San Diego, CA.

Mas-Colell, Andreu − Whinston, M.D. − Green, J. R. (1995): Microeconomic Theory, Oxford Univ. Press

Nisan, Noam− Ronen, Amir (2001): Algorithmic Mechanism Design. Games and Economic Behavior. 35, 197–211.

Nisan, Noam − Roughgarden, T. − Tardos E. − Vazirani, V. (eds.) (2007): Algorithmic Game Theory, Cambridge University Press, Cambridge

Papadimitriou, Christos (2001): Algorithms, Games, and the Internet. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC). 749–753.

Rónyai Lajos − Ivanyos G. − Szabó R. (1999): Algoritmusok, TypoTex, Budapest

Roughgarden, Tim (2005): Selfish Routing and the Price of Anarchy, MIT Press

Roughgarden, Tim − Tardos Éva (2002): How Bad Is Selfish Routing? Journal of the ACM. 49, 236–259.

Shneidman, Jeffrey − Parkes, David C. (2004): Specification Faithfulness in Networks with Rational Nodes. In: Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC’04). 88–97.

Steimle, Jürgen (2008): Algorithmic Mechanism Design, Springer-Verlag, Berlin−Heidelberg

Wardrop, John Glen (1952): Some Theoretical Aspects of Road Traffic Research. Proceedings of the Institute of Civil Engineers. II. 1, 325–378.