Media streaming is among the most popular services provided over the Internet. The lack of a central authority that controls the users, motivates the analysis of Media on Demand (MoD) services using game theoretic concepts. In this work we define and study the corresponding resource-allocation game, where users correspond to self-interested players who choose a MoD server with the objective of minimizing their individual cost. A server provides both storage and broadcasting needs. Accordingly, the user's cost function encompasses both positive and negative congestion effects.
In general, a system in our model consists of a set of N identical servers and n users. Each user is associated with a type (class) and should be serviced by a single server. Every user generates one unit of load on the server it is assigned to. The load on the server constitutes one component of the user's cost. In addition, the service requires an access to an additional resource whose activation-cost is equally shared by all the users {\em of the same class} that are assigned to the same server. This model generalizes the model introduced by Feldman and Tamir (2012), where all users belong to the same class. In MoD systems, the bandwidth required for transmitting a certain media-file corresponds to one unit of load. The storage cost of the media-file on a server is shared by the users that require its transmission and are serviced by the server.
We provide results with respect to equilibrium existence, computation, convergence and quality. We show that a pure Nash Equilibrium (NE) always exist and best-response dynamics converge in polynomial time. The equilibrium inefficiency is analyzed with respect to the objective of minimizing the maximal cost. We prove that the Price of Anarchy is bounded by N and that this bound is tight. For the Price of Stability we show an upper bound of 2, and a lower bound of 2-1/N. The upper bound is proved by introducing an efficient algorithm for calculating a NE that achieves 2-approximation to the optimal max-cost. For two servers we show a tight bound of 3/2.
The results are part of an M.Sc Thesis under the supervision of Tami Tamir.