Minimization Fractional Prophet Inequalities for Sequential Procurement

References

• [1] Agrawal S, Wang Z, Ye Y (2014) A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4):876–890.Link, Google Scholar
• [2] Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930–972.Crossref, Google Scholar
• [3] Alaei S, Hajiaghayi M, Liaghat V (2012) Online prophet-inequality matching with applications to ad allocation. Proc. 13th ACM Conf. Electronic Commerce (EC ’12) (Association for Computing Machinery, New York), 18–35. https://dl.acm.org/doi/10.1145/2229012.2229018.Google Scholar
• [4] Alon N, Spencer J (2008) The Probabilistic Method, 3rd ed. (John Wiley & Sons, New York).Crossref, Google Scholar
• [5] Andrew L, Barman S, Ligett K, Lin M, Meyerson A, Roytman A, Wierman A (2013) A tale of two metrics: Simultaneous bounds on competitiveness and regret. Shalev-Shwartz S, Steinwart I, eds. Proc. 26th Annual Conf. Learn. Theory. Proceedings of Machine Learning Research, vol. 30 (PMLR, New York), 741–763.Google Scholar
• [6] Arya A, Mittendorf B, Sappington DEM (2008) The make-or-buy decision in the presence of a rival: Strategic outsourcing to a common supplier. Management Sci. 54(10):1747–1758.Link, Google Scholar
• [7] Azar Y, Buchbinder N, Chan TH, Chen S, Cohen IR, Gupta A, Huang Z, et al. (2016) Online algorithms for covering and packing problems with convex objectives. IEEE 57th Annual Sympos. Foundations Comput. Sci. FOCS (IEEE Computer Society, Piscataway, NJ), 148–157. https://ieeexplore.ieee.org/document/7782927.Google Scholar
• [8] Bertsekas DP (1995) Dynamic Programming and Optimal Control, vol. 1 (Athena Scientific, Belmont, MA).Google Scholar
• [9] Bose S, Cai DWH, Low SH, Wierman A (2014) The role of a market maker in networked Cournot competition. 53rd IEEE Conf. Decision Control CDC 2014 (IEEE, Piscataway, NJ), 4479–4484. https://ieeexplore.ieee.org/document/7040088.Google Scholar
• [10] Buchbinder N, Naor JS (2009) The design of competitive online algorithms via a primal–dual approach. Foundations Trends Theoret. Comput. Sci. 3(2–3):93–263.Crossref, Google Scholar
• [11] Chaisiri S, Lee BS, Niyato D (2012) Optimization of resource provisioning cost in cloud computing. IEEE Trans. Services Comput. 5(2):164–177. https://ieeexplore.ieee.org/document/5710870.Crossref, Google Scholar
• [12] Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Proc. 42nd ACM Sympos. Theory Comput. STOC ‘10 (Association for Computing Machinery, New York), 311–320. https://dl.acm.org/doi/10.1145/1806689.1806733.Google Scholar
• [13] Chen J, Guo Z (2014) Strategic sourcing in the presence of uncertain supply and retail competition. Production Oper. Management 23(10):1748–1760.Crossref, Google Scholar
• [14] Chen N, Agarwal A, Wierman A, Barman S, Andrew LLH (2015) Online convex optimization using predictions. Proc. 2015 ACM SIGMETRICS Internat. Conf. Measurement Model. Comput. Systems (Association for Computing Machinery, New York), 191–204. https://doi.org/10.1145/2745844.2745854.Google Scholar
• [15] Chen N, Comden J, Liu Z, Gandhi A, Wierman A (2016) Using predictions in online optimization: Looking forward with an eye on the past. Proc. 2016 ACM SIGMETRICS Internat. Conf. Measurement Model. Comput. Sci. (SIGMETRICS ’16) (Association for Computing Machinery, New York), 193–206. https://doi.org/10.1145/2896377.2901464.Google Scholar
• [16] Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2019) Recent developments in prophet inequalities. ACM SIGecom Exchanges 17(1):61–70.Crossref, Google Scholar
• [17] Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2021) Posted price mechanisms and optimal threshold strategies for random arrivals. Math. Oper. Res. 46(4):1452–1478.Link, Google Scholar
• [18] Cover TM, Thomas JA (2012) Elements of Information Theory (John Wiley & Sons, New York).Google Scholar
• [19] Delage E, Ye Y (2010) Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3):595–612.Link, Google Scholar
• [20] Disser Y, Fearnley J, Gairing M, Göbel O, Klimm M, Schmand D, Skopalik A, Tönnis A (2020) Hiring secretaries over time: The benefit of concurrent employment. Math. Oper. Res. 45(1):323–352.Link, Google Scholar
• [21] Dudley R (2002) Real Analysis and Probability, vol. 74 (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [22] Düetting P, Feldman M, Kesselheim T, Lucier B (2020) Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. SIAM J. Comput. 49(3):540–582. https://epubs.siam.org/doi/abs/10.1137/20M1323850.Google Scholar
• [23] Esfandiari H, Hajiaghayi M, Liaghat V, Monemizadeh M (2017) Prophet secretary. SIAM J. Discrete Math. 31(3):1685–1701. https://epubs.siam.org/doi/10.1137/15M1029394.Google Scholar
• [24] Grünwald PD, Dawid AP (2004) Game theory, maximum entropy, minimum discrepancy and robust Bayesian decision theory. Ann. Statist. 32(4):1367–1433.Crossref, Google Scholar
• [25] Hajiaghayi MT, Kleinberg RD, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Proc. 22nd AAAI Conf. Artificial Intelligence ‘07 (AAAI Press, Palo Alto, CA), 58–65. https://dl.acm.org/doi/10.5555/1619645.1619656.Google Scholar
• [26] Hazan E (2016) Introduction to online convex optimization. Foundations Trends Optim. 2(3–4):157–325.Crossref, Google Scholar
• [27] Hill TP (1983) Prophet inequalities and order selection in optimal stopping problems. Proc. Amer. Math. Soc. 88(1):131–137.Crossref, Google Scholar
• [28] Hill TP, Kertz RP (1981) Additive comparisons of stop rule and supremum expectations of uniformly bounded independent random variables. Proc. Amer. Math. Soc. 83(3):582–585.Crossref, Google Scholar
• [29] Hill TP, Kertz RP (1981) Ratio comparisons of supremum and stop rule expectations. Zeitschrift Wahrscheinlichkeitstheorie Verwandte Gebiete 56(2):283–285.Crossref, Google Scholar
• [30] Hill TP, Kertz RP (1992) A survey of prophet inequalities in optimal stopping theory. Contemporary Math. 125(1):191–207.Crossref, Google Scholar
• [31] Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Proc. 44th Sympos. Theory Comput. Conf. STOC ‘12 (Association for Computing Machinery, New York), 123–136. https://dl.acm.org/doi/10.1145/2213977.2213991.Google Scholar
• [32] Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83(4):745–747.Crossref, Google Scholar
• [33] Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Kuelbs J, ed. Probability on Banach Spaces, Advances in Probability Related Topics, vol. 4 (Dekker, New York), 197–266.Google Scholar
• [34] Low SH (2014) Convex relaxation of optimal power flow, part I: Formulations and equivalence. IEEE Trans. Control Network Systems 1(1):15–27.Crossref, Google Scholar
• [35] McShane EJ (1983) Unified Integration (Academic Press, New York).Google Scholar
• [36] Niu B, Li J, Zhang J, Cheng HK, Tan YR (2019) Strategic analysis of dual sourcing and dual channel with an unreliable alternative supplier. Production Oper. Management 28(3):570–587.Crossref, Google Scholar
• [37] Rajagopal R, Bitar E, Varaiya P, Wu F (2013) Risk-limiting dispatch for integrating renewable power. Internat. J. Electr. Power Energy Systems 23(10):1748–1760.Google Scholar
• [38] Rubinstein A, Singla S (2017) Combinatorial prophet inequalities. Klein PN, ed. Proc. Twenty-Eighth Annual ACM-SIAM Sympos. Discrete Algorithms SODA 2017 (SIAM), 1671–1687.Google Scholar
• [39] Salop SC, Scheffman DT (1987) Cost-raising strategies. J. Indust. Econom. 36(1):19–34.Crossref, Google Scholar
• [40] Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4):1213–1216.Crossref, Google Scholar
• [41] Sethi S, Yan H, Yan JH, Zhang H (2005) An analysis of staged purchases in deregulated time-sequential electricity markets. J. Indust. Management Optim. 1(4):443–463.Crossref, Google Scholar
• [42] Shalev-Shwartz S (2012) Online learning and online convex optimization. Foundations Trends Machine Learn. 4(2):107–194.Crossref, Google Scholar
• [43] Varaiya PP, Wu FF, Bialek JW (2011) Smart operation of smart grid: Risk-limiting dispatch. Proc. IEEE 99(1):40–57.Crossref, Google Scholar
• [44] Wood AJ, Wollenberg BF (2012) Power Generation, Operation, and Control (John Wiley & Sons, New York).Google Scholar