{"corpus_id":202151589,"paper_sha":"fddf69b78237a054a085a0f9049f8ef3f4dc9b70","doi":"10.1016/J.TCS.2019.08.019","arxiv_id":null,"pmid":null,"pmcid":null,"mag_id":2969663833,"dblp_id":"journals/tcs/LiuXTLC20","acl_id":null,"title":"Game theory-based optimization of distributed idle computing resources in cloud environments","year":2020,"publication_date":"2020-02-01","venue":"Theoretical Computer Science","journal":{"name":"Theor. Comput. Sci.","pages":"468-488","volume":"806"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":null,"s2_fields_of_study":["Computer Science","Economics"],"reference_count":39,"citation_count":14,"influential_citation_count":0,"is_open_access":false,"arxiv_categories":null,"arxiv_license":null,"arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":null,"s2_open_access_landing_url":null,"s2_open_access_license":null,"s2_open_access_status":null,"pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"Abstract With the rapid cloud technological advancement and economic growth, more and more organizations have purchased cloud resources for daily business operations besides building their own IT infrastructures. Thus, it is very important to understand the economy of cloud computing. In this paper, we mainly focus on examining the private idle computing resources owned by various organizations who are willing to form a network of ad hoc cloud provider and sell the services to cloud users. In such a case, the organizations cannot only meet their own demands, but also sell their idle computing resources in the form of ad hoc cloud. Naturally, the organizations, as provider, aim at maximizing their own profit through adjusting business costs and sale prices. Due to the uncertainty of the amount of idle computing resources, dynamic pricing is challenging. We approach the problem from the perspective of game theory and formulate it as a non-cooperative game among multiple organizations, i.e., the game player. For each player, a utility function is used to represent its profits. The players choose request strategies and sales service strategies to maximize the utility function. This paper has proved that there exists Nash equilibrium for this game problem. We proposed an iterative proximal algorithm (IPA) for calculating the Nash equilibrium. After analyzing the convergence of the IPA, we found that the algorithm converges to the Nash equilibrium solution when reasonable conditions are satisfied and conforms to the theoretical proof. Experimental results show that our proposed algorithm can quickly converge to a stable state, and by calculating the appropriate service (resource) request strategies and selling service strategies for all organizations, organizations' profit are increased compared to without IPA algorithm.","claims":[{"public_id":"cl_d6e800e1cb4e44fc223c883a0d53d0e8","status":"active","text":"A non-cooperative game formulation captures the interactions among multiple organizations that sell private idle computing resources in an ad hoc cloud market.","confidence":0.95,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_d6e800e1cb4e44fc223c883a0d53d0e8"},{"public_id":"cl_da6fcf9baa1403b3b70c035752d0eed8","status":"active","text":"An iterative proximal algorithm can compute the Nash equilibrium and converges to it under reasonable conditions.","confidence":0.96,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_da6fcf9baa1403b3b70c035752d0eed8"},{"public_id":"cl_28afe249616661806552bc8bc5e50617","status":"active","text":"Experimental results show that the algorithm reaches a stable state quickly and increases organizations' profits compared with not using the iterative proximal algorithm.","confidence":0.93,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_28afe249616661806552bc8bc5e50617"},{"public_id":"cl_f247069a8c2239769f5335765420a05f","status":"active","text":"Nash equilibrium exists for the formulated resource-sharing game.","confidence":0.97,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_f247069a8c2239769f5335765420a05f"}],"concepts":[{"public_id":"co_000ca2ccd215ed43bd56b2b15f8d05c8","status":"active","name":"cloud environments","description":"Cloud computing settings in which computing services and resources are provisioned and used.","types":["environment"],"aliases":["cloud computing environments"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_000ca2ccd215ed43bd56b2b15f8d05c8"},{"public_id":"co_27d59de01755e8ad1b4f7f5deb1fea45","status":"active","name":"request strategies","description":"Strategies that determine how organizations request computing resources in the game.","types":["strategy"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_27d59de01755e8ad1b4f7f5deb1fea45"},{"public_id":"co_2d4c5f6c37a5ef6e50d0baeb0cc6cea5","status":"active","name":"iterative proximal algorithm","description":"An iterative algorithm proposed to calculate the Nash equilibrium of the game.","types":["algorithm"],"aliases":["IPA"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_2d4c5f6c37a5ef6e50d0baeb0cc6cea5"},{"public_id":"co_5ba9d87183764759918485912d4b9480","status":"active","name":"game theory-based optimization","description":"An optimization approach that uses game-theoretic models to analyze strategic decision making among participants.","types":["method"],"aliases":["game-theory-based optimization"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_5ba9d87183764759918485912d4b9480"},{"public_id":"co_6574b48715cbaef4104d66e79b909d18","status":"active","name":"organizations' profit","description":"The profit earned by organizations from operating as resource providers and selling idle computing capacity.","types":["outcome"],"aliases":["profit"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_6574b48715cbaef4104d66e79b909d18"},{"public_id":"co_8873dc92b911e3f2b24572045715ca9a","status":"active","name":"stable state","description":"An equilibrium-like operating point reached by the algorithm during iteration.","types":["outcome"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_8873dc92b911e3f2b24572045715ca9a"},{"public_id":"co_a1b0e322f163af2f992dedcd5c8aea01","status":"active","name":"distributed idle computing resources","description":"Unused computing capacity owned by multiple organizations and made available for sharing or sale.","types":["resource"],"aliases":["idle computing resources"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_a1b0e322f163af2f992dedcd5c8aea01"},{"public_id":"co_a4df255067c14a0114b0f7c9a7bfe6b3","status":"active","name":"Nash equilibrium","description":"A stable game state in which no player can improve its utility by changing strategy unilaterally.","types":["solution concept"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_a4df255067c14a0114b0f7c9a7bfe6b3"},{"public_id":"co_ad8728a56de5c33aa3018a6fc473e42b","status":"active","name":"non-cooperative game","description":"A game-theoretic model in which players make decisions independently to maximize their own utility.","types":["model"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_ad8728a56de5c33aa3018a6fc473e42b"},{"public_id":"co_b56515976ff5ff9b9ab5faf7cf80d584","status":"active","name":"ad hoc cloud","description":"A temporary cloud provider network formed from organizations that offer their idle computing resources to users.","types":["cloud architecture"],"aliases":["ad hoc cloud provider"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_b56515976ff5ff9b9ab5faf7cf80d584"},{"public_id":"co_c7177e26272ad9e3a49e9d7f418ce4b0","status":"active","name":"sales service strategies","description":"Strategies that determine how organizations offer and sell computing services or resources.","types":["strategy"],"aliases":["selling service strategies"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_c7177e26272ad9e3a49e9d7f418ce4b0"},{"public_id":"co_e86972d192d98842399c337bfd08d117","status":"active","name":"private idle computing resources","description":"Unused computing resources privately owned by organizations and available for potential resale or sharing.","types":["resource"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_e86972d192d98842399c337bfd08d117"},{"public_id":"co_e8ec7656c6d6e3002e238481b54d2033","status":"active","name":"convergence","description":"The property that an iterative method approaches a limiting solution over repeated updates.","types":["algorithm property"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_e8ec7656c6d6e3002e238481b54d2033"},{"public_id":"co_f4208c91342e789909d5b955a1df3365","status":"active","name":"utility function","description":"A function representing each player's profit or payoff in the game formulation.","types":["mathematical function"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_f4208c91342e789909d5b955a1df3365"}],"external_ids":{"DOI":"10.1016/J.TCS.2019.08.019","ArXiv":null,"PubMed":null,"PubMedCentral":null,"MAG":2969663833,"DBLP":"journals/tcs/LiuXTLC20","ACL":null},"open_access":{"is_open_access":false,"pdf_url":null,"landing_url":"https://sah.borca.ai/papers/202151589","source":null,"pdf_url_source":null,"license":null,"reason":"pdf_url_not_indexed"},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":false,"full_text_source":null,"count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":635335,"paper_uid":"dd1ce762-12af-4a62-bb61-5e3d61fcc447","canonical_identity":{"paper_id":635335,"paper_uid":"dd1ce762-12af-4a62-bb61-5e3d61fcc447","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/202151589"}