by David Kitchin

abstract

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.