Classification of $\sigma$-validity in iterated announcements

Abstract

In their 2018 paper, Agotnes, van Ditmarsch, and Wang extended the notions of success and self-refutation in public announcements to true lies, impossible lies, and $\sigma$-validity in general. Here, $\sigma$ is a finite or infinite sequence of $0$s and $1$s. For example, successful formulas and self-refuting formulas are $11$-valid and $10$-valid, respectively. They then posed a conjecture on the classification of such sequences in terms of $\sigma$-validity. In this paper, we disprove the conjecture and give corrected classifications for multi-agent K45, single-agent KD45, multi-agent KD45 with more than one agent, and multi-agent S5 after reformulating the statement more explicitly. The results indicate that there is an asymmetry between truthful announcements and false announcements: the former are stable while the latter are fragile in general. In particular, all successful formulas remain true forever while some impossible lies can be true at some point when repeatedly announced. Also, although some self-refuting formulas can become true again after following the truth pattern $10$, all $100$-valid formulas are destructive in the sense that they remain false forever once they become false. On the other hand, some true lies are fragile in the sense that truths created by lying can become false again.

21 pages, 4 figures. v2: Added proofs of the nonexistence of non-trivially 0k1-valid and 01k0-valid formulas in multi-agent KD45, thereby completing the classification for this class. Revised related statements and proofs throughout. v3: Added a link to the GitHub repository containing the Lean 4 formalization