Bottom line. For every n≥1, every network N with n retailers that satisfies the standing assumptions, all reals m,γ with m≥1 and γ≥49+4m1 such that Hi≥mh for all i, h≤p and Kmax≤(γ−1)K0, every valid initial state x, and every parameter vector c that satisfies the FIFO-choice predicate for N, the statement asserts
CN,x(πN,x,cFIFO) ≤ γ⋅OPT(N,x),
as an inequality in [0,∞]. The left side is the upper-limit long-run average expected cost of one specific deterministic policy built from (N,x,c). The right side is γ times the infimum of the same cost functional over all randomized, nonanticipative, measurable, feasible policies started from the same x. The constant enters as ofReal(γ)=max(γ,0), which equals γ because γ>49. Words such as warehouse, retailer, order, dispatch and request are labels taken from identifier names. Every object is defined by the formulas below.
Binders and hypotheses (all universally quantified, and there are no others).
- n∈N with 0<n. Retailers are written i=1,…,n here. The code indexes them 0,…,n−1, and their order matters only for tie-breaking in the FIFO queue.
- A network N=(L0,(Li),μ,K0,(Ki),h,(Hi),p), and the hypothesis that N satisfies the standing assumptions.
- m,γ∈R with 1≤m and 49+4m1≤γ.
- mh≤Hi for every i; h≤p; Kmax≤(γ−1)K0.
- An initial state x, and the hypothesis that x is valid.
- A parameter vector c, and the hypothesis that c satisfies the FIFO-choice predicate for N.
Network, standing assumptions, Kmax. L0,Li∈N, with zero allowed and no other constraint. μ is a probability measure on [0,∞)n: the law of one period's demand vector ξ=(ξ1,…,ξn), with any dependence across retailers. K0,Ki,h,Hi,p are reals. Demands in different periods are i.i.d. with law μ, because every cost functional below uses product measures. The standing assumptions are exactly:
- 0<Eμ[ξi]<∞ for every i, computed as a [0,∞]-valued integral;
- K0≥0 and Ki≥0;
- h>0, Hi>0 and p>0.
Kmax is the real supremum of the family (Ki)i. Since n≥1 it equals maxiKi. For an empty family, the real supremum would be the conventional value 0.
Initial state and validity. x=(W,I,α,β) with W∈R, I=(Ii)∈Rn, α:N→R and βi:N→R. Only αt for t<L0 and βi,t for t<Li are ever used, as exogenous arrivals in period t. Valid means W≥0, αt≥0 for all t∈N, and βi,t≥0 for all i,t, unused entries included. There is no condition on I, so negative Ii are allowed.
Cost functional (used on both sides). A policy on a measurable space U is any pair of real-valued maps ordt(u,d) and dispt,i(u,d), t∈N. Here d=(d0,d1,…) is a demand path with dt=(dt,1,…,dt,n)∈[0,∞)n. Given x, the arrivals are:
- at the warehouse, At0=αt for t<L0 and At0=ordt−L0 for t≥L0;
- at retailer i, Ati=βi,t for t<Li and Ati=dispt−Li,i for t≥Li.
From these,
Wt=W+r=0∑t(Ar0−i∑dispr,i),Wtav=W+r=0∑t−1(Ar0−i∑dispr,i)+At0,Ii,t=Ii+r=0∑t(Ari−dr,i),
ct=K01[ordt>0]+i∑Ki1[dispt,i>0]+hWt+i∑(HiIi,t++pIi,t−),
with y+=max(y,0) and y−=max(−y,0). The warehouse term is hWt, not hWt+. For a probability measure ν on U,
CN,x(π,ν)=T→∞limsup T1∫t=0∑T−1max(ct(u,zˉ),0)(ν⊗μ⊗T)(du,dz) ∈[0,∞],
where z=(z0,…,zT−1) and zˉ is the path z0,…,zT−1,0,0,…. This means:
- u is drawn once from ν, independently of the demands;
- each period cost is truncated below at 0 before summing;
- the integral of the [0,∞]-valued integrand is taken in the lower-integral sense (the supremum of integrals of measurable simple functions below it). This is the usual integral when the integrand is measurable, and it is defined even when it is not.
For a deterministic policy, U is a one-point space with its Dirac measure. Then C reduces to limsupTT1Ez∼μ⊗T∑t<Tmax(ct(zˉ),0). The left side of the theorem is this quantity for πN,x,cFIFO.
The optimum OPT(N,x). It is the infimum in [0,∞] of CN,x(π,ν) over every measurable space U, every probability measure ν on U, and every policy π on U that is:
- nonanticipative: ordt(u,d) and dispt,i(u,d) depend on d only through d0,…,dt−1;
- measurable: for each t and i, the maps (u,d)↦ordt(u,d) and (u,d)↦dispt,i(u,d) are measurable for the product σ-algebra on U×([0,∞)n)N;
- feasible for x: for every u, every demand path d (not only almost every) and every t, ordt≥0, dispt,i≥0 for all i, and ∑idispt,i≤Wtav.
For valid x this class is nonempty, since the policy that never orders or dispatches belongs to it. Feasibility gives Wt=Wtav−∑idispt,i≥0. So under the standing sign conditions every ct≥0 for these policies, and the truncation has no effect on the right side.
Single-location ingredients of the choice predicate. Let ρi be the law of ξi and ρΣ the law of ξ1+⋯+ξn, both under μ. Define
Fi(y)=E[Hi(y−Zi)++p(Zi−y)+],Zi=sum of Li+1 i.i.d. draws from ρi,
f0(y)=E[h(y−Z0)++p(Z0−y)+],Z0=sum of L0 i.i.d. draws from ρΣ (Z0=0 if L0=0).
These real-valued integrals would default to 0 for a non-integrable integrand, but the finite means make them genuine expectations.
Now take a probability law ρ on [0,∞), a function f:R→R, reals K,s,S, and i.i.d. draws ζ0,ζ1,… from ρ. Run the (s,S) recursion: Y0=S; Y~t=S if Yt≤s, otherwise Y~t=Yt; Yt+1=Y~t−ζt. Define
SSρ(f,K;s,S)=T→∞limsupT1Et=0∑T−1(K1[Yt≤s and Yt<S]+f(Y~t))+,
Vρ(f,K)=inf T→∞limsupT1Et=0∑T−1(K1[qt>0]+f(yt))+,yt=r=0∑tqr−r=0∑t−1ζr.
In Vρ the infimum runs over every measurable space U, every probability ν on U (with u∼ν independent of the ζ's), and every rule qt(u,ζ)∈R that is nonanticipative (qt depends only on ζ0,…,ζt−1), jointly measurable, and ≥0 for all t,u,ζ. So this level starts at 0, while the (s,S) recursion starts at S. Further,
Mρ(h,p;s,S,a)=T→∞limsupT1Et=0∑T−1(h(a−Y~t)++p(Y~t−a)+)+,Mˉρ(h,p;s,S)=a∈RinfMρ(h,p;s,S,a),
Augi(s,S)=SSρi(Fi,Ki;s,S)+Mˉρi(h,p;s,S).
All of these lie in [0,∞]. As on the network level, the horizon-T expectations are over T i.i.d. draws padded with zeros, and no term depends on the padding. In every instance used below, the per-period costs inside them are nonnegative under the standing assumptions, so the outer (⋅)+ has no effect.
A pair (sh,Sh) is a canonical optimum for (ρ,f,K) if all of the following hold:
- sh<Sh;
- SSρ(f,K;sh,Sh)=Vρ(f,K);
- f(sh)+=Vρ(f,K);
- f(Sh)+≤Vρ(f,K);
- f(y)+≤Vρ(f,K) for all y∈[sh,Sh].
The equality with the finite number f(sh)+ forces Vρ(f,K)<∞.
A pair (s′,S′) is a best half window of [sh,Sh] for (ρ,f) if:
- sh≤s′<S′≤Sh and S′−s′=21(Sh−sh);
- SSρ(f,0;s′,S′)≤SSρ(f,0;s′′,S′′) for every pair (s′′,S′′) with sh≤s′′<S′′≤Sh and S′′−s′′=21(Sh−sh).
The FIFO-choice predicate. c consists of reals si,Si,ai for i=1,…,n, and reals s0,S0. The predicate is the conjunction of:
- For each i with Ki>0 there exist reals sh,Sh,s′,S′ such that:
- (sh,Sh) is a canonical optimum for (ρi,Fi,35Ki);
- (s′,S′) is a best half window of [sh,Sh] for (ρi,Fi);
- either (si,Si)=(sh,Sh) and Augi(sh,Sh)≤Augi(s′,S′), or (si,Si)=(s′,S′) and Augi(s′,S′)≤Augi(sh,Sh);
- Mρi(h,p;si,Si,ai)=Mˉρi(h,p;si,Si), that is, ai attains the infimum over a.
- For each i with Ki=0: si=Si, Fi(Si)≤Fi(y) for every y∈R, and ai=Si.
- s0≤S0.
- SSρΣ(f0,K0+Kmax;s0,S0)=VρΣ(f0,K0+Kmax).
The fixed cost is 35Ki in the canonical optimum, 0 in the half-window comparison, and Ki inside Augi. Under the standing assumptions each i falls under exactly one of items 1 and 2.
The FIFO policy πN,x,cFIFO. It is deterministic. Its ordt(d) and dispt,i(d) are the period-t outputs of the state machine below, run on d0,…,dt−1.
The state consists of:
- an on/off flag;
- a free warehouse stock Wˉ;
- retailer levels ℓi;
- scheduled arrivals SP(τ) at the warehouse and RPi(τ) at retailer i, for every period τ;
- a queue (ordered list) of requests, each with a retailer, a size, an allocated amount and a shipped amount.
Initially the flag is off, Wˉ=W and ℓi=Ii. SP(τ)=ατ for τ<L0 and 0 otherwise, RPi(τ)=βi,τ for τ<Li and 0 otherwise, and the queue is empty.
In period t:
- Receive: Wˉ←Wˉ+SP(t) and ℓi←ℓi+RPi(t).
- If the flag is on, go to step 3. If it is off, check whether t+1≥Tpipe:=max(L0,maxiLi) and ℓi≤Si for every i.
- If both hold, turn the flag on (it then stays on forever). Append, in increasing i, a request of size Si−ℓi for each i with Si−ℓi>0, then continue with step 3.
- Otherwise output ordt=0 and dispt,i=0, and go to step 5.
- Compute requests and the warehouse order from the state at the start of this step. Let ITi=∑k=1LiRPi(t+k) and IT0=∑k=1L0SP(t+k). Over retailer i's queued requests, let Oi=∑(size−shipped) and Ri=∑(allocated−shipped).
- Let p^i:=ℓi+ITi+Oi. Each i with p^i≤si and Si−p^i>0 gets a new request of size Si−p^i, appended at the back of the queue in increasing i.
- Let P0:=Wˉ+∑iRi+IT0+∑i(ℓi+ITi−ai). The order is q0=S0−P0 if P0≤s0, and q0=0 otherwise. It is added to Wˉ at once if L0=0, and to SP(t+L0) otherwise.
- FIFO allocation. Scan the queue from the front with w=Wˉ. Each request receives min(size−allocated,w), which is subtracted from w, and everything allocated but not yet shipped is shipped at once. Let Di be the total shipped to retailer i this period. Then:
- set Wˉ=w and delete requests with shipped ≥ size;
- add Di to ℓi at once if Li=0, and to RPi(t+Li) otherwise;
- output ordt=q0 and dispt,i=Di.
- Demand: ℓi←ℓi−dt,i.
The engine also has a per-retailer batching option. It is off for every retailer here, so request offsets, time stamps, the request counter and the offset rule (the zero rule) do not affect the outputs. The left side feeds only the output sequences ordt and dispt,i into the generic formulas for Wt, Ii,t and ct above. The engine's internal state does not enter the cost.
Edge cases and scope.
-
Role of 0<n. It excludes the network with no retailers. It makes Kmax a maximum over a nonempty finite family, and it makes every clause quantified over retailers non-vacuous.
-
Constants. With m≥1, the threshold 49+4m1 lies in (49,25], equal to 25 at m=1. Hence γ>49, ofReal(γ)=γ and γ−1>45.
-
Which γ are covered. m appears only in hypotheses. For a fixed network the statement covers every γ≥49+4m1 with 1≤m≤miniHi/h, subject also to (γ−1)K0≥Kmax. If K0>0 that last condition reads γ≥1+Kmax/K0. Networks with some Hi<h, or with p<h, are not covered.
-
K0=0. Then Kmax≤0, which together with Ki≥0 forces every Ki=0.
-
Values in [0,∞]. Both sides are extended nonnegative reals, and γ⋅∞=∞.
- If OPT(N,x)=∞, the inequality holds automatically.
- If OPT(N,x)=0, it asserts that the left side is 0.
- A left side equal to ∞ is compatible with the claim only when OPT(N,x)=∞.
- OPT is not ∞ by emptiness, since the class is nonempty for valid x. Whether it is finite depends on the data, and the statement does not say.
-
Truncation. Each ct enters as max(ct,0). For the FIFO policy, a negative ct could come only from hWt with Wt<0, where Wt is the generic formula applied to the FIFO outputs. The statement neither excludes nor asserts this.
-
Status of the FIFO policy. The theorem does not state that the FIFO policy is feasible or measurable, or that it belongs to the class defining OPT. It only compares two numbers. By construction its period-t outputs depend only on d0,…,dt−1, so the zero padding after T is immaterial on both sides. No measurability is assumed for it, which is where the lower-integral reading matters.
-
Attainment required by the predicate. The choice predicate requires exact attainment:
- an optimal (s,S) pair for (ρΣ,f0,K0+Kmax);
- for Ki>0, a canonical optimum with finite V, an attained best half window, and an attained minimizing ai;
- for Ki=0, a minimizer of Fi.
The statement does not assert that such a c exists, and for a network admitting none it is vacuous. Equalities and inequalities between these averages are in [0,∞], so item 4 and the ai condition would also be met with both sides equal to ∞.
-
Joint satisfiability. The hypotheses can all hold at once. Example data:
- n=1, L0=L1=0, and μ the point mass at demand 1;
- K0=1, K1=0, h=H1=p=1, m=1, γ=25;
- x=0 (all components zero);
- c with s1=S1=a1=1 and (s0,S0)=(−1,0).
Here F1(y)=∣y−1∣ and f0(y)=∣y∣, and both sides of item 4 equal 1.
Confirmed by the moderator at approval.