Convex Prophet Inequalities
Pages 85 - 86
Abstract
We introduce a new class of prophet inequalities-convex prophet inequalities-where a gambler observes a sequence of convex cost functions ci (xi ) and is required to assign some fraction 0 ≤ xi ≤ 1 to each, such that the sum of assigned values is exactly 1. The goal of the gambler is to minimize the sum of the costs. We provide an optimal algorithm for this problem, a dynamic program, and show that it can be implemented in polynomial time when the cost functions are polynomial. We also precisely characterize the competitive ratio of the optimal algorithm in the case where the gambler has an outside option and there are polynomial costs, showing that it grows as !(np-1/ζ), where n is the number of stages, p is the degree of the polynomial costs and the coefficients of the cost functions are bounded by [`,u].
References
[1]
Jonatha Anselmi, Danilo Ardagna, John CS Lui, Adam Wierman, Yunjian Xu, and Zichao Yang. 2013. The Economics of the Cloud: Price Competition and Congestion. Proceedings of NetEcon (2013).
[2]
Alain Bensoussan, Metin Ãakany, and Suresh P. Sethi. 2007. A Multiperiod Newsvendor Problem with Partially Observed Demand. Mathematics of Operations Research 32, 2 (2007), 322--344.
[3]
Dimitri P Bertsekas. 1995. Dynamic programming and optimal control. Vol. 1. Athena Scientific Belmont, MA.
[4]
Subhonmesh Bose, Desmond Cai, Steven Low, and Adam Wierman. 2014. The role of a market maker in networked cournot competition. In Proceedings of IEEE CDC.
[5]
M. Carrion, A. B. Philpott, A. J. Conejo, and J. M. Arroyo. 2007. A Stochastic Programming Approach to Electric Energy Procurement for Large Consumers. IEEE Transactions on Power Systems 22, 2 (May 2007), 744--754.
[6]
Sivadon Chaisiri, Bu-Sung Lee, and Dusit Niyato. 2012. Optimization of resource provisioning cost in cloud computing. IEEE Transactions on Services Computing 5, 2 (2012), 164--177.
[7]
Lynwood A Johnson and Douglas C Montgomery. 1974. Operations research in production planning, scheduling, and inventory control. Vol. 6. Wiley New York.
[8]
Panqanamala Ramana Kumar and Pravin Varaiya. 2015. Stochastic systems: Estimation, identification, and adaptive control. SIAM.
[9]
S. H. Low. 2014. Convex Relaxation of Optimal Power Flow, Part I: Formulations and Equivalence. IEEE Transactions on Control of Network Systems 1, 1 (March 2014), 15--27.
[10]
Jayakrishnan Nair, Sachin Adlakha, and Adam Wierman. 2014. Energy procurement strategies in the presence of intermittent sources. In Proceedings of ACM Sigmetrics.
[11]
Ram Rajagopal, Eilyan Bitar, Pravin Varaiya, and Felix Wu. 2013. Risklimiting dispatch for integrating renewable power. International Journal of Electrical Power & Energy Systems 44, 1 (2013), 615 -- 628.
[12]
Suresh Sethi, Houmin Yan, J Houzhong Yan, and Hanqin Zhang. 2005. An analysis of staged purchases in deregulated time-sequential electricity markets. Journal of Industrial and Management Optimization 1, 4 (2005), 443--463.
[13]
Allen J Wood and Bruce F Wollenberg. 2012. Power generation, operation, and control. John Wiley & Sons.
Recommendations
Convex Prophet Inequalities
We introduce a new class of prophet inequalities-convex prophet inequalities-where a gambler observes a sequence of convex cost functions ci(xi) and is required to assign some fraction 0 ≤ xi ≤ 1 to each, such that the sum of assigned values is exactly ...
Stability Inequalities for Projections of Convex Bodies
The projection function $$P_K$$PK of an origin-symmetric convex body K in $${{\mathbb {R}}}^n$$Rn is defined by $$P_K(\xi )=|K\vert {\xi ^\bot }|,\ \xi \in S^{n-1},$$PK(ź)=|K|źź|,źźSn-1, where $$K\vert {\xi ^\bot }$$K|źź is the projection of K to the ...
Inequalities for Ultraspherical and Laguerre Polynomials
R. Askey and G. Gasper have proved that \[\sum_{k = 0}^n {\frac{{(\lambda )_k }}{{k!}}} \frac{{(\lambda )_{n - k} }}{{(n - k)!}}\frac{{\sin (k + 1)\theta }}{{(k + 1)\sin \theta }} > 0,\quad 0 < \theta < \pi ,\] for $0 \leqq \lambda \leqq 2$ and Askey ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2019 Authors.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 17 January 2019
Published in SIGMETRICS Volume 46, Issue 2
Check for updates
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 20Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)1
Reflects downloads up to 19 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in