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.