Game Theory for Networks. 2nd International ICST Conference, GAMENETS 2011, Shanghai, China, April 16-18, 2011, Revised Selected Papers

Research Article

Capacity Allocation Games for Network-Coded Multicast Streaming

Download60 downloads
  • @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
Elliot Anshelevich1,*, Bugra Caskurlu2,*, Koushik Kar1,*, Hang Zhang1,*
  • 1: Rensselaer Polytechnic Institute
  • 2: West Virginia University
*Contact email: eanshel@cs.rpi.edu, caskurlu@gmail.com, kark@rpi.edu, zhangh10@rpi.edu

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.