# A New Dynamic Game-Based Pricing Model for Cloud Environment
## 4 The Proposed Game-Based Pricing Method
### Finding the Sub-Game Perfect Nash Equilibrium of the Game  
The backward induction method is employed in order to resolve the game and uncover the sub-game perfect Nash equilibrium [38]. First, the lower level (provider level) sub-games are solved. It should be determined which actions the provider (final mover) should take in each possible circumstance to maximize its profit. Second, the upper level (user level) sub-game should be solved. By finding a solution to this sub-game, the actions that would lead to the Nash equilibrium for both players will be established.  
**Lower-level sub-games:** In each sub-game, the optimal price for the corresponding candidate virtual machine should be determined so that the cloud provider's profit is maximized. Therefore, the derivative of the provider's payoff function concerning variable \(P_{i}\) should be found. This derivative is equal to zero, and the equation is solved for \(P_{i}\). First, the extended form of the provider's payoff function is written as follows:  
\[\pi_{cp}\big{(}VM_{j},P_{i}\big{)}=\left(rq\ P_{i}TW+\frac{\alpha P _{i}^{2}TW+\beta P_{i}TW}{Q_{0}}\right)-\left(FPrqP_{i}TW+\frac{FP\alpha P_{ i}^{2}TW+FP\beta P_{i}TW}{Q_{0}}\right)\]  
Now  
\[\frac{\partial\pi_{cp}\big{(}VM_{j},\ \ P_{i}\big{)}}{\partial P_{i}}=0\Rightarrow\]  
\[\left(rq\ TW+\frac{2\ \alpha\ P_{i}TW+\beta TW}{Q_{0}}\right)-\left(FPrqTW+ \frac{2\ FP\alpha P_{i}TW+FP\beta TW}{Q_{0}}\right)=0\]  
Therefore, the optimal price in each possible circumstance can be finally calculated as follows:  
\[P^{*}=\frac{Q_{0}\pi_{q}+\beta}{-2\ \alpha} \tag{8}\]  
**Upper-level sub-game:** After finding out the optimal reaction of the second player (\(P^{*}\)) to the user's moves in the sub-games at a lower level, the sub-game at a higher level can be resolved. At this step, the best response of the user to the cloud provider's action would also be determined. Knowing the price selected by the provider for each candidate virtual machine, the resource broker can calculate the amount of the user's profit for each action and choose the most proper virtual machine for the user. To determine the user's earnings, the resource broker utilizes Equations (5)-(7). Therefore, the best response of the user to action \(P^{*}\) of the provider can be determined as follows:  
\[VM^{*}=\underset{VM_{j}}{\mathrm{Argmax}}\pi_{u}\big{(}VM_{j},\ P^{*}\big{)} \tag{9}\]  
The action pair \((VM^{*},\ P^{*})\) is a Nash equilibrium because both players' action is the best response to each other.  
The steps involved in the proposed method, executed by the Grid's Resource Broker, are illustrated in Algorithm 1. The proposed method first collects information about the physical machine conditions. Then, to handle each request, it determines on which physical machine the desired virtual machine can be created for the successful execution of the request. In the next step, the dynamic game tree is constructed as described in Section 4.2. In the initial phase of game resolution, it determines the optimum cost for every potential virtual machine based on Equation (8). At this stage, it seeks to increase the profit of the cloud provider. In the second stage of solving the game, he chooses the best virtual machine for the user's request based on Equation (9). At this stage, the user's profit is expected to increase.  
```
1 Input:\(N\) number of user requests
2 Output: Best \(VM\) for each request with minimum cost
3 Get information about the status of physical machines
4 While the request queue is not empty Do
5 For each request Do
6 Find all PMs capable of executing the request
7 Construct the dynamic game tree
8 Find the best price for VMs based on Equation (8)
9 Find the best VM based on Equation (9)
10 Update status information of physical machines
11 End for
12 End while
```  
**Algorithm 1** Resource Broker