The cost of leaving information out.
Combining observation outputs makes an interface simpler. It can also increase the evidence needed afterward. ChoiceProof studies how this simplification changes the optimal cost of verification in finite models that account for faulty observation sources.
Preserving the distinctions needed for verification does not necessarily preserve its cost.
Cost preserved
Combining outputs can leave the optimal verification cost unchanged.
Additional cost
Verification can remain possible while requiring more evidence-acquisition queries.
Essential distinctions lost
Executions that could previously be distinguished may become indistinguishable, preventing verification from being completed.
We characterize the cost increase in the studied models through an exact worst-case multiplier. An upper bound and a matching construction establish the precision of the guarantee. The multiplier results are accompanied by certificates that can be checked separately from the optimization procedure.
For the studied models with fixed observation capabilities and prices, we also derive conditions under which simplification preserves optimal cost after earlier observations have narrowed the candidate executions. This accounts for the value of information throughout verification.
These results support interface design that considers both which information to retain and how that choice affects the cost of acquiring evidence later.