# Priority Pricing for Efficient Resource Usage of Mobile Internet Access
## 5 Pricing Optimality Analysis
### Search Space Pruning  
The algorithm used two rules for the search space pruning. Among all possible prices for service level \(i\), \(P_{i}\), the algorithm prunes out the price vectors that will result in no jobs selecting level \(i\) and the price vectors that will make all of the jobs select level \(i\). In Figure 4, \(\Pi_{i}\) represents the range of \(P_{i}\) under which no job will select level \(i\), and \(\Phi_{i}\) represents the range of \(P_{i}\) under which all jobs will choose level \(i\). Note that \(\Pi_{i}\) is always located above \(\Phi_{i}\). The shaded region between \(\Pi_{i}\) and \(\Phi_{i}\) is subjected to analysis when using the SAM. Suppose \(P_{i}^{*}\) is the smallest \(P_{i}\) value in \(\Pi_{i}\). Because no job chooses level \(i\) with \(P_{i}^{*}\), all of the prices that are higher than \(P_{i}^{*}\) will end up with the same result, that is, there are no jobs that will choose level \(i\). Therefore, we only need to consider \(P_{i}^{*}\) and prune \(\Pi_{i}\). Similarly, we only need to consider the largest \(P_{i}\) value in \(\Phi_{i}\) and can, therefore, prune \(\Phi_{i}\).The key issue is how to find the boundary of these regions (i.e., the smallest \(P_{i}\) of \(\Pi_{i}\) and the largest \(P_{i}\) of \(\Phi_{i}\)). Figure 4: Pruning regions. \begin{table}
\begin{tabular}{c c} \hline \hline  & \(\{\lambda_{1},\lambda_{2}\}\)**when \(\{P_{1},P_{2}\}\)** = [2.21, 1.61] \\ \hline Equilibrium model & Converges on [0.183, 0.278]. \\ \hline SAM (\(F=100\)) & Oscillates among [0.183, 0.282], [0.183, 0.277], [0.188, 0.277], \\  & \(\{0.178, 0.277\}\), and \(\{0.183, 0.272\}\). \\ \hline SAM (\(F=2\)) & Oscillates among [0.0, 0.495], [0.0, 0.742], [0.0, 0.247], \\  & \(\{0.247, 0.247\}\), [0.247, 0.495], [0.247, 0.742], and \(\{0.0, 0.0\}\). \\ \hline SAM (\(F=1\)) & Oscillates among [0.0, 0.0], [0.495, 0.0] and [0.0, 0.99]. \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Case III comparison results. This section explains the pruning rules for a two-service-level system as an example, and presents general cases later. For a system with two levels, this section suggests the following four pruning rules in Figure 5, which have two rules for each service level. Rules 1 and 2 have the following meanings: if there is no queuing delay, the minimum expected completion time is \(C_{j}/\mu\), and the maximum utility of a type-\(j\) job is \(U_{j}(C_{j}/\mu)\). Thus, if \(P_{1}\) is greater than the maximum utility value for all jobs (i.e., if \(P_{1}C_{j}>U_{j}(C_{j}/\mu)\) for all \(j\in J\)), then level 1 will not be selected. By contrast, if \(P_{2}\) is greater than \(P_{1}\), level 2 will not be selected, because jobs in level 1 have priority over jobs in level 2 under SPS and thus no one will pay more for level 2. Rule 3 prunes all \(P_{1}\)'s, which guarantees that all jobs will choose level 1. The highest price of the level 1 to guarantee that all of the jobs select level 1 is \(\min\left[U_{j}\left(T_{1j}^{*}\right)/C_{j}\right]\) (i.e., \(P_{1}C_{j}<U_{j}\left(T_{1j}^{*}\right)\) for all \(j\in J\)), where \(T_{1j}\) is the expected completion time of a type-\(j\) job at level 1 when the job arrival rate vector is \(\left\{0,\lambda,0\right\}\). \(T_{1j}\) can be computed using Equation (1). Rule 4 prunes all \(P_{2}\)'s, which guarantees that all jobs choose level 2. The first condition for this scenario is \(P_{2}C_{j}<U_{j}\left(T_{2j}^{*}\right)\) for all \(j\in J\), where \(T_{2j}^{*}\) is the expected completion time of a type-\(j\) job at level 2, when the job arrival rate vector is \(\left\{0,\,0,\,\lambda\right\}\). Another condition is \(P_{2}C_{j}<U_{j}\left(T_{2j}\right)-U_{j}\left(T_{1j}\right)+P_{1}C_{j}\) for all \(j\). Here, \(T_{1j}\) for the first user choosing level 1 is \(C_{j}/\mu\) (i.e., zero queuing delay). Therefore, the largest \(P_{2}\) should be \(\min\left[U_{j}\left(T_{2j}^{*}\right)/C_{j},\,U_{j}\left(T_{2j}^{*}\right)/C _{j}-U_{j}\left(C_{j}/\right)/C_{j}+P_{1}\right]\) for all \(j\).