In this section, we show that all Nash equilibrium strategies are threshold strategies of type (
4):
retailer i reorders only if the number of active retailers is greater than or equal to a given threshold. For the general model explained in Sect.
3, proving that strategies at a Nash equilibrium have a threshold structure is not straight forward, for that reason in this section the results are given for a single retailer
i. To show this, in the next subsection we prove the optimality of the (
s,
S)-like strategies via
\({\mathscr {K}}\)-convex analysis (see the definition in [
5], chapter 4). We recall from [
5] that (
s,
S) strategies are strategies where replenishments occur anytime the inventory level goes below a lower threshold
s. Replenishments bring back the inventory level up to a higher threshold
S [
6]. This is formally stated below where
\(\mu (.)\) is the strategy,
x the inventory, and
s and
S lower and upper thresholds, respectively:
$$\begin{aligned} \mu (x)=\left\{ \begin{array}{ll} S-x &{} \qquad \hbox {if} \quad x < s,\\ 0 &{} \qquad \hbox {if} \quad x \ge s. \end{array}\right. \end{aligned}$$
(10)
We refer to (
s,
S)-like strategies as (
s,
S) strategies whose thresholds depend on the players and on time, i.e., we will have
\(s:=s_i^t\) and
\(S:=S_i^t\) for fixed
i and
t.
Let
\(K^t(u_{-i}^t)=\frac{K}{1 + \sum \nolimits _{i\in \varGamma ,j\ne i} \delta (u_j^t)}\) be the transportation cost charged to each retailer
i that replenishes at stage
t. Fix decisions
\(u_{-i}^0,\ldots ,u_{-i}^{N-1}\) of all retailers other than
i over the horizon and denote such decisions
\({\bar{u}}_{-i}^0,\ldots ,{\bar{u}}_{-i}^{N-1}\). Similarly, denote the resulting transportation costs by
\(K^0,\ldots ,K^{N-1}\). Note that
\(K^t\) is a function of
\(u_{-i}^t\) but for ease of notation sometimes we omit the dependence. Then, let us rewrite the stage cost (
2) for retailer
i as
$$\begin{aligned} g_{i}(x_i^t,u_i^t,{\bar{u}}_{-i}^t)&= K^t \delta (u_i^t)+cu_i^t\\&\quad + p {\mathbb {E}} \{ \max (0,-x_i^{t+1}) \} +h {\mathbb {E}} \{ \max (0,x_i^{t+1}) \}. \end{aligned}$$
Now, we can write the cost-to-go from stage
t to the final stage recursively using dynamic programming and the Bellman equation. Let us use the superscript
t to indicate the iteration. Then, we have
$$\begin{aligned} v^{t}_{i}(x_i^t,{\bar{u}}_{-i}^{t\sim N-1})&=\min _{u_{i}^t\in U} [g_{i}(x_i^t,u_i^t,{\bar{u}}_{-i}^t) \nonumber \\&\quad \, + {\mathbb {E}} \{ v^{t+1}_{i}(x_i^{t+1},{\bar{u}}_{-i}^{t+1\sim N-1}) \} ], \;\; t= 0,\ldots N-1, \end{aligned}$$
(11)
$$\begin{aligned} {J_i^N(x_i^N)=0}, \end{aligned}$$
(12)
where
\(J^{0}_{i}(x_i^0,{\bar{u}}_{-i}^0)\) is equal to the cost
\(J_{i}(x_i^0,{u}_{-i}^0)\) introduced in (
3). Being
\(y_i^t=x_i^t+u_i^t\), the instantaneous inventory position, i.e., the inventory level just after the order has been issued, let us define the new function
$$\begin{aligned} G^{t}_{i}(y_i^t,\,{\bar{u}}_{-i}^{t+1\sim N-1})&= cy_i^t+p {\mathbb {E}} \{ \max (0,-(y_i^t-\omega _{i}^t)) \} \\&\quad +\,h {\mathbb {E}} \{ \max (0,y_i^t-\omega _i^t) \} + {\mathbb {E}} \{ v_{i}^{t+1}(x_i^{t+1},{\bar{u}}_{-i}^{t+1\sim N-1}) \}, \end{aligned}$$
and rewrite the Bellman Eq. (
11) as follows
$$\begin{aligned} v_{i}^{t}(x_{i}^t,{\bar{u}}_{-i}^{t\sim N-1})&=-c_{i}x_{i}^t+\min _{y_{i}^t\ge x_i^t}[K^t(u_{-i}^t)\nonumber \\&\quad +\,G_{i}^t(y_i^t,{\bar{u}}_{-i}^{t+1\sim N-1}),\,G_i^t(x_i^t,{\bar{u}}_{-i}^{t+1\sim N-1})]. \end{aligned}$$
(13)
Note that if we can show that
\(v_i^{t+1}\) is
\({\mathscr {K}}\)-convex with
\({\mathscr {K}} = K^t\) then
\(G_i^t\) is also
\({\mathscr {K}}\)-convex for
\({\mathscr {K}} = K^{t}\) and the Bellman Eq. (
13) has a unique minimizer. Indeed, it has been proved in [
5], chapter 4.2, that
\({\mathscr {K}}\)-convexity of
\(G_i^t(y_i^t,{\bar{u}}_{-i}^{t+1})\) implies
\({\mathscr {K}}\)-convexity of
\(v_i^t(x_i^t,{\bar{u}}_{-i}^t)\). This represents a
sufficient optimality condition for the (
s,
S)-like strategies with thresholds depending on time
t, that is,
\(s:=s_i^t\) and
\(S:=S_i^t\), where
\(s_i^t\) and
\(S_i^t\) satisfy:
$$\begin{aligned} S_i^t= & {} \arg \min _\gamma G_i^t(\gamma ,{\bar{u}}_{-i}^{t+1\sim N-1}),\\ G_i^t(s_i^t,{\bar{u}}_{-i}^{t+1\sim N-1})= & {} G_i^t(S_i^t,{\bar{u}}_{-i}^{t+1\sim N-1})+K^t(u_{-i}^t). \end{aligned}$$
The meaning of
\(s_i^t\) and
\(S_i^t\) is exactly the same as in the (
s,
S) strategies (cfg. [
5]), that is,
\(s_i^t\) represents the minimum threshold on inventory level below which retailers replenish to restore the inventory up to level
\(S_i^t\). Now, let us call
\({\underline{s}}_i^t\), the threshold which corresponds to the assumption that the
ith retailer is charged the whole transportation cost, i.e.,
$$\begin{aligned} G_i^t\left( {\underline{s}}_i^t,{\bar{u}}_{-i}^{t+1 \sim N-1}\right) =G_i^t\left( S_i^t,{\bar{u}}_{-i}^{t+1 \sim N-1}\right) +K. \end{aligned}$$
In the above condition, we have set
\(K^t=K\).
Analogously, let us denote by
\({\overline{s}}_i^t\) the threshold computed as if all retailers would share equally the transportation cost, i.e.,
$$\begin{aligned} G_i^t({\overline{s}}_i^t,{\bar{u}}_{-i}^{t+1 \sim N-1})=G_i^t(S_i^t,{\bar{u}}_{-i}^{t+1 \sim N-1})+\frac{K}{n}. \end{aligned}$$
In essence, in the condition above, each retailer is charged a transportation cost
\(K^t=\frac{K}{n}\), namely one
nth of the full cost
K. Hence, we have
\({\underline{s}}_i \le s_i^t\le {\overline{s}}_i\).
Proof
The proof is by induction. Assume
\(J_i^N(x_i^N)=0\), and consider the convex function
$$\begin{aligned} G^{N-1}_{i}\left( y_{i}^{N-1},{\bar{u}}_{-i}^N\right)&= cy_{i}^{N-1}+p {\mathbb {E}} \{ \max \left( 0,-\left( y_{i}^{N-1}-\omega _{i}^{N-1}\right) \right) \} \nonumber \\&\quad +\, h {\mathbb {E}} \{ \max \left( 0,y_{i}^{N-1}-\omega _{i}^{N-1}\right) \} . \end{aligned}$$
(14)
Then, we say that
\(G^{N-1}_i(\cdot )\) is convex and hence, it is also
\({\mathscr {K}}\)-convex where
\({\mathscr {K}}=K^{N-1}\) as shown in Fig.
1. Here, we also use the notation
$$\begin{aligned} H_i^{N-1}(x_i)&:=p {\mathbb {E}} \{ \max (0,-(x_{i}^{N-1}-\omega _{i}^{N-1}) \} \\&\quad +\,h {\mathbb {E}} \{ \max (0,x_{i}^{N-1}-\omega _{i}^{N-1}) \}. \end{aligned}$$
The above reasoning on
\({\mathscr {K}}\)-convexity implies that the piecewise linear function
$$\begin{aligned} v_{i}^{N-1}\left( x_{i}^{N-1},{\bar{u}}_{-i}^{N-1}\right)&=-c_{i}x_{i}^{N-1} +\min _{y_{i}^{N-1}\ge x_i^{N-1}}\left[ K^{N-1}\left( u_{-i}^{N-1}\right) \right. \nonumber \\&\quad \left. +\,G_{i}^{N-1}\left( y_i^{N-1},{\bar{u}}_{-i}^N\right) , G_i^{N-1}\left( x_i^{N-1},{\bar{u}}_{-i}^N\right) \right] \end{aligned}$$
(15)
is
\(K^{N-1}\)-convex, with a global minimum at
\({S_i^{N-1}}:= \arg \min _{\gamma } G^{N-1}_{i}(\gamma ,{\bar{u}}_{-i}^N)\) (in the deterministic case if the cost of purchase is relatively small then
\({S_i^{N-1}}=\omega _i^{N-1}\)) (see, e.g., Fig.
1).
To obtain \(S_i^{N-1}\), let a probability distribution function \(\phi ^{N-1}: {\mathbb {Z}}_+ \rightarrow [0,1]\) be given, namely \(\omega \mapsto \phi ^{N-1}(\omega )\) where \(\phi ^{N-1}(\omega )\) is the probability that \(\omega _i^{N-1} = \omega \) for all \(\omega \in {\mathbb {Z}}_+\).
Then, the cost of reordering is given by
$$\begin{aligned}&K^{N-1}(u_{-i}^{N-1}) -c_{i}x_{i}^{N-1} +G_{i}^{N-1}(\gamma ,{\bar{u}}_{-i}^N) \\&\quad = K^{N-1}(u_{-i}^{N-1}) + c_i u_{i}^{N-1} \\&\qquad +p {\mathbb {E}} \{ \max (0,-(\gamma -\omega _{i}^{N-1}))\} + h {\mathbb {E}} \{ \max (0,\gamma -\omega _{i}^{N-1}) \} \\&\quad = K^{N-1}(u_{-i}^{N-1}) + c_i ( \gamma - x_{i}^{N-1} ) + h \mathbf{E}_h^{N-1}(\gamma ) + p {\mathbf {E}}_s^{N-1}(\gamma ), \end{aligned}$$
where
\({\mathbf {E}}_h^t(\gamma )\) and
\({\mathbf {E}}_s^t(\gamma )\) are the expected holding and shortage, respectively, defined as:
$$\begin{aligned} {\mathbf {E}}_h^t(\gamma ):={\mathbb {E}} \left\{ \max \left( 0,\gamma -\omega _{i}^t\right) \right\} , \end{aligned}$$
$$\begin{aligned} {\mathbf {E}}_s^t\left( \gamma ):={\mathbb {E}}\left\{ \max (0,-\left( \gamma -\omega _{i}^t\right) \right) \right\} . \end{aligned}$$
Let the discrete difference operator be given,
\(\frac{{\text {d}}}{{\text {d}}S}\) and let us apply such an operator to function
\( G^{N-1}_{i}\left( \gamma ,{\bar{u}}_{-i}^N\right) = c_i \left( \gamma - x_{i}^{N-1} \right) + h {\mathbf {E}}_h(\gamma ) + p {\mathbf {E}}_s(\gamma ). \) Then, we have
$$\begin{aligned} \frac{\text {{d}}}{\text {{d}}\gamma } G^{N-1}_{i}\left( \gamma ,{\bar{u}}_{-i}^N\right)&:= G^{N-1}_{i}\left( \gamma +1,{\bar{u}}_{-i}^N\right) - G^{N-1}_{i}\left( \gamma ,{\bar{u}}_{-i}^N\right) \\&\quad = c_i + h \varPhi ^{N-1}_\omega [\gamma ] - p\left( 1 - \varPhi ^{N-1}_\omega [\gamma ]\right) . \end{aligned}$$
where
$$\begin{aligned} \varPhi ^t_\omega [\gamma ]:=\sum \nolimits _{\omega =0}^\gamma \phi ^t_{\omega }, \quad 1- \varPhi ^t_\omega [\gamma ]:=\sum \nolimits _{\omega =\gamma +1}^\infty \phi ^t_{\omega }. \end{aligned}$$
In the above equations, we make use of the following conditions
$$\begin{aligned} \begin{array}{ll} \sum \nolimits _{\omega =0}^{\gamma +1 }(\gamma +1 -\omega ) \phi ^{N-1}_{\omega } = \sum \nolimits _{\omega =0}^{\gamma }(\gamma +1 -\omega ) \phi ^{N-1}_{\omega } \\ \qquad = \sum \nolimits _{\omega =0}^{\gamma }(\gamma -\omega ) \phi ^{N-1}_{\omega } + \sum \nolimits _{\omega =0}^{\gamma } \phi ^{N-1}_{\omega },\\ \sum \nolimits _{\omega =\gamma +2}^\infty (\omega - \gamma -1) \phi ^{N-1}_{\omega }= \sum \nolimits _{\omega =\gamma +1}^\infty (\omega - \gamma -1) \phi ^{N-1}_{\omega } \\ \qquad = \sum \nolimits _{\omega =\gamma +1}^\infty (\omega - \gamma ) \phi ^{N-1}_{\omega } - \sum \nolimits _{\omega =\gamma +1}^\infty \phi ^{N-1}_{\omega }.\end{array} \end{aligned}$$
(16)
The order-up-to level
\(S_i^{N-1}\) is the optimal
\(\gamma \), which is obtained from solving
$$\begin{aligned}&\min _\gamma \, \left\{ \gamma | \, \frac{\text {d}}{{\text {d}}\gamma } G^{N-1}_{i}\left( \gamma ,{\bar{u}}_{-i}^N\right) \ge 0\right\} \\&\quad = \min _\gamma \,\left\{ \gamma | \, c_i + h \varPhi ^{N-1}_\omega [\gamma ] - p \left( 1 - \varPhi ^{N-1}_\omega [\gamma ]\right) \ge 0\right\} . \end{aligned}$$
From the above, we then obtain
$$\begin{aligned} S_i^{N-1} = \arg \min _\gamma \Big \{\gamma | \, \varPhi ^{N-1}_\omega [\gamma ] \ge \frac{-c_i + p }{h +p} \Big \}. \end{aligned}$$
To obtain
\(s_i^{N-1}\), let us consider the cost of not reordering, which is given by
$$\begin{aligned} -c_{i}x_{i}^{N-1} +G_{i}^{N-1}(x_{i}^{N-1},{\bar{u}}_{-i}^N)&= p {\mathbb {E}} \{ \max (0,-(x_{i}^{N-1}-\omega _{i}^{N-1}))\} \\&\quad +\, h {\mathbb {E}} \{ \max (0,x_{i}^{N-1} -\omega _{i}^{N-1}) \} \\&= h {\mathbf {E}}_h(x_{i}^{N-1}) + p {\mathbf {E}}_s(x_{i}^{N-1}) \end{aligned}$$
Also, we have
$$\begin{aligned} s_i^{N-1}&:= \arg \min _{x_{i}^{N-1}} \left\{ x_{i}^{N-1} | \, h {\mathbf {E}}_h\left( x_{i}^{N-1}\right) + p {\mathbf {E}}_s\left( x_{i}^{N-1}\right) \right. \\&\le K^{N-1}\left( u_{-i}^{N-1}\right) -c_i \left( S_{i}^{N-1} - x_{i}^{N-1}\right) \\&\left. \quad +\, h {\mathbf {E}}_h\left( S_{i}^{N-1}\right) + p {\mathbf {E}}_s\left( S_{i}^{N-1}\right) \right\} . \end{aligned}$$
Now, we are going to assume that the statement is true for some
\(t=m\), and we are going to proof that it is also valid for
\(t=m-1\).
Consider now the convex function (see Fig.
2 which illustrate the example of
\(t=N-2\))
$$\begin{aligned} G_i^{m-1}(y_{i}^{m-1},{\bar{u}}_{-i}^{m})&= c_iy_{i}^{m-1}+p {\mathbb {E}} \left\{ \max \left( 0,-\left( y_{i}^{m-1}-\omega _{i}^{m-1}\right) \right) \right\} \nonumber \\&\quad +\,h {\mathbb {E}} \left\{ \max \left( 0,y_{i}^{m-1}-\omega _{i}^{m-1}\right) \right\} + {\mathbb {E}} \left\{ v_{i}^{m}\left( x_i^{m},{\bar{u}}_{-i}^{m}\right) \right\} \nonumber \\&= c_i y_{i}^{m-1} + h {\mathbf {E}}_h\left( y_{i}^{m-1}\right) + p {\mathbf { E}}_s\left( y_{i}^{m-1}\right) \nonumber \\&\quad + \sum \nolimits _{\omega =0}^{\infty } v_{i}^{m}\left( y_{i}^{m-1}-\omega , {\bar{u}}_{-i}^{m}\right) \phi ^{m-1}_{\omega }. \end{aligned}$$
(17)
We know that
\(G_i^{m-1}\) is
\({\mathscr {K}}\)-convex, with
\({\mathscr {K}}=K^{m-1}\). This property implies that the function
$$\begin{aligned} v_{i}^{m-1}\left( x_{i}^{m-1},{\bar{u}}_{-i}^{m-1}\right)&= -c_{i}x_{i}^{m-1}+\min _{y_{i}^{m-1}\ge x_i^{m-1}}\left[ K^{m-1}\left( u_{-i}^{m-1}\right) \right. \nonumber \\&\quad \left. +\,G_{i}^{m-1}\left( y_{i}^{m-1},{\bar{u}}_{-i}^{m}\right) , G_{i}^{m-1}\left( x_{i}^{m-1},{\bar{u}}_{-i}^{m}\right) \right] , \end{aligned}$$
(18)
is
\(K^{m-1}\)-convex, with a global minimum at
\(S_i^{m-1}:=\) \(argmin_{\gamma }G_i^{m-1}(\gamma ,{\bar{u}}_{-i}^m)\). It is important to notice that we can ensure the existence of a unique minimum value in (
18) thanks to the nondecreasing property of
\(K^{m-1}\).
The cost of reordering for
\(t=m-1\) is given by
$$\begin{aligned}&K^{m-1}\left( u_{-i}^{m-1}\right) -c_{i}x_{i}^{m-1} +G_{i}^{m-1}\left( \gamma ,{\bar{u}}_{-i}^m\right) \\&\quad = K^{m-1}\left( u_{-i}^{m-1}\right) + c_i u_{i}^{m-1} \\&\qquad +p {\mathbb {E}} \left\{ \max \left( 0,-\left( \gamma -\omega _{i}^{m-1}\right) \right) \right\} + h {\mathbb {E}} \left\{ \max \left( 0,\gamma -\omega _{i}^{m-1}\right) \right\} \\&\quad = K^{m-1}(u_{-i}^{m-1}) + c_i \left( \gamma - x_{i}^{m-1} \right) + h \mathbf{E}_h^{m-1}(\gamma ) + p {\mathbf {E}}_s^{m-1}(\gamma ). \end{aligned}$$
Applying operator
\(\frac{{\text {d}}}{{\text {d}}\gamma }\) to function
\(G_i^{m-1}(\gamma ,{\bar{u}}_{-i}^m)\), we have
$$\begin{aligned} \frac{\text {d}}{\text {d}\gamma } G^{m-1}_{i}(\gamma ,{\bar{u}}_{-i}^m)&:= G^{m-1}_{i}\left( \gamma +1,{\bar{u}}_{-i}^m\right) - G^{m-1}_{i}\left( \gamma ,{\bar{u}}_{-i}^m\right) \\&= c_i + h \varPhi ^{m-1}_\omega [\gamma ] - p \left( 1 - \varPhi ^{m-1}_\omega [\gamma ]\right) + \\&\quad \sum \nolimits _{\omega =0}^{\infty } \left[ v_{i}^{m}(\gamma +1-\omega , \cdot ) - v_{i}^{m}\left( \gamma -\omega , \cdot \right) \right] \phi ^{m-1}_{\omega }. \end{aligned}$$
Hence, the order-up-to level
\(S_i^{m-1}\) is the optimal
\(\gamma \), which is obtained from solving
$$\begin{aligned} S_i^{m-1}&= \arg \min _\gamma \,\left\{ \gamma | \, c_i + h \varPhi ^{m-1}_\omega [\gamma ] - p \left( 1 - \varPhi ^{m-1}_\omega [\gamma ]\right) \right. \\&\left. \quad + \sum \nolimits _{\omega =0}^{\infty } \left[ v_{i}^{m}\left( \gamma +1-\omega , \cdot \right) - v_{i}^{m}\left( \gamma -\omega , \cdot \right) \right] \phi ^{m-1}_{\omega } \ge 0\right\} . \end{aligned}$$
To obtain
\(s_i^{m-1}\), let us consider the cost of not reordering, which is given by
$$\begin{aligned}&-c_{i}x_{i}^{m-1} +G_{i}^{m-1}\left( x_{i}^{m-1},{\bar{u}}_{-i}^{m}\right) \\&\quad = h {\mathbf {E}}_h\left( x_{i}^{m-1}\right) + p {\mathbf {E}}_s(x_{i}^{m-1}) + \sum \nolimits _{\omega =0}^{\infty } v_{i}^{m}\left( x_{i}^{m-1}-\omega , {\bar{u}}_{-i}^{m}\right) \phi ^{m-1}_{\omega }. \end{aligned}$$
Then, we have
$$\begin{aligned} s_i^{m-1}&:= \arg \min _{x_{i}^{m-1}} \left\{ x_{i}^{m-1} | \, -c_{i}x_{i}^{m-1} +G_{i}^{m-1}(x_{i}^{m-1} ,{\bar{u}}_{-i}^{m}) \right. \\&\left. \quad + \sum \nolimits _{\omega =0}^{\infty } v_{i}^{m}(x_{i}^{m-1}-\omega , {\bar{u}}_{-i}^{m}) \phi ^{m-1}_{\omega }\right. \\&\left. \le K^{m-1}(u_{-i}^{m-1})-c_{i}S_{i}^{m-1} +G_{i}^{m-1}(S_{i}^{m-1},{\bar{u}}_{-i}^{m})\right. \\&\left. \quad + \sum \nolimits _{\omega =0}^{\infty } v_{i}^{m}(S_{i}^{m-1}-\omega , {\bar{u}}_{-i}^{m}) \phi ^{m-1}_{\omega }\right\} . \end{aligned}$$
The above can be rewritten as
$$\begin{aligned} s_i^{m-1}&:= \arg \min _{x_{i}^{m-1}} \Big \{x_{i}^{m-1} | \, h {\mathbf {E}}_h(x_{i}^{m-1}) + p {\mathbf {E}}_s(x_{i}^{m-1}) \\&\quad + \sum \nolimits _{\omega =0}^{\infty } v_{i}^{m}(x_{i}^{m-1}-\omega , {\bar{u}}_{-i}^{m}) \phi ^{m-1}_{\omega } \\&\le K^{m-1}(u_{-i}^{m-1})-c_i ( S_{i}^{m-1} - x_{i}^{m-1} ) \\&\quad + h {\mathbf {E}}_h(S_{i}^{m-1}) + p {\mathbf { E}}_s(S_{i}^{m-1})\\&\quad + \,\sum \nolimits _{\omega =0}^{\infty } v_{i}^{m}(S_{i}^{m-1}-\omega , {\bar{u}}_{-i}^{m}) \phi ^{m-1}_{\omega } \Big \}. \end{aligned}$$
Thus by induction backwards in time, we have proved Theorem
1.
\(\square \)
In the following result on a single-stage inventory game (where we have dropped index t), we reinterpret a threshold on the inventory level as a threshold on the number of “active retailers”.