# Priority Pricing for Efficient Resource Usage of Mobile Internet Access
## 5 Pricing Optimality Analysis
### Heuristic Search  
After pruning has been performed, the algorithm explores the remaining search space using the heuristic search method. The algorithm adopted the \"iterative-deepening\" search [39], which combines the benefits of performing both a depth-first search and breadth-first search. The process begins by coarsely selecting the price vectors from the search space and then gradually tries out the other price vectors, while increasing the  
Figure 5: Pruning rules for a system with two service levels.  
Figure 6: Pruning rules for a system with \(I\) service levels.  
granularity of prices until either the computational time limit has been exhausted or the pre-set search depth limit has been reached. The algorithm also stops if the improvements between the results are negligibly small. The pseudocode for the search algorithm is shown in Figure 7.  
Let us compute the system objective value for a given price vector \(\{P_{i}\}\) as follows: First, SAM produces a state-transition graph. If the system converges to a steady state, then we need to account for only that state when computing the system objective value. If the system oscillates, the system objective value can be obtained by computing the weighted average of the system objective values of all states in the oscillation loop.  
Another heuristic is the hill-climbing search. In general, the hill-climbing search can find the optimal solution if the objective function is unimodal (i.e., when a proper maximum is in a given region). Owing to the risk of oscillation, unimodality with respect to the price vector is not guaranteed, and the existence of local optima is possible. Techniques such as simulated annealing and multi-criteria decision analysis may be used to avoid settling into a local optimum or evaluate conflicting criteria of price and QoS, but this study does not deal with them.  
Let us compute the system objective value for a given price vector \(\{P_{i}\}\) by utilizing the SAM result as follows: SAM produces a state-transition graph. If the system converges to a steady state, then the system objective value is updated.  
Figure 7: Iterative deepening search algorithm.  
steady state, we need to account for only that state when computing the system objective value. If the system oscillates, the system objective value can be obtained by computing the weighted average of the system objective values of all states in the oscillation loop. For instance, in a profit-maximization system, when the system converges to a steady state of the job arrival rate vector \(\{\lambda_{i}\}\), the system objective function (i.e., the total system profit) is the sum of revenues collected at all service levels minus the fee that the service provider pays to his upper-level service provider:  
\[\sum_{i\in I}(P_{i}\;\lambda_{i}C)-\mu P_{B}C \tag{15}\]  
where \(C\) is the average job size (i.e., \(C\;=\;\sum\limits_{j\in I}C_{j}\cdot Prob(j)\)), where \(Prob(j)\) is the probability that a job is of type \(j\). Note that the use of \(C\) may be approximate when some jobs are not sent. However, when the jobs not sent have an average size similar to the jobs sent, it is a good approximation. The system objective function in the case of system oscillation is calculated as follows:  
\[\sum_{\{S\}}(W(S)\sum_{i}P_{i}\lambda_{i}(S)C))-\mu P_{B}C \tag{16}\]  
where \(\{S\}\) denotes the set of recurring states in the oscillation loop, \(W(S)\) is the stationary probability of state \(S\), and \(\lambda_{i}(S)\) is the job arrival rate at level \(i\) in state \(S\).