Observation, Beliefs, and Decision

With $P(\text{flag})=\rho \beta +(1-\rho )\alpha$, the optimal rule inspects after signal $s$ iff the posterior $P(\text{contraband}\mid s)\ge c_I/c_M$, and the optimal expected cost is

against $\min \{c_I,c_M\rho \}$ without the signal. At base values the posteriors are $\frac{4}{13}$ after a flag and $\frac{1}{37}$ after a clear signal; the rule inspects flagged consignments and releases the rest; the expected cost falls from $1$ to $\frac{33}{50}$, so $\mathrm{VoI}({\pi }_1)=\frac{17}{50}$.

Let $\pi =(\beta ,\alpha )$ with $\beta \ne \alpha$. A binary experiment ${\pi }^{\prime }=({\beta }^{\prime },{\alpha }^{\prime })$ is a garbling of $\pi$ iff there are $k_1,k_2\in [0,1]$ with

that is, iff $({\beta }^{\prime },{\alpha }^{\prime })$ lies in the parallelogram with vertices $(0,0)$, $(1,1)$, $(\beta ,\alpha )$ and $(1-\beta ,1-\alpha )$.

At base values, with information measured in nats:

signal & mutual information & value $\mathrm{VoI}$ & $V(I)$ at that $I$

${\pi }_1=(\frac{4}{5},\frac{1}{5})$ & $0.072654\dots$ & $\frac{17}{50}$ & $0.496411\dots$

${\pi }_2=(\frac{19}{20},\frac{2}{5})$ & $0.063529\dots$ & $\frac{89}{200}$ & $0.454877\dots$

${\pi }_3=(\frac{37}{50},\frac{13}{50})$ & $0.044434\dots$ & $\frac{43}{250}$ & $0.354693\dots$

perfect signal & $H(\rho )=0.325082\dots$ & $\frac{9}{10}$ & $\frac{9}{10}$

{/table}

Each $V(I)$ in the table is enclosed by a certified interval of width below $2\cdot 10^{-34}$; every signal's value lies below the curve, and mutual information ranks ${\pi }_1$ above ${\pi }_2$ although ${\pi }_2$ is worth more in this problem.

The team optimum over local policies is $\frac{9}{16}$, attained by both agents following their signals. Among deterministic local policies the person-by-person optimal pairs are this one and the two constant pairs (both always choose $0$; both always choose $1$), each worth $\frac{1}{2}$. With independent private randomisation there are exactly two more: each agent plays always-$0$ with probability $\frac{3}{5}$ and follows its signal with probability $\frac{2}{5}$, or always-$1$ with probability $\frac{3}{5}$ and follows its signal with probability $\frac{2}{5}$; each pair is worth $\frac{9}{20}$. A single controller seeing both signals achieves $\frac{3}{4}$.

Among pairs in which ${\gamma }_1$ is affine, the minimum cost at $k=\frac{1}{5}$, $\sigma =5$ is exactly $\frac{24}{25}$, attained by $x_1=\lambda x_0$ with $\lambda =(5\pm \sqrt{21})/10$ and ${\gamma }_2(y)=\lambda y$. Each of these pairs is person-by-person optimal: neither controller can lower the cost by changing its own policy to any measurable policy.

For step policies the cost has the following certified brackets at $k=\frac{1}{5}$, $\sigma =5$:

first-stage policy & cost $J$ with the optimal second stage

$x_1=\sigma \mathrm{sgn}(x_0)$ (Witsenhausen's choice) & $[0.404253198,0.404253200]$

$x_1=a\mathrm{sgn}(x_0)$, $a=4.051$ & $[0.364829998,0.364830029]$

nearest of the $11$ points $dj$, $|j|\le 5$, $d=6.54$ (states beyond $\pm 32.7$ sent to $\pm 32.7$) & $[0.171559697,0.171560227]$

{/table}

The values of $a$ and $d$ are the best on grids of step $0.001$ and $0.005$; no optimality within the class is claimed.

For every pair $({\gamma }_1,{\gamma }_2)$,

and at $k=\frac{1}{5}$, $\sigma =5$ the right-hand side exceeds $0.027604$.

In Model O5:

• Rooted detection is maximised by filling classes in decreasing order of ${\pi }_k$. The maximum $D^{\ast }(b)$ is concave and piecewise linear in $b$, with slopes ${\pi }_k/\rho$ in that order. Equivalently, some price $\lambda$ makes the optimal rule check every consignment in a class with ${\pi }_k>\lambda$ and none in a class with ${\pi }_k<\lambda$: Model O1's threshold rule, with the break-even probability $c_I/c_M$ replaced by the budget's shadow price. The price $\lambda$ is in units of violations found per check, the multiplier of $\rho D$; in units of the conditional detection $D$ itself the multiplier is $\lambda /\rho$.

• If one benchmark is a garbling of another, every policy on the garbled classes is reproduced on the original classes with the same budget and the same detection; hence the garbled benchmark's $D^{\ast }(b)$ is no larger, for every budget $b$.

• Every feasible policy has $G(x)\le b$, with equality only for uniform checking at rate $b$. For $f\in [0,b]$, the largest rooted detection among policies with $G(x)\ge f$ is $f+D_{1-f}^{\ast }(b-f)$, where $D_{1-f}^{\ast }$ is the maximum of (a) with every rate capped at $1-f$.

• Where $b>0$ and no cap binds along this frontier, it is linear in $f$, and the objective $(1-\mu )D+\mu G$ is maximised at one of its ends: by concentration if $\mu <{\mu }^{\ast }=1-b/D^{\ast }(b)$, by uniform checking if $\mu >{\mu }^{\ast }$.

At the stylised values: concentration checks $\frac{3}{10}$ of the high class and detects $\frac{6}{41}$ of rooted violation, with threshold $\lambda =\frac{1}{5}$ (a marginal check there raises $D$ by $\lambda /\rho =\frac{200}{41}$ per unit of budget) and guarantee $0$; uniform checking detects and guarantees $\frac{3}{100}$; rates in the ratio $1:3:9$ give $(\frac{1}{80},\frac{3}{80},\frac{9}{80})$, detection $\frac{231}{3280}$ and guarantee $\frac{1}{80}$, while the frontier at that guarantee reaches $\frac{321}{3280}$; and ${\mu }^{\ast }=\frac{159}{200}$.

Consider one decision-maker with finite state, action and observation sets, a finite horizon, known controlled Markov transition and observation kernels, an immediate utility that depends on the current state and action, and the expected sum of utilities as objective. Then some optimal policy has the form $a={\mu }_t(\mathbf{b})$, where $\mathbf{b}$ is the current belief and $t$ the number of periods left. The optimal value with $t$ periods left is $V_t(\mathbf{b})={\max }_{\eta \in {\mathcal{E}}_t}⟨\eta ,\mathbf{b}⟩$ for a finite set ${\mathcal{E}}_t$ of alpha vectors; hence it is convex and piecewise linear in $\mathbf{b}$ (concave, for a cost to be minimised).