We consider the design of multicast networks when both edges and nodes are selfish agents. Our objective is a budget-balanced, strategy-proof mechanism which selects the set of clients to receive service and constructs a network to provide the service. It extracts payments from the clients and pays edges to participate in the network, and aims to maximize profit from the transaction. We introduce the notion of @i(profit guaranteeing) mechanisms, and show the existence of one such mechanism. The mechanism provides guarantees of the form that in a sufficiently profitable market, it obtains some fraction of the obtainable profit, and if the market is sufficiently unprofitable, then the mechanism demonstrates that no profitable solution exists. The mechanism runs in polynomial time. To our knowledge, this is the first study of mechanisms for designing multicast networks in which edge values are unknown.

11 pages

*Graduate School of Industrial Administration, Carnegie Mellon University

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]