What a passage report costs
A museum surveyor sees the building. A handler knows which passages fit the exhibit. Who should inspect, who should ask, and what does the other person need to hear before choosing a route?
A question the wrong person cannot answer
Start with East and West. Each local menu is nonempty. Both people know that at least one route works for this move. Of the nine possible pairs of menus, seven meet that promise. The handler knows their own fit list throughout.
| Who has the question? | What they can see | What follows |
|---|---|---|
| Surveyor, “Can this exhibit use East here?” | The building allows both routes. The exhibit could fit East alone or West alone. | The truthful answers differ. The surveyor sees the same thing in both cases. |
| Surveyor after an extra fit inspection | The building menu and whether this exhibit fits East. | East works if and only if both allow East. The handler can act on the yes/no answer in all seven cases. |
| Surveyor, “Does the building allow East?” | The building menu alone. | A handler fitting only one route can choose it by the promise. A handler fitting both chooses East on yes, West on no. The second inspection disappears. |
The last rule is more useful than repairing the original question if the extra inspection consumes effort. A current answer about the building becomes sufficient in combination with the handler’s own information. A missing, unrelated or previous-move message gives no new fact about this move. A handler who fits both can then face two indistinguishable buildings demanding different choices. A known, available and authorised fifth passage removes the need to classify the original routes when any successful passage will do.
Three inspections can do the work of four
Label the four passages A–D. A building menu lists the passages the building allows; a fit menu lists the passages the exhibit can use. There are 15 nonempty menus on each side and 225 pairs. In 175 pairs the two menus intersect. Each inspection reveals one named passage’s available/unavailable bit. A survey report must be a function of readings the surveyor actually obtained. A handler may use only the current message, the fit menu, the agreed rule and any explicit guarantee.
Which building menus may share a report? Nested menus can. Of the menus consistent with the report and the handler’s knowledge that a route works, take the smallest. Any fitted passage in that menu works in every remaining menu. Two incomparable building menus cannot share a report. Give the handler a fit list containing one passage unique to each. Both worlds obey the promise and they force opposite choices. A reporting vocabulary therefore partitions building menus into chains under inclusion. This is the minimum-chain-partition side of classical order theory. The project-spine problem is a different construction.
What must the surveyor read? With two or more passages left unread, a transcript admits two incomparable completions. Each includes one unread passage and excludes the other. A handler fitting only those two passages forces opposite choices. Every successful sender-only procedure therefore needs at least three membership readings, even with adaptive order. This lower bound assumes the inspector learns only one named membership per reading.
If the three inspections are always A, B and C, the eight possible transcripts cannot share a meaning with one another. For any two different transcripts, choose completions that are incomparable. If their inspected yes-sets are nested, include D in the smaller completion and omit it in the larger. The empty yes-set still has the admissible completion containing D alone. Thus the fixed-three design requires eight meanings.
| First readings | Third | If third is shut | If third is open |
|---|---|---|---|
| A shut, B shut | C | D → code 1 | C or CD → code 3 |
| A shut, B open | C | B or BD → code 4 | BC or BCD → code 5 |
| A open, B shut | D | A or AC → code 2 | AD or ACD → code 1 |
| A open, B open | C | AB or ABD → code 6 | ABC or ABCD → code 2 |
Code 1 covers D, AD and ACD. If the handler fits B and C, the promise rules out the first two buildings, leaving C as a sound choice. The surveyor need never learn whether the exhibit fits C. Code 2 joins A, AC, ABC and ABCD. The other four reports each cover one leaf of the inspection tree. The six two-passage building menus are mutually incomparable, so any one-way reporting scheme needs at least six meanings, even after a full survey. This procedure meets both the three-reading and six-meaning lower bounds.
There are 576 ordered three-inspection trees, choosing an uninspected passage at each branch. Grouping their leaves by exhaustive subset search gives 432 trees requiring six meanings, 96 requiring seven and 48 requiring eight. A full four-passage survey also supports six meanings, and an ordinary four-box checklist can always send all four entries. At this scale six codes and eight codes both need three fixed-length bits. Codebook size alone measures neither radio time nor human effort.
Where the change actually saves a bit. In a nine-passage museum a checked eight-inspection adaptive tree needs 126 meanings, matching the lower bound from the 126 four-passage menus. A fixed list of eight inspections needs 256 meanings. That is seven versus eight fixed-length payload bits on one outbound report, with the codebooks already agreed. Nine is the first passage count for which the middle-rank lower bound permits this saving. The appendix supplies the actual tree, codebook and a checker for every menu pair. Inspect the five- and nine-passage certificates.
What changes if the handler may ask?
The one-way result changes when the handler is allowed to name a passage in a question. They ask about passages on their fit list in alphabetical order. Stop at the first current yes. Under the feasibility promise they may choose the last remaining fitted passage without asking. A handler fitting only D therefore needs no communication. Across the four single-passage fit lists, that accounts for 32 of 175 feasible pairs.
If the handler must also recognise blockage, admit all 225 pairs. Any two different building menus now require different sender-only reports: choose a fit list consisting solely of a passage on which they disagree. One world permits that route and the other requires a blockage report. A one-way message therefore needs 15 meanings and a survey that sometimes reads all four passages. Even sending every bit actually observed, the fixed-three and adaptive-three designs each settle only 187 of 225 pairs.
Why every three-inspection one-way tree leaves exactly 38 pairs unsettled
Give the handler the entire inspection transcript. A leaf with at least one open passage observed leaves exactly two possible buildings: the set S of observed open passages, or S plus the single unread passage d. A decision is unresolved precisely when the exhibit fits d and fits none of S. For k observed open passages there are 23−k such fit lists and two possible buildings. The all-shut transcript already identifies d as the sole open passage because the building menu is nonempty. In a complete three-reading tree, the number of transcripts with k yes answers is the binomial coefficient “3 choose k”, regardless of which doors the surveyor selects. The unsettled count is therefore 2 × (3 × 4 + 3 × 2 + 1) = 38. All 576 trees were also checked against an ordinary decision table. An earlier stop or a compressed message cannot distinguish more cases than the full transcript.
The same count for n passages and n−1 distinct named readings per path is 2 × (3n−1 − 2n−1) unsettled ordered menu pairs. This is a count of information states under the stipulated universe. It gives no field frequency of blockages.
In dialogue the handler can ask about every fitted passage. If the fit list covers all four, knowing the building menu is nonempty allows the last passage to be inferred after three negatives. If the fit list is smaller it has at most three entries. The dialogue therefore diagnoses all 225 pairs within three readings. Three is necessary in the worst case: a handler fitting B, C and D has to rule out each of those passages to certify blockage in a building that allows only A. For example, let the building allow only B and the exhibit fit A and D. Both three-reading survey plans leave B and BD indistinguishable. Ask about A and D instead and two negatives certify blockage. Replay that decision with both teams’ views. The extra channel carries information: the handler names which passage to inspect and receives a current answer. The final choice stays with the handler.
Is alphabetical order leaving an easier dialogue undiscovered? For each of the 15 fit lists we also solved the ordinary decision table backwards. At a view with a common route or known blockage, stop. Otherwise try every named passage, splitting the remaining buildings into yes and no. The minimum worst-case cost is one plus the smaller achievable maximum of the two continuation costs. For total cost over equally weighted cases, charge one reading to every remaining case and add the best totals in each branch. The procedure considers questions about passages outside the fit list as well. Alphabetical questioning meets both optima for every fit list: 177 readings across the 175 feasible pairs, or 317 across all 225 when blockage matters. These optima assume unit-price membership readings, a reliable immediate exchange, no batching, and the two stated objectives. Read the recurrence.
When is the conversation worth the interruption?
Across the 175 feasible menu pairs counted once each, the three-reading one-way plans use 525 inspections and 175 outbound reports. Dialogue uses 177 inspections, 177 questions and 177 replies. With either direction of contact priced the same, dialogue trades 179 extra contacts for 348 fewer inspections. On the hardest single move it still takes three inspections and can interrupt the team six times. Give the alternatives your own prices below.
| Arrangement | Settled pairs | Effort per move |
|---|
These are invented prices and menu weights. A named request and a codeword can take different amounts of time in practice. The calculator assigns the same price to a short reply and an outbound survey report and excludes setup, codebook learning and maintenance. A known service passage supplies a different physical option. Its availability, setup cost, permission and suitability would need their own evidence.
Where the guarantee ends
The readings and meanings are correct, the two private menus stay fixed for the episode, and everyone uses the same known protocol. Questions in the dialogue reach the surveyor. On a current channel the requested replies arrive before action. For the loss controls no current answer gets through; the procedure stops asking after the first unusable answer. No information is encoded in silence. Partial delivery, a changing route during the survey, belief in a false answer, retries and date authentication require a different model. An older report might happen to be correct but has no evidential force here.
Each agreed survey tree and dialogue is finite. With a current channel, permission to move and the stated feasibility conditions, every successful branch reaches a justified decision within the stated bound. Holding on insufficient evidence is safe but cannot deliver a route-selection guarantee. A route selection does not move the exhibit or establish readiness to reopen. For those separate checkpoints see Local signals. A receiver can use the ordinary checklist or the actor table above to recover the same calls; the search adds a lower bound, alternative inspection orders, explicit costs and checkable failures. No practitioner performance was measured.
What the sources contribute
- Bolander's perspective on possible worlds and uniform actions motivates keeping together situations with the same local observation. Here inspection is a Boolean reading and the trees have explicit bounds. A Gentle Introduction to Epistemic Planning, §§6, 7 and 9.
- Engesser, Bolander, Mattmüller and Nebel give actions owners and require applicability and uniformity from their point of view. The surveyor’s encoder and handler’s decoder obey those restrictions. We investigate one agreed policy at a time. Cooperative Epistemic Multi-Agent Planning, §3, especially Definitions 9–11.
- Moses connects necessary conditions on deliberate actions to knowledge at the actor. Our finite intersection test directly checks what the handler can justify. The paper’s qualification on asynchronous settings matters, and knowledge alone does not confer authority. Knowledge of Preconditions, Theorem 3.1 and note 2.
- Halpern and Moses distinguish delivery, the recipient’s knowledge and the sender’s knowledge of receipt. We model the arrival needed for a single recipient's decision and make no claim of common knowledge. Knowledge and Common Knowledge, §§4–6 and 8.
- Hutchins’ cockpit account shows how a marker and a spoken cue redistribute work across people and artefacts. That motivates comparing the checklist, adaptive code card, dialogue and service passage. It supplies no museum timings. How a Cockpit Remembers Its Speeds, manuscript pp. 14–20.
- Four further readings sharpen the limits. Bolander, Burigana and Montali’s depth counts levels of nested belief; our bound counts physical readings. Belardinelli and Bolander allow unattended propositions and false defaults; our model assumes a current answer is understood. Depth-Bounded Epistemic Planning, §§4–7 · Attention!, §§3–5 (corrected version).
- Taylor’s external representations and Wynn and Clarkson’s account of maintaining a process library raise a practical cost our calculation excludes. Someone has to teach and maintain the 126-meaning codebook. Their observation that participants can miss an invalidation is also a reason to distinguish an old answer from a current one. Taylor, closing discussion · Wynn and Clarkson, §§6.2.3 and 6.3.
The museum assumptions, probes, dialogue, finite searches and certificates are our constructions. The antichain bound and relation to chain partitions use classical Dilworth order theory. We make no claim of priority for these combinatorial results.
Four-passage results and two-passage cases (JSON) · Recalculation program · Executable survey and handler rules · Larger certificates. The independent actor and decision-table check reconstructs the four-passage outcomes from local transcripts, examines all 576 inspection trees, and exercises withheld authority and unusable reports. The larger checker decodes every admitted fit/building pair without calling the codebook generator. With Node installed, the repository runs node --test model/*.test.mjs and node model/export-survey.mjs --check.