Abstract
Prophet inequalities bound the reward of an online algorithm—or gambler—relative to the optimum offline algorithm—the prophet—in settings that involve making selections from a sequence of elements whose order is chosen adversarially but whose weights are random. The goal is to maximize total weight.
We consider the problem of choosing quantities of each element subject to polymatroid constraints when the weights are arbitrary concave functions. We present an online algorithm for this problem that does at least half as well as the optimum offline algorithm. This is best possible, as even in the case where a single number has to be picked no online algorithm can do better.
An important application of our result is in algorithmic mechanism design, where it leads to novel, truthful mechanisms that, under a monotone hazard rate (MHR) assumption on the conditional distributions of marginal weights, achieve a constant-factor approximation to the optimal revenue for this multi-parameter setting. Problems to which this result applies arise, for example, in the context of Video-on-Demand, Sponsored Search, or Bandwidth Markets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alaei, S.: Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. In: Proc. of 52nd FOCS, pp. 512–521 (2011)
Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: Proc. of 18th SODA, pp. 434–443 (2007)
Babaioff, M., Lucier, B., Nisan, N.: Bertrand networks. In: Proc. of 14th EC, pp. 33–34 (2013)
Bikhchandani, S., de Vries, S., Schummer, J., Vohra, R.V.: An ascending vickrey auction for selling bases of a matroid. Operations Research 59(2), 400–413 (2011)
Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: Proc. of 41th STOC, pp. 311–320 (2010)
Dean, B.C., Goemans, M.X., Vondrák, J.: Approximating the stochastic knapsack problem: The benefit of adaptivity. In: Proc. of 45th FOCS, pp. 208–217 (2004)
Dhangwatnotai, P., Roughgarden, T., Yan, Q.: Revenue maximization with a single sample. Games and Economic Behavior (2014) (in press)
Dütting, P., Kleinberg, R.: Polymatroid prophet inequalities (2013). http://arxiv.org/abs/1307.5299
Feldman, M., Gravin, N., Lucier, B.: Combinatorial auctions via posted prices. In: Proc. of 26th SODA, pp. 123–135 (2015)
Goel, G., Mirrokni, V.S., Paes Leme, R.: Polyhedral clinching auctions and the adwords polytope. In: Proc. of 44th STOC, pp. 107–122 (2012)
Guha, S., Munagala, K.: Multi-armed bandits with metric switching costs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol. 5556, pp. 496–507. Springer, Heidelberg (2009)
Guha, S., Munagala, K., Shi, P.: Approximation algorithms for restless bandit problems. Journal of the ACM 58, 3:1–3:50 (2010)
Hajiaghayi, M., Kleinberg, R., Sandholm, T.W.: Automated mechanism design and prophet inequalities. In: Proc. of 22nd AAAI, pp. 58–65 (2007)
Kleinberg, R., Weinberg, S.M.: Matroid prophet inequalities. In: Proc. of 44th STOC, pp. 123–136 (2012)
Krengel, U., Sucheston, L.: Semiamarts and finite values. Bulletin of the American Mathematical Society 83, 745–747 (1977)
Krengel, U., Sucheston, L.: On semiamarts, amarts, and processes with finite value. Advances in Probability and Related Topics 4, 197–266 (1978)
Myerson, R.: Optimal auction design. Mathematics of Operations Research 6, 58–73 (1981)
Samuel-Cahn, E.: Comparison of threshold stop rules and maximum for independent nonnegative random variables. Annals of Probability 12, 1213–1216 (1984)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer (2002)
Tse, D.N.C., Hanly, S.V.: Multiaccess fading channels-part I: Polymatroid structure, optimal resource allocation and throughput capacities. Transactions on Information Theory 44, 2796–2815 (1998)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dütting, P., Kleinberg, R. (2015). Polymatroid Prophet Inequalities. In: Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015. Lecture Notes in Computer Science(), vol 9294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48350-3_37
Download citation
DOI: https://doi.org/10.1007/978-3-662-48350-3_37
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48349-7
Online ISBN: 978-3-662-48350-3
eBook Packages: Computer ScienceComputer Science (R0)