CENTER Carnegie Mellon UniversityCarnegie Mellon Computer Science DepartmentSchool of Computer Science
Multicast Networks: Profit Maximization & Strategyproofness
Related Activities
Outreach Roadshow

by David Kitchin


Consider the problem of broadcasting a movie over the Internet. The broadcaster would like to maximize the money received from customers for the movie service, while minimizing the money paid to service providers for using their bandwidth. As a graph theory problem with all values (costs and utilities) known, this is the Net Worth problem, which is known to be in NP.

However, we study this problem from a game theory perspective. In the multicast network game, costs and utilities are unknown. We must construct a mechanism to negotiate with selfish agents (edges and vertices) while trying to maximize our profit. We also impose on this mechanism the crucial condition of strategyproofness: we must guarantee that no agent has an incentive to lie.

We consider previous research, which addresses only limited versions of the problem (nodes as agents only, or MST on edges as agents only). We show that due to the hardness of the underlying graph problem, a mechanism for the unrestricted multicast game cannot maximize profit or even approximate maximum achievable profit. We introduce the concept of profit guaranteeing to evaluate such mechanisms, and demonstrate a mechanism for the unrestricted game that can provide a profit guarantee if the agents are competitive.


This material is based upon work supported by National Science Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the
National Science Foundation