2 Min-max and newsboy model

2.1 Description of the Newsboy Problem

The "newsboy problem" can be stated as follows (using the Scarf's notations). We have the opportunity to purchase now an amount $y$ of some good, at unitary cost $c$ (regardless of the quantity purchased). It is assumed that the future demand distribution is exactly known by its cumulative density function $\Phi \left(\xi \right)$, that the future unit selling price $r$ is known and independent of the number sold and that non sold units are discarded. We have not considered the possibility of a salvation value $s$, because the only modification is to transform $c, r$ into $c-s, r-s$ (Mileff and Nehézg, 2006).

When the actual demand $\xi$ has occurred, the gain is $G\left(y, \xi \right)=r \min\left(y, \xi \right)-c y$. At ordering time, we have to consider its expected value: $G\left(y, \Phi \right)\doteq\mathrm{E}\left(G\left(y, \xi \right)\right)$. Defining, for a given $y$, the overflow probability $\theta_{y}$, the "lower mean" $\xi ^{o}_{y}$ and the "upper mean" $\xi ^{u}_{y}$ by:

$$\theta_{y}\doteq Pr\: \left(\xi >y\right)$$

$$\xi ^{u}_{y}\doteq\mathrm{E}\left(\xi \mid\xi >y\right)\quad;\quad\xi ^{o}_{y}\doteq\mathrm{E}\left(\xi \mid\xi <y\right)$$

and comparing with the naive value $\widehat{G}\doteq G\left(\mu , \mu \right)$, where $\mu =\mathrm{E}\left(\xi \right)$, we obtain:

$$\widehat{G}-G\left(y, \Phi \right)=$$

$$\left(1-\theta_{y}\right)\left(y-\xi ^{o}_{y}\right) c+\theta_{y} \left(\xi ^{u}_{y}-y\right) \left(r-c\right)\qquad$$ (1)

Since everything in this formula is positive, the quantity $\widehat{G}$ is an upper bound for $G\left(y, \Phi \right)$ and $\widehat{G}-G\left(y, \Phi \right)$ appears to be the cost associated with the choice $y$.

The usual criterion used to determine the optimal value $y^{*}$ is to minimize this cost. Deriving $G\left(y, \Phi \right)$, we obtain the condition $r\int_{y}^{\infty} \mathrm{d}\Phi \! \left(\xi \right)-c=0$, i.e. the well known newsboy result:

$$\Phi \left(y^{*}\right)=1-\frac{c}{r}$$ (2)

In other words: when $\Phi$ is known, the best quantity one can buy depends on the profitability of the product and is generally not the expectation of the demand. Reporting (2) into (1) leads to the following expression (where $*$ is used as index instead of $y^{*}$):

$$\widehat{G}-G\left(y^{*}, \Phi \right)=\theta_{*}\left(1-\theta_{*}\right)\left(\xi ^{u}_{*}-\xi ^{o}_{*}\right) r.$$ (3)

This expression gives the cost of uncertainty, i.e. the loss that remains from the ideal case even when we adopt the best decision.

2.2 Min-max Solution for $\mathcal{F}\left(\mu,\sigma\right)$

The best order decision must be analyzed under various weaker hypotheses than an exact knowledge of the distribution $\Phi$. For example, it can be assumed that the mean demand is identifiable with enough precision, and that, additionally, some measure of the dispersion of the demand is also identifiable. In such a condition, various families of demand pdfs need to be investigated. The determination of the optimal decision becomes a min-then-max problem, where the objective is to optimize the gain for the worst case over a family of demand models, in order to guarantee a lower bound for the expected performance. In other words, we solve:

$$G^{*}\doteq G\left(y^{*}, \mathcal{F}\right)\doteq\max_{y} \min_{\Phi \in\mathcal{F}}G\left(y, \Phi \right)$$ (4)

The founding result obtained by Scarf (1958) addresses the case where the standard deviation $\sigma$ is known (together with the mean $\mu$). The key fact is that, over all distributions $\Phi$ sharing the given value of $\left(\mu , \sigma\right)$, the worse case for a given $y$ is ever a "two Dirac's" distribution. Therefore the best decision against the whole family $\mathcal{F}\left(\mu , \sigma\right)$ can be obtained by taking into account only these distributions, leading to the solution:

$$ \mathrm{if}\;{\displaystyle c/r>\left(1+\sigma^{2}/\mu ^{2}\right)^{-1}}$$

$$\mathrm{then} \mathrm{do}\:\mathrm{nothing} : y^{*}=0,\quad G^{*}=0$$

$$\mathrm{else} \left\{ \begin{array}{ccc} \displaystyle {y^{*}} &... ...e {\mu \left(r-c\right)-\sigma\sqrt{c\left(r-c\right)}}\end{array}\qquad\right.$$ (5)

It can be noticed that, in the "two Dirac's" case, either $\xi =\xi ^{o}$ or $\xi =\xi ^{u}$, while the condition on $c/r$ is needed to ensure $\xi ^{o}>0$.

2.3 The Intermeans Parameter

Knowing that $\mu =\mathrm{E}\left(\xi \right)$ is not the optimal decision, we can nevertheless examine what happens when this choice is taken. By the definition of the mean, we have $\forall y : \theta _{y} \xi ^{u}_{y}+\left(1-\theta _{y}\right)\xi ^{o}_{y}=\mu$. Using this expression in (1), we obtain the "cost of mean" formula:

$$\widehat{G}-G\left(\mu , \Phi \right) = r \delta$$ (6)

$$where\quad\delta \doteq \theta _{\mu }\left(1-\theta _{\mu }\right)\left(\xi ^{u}_{\mu }-\xi ^{o}_{\mu }\right)$$ (7)

Obviously, the "cost of mean" is an upper bound for (3). Being independent of the cost to price ratio, this bound is of interest and places the focus onto the quantity $\delta$, later referred as the "intermeans parameter".

This quantity has some similarity with the interquartile range and therefore appears to be a measure of the dispersion of the distribution. Since this use of $\delta$ seems to be new, we have undertaken a comparison between this quantity and the usual measure of the dispersion, i.e. the standard deviation $\sigma$. This leads to Tab. 1.

Tab. 1: Some values for the ratio $\delta /\sigma$.

distribution	$\delta /\sigma$ (exact)	$\delta /\sigma$ (approx)
uniform	$\sqrt{3}/4$	$\approx0.433$
normal	$1/\sqrt{2 \pi}$	$\approx0.399$
triangular	1/ $\sqrt{6} \cdots 8\sqrt{2}/27$	$0.408 \cdots 0.419$
lognormal	$\leq1/\sqrt{2 \pi}$	$\leq0.399$
two Dirac's	$0 \cdots 1/2$	$0 \cdots 0.5$

From now on, all $\theta , \xi ^{o}, \xi ^{u}$ are relative to the mean as in (7), and subscripts will be omitted. It can be seen that $\mu -\xi ^{o}-\delta =\delta \theta /\left(1-\theta \right)$ and $-\mu +\xi ^{u}-\delta =\delta \left(1-\theta \right)/\theta$. Therefore, the points $\mu \pm\delta$ are ever situated as in Fig. 1 and the relation $x y=\delta ^{2}$ holds.

Fig. 1: Meaning of $\delta$ : the $x y=\delta ^{2}$ property.

2.4 Min-max Solution for $\mathcal{F}\left(\mu,\delta\right)$

For most of the usual distributions, the assumptions "knowing $\left(\mu , \sigma\right)$" and "knowing $\left(\mu , \delta \right)$" are quite equivalent. Even for the lognormal distribution, the relation $0.333\leq\delta/\sigma\leq0.399$ holds if we assume that the demand has only a chance over a thousand to go outside the interval $\left[\mu /10, \mu \times10\right]$.

When using two Dirac's distributions, both assumptions are no more equivalent, leading to the following result (Douillet and Rabenasolo, 2006).

When playing against the family $\mathcal{F}\left(\mu , \delta , Dirac\right)$ of all the "two Dirac's" sharing the same values of the mean and the intermeans parameter, the robust decision is no more given by (5) but by:

$$\left\{ \begin{array}{ccc} \mathrm{if}\;{\displaystyle 1-\frac{\d... ...laystyle \frac{\delta }{\mu }} & & y^{*}={\displaystyle \mu }\end{array}\right.$$ (8)