Posted Price Profit Maximization for Multicast by Approximating Fixed Points
Title | Posted Price Profit Maximization for Multicast by Approximating Fixed Points |
Publication Type | Journal Article |
Year of Publication | 2006 |
Authors | Mehta, A., Shenker S. J., & Vazirani V. V. |
Published in | Journal of Algorithms |
Volume | 58 |
Issue | 2 |
Page(s) | 150-164 |
Other Numbers | 2231 |
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 |