Research Article
Capacity Allocation Games for Network-Coded Multicast Streaming
@INPROCEEDINGS{10.1007/978-3-642-30373-9_45, author={Elliot Anshelevich and Bugra Caskurlu and Koushik Kar and Hang Zhang}, title={Capacity Allocation Games for Network-Coded Multicast Streaming}, proceedings={Game Theory for Networks. 2nd International ICST Conference, GAMENETS 2011, Shanghai, China, April 16-18, 2011, Revised Selected Papers}, proceedings_a={GAMENETS}, year={2012}, month={10}, keywords={capacity allocation games the price of stability Nash equilibrium multicast networks}, doi={10.1007/978-3-642-30373-9_45} }- Elliot Anshelevich
Bugra Caskurlu
Koushik Kar
Hang Zhang
Year: 2012
Capacity Allocation Games for Network-Coded Multicast Streaming
GAMENETS
Springer
DOI: 10.1007/978-3-642-30373-9_45
Abstract
In this paper we formulate and study a capacity allocation game between a set of receivers (players) that are interested in receiving multicast data (video/multimedia) being streamed from a server through a multihop network. We consider multicast streaming, where the multicast stream from the source (origin-server) to any particular receiver (end-user) can be split over multiple paths. The receivers are selfish and non-cooperative, but must collaboratively purchase capacities of links in the network, as necessary for delivery of the multicast stream from the source to the individual receivers, assuming that the multicast stream is . For this multicast capacity allocation (network formation) game, we show that the Nash equilibrium is guaranteed to exist in general. For a 2-tier network model where the receivers must obtain the multicast data from the source through a set of relay nodes, we show that the price-of-stability is at most 2, and provide a polynomial-time algorithm that computes a Nash equilibrium whose social cost is within a factor of 2 of the socially optimum solution. For more general network models, we give a polynomial time algorithm that computes a 2-approximate Nash equilibrium whose cost is at most 2 times the social optimum. Simulation studies show that our algorithms generate efficient Nash equilibrium allocation solutions for a vast majority of randomly generated network topologies.