One source, or all three.
We determine the exact minimum worst-case expected observation cost in a three-source model where one source may falsify its report after seeing the honest readings. The result covers every admissible adaptive and randomized strategy under the specified accuracy and 5% failure-probability requirements. An observation plan attains the universal lower bound.
Worst-case expected cost (model cost units)
Allowed failure probability δ
Achievable observation plan = Lower bound for every strategy
r₃ ≈ 0.2698546%r₁ ≈ 33.4233456%
The endpoints represent buying all three readings and buying one uniformly chosen reading. At a 5% allowed failure probability, the minimum worst-case expected cost is about 5.4293 model cost units.
An achievable cost meets the theoretical limit.
The task is to estimate the value at time 4 to within one unit. Which reports are worth buying if, in every admissible world, the probability of exceeding that error must stay at or below 5%?
One late report costs 2 units. All three cost 6. Choosing between these purchases with the right probabilities brings the expected cost to about 5.4293 units in every world. The proof gives the matching lower bound. Every strategy that meets the accuracy requirement has a worst-case expected cost at least this large.
≈ 5.429303494829 cost units
Q is the standard normal upper-tail function. The worst-case failure probabilities for the one-report and three-report plans are r₁ and r₃, respectively.
Choose before observing.
The plan skips all early observations. Before observing any readings, it randomly selects one of two purchase options. With probability approximately 14.2674%, it chooses one of the three sources uniformly and uses its late reading directly. Otherwise, it buys all three late readings and returns their median.
Choose one source uniformly
Cost 2. Return the selected reading.
Read all three sources
Cost 6. Return the median of the three readings.
The 5% limit applies to failure over the whole plan. If α is the probability of choosing one late report, the worst-case failure probability across both branches is αr₁ + (1 − α)r₃ = 0.05.
Compared with every admissible strategy.
A competing strategy can change its late purchases after seeing the early readings, stop buying reports, or use private randomness to turn the readings into an estimate. The lower bound covers all of these choices.
Consider a strategy that buys all three late reports. The dishonest source can place its report so that the honest reading farther from the target becomes the middle value. If that middle value falls just outside the error tolerance, a random shift of the estimate might bring it back inside. The same rule can also push an estimate that was already within tolerance across the boundary.
For each distance from the tolerance boundary, the proof compares the Gaussian probability within that distance on the inside and on the outside. In the worst case, any gain from correcting an out-of-range estimate is offset by errors introduced inside the boundary. This yields a risk lower bound for every randomized estimator on the three-report branch. Combining it with the bounds for the other purchase histories establishes the cost limit.
Model and verification
Costs are measured in the model’s units paid per report. The accuracy requirement applies separately to every admissible trajectory and source behavior.
| Sources | At most one of the three sources may falsify reports. Its identity is fixed before the honest noise and the controller’s random choices are drawn. |
|---|---|
| False reports | The dishonest source knows the trajectory and may see the honest reports from the same round before responding. Future honest noise and the controller’s unrevealed random choices are hidden. |
| Honest reports | Each reading is the true value at its sampling time plus independent, zero-mean Gaussian noise with standard deviation 1/4. |
| Trajectory and target | The absolute change between any two times is at most one quarter of the elapsed time. The target is x(4), the true value at time 4. |
| Accuracy | Absolute error up to 1 is allowed. The probability of larger error must be at most 5% in every admissible world. |
| Early reports E | Sampled at time 1 and returned at time 2. Each costs 1 unit. |
| Late reports L | Sampled at time 3 and returned at time 4. Each costs 2 units. |
| Purchase timing | The early subset is chosen before any reports arrive. The late subset may depend on the early readings, but the entire subset must be selected and paid for before any late report returns. |
The mathematical proof establishes optimality over the continuous space of strategies on real-valued readings. Computational replay checks the Gaussian constants, finite regression cases and existing certificates for the branches that purchase early observations.