Journal of Computer Science and Technology ›› 2019, Vol. 34 ›› Issue (3): 645-656.doi: 10.1007/s11390-019-1933-9

Special Issue: Artificial Intelligence and Pattern Recognition; Theory and Algorithms

• Artificial Intelligence and Pattern Recognition • Previous Articles     Next Articles

Competitive Cloud Pricing for Long-Term Revenue Maximization

Jiang Rong1,2, Tao Qin3, Senior Member, ACM, IEEE, Bo An4, Member, CCF, ACM, IEEE   

  1. 1 Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China;
    2 University of Chinese Academy of Sciences, Beijing 100049, China;
    3 Microsoft Research Asia, Beijing 100080, China;
    4 School of Computer Science and Engineering, Nanyang Technological University, Singapore 639798, Singapore
  • Received:2018-05-09 Revised:2019-03-23 Online:2019-05-05 Published:2019-05-06
  • About author:Jiang Rong is a Ph.D. candidate of Institute of Computing Technology, Chinese Academy of Sciences, Beijing. His research interests include deep learning, reinforcement learning, artificial intelligence, game theory and multi-agent systems. He got his B.S. degree in information engineering from South China University of Technology, Guangzhou, in 2013.

We study the pricing policy optimization problem for cloud providers while considering three properties of the real-world market:1) providers have only incomplete information about the market; 2) it is in evolution due to the increasing number of users and decreasing marginal cost of providers; 3) it is fully competitive because of providers' and users' revenuedriven nature. As far as we know, there is no existing work investigating the optimal pricing policies under such realistic settings. We first propose a comprehensive model for the real-world cloud market and formulate it as a stochastic game. Then we use the Markov perfect equilibrium (MPE) to describe providers' optimal policies. Next we decompose the problem of computing the MPE into two subtasks:1) dividing the stochastic game into many normal-formal games and calculating their Nash equilibria, for which we develop an algorithm ensuring to converge, and 2) computing the MPE of the original game, which is efficiently solved by an algorithm combining the Nash equilibria based on a mild assumption. Experimental results show that our algorithms are efficient for computing MPE and the MPE strategy leads to much higher profits for providers compared with existing policies.

Key words: cloud computing; Markov perfect equilibrium; game theory; revenue maximization;

[1] Nir Y L, Devin F, Loubière P. Cloud resource management using constraints acquisition and planning. In Proc. the 25th AAAI Workshops:AI for Data Center Management and Cloud Computing, August 2011, Article No. 4.
[2] Wang C J, Ma W D, Qin T, Chen X J, Hu X D, Liu T Y. Selling reserved instances in cloud computing. In Proc. the 24th International Joint Conference on Artificial Intelligence, July 2015, pp.224-231.
[3] Xu B L, Qin T, Qiu G P, Liu T Y. Optimal pricing for the competitive and evolutionary cloud market. In Proc. the 24th International Joint Conference on Artificial Intelligence, July 2015, pp.139-145.
[4] Laatikainen G, Ojala A, Mazhelis O. Cloud services pricing models. In Proc. the 4th International Conference on Software Business, June 2013, pp.117-129.
[5] Sharma B, Thulasiram R K, Thulasiraman P, Garg S K, Buyya R. Pricing cloud compute commodities:A novel financial economic model. In Proc. the 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, May 2012, pp.451-457.
[6] Wang H Y, Jing Q F, Chen R S, He B S, Qian Z P, Zhou L D. Distributed systems meet economics:Pricing in the cloud. In Proc. the 2nd USENIX Workshop on Hot Topics in Cloud Computing, June 2010, Article No. 11.
[7] Thuijsman F. Optimality and Equilibria in Stochastic Games. CWI, 1992.
[8] Doraszelski U, Escobar J F. A theory of regular Markov perfect equilibria in dynamic stochastic games:Genericity, stability, and purification. Theoretical Economics, 2010, 5(3):369-402.
[9] Maskin E, Tirole J. Markov perfect equilibrium:I. observable actions. Journal of Economic Theory, 2001, 100(2):191-219.
[10] Feng Y, Li B C, Li B. Price competition in an oligopoly market with multiple IaaS cloud providers. IEEE Transactions on Computers, 2014, 63(1):59-73.
[11] Kantere V, Dash D, Francois G, Kyriakopoulou S, Ailamaki A. Optimal service pricing for a cloud cache. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(9):1345-1358.
[12] Xu H, Li B C. Maximizing revenue with dynamic cloud pricing:The infinite horizon case. In Proc. the 2012 IEEE International Conference on Communications, June 2012, pp.2929-2933.
[13] Vengerov D. A gradient-based reinforcement learning approach to dynamic pricing in partially-observable environments. Future Generation Computer Systems, 2008, 24(7):687-693.
[14] Xu H, Li B C. Dynamic cloud pricing for revenue maximization. IEEE Transactions on Cloud Computing, 2013, 1(2):158-171.
[15] Truong-Huu T, Tham C K. A game-theoretic model for dynamic pricing and competition among cloud providers. In Proc. the 6th IEEE/ACM International Conference on Utility and Cloud Computing, Dec. 2013, pp.235-238.
[16] Truong-Huu T, Tham C K. A novel model for competition and cooperation among cloud providers. IEEE Transactions on Cloud Computing, 2014, 2(3):251-265.
[17] Chien S, Sinclair A. Convergence to approximate Nash equilibria in congestion games. In Proc. the 18th Annual ACMSIAM Symposium on Discrete Algorithms, January 2007, pp.169-178.
[18] Goemans M, Mirrokni V, Vetta A. Sink equilibria and convergence. In Proc. the 46th Annual IEEE Symposium on Foundations of Computer Science, October 2005, pp.142- 151.
[19] Nisan N, Roughgarden T, Tardos E, Vazirani V V. Algorithmic Game Theory (1st edition). Cambridge University Press, 2007.
[20] Bowling M, Veloso M. Multiagent learning using a variable learning rate. Artificial Intelligence, 2002, 136(2):215-250.
[21] Busoniu L, Babuska R, de Schutter B. A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C, 2008, 38(2):156-172.
[22] Elmaghraby W, Keskinocak P. Dynamic pricing in the presence of inventory considerations:Research overview, current practices, and future directions. Management Science, 2003, 49(10):1287-1309.
[23] Jiang B J, Chen P Y, Mukhopadhyay T. Software licensing:Pay-per-use versus perpetual. 2007. http://dx.doi.org/10.2139/ssrn.1088570, Dec. 2018.
[24] Ma H, Liu C, King I, Lyu M R. Probabilistic factor models for web site recommendation. In Proc. the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval, July 2011, pp.265-274.
[25] Oliver F R. Methods of estimating the logistic growth function. Journal of the Royal Statistical Society. Series C (Applied Statistics), 1964, 13(2):57-66.
[26] Pearl R, Reed L J. On the rate of growth of the population of the United States since 1790 and its mathematical representation. Proceedings of the National Academy of Sciences of the United States of America, 1920, 6(6):275-288.
[27] Jung H, Klein C M. Optimal inventory policies under decreasing cost functions via geometric programming. European Journal of Operational Research, 2001, 132(3):628- 642.
[28] Allon G, Gurvich I. Pricing and dimensioning competing large-scale service providers. Manufacturing & Service Operations Management, 2010, 12(3):449-469.
[29] Lin K Y, Sibdari S Y. Dynamic price competition with discrete customer choices. European Journal of Operational Research, 2009, 197(3):969-980.
[30] Hu J L, Wellman M P. Multiagent reinforcement learning:Theoretical framework and an algorithm. In Proc. the 15th International Conference on Machine Learning, July 1998, pp.242-250.
[31] Schneider M L, Whitlatch E E. User-specific water demand elasticities. Journal of Water Resources Planning and Management, 1991, 117(1):52-73.
[32] Park S T, Chu W. Pairwise preference regression for coldstart recommendation. In Proc. the 3rd ACM Conference on Recommender Systems, October 2009, pp.21-28.
[1] Leo Mendiboure, Mohamed-Aymen Chalouf, Francine Krief. Edge Computing Based Applications in Vehicular Environments: Comparative Study and Main Issues [J]. Journal of Computer Science and Technology, 2019, 34(4): 869-886.
[2] Lei Cui, Youyang Qu, Mohammad Reza Nosouhi, Shui Yu, Jian-Wei Niu, Gang Xie. Improving Data Utility Through Game Theory in Personalized Differential Privacy [J]. Journal of Computer Science and Technology, 2019, 34(2): 272-286.
[3] Fateh Boucenna, Omar Nouali, Samir Kechid, M. Tahar Kechadi. Secure Inverted Index Based Search over Encrypted Cloud Data with User Access Rights Management [J]. Journal of Computer Science and Technology, 2019, 34(1): 133-154.
[4] Yang Li, Wen-Zhuo Song, Bo Yang. Stochastic Variational Inference-Based Parallel and Online Supervised Topic Model for Large-Scale Text Processing [J]. Journal of Computer Science and Technology, 2018, 33(5): 1007-1022.
[5] Bao-Kun Zheng, Lie-Huang Zhu, Meng Shen, Feng Gao, Chuan Zhang, Yan-Dong Li, Jing Yang. Scalable and Privacy-Preserving Data Sharing Based on Blockchain [J]. , 2018, 33(3): 557-567.
[6] An-Zhen Zhang, Jian-Zhong Li, Hong Gao, Yu-Biao Chen, Heng-Zhao Ma, Mohamed Jaward Bah. CrowdOLA: Online Aggregation on Duplicate Data Powered by Crowdsourcing [J]. , 2018, 33(2): 366-379.
[7] Qin Liu, Yuhong Guo, Jie Wu, Guojun Wang. Effective Query Grouping Strategy in Clouds [J]. Journal of Computer Science and Technology, 2017, 32(6): 1231-1249.
[8] Wei-Qing, Liu Jing Li. An Approach to Automatic Performance Prediction for Cloud-enhanced Mobile Applications with Sparse Data [J]. , 2017, 32(5): 936-956.
[9] Yuhun Jun, Jaemin Lee, Euiseong Seo. Evaluation of Remote-I/O Support for a DSM-Based Computation Offloading Scheme [J]. , 2017, 32(5): 957-973.
[10] Dong-Gang Cao, Bo An, Pei-Chang Shi, Huai-Min Wang. Providing Virtual Cloud for Special Purposes on Demand in JointCloud Computing Environment [J]. , 2017, 32(2): 211-218.
[11] Zuo-Ning Chen, Kang Chen, Jin-Lei Jiang, Lu-Fei Zhang, Song Wu, Zheng-Wei Qi, Chun-Ming Hu, Yong-Wei Wu, Yu-Zhong Sun, Hong Tang, Ao-Bing Sun, Zi-Lu Kang. Evolution of Cloud Operating System: From Technology to Ecosystem [J]. , 2017, 32(2): 224-241.
[12] Bin-Lei Cai, Rong-Qi Zhang, Xiao-Bo Zhou, Lai-Ping Zhao, Ke-Qiu Li. Experience Availability: Tail-Latency Oriented Availability in Software-Defined Cloud Computing [J]. , 2017, 32(2): 250-257.
[13] Xian-Mang He, Xiaoyang Sean Wang, Member, CCF, ACM, IEEE, Dong Li, Yan-Ni Hao. Semi-Homogenous Generalization:Improving Homogenous Generalization for Privacy Preservation in Cloud Computing [J]. , 2016, 31(6): 1124-1135.
[14] Farrukh Nadeem, Rizwan Qaiser. An Early Evaluation and Comparison of Three Private Cloud Computing Software Platforms [J]. , 2015, 30(3): 639-654.
[15] Claudia Canali, Riccardo Lancellotti. Improving Scalability of Cloud Monitoring Through PCA-Based Clustering of Virtual Machines [J]. , 2014, 29(1): 38-52.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved