Vi anser att ett multicast spel som spelas av en uppsättning själviska icke-kooperativa spelare (dvs noder) på en rotad oriktad graf. Spelare anländer en efter en och varje ansluter till roten genom att girigt välja en väg minimera sin kostnad; kostnaden för att använda en kant delas lika mellan alla användare som använder kanten. Hur stor kan summan av spelarnas kostnader vara, jämfört med kostnaden för en "socialt optimal" lösning, definieras som ett minimum Steiner träd ansluta spelarna till roten? Vi visar att förhållandet är O(log 2 n) och  på (log n), när det finns n spelare. Man kan se detta multicast-spel som en variant av ONLINE STEINER TREE med en annan kostnadsdelningsmekanism. Dessutom överväger vi vad som händer om spelarna, i en andra fas, tillåts att ändra sina vägar för att minska sina kostnader. Således, i den andra fasen spelar spelarna bäst svar dynamik tills så småningom en Nash jämvikt uppnås. Vi visar att priset på anarki är O(log 3 n) och -(log n). Vi gör också framsteg mot att förstå det utmanande fallet där ankomster och vägändringar vid befintliga terminaler interleaveds. I synnerhet analyserar vi det intressanta specialfallet där terminalerna avfyrar i slumpmässig ordning och bevisar att kostnaden för den lösning som produceras (med godtycklig interleating av åtgärder) är som mest O(polylog(n) ε n) gånger den optimala.
Senare Charikar et al. REF förbättrar detta som är bundet till O(log 3 n)OP T och gör också framsteg i fallet när bästa svar och sekventiell ankomst görs mellanhand.
Online multicast with egalitarian cost sharing
{'venue': "SPAA '08", 'journal': None, 'mag_field_of_study': ['Computer Science']}