Explorations of Game Theory Applied in Cloud Computing

Abstract

Cloud computing has recently emerged as a paradigm for a cloud provider to host and deliver computing services to enterprises and consumers [1]. Usually, the provided services mainly refer to Software as a Service (SaaS), Platform as a Service (PaaS), and Infrastructure as a Service (IaaS), which are all made available to the general public in a pay-as-you-go manner [2, 3]. In most systems, the service provider provides the architecture for users to make reservations/price bidding in advance [4, 5].

1 Background and Motivation

Cloud computing has recently emerged as a paradigm for a cloud provider to host and deliver computing services to enterprises and consumers [1]. Usually, the provided services mainly refer to Software as a Service (SaaS), Platform as a Service (PaaS), and Infrastructure as a Service (IaaS), which are all made available to the general public in a pay-as-you-go manner [2, 3]. In most systems, the service provider provides the architecture for users to make reservations/price bidding in advance [4, 5]. When making reservations for a cloud service or making price bidding for resource usage, multiple users and the cloud provider need to reach an agreement on the costs of the provided service and make planning to use the service/resource in the reserved time slots, which could lead to a competition for the usage of limited resources [6]. Therefore, it is important for a user to configure his/her strategies without complete information of other users, such that his/her utility is maximized.

For a cloud provider, the income (i.e., the revenue) is the service charge to users [7]. When providing services to multiple cloud users, a suitable pricing model is a significant factor that should be taken into account. The reason lies in that a proper pricing model is not just for the profit of a cloud provider, but for the appeals to more cloud users in the market to use cloud service. Specifically, if the per request charge is too high, a user may refuse to use the cloud service, and choose another cloud provider or just finish his/her tasks locally. On the contrary, if the charge is too low, the aggregated requests may be more than enough, which could lead to low service quality (long task response time) and thus dissatisfies its cloud users.

A rational user will choose a strategy to use the service/resources that maximizes his/her own net reward, i.e., the utility obtained by choosing the cloud service minus the payment [1]. On the other hand, the utility of a user is not only determined by the importance of his/her tasks (i.e., how much benefit the user can receive by finishing the tasks), but also closely related to the urgency of the task (i.e., how quickly it can be finished). The same task, such as running an online voice recognition algorithm, is able to generate more utility for a cloud user if it can be completed within a shorter period of time in the cloud [1]. However, considering the energy saving and economic reasons, it is irrational for a cloud provider to provide enough computing resources to satisfy all requests in a time slot. Therefore, multiple cloud users have to compete for the cloud service/resources. Since the payment and time efficiency of each user are affected by decisions of other users, it is natural to analyze the behavior of such systems as strategic games [4].

In this chapter, we try to enhance services in cloud computing by considering from multiple users’ perspective. Specifically, we try to improve cloud services by simultaneously optimizing multiple users’ utilities which involve both time and payment. We use game theory to analyze the situation. We formulate a service reservation model and a price bidding model and regard the relationship of multiple users as a non-cooperative game. We try to obtain a Nash equilibrium to simultaneously maximize multiple users’ utilities. To solve the problems, we prove the existence of Nash equilibrium and design two different approaches to obtain a Nash equilibrium for the two problems, respectively. Extensive experiments are also conducted, which verify our analyses and show the efficiencies of our methods.

2 Related Works

In many scenarios, a service provider provides the architecture for users to make reservations in advance [4,5,6] or bid for resource usage [8,9,10]. One of the most important aspects that should be taken into account by the provider is its resource allocation model referring users’ charging/bidding prices, which is closely related to its profit and the appeals to market users.

Many works have been done on the pricing scheme in the literature [7, 11,12,13,14,15]. In [7], Cao et al. proposed a time dependent pricing scheme, i.e., the charge of a user is dependent on the service time of his/her requirement. However, we may note that the service time is not only affected by the amount of his/her own requirement, but also influenced by other factors such as the processing capacity of servers and the requirements of others. Mohsenian-Rad et al. [11] proposed a dynamic pricing scheme, in which the per price (the cost of one request or one unit of load) of a certain time slot is set as an increasing and smooth function of the aggregated requests in that time slot. That is to say, when the aggregated requests are quite much in a time slot, the users have to pay relatively high costs to complete the same amount of requests, which is an effective way to convince the users to shift their peak-time task requests. In [9], Samimi et al. focused on resource allocation in cloud that considers the benefits for both the users and providers. To address the problem, they proposed a new resource allocation model called combinatorial double auction resource allocation (CDARA), which allocates the resources according to bidding prices. In [8], Zaman and Grosu argued that combinatorial auction-based resource allocation mechanisms are especially efficient over the fixed-price mechanisms. They formulated resource allocation problem in clouds as a combinatorial auction problem and proposed two solving mechanisms, which are extensions of two existing combinatorial auction mechanisms. In [10], the authors also presented a resource allocation model using combinatorial auction mechanisms. Similar studies and models can be found in [16,17,18,19]. Similar studies and models can be found in [12,13,14,15,16,17,18,19]. However, these models are only applied to control energy consumption and different from applications in cloud services, since there is no need to consider time efficiency in them. Furthermore, almost all of them consider from the perspective of a cloud provider, which is significantly different from our multiple users’ perspective.

Game theory is a field of applied mathematics that describes and analyzes scenarios with interactive decisions [20,21,22]. It is a formal study of conflicts and cooperation among multiple competitive users [23] and a powerful tool for the design and control of multiagent systems [24]. There has been growing interest in adopting cooperative and non-cooperative game theoretic approaches to modeling many problems [11, 25,26,27]. In [11], Mohsenian-Rad et al. used game theory to solve an energy consumption scheduling problem. In their work, they proved the existence of the unique Nash equilibrium solution and then proposed an algorithm to obtain it. They also analyzed the convergence of their proposed algorithm. Even though the formats for using game theory in our work, i.e., proving Nash equilibrium solution existence, proposing an algorithm, and analyzing the convergence of the proposed algorithm, are similar to [11], the formulated problem and the analysis process are entirely different. In [28], the authors used cooperative and non-cooperative game theory to analyze load balancing for distributed systems. Different from their proposed non-cooperative algorithm, we solve our problem in a distributed iterative way. In our previous work [29], we used non-cooperative game theory to address the scheduling for simple linear deteriorating jobs. For more works on game theory, the reader is referred to [15, 28, 30,31,32].

3 Strategy Configurations of Multiple Users Competition for Cloud Service Reservation

3.1 Model Formulation and Analyses

To begin with, we present our system model in the context of a service cloud provider, and establish some important results. In this paper, we are concerned with a market with a service cloud provider and n cloud users, who are competing for the cloud service reservation. We denote the set of users as $\mathcal {N}=\{1,\ldots , n\}$. The arrival of requests from cloud user i ($i \in \mathcal {N}$) is assumed to follow a Poisson process. The cloud provider is modeled by an M/M/m queue, serving a common pool of cloud users with m homogeneous servers. Similar to [33, 34], we assume that the request profile of each user is determined in advance for H future time slots. Each time slot can represent different timing horizons, e.g., one hour of a day.

3.1.1 Request Profile Model

We consider a user request model motivated by [12, 15], where the user i′s ($i \in \mathcal {N}$) request profile over the H future time slots is formulated as

$$\displaystyle \begin{aligned} \boldsymbol{\lambda}_i = \left( \lambda_i^1, \ldots ,\lambda_i^H \right)^T, {} \end{aligned} $$

(1)

where $\lambda _i^h$ ($i \in \mathcal {N}$) is the arrival rate of requests from user i in the hth time slot and it is subject to the constraint $\sum _{h=1}^H\lambda _i^h=\Lambda _i$, where Λ_i denotes user i’s total requests. The arrivals in different time slots of the requests are assumed to follow a Poisson process. The individual strategy set of user i can be expressed as

$$\displaystyle \begin{aligned} Q_i = \left\{ {{\boldsymbol{\lambda} _i}\Bigg|\sum_{h = 1}^H {\lambda _i^h} = {\Lambda _i} \ \mbox{and} \ \lambda _i^h \ge 0,\forall h \in \mathcal{H}} \right\}, {} \end{aligned} $$

(2)

where $\mathcal {H}=\{1,\ldots ,H\}$ is the set of all H future time slots.

3.1.2 Load Billing Model

To efficiently convince the users to shift their peak-time requests and fairly charge the users for their cloud services, we adopt the instantaneous load billing scheme, which is motivated by [12, 15], where the request price (the cost of one request) of a certain time slot is set as an increasing and smooth function of the total requests in that time slot, and the users are charged based on the instantaneous request price. In this paper, we focus on a practical and specific polynomial request price model. Specifically, the service price for one unit of workload of the hth time slot is given by

$$\displaystyle \begin{aligned} C\left( {\lambda _{\Sigma} ^h} \right) = a{\left( {\lambda _{\Sigma} ^h} \right)^2} + b, {} \end{aligned} $$

(3)

where a and b are constants with a, b > 0, and $\lambda _{\Sigma }^h$ is the aggregated requests from all users in time slot h, i.e., $\lambda _{\Sigma } ^h = \sum \limits _{i = 1}^n {\lambda _i^h}$.

3.1.3 Cloud Service Model

The cloud provider is modeled by an M/M/m queue, serving a common pool of multiple cloud users with m homogeneous servers. The processing capacity of each server is presented by its service rate μ ₀. We denote μ as the total processing capacity of all m servers and Λ as the aggregated requests from all cloud users, respectively. Then we have μ = mμ ₀, and $\Lambda = \sum \limits _{i = 1}^n {{\Lambda _i}}$.

Let p _i be the probability that there are i service requests (waiting or being processed) and ρ =  Λ∕μ be the service utilization in the M/M/m queuing system. With reference to [7, 35], we obtain

$$\displaystyle \begin{aligned} p_i = \begin{cases} \frac{1}{{i!}}{{\left( {m\rho } \right)}^i}{p_0}, & i < m; \\ \frac{{{m^m}{\rho ^i}}}{{m!}}{p_0}, & i \ge m; \\ \end{cases} {} \end{aligned} $$

(4)

where

$$\displaystyle \begin{aligned} p_0 = \left\{ {\sum_{k = 0}^{m - 1} {\frac{1}{{k!}}{{\left( {m\rho } \right)}^k}} + \frac{1}{{m!}}\frac{{{{(m\rho )}^m}}}{{1 - \rho }}} \right\}^{ - 1}. {} \end{aligned} $$

(5)

The average number of service requests (in waiting or in execution) is

$$\displaystyle \begin{aligned} \bar{N} = \sum_{i = 0}^\infty {k{p_i}} = \frac{{{p_m}}}{{1 - \rho }} = m\rho + \frac{\rho }{{1 - \rho }}{P_q}, {} \end{aligned} $$

(6)

where P _q represents the probability that the incoming requests need to wait in queue.

Applying Little’s result, we get the average response time as

$$\displaystyle \begin{aligned} \bar{T} = \frac{\bar{N}}{\Lambda } = \frac{1}{\Lambda }\left( {m\rho + \frac{\rho }{{1 - \rho }}{P_q}} \right). {} \end{aligned} $$

(7)

In this paper, we assume that all the servers will likely keep busy, because if not so, some servers could be shutdown to reduce mechanical wear and energy cost. For analytical tractability, P _q is assumed to be 1. Therefore, we have

$$\displaystyle \begin{aligned} {\bar{T}} = \frac{\bar{N}}{\Lambda } = \frac{1}{\Lambda }\left( {m\rho + \frac{\rho }{{1 - \rho }}} \right) = \frac{m}{\mu } + \frac{1}{{\mu - \Lambda}}. {} \end{aligned} $$

(8)

Now, we focus on time slot h ($h \in \mathcal {H}$). We get that the average response time in that time slot as

$$\displaystyle \begin{aligned} \bar{T^h} = \frac{m}{\mu } + \frac{1}{{\mu - \lambda _{\Sigma} ^h}}, {} \end{aligned} $$

(9)

where $\lambda _{\Sigma } ^h = \sum \limits _{i = 1}^n {\lambda _i^h}$. In this paper, we assume that $\lambda _i^h < \mu \ (\forall h \in \mathcal {H})$, i.e., the aggregated requests in time slot h never exceeds the total capacity of all servers.

3.1.4 Architecture Model

In this subsection, we model the architecture of our proposed service mechanism, in which the cloud provider can evaluate proper charge parameters according to the aggregated requests and the cloud users can make proper decisions through the information exchange module. As shown in Fig. 1, each user i ($i \in \mathcal {N}$) is equipped with a utility function (U _i) and the request configuration (λ _i), i.e., the service reservation strategy over H future time slots. All requests enter a queue to be processed by the cloud computing. Let λ _Σ be aggregated request vector, then we have ${\boldsymbol {\lambda } _{\Sigma } } = \sum \limits _{i = 1}^n {{\boldsymbol {\lambda } _i}}$. The cloud provider consists of m homogeneous servers with total processing rate μ, i.e., μ = mμ ₀, where μ ₀ is the service rate of each server, and puts some information (e.g., price parameters a and b, current aggregated request vector λ _Σ) into the information exchange module. When multiple users try to make a cloud service reservation, they first get information from the exchange module, then compute proper strategies such that their own utilities are maximized and send the newly strategies to the cloud provider. The procedure is terminated until the set of remaining users, who prefer to make cloud service reservation, and their corresponding strategies are kept fixed.

Fig. 1

Architecture overall view

3.1.5 Problem Formulation

Now, let us consider user i′s ($i \in \mathcal {N}$) utility in time slot h. A rational cloud user will seek a strategy to maximize its expected net reward by finishing the tasks, i.e., the benefit obtained by choosing the cloud service minus its total payment. Since all cloud users are charged based on the instantaneous load billing and how much tasks they submit, we denote the cloud user i′s payment in time slot h by $P_i^h$, where $P_i^h = C\left ( {\lambda _{\Sigma } ^h} \right )\lambda _i^h$ with $C\left ( {\lambda _{\Sigma } ^h} \right )$ denoting the service price for one unit of workload in time slot h. On the other hand, since a user will be more satisfied with much faster service, we also take the average response time into account. Note that time utility will be deteriorated with the delay of time slots. Hence, in this paper, we assume that the deteriorating rate of time utility is δ (δ > 1). Denote $\bar T^h$ the average response time and T ^h the time utility of user i in time slot h, respectively. Then we have $T^h = \delta ^h\bar T^h$. More formally, the utility of user i ($i \in \mathcal {N}$) in time slot h is defined as

$$\displaystyle \begin{aligned} U_i^h\left( {\lambda _i^h,\boldsymbol{\lambda} _{ - i}^h} \right) & = r\lambda _i^h - P_i^h\left( {\lambda _i^h,\boldsymbol{\lambda} _{ - i}^h} \right) - {w_i}{T^h}\left( {\lambda _i^h,\boldsymbol{\lambda} _{ - i}^h} \right) \\ & = r\lambda _i^h - P_i^h\left( {\lambda _i^h,\boldsymbol{\lambda} _{ - i}^h} \right) - {w_i}{\delta ^h}\bar{T^h}\left( {\lambda _i^h,\boldsymbol{\lambda} _{ - i}^h} \right), \end{aligned} $$

(10)

where $\boldsymbol {\lambda } _{ - i}^h = \left ( {\lambda _1^h, \ldots ,\lambda _{i - 1}^h,\lambda _{i + 1}^h, \ldots ,\lambda _n^h} \right )$ denotes the vector of all users’ request profile in time slot h except that of user i, r (r > 0) is the benefit factor (the reward obtained by one task request), and w _i (w _i > 0) is the waiting cost factor, which reflects its urgency. If a user is more concerned with task completion, then the associated waiting factor w _i might be larger.

For simplicity, we use $P_i^h$ and $\bar T^h$ to denote $P_i^h\left ( {\lambda _i^h,\boldsymbol {\lambda } _{ - i}^h} \right )$ and $\bar T^h\left ( {\lambda _i^h,\boldsymbol {\lambda } _{ - i}^h} \right )$, respectively. Following the adopted request price model, the total utility obtained by user i ($i \in \mathcal {N}$) over all H future time slots can thus be given by

$$\displaystyle \begin{aligned} {U_i}(\boldsymbol{\lambda} _i,{{\boldsymbol{\lambda}} _{ - i}}) = \sum_{h = 1}^H {U_i^h(\lambda _i^h,\boldsymbol{\lambda} _{ - i}^h)} = \sum_{h = 1}^H {\left( {r\lambda _i^h - P_i^h - {w_i}{\delta ^h}{\bar{T}^h}} \right)}, \end{aligned} $$

(11)

where ${{\boldsymbol {\lambda }} _{ - i}} = \left ( {{\boldsymbol {\lambda } _1}, \ldots ,{\boldsymbol {\lambda } _{i - 1}},{\boldsymbol {\lambda } _{i + 1}}, \ldots ,{\boldsymbol {\lambda } _n}} \right )$ denotes the (n − 1) H × 1 vector of all users’ request profile except that of user i.

We consider the scenario where all users are selfish. Specifically, each user tries to maximize his/her total utility over the H future time slots, i.e., each user i ($i \in \mathcal {N}$) tries to find a solution to the following optimization problem (OPT_i):

$$\displaystyle \begin{aligned} \mbox{maximize} \ \ {U_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{ - i}}), \ {\boldsymbol{\lambda} _i} \in {Q_i}. {} \end{aligned} $$

(12)

3.2 Game Formulation and Analyses

In this section, we formulate the considered scenario into a non-cooperative game among the multiple cloud users. By employing variational inequality (VI) theory, we analyze the existence of a Nash equilibrium solution set for the formulated game. And then we propose an iterative proximal algorithm to compute a Nash equilibrium. We also analyze the convergence of the proposed algorithm.

3.2.1 Game Formulation

Game theory studies the problems in which players try to maximize their utilities or minimize their disutilities. As described in [28], a non-cooperative game consists of a set of players, a set of strategies, and preferences over the set of strategies. In this paper, each cloud user is regarded as a player, i.e., the set of players is the n cloud users. The strategy set of player i ($i \in \mathcal {N}$) is the request profile set of user i, i.e., Q _i. Then the joint strategy set of all players is given by Q = Q ₁ ×⋯ × Q _n.

As mentioned before, all users are considered to be selfish and each user i ($i \in \mathcal {N}$) tries to maximize his/her own utility or minimize his/her disutility while ignoring the others. In view of (12), we can observe that user i′s optimization problem is equivalent to

$$\displaystyle \begin{aligned} \mbox{minimize} \quad &{f_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{ - i}}) = \sum_{h = 1}^H {\left( {P_i^h + {w_i}{\delta ^h}{{\bar T}^h} - r\lambda _i^h} \right),} \\ s.t. \quad &(\boldsymbol{\lambda}_i, \boldsymbol{\lambda}_{-i}) \in Q. {} \end{aligned} $$

(13)

The above formulated game can be formally defined by the tuple $G = \left \langle {Q,\boldsymbol {f}} \right \rangle$, where $\boldsymbol {f} = \left ( {{f_1}, \ldots ,{f_n}} \right )$. The aim of user i ($i \in \mathcal {N}$), given the other players’ strategies λ _−i, is to choose an λ _i ∈ Q _i such that his/her disutility function f _i(λ _i, λ _−i) is minimized. That is to say, for each user i ($i \in \mathcal {N}$),

$$\displaystyle \begin{aligned} \boldsymbol{\lambda} _i^\ast \in \mathop {\arg \min }\limits_{{\boldsymbol{\lambda} _i} \in {Q_i}} {f_i}({\boldsymbol{\lambda} _i},\boldsymbol{\lambda} _{ - i}^\ast), \ {\boldsymbol{\lambda} ^\ast} \in Q. {} \end{aligned} $$

(14)

At the Nash equilibrium, each player cannot further decrease its disutility by choosing a different strategy while the strategies of other players are fixed. The equilibrium strategy profile can be found when each player’s strategy is the best response to the strategies of other players.

3.2.2 Billing Parameters Analysis

It is important to investigate the way the cloud provider decides load billing scheme. In our proposed model, the request charge changes according to the total load during different time slots. The cloud provider needs to decide the proper pricing parameters a and b. The reason lies in that if the per request charge (the cost of one task request) is too high, some users may refuse to use the cloud service, and choose to finish his/her tasks locally. On the contrary, if the charge is low, the aggregated requests may be more than enough, which could lead to low service quality (long task response time). In this paper, we assume that each user i ($i \in \mathcal {N}$) has a reservation value v _i. That is to say, cloud user i will prefer to use the cloud service if ${U_i}\left ( {{\boldsymbol {\lambda } _i},{\boldsymbol {\lambda } _{ - i}}} \right ) \ge {v_i}$ and refuse to use the service otherwise. If the cloud provider wants to appeal all n cloud users to use its service while charging relatively high, then it must guarantee that the obtained utility of each user i ($i \in \mathcal {N}$) is equal to his/her reservation value v _i, i.e., ${U_i}\left ( {{\boldsymbol {\lambda } _i},{\boldsymbol {\lambda } _{ - i}}} \right ) = {v_i}$ ($\forall i \in \mathcal {N}$), which implies that

$$\displaystyle \begin{aligned} \sum_{h = 1}^H {\left( {r\lambda _i^h - P_i^h - {w_i}{\delta ^h}{{\bar T}^h}} \right)} = {v_i}, \forall i \in \mathcal{N}. {} \end{aligned} $$

(15)

Considering all users together, (15) is equivalent to

$$\displaystyle \begin{aligned} r\Lambda - P_T - {w_{\Sigma} }\sum_{h = 1}^H {{\delta ^h}\bar T^h} = \sum_{i = 1}^n {{v_i}}, {} \end{aligned} $$

(16)

where $\Lambda = \sum \limits _{i = 1}^n {{\Lambda _i}}$, ${w_{\Sigma } } = \sum \limits _{i = 1}^n {{w_i}}$, and $P_T = \sum \limits _{i = 1}^n\sum \limits _{h = 1}^H {{P_i ^h}}$.

For the cloud provider, its objective is trying to decide proper pricing parameters a and b such that its net reward, i.e., the charge to all cloud users (P _T) minus its cost (e.g., energy cost and machine maintenance cost), is maximized. In this paper, we denote π as the net profit and γ _h the cost in time slot h. When total capacity μ is determined, γ _h is assumed to be constant. Then the cloud provider’s problem is to try to maximize the value π. That is

$$\displaystyle \begin{aligned} \mbox{maximize} \quad & \pi = P_T(\boldsymbol{\lambda}) - \sum_{h = 1}^H {{\gamma _h}}, \\ \mbox{s.t.} \quad & r\Lambda - P_T(\boldsymbol{\lambda}) - {w_{\Sigma} }\sum_{h = 1}^H {{\delta ^h}\bar T^h} = \sum_{i = 1}^n {{v_i}}, {} \end{aligned} $$

(17)

$$\displaystyle \begin{aligned} & \Lambda = \sum_{i = 1}^n\Lambda_i = \sum_{h = 1}^H {{\lambda_{\Sigma} ^h}}, \end{aligned} $$

(18)

$$\displaystyle \begin{aligned} & \mu > {\lambda_{\Sigma} ^h} \ge 0,\forall h \in \mathcal{H}. {} \end{aligned} $$

(19)

The above optimization problem is equivalent to

$$\displaystyle \begin{aligned} \mbox{maximize} \quad & \pi = r\Lambda - {w_{\Sigma} }\sum_{h = 1}^H {{\delta ^h}\bar T^h} - \sum_{i = 1}^n {{v_i}} - \sum_{h = 1}^H {{\gamma _h}}, \\ \mbox{s.t.} \quad & \Lambda = \sum_{i = 1}^n\Lambda_i = \sum_{h = 1}^H {{\lambda_{\Sigma} ^h}}, \\ & \mu > {\lambda_{\Sigma} ^h} \ge 0,\forall h \in \mathcal{H}. {} \end{aligned} $$

(20)

Theorem 3.1

For the cloud provider, the profit is maximized when the billing parameters (a and b) satisfy the constraint (17) and

$$\displaystyle \begin{aligned} {\lambda_{\Sigma} ^h} = \mu - \frac{\left( {H\mu - \Lambda } \right)\left( {1 - {\delta ^{1/2}}} \right){\delta ^{\left( {h - 1} \right)/2}}}{{\left( {1 - {\delta ^{H/2}}} \right)}}, {} \end{aligned} $$

(21)

where $h \in \mathcal {H}$.

Proof

We can maximize π in (20) by using the method of Lagrange multiplier, namely,

$$\displaystyle \begin{aligned} \frac{{\partial \pi }}{{\partial \lambda _{\Sigma} ^h}} = -{w_{\Sigma} }{\delta ^h}\frac{{\partial \bar T^h }}{{\partial \lambda _{\Sigma} ^h}} = -\varphi, \end{aligned}$$

where φ is the Lagrange multiplier. That is,

$$\displaystyle \begin{aligned} \frac{{{w_{\Sigma} }{\delta ^h}}}{{{{\left( {\mu - \lambda _{\Sigma} ^h} \right)}^2}}} = \varphi, \end{aligned}$$

for all 1 ≤ h ≤ H, and $\sum \limits _{h = 1}^H {\lambda _{\Sigma } ^h} = \Lambda$. After some algebraic calculation, we have

$$\displaystyle \begin{aligned} \varphi = \frac{{{w_{\Sigma} }\delta {{\left( {1 - {\delta ^{H/2}}} \right)}^2}}}{{{{\left( {H\mu - \Lambda } \right)}^2}{{\left( {1 - {\delta ^{1/2}}} \right)}^2}}}. \end{aligned}$$

Then we can obtain

$$\displaystyle \begin{aligned} {\lambda_{\Sigma} ^h} = \mu - \frac{\left( {H\mu - \Lambda } \right)\left( {1 - {\delta ^{1/2}}} \right){\delta ^{\left( {h - 1} \right)/2}}}{{\left( {1 - {\delta ^{H/2}}} \right)}}, \end{aligned}$$

and the result follows. □

Note that the obtained result (21) must satisfy the constraint (19), that is to say,

$$\displaystyle \begin{aligned} \begin{cases} \mu - \frac{\left( {H\mu - \Lambda } \right)\left( {1 - {\delta ^{1/2}}} \right){\delta ^{\left( {H - 1} \right)/2}}}{{\left( {1 - {\delta ^{H/2}}} \right)}} \ge 0, & h = H; \\ \mu - \frac{\left( {H\mu - \Lambda } \right)\left( {1 - {\delta ^{1/2}}} \right)}{{\left( {1 - {\delta ^{H/2}}} \right)}} < \mu, & h = 1; \\ H\mu-\Lambda > 0. \end{cases} \end{aligned} $$

(22)

We obtain

$$\displaystyle \begin{aligned} \begin{cases} \mu \le \frac{c\Lambda}{cH-1}, \\ H\mu > \Lambda, \end{cases} \end{aligned} $$

(23)

where

$$\displaystyle \begin{aligned} c = \frac{\left( 1-\delta^{1/2} \right)\delta^{(H-1)/2}}{1-\delta^{H/2}}. \end{aligned}$$

Then we have

$$\displaystyle \begin{aligned} \frac{H}{\Lambda} < \mu \le \frac{\Lambda}{H-1/c}, {} \end{aligned} $$

(24)

where

$$\displaystyle \begin{aligned} c = \frac{\left( 1-\delta^{1/2} \right)\delta^{(H-1)/2}}{1-\delta^{H/2}}. \end{aligned}$$

As mentioned before, we assume that the aggregated requests do not exceed the capacity of all the servers, i.e., Hμ >  Λ. In addition, if $\mu > \frac {\Lambda }{H-1/c}$, it is possible to shutdown some servers such that μ satisfies the constraint (24), which can also save energy cost. Therefore, in this paper, we assume that the total processing capacity μ satisfies constraint (24).

From Theorem 3.1, we know that if the cloud provider wants to appeal all the n cloud users to use its service, then proper pricing parameters a and b can be selected to satisfy constraint (17). Specifically, if b (a) is given, and a (b) is higher than the computed value from (17), then there exist some users who refuse to use the cloud service, because their obtained utilities are less than their reservation values.

3.2.3 Nash Equilibrium Analysis

In this subsection, we analyze the existence of Nash equilibrium for the formulated game $G = \left \langle {Q,\boldsymbol {f}} \right \rangle$ and prove the existence problem by employing variational inequality (VI) theory. Then we propose an iterative proximal algorithm (IPA). The convergence of the proposed algorithm is also analyzed. Before address the problem, we show three important properties presented in Theorems 3.2, 3.3, and 3.4, which are helpful to prove the existence of Nash equilibrium for the formulated game.

Theorem 3.2

For each cloud user i ( $i \in \mathcal {N}$), the set Q _i is convex and compact, and each disutility function f _i(λ _i, λ _−i) is continuously differentiable in λ _i. For each fixed tuple λ _−i, the disutility function f _i(λ _i, λ _−i) is convex in λ _i over the set Q _i.

Proof

It is obvious that the statements in the first part of above theorem hold. We only need to prove the convexity of f _i(λ _i, λ _−i) in λ _i for every fixed λ _−i. This can be achieved by proving that the Hessian matrix of f _i(λ _i, λ _−i) is positive semidefinite [12, 36]. Since ${f_i}({\boldsymbol {\lambda } _i},{\boldsymbol {\lambda } _{ - i}}) = \sum \limits _{h = 1}^H {\left ( {P_i^h + {w_i}{\delta ^h}{{\bar T}^h} - r\lambda _i^h} \right )}$, we have

$$\displaystyle \begin{aligned} {\nabla _{{\boldsymbol{\lambda} _i}}}{f_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{ - i}}) = \left[ {\frac{{\partial {f_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{ - i}})}}{{\partial \lambda _i^h}}} \right]_{h = 1}^H = \left( {\frac{{\partial {f_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{ - i}})}}{{\partial \lambda _i^1}}, \ldots ,\frac{{\partial {f_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{ - i}})}}{{\partial \lambda _i^H}}} \right). \end{aligned} $$

and the Hessian matrix is expressed as

$$\displaystyle \begin{aligned} \nabla _{{\boldsymbol{\lambda} _i}}^2 & {f_i} ({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{ - i}}) \\ & = {\mathrm{diag}}\left\{ {\left[ {\frac{{{\partial ^2}f_i({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{ - i}})}}{{\partial {{(\lambda _i^h)}^2}}}} \right]_{h = 1}^H} \right\} \\ & = {\mathrm{diag}}\left\{ {\left[ {2a\left( {2\lambda _{\Sigma} ^h + \lambda _i^h} \right) +\frac{2{w_i}{\delta^h}}{{{{\left( {\mu - \lambda _{\Sigma} ^h} \right)}^3}}}} \right]_{h = 1}^H} \right\}. {} \end{aligned} $$

(25)

Obviously, the diagonal matrix in (25) has all diagonal elements being positive. Thus, the Hessian matrix of f _i(λ _i, λ _−i) is positive semidefinite and the result follows. The theorem is proven. □

Theorem 3.3

The Nash equilibrium of the formulated game G is equivalent to the solution of the variational inequality (VI) problem, denoted by VI(Q, F), where Q = Q ₁ ×⋯ × Q _n and

$$\displaystyle \begin{aligned} {\boldsymbol{{\mathrm{F}}}}(\boldsymbol{\lambda} ) = \left( {{\boldsymbol{{\mathrm{F}}}_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{ - i}})} \right)_{i = 1}^n, \end{aligned} $$

(26)

with

$$\displaystyle \begin{aligned} {\boldsymbol{{\mathrm{F}}}_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{ - i}}) = {\nabla _{{\boldsymbol{\lambda} _i}}}{f_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{ - i}}). \end{aligned} $$

(27)

Proof

According to Prop. 4.1 in [37], we know that the above claim follows if two conditions are satisfied. First, for each user i ($i \in \mathcal {N}$), the strategy set Q _i is closed and convex. Second, for every fixed λ _−i, the disutility function f _i(λ _i, λ _−i) is continuously differentiable and convex in λ _i ∈ Q _i. By Theorem 3.2, it is easy to know that both the mentioned two conditions are satisfied in the formulated game G. Thus, the result follows. □

Theorem 3.4

If both matrices $\mathcal {M}_1$ and $\mathcal {M}_2$ are semidefinite, then the matrix $\mathcal {M}_3 = \mathcal {M}_1+\mathcal {M}_2$ is also semidefinite.

Proof

As mentioned above, both matrices $\mathcal {M}_1$ and $\mathcal {M}_2$ are semidefinite. Then we have ∀x

$$\displaystyle \begin{aligned} \boldsymbol{x}^T\mathcal{M}_1\boldsymbol{x} \ge 0 \ \mbox{and} \ \boldsymbol{x}^T\mathcal{M}_2\boldsymbol{x} \ge 0. \end{aligned}$$

We obtain ∀x,

$$\displaystyle \begin{aligned} \boldsymbol{x}^T\mathcal{M}_3\boldsymbol{x} = \boldsymbol{x}^T\mathcal{M}_1\boldsymbol{x} + \boldsymbol{x}^T\mathcal{M}_2\boldsymbol{x} \ge 0. \end{aligned}$$

Thus, we can conclude that $\mathcal {M}_3$ is semidefinite and the result follows. □

Recall that the objective of this subsection is to study the existence of Nash equilibrium for the formulated game $G = \left \langle {Q,\boldsymbol {f}} \right \rangle$ in (54). In the next theorem, we prove that if several conditions are satisfied, the existence of such Nash equilibrium is guaranteed.

Theorem 3.5

If max_i=1,…,n(w _i) ≤ 1∕n, there exists a Nash equilibrium solution set for the formulated game $G = \left \langle {Q, \boldsymbol {f}} \right \rangle$.

Proof

Based on Theorem 3.3, the proof of this theorem follows if we can show that the formulated variational inequality problem VI(Q, F) in Theorem 3.3 possesses a solution set. According to Th. 4.1 in [37], the VI(Q, F) admits a solution set if the mapping $\boldsymbol {{\mathrm {F}}} \left ( \boldsymbol {\lambda } \right )$ is monotone over Q, since the feasible set Q is compact and convex.

To prove the monotonicity of $\boldsymbol {{\mathrm {F}}} \left ( \boldsymbol {\lambda } \right )$, it suffices to show that for any λ and s in Q,

$$\displaystyle \begin{aligned} {\left( {\boldsymbol{\lambda} - \boldsymbol{s}} \right)^T}\left( {\boldsymbol{{\mathrm{F}}}\left( \boldsymbol{\lambda} \right) - \boldsymbol{{\mathrm{F}}}\left( \boldsymbol{s} \right)} \right) \ge 0, \end{aligned}$$

namely,

$$\displaystyle \begin{aligned} \sum_{h = 1}^H {\sum_{i = 1}^n {\left( {\lambda _i^h - s_i^h} \right)\left( {{\nabla _{\lambda _i^h}}{f_i}\left( \boldsymbol{\lambda} \right) - {\nabla _{s_i^h}}{f_i}\left( \boldsymbol{s} \right)} \right)} } \ge 0. {} \end{aligned} $$

(28)

Let ${\boldsymbol {\lambda } ^h} = {\left ( {\lambda _1^h, \ldots ,\lambda _n^h} \right )^T}$ and ${\boldsymbol {s}^h} = {\left ( {s_1^h, \ldots ,s_n^h} \right )^T}$, then we can write (28) as

$$\displaystyle \begin{aligned} \sum_{h = 1}^H {\left( {{\boldsymbol{\lambda} ^h} - {\boldsymbol{s}^h}} \right)\left( {{\nabla _{{\boldsymbol{\lambda} ^h}}}{f^h}\left( {{\boldsymbol{\lambda} ^h}} \right) - {\nabla _{{\boldsymbol{s}^h}}}{f^h}\left( {{\boldsymbol{s}^h}} \right)} \right)} \ge 0, {} \end{aligned} $$

(29)

where

$$\displaystyle \begin{aligned} {f^h}\left( {{\boldsymbol{\lambda} ^h}} \right) = \sum\limits_{i = 1}^n {\left( {P_i^h + {w_i}{\delta^h}{{\bar T}^h} - r\lambda _i^h} \right)}, \end{aligned}$$

and

$$\displaystyle \begin{aligned} {\nabla _{{\boldsymbol{\lambda} ^h}}}{f^h}\left( {{\boldsymbol{\lambda} ^h}} \right) = {\left( {{\nabla _{\lambda _1^h}}{f^h}\left( {{\boldsymbol{\lambda} ^h}} \right), \ldots ,{\nabla _{\lambda _n^h}}{f^h}\left( {{\boldsymbol{\lambda} ^h}} \right)} \right)^T}. \end{aligned}$$

We can observe that if

$$\displaystyle \begin{aligned} \left( {{\boldsymbol{\lambda} ^h} - {\boldsymbol{s}^h}} \right)\left( {{\boldsymbol{g}^h}\left( {{\boldsymbol{\lambda} ^h}} \right) - {\boldsymbol{g}^h}\left( {{\boldsymbol{s}^h}} \right)} \right) \ge 0, \ \forall h \in \mathcal{H}, {} \end{aligned} $$

(30)

where ${\boldsymbol {g}^h}\left ( {{\boldsymbol {\lambda } ^h}} \right ) = {\nabla _{{\boldsymbol {\lambda } ^h}}}{f^h}({\boldsymbol {\lambda } ^h})$, then equation (29) holds.

Recall the definition of a monotone mapping, we can find that (30) holds if the mapping ${\boldsymbol {g}^h}\left ( {{\boldsymbol {\lambda } ^h}} \right )$ is monotone. With reference to [37], the condition in (30) is equivalent to proving the Jacobian matrix of ${\boldsymbol {g}^h}\left ( {{\boldsymbol {\lambda } ^h}} \right )$, denoted by $\boldsymbol {{\mathrm {G}}}\left ( {{\boldsymbol {\lambda } ^h}} \right )$, is positive semidefinite.

After some algebraic manipulation, we can write the (i, j)th element of $\boldsymbol {{\mathrm {G}}}\left ( {{\boldsymbol {\lambda } ^h}} \right )$ as

$$\displaystyle \begin{aligned} {\left[ {\boldsymbol{{\mathrm{G}}}\left( {{\boldsymbol{\lambda} ^h}} \right)} \right]_{i,j}} = \begin{cases} {2a\left( {2\lambda _{\Sigma} ^h + \lambda _i^h} \right) +{\frac{2{w_i}{\delta^h}}{{{{\left( {\mu - \lambda _{\Sigma} ^h} \right)}^3}}}}, \ \mbox{if} \ i = j}; \\ {2a\left( {\lambda _{\Sigma} ^h + \lambda _i^h} \right) +{\frac{2{w_i}{\delta^h}}{{{{\left( {\mu - \lambda _{\Sigma} ^h} \right)}^3}}}}, \ \ \mbox{if} \ i \ne j.} \end{cases} \end{aligned} $$

Since the matrix $\boldsymbol {{\mathrm {G}}}\left ( {{\boldsymbol {\lambda } ^h}} \right )$ may not be symmetric, we can prove its positive semidefiniteness by showing that the symmetric matrix

$$\displaystyle \begin{aligned} \boldsymbol{{\mathrm{G}}} & \left( {{\boldsymbol{\lambda} ^h}} \right) + \boldsymbol{{\mathrm{G}}}{\left( {{\boldsymbol{\lambda} ^h}} \right)^T} = \\ & 2a\underbrace {\left({\boldsymbol{\lambda} ^h}\boldsymbol{1}_{n \times 1}^T + {\boldsymbol{1}_{n \times 1}}{{\left( {{\boldsymbol{\lambda} ^h}} \right)}^T} + 2\lambda _{\Sigma} ^h{\boldsymbol{1}_{n \times n}} + 2\lambda _{\Sigma} ^h{\boldsymbol{{\mathrm{E}}}_n} \right)}_{{\mathcal{M}_1}} \\ & + 2a\sigma \underbrace {\left( {\boldsymbol{w}\boldsymbol{1}_{n \times 1}^T + {\boldsymbol{1}_{n \times 1}}{\boldsymbol{w}^T}} \right)}_{{\mathcal{M}_2}} \end{aligned}$$

is positive semidefinite [38], where

$$\displaystyle \begin{aligned} \sigma = {\frac{{\delta^h}}{{{{a\left( {\mu - \lambda _{\Sigma} ^h} \right)}^3}}}}, \end{aligned}$$

w = (w ₁, …, w _n)^T, 1 _r×s is a r × s matrix with every element of 1, and E _n is an identity matrix. This is equivalent to showing that the smallest eigenvalue of this matrix is non-negative.

With referring to [12, 38], we obtain the two non-zero eigenvalues of $\mathcal {M}_1$ as follows:

$$\displaystyle \begin{aligned} \eta _{\mathcal{M}_1}^1 = (n+3)\lambda _{\Sigma} ^h + \sqrt {n\sum_{i = 1}^n {{{\left( {\lambda _i^h + \lambda _{\Sigma} ^h} \right)}^2}} }, \end{aligned}$$

$$\displaystyle \begin{aligned} \eta _{\mathcal{M}_1}^2 = (n+3)\lambda _{\Sigma} ^h - \sqrt {n\sum_{i = 1}^n {{{\left( {\lambda _i^h + \lambda _{\Sigma} ^h} \right)}^2}} }. \end{aligned}$$

Let

$$\displaystyle \begin{aligned} A\left(\boldsymbol{\lambda}^h\right) = (n+3)\lambda _{\Sigma} ^h,\ \end{aligned}$$

and

$$\displaystyle \begin{aligned} B\left(\boldsymbol{\lambda}^h\right) = \sqrt {n\sum\limits_{i = 1}^n {{{\left( {\lambda _i^h + \lambda _{\Sigma} ^h} \right)}^2}} }, \end{aligned}$$

and $\eta _{\min }$ be the minimal eigenvalue of matrix $\mathcal {M}_1$. Then, we have $\eta _{\min } = \min \left \{ A\left (\boldsymbol {\lambda }^h\right ) - B\left (\boldsymbol {\lambda }^h\right ), 2\lambda _{\Sigma }^h \right \}$. Furthermore, we can derive that

$$\displaystyle \begin{aligned} {\left( {A\left( {{\boldsymbol{\lambda} ^h}} \right)} \right)^2} - {\left( {B\left( {{\boldsymbol{\lambda} ^h}} \right)} \right)^2} &=\left( 4n+9 \right)\left( \lambda _{\Sigma} ^h \right)^2 - n\sum_{i = 1}^n {{{\left( \lambda _i^h \right)}^2}} \\ & \geq n\left( \left(\sum_{i = 1}^n \lambda _i^h \right)^2 - \sum_{i = 1}^n {{{\left( \lambda _i^h \right)}^2}} \right) \geq 0. \end{aligned} $$

Hence, we can obtain $\eta _{\min } \ge 0$ and conclude that $\mathcal {M}_1$ is semidefinite. Similar to the semidefinite proof of $\mathcal {M}_1$, we can also obtain that if max_i=1,…,n(w _i) ≤ 1∕n, then $\mathcal {M}_2$ is semidefinite. By Theorem 3.4, we can conclude that the matrix $\boldsymbol {{\mathrm {G}}}\left ( {{\boldsymbol {\lambda } ^h}} \right )$ is semidefinite, and the result follows. □

3.2.4 An Iterative Proximal Algorithm

Once we have established that the Nash equilibria of the formulated game $\boldsymbol {{\mathrm {G}}} = \left \langle {Q,\boldsymbol {f}} \right \rangle$ exists, we are interested in obtaining a suitable algorithm to compute one of these equilibria with minimum information exchange between the multiple users and the cloud provider.

Note that we can further rewrite the optimization problem (54) as follows:

$$\displaystyle \begin{aligned} \mbox{minimize} \quad &{f_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{\Sigma}}) = \sum_{h = 1}^H {\left( {P_i^h + {w_i}{\delta ^h}{{\bar T}^h} - r\lambda _i^h} \right),} \\ \mbox{s.t.} \quad &\boldsymbol{\lambda}_i \in Q_i, {} \end{aligned} $$

(31)

where λ _Σ denotes the aggregated request profile of all users over the H future time slots, i.e., ${\boldsymbol {\lambda } _{\Sigma } } = \sum \limits _{i = 1}^n {{\boldsymbol {\lambda } _i}}$. From (31), we can see that the calculation of the disutility function of each individual user only requires the knowledge of the aggregated request profile of all users (λ _Σ) rather than that the specific individual request profile of all other users (λ _−i), which can bring about two advantages. On the one hand, it can reduce communication traffic between users and the cloud provider. On the other hand, it can also keep privacy for each individual user to certain extent, which is seriously considered by many cloud users.

Since all users are considered to be selfish and try to minimize their own disutilities while ignoring the others. It is natural to consider an iterative algorithm where, at every iteration k, each individual user i ($\forall i \in \mathcal {N}$) updates his/her strategy to minimize his/her own disutility function f _i(λ _i, λ _Σ). However, following Th. 4.2 in [37], it is not difficult to show that their convergence cannot be guaranteed in our case if the users are allowed to simultaneously update their strategies according to (31).

To overcome this issue, we consider an iterative proximal algorithm (IPA), which is based on the proximal decomposition Alg. 4.2 [37]. The proposed algorithm is guaranteed to converge to a Nash equilibrium under some additional constraints on the parameters of the algorithm. With reference to [37], consider the regularized game in which each user i ($i \in \mathcal {N}$) tries to solve the following optimization problem:

$$\displaystyle \begin{aligned} \mbox{minimize} \quad &{f_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{\Sigma}}) + \frac{\tau }{2}{\left\|{\boldsymbol{\lambda} _i} - \bar{\boldsymbol{\lambda}}_{\boldsymbol{i}} \right\|{}^2}, \\ \mbox{s.t.} \quad &\boldsymbol{\lambda}_i, \bar{\boldsymbol{\lambda}}_{\boldsymbol{i}} \in Q_i. {} \end{aligned} $$

(32)

That is to say, when given the aggregated requests, we must find a strategy vector $\boldsymbol {\lambda }_i^\ast$ for user i ($i \in \mathcal {N}$) such that

$$\displaystyle \begin{aligned} \boldsymbol{\lambda} _i^\ast \in \mathop {\arg \min }\limits_{{\boldsymbol{\lambda} _i} \in {Q_i}} \left\{ {f_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{\Sigma}}) + \frac{\tau }{2}{\left\|{\boldsymbol{\lambda} _i} - \bar{\boldsymbol{\lambda}}_{\boldsymbol{i}} \right\|{}^2} \right\}, {} \end{aligned} $$

(33)

where τ(τ > 0) is a regularization parameter and may guarantee the convergence of the best-response algorithm Cor. 4.1 in [37] if it is large enough. The idea is formalized in Algorithm 1.

Algorithm 1 Iterative Proximal Algorithm (IPA)

Theorem 3.6

There exists a constant τ ₀ such that if τ > τ ₀, then any sequence $\left \{ {\boldsymbol {\lambda } _i^{(k)}} \right \}_{k = 1}^\infty$ (i ∈ S _c) generated by the IPA algorithm converges to a Nash equilibrium.

Proof

We may note that Algorithm 1 converges if the inner while loop (Steps 4–14) can be terminated. Therefore, if we can prove that Steps 4–14 converges, the result follows. In practice, Steps 4–14 in Algorithm 1 is a developed instance of the proximal decomposition algorithm, which is presented in Alg. 4.2 [37] for the variational inequality problem. Next, we rewrite the convergence conditions exploiting the equivalence between game theory and variational inequality (Ch. 4.2 in [37]). Given f _i(λ _i, λ _−i) defined as in Eq. (54), Algorithm 1 convergences if the following two conditions are satisfied. (1) The Jacobian matrix of F is positive semidefinite (Th. 4.3 [37]). We denote the Jacobian by ${\mathrm {J}}\boldsymbol {{\mathrm {F}}}(\boldsymbol {\lambda } ) = \left ( {{{\mathrm {J}}_{{\boldsymbol {\lambda } _j}}}{\boldsymbol {{\mathrm {F}}}_i}(\boldsymbol {\lambda } )} \right )_{i,j = 1}^n$, where ${{{\mathrm {J}}_{{\boldsymbol {\lambda } _j}}}{\boldsymbol {{\mathrm {F}}}_i}(\boldsymbol {\lambda } )} = \left ( {{\nabla _{{\boldsymbol {\lambda } _j}}}{f_i}(\boldsymbol {\lambda } )} \right )_{j = 1}^n$, which is the partial Jacobian matrix of F _i with respect to λ _j vector. (2) The n × n matrix Υ _F,τ = Υ _F + τE _n is a P-matrix (Cor. 4.1 [37]), where

$$\displaystyle \begin{aligned} {\left[ {{\boldsymbol{\Upsilon} _{\mathbf{F}}}} \right]_{ij}} = \begin{cases} \alpha_i^{\min}, & \mbox{if} \ i = j; \\ -\beta_{ij}^{\max}, & \mbox{if} \ i \ne j; \end{cases} \end{aligned} $$

with

$$\displaystyle \begin{aligned} \alpha _i^{\min } = \mathop {\inf }\limits_{\boldsymbol{\lambda} \in Q} {\eta _{\min }}\left( {{\boldsymbol{{\mathrm{J}}}_{{\boldsymbol{\lambda} _i}}}{\boldsymbol{{\mathrm{F}}}_i}\left( \boldsymbol{\lambda} \right)} \right), \end{aligned}$$

and

$$\displaystyle \begin{aligned} \beta _{ij}^{\max } = \mathop {\sup }\limits_{\boldsymbol{\lambda} \in Q} {\eta _{\min }}\left( {{\boldsymbol{{\mathrm{J}}}_{{\boldsymbol{\lambda} _j}}}{\boldsymbol{{\mathrm{F}}}_i}\left( \boldsymbol{\lambda} \right)} \right), \end{aligned}$$

and ${\eta _{\min }}\left ( \boldsymbol {{\mathrm {A}}} \right )$ denoting the smallest eigenvalue of A. After some algebraic manipulation, we can write the block elements of JF(λ) as

$$\displaystyle \begin{aligned} {{\mathrm{J}}_{{\boldsymbol{\lambda} _i}}}{\boldsymbol{{\mathrm{F}}}_i}(\boldsymbol{\lambda} ) & = \nabla _{{\boldsymbol{\lambda} _i}}^2{f_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{\Sigma}}) \\ & = {\mathrm{diag}}\left\{ {\left[ {2a\left( {2\lambda _{\Sigma} ^h + \lambda _i^h} \right) +\frac{2{w_i}{\delta^h}}{{{{\left( {\mu - \lambda _{\Sigma} ^h} \right)}^3}}}} \right]_{h = 1}^H} \right\}, \end{aligned} $$

and

$$\displaystyle \begin{aligned} {{\mathrm{J}}_{{\boldsymbol{\lambda} _j}}}{\boldsymbol{{\mathrm{F}}}_i}(\boldsymbol{\lambda} ) & = \nabla _{{\boldsymbol{\lambda} _i\boldsymbol{\lambda} _j}}^2{f_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{\Sigma}}) \\ & = {\mathrm{diag}}\left\{ {\left[ {2a\left( {\lambda _{\Sigma} ^h + \lambda _i^h} \right) +\frac{2{w_i}{\delta^h}}{{{{\left( {\mu - \lambda _{\Sigma} ^h} \right)}^3}}}} \right]_{h = 1}^H} \right\}, \end{aligned} $$

for i≠j ($i,j \in \mathcal {N}$).

Next, we show that the above conditions (1) and (2) hold, respectively. By Theorem 3.2, we know that the vector function F(λ) is monotone on Q, which implies that JF(λ) is semidefinite. On the other hand, considering ${{\mathrm {J}}_{{\boldsymbol {\lambda } _i}}}{\boldsymbol {{\mathrm {F}}}_i}(\boldsymbol {\lambda } )$, we have $\alpha _i^{\min } > 0$.

Let

$$\displaystyle \begin{aligned} {L^h}({\lambda_i ^h}, \boldsymbol{\lambda} _{-i}^h) = 2a\left( {\lambda _{\Sigma} ^h + \lambda _i^h} \right) +\frac{2{w_i}{\delta^h}}{{{{\left( {\mu - \lambda _{\Sigma} ^h} \right)}^3}}}. \end{aligned}$$

Then, we have $\frac {{\partial {L^h}}}{{\partial \lambda _i^h}} > 0$. As mentioned before, $\lambda _{\Sigma }^h$ ($\forall h \in \mathcal {H}$) does not exceed the total processing capacity of all servers μ. We assume that $\lambda _{\Sigma }^h \le (1 - \varepsilon )\mu$, where ε is a small positive constant. Then we can conclude that

$$\displaystyle \begin{aligned} {L^h}({\lambda_i ^h}, \boldsymbol{\lambda} _{-i}^h) \le 4a\left( 1-\varepsilon \right)\mu +\frac{2{w_{\max}}{\delta^h}}{{{{\left( \varepsilon\mu \right)}^3}}}, \end{aligned}$$

where $w_{\max } = \max _{i=1,\ldots ,n}\{w_i\}$.

Hence, if

$$\displaystyle \begin{aligned} \tau_0 \ge (n-1)\left( 4a\left( 1-\varepsilon \right)\mu +\frac{2{w_{\max}}{\delta^H}}{{{{\left( \varepsilon\mu \right)}^3}}} \right), \end{aligned}$$

then

$$\displaystyle \begin{aligned} \beta _{ij}^{\max } = \mathop {\sup }\limits_{\boldsymbol{\lambda} \in Q} \left\|{{{\mathrm{J}}_{{\boldsymbol{\lambda} _j}}}{\boldsymbol{{\mathrm{F}}}_i}\left( \boldsymbol{\lambda} \right)} \right\| \le \tau_0. \end{aligned}$$

Then, it follows from Prop 4.3 in [37] that, if τ is chosen as in Theorem 3.6, the matrix Υ _F,τ is a P-matrix, and the result follows. □

Next, we focus on the calculation for the optimization problem in (33). Let

$$\displaystyle \begin{aligned} L_i(\boldsymbol{\lambda}_i, \boldsymbol{\lambda}_{\Sigma}) & = {f_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\lambda} _{\Sigma}}) + \frac{\tau }{2}{\left\|{\boldsymbol{\lambda} _i} - \bar{\boldsymbol{\lambda}}_{\boldsymbol{i}} \right\|{}^2}. {} \end{aligned} $$

(34)

Then, we have to minimize L _i(λ _i, λ _Σ). Note that the variable in (34) is only λ _i, therefore, we can rewrite (34) as

$$\displaystyle \begin{aligned} L_i(\boldsymbol{\lambda}_i, \boldsymbol{\kappa}_{\Sigma}) & = {f_i}({\boldsymbol{\lambda} _i},{\boldsymbol{\kappa} _{\Sigma}}) + \frac{\tau }{2}{\left\|{\boldsymbol{\lambda} _i} - \bar{\boldsymbol{\lambda}}_{\boldsymbol{i}} \right\|{}^2}, {} \end{aligned} $$

(35)

where κ _Σ = λ _Σ −λ _i. We denote R _i the constraint of user i, i.e.,

$$\displaystyle \begin{aligned} {R_i} = \lambda_i^1 + \lambda_i^2 + \ldots + \lambda_i^H = {\Lambda _i}, \end{aligned}$$

and try to minimize L _i(λ _i, κ _Σ) by using the method of Lagrange multiplier, namely,

$$\displaystyle \begin{aligned} \frac{{\partial {L_i}}}{{\partial \lambda _i^h}} = \phi \frac{{\partial {R_i}}}{{\partial \lambda _i^h}} = \phi, \end{aligned}$$

for all 1 ≤ h ≤ H, where ϕ is a Lagrange multiplier. Notice that

$$\displaystyle \begin{aligned} \frac{{\partial P_i^h}}{{\partial \lambda _i^h}} = a\left( {2(\lambda_i^h + \kappa _{\Sigma} ^h)\lambda _i^h + {{\left( {\lambda_i^h + \kappa _{\Sigma} ^h} \right)}^2}} \right) + b, \end{aligned}$$

and

$$\displaystyle \begin{aligned} \frac{{\partial {{\bar T}^h}}}{{\partial \lambda _i^h}} = \frac{1}{{{{\left( {\mu - \kappa _{\Sigma} ^h - \lambda_i^h} \right)}^2}}}. \end{aligned}$$

We obtain

$$\displaystyle \begin{aligned} \frac{{\partial {L_i}}}{{\partial \lambda _i^h}} & = \frac{{\partial P_i^h}}{{\partial \lambda _i^h}} + w_i\delta^h\frac{{\partial {{\bar T}^h}}}{{\partial \lambda _i^h}}-r + \tau \left( {\lambda _i^h - \bar \lambda _i^h} \right) \\ & {=} a\left( {2(\lambda_i^h {+} \kappa _{\Sigma} ^h)\lambda _i^h {+} {{\left( {\lambda_i^h {+} \kappa _{\Sigma} ^h} \right)}^2}} \right) {+} b {+} \frac{{{w_i}{\delta ^h}}}{{{{\left( {\mu {-} \kappa _{\Sigma} ^h {-} \lambda_i^h} \right)}^2}}} {-} r {+} \tau \left( {\lambda _i^h {-} \bar \lambda _i^h} \right) {=} \phi. {} \end{aligned} $$

(36)

Denote $Y_i^h(\lambda _i^h, \kappa _{\Sigma }^h)$ as the first order of L _i(λ _i, κ _Σ) on $\lambda _i^h$. Then, we have

$$\displaystyle \begin{aligned} Y_i^h(\lambda_i^h, & \kappa_{\Sigma}^h) = a\left( {2(\lambda_i^h + \kappa _{\Sigma} ^h)\lambda _i^h + {{\left( {\lambda_i^h + \kappa _{\Sigma} ^h} \right)}^2}} \right) \\ & + b + \frac{{{w_i}{\delta ^h}}}{{{{\left( {\mu - \kappa _{\Sigma} ^h - \lambda_i^h} \right)}^2}}} - r + \tau \left( {\lambda _i^h - \bar \lambda _i^h} \right). {} \end{aligned} $$

(37)

Since the first order of $Y_i^h(\lambda _i^h, \kappa _{\Sigma }^h)$ is

$$\displaystyle \begin{aligned} \frac{{\partial Y_i^h}}{{\partial \lambda _i^h}} = \frac{{{\partial ^2}{L_i}}}{{\partial {{\left( {\lambda _i^h} \right)}^2}}} = & 2a\left( {3\lambda_i^h + 2\kappa _{\Sigma} ^h } \right) + \frac{{2{w_i}{\delta ^h}}}{{{{\left( {\mu - \kappa _{\Sigma} ^h - \lambda_i^h} \right)}^3}}} + \tau > 0, {} \end{aligned} $$

(38)

we can conclude that $Y_i^h(\lambda _i^h, \kappa _{\Sigma }^h)$ is an increasing positive function on $\lambda _i^h$. Based on above derivations, we propose an algorithm to calculate λ _i ($i \in \mathcal {N}$), which is motivated by [35].

Given ε, μ, a, b, r, τ, λ _i, λ _Σ, and Λ_i, our optimal request configuration algorithm to find λ _i is given in Algorithm 2. The algorithm uses another subalgorithm Calculate$\_\lambda _i^h$ described in Algorithm 3, which, given $\varepsilon , \mu , a, b, r, \tau , \kappa _{\Sigma }^h$, and ϕ, finds $\lambda _i^h$ satisfies (36).

The key observation is that the left-hand side of (36), i.e., (37), is an increasing function of $\lambda _i^h$ (see (38)). Therefore, given ϕ, we can find $\lambda _i^h$ by using the binary search method in certain interval [lb, ub] (Steps 2–9 in Algorithm 3). We set lb simply as 0. For ub, as mentioned in Theorem 3.6,

$$\displaystyle \begin{aligned} \lambda_i^h \le (1-\varepsilon)\mu, \end{aligned}$$

where ε is a relative small positive constant. Therefore, in this paper, ub is set in Step 1 based on the above discussion. The value of ϕ can also be found by using the binary search method (Steps 10–20 in Algorithm 2). The search interval [lb, ub] for ϕ is determined as follows. We set lb simply as 0. As for ub, we notice that the left-hand side of (36) is an increasing function of $\lambda _i^h$. Then, we set an increment variable inc, which is initialized as a relative small positive constant and repeatedly doubled (Step 7). The value of inc is added to ϕ to increase ϕ until the sum of $\lambda _i^h$ ($h \in \mathcal {H}$) found by Calculate$\_\lambda _i^h$ is at least Λ_i (Steps 2–8). Once [lb, ub] is decided, ϕ can be searched based on the fact that $Y_i^h(\lambda _i^h, \boldsymbol {\lambda }_{-i}^h)$ is an increasing function of $\lambda _i^h$. After ϕ is determined (Step 21), λ _i can be computed (Steps 22–24).

Algorithm 2 Calculate_λ _i(ε, μ, a, b, r, τ, λ _i, λ _Σ, Λ_i)

Algorithm 3 Calculate_λih(ε, μ, a, b, r, τ, κ Σh, ϕ)

Finally, we can describe the proposed iterative proximal algorithm as follows. At the beginning, each cloud user i ($i \in \mathcal {N}$) sends his/her weight value (w _i) and total task request ( Λ_i) to the cloud provider. Then the cloud provider computes τ as in Theorem 3.6 according to the aggregated information and chooses proper parameters a and b such that constraint (17) is satisfied. After this, the cloud provider puts the computed load billing parameters a and b into public information exchange module. Then, at each iteration k, the cloud provider broadcasts a synchronization signal and the current aggregated request profile $\boldsymbol {\lambda } _{\Sigma }^{(k)}$. Within iteration k, each user receives the aggregated profile $\boldsymbol {\lambda } _{\Sigma }^{(k)}$ and computes his/her strategy by solving its own optimization problem in (32), and then sends the newly updated strategy to the cloud provider. Lastly, as indicated in Steps 10–12 of Algorithm 1, the cloud provider checks whether the Nash equilibrium has been achieved and if so, it broadcasts a signal to inform all users to update their centroid $\bar {\boldsymbol {\lambda }} _{\boldsymbol {i}}$. It also checks whether all cloud users’ strategies are unchanged and if so, it informs all users to choose whether they still prefer to the cloud service due to their reserved values. This process continues until the set of the remaining cloud users and their corresponding strategies are kept fixed. In this paper, we assume that the strategies of all cloud users are unchanged if ${\left \|{{\boldsymbol {\lambda } ^{(k)}} - {\boldsymbol {\lambda } ^{(k - 1)}}} \right \|} \le \epsilon$, where ${\boldsymbol {\lambda } ^{(k)}} = \left ( {\boldsymbol {\lambda } _i^{(k)}} \right )_{i = 1}^n$ with $\boldsymbol {\lambda } _i^{(k)} = \left ( {{{\left ( {\lambda _i^h} \right )}^{(k)}}} \right )_{h = 1}^H$. The parameter 𝜖 is a pre-determined relatively small constant. We also denote S _c as the current set of remaining cloud users. Note that the individual strategies are not revealed among the users in any case, and only the aggregated request profile λ ^(k), which is determined at the cloud provider adding the individual H-time slots ahead request profile, is communicated between the cloud provider and multiple cloud users.

3.3 Performance Evaluation of IPA

In this section, we provide some numerical results to validate our theoretical analyses and illustrate the performance of the IPA algorithm.

In the following simulation results, we consider the scenario consisting of maximal 50 cloud users. Each time slot is set as one hour of a day and H is set as 24. As shown in Table 1, the aggregated request (Λ) is varied from 50 to 500 with increment 50. The number of cloud users (n) is varied from 5 to 50 with increment 5. Each cloud user i ($i \in \mathcal {N}$) chooses a weight value from 0 to 1∕n to balance his/her time utility and net profit. For simplicity, the reservation value v _i for each user i ($i \in \mathcal {N}$) and billing parameter b are set to zero. Market benefit factor r is set to 50, deteriorating rate on time utility δ is equal to 1.2, and ε is set as 0.01. The total capacity of all servers μ is selected to satisfy constraint (24) and another billing parameter a is computed according to (17). In our simulation, the initial strategy configuration, i.e., before using IPA algorithm, is randomly generated from Q.

Table 1 System parameters

Figure 2 presents the utility results for five different cloud users versus the number of iterations of the proposed IPA algorithm. Specifically, Fig. 2 presents the utility results of 5 randomly selected cloud users (users 1, 9, 23, 38, and 46) with a scenario consisting of 50 cloud users. We can observe that the utilities of all the users seem to increase and finally reach a relative stable state with the increase of iteration number. The reason behind lies in that the request strategies of all the users keep unchanged, i.e., reach a Nash equilibrium solution after several iterations. This trend also reflects the convergence process of our proposed IPA algorithm. It can be seen that the developed algorithm converges to a Nash equilibrium very quickly. Specifically, the utility of each user has already achieved a relatively stable state after about 8 iterations, which verifies the validness of Theorem 3.6, as well as displays the high efficiency of the developed algorithm.

Fig. 2

Convergence process

In Fig. 3, we compare the aggregated request profile of all cloud users with the situation before and after IPA algorithm. Specifically, Fig. 3 shows the aggregated requests in different time slots. The situation before IPA algorithm corresponds to a feasible strategy profile randomly generated in the initialization stage, while the situation after IPA algorithm corresponds to the result obtained by using our proposed IPA algorithm. Obviously, the proposed service reservation scheme encourages the cloud users to shift their task requests in peak time slots to non-peak time slots, resulting in a more balanced load shape and lower total load. We can also observe that the aggregated requests in different time slots are almost the same. To demonstrate this phenomenon, we further investigate the specific utilities of some users and their corresponding strategies in different time slots, which are presented in Figs. 4 and 5.

Fig. 3

Aggregation load

Fig. 4

Specific slot utility

Fig. 5

Specific slot shifting

In Figs. 4 and 5, we plot the utility shape and the request profile of some cloud users for the developed IPA algorithm for a scenario of 10 users. Figure 4 presents the utility shape under the developed algorithm over future 24 time slots. We randomly select 6 users (users 2, 3, 4, 7, 9, and 10). It can be seen that the utilities in different time slots of all users tend to decrease at different degrees. Specifically, the slot utilities of the users with higher weights have a clearly downward trend and tend to decrease sharply in later time slots (users 2, 3, 7, 9). On the other hand, the slot utilities of the users with lower weights decline slightly (users 4, 10). Figure 5 exhibits the corresponding request strategies of the users shown in Fig. 4. We can observe that the slot utilities of the users with higher weights tend to decrease (users 2, 3, 7, 9) while those of the users with lower weights tend to increase (users 4, 10). Furthermore, the aggregated requests increase or decrease sharply in later time slots. The reason behind lies in the fact that in our proposed model, we take into the average response time into account and the deteriorating factor of the value grows exponentially, which also demonstrates the downward trends shown in Fig. 4. On the other hand, the weights are chosen randomly, there could be a balance between the increment and the decrement of the utilities. Hence, the aggregated requests in different time slots make little differences (Fig. 3).

Figures 6 and 7 present the average utility versus the increase of request aggregation and the number of users, respectively. Figure 6 illustrates the average utility results with the linear increment of request aggregation. We can observe that the average utility also linearly increases with the increase of request aggregation. No matter what the request aggregation is, the average utility obtained after our proposed IPA algorithm is better than that of the initial strategy profile. Moreover, the differences between the results before IPA algorithm and those after the algorithm are also increases. That is to say, our proposed IPA algorithm makes significant sense when the aggregated requests are somewhat large. Figure 7 shows the impacts of number of users. It can be seen that both of the results after IPA algorithm and before algorithm are inversely proportional to the number of uses. The reason behind lies in that the variation of number of users makes little impact on the average utility value when the request aggregation is fixed. Moreover, similar to the results presented in Fig. 6, the average utility obtained after IPA algorithm is always better than that of the initial strategy profile.

Fig. 6

Average utility vs. aggregation

Fig. 7

Average utility vs. number of users

4 A Framework of Price Bidding Configurations for Resource Usage in Cloud Computing

4.1 System Model and Problem Formulation

To begin with, we present our system model in the context of a service cloud provider with multiple cloud users, and establish some important results. In this paper, we are concerned with a market with a service cloud provider and n cloud users, who are competing for using the computing resources provided by the cloud provider. We denote the set of users as $\mathcal {N} = \left \{ {1, \ldots ,n} \right \}$. Each cloud user wants to bid for using some servers for several future time slots. The arrival requests from cloud user i ($i \in \mathcal {N}$) is assumed to follow a Poisson process. The cloud provider consists of multiple zones. In each zone, there are many homogeneous servers. In this paper, we focus on the price bidding for resource usage in a same zone and assume that the number of homogeneous servers in the zone is m. The cloud provider tries to allocate cloud user i ($i \in \mathcal {N}$) with m _i servers without violating the constraint $\sum \nolimits _{i \in \mathcal {N}} {{m_i}} \le m$. The allocated m _i servers for cloud user i ($i \in \mathcal {N}$) are modeled by an M/M/m queue, only serving the requests from user i for t _i future time slots. We summarize all the notations used in this sub-section in the notation table.

4.1.1 Bidding Strategy Model

As mentioned above, the n cloud users compete for using the m servers by bidding different strategies. Specifically, each cloud user responds by bidding with a per server usage price p _i (i.e., the payment to use one server in a time slot) and the number of time slots t _i to use cloud service. Hence, the bid of cloud user i ($i \in \mathcal {N}$) is an ordered pair ${b_i} = \left \langle {{p_i},{t_i}} \right \rangle$.

We assume that cloud user i ($i \in \mathcal {N}$) bids a price ${p_i} \in {\mathcal {P}_i}$, where ${\mathcal {P}_i} = \left [ { \underline {p},{{\bar p}_i}} \right ]$, with ${{{\bar p}_i}}$ denoting user i′s maximal possible bidding price. $\underline {p}$ is a conservative bidding price, which is determined by the cloud provider. If $\underline {p}$ is greater than ${\bar p_i}$, then $\mathcal {P}_i$ is empty and the cloud user i ($i \in \mathcal {N}$) refuses to use cloud service. As mentioned above, each cloud user i ($i \in \mathcal {N}$) bids for using some servers for t _i future time slots. In our work, we assume that the reserved time slots t _i is a constant once determined by the cloud user i. We define user i′s ($i \in \mathcal {N}$) request profile over the t _i future time slots as follow:

$$\displaystyle \begin{aligned} \boldsymbol{\lambda}_i^{{t_i}} = {\left( {\lambda _i^1, \ldots ,\lambda _i^{{t_i}}} \right)^T}, \end{aligned} $$

(39)

where $\lambda _i^t$ ($t \in \mathcal {T}_i$) with $\mathcal {T}_i = \{ 1, \dots , t_i\}$, is the arrival rate of requests from cloud user i in the t-th time slot. The arrival of the requests in different time slots of are assumed to follow a Poisson process.

4.1.2 Server Allocation Model

We consider a server allocation model motivated by [39, 40], where the allocated number of servers is proportional fairness. That is to say, the allocated share of servers is the ratio between the cloud user’s product value of his/her bidding price with reserved time slots and the summation of all product values from all cloud users. Then, each cloud user i ($i \in \mathcal {N}$) is allocated a portion of servers as

$$\displaystyle \begin{aligned} {m_i}\left( b_i, \boldsymbol{b}_{-i} \right) = \left\lfloor {\frac{{{p_i}{t_i}}}{{\sum\nolimits_{j \in \mathcal{N}} {{p_j}{t_j}} }} \cdot m} \right\rfloor, {} \end{aligned} $$

(40)

where ${\boldsymbol {b}_{ - i}} = \left ( {{b_1}, \ldots ,{b_{i - 1}},{b_{i + 1}}, \ldots ,{b_n}} \right )$ denotes the vector of all users’ bidding profile except that of user i, and $\left \lfloor x \right \rfloor$ denotes the greatest integer less than or equal to x. We design a server allocation model as Eq. (40) for two considerations. On one hand, if the reserved time slots to use cloud service t _i is large, the cloud provider can charge less for one server in a unit of time to appeal more cloud users, i.e., the bidding price p _i can be smaller. In addition, for the cloud user i ($i \in \mathcal {N}$), he/she may be allocated more servers, which can improve his/her service time utility. On the other hand, if the bidding price p _i is large, this means that the cloud user i ($i \in \mathcal {N}$) wants to pay more for per server usage in a unit of time to allocate more servers, which can also improve his/her service time utility. This is also beneficial to the cloud provider due to the higher charge for each server. Therefore, we design a server allocation model as Eq. (40), which is proportional to the product of p _i and t _i.

4.1.3 Cloud Service Model

As mentioned in the beginning, the allocated m _i servers for cloud user i ($i \in \mathcal {N}$) are modeled as an M/M/m queue, only serving the requests from cloud user i for t _i future time slots. The processing capacity of each server for requests from cloud user i ($i \in \mathcal {N}$) is presented by its service rate μ _i. The requests from cloud user i ($i \in \mathcal {N}$) in t-th ($t \in \mathcal {T}_i$) time slot are assumed to follow a Poisson process with average arrival rate $\lambda _i^t$.

Let $\pi _{ik}^t$ be the probability that there are k service requests (waiting or being processed) in the t-th time slot and be the corresponding service utilization in the M/M/m queuing system. With reference to [7], we obtain

$$\displaystyle \begin{aligned} \pi_{ik}^t = \begin{cases} {\frac{1}{{k!}}{{\left( {{m_i}{\rho _i^t}} \right)}^k}{\pi_{i0}^t}}, & k < m_i; \\ {\frac{{m_i^{{m_i}}\left(\rho _i^t\right)^k}}{{{m_i}!}}{\pi_{i0}^t}}, & k \ge m_i; \\ \end{cases} {} \end{aligned} $$

(41)

where

$$\displaystyle \begin{aligned} {\pi_{i0}^t} = {\left\{ {\sum_{l = 0}^{{m_i} - 1} {\frac{1}{{l!}}{{\left( {{m_i}{\rho _i^t}} \right)}^l}} + \frac{1}{{{m_i}!}} \cdot \frac{{{{\left( {{m_i}{\rho _i^t}} \right)}^{{m_i}}}}}{{1 - {\rho _i^t}}}} \right\}^{ - 1}}. \end{aligned} $$

(42)

The average number of service requests (in waiting or in execution) in t-th time slot is

$$\displaystyle \begin{aligned} {\bar N_i^t} = \sum_{k = 0}^\infty {k{\pi_{ik}^t}} = \frac{{{\pi_{i{m_i}}^t}}}{{1 - {\rho _i^t}}} = {m_i}{\rho _i^t} + \frac{{{\rho _i^t}}}{{1 - {\rho _i^t}}}{\Pi_{i}^t}, \end{aligned} $$

(43)

where $\Pi _{i}^t$ represents the probability that the incoming requests from cloud user i ($i \in \mathcal {N}$) need to wait in queue in the t-th time slot.

Applying Little’s result, we get the average response time in the t-th time slot as

$$\displaystyle \begin{aligned} {\bar T_i^t} = \frac{{{{\bar N}_i^t}}}{{{\lambda _i^t}}} = \frac{1}{{{\lambda _i^t}}}\left( {{m_i}{\rho _i^t} + \frac{{{\rho _i^t}}}{{1 - {\rho _i^t}}}{\Pi_{i}^t}} \right). \end{aligned} $$

(44)

In this work, we assume that the allocated servers for each cloud user will likely keep busy, because if no so, a user can bid lower price to obtain less servers such that the computing resources can be fully utilized. For analytical tractability, $\Pi _{i}^t$ is assumed to be 1. Therefore, we have

$$\displaystyle \begin{aligned} \bar T_i^t = \frac{{\bar N_i^t}}{\lambda _i^t} = \frac{1}{{{\lambda _i^t}}}\left( {{m_i}{\rho _i^t} + \frac{{{\rho _i^t}}}{{1 - {\rho _i^t}}}} \right) = \frac{1}{{{\mu _i}}} + \frac{1}{{{m_i}{\mu _i} - {\lambda _i^t}}}. \end{aligned} $$

(45)

Note that the request arrival rate from a user should never exceed the total processing capacity of the allocated servers. In our work, we assume that the remaining processing capacity for serving user i ($i \in \mathcal {N}$) is at least σμ _i, where σ is a relative small positive constant. That is, if $\lambda _i^t > (m_i-\sigma )\mu _i$, cloud user i ($i \in \mathcal {N}$) should reduce his/her request arrival rate to (m _i − σ)μ _i. Otherwise, server crash would be occurred. Hence, we have

$$\displaystyle \begin{aligned} \bar T_i^t = \frac{1}{{{\mu _i}}} + \frac{1}{{{m_i}{\mu _i} - \chi _i^t}}, {} \end{aligned} $$

(46)

where $\chi _i^t$ is the minimum value of $\lambda _i^t$ and $\left ( {{m_i} {-} \sigma } \right ){\mu _i}$, i.e., $\chi _i^t {=} \min \!\left \{ {\lambda _i^t,\left ( {{m_i} {-} \sigma } \right ){\mu _i}} \right \}$.

4.1.4 Architecture Model

In this subsection, we model the architecture of our proposed framework to price bids for resource usage in cloud computing. The multiple users can make appropriate bidding decisions through the information exchange module. As shown in Fig. 8, each cloud user i ($i \in \mathcal {N}$) is equipped with a utility function (u _i), the request arrival rate over reserved time slots ($\boldsymbol {\lambda }_i^{t_i}$), and the bidding configuration (b _i), i.e., the payment strategy for one server in a unit of time and the reserved time slots. Let $\Xi _{\mathcal {N}}$ be the aggregated payment from all cloud users for using a server, then we have $\Xi _{\mathcal {N}} = \sum \limits _{i = 1}^n {{p_i}{t_i}}$. Denote ${\boldsymbol {m}} = {\left ( {{m_i}} \right )_{i \in \mathcal {N}}}$ as the server allocation vector, ${\boldsymbol {b}} = {\left ( {{b_i}} \right )_{i \in \mathcal {N}}}$ as the corresponding bids, and ${\boldsymbol {u}} = {\left ( {{u_i}} \right )_{i \in \mathcal {N}}}$ as the utility functions of all cloud users. The cloud provider consists of m homogeneous servers and communicates some information (e.g., conservative bidding price $\underline {p}$, current aggregated payment from all cloud users for using a server ${\Xi _{\mathcal {N}}}$) with multiple users through the information exchange module. When multiple users try to make price bidding strategies for resource usage in the cloud provider, they first get information from the information exchange module, then configure proper bidding strategies (b) such that their own utilities (u) are maximized. After this, they send the updated strategies to the cloud provider. The procedure is terminated when the set of remaining cloud users, who prefer to use the cloud service, and their corresponding bidding strategies are kept fixed.

Fig. 8

Architecture model

4.1.5 Problem Formulation

Now, let us consider user i′s ($i \in \mathcal {N}$) utility in time slot t ($t \in \mathcal {T}_i$). A rational cloud user will seek a bidding strategy to maximize his/her expected net reward by finishing the requests, i.e., the benefit obtained by choosing the cloud service minus his/her payment. Since all cloud users are charged based on their bidding prices and allocated number of servers, we denote the cloud user i′s payment in time slot t by $P_i^t\left ( b_i, \boldsymbol {b}_{-i} \right )$, where $P_i^t \left ( b_i, \boldsymbol {b}_{-i} \right ) = p_im_i\left ( b_i, \boldsymbol {b}_{-i} \right )$ with ${\boldsymbol {b}_{ - i}} = \left ( {{b_1}, \ldots ,{b_{i - 1}},{b_{i + 1}}, \ldots ,{b_n}} \right )$ denoting the vector of all users’ bidding profile except that of user i. Denote $P_T\left (b_i, \boldsymbol {b}_{-i} \right )$ as the aggregated payment from all cloud users, i.e., the revenue of the cloud provider. Then, we have

$$\displaystyle \begin{aligned} {P_T} \left( b_i, \boldsymbol{b}_{-i} \right) = \sum_{i = 1}^n {\sum_{t = 1}^{{t_i}} {P_i^t}\left( b_i, \boldsymbol{b}_{-i} \right) } = \sum_{i = 1}^n \left({{p_i}{m_i}\left( b_i, \boldsymbol{b}_{-i} \right){t_i}}\right). \end{aligned} $$

(47)

On the other hand, since a user will be more satisfied with much faster service, we also take the average response time into account. From Eq. (46), we know that the average response time of user i ($i \in \mathcal {N}$) is impacted by m _i and $\chi _i^t$, where $\chi _i^t = \min \left \{ {\lambda _i^t,\left ( {{m_i} - \sigma } \right ){\mu _i}} \right \}$. The former is varied by (b _i, b _−i), and the latter is determined by $\lambda _i^t$ and m _i. Hence, we denote the average response time of user i as $\bar T_i^t \left (b_i, \boldsymbol {b}_{-i}, \lambda _i^t \right )$. More formally, the utility of user i ($i \in \mathcal {N}$) in time slot t is defined as

$$\displaystyle \begin{aligned} u_i^t\left( {{b_i},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right) = {r_i}{\chi _{i}^t} - \delta_i P_i^t\left( {{b_i},{\boldsymbol{b}_{ - i}}} \right) - {w_i}\bar T_i^t\left( {{b_i},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right), \end{aligned} $$

(48)

where $\chi _i^t$ is the minimum value of $\lambda _i^t$ and $\left ( {{m_i}\left ( b_i, \boldsymbol {b}_{-i} \right )- \sigma } \right ){\mu _i}$, i.e., $\chi _i^t = \min \left \{ {\lambda _i^t,\left ( {{m_i}\left ( b_i, \boldsymbol {b}_{-i} \right ) - \sigma } \right ){\mu _i}} \right \}$ with σ denoting a relative small positive constant, r _i (r _i > 0) is the benefit factor (the reward obtained by finishing one task request) of user i, δ _i (δ _i > 0) is the payment cost factor, and w _i (w _i > 0) is the waiting cost factor, which reflects its urgency. If a user i ($i \in \mathcal {N}$) is more concerned with service time utility, then the associated waiting factor w _i might be larger. Otherwise, w _i might be smaller, which implies that the user i is more concerned with profit.

Since the reserved server usage time t _i is a constant and known to cloud user i ($i \in \mathcal {N}$), we use $u_i^t\left ( {{p_i},{\boldsymbol {b}_{ - i}},\lambda _i^t} \right )$ instead of $u_i^t\left ( {{b_i},{\boldsymbol {b}_{ - i}},\lambda _i^t} \right )$. For further simplicity, we use $P_i^t$ and $\bar T_i^t$ to denote $P_i^t\left ( {{b_i},{\boldsymbol {b}_{ - i}}} \right )$ and $T_i^t\left ( {{b_i},{\boldsymbol {b}_{ - i}},\lambda _i^t} \right )$, respectively. Following the adopted bidding model, the total utility obtained by user i ($i \in \mathcal {N}$) over all t _i time slots can thus be given by

$$\displaystyle \begin{aligned} {u_i}\left( {{p_i},{\boldsymbol{b}_{ - i}},\boldsymbol{\lambda} _i^{{t_i}}} \right) & = \sum_{t = 1}^{{t_i}} {u_i^t\left( {{p_i},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right)} \\ & = \sum_{t = 1}^{{t_i}} {\left( {{r_i}{\chi _{i}^t} - P_i^t - {w_i}\bar T_i^t} \right)}. {} \end{aligned} $$

(49)

In our work, we assume that each user i ($i \in \mathcal {N}$) has a reservation value v _i. That is to say, cloud user i will prefer to use the cloud service if ${u_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right ) \ge v_i$ and refuse to use the cloud service otherwise.

We consider the scenario where all users are selfish. Specifically, each cloud user tries to maximize his/her total utility over the t _i future time slots, i.e., each cloud user i ($i \in \mathcal {N}$) tries to find a solution to the following optimization problem (OPT_i):

$$\displaystyle \begin{aligned} \mbox{maximize} \ \ {u_i}\left( {{p_i},{\boldsymbol{b}_{ - i}},\boldsymbol{\lambda} _i^{{t_i}}} \right), \ {p_i} \in {\mathcal{P}_i}. \end{aligned} $$

(50)

Remark 4.1

In finding the solution to (OPT_i), the bidding strategies of all other users are kept fixed. In addition, the number of reserved time slots once determined by a user is constant. So the variable in (OPT_i) is the bidding price of cloud user i, i.e., p _i.

4.2 Game Formulation and Analyses

In this section, we formulated the considered scenario into a non-cooperative game among the multiple cloud users. By relaxing the condition that the allocated number of servers for each user can be fractional, we analyze the existence of a Nash equilibrium solution set for the formulated game. We also propose an iterative algorithm to compute a Nash equilibrium and then analyze its convergence. Finally, we revise the obtained Nash equilibrium solution and propose an algorithm to characterize the whole process of the framework.

4.2.1 Game Formulation

Game theory studies the problems in which players try to maximize their utilities or minimize their disutilities. As described in [5], a non-cooperative game consists of a set of players, a set of strategies, and preferences over the set of strategies. In this paper, each cloud user is regarded as a player, i.e., the set of players is the n cloud users. The strategy set of player i ($i \in \mathcal {N}$) is the price bidding set of user i, i.e., $\mathcal {P}_i$. Then the joint strategy set of all players is given by $\mathcal {P} = {\mathcal {P}_1} \times \cdots \times {\mathcal {P}_n}$.

As mentioned before, all users are considered to be selfish and each user i ($i \in \mathcal {N}$) tries to maximize his/her own utility or minimize his/her disutility while ignoring those of the others. Denote

$$\displaystyle \begin{aligned} {\psi _i^t\left( {{p_i},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right)} = { \delta_i{P_i^t + {w_i}T_i^t - {r_i}{\chi _{it}}} }. \end{aligned} $$

(51)

In view of (49), we can observe that user i′s optimization problem (OPT_i) is equivalent to

$$\displaystyle \begin{aligned} \mbox{minimize} \quad &{f_i}\left( {{p_i},{\boldsymbol{b}_{ - i}},\boldsymbol{\lambda} _i^{{t_i}}} \right) = \sum_{t = 1}^{{t_i}} {\psi _i^t\left( {{p_i},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right)}, \\ \mbox{s.t.} \quad &\left( {{p_i},{\boldsymbol{p}_{ - i}}} \right) \in \mathcal{P}. {} \end{aligned} $$

(52)

The above formulated game can be formally defined by the tuple $G = \left \langle {\mathcal {P},{\boldsymbol {f}}} \right \rangle$, where ${\boldsymbol {f}} = \left ( {{f _1}, \ldots ,{f _n}} \right )$. The aim of cloud user i ($i \in \mathcal {N}$), given the other players’ bidding strategies b _−i, is to choose a bidding price ${p_i} \in {\mathcal {P}_i}$ such that his/her disutility function ${f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right )$ is minimized.

Definition 4.1 (Nash equilibrium)

A Nash equilibrium of the formulated game $G = \left \langle {\mathcal {P},{\boldsymbol {f}}} \right \rangle$ defined above is a price bidding profile p ^∗ such that for every player i ($i \in \mathcal {N}$):

$$\displaystyle \begin{aligned} p_i^\ast \in \mathop {\arg \min }\limits_{{p_i} \in {\mathcal{P}_i}} {f_i}\left( {{p_i},{\boldsymbol{b}_{ - i}},\boldsymbol{\lambda} _i^{{t_i}}} \right), \ {{\boldsymbol{p}}^{\ast}} \in \mathcal{P}. \end{aligned} $$

(53)

At the Nash equilibrium, each player cannot further decrease its disutility by choosing a different price bidding strategy while the strategies of other players are fixed. The equilibrium strategy profile can be found when each player’s strategy is the best response to the strategies of other players.

4.2.2 Nash Equilibrium Existence Analysis

In this subsection, we analyze the existence of Nash equilibrium for the formulated game $G = \left \langle {\mathcal {P},\boldsymbol {f} } \right \rangle$ by relaxing one condition that the allocated number of servers for each user can be fractional. Before addressing the equilibrium existence analysis, we show two properties presented in Theorems 4.1 and 4.2, which are helpful to prove the existence of Nash equilibrium for the formulated game.

Theorem 4.1

Given a fixed b _−i and assuming that ( $i \in \mathcal {N}$), then each of the functions $\psi _i^t\left ( {{p_i},{\boldsymbol {b}_{ - i}},\lambda _i^t} \right )$ ( $t_i \in \mathcal {T}_i$) is convex in $p_i \in \mathcal {P}_i$.

Proof

Obviously, $\psi _i^t\left ( {{p_i},{\boldsymbol {b}_{ - i}},\lambda _i^t} \right )$ ($t \in \mathcal {T}_i$) is a real continuous function defined on $\mathcal {P}_i$. The proof of this theorem follows if we can show that $\forall {p_{(1)}},{p_{(2)}} \in {\mathcal {P}_i}$,

$$\displaystyle \begin{aligned} & \psi _i^t\left( {\theta {p_{(1)}} + \left( {1 - \theta } \right){p_{(2)}},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right) \le \theta \psi _i^t\left( {{p_{(1)}},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right) + \left( {1 - \theta } \right)\psi _i^t\left( {{p_{(2)}},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right), \end{aligned} $$

where 0 < θ < 1.

Notice that, $\psi _i^t\left ( {{p_i},{\boldsymbol {b}_{ - i}},\lambda _i^t} \right )$ is a piecewise function and the breakpoint satisfies $\left ( {{m_i} - \sigma } \right ){\mu _i} = \lambda _i^t$. Then, we obtain the breakpoint as

$$\displaystyle \begin{aligned} p_i^t = \frac{{{m_i}{\Xi _{{\Xi _{\mathcal{N}\backslash \{ i\} }}}}}}{{\left( {m - {m_i}} \right){t_i}}} = \frac{{\left( {\lambda _i^t + \sigma {\mu _i}} \right){{\Xi _{\mathcal{N}\backslash \{ i\} }}}}}{{\left( {\left( {m - \sigma } \right){\mu _i} - \lambda _i^t} \right){t_i}}}, \end{aligned}$$

where ${\Xi _{\mathcal {N}\backslash \{ i\} }}$ denotes the aggregated payment from all cloud users in $\mathcal {N}$ except of user i, i.e., ${\Xi _{\mathcal {N}\backslash \{ i\} }} = \sum \nolimits _{j \in \mathcal {N}, j \ne i} {{p_i}{t_i}}$. Next, we discuss the convexity of the function $\psi _i^t\left ( {{p_i},{\boldsymbol {b}_{ - i}},\lambda _i^t} \right )$.

Since

$$\displaystyle \begin{aligned} \psi _i^t\left( {{p_i},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right) = \delta_iP_i^t + {w_i}\bar T_i^t - {r_i}\chi _i^t, \end{aligned} $$

where $\chi _i^t = \min \left \{ {\left ( {{m_i} - \sigma } \right ){\mu _i},\lambda _i^t} \right \}$, we have

$$\displaystyle \begin{aligned} \frac{{\partial \psi _i^t}}{{\partial {p_i}}}\left( {{p_i},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right) = \delta_i\frac{{\partial P_i^t}}{{\partial {p_i}}} + {w_i}\frac{{\partial \bar T_i^t}}{{\partial {p_i}}} - {r_i}\frac{{\partial \chi _i^t}}{{\partial {p_i}}}. \end{aligned} $$

On the other hand, since $\frac {{\partial \bar T_i^t}}{{\partial {p_i}}} = 0$ for ${p_i} \in \left [ { \underline {p},p_i^t} \right )$ and $\frac {{\partial \chi _i^t}}{{\partial {p_i}}} = 0$ for ${p_i} \in \left ( {p_i^t,{{\bar p}_i}} \right ]$, we obtain

$$\displaystyle \begin{aligned} & \frac{\partial }{{\partial {p_{i}}}}\varphi _i^t\left( {{p_i},{\boldsymbol{b}_{ - i}},\lambda _i^{{t}}} \right) = \begin{cases} {\delta_i\frac{{\partial P_i^t}}{{\partial {p_i}}} - {r_i}\frac{{\partial \chi _i^t}}{{\partial {p_i}}}}, & p_i < p_i^t; \\ {\delta_i\frac{{\partial P_i^t}}{{\partial {p_i}}} + {w_i}\frac{{\partial \bar T_i^t}}{{\partial {p_i}}}}, & p_i > p_i^t. \\ \end{cases} \end{aligned} $$

Namely,

$$\displaystyle \begin{aligned} \frac{\partial }{{\partial {p_{i}}}}\varphi _i^t\left( {{p_i},{\boldsymbol{b}_{ - i}},\lambda _i^{{t}}} \right) = \begin{cases} {\delta_i\left( {\frac{{m{p_i}{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{\Xi_{\mathcal{N}}^2}}} + {m_i}} \right) - \frac{{m{r_i}{\mu _i}{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{\Xi_{\mathcal{N}}^2}}}}, & p_i < p_i^t; \\ {\delta_i\left( {\frac{{m{p_i}{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{\Xi_{\mathcal{N}}^2}}} + {m_i}} \right) - \frac{{m{w_i}{\mu _i}{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{{\left( {{m_i}{\mu _i} - \lambda _i^t} \right)}^2}{\Xi_{\mathcal{N}} ^2}}}}, & p_i > p_i^t, \\ \end{cases} \end{aligned} $$

where

$$\displaystyle \begin{aligned} \Xi_{\mathcal{N}} = {\Xi _{\mathcal{N}\backslash \{ i\} }} + p_it_i = \sum\nolimits_{j \in \mathcal{N}} {{p_j}{t_j}}. \end{aligned} $$

We can further obtain

$$\displaystyle \begin{aligned} & \frac{{{\partial ^2}}}{{\partial p_i^2}}\psi _i^t\left( {{p_i},{\boldsymbol{b}_{ - i}},\lambda _i^{{t}}} \right) = \begin{cases} {\frac{{2m{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{\Xi_{\mathcal{N}} ^2}}}\left( {\frac{{\left( {{r_i}{\mu _i} - {p_i}} \right){t_i}}}{\Xi_{\mathcal{N}} } + 1} \right)}, & p_i < p_i^t; \\ {\frac{{2m{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{\Xi_{\mathcal{N}} ^2}}}\left( {1 - \frac{{{p_i}{t_i}}}{\Xi_{\mathcal{N}} }} \right) + } \\ \quad {\frac{{2m{w_i}{\mu _i}t_i^2{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{{\left( {{m_i}{\mu _i} - \lambda _i^t} \right)}^2}{\Xi_{\mathcal{N}}^3}}}\left( {\frac{{{\mu _i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{\left( {{m_i}{\mu _i} - \lambda _i^t} \right)\Xi_{\mathcal{N}} }} + 1} \right)}, & p_i > p_i^t. \\ \end{cases} \end{aligned} $$

Obviously,

$$\displaystyle \begin{aligned} \frac{{{\partial ^2}}}{{\partial p_i^2}}\psi _i^t\left( {{p_i},{\boldsymbol{b}_{ - i}},\lambda _i^{{t}}} \right) > 0, \end{aligned} $$

for all ${p_i} \in \left [ { \underline {p},p_i^t} \right )$ and ${p_i} \in \left ( {p_i^t,{{\bar p}_i}} \right ]$. Therefore, $\forall {p_{(1)}},{p_{(2)}} \in \left [ { \underline {p},p_i^t} \right )$ or $\forall {p_{(1)}},{p_{(2)}} \in \left ( {p_i^t,{{\bar p}_i}} \right ]$,

$$\displaystyle \begin{aligned} & \psi _i^t\left( {\theta {p_{(1)}} + \left( {1 - \theta } \right){p_{(2)}},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right) \\ & \qquad \le \theta \psi _i^t\left( {{p_{(1)}},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right) + \left( {1 - \theta } \right)\psi _i^t\left( {{p_{(2)}},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right), \end{aligned} $$

where 0 < θ < 1.

Next, we focus on the situation where ${p_{(1)}} \in \left [ { \underline {p},p_i^t} \right )$ and ${p_{(2)}} \in \left ( {p_i^t,{{\bar p}_i}} \right ]$. Since $\psi _i^t\left ( {{p_i},\boldsymbol {b}_i,\lambda _i^t} \right )$ is convex on $\left [ { \underline {p},p_i^t} \right )$ and $\left ( {p_i^t,{{\bar p}_i}} \right ]$, respectively. We only need to prove that the value of $\psi _i^t\left ( {p_i^t,\boldsymbol {b}_i ,\lambda _i^t} \right )$ is less than that of in the linear function value connected by the point in ${p_{\left ( 1 \right )}}$ and the point in ${p_{\left ( 2 \right )}}$, i.e.,

$$\displaystyle \begin{aligned} \psi _i^t\left( {p_i^t,\boldsymbol{b}_i ,\lambda _i^t} \right) \le \theta _i^t\psi _i^t\left( {{p_{(1)}},\boldsymbol{b}_i ,\lambda _i^t} \right) + \left( {1 - \theta _i^t} \right)\psi _i^t\left( {{p_{(2)}},\boldsymbol{b}_i ,\lambda _i^t} \right), \end{aligned} $$

where $\theta _i^t = \frac {{{p_{(2)}} - p_i^t}}{{{p_{(2)}} - {p_{(1)}}}}$. We proceed as follows (see Fig. 9).

Fig. 9

An illustration

Define a function $g_i^t\left ( {{p_i},\boldsymbol {b}_i ,\lambda _i^t} \right )$ on $p_i \in \mathcal {P}_i$, where

$$\displaystyle \begin{aligned} g_i^t\left( {{p_i},\boldsymbol{b}_i ,\lambda _i^t} \right) = \delta_i{p_i}{m_i} + \frac{{{w_i}\left( {\sigma + 1} \right)}}{{\sigma {\mu _i}}} - {r_i}\left( {{m_i} - \sigma } \right){\mu _i}. \end{aligned} $$

We have

$$\displaystyle \begin{aligned} \psi _i^t\left( {p_i,\boldsymbol{b}_i ,\lambda _i^t} \right) = g_i^t\left( {p_i,\boldsymbol{b}_i ,\lambda _i^t} \right), \end{aligned} $$

for all $\underline {p} \le {p_i} \le p_i^t$. If , then

$$\displaystyle \begin{aligned} & \frac{\partial }{{\partial {p_i}}}g_i^t\left( {{p_i},\boldsymbol{b}_i ,\lambda _i^t} \right) \\ & \qquad \quad = \delta_i\left( {\frac{{m{p_i}{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{\Xi_{\mathcal{N}}^2}}} + {m_i}} \right) - \frac{{m{r_i}{\mu _i}{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{\Xi_{\mathcal{N}}^2}}} \\ & \qquad \quad \le \delta_i\left( {\frac{{m{p_i}{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{\Xi_{\mathcal{N}}^2}}} + {m_i}} \right) - \frac{{m{w_i}{\mu _i}{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{{\left( {{m_i}{\mu _i} - \lambda _i^t} \right)}^2}{\Xi_{\mathcal{N}}^2}}} \\ & \qquad \quad = \frac{\partial }{{\partial {p_i}}}\psi _i^t\left( {{p_i},\boldsymbol{b}_i ,\lambda _i^t} \right), \end{aligned} $$

for all $p_i^t < {p_i} \le {\bar p_i}$. We have

$$\displaystyle \begin{aligned} \psi _i^t\left( {{p_i},\boldsymbol{b}_i ,\lambda _i^t} \right) \ge g_i^t\left( {{p_i},\boldsymbol{b}_i ,\lambda _i^t} \right), \end{aligned} $$

for all $p_i^t < {p_i} \le {\bar p_i}$.

On the other hand, according to the earlier derivation, we know that

$$\displaystyle \begin{aligned} \frac{{{\partial ^2}}}{{\partial p_i^2}}g_i^t\left( {{p_i},\boldsymbol{b}_i ,\lambda _i^t} \right) > 0, \end{aligned} $$

for all $p_i \in \mathcal {P}_i$. That is, $g_i^t\left ( {{p_i},\boldsymbol {b}_i ,\lambda _i^t} \right )$ is a convex function on $\mathcal {P}_i$, and we obtain

$$\displaystyle \begin{aligned} & \psi _i^t\left( {p_i^t,\boldsymbol{b}_i ,\lambda _i^t} \right) \\ & \qquad \le \theta _i^tg_i^t\left( {{p_{(1)}},\boldsymbol{b}_i ,\lambda _i^t} \right) + \left( {1 - \theta _i^t} \right)g_i^t\left( {{p_{(2)}},\boldsymbol{b}_i ,\lambda _i^t} \right) \\ & \qquad = \theta _i^t\psi _i^t\left( {{p_{(1)}},\boldsymbol{b}_i ,\lambda _i^t} \right) + \left( {1 - \theta _i^t} \right)g_i^t\left( {{p_{(2)}},\boldsymbol{b}_i ,\lambda _i^t} \right) \\ & \qquad \le \theta _i^t\psi _i^t\left( {{p_{(1)}},\boldsymbol{b}_i ,\lambda _i^t} \right) + \left( {1 - \theta _i^t} \right)\psi _i^t\left( {{p_{(2)}},\boldsymbol{b}_i ,\lambda _i^t} \right). \end{aligned} $$

Thus, we have $\psi _i^t\left ( {{p_{i}},{\boldsymbol {b}_{ - i}},\lambda _i^t} \right )$ is convex on $p_i \in \mathcal {P}_i$. This completes the proof and the result follows. □

Theorem 4.2

If both functions ${\mathcal {K}_1}\left ( x \right )$ and ${\mathcal {K}_2}\left ( x \right )$ are convex in $x \in \mathcal {X}$, then the function ${\mathcal {K}_3}\left ( x \right ) = {\mathcal {K}_1}\left ( x \right ) + {\mathcal {K}_2}\left ( x \right )$ is also convex in $x \in \mathcal {X}$.

Proof

As mentioned above, both of the functions ${\mathcal {K}_1}\left ( x \right )$ and ${\mathcal {K}_2}\left ( x \right )$ are convex in $x \in \mathcal {X}$. Then we have $\forall {x_1},{x_2} \in \mathcal {X}$,

$$\displaystyle \begin{aligned} {\mathcal{K}_1}\left( {\theta {x_1} + \left( {1 - \theta } \right){x_2}} \right) \le \theta {\mathcal{K}_1}\left( {{x_1}} \right) + \left( {1 - \theta } \right){\mathcal{K}_1}\left( {{x_2}} \right), \end{aligned} $$

and

$$\displaystyle \begin{aligned} {\mathcal{K}_2}\left( {\theta {x_1} + \left( {1 - \theta } \right){x_2}} \right) \le \theta {\mathcal{K}_2}\left( {{x_1}} \right) + \left( {1 - \theta } \right){\mathcal{K}_2}\left( {{x_2}} \right), \end{aligned} $$

where 0 < θ < 1. We further obtain $\forall {x_1},{x_2} \in \mathcal {X}$,

$$\displaystyle \begin{aligned} & {\mathcal{K}_3}\left( {\theta {x_1} + \left( {1 - \theta } \right){x_2}} \right) \\ & \qquad = {\mathcal{K}_1}\left( {\theta {x_1} + \left( {1 - \theta } \right){x_2}} \right) + {\mathcal{K}_2}\left( {\theta {x_1} + \left( {1 - \theta } \right){x_2}} \right) \\ & \qquad \le \theta \left( {{\mathcal{K}_1}\left( {{x_1}} \right) + {\mathcal{K}_2}\left( {{x_1}} \right)} \right) + \left( {1 - \theta } \right)\left( {{\mathcal{K}_1}\left( {{x_2}} \right) + {\mathcal{K}_2}\left( {{x_2}} \right)} \right) \\ & \qquad = \theta {\mathcal{K}_3}\left( {{x_1}} \right) + \left( {1 - \theta } \right){\mathcal{K}_3}\left( {{x_2}} \right). \end{aligned} $$

Thus, we can conclude that $\mathcal {K}_3\left ( x \right )$ is also convex in $x \in \mathcal {X}$ and the result follows. □

Theorem 4.3

There exists a Nash equilibrium solution set for the formulated game $G = \left \langle {\mathcal {P},\boldsymbol {f} } \right \rangle$ , given that the condition ( $i \in \mathcal {N}$ ) holds.

Proof

According to [12, 20], the proof of this theorem follows if the following two conditions are satisfied. (1) For each cloud user i ($i \in \mathcal {N}$), the set $\mathcal {P}_i$ is convex and compact, and each disutility function ${f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right )$ is continuous in $p_i \in \mathcal {P}_i$. (2) For each fixed tuple b _−i, the function ${f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right )$ is convex in p _i over the set $\mathcal {P}_i$.

It is obvious that the statements in the first part hold. We only need to prove the convexity of ${f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right )$ in p _i for every fixed b _−i. By Theorem 4.1, we know that if ($i \in \mathcal {N}$), then each of the functions $\psi _i^t\left ( {{p_i},{\boldsymbol {b}_{ - i}},\lambda _i^t} \right )$ ($t \in \mathcal {T}_i$) is convex in $p_i \in \mathcal {P}_i$. In addition, according to the property presented in Theorem 4.2, it is easy to deduce that

$$\displaystyle \begin{aligned} {f_i}\left( {{p_i},{\boldsymbol{b}_{ - i}},\boldsymbol{\lambda} _i^{{t_i}}} \right) = \sum_{t = 1}^{{t_i}} {\psi _i^t\left( {{p_i},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right)}, \end{aligned}$$

is also convex in $p_i \in \mathcal {P}_i$. Thus, the result follows. □

4.2.3 Nash Equilibrium Computation

Once we have established that the Nash equilibrium of the formulated game $G = \left \langle {\mathcal {P},\boldsymbol {f}} \right \rangle$ exists, we are interested in obtaining a suitable algorithm to compute one of these equilibriums with minimum information exchange between the multiple users and the cloud providers.

Note that we can further rewrite the optimization problem (52) as follows:

$$\displaystyle \begin{aligned} \mbox{minimize} \quad & {f_i}\left( {{p_i},\Xi_{\mathcal{N}},\boldsymbol{\lambda} _i^{{t_i}}} \right) = \sum_{t = 1}^{{t_i}} {\psi _i^t\left( {{p_i},\Xi_{\mathcal{N}},\lambda _i^t} \right)}, \\ \mbox{s.t.} \quad & \left( {{p_i},{\boldsymbol{p}_{ - i}}} \right) \in \mathcal{P}, {} \end{aligned} $$

(54)

where $\Xi _{\mathcal {N}}$ denotes the aggregated payments for each server from all cloud users, i.e., $\Xi _{\mathcal {N}} = \sum \nolimits _{j \in \mathcal {N}} {{p_j}{t_j}}$. From (54), we can observe that the calculation of the disutility function of each individual user only requires the knowledge of the aggregated payments for a server from all cloud users ($\Xi _{\mathcal {N}}$) rather than that the specific individual bidding strategy profile (b _−i), which can bring about two advantages. On the one hand, it can reduce communication traffic between users and the cloud provider. On the other hand, it can also keep privacy for each individual user to certain extent, which is seriously considered by many cloud users.

Since all users are considered to be selfish and try to minimize their own disutility while ignoring those of the others. It is natural to consider an iterative algorithm where, at every iteration k, each individual user i ($i \in \mathcal {N}$) updates his/her price bidding strategy to minimize his/her own disutility function ${f_i}\left ( {{p_i},\Xi _{\mathcal {N}} ,\boldsymbol {\lambda } _i^{{t_i}}} \right )$. The idea is formalized in Algorithm 1.

Algorithm 4 ℐterative Algorithm (ℐA)

Given $\mathcal {S}$, $\boldsymbol {\lambda }_{\mathcal {S}}$, and 𝜖, where $\mathcal {S}$ is the set of cloud users who want to use the cloud service, $\boldsymbol {\lambda }_{\mathcal {S}}$ is the request vector of all cloud users in $\mathcal {S}$, i.e., ${\boldsymbol {\lambda } _{\mathcal {S}}} = {\left \{ {\boldsymbol {\lambda } _i^{{t_i}}} \right \}_{i \in \mathcal {S}}}$, and 𝜖 is a relative small constant. The iterative algorithm ($\mathcal {I}\mathcal {A}$) finds optimal bidding prices for all cloud users in $\mathcal {S}$. At the beginning of the iterations, the bidding price of each cloud user is set as the conservative bidding price ($\underline {p}$). We use a variable k to index each of the iterations, which is initialized as zero. At the beginning of the iteration k, each of the cloud users i ($i \in \mathcal {N}$) receives the value $\Xi _{\mathcal {S}}^{(k)}$ from the cloud provider and computes his/her optimal bidding price such that his/her own disutility function $f_i\left ( p_i, \Xi _{\mathcal {S}}^{(k)}, \boldsymbol {\lambda }_i^{t_i} \right )$ ($i \in \mathcal {S}$) is minimized. Then, each of the cloud users in $\mathcal {S}$ updates their price bidding strategy and sends the updated value to the cloud provider. The algorithm terminates when the price bidding strategies of all cloud users in $\mathcal {S}$ are kept unchanged, i.e., $\left \|{\boldsymbol {p}_{\mathcal {S}}^{(k)} - \boldsymbol {p}_{\mathcal {S}}^{(k - 1)}} \right \| \le \epsilon$.

In subsequent analyses, we show that the above algorithm always converges to a Nash equilibrium if one condition is satisfied for each cloud user. If so, we have an algorithmic tool to compute a Nash equilibrium solution. Before addressing the convergency problem, we first present a property presented in Theorem 4.4, which is helpful to derive the convergence result.

Theorem 4.4

If ${r_i} > \max \left \{ {\frac {{2{\delta _i}{{\bar p}_i}}}{{{\mu _i}}},\frac {{{w_i}}}{{{\sigma ^2}\mu _i^2}}} \right \}$ ( $i \in \mathcal {N}$), then the optimal bidding price $p_i^\ast$ ( $p_i^\ast \in \mathcal {P}_i$) of cloud user i ( $i \in \mathcal {N}$) is a non-decreasing function with respect to ${\Xi _{\mathcal {N}\backslash \{ i\} }}$, where ${\Xi _{\mathcal {N}\backslash \{ i\} }} = \sum \nolimits _{j \in \mathcal {N}} {{p_j}{t_j}} - {p_i}{t_i}$.

Proof

According to the results in Theorem 4.1 we know that for each cloud user i ($i \in \mathcal {N}$), given a fixed b _−i, there are t _i breakpoints for the function ${f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right )$. We denote $\mathcal {B}_i$ as the set of the t _i breakpoints, then we have ${\mathcal {B}_i} = \left \{ {p_i^t} \right \}_{t \in \mathcal {T}_i}$, where

$$\displaystyle \begin{aligned} p_i^t = \frac{{{m_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{\left( {m - {m_i}} \right){t_i}}} = \frac{{\left( {\lambda _i^t + \sigma {\mu _i}} \right){\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{\left( {\left( {m - \sigma } \right){\mu _i} - \lambda _i^t} \right){t_i}}}. \end{aligned} $$

Combining the above t _i breakpoints with two end points, i.e., $\underline {p}$ and $\bar p_i$, we obtain a new set ${\mathcal {B}_i} \cup \left \{ { \underline {p},{{\bar p}_i}} \right \}$. Reorder the elements in ${\mathcal {B}_i} \cup \left \{ { \underline {p},{{\bar p}_i}} \right \}$ such that $p_i^{(0)} \le p_i^{(1)} \le \cdots \le p_i^{{(t_i)}} \le p_i^{(t_i+1)}$, where $p_i^{(0)} = \underline {p}$ and $p_i^{(t_i+1)} = \bar p_i$. Then, we obtain a new ordered set $\mathcal {B}_i^{\prime }$. We discuss the claimed theorem by distinguishing three cases according to the first derivative results of the disutility function ${f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right )$ on ${p_i} \in {\mathcal {P}_i}\backslash \mathcal {B}_i$.

Case 1

$\frac {\partial }{{\partial {{\bar p}_i}}}{f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right ) < 0$. According to the results in Theorem 4.2, we know that the second derivative of ${f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right )$ on $p_i \in {\mathcal {P}_i}\backslash {\mathcal {B}_i}$ is positive, i.e., $\frac {\partial ^2 }{{\partial {{p}_i^2}}}{f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right ) > 0$ for all $p_i \in {\mathcal {P}_i}\backslash {\mathcal {B}_i}$. In addition, if , the left partial derivative is less than that of the right partial derivative in each of the breakpoints in $\mathcal {B}_i$. Therefore, if $\frac {\partial }{{\partial {{\bar p}_i}}}{f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right ) < 0$, then $\frac {\partial }{{\partial {{p}_i}}}{f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right ) < 0$ for all $p_i \in {\mathcal {P}_i}\backslash {\mathcal {B}_i}$. Namely, ${f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right )$ is a decreasing function on $p_i \in {\mathcal {P}_i}\backslash {\mathcal {B}_i}$. Hence, the optimal bidding price of cloud user i is $p_i^\ast = {\bar p_i}$. That is to say, the bidding price of cloud user i increases with respect to Ξ_−i.

Case 2

$\frac {\partial }{{\partial \underline {p}}}{f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right ) > 0$. Similar to Case 1, according to the results in Theorem 4.2, we know that $\frac {\partial ^2 }{{\partial {p_i^2}}}{f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right ) > 0$ for all $p_i \in {\mathcal {P}_i}\backslash {\mathcal {B}_i}$. Hence, if $\frac {\partial }{{\partial \underline {p}}}{f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right ) > 0$, ${f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right )$ is an increasing function for all $p_i \in {\mathcal {P}_i}\backslash {\mathcal {B}_i}$. Therefore, under this situation, the optimal bidding price of cloud user i is $p_i^\ast = \underline {p}$, i.e., the optimal bidding price is always the conservative bidding price, which is the initialized value.

Case 3

$\frac {\partial }{{\partial { \underline {p}}}}{f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right ) < 0$ and $\frac {\partial }{{\partial \bar p_i}}{f_i}\left ( {{p_i},{\boldsymbol {b}_{ - i}},\boldsymbol {\lambda } _i^{{t_i}}} \right ) > 0$. Under this situation, it means that there exists an optimal bidding price $p_i^\ast \in {\mathcal {P}_i}\backslash {\mathcal {B}_i^{\prime }}$ such that

$$\displaystyle \begin{aligned} \frac{\partial }{{\partial p_i}}{f_i}\left( {{p_i^\ast},{\boldsymbol{b}_{ - i}},\boldsymbol{\lambda} _i^{{t_i}}} \right) & = \sum_{t = 1}^{{t_i}} {\frac{\partial }{{\partial p_i}}\psi _i^t\left( {{p_i^\ast},{\boldsymbol{b}_{ - i}},\lambda _i^{{t_i}}} \right)} \\ & = \sum_{t = 1}^{{t_i}} {\left( {\frac{{\partial P_i^t}}{{\partial p_i}} + {w_i}\frac{{\partial \bar T_i^t}}{{\partial p_i}} - r\frac{{\partial \chi _i^t}}{{\partial p_i}}} \right)} = 0. {} \end{aligned} $$

(55)

Otherwise, the optimal bidding price for cloud user i ($i \in \mathcal {N}$) is in $\mathcal {B}_i^{\prime }$. If above equation holds, then there exists an integer t ^′ (0 ≤ t ^′≤ t _i), such that the optimal bidding price $p_i^\ast$ is in $( {p_i^{{(t^{\prime })}},p_i^{{(t^{\prime }} + 1)}} ) \subseteq {\mathcal {P}_i}\backslash {\mathcal {B}_i}^{\prime }$.

According to the derivations in Theorem 4.1, we know that the first derivative of $\psi _i^t\left ( {{p_i},{\boldsymbol {b}_{ - i}},\lambda _i^t} \right )$ is

$$\displaystyle \begin{aligned} & \frac{\partial }{{\partial {p_i}}}\psi _i^t\left( {{p_i},{\boldsymbol{b}_{ - i}},\lambda _i^t} \right) \\ & \quad = \begin{cases} {\delta_i\left( {\frac{{m{p_i}{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{\Xi_{\mathcal{N}}^2}}} + {m_i}} \right) - \frac{{m{r_i}{\mu _i}{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{\Xi_{\mathcal{N}}^2}}}}, & p_i < p_i^t; \\ {\delta_i\left( {\frac{{m{p_i}{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{\Xi_{\mathcal{N}}^2}}} + {m_i}} \right) - \frac{{m{w_i}{\mu _i}{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{{\left( {{m_i}{\mu _i} - \lambda _i^t} \right)}^2}{\Xi_{\mathcal{N}}^2}}}}, & p_i > p_i^t, \\ \end{cases} \end{aligned} $$

That is,

$$\displaystyle \begin{aligned} & \frac{\partial }{{\partial {p_i}}}\psi _i^t\left( {{p_i},{\boldsymbol{b}_{ - i}},\lambda _i^{{t}}} \right) \\ & ~ = \begin{cases} \frac{{m{t_i}}}{{{\Xi_{\mathcal{N}}^2}}}\left( {\delta_i{p_i}\left( {{p_i}{t_i} + 2{\Xi _{\mathcal{N}\backslash \{ i\} }}} \right) - {r_i}{u_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}} \right), & p_i < p_i^t; \\ \frac{{m{t_i}}}{{{\Xi_{\mathcal{N}}^2}}}\left( {\delta_i{p_i}\left( {{p_i}{t_i} + 2{\Xi _{\mathcal{N}\backslash \{ i\} }}} \right) - \frac{{{w_i}{u_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{{\left( {{m_i}{\mu _i} - \lambda _i^t} \right)}^2}}}} \right), & p_i > p_i^t. \\ \end{cases} \end{aligned} $$

Therefore, the Eq. (55) is equivalent to the following equation:

$$\displaystyle \begin{aligned} h\left( {p_i^\ast} \right) = \sum_{t = 1}^{{t_i}} {\varphi _i^t\left( {{p_i^\ast},{\boldsymbol{b}_{ - i}},\lambda _i^{{t}}} \right)} = 0, \end{aligned} $$

where

$$\displaystyle \begin{aligned} & {\varphi _i^t\left( {{p_i^\ast},{\boldsymbol{b}_{ - i}},\lambda _i^{{t}}} \right)} \\ & \qquad = \begin{cases} {\delta_i{p_i^\ast}\left( {{p_i^\ast}{t_i} + 2{\Xi _{\mathcal{N}\backslash \{ i\} }}} \right) - {r_i}{u_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}, & p_i^\ast < p_i^t; \\ {\delta_i{p_i^\ast}\left( {{p_i^\ast}{t_i} + 2{\Xi _{\mathcal{N}\backslash \{ i\} }}} \right) - \frac{{{w_i}{u_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{{\left( {{m_i}{\mu _i} - \lambda _i^t} \right)}^2}}}}, & p_i^\ast > p_i^t. \\ \end{cases} \end{aligned} $$

After some algebraic manipulation, we can write the first derivative result of $\varphi _i^t\left ( {{p_i^\ast },{\boldsymbol {b}_{ - i}},\lambda _i^{{t}}} \right )$ on $p_i^\ast$ as

$$\displaystyle \begin{aligned} & \frac{\partial }{{\partial {p_i^\ast}}}\varphi _i^t\left( {{p_i^\ast},{\boldsymbol{b}_{ - i}},\lambda _i^{{t}}} \right) \\ & \qquad = \begin{cases} 2\delta_i\left({p_i^\ast}{t_i} + {\Xi _{\mathcal{N}\backslash \{ i\} }}\right), & p_i^\ast < p_i^t; \\ 2\delta_i\left({p_i^\ast}{t_i} + {\Xi _{\mathcal{N}\backslash \{ i\} }}\right) + \frac{{2{w_i}{t_i}\mu _i^2\Xi _{\mathcal{N}\backslash \{ i\} }^2}}{{{{\left( {{m_i}{\mu _i} - \lambda _i^t} \right)}^3}{\Xi_{\mathcal{N}}^2}}}, & p_i^\ast > p_i^t, \\ \end{cases} \end{aligned} $$

and the first derivative result of the function $\varphi _i^t\left ( {{p_i^\ast },{\boldsymbol {b}_{ - i}},\lambda _i^{{t}}} \right )$ on $\Xi _{\mathcal {N}\backslash \{ i\} }$ as

$$\displaystyle \begin{aligned} & \frac{\partial }{{\partial {\Xi _{\mathcal{N}\backslash \{ i\} }}}}\varphi _i^t\left( {{p_i^\ast},{\boldsymbol{b}_{ - i}},\lambda _i^{{t}}} \right) \\ & \qquad = \begin{cases} 2\delta_i{p_i^\ast} - {r_i}{u_i}, & p_i^\ast < p_i^t; \\ 2\delta_i{p_i^\ast} - {r_i}{u_i} - \frac{{{w_i}{\mu _i}}}{{{{\left( {{m_i}{\mu _i} - \lambda _i^t} \right)}^2}}} \\ \qquad \qquad - \frac{{2m{w_i}\mu _i^2{p_i^\ast}{t_i}{\Xi _{\mathcal{N}\backslash \{ i\} }}}}{{{{\left( {{m_i}{\mu _i} - \lambda _i^t} \right)}^3}{\Xi_{\mathcal{N}}^2}}}, & p_i^\ast > p_i^t. \\ \end{cases} \end{aligned} $$

Obviously, we have

$$\displaystyle \begin{aligned} \frac{\partial }{{\partial {p_i^\ast}}}\varphi _i^t\left( {{p_i^\ast},{\boldsymbol{b}_{ - i}},\lambda _i^{{t}}} \right) > 0, \end{aligned} $$

for all ${p_i^\ast } \in {\mathcal {P}_i}\backslash \mathcal {B}_i^{\prime }$. If , then

$$\displaystyle \begin{aligned} \frac{\partial }{{\partial {\Xi _{\mathcal{N}\backslash \{ i\} }}}}\varphi _i^t\left( {{p_i^\ast},{\boldsymbol{b}_{ - i}},\lambda _i^{{t}}} \right) < 0. \end{aligned} $$

Therefore, if ${r_i} > \max \left \{ {\frac {{2{\delta _i}{{\bar p}_i}}}{{{\mu _i}}},\frac {{{w_i}}}{{{\sigma ^2}\mu _i^2}}} \right \}$, the function $h\left ( {b_i^\ast } \right )$ decreases with the increase of ${\Xi _{\mathcal {N}\backslash \{ i\} }}$. If ${\Xi _{\mathcal {N}\backslash \{ i\} }}$ increases, to maintain the equality $h\left ( {b_i^\ast } \right ) = 0$, $b_i^\ast$ must increase. Hence, $b_i^\ast$ increases with the increase of ${\Xi _{\mathcal {N}\backslash \{ i\} }}$. This completes the proof and the result follows. □

Theorem 4.5

Algorithm $\mathcal {I}\mathcal {A}$ converges to a Nash equilibrium, given that the condition ${r_i} > \max \left \{ {\frac {{2{\delta _i}{{\bar p}_i}}}{{{\mu _i}}},\frac {{{w_i}}}{{{\sigma ^2}\mu _i^2}}} \right \}$ ( $i \in \mathcal {N}$ ) holds.

Proof

We are now ready to show that the proposed $\mathcal {I}\mathcal {A}$ algorithm always converges to a Nash equilibrium solution, given that ${r_i} > \left \{ {\frac {{2{\delta _i}{{\bar p}_i}}}{{{\mu _i}}},\frac {{{w_i}}}{{{\sigma ^2}\mu _i^2}}} \right \}$ ($i \in \mathcal {N}$) holds. Let $p_i^{\left ( k \right )}$ be the optimal bidding price of cloud user i ($i \in \mathcal {N}$) at the k-th iteration. We shall prove above claim by induction that $p_i^{\left ( k \right )}$ is non-decreasing in k. In addition, since $p_i^\ast$ is bounded by ${\bar p_i}$, this establishes the result that $p_i^{\left ( k \right )}$ always converges.

By Algorithm 1, we know that the bidding price of each cloud user is initialized as the conservative bidding price, i.e., $p_i^{(0)}$ is set as $\underline {p}$ for each of the cloud users i ($i \in \mathcal {N}$). Therefore, after the first iteration, we obtain the results $p_i^{\left ( 1 \right )} \ge p_i^{\left ( 0 \right )}$ for all $i \in \mathcal {N}$. This establishes our induction basis.

Assuming that the result is true in the k-th iteration, i.e., $p_i^{\left ( k \right )} \ge p_i^{\left ( k-1 \right )}$ for all $i \in \mathcal {N}$. Then, we need to show that in the (k + 1)-th iteration, $p_i^{\left ( k+1 \right )} \ge p_i^{\left ( k \right )}$ is satisfied for all $i \in \mathcal {N}$. We proceed as follows.

By Theorem 4.4, we know that if , the optimal bidding price $p_i^\ast$ of cloud user i ($i \in \mathcal {N}$) increases with the increase of ${\Xi _{\mathcal {N}\backslash \{ i\} }}$, where ${\Xi _{\mathcal {N}\backslash \{ i\} }} = \sum \nolimits _{j \in \mathcal {N},j \ne i} {{p_j}{t_j}}$. In addition, we can deduce that

$$\displaystyle \begin{aligned} \Xi _{{\mathcal{N}\backslash \{ i\} }}^{\left( k \right)} = \sum_{j \in \mathcal{N},j \ne i} {p_j^{\left( k \right)}{t_j}} \ge \sum_{j \in \mathcal{N},j \ne i} {p_j^{\left( {k - 1} \right)}{t_j}} = \Xi _{{\mathcal{N}\backslash \{ i\} }}^{\left( {k - 1} \right)}. \end{aligned} $$

Therefore, the optimal bidding price of cloud user i ($i \in \mathcal {N}$) in the $\left (k+1\right )$-th iteration $p_i^{\left ( k+1 \right )}$, which is a function of $\Xi _{{\mathcal {N}\backslash \{ i\} }}^{\left ( k \right )}$, satisfies $p_i^{\left ( k+1 \right )} \ge p_i^{\left ( k \right )}$ for all $i \in \mathcal {N}$. Thus, the result follows. □

Algorithm 5 Calculate_p _i( Ξ, λit _i, 𝜖)

Next, we focus on the calculation for the optimal bidding price $p_i^\ast$ in problem (54), i.e., calculate

$$\displaystyle \begin{aligned} {p_i^\ast} \in \mathop {\arg \min }\limits_{{p_i} \in {\mathcal{P}_i}} {f_i}\left( {{p_i},\Xi_{\mathcal{N}} ,\boldsymbol{\lambda} _i^{{t_i}}} \right). \end{aligned} $$

(56)

From Theorem 4.5, we know that the optimal bidding price $p_i^\ast$ of cloud user i ($i \in \mathcal {N}$) is either in $\mathcal {B}_i^{\prime }$ or in ${\mathcal {P}_i}\backslash {\mathcal {B}_i^{\prime }}$ such that

$$\displaystyle \begin{aligned} \frac{\partial }{{\partial p_i}}{f_i}\left( {{p_i^\ast},\Xi_{\mathcal{N}} ,\boldsymbol{\lambda}_i^{{t_i}}} \right) & = \sum_{t = 1}^{{t_i}} {\frac{\partial }{{\partial p_i}}\psi _i^t\left( {{p_i^\ast},\Xi_{\mathcal{N}} ,\lambda _i^{{t}}} \right)} \\ & = \sum_{t = 1}^{{t_i}} {\left( \delta_i{\frac{{\partial P_i^t}}{{\partial p_i}} + {w_i}\frac{{\partial \bar T_i^t}}{{\partial p_i}} - {r_i}\frac{{\partial \chi _i^t}}{{\partial p_i}}} \right)} = 0, {} \end{aligned} $$

(57)

where ${\mathcal {B}_i^{\prime }}$ is an ordered set for all elements in ${{\mathcal {B}_i} \cup \left \{ { \underline {p},{{\bar p}_i}} \right \}}$, and $\mathcal {B}_i$ is the set of t _i breakpoints of cloud user i ($i \in \mathcal {N}$), i.e., $\mathcal {B}_i = \left \{ p_i^ t\right \}_{t \in \mathcal {T}_i}$ with

$$\displaystyle \begin{aligned} p_i^t = \frac{{{m_i}{\Xi _{{\mathcal{N}\backslash \{ i\} }}}}}{{\left( {m - {m_i}} \right){t_i}}} = \frac{{\left( {\lambda _i^t + \sigma {\mu _i}} \right){\Xi _{ {\mathcal{N}\backslash \{ i\} }}}}}{{\left( {\left( {m - \sigma } \right){\mu _i} - \lambda _i^t} \right){t_i}}}. \end{aligned} $$

(58)

Assuming that the elements in $\mathcal {B}_i^{\prime }$ satisfy $p_i^{( 0 )} \le p_i^{( 1 )} \le \cdots \le p_i^{( {{t_i+1}})}$, where $p_i^{(0)} = \underline {p}$ and $p_i^{(t_i+1)} = \bar p_i$. If equation (57) holds, then there exists an integer t ^′ (0 ≤ t ^′≤ t _i) such that the optimal bidding price $p_i^\ast \in ( {p_i^{{(t^{\prime })}},p_i^{{(t^{\prime }} + 1)}} ) \subseteq {\mathcal {P}_i}\backslash {\mathcal {B}_i^{\prime }}$. In addition, from the derivations in Theorem 4.5, we know that

$$\displaystyle \begin{aligned} \frac{{{\partial ^2}}}{{\partial p_i^2}}{f_i}\left( {{p_i},{\Xi_{\mathcal{N}}},\boldsymbol{\lambda}_i^{{t_i}}} \right) > 0, {} \end{aligned} $$

(59)

for all ${p_i} \in {\mathcal {P}_i}\backslash {\mathcal {B}_i^{\prime }}$. Therefore, we can use a binary search method to search the optimal bidding price $p_i^{\ast }$ in each of the sets $( {p_i^{{(t^{\prime })}},p_i^{{(t^{\prime }} + 1)}} ) \subseteq {\mathcal {P}_i}\backslash {\mathcal {B}_i^{\prime }}$ ($0 \le t_i^{\prime } \le t_i$), which satisfies (57). If we cannot find such a bidding price in ${\mathcal {P}_i}\backslash {\mathcal {B}_i^{\prime }}$, then the optimal bidding price $p_i^\ast$ is in $\mathcal {B}_i^{\prime }$. The idea is formalized in Algorithm 2.

Given Ξ, $\boldsymbol {\lambda }_i^{t_i}$, and 𝜖, where $\Xi = \sum \nolimits _{j \in \mathcal {N}} {{p_j}{t_j}}$, , and 𝜖 is a relatively small constant. Our optimal price bidding configuration algorithm to find $p_i^\ast$ is given in Algorithm $\mathcal {C}alculate\_p_i$. The key observation is that the first derivative of function ${f_i}\left ( {{p_i}, \Xi , \boldsymbol {\lambda } _i^{{t_i}}} \right )$, i.e., $\frac {\partial }{{\partial {p_i}}}{f_i}\left ( {{p_i}, \Xi ,\boldsymbol {\lambda }_i^{{t_i}}} \right )$, is an increasing function in ${p_i} \in ( {p_i^{({t^{\prime }})},p_i^{({t^{\prime }} + 1)}} ) \subset {\mathcal {P}_i}\backslash \mathcal {B}_i^{\prime }$ (see (59)), where 0 ≤ t ^′≤ t _i. Therefore, if the optimal bidding price is in ${\mathcal {P}_i}\backslash \mathcal {B}_i^{\prime }$, then we can find $p_i^\ast$ by using the binary search method in one of the intervals (${p_i^{({t^{\prime }})},p_i^{({t^{\prime }} + 1)}}$) (0 ≤ t ^′≤ t _i) (Steps 3–17). In each of the search intervals $( {p_i^{({t^{\prime }})},p_i^{({t^{\prime }} + 1)}} )$, we set ub as $( {p_i^{({t^{\prime }} + 1)} - \epsilon } )$ and lb as $( {p_i^{({t^{\prime }})} + \epsilon } )$ (Step 4), where 𝜖 is relative small positive constant. If the first derivative of function ${f_i}\left ( {{p_i}, \Xi , \boldsymbol {\lambda } _i^{{t_i}}} \right )$ on lb is positive or the first derivative on ub is negative, then the optimal bidding price is not in this interval (Step 5). Once the interval, which contains the optimal bidding price is decided, we try to find the optimal bidding price $p_i^\ast$ (Steps 8–16). Notice that, the optimal bidding price may in $\mathcal {B}_i^{\prime }$ rather than in ${\mathcal {P}_i}\backslash \mathcal {B}_i^{\prime }$ (Step 19). Under this situation, we check each of the breakpoints in $\mathcal {B}_i^{\prime }$ and find the optimal bidding price (Steps 21–25).

By Algorithm 2, we note that the inner while loop (Steps 8–15) is a binary search process, which is very efficient and requires $\Theta \left ( { \log \frac {\bar p_{\max }- \underline {p}}{\epsilon }} \right )$ to complete, where $\bar p_{\max }$ is the maximum upper bidding bound of all users, i.e., $\bar p_{\max } = {\max _{i \in \mathcal {N}}}\left ( {{{\bar p}_i}} \right )$. Let $t_{\max } = {\max _{i \in \mathcal {N}}}\left ( {{{t}_i}} \right )$, then the outer while loop (Steps 3–17) requires time $\Theta \left ( t_{\max }{ \log \frac {\bar p_{\max }- \underline {p}}{\epsilon }} \right )$. On the other hand, the for loop (Steps 21–25) requires $\Theta \left ( {{t_{\max }}} \right )$ to find solution in set $\mathcal {B}_i^{\prime }$. Therefore, the time complexity of Algorithm 2 is $\Theta \left ( {{t_{\max }}\left ( { \log \frac {\bar p_{\max }- \underline {p}}{\epsilon } + 1} \right )} \right )$.

4.2.4 A Near-Equilibrium Price Bidding Algorithm

Notice that, the equilibrium bidding prices obtained by $\mathcal {I}\mathcal {A}$ algorithm are considered under the condition that the allocated number servers can be fractional, i.e., in the computation process, we use

$$\displaystyle \begin{aligned} m_i = \frac{{{p_i}{t_i}}}{{\sum\nolimits_{j \in \mathcal{N}} {{p_j}{t_j}} }} \cdot m, {} \end{aligned} $$

(60)

instead of

$$\displaystyle \begin{aligned} {m_i} = \left\lfloor {\frac{{{p_i}{t_i}}}{{\sum\nolimits_{j \in \mathcal{N}} {{p_j}{t_j}} }} \cdot m} \right\rfloor. {} \end{aligned} $$

(61)

Therefore, we have to revise the solution and obtain a near-equilibrium price bidding strategy. Note that, under Eq. (61), there may exist some remaining servers, which is at most n. Considering for this, we reallocate the remaining servers according to the bidding prices. The idea is formalized in our proposed near-equilibrium price bidding algorithm ($\mathcal {N}\mathcal {P}\mathcal {B}\mathcal {A}$), which characterizes the whole process.

Algorithm 6 Near-equilibrium Price ℬidding Algorithm (NPℬA)

At the beginning, the cloud provider sets a proper conservative bidding price ($\underline {p}$) and puts its value to into public information exchange module. Each cloud user i ($i \in \mathcal {N}$) sends his/her reserved time slots value (t _i) to the cloud provider. We denote the current set of cloud users who want to use cloud service as $\mathcal {S}_c$ and assume that in the beginning, all cloud users in $\mathcal {N}$ want to use cloud service, i.e., set $\mathcal {S}_c$ as $\mathcal {N}$ (Step 1). For each current user set $\mathcal {S}_c$, we calculate the optimal bidding prices for all users in $\mathcal {S}_c$ by $\mathcal {I}\mathcal {A}$ algorithm, under the assumption that the allocated servers can fractional (Step 3). And then, we calculate their corresponding allocated servers (Steps 4–6). We calculate the remaining servers and introduce a flag variable. The inner while loop tries to allocate the remaining servers according to the calculated bidding strategies of the current users in $\mathcal {S}_c$ (Steps 8–16). The variable flag is used to flag whether there is a user in $\mathcal {S}_c$ can improve his/her utility by the allocated number of servers. The while loop terminates until the remaining servers is zero or there is no one such user can improve his/her utility by reallocating the remaining servers. For each user in $\mathcal {S}_c$, if his/her utility value is less than the reserved value, then we assume that he/she refuses to use cloud service (Steps 17–21). The algorithm terminates when the users who want to use cloud service are kept unchanged (Steps 2–22).

4.3 Performance Evaluation

In this section, we provide some numerical results to validate our theoretical analyses and illustrate the performance of the $\mathcal {N}\mathcal {P}\mathcal {B}\mathcal {A}$ algorithm.

In the following simulation results, we consider the scenario consisting of maximal 200 cloud users. Each time slot is set as one hour of a day and the maximal time slots of a user can be 72. As shown in Table 2, the conservative bidding price ($\underline {p}$) is varied from 200 to 540 with increment 20. The number of cloud users (n) is varied from 50 to 200 with increment 10. The maximal bidding price ($\bar p_i$) and market benefit factor (r _i) of each cloud user are randomly chosen from 500 to 800 and 30 to 120, respectively. Each cloud user i ($i \in \mathcal {N}$) chooses a weight value from 0.1 to 2.5 to balance his/her time utility and profit. We assume that the request arrival rate ($\lambda _i^t$) in each time slot of each cloud user is selected randomly and uniformly between 20 and 480. The processing rate (μ _i) of a server to the requests from cloud user i ($i \in \mathcal {N}$) is randomly chosen from 60 to 120. For simplicity, the reservation value (v _i) and payment cost weight (δ _i) for each of the cloud users are set as zero and one, respectively. The number of servers m in the cloud provider is set as a constant 600, σ is set as 0.1, and 𝜖 is set as 0.01 (Table 3).

Table 2 Notations

Table 3 System parameters

Figure 10 shows an instance for the bidding prices of six different cloud users versus the number of iterations of the proposed $\mathcal {I}\mathcal {A}$ algorithm. Specifically, Fig. 10 presents the bidding price results of 6 randomly selected cloud users (users 8, 18, 27, 41, 59, and 96) with a scenario consisting of 100 cloud users. We can observe that the bidding prices of all users seem to be non-decreasing with the increase of iteration number and finally reach a relative stable state, which verifies the validness of Theorem 3.4. That is, the bidding prices of all cloud users keep unchanged, i.e., reach a Nash equilibrium solution after several iterations. In addition, it can also be seen that the developed algorithm converges to a Nash equilibrium very quickly. Specifically, the bidding price of each user has already achieved a relatively stable state after 5 iteration, which shows the high efficiency of our developed algorithm.

Fig. 10

Convergence process of bidding price

In Fig. 11, we show the trend of the aggregated payment from all cloud users (P _T), i.e., the revenue of the cloud provider, versus the increment of the conservative bidding price. We compare two kinds of results with the situations by computing the allocated number of servers for each cloud user i ($i \in \mathcal {N}$) as (60) and (61), respectively. Specifically, we denote the obtained payment as V _T when compute m _i as (60) and P _T for (61). Obviously, the former is the optimal value computed from the Nash equilibrium solution and bigger than that of the latter. However, it cannot be applied in a real application, because the allocated number of servers cannot be fractional. We just obtain a near-equilibrium solution by assuming that the allocated number of servers can be fractional at first. Even though the obtained solution is not optimal, we can compare these two kinds of results and show that how closer our proposed algorithm can find a near-equilibrium solution to that of the computed optimal one.

Fig. 11

Aggregated payment of all users

We can observe that the aggregated payment from all cloud users tends to increase with the increase of conservative bidding price at first. However, it decreases when conservative bidding price exceeds a certain value. The reason behind lies in that when conservative bidding price increases, more and more cloud users refuse to use the cloud service due to the conservative bidding price exceeds their possible maximal price bidding values or their utilities are less than their reservation values, i.e., the number of users who choose cloud service decreases (see Fig. 12). We can also observe that the differences between the values of P _T and V _T are relatively small and make little differences with the increase of the conservative bidding price. Specifically, the percent differences between the values of V _T and P _T range from 3.99% to 8.41%, which reflects that our $\mathcal {N}\mathcal {P}\mathcal {B}\mathcal {A}$ algorithm can find a very well near-optimal solution while ignoring the increment of conservative bidding price. To demonstrate this phenomenon, we further investigate the specific utilities of some users and their corresponding bidding prices, which are presented in Figs. 13 and 14.

Fig. 12

Actual number of cloud users

Fig. 13

Specific user utility

Fig. 14

Specific user bidding price

In Figs. 13 and 14, we plot the utility shape and the bidding prices of some cloud users for the developed $\mathcal {N}\mathcal {P}\mathcal {B}\mathcal {A}$ algorithm. Figure 13 presents the utility shape under the developed algorithm versus the increment of conservative bidding price. We randomly select 6 users (users 1, 19, 35, 58, 87, and 100). It can be seen that the utility trends of all cloud users tend to decreases with the increase of conservative bidding price. However, under every conservative bidding price, for each user, the differences between the utilities computed by using m _i as (60) (the larger one) and (61) (the smaller one) for each cloud user are relatively small. Therefore, the differences between the aggregated payments of (P _T) and (V _T) are small (see Fig. 11). Figure 14 exhibits the corresponding bidding prices of the users shown in Fig. 13. We can observe that some users may refuse to use cloud service when conservative bidding price exceeds a certain value (user 2). When users choose to use cloud service, the treads of their bidding prices tend to be non-decreasing with the increment of conservative bidding price (user 19, 34, 75, 87, and 100). This phenomenon also verifies the aggregated payment trend shown in Fig. 11. Specifically, due to the increases of users’ bidding prices, the aggregated payment from all cloud users tend to increase at first. However, when conservative bidding price exceeds a certain value, more and more cloud users refuse to use cloud service. Therefore, the aggregated payment tends to decrease when conservative bidding price is large enough.

In Fig. 15, we show the impact of number of cloud users on aggregated payment. Similar to Fig. 11, the differences between the values of P _T and V _T are relatively small. Specifically, the percent differences between the values of V _T and P _T range from 3.14% to 12.37%. That is, the aggregated payment results for different number of users are largely unchanged. In Fig. 16, we can observe that with the increase of number of cloud users, the trend of the differences between the number of cloud users and the actual number of cloud users who choose cloud service also increases. The reason behind lies in that with the increase of number of cloud users, more and more users refuse to use cloud service due to their utilities are less than their conservative values. This also partly verifies the aggregated payment trend shown in Fig. 15, in which the aggregated payments are largely unchanged with the increase of number cloud users.

Fig. 15

Aggregated payment on number of users

Fig. 16

(Actural) number of cloud users

5 Conclusions

With the popularization of cloud computing and its many advantages such as cost-effectiveness, flexibility, and scalability, more and more applications are moved from local to cloud. However, most cloud providers do not provide a mechanism in which the users can configure optimizing strategies and decide whether to use the cloud service. To remedy these deficiencies, we focus on proposing a framework to obtain an appropriate strategy for each cloud user.

We try to enhance services in cloud computing by considering from multiple users’ perspective. Specifically, we try to improve cloud services by simultaneously optimizing multiple users’ utilities which involve both time and payment. We use game theory to analyze the situation and try to obtain a Nash equilibrium to simultaneously maximize multiple users’ utilities. We prove the existence of Nash equilibrium and design two different approaches to obtain a Nash equilibrium for the two problems, respectively. Extensive experiments are also conducted, which verify our analyses and show the efficiencies of our methods.