Abstract:

In the online multicast cost-sharing model introduced by Chekuri,
Chuzhoy, Lewin-Eytan, Naor, and Orda in Electronic Commerce 2006,
users in Phase 1 choose a cheapest path to the root, in which the
cost of an edge is shared equally among all users of the edge, and
later, in Phase 2, update their paths to the root so as to decrease
their costs, if possible. Chekuri et al. studied the "price of
anarchy," that is, the worst case ratio between the cost of the
constructed graph and the minimum cost of a Steiner tree connecting
all players to the root, proving it to be O((sqrt n)*log^2 n) and
Omega(log n/log log n). We show by contrast that the price of anarchy
is polylogarithmic and Omega(log n), thereby improving the upper
bound dramatically and the lower bound slightly.

This is joint work with Moses Charikar, Claire Mathieu, Seffi Naor,
and Mike Saks.