|
Abstract : |
We continue the study of multicast cost sharing from the viewpoints of both computational complexity and economic mechanism design. We provide fundamental lower bounds on the network complexity of group-strategyproof, budget-balanced mechanisms. We also extend a classical impossibility result in game theory to show that no strategyproof mechanism can be both approximately ecient and approximately budget-balanced. Our results show that one important and natural case of multicast cost sharing is an example (to our knowledge, the rst in the literature) of a representative hard problem in distributed, algorithmic mechanism design; in this sense, they represent progress toward the development of a \complexity theory of Internet computation.", |
