Ian A. Kash
Peter Key
Abstract
The problem of pricing the cloud has attracted much recent attention due to the widespread use of cloud computing and cloud services. From a theoretical perspective, several mechanisms that provide strong efficiency or fairness guarantees and desirable incentive properties have been designed. However, these mechanisms often rely on a rigid model, with several parameters needing to be precisely known for the guarantees to hold. In this article, we consider a stochastic model and show that it is possible to obtain good welfare and revenue guarantees with simple mechanisms that do not make use of the information on some of these parameters. In particular, we prove that a mechanism that sets the same price per timestep for jobs of any length achieves at least 50% of the welfare and revenue obtained by a mechanism that can set different prices for jobs of different lengths, and the ratio can be improved if we have more specific knowledge of some parameters. Similarly, a mechanism that sets the same price for all servers even though the servers may receive different kinds of jobs can provide a reasonable welfare and revenue approximation compared to a mechanism that is allowed to set different prices for different servers.
- Vineet Abhishek, Ian A. Kash, and Peter Key. 2012. Fixed and market pricing for cloud services. In Proceedings of the 7th Workshop on the Economics of Networks, Systems, and Computation.Google Scholar
Cross Ref
- Amazon. 2017. Amazon EC2 Spot Instances Pricing. Retrieved May 1, 2019 from http://aws.amazon.com/ec2/spot/pricing.Google Scholar
- Yossi Azar, Inna Kalp-Shaltiel, Brendan Lucier, Ishai Menache, Joseph (Seffi) Naor, and Jonathan Yaniv. 2015. Truthful online scheduling with commitments. In Proceedings of the 16th ACM Conference on Economics and Computation. 715--732. Google ScholarDigital Library
- Azure. 2016. Microsoft Azure Pricing Calculator. Retrieved May 1, 2019 from http://azure.microsoft.com/en-us/pricing/calculator.Google Scholar
- Moshe Babaioff, Liad Blumrosen, Shaddin Dughmi, and Yaron Singer. 2011. Posting prices with unknown distributions. In Proceedings of the 1st Innovations in Computer Science Conference. 166--178.Google Scholar
- Liad Blumrosen and Thomas Holenstein. 2008. Posted prices vs. negotiations: An asymptotic analysis. In Proceedings of the 9th ACM Conference on Electronic Commerce. 49. Google ScholarDigital Library
- Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the 42nd ACM Symposium on Theory of Computing. 311--320. Google ScholarDigital Library
- Ilan Reuven Cohen, Alon Eden, Amos Fiat, and Lukasz Jez. 2015. Pricing online decisions: Beyond auctions. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. 73--91. Google ScholarDigital Library
- Vincent Cohen-Addad, Alon Eden, Michal Feldman, and Amos Fiat. 2016. The invisible hand of dynamic market pricing. In Proceedings of the 17th ACM Conference on Economics and Computation. 383--400. Google ScholarDigital Library
- Louis Columbus. 2016. Roundup of Cloud Computing Forecasts and Market Estimates, 2016. Retrieved May 1, 2019 from http://www.forbes.com/sites/louiscolumbus/2016/03/13/roundup-of-cloud-computing-forecasts-and-market-estimates-2016.Google Scholar
- Sina Dehghani, Ian A. Kash, and Peter Key. 2016. Online Stochastic Scheduling and Pricing the Cloud. Working Paper.Google Scholar
- Ludwig Dierks and Sven Seuken. 2016. Cloud Pricing: The Spot Market Strikes Back. In Proceedings of the Workshop on Economics of Cloud Computing.Google Scholar
- Yann Disser, John Fearnley, Martin Gairing, Oliver Göbel, Max Klimm, Daniel Schmand, Alexander Skopalik, et al. 2016. Hiring secretaries over time: The benefit of concurrent employment. arXiv:1604.08125.Google Scholar
- Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. 2017. Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science. 540--551.Google ScholarCross Ref
- Paul Dütting, Felix Fischer, and Max Klimm. 2018. Revenue gaps for static and dynamic posted pricing of homogeneous goods. arXiv:1607.07105.Google Scholar
- Tomer Ezra, Michal Feldman, Tim Roughgarden, and Warut Suksompong. 2018. Pricing multi-unit markets. In Proceedings of the 14th Conference on Web and Internet Economics. 140--153.Google ScholarDigital Library
- Michal Feldman, Nick Gravin, and Brendan Lucier. 2015. Combinatorial auctions via posted prices. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. 123--135. Google ScholarDigital Library
- Eric J. Friedman, Ali Ghodsi, and Christos-Alexandros Psomas. 2014. Strategyproof allocation of discrete jobs on multiple machines. In Proceedings of the 15th ACM Conference on Economics and Computation. 529--546.Google ScholarDigital Library
- Eric J. Friedman, Miklós Z. Rácz, and Scott Shenker. 2015. Dynamic budget-constrained pricing in the cloud. In Proceedings of the 28th Canadian Conference on Artificial Intelligence. 114--121.Google ScholarCross Ref
- Darrell Hoy, Nicole Immorlica, and Brendan Lucier. 2016. On-demand or spot? Selling the cloud to risk-averse customers. In Proceedings of the 12th International Conference on Web and Internet Economics. 73--86. Google ScholarDigital Library
- Navendu Jain, Ishai Menache, Joseph (Seffi) Naor, and Jonathan Yaniv. 2011. A truthful mechanism for value-based scheduling in cloud computing. In Proceedings of the 4th International Symposium on Algorithmic Game Theory. 178--189. Google ScholarDigital Library
- Navendu Jain, Ishai Menache, Joseph (Seffi) Naor, and Jonathan Yaniv. 2012. Near-optimal scheduling mechanisms for deadline-sensitive jobs in large computing clusters. In Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures. 255--266.Google ScholarDigital Library
- Ian A. Kash and Peter Key. 2016. Pricing the cloud. IEEE Internet Computing 20, 1 (2016), 36--43.Google ScholarDigital Library
- Brendan Lucier, Ishai Menache, Joseph (Seffi) Naor, and Jonathan Yaniv. 2013. Efficient online scheduling for deadline-sensitive jobs. In Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures. 305--314.Google ScholarDigital Library
- Changjun Wang, Weidong Ma, Tao Qin, Xujin Chen, Xiaodong Hu, and Tie-Yan Liu. 2015. Selling reserved instances in cloud computing. In Proceedings of the 24th International Conference on Artificial Intelligence. 224--230. Google ScholarDigital Library
- Hong Zhang, Bo Li, Hongbo Jiang, Fangming Liu, Athanasios V. Vasilakos, and Jiangchuan Liu. 2013. A framework for truthful online auctions in cloud computing with heterogeneous user demands. In Proceedings of IEEE INFOCOM 2013. 1510--1518.Google ScholarCross Ref
Index Terms
- Simple Pricing Schemes for the Cloud
Recommendations
Simple pricing schemes for the cloud
NetEcon '17: Proceedings of the 12th workshop on the Economics of Networks, Systems and ComputationThe problem of pricing the cloud has attracted much recent attention due to the widespread use of cloud computing and cloud services. From a theoretical perspective, several mechanisms that provide strong efficiency or fairness guarantees and desirable ...
Pricing Multi-Unit Markets
We study the power and limitations of posted prices in multi-unit markets, where agents arrive sequentially in an arbitrary order. We prove upper and lower bounds on the largest fraction of the optimal social welfare that can be guaranteed with posted ...
Simple Economies are Almost Optimal
EC '21: Proceedings of the 22nd ACM Conference on Economics and ComputationConsider a seller that intends to auction some item. The seller can invest money and effort in advertising in different market segments in order to recruit n bidders to the auction. Alternatively, the seller can have a much cheaper and focused marketing ...
Comments