# Variables Reduction in Sequential Resource Allocation Problems
## 6 The Variables Reduction Technique  
This section is devoted to the derivation of Theorem 1. Let us prepare the proof by gradually showing auxiliary results. Our arguments rely on convexity of the functions \((V_{t})_{t=0}^{T}\) from (9)-(11). It turns out that, based on the assumption  
\[ \begin{array}{l}\tilde{V}_{t+1}(\cdot,z)\text{ is convex and non-decreasing on }I\\ \text{ and }\tilde{V}_{t+1}(\cdot,z)=+\infty\text{ on }\mathbb{R}\setminus I, \text{ for all }z\in\mathbb{R}^{d},\end{array}  \tag{65}\]  
the same properties can be deduced for \(\tilde{V}_{t}(\cdot,z)\) as formulated in the following lemma. Lemma 1: _Given costs and resource consumption (18), let \(t\in\{0,\ldots,T-1\}\), suppose that (65) holds and consider \(V_{t}(\cdot,z)\) defined by (11). If (22) holds then \(V_{t}(\cdot,z)\) is non-decreasing on \(I\) for all \(z\in\mathbb{R}^{d}\). If in addition (24) is satisfied, then \(V_{t}(\cdot,z)\) is non-decreasing and convex on \(I\) for all \(z\in\mathbb{R}^{d}\)._  
Proof: Given \(z\in\mathbb{R}^{d}\), \(e,e^{\prime}\in I\) with \(e<e^{\prime}\), and arbitrary \(\xi^{\prime}\in\Xi\) there exists by (22) an action \(\xi\in\Xi\) with  
\[e+E_{t}^{e,z}(\xi)=e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime})\text{ and }C_{t}^{e,z}(\xi)\leq C_{t}^{e^{\prime},z}(\xi^{\prime})\]  
which gives  
\[C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z)\leq C_{t}^{e^{\prime},z }(\xi^{\prime})+\tilde{V}_{t+1}(e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime} ),z)\]  
and shows \(V_{t}(e,z)\leq V_{t}(e^{\prime},z)\) by minimization in \(\xi\) and \(\xi^{\prime}\) over \(\Xi\). Now we turn to the convexity. Using the infimum in (11) for each \(\delta>0\), there exist \(\xi,\xi^{\prime}\in\Xi\) such that  
\[\frac{\delta}{2}+V_{t}(e,z) \geq C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z),\] \[\frac{\delta}{2}+V_{t}(e^{\prime},z) \geq C_{t}^{e^{\prime},z}(\xi^{\prime})+\tilde{V}_{t+1}(e^{\prime} +E_{t}^{e^{\prime},z}(\xi^{\prime}),z).\]  
Please note that these values are finite due to (20), which means that  
\[e+E_{t}^{e,z}(\xi)\in I,\quad e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime})\in I.\]  
That is, by convex linear combinations of the activities (\(\Xi\) is convex by (24)) and resource levels we obtain  
\[\xi^{(\lambda)} =\lambda\xi+(1-\lambda)\xi^{\prime}\in\Xi\] \[e^{(\lambda)} =\lambda e+(1-\lambda)e^{\prime}\in I.\]  
Now, by convexity of costs functions (24) it holds that  
\[\lambda C_{t}^{e,z}(\xi)+(1-\lambda)\ C_{t}^{e^{\prime},z}(\xi^{\prime})\geq C _{t}^{e^{(\lambda)},z}(\xi^{(\lambda)})\]  
and using assumption (65) we conclude  
\[\lambda\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z)+(1-\lambda)\tilde{V }_{t+1}(e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime}),z)\geq\] \[\geq\tilde{V}_{t+1}(\lambda e+(1-\lambda)e^{\prime}+\lambda E_{t} ^{e,z}(\xi)+(1-\lambda)E_{t}^{e^{\prime},z}(\xi^{\prime}),z)\geq\] \[C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z)\leq C_{t}^{e^{\prime},z }(\xi^{\prime})+\tilde{V}_{t+1}(e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime} ),z)\]0  
From this, we proceed with  
\[C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z)\leq C_{t}^{e^{\prime},z }(\xi^{\prime})+\tilde{V}_{t+1}(e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime} ),z)\]1 \[C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z)\leq C_{t}^{e^{\prime},z }(\xi^{\prime})+\tilde{V}_{t+1}(e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime} ),z)\]2 \[C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z)\leq C_{t}^{e^{\prime},z }(\xi^{\prime})+\tilde{V}_{t+1}(e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime} ),z)\]3  
that shows the desired convexity.