Posted Price Profit Maximization for Multicast by Approximating Fixed Points

TitlePosted Price Profit Maximization for Multicast by Approximating Fixed Points
Publication TypeJournal Article
Year of Publication2006
AuthorsMehta, A., Shenker S., & Vazirani V. V.
Published inJournal of Algorithms
Volume58
Issue2
Page(s)150-164
Other Numbers2231
Abstract

We describe an iterative fixed point approach for the following stochastic optimization problem: given a multicast tree and probability distributions of user utilities, find an optimal posted price mechanism-i.e., compute prices to offer the users in order to maximize the expected profit of the service provider. We show that any optimum pricing is a fixed point of an efficiently computable function. We can then apply the non-linear Jacobi and Gauss-Seidel methods of coordinate descent. We provide proof of convergence to the optimum prices for special cases of utility distributions and tree edge costs.

Bibliographic Notes

Journal of Algorithms, Vol. 58, Issue 2, pp. 150-164

Abbreviated Authors

A. Mehta, S. Shenker, and V. Vazirani

ICSI Research Group

Networking and Security

ICSI Publication Type

Article in journal or magazine