Sammanfattning En naturlig generalisering av den själviska routingmiljön uppstår när en del användare lyder en central samordnande myndighet, medan resten agerar själviskt. Ett sådant beteende kan modelleras genom att dela upp användarna i en α-fraktion som styrs enligt den centrala samordnarens routingstrategi (Stockelberg-strategin), och de återstående 1 − α som själviskt bestämmer sin strategi, med tanke på de samordnade användarnas routing. Man försöker kvantifiera det resulterande priset på anarki, dvs. förhållandet mellan kostnaden för den värsta trafikjämvikten och systemet optimalt, som en funktion av α. Det är välkänt att priset på anarki för α = 0 och linjär latens fungerar högst 4/3 (J. ACM 49, 236-259, 2002). Om α tenderar till 1, bör priset på anarki också tendera till 1 för någon rimlig algoritm som används av samordnaren. Vi analyserar två sådana algoritmer för Stackelberg routing, LLF och SCALE. För allmänna topologiska nätverk, multicommodity användare, och linjär latency funktioner, visar vi ett pris på anarki bundet till SCALE som minskar från 4/3 till 1 som α ökar från 0 till 1, och beror endast på α. Fram till detta arbete, en sådan kompromiss var känd endast för fallet med två noder i samband med parallella länkar (SIAM J. Comput. 33, 332-350, 2004), medan det för allmänna nät inte var klart om ett sådant resultat kunde uppnås, även i fallet med en enda vara. Vi visar en svagare gräns för LLF och även en del förlängningar till allmänna latensfunktioner. Att det finns en central samordnare är ett ganska starkt krav för ett nätverk. Vi visar att vi kan göra oss av med en sådan samordnare, så länge vi tillåts införa skatter (tullar) på kanterna för att styra de själviska användarna mot en förbättrad systemkostnad. Så länge det finns minst en bråkdel α av användarna som betalar sina skatter, visar vi förekomsten av skatter som leder till simuleringen av SCALE av skattebetalarna. Utvidgningen av de resultat som nämns ovan kvantifierar förbättringen av systemkostnaderna i takt med att antalet skatteindrivare minskar.
Karakostas och Kolliopoulos REF visade sig vara övre gränser för priset på anarki för SCALE och LLF.
Stackelberg Strategies for Selfish Routing in General Multicommodity Networks
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}