Adaptive and Resilient Revenue Maximizing Dynamic Resource Allocation and Pricing for Cloud-Enabled IoT Systems
Muhammad Junaid Farooq Quanyan Zhu
cs.DC




[
    [
    December 30, 2023
=====================

empty
empty





Cloud computing is becoming an essential component in the emerging Internet of Things (IoT) paradigm. The available resources at the cloud such as computing nodes, storage, databases, etc. are often packaged in the form of virtual machines (VMs) to be used by remotely located IoT client applications for computational tasks. However, the cloud has a limited number of VMs available and hence, for massive IoT systems, the available resources must be efficiently utilized to increase productivity and subsequently maximize revenue of the cloud service provider (CSP). IoT client applications generate requests with computational tasks at random times with random complexity to be processed by the cloud. The CSP has to decide whether to allocate a VM to a task at hand or to wait for a higher complexity task in the future. We propose a threshold-based mechanism to optimally decide the allocation and pricing of VMs to sequentially arriving requests in order to maximize the revenue of the CSP over a finite time horizon. Moreover, we develop an adaptive and resilient framework that can counter the effect of realtime changes in the number of available VMs at the cloud server, the frequency and nature of arriving tasks on the revenue of the CSP.






§ INTRODUCTION


In recent years, due to the ubiquity of the internet, there has been an increasing trend towards offloading computing, control, and storage to the cloud instead of doing it locally at the client side <cit.>. This trend is expected to accentuate with the proliferation of the Internet of things (IoT) <cit.>. The IoT applications can request for cloud resources for a variety of different computational tasks. For instance, they can invoke machine learning and data analytics models already implemented in the cloud server to enable powerful features such as predictive analytics, video processing, and natural language processing. With a massive surge in the number of applications requesting the cloud for computational resources in the future, there will be a need for an efficient allocation and pricing mechanism at the cloud server. A cloud service provider (CSP) has several resources such as computing nodes, storage, databases, etc., that can be used remotely by IoT applications. Often, these resources are packaged into virtual machine (VM) instances that act as processing units. When the number of requesting applications is large and the available VMs are limited, as envisioned in massive IoT systems <cit.>, it is important to select which applications are serviced particularly when the allocation is planned for longer periods of time.

The challenges faced by the CSP in allocating the available VMs to requesting applications are twofold. Firstly, the available VMs at the CSP are limited, so it is important to allocate the most computationally intensive tasks to the available VMs in order to maximize the productivity of the IoT client applications and the generated revenue by charging them appropriately. However, the tasks arrive sequentially at the server and the CSP has to decide immediately to allocate a VM to it or to wait for a more valuable task in the immediate future. The challenge lies in the uncertainty about the nature of upcoming requests in the future. A computationally intensive task may not ever request for service while the low complexity tasks are refused service. It leads to an under-utilization of resources resulting in lower productivity and revenue of the CSP. On the other hand, if the VMs are allocated to low complexity tasks, then a high complexity task may request service in the future and has to be refused due to the unavailability of an VM at the cloud server.

Therefore, there is a need for a dynamically efficient mechanism for allocating and pricing the VMs that takes these tradeoffs into account. Fig. <ref> illustrates the sequential arrival of IoT computation requests at the CSP.



There has been considerable work in the literature towards resource allocation in cloud computing environments <cit.>. The focus is mainly on efficient resource management and load balancing for higher availability and performance <cit.> or resource allocation and pricing for revenue maximization <cit.>. Regarding dynamic pricing and revenue maximization, several works exist such as <cit.> which use price control to adjust demand levels. Others have used auction mechanisms to collect bids and allocate available computational resources such as <cit.>. However, most existing works on resource allocation in cloud computing do not take into account the sequential arrival of computing tasks and the uncertainty about the future. This is essential in the setting of cloud computing because the computational requests are spontaneous and the decision for allocation has to be made immediately upon arrival. A dynamically efficient policy for allocating resources to sequentially arriving agents in order to maximize social welfare was first proposed by Albright <cit.>. Consequently, a revenue maximizing approach towards sequential allocation of resources has been introduced in <cit.>. However, their work deals with heterogeneous resources and cannot be used to model situations with identical resources. In cloud-enabled IoT systems, often multiple identical resources such as VMs are available to be allocated to client applications. A framework for pricing the cloud for maximizing revenue is proposed in <cit.>. However, their solution is based on stochastic dynamic programming which cannot adapt in realtime scenarios. Our solution provides a dynamically optimal plug and play policy that can be pre-computed and used in realtime using a lookup table.




In this paper, we develop an adaptive and resilient dynamic resource allocation and pricing framework for cloud-enabled IoT systems. We present an optimal dynamic policy to filter incoming service requests by IoT applications based on the complexity of the tasks.

The qualification threshold for tasks is adaptive to the number of available VMs, the arrival rate of requests, and their average complexity. The optimal policy can be dynamically updated in order to maintain high expected revenues of the CSP.

Furthermore, the proposed framework is also able to adapt according to the changing availability of the VMs due to reprovisioning of resources for other applications or due to the effect of malicious attacks.









§ SYSTEM MODEL

We consider a CSP having a set of N_t ∈ℤ^+ available VMs at time t∈[0,T]. The VMs are identical and are characterized by their computational efficiency[The computational efficiency can be determined by evaluating the relative time taken by the VM to successfully execute a benchmark task.] denoted by q ∈ [0,1]. The CSP receives requests[Throughout the paper, we use the word `requests' to refer to computational tasks generated by IoT applications that arrive at the CSP for processing.] for computation by IoT client applications. These requests arrive sequentially at the cloud server according to a Poisson process with density λ∈ℝ^+ requests per unit time. Each task has computational complexity denoted by X ∈ℝ^+. The computational complexity can be measured in terms of the number of CPU cycles or equivalently the time required to complete a given computational task. The computational complexities of sequentially arriving tasks are considered to be independent and identically distributed (i.i.d.) random variables with probability density function (pdf) and cumulative distribution function (cdf) denoted by f_X(x)  and F_X(x) respectivley.

The utility of the i^th arriving client application with a task complexity of x_i, i ∈ℤ^+, that is allocated a VM with efficiency q, is measured by the product qx_i, which refers to the resulting value created by the allocation or the productivity.





Since the available VMs are limited, the CSP needs to allocate the VMs to only the high complexity arriving tasks in order to increase the total productivity of the clients as well as efficient utilization of available computational resources. Creating higher value sets the ground for the CSP to charge higher prices and hence generate more revenue.
However, the decision has to be taken immediately[We assume that the tasks are impatient and need to be processed immediately without delay.] upon arrival of the tasks without knowledge of tasks arriving in the future. Therefore, the CSP has the option to either allocate one of the available VMs or to refuse the requesting application.



 §.§ Allocation & Pricing Rule

In order to allocate available VMs to randomly arriving computational requests, we adapt the result from the sequential stochastic assignment literature, which is based on the Hardy-Littlewood-Polya inequality <cit.> and is stated by the following theorem:

If there are n VMs with computational efficiencies q_1, q_2, …, q_n such that 0 < q_1 ≤ q_2 ≤…≤ q_n, then there exists a set of functions

    0 = z_n+1(t) ≤ z_n(t) ≤…≤ z_1(t) ≤ z_0(t) = ∞.

such that it is optimal (in terms of social welfare) to assign a VM with efficiency q_i to an incoming task with complexity x if z_n-i+1(t) ≤ x ≤ z_n-i(t). Furthermore, if x < z_n(t), it is optimal not to allocate it.



In the case of identical objects, the CSP needs to set only a single dynamic threshold, which we refer to
as the qualification threshold, that allows it to decide whether to allocate a VM or not based on the nature of the arriving task. Let y_N_t(t) ∈ℝ^+, ∀ t ∈ [0,T] denote the threshold if N_t VMs are available for allocation at time t.
In other words, only the requests with x_i ≥ y_N_t(t), i ∈ℤ^+, will be allocated to an available VM at time t. 
The allocation process has to be completed within a finite time horizon denoted by T. Since the VMs have no commercial value if they remain idle or unallocated during the allocation period, therefore the threshold needs to be dynamic in order to efficiently generate revenue from available resources. The decision problem lies in that fact that it may be more valuable to assign a VM to a low complexity task than waiting for a high complexity task to arrive in the future which may not ever realize.





The next step is to develop a pricing scheme for the available VMs. Since all the VMs are identical in terms of their performance, therefore they must be priced equally. The threshold based allocation policy provides a natural method for pricing the available VMs. Since each arriving task that is successfully allocated a VM at time t receives a value of at least qy_N_t(t). Therefore, it is fair to charge the price 𝒫: [0,1] ×ℝ^+ × [0,T]→ℝ^+ to a qualified task for being processed by a VM as follows: 


    𝒫(q,y_N_t(t),t) = q y_N_t(t) + S(t),

where S(t) represents the constant additional pricing independent of the allocation. This pricing policy is implementable as any individually rational client will be willing to pay at least an amount equal to its received value. Note that S(t) can be used to adjust the prices due to external factors such as promotions, packages, pricing agreements, etc. In the following section, we provide the dynamically optimal allocation threshold and the resulting price charged by the CSP to allocated tasks.






§ METHODOLOGY
 
We will begin by quantifying the total expected revenue of the CSP and subsequently derive the optimal dynamic threshold that maximizes the revenue. The total expected revenue of the CSP ℛ: [0,1] ×ℝ^+ × [0,T]→ℝ^+ if N_t identical VMs with computational efficiency q are available at time t and a qualification threshold y_N_t(t) is used from time t onwards can be expressed as follows: 


    ℛ(q, y_N_t(t),t) = ∑_n=1^N_t q ∫_t^T y_N_t(s) h_n(s) ds + κ_T,

where h_n(t) is the density of waiting time until the n^th arrival of a qualifying task, i.e., having a task complexity greater than y_N_t(t), and κ_T is a constant factor due to the additional pricing function S(t). The density of waiting time can be expressed by the density of the n^th arrival in a non-homogeneous Poisson process with intensity λ̂(s) = λ (1 - F(y_N_t(s))). Consequently, the density can be written as follows <cit.>:



    h_n(s)    = λ̂(s) exp(- ∫_t^s λ̂(u) du ) (∫_t^s λ̂(u) du )^n-1/(n-1)! , t ≤ s ≤ T.


The objective is to select a time-varying threshold y_N_t(t) which maximizes the expected revenue functional given by (<ref>). The problem can be formally stated as follows:

    y_N_t(t)maximize      ℛ(q, y_N_t(t),t) 
       subject to       y_N_t(t) ≥ 0, ∀ t∈ [0,T].

Note that the optimization is over the space of functions where an optimal function y_N_t(t) is sought for a given number of available VMs at time t.

Our aim is to design the threshold function that strikes the optimal balance between the number of qualifying tasks and the generated revenue. In the sequel, we provide the optimal qualification threshold for maximum revenue generation by the CSP and the properties of the optimal policy.




 
If N_t VMs are available to the CSP at time t, computational requests arrive sequentially according to a Poisson process with intensity λ and the computational complexity of tasks are i.i.d. random variables with pdf f_X(x) and cdf F_X(x), then it is optimal to allocate an available VM to an incoming computational request if the complexity of an upcoming task x ≥ y_N_t(t). The optimal y_N_t(t) satisfies the following integral equation:



    y_N_t(t)  =   1 - F_X(y_N_t(t))/f_X(y_N_t(t)) +  λ∫_t^T (1 - F_X(y_N_t(s)))^2 /f_X(y_N_t(s)) J_N_t(t,s)ds,


where J_N_t(t,s) can be expressed as follows:

    J_N_t(t,s) = 1/∑_n=1^N_t1/(n-1)!(∫_t^s λ̂(u) du)^n-1×
       ∑_n=1^N_t1/(n-1)!( (∫_t^s λ̂(u) du)^n-1 - (n-1)(∫_t^s λ̂(u) du)^n-2).



See Appendix <ref>.











The behaviour of the optimal dynamic threshold for large number of available VMs is provided by the following corollary.

If the number of available VMs is large, then the revenue maximizing threshold becomes constant and the allocation mechanism reduces to a first price auction mechanism, i.e., allocate a VM to a task if the complexity is higher than the virtual valuation.


In the optimal allocation policy, if we let N_t →∞, then the optimal threshold solves the following integral equation:



    y_∞(t) =   1 - F_X(y_∞(t))/f_X(y_∞(t)) + ∫_t^T (1 - F_X(y_∞(t)))^2/f_X(y_∞(t))×
                           ( N_t →∞lim J_N_t(t,s) ) ds.


Now, N_t →∞lim J_N_t(t,s) can be evaluated as follows:



    N_t →∞lim J_N_t(t,s)    = ∑_n=1^∞H^n-1(s)/(n-1)!   -  ∑_n=1^∞(n-1)H^n-2(s)/(n-1)!/∑_n=1^∞H^n-1(s)/(n-1)!
       = e^H(s) - e^H(s)/e^H(s) = 0.


Therefore, it follows that y_∞(t) = 1 - F_X(y_∞(t))/f_X(y_∞(t)). Note that x - 1 - F_X(x)/f_X(x) is referred to as the virtual valuation of the agent of type x in mechanism design literature <cit.>. Hence, it can be concluded that if the number of available VMs is large, then only the virtual valuation of the arriving tasks can be recovered and the CSP is willing to offer the VMs for lowest possible threshold.













The behaviour of the dynamically optimal qualification threshold with a variation in the number of available VMs at time t can be summarized by the following theorem.

The qualification threshold of the tasks and consequently price of VMs decreases as the number of available VMs at the cloud server increases and vice versa, i.e., y_M_t(t) ≤ y_N_t(t) if M_t ≥ N_t, ∀ t.


See Appendix <ref>.






In the following section, we discuss how the dynamically optimal policy leads to an adaptive and resilient behaviour in the revenue of the CSP and describe the developed mechanism algorithmically.




§ ADAPTIVE AND RESILIENT ALLOCATION AND PRICING POLICY

The number of available VMs at the cloud server may change over time as some of them might become unavailable due to failure or malicious attacks <cit.>. The CSP might also destroy the created VMs in order to free up computational resources for other applications. On the other hand, previously allocated VMs might be released by applications or new VMs may be provisioned by the CSP in real time to accommodate higher demand. However, a change in the available number of VMs may affect the expected revenue of the CSP under a particular allocation and pricing policy particularly if there is a significant decrease in the number of remaining VMs. In order to reduce any negative impact on the expected revenue of the CSP, the proposed revenue maximizing framework will react to the changes in the available number of VMs by adapting the qualification threshold or equivalently the price.

Furthermore, the developed framework can react to changes in the frequency and the nature of computational requests. The optimal resilient policy is denoted by Π(λ̃_t, Ñ_t, t), where λ̃_t is the rate of arrival of requests and Ñ_t represents the number of available VMs at time t. Note that Ñ_t = N_t + η_t, where η_t ∈ℤ is the change in the number of available VMs at time t. The adaptive qualification threshold ỹ_N_t(t) can be pre-computed using the optimal policy framework presented earlier in this Section. The policy then becomes a lookup table that the CSP uses to allocate and price the upcoming tasks. Note that the variations in the inputs of the framework can be directly incorporated into the derived results. For instance, if η_t VMs enter/leave the system at time t, then it is equivalent to as if there were N_t + η_t available VMs at time t. Hence, the optimal threshold corresponding to N_t+η_t must be used for time t onwards for maximizing revenue.
































The algorithm proceeds as follows. While the allocation period has not expired and there is still an available VM at the CSP, if an IoT application requests for computation, then the first step is to evaluate the task complexity. Once the complexity is determined, it is compared against the decision threshold. However, the optimal threshold used will depend on the current situation at the CSP. Hence, the updated number of available VMs Ñ_t and the updated arrival rate of requests λ̃ is used to read off the optimal policy from the lookup table Π(λ̃_t, Ñ_t, t) at time t. A flow diagram is provided in Fig. <ref> to illustrate the sequence of the mechanism.








§ NUMERICAL RESULTS & DISCUSSIONS

In this section, we provide numerical results for the proposed adaptive and resilient optimal dynamic allocation and pricing framework. We assume a single CSP having N_t available VMs to allocate to arriving computational requests within an allocation time horizon of T = 12 hours. The number of available VMs available at time t=0, referred to as N_0 is set to be 100. The computational efficiency of the VMs is selected to be q = 1 without loss of generality. Note that the characteristics of the VMs is only relevant to the pricing policy but not the allocation.



The tasks arrive at the CSP according to a homogeneous Poisson process with intensity λ = 100 requests per hour unless otherwise stated.
We also assume that the complexity of sequentially arriving computational requests are distributed according to an exponential distribution with a mean of 1/α, i.e., f_X(x) = α e^-α x, and F_X(x) = 1 - e^-α x. For simplicity, we select α = 1, resulting in an average task complexity of 1. The optimal task qualification thresholds in this case if N_t VMs are available at time t can be obtained by the solution of the integral equation expressed by (<ref>). The equation can be solved numerically using the Picard fixed point iteration <cit.>. Fig. <ref> shows the dynamic thresholds for qualification of an arriving task for low (λ = 10) and high (λ = 100) arrival rates of the requests. It can be observed in general that the qualification thresholds decrease as the time approaches towards the terminal time. This is due to the fact that the valuable option of allocating an available VM to a higher complexity task reduces in probability. Furthermore, as we approach the horizon, it is more valuable to allocate a VM to a lower complexity task than to not allocate it at all. It can also be observed from Fig. <ref> that for lower arrival rates, the thresholds drop quickly as compared to the thresholds for the high arrival rates in Fig. <ref>. This is because the expected arrivals are lower in the former and hence the mechanism adjusts the thresholds to qualify more arrivals to tap the revenue potential. The associated pricing curves follow a similar trend as the allocation thresholds except that they are scaled by the characteristics of the VMs. However, in the considered situation, they are identical since q=1.

























Next we investigate the adaptive and resilient behaviour of the proposed mechanism.

A set of failures and capacity enhancements are simulated at fixed times. For instance, a loss of 15 VMs and 5 VMs is assumed to occur at t = 2 hours and t = 6 hours respectively. Similarly, new additions of 10 VMs and 5 VMs is assumed to occur at t = 4 hours and t = 8 hours. Note that when a loss of 15 VMs occurred at t=2 hours, the situation becomes equivalenlt to as if initially the CSP had 85 available VMs. Therefore from t = 2 onwards, the optimal revenue maximizing policy is to use the threshold and pricing corresponding to the N_0 = 85 curve. As the number of available VMs change over times, the optimal policy needs to be updated. The optimal dynamic allocation policy for the above mentioned events is shown by the bold line in Fig. <ref>. Notice that as the number of available VMs decreases, the allocation threshold and the price jumps in order to make up for the lost revenue. Similarly, if new VMs become available, the threshold and prices drop in order to strike a new balance between the qualifying tasks and the payment.





In Fig. <ref>, we show the behaviour of the adaptive and resilient mechanism on the expected revenue of the CSP in response to the variations in the number of available VMs at the cloud server. It can be observed that the adaptive strategy is able to maintain a high expected revenue despite variations in the number of available VMs. Note that during the times when there is a drop in the number of available VMs, the expected revenue does not fall as much due to a rectified allocation and pricing policy as illustrated in Fig. <ref>. Hence, it is shown that a timely rectification of allocation and pricing decision enables the mechanism to be adaptive and resilient against any significant changes in the available resources to the CSP.


























§ CONCLUSION

In this paper, we have proposed an adaptive and resilient dynamic revenue maximizing framework for cloud computing environments. The framework uses a threshold-based filtering policy making real time allocation and pricing decisions for sequentially arriving computational requests.



It has been shown that the framework is adaptive and resilient to changes in the number of available VMs or the statistical properties of the arrivals. The set of optimal policies can be pre-computed and used as a lookup table as conditions at the cloud server change over time. Therefore, the developed framework provides an optimal and implementable mechanism for allocation and pricing in cloud computing environments. Future directions in this line of work may include developing optimal allocation policies for multiple types of identical resources available at the CSP. Furthermore, the allocation framework can be extended to multiple layers such as in fog/edge computing paradigms.


















§ PROOF OF THEOREM <REF>
 
















Let H(s)= ∫_t^s λ̂(u) du = ∫_t^s λ( 1 - F_X(y_N_t(u)) ) du. Then the expected revenue at time t if N_t VMs are available can be written as follows:



    ℛ({q}_N_t,t) =    q ∫_t^T ∑_n=1^N_t1/(n-1)! F_X^-1(  1 - H^'(s)/λ) ×
            H^'(s) e^-H(s) (H(s))^n-1 ds + κ_T.


This functional can be optimized for the time varying threshold y_N_t(t) using the calculus of variations <cit.>. We denote the kernel of integration as 



    ℒ(s,H(s), H^'(s))  =   ∑_n=1^N_tH^' (s) e^-H(s) H^n-1(s)/(n-1)! F_X^-1(   1 - H^'(s)/λ).


The Euler-Lagrange equation <cit.> represents the necessary condition satisfied by H(s) to be a stationary function of the expected revenue R({q}_N_t,t) and can be written as follows: 



    ∂ℒ(s,H(s), H^'(s))/∂ H(s) - d/dt∂ℒ(s,H(s), H^'(s))/∂ H^'(s) = 0.


The partial derivatives and the condition satisfied by the resulting Euler-Lagrange equation are given by (<ref>), (<ref>), and (<ref>) respectively. The expression in (<ref>) can be further reduced as follows: 



    2 H^''(s)  -  (H^'(s))^2 ∑_n=1^N_t1/(n-1)!( H^n-1(s) - (n-1)H^n-2(s))/∑_n=1^N_t1/(n-1)! H^n-1(s)   +  
        H^'(s) H^''(s) f_X^'(F_X^-1(1 - H^'(s)/λ))/λ f^2_X ( F_X^-1(1 - H^'(s)/λ) )  = 0.


Let J_N_t(t,s) = ∑_n=1^N_t1/(n-1)!( H^n-1(s) - (n-1)H^n-2(s))/∑_n=1^N_t1/(n-1)!  H^n-1(s). Then, plugging back H(s) = ∫_t^s λ( 1 - F_X(y_N_t(u)) ) du results in the following: 



    -2  y_N_t^'(s) - λ (1 - F_X(y_N_t(s)))^2 J_N_t(t,s)/f(y_N_t(s)) - 
       (1 - F_X(y_N_t(s))) y_N_t^'(s) f^'_X(y_N_t(s))/f^2_X(y_N_t(s)) = 0


It can be further expressed as follows: 



    - y_N_t^'(s) - y_N_t^'(s) ( 1 + (1 - F_X(y_N_t(s))) f^'_X(s)/(f_X(y_N_t(s)))^2) = 
       λ (1 - F_X(y_N_t(s)))^2 J_N_t(t,s)/f_X(y_N_t(s)),


Since 
d/ds( 1 - F_X(y_N_t(s)/f(y_N_t(s))) = -y^'_1(s) ( 1 + (1 - F_X(y_N_t(s))) f_X^'(y_N_t(s))/(f_X(y_N_t(s)))^2), so the condition in (<ref>) can be written as follows: 



    d/ds( 1 - F_X(y_N_t(s))/f_X(y_N_t(s)))  =    y^'_1(s) + λ(1 - F_X(y_N_t(s)))^2 /f_X(y_N_t(s))J_N_t(t,s) .


Integrating both sides with respect to s from t to T results in the following: 



    ( 1 - F_X(y_N_t(T))/f_X(y_N_t(T))) - ( 1 - F_X(y_N_t(t))/f_X(y_N_t(t))) = y_N_t(T) - 
        y_N_t(t) +   λ∫_t^T  (1 - F_X(y_N_t(s)))^2 /f_X(y_N_t(s))J_N_t(t,s) ds.


Using the boundary condition, y_N_t(T) = 1 - F_X(y_N_t(T))/f(y_N_t)(T), i.e., at the terminal time only the virtual valuation of the users can be recovered, it follows that the cutoff curve y_N_t(t) satisfies the equation given by Theorem <ref>.













§ PROOF OF THEOREM <REF>

 
First we need to show that for {M_t,N_t ∈ℤ^+ : M_t ≥ N_t}, J_M_t(t,s) ≤ J_M_t(t,s), ∀ t,s. To do this we will show that J_N_t + 1(t,s) ≤ J_N_t(t,s). It is equivalent to showing that J_N_t + 1(t,s) - J_N_t(t,s)≤ 0, i.e., 



    ∑_n=1^N_t + 1H^n-1(s)/(n-1)!   -  ∑_n=1^N_t+1(n-1)H^n-2(s)/(n-1)!/∑_n=1^N_t+1H^n-1(s)/(n-1)!   -  
    ∑_n=1^N_tH^n-1(s)/(n-1)!   -  ∑_n=1^N_t(n-1)H^n-2(s)/(n-1)!/∑_n=1^N_tH^n-1(s)/(n-1)!≤ 0.


It can be further expressed as follows: 



    ( ∑_n=1^N_tH^n-1(s)/(n-1)!) (H^N_t(s) - N_t H^N_t-1(s)/N_t!) - 
    ( ∑_n=1^N_tH^n-1(s) - (n-1)H^n-2(s)/(n-1)!)H^N_t(s)/N_t!≤ 0.


Expanding the condition results in the following: 



    ∑_n=1^N_t( H^N_t + n -1(s) - N_t H^N_t + n -2(s) - H^N_t + n - 1(s) /(n-1)! + . 
       . (n-1)H^N_t + n -2(s)/(n-1)!)≤ 0.


It is equivalent to the following condition:



    ∑_n=1^N_tH^N_t + n -2(s)(n+1-N_t)/(n-1)≤ 0,


which is true since (n+1-N_t) ≤ 0, ∀ n = 1, …, N_t. Therefore, it is evident that J_N_t + 1(t,s) ≤ J_N_t(t,s). Using induction it can be shown that the inequality J_M_t(t,s) ≤ J_N_t(t,s) holds for general M_t and N_t such that M_t ≥ N_t, ∀ t. From Theorem <ref>, the result follows directly with the assumption of increasing virtual valuations, i.e., x - 1 - F_X(x)/f_X(x) is increasing in x.










IEEEtran




