The Temporal Mind: Observations on the logic of belief change in interactive systems [PhD Thesis]

1 Introduction 1 1.1 Logic, belief change and rational agency . . . . . . . . . . . . . . 1 1.2 Perspectives on intelligent interaction . . . . . . . . . . . . . . . . 3 1.3 Logics of knowledge and belief . . . . . . . . . . . . . . . . . . . . 6 1.3.1 AGM and plausibility orderings . . . . . . . . . . . . . . . 6 1.3.2 Epistemic models and epistemic logics . . . . . . . . . . . 7 1.3.3 Epistemic plausibility models and doxastic logics . . . . . 10 1.4 Global vs local models of rational agency . . . . . . . . . . . . . . 13 1.5 Game theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.5.1 On the interpretation of games . . . . . . . . . . . . . . . 14 1.5.2 Games as models. . . . . . . . . . . . . . . . . . . . . . . . 15 1.6 Dynamic and temporal logics for belief change . . . . . . . . . . . 18 1.6.1 Dynamic logics . . . . . . . . . . . . . . . . . . . . . . . . 19 1.6.2 Temporal logics . . . . . . . . . . . . . . . . . . . . . . . . 21 1.7 Expressive power of extended modal languages . . . . . . . . . . . 23 1.8 Recapitulation and coda . . . . . . . . . . . . . . . . . . . . . . . 26 Summary and sources of the chapters 29 2 Bridges between dynamic doxastic and doxastic temporal logics 31 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2 Background results . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3 Dynamic logics of stepwise belief change (DDL) . . . . . . . . . . 35 2.3.1 Plausibility models: static doxastic situations . . . . . . . 35 2.3.2 Describing doxastic events . . . . . . . . . . . . . . . . . . 35 2.4 Doxastic temporal models: the global view . . . . . . . . . . . . . 38 2.5 From DDL models to doxastic temporal models . . . . . . . . . . 39 2.6 Crucial frame properties for priority update . . . . . . . . . . . . 41 2.6.1 Bisimulation invariance . . . . . . . . . . . . . . . . . . . . 41 2.6.2 Agent-oriented properties . . . . . . . . . . . . . . . . . . 42 2.7 The main representation theorem . . . . . . . . . . . . . . . . . . 43 2.8 Extension to arbitrary pre-orders . . . . . . . . . . . . . . . . . . 45 2.9 Additional extensions and variations of the theorem . . . . . . . . 48 2.9.1 From uniform to local protocols . . . . . . . . . . . . . . . 49 2.9.2 Languages and bisimulations . . . . . . . . . . . . . . . . . 49 2.9.3 Alternative model classes . . . . . . . . . . . . . . . . . . . 49 2.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3 Merging modal logics of belief change: languages and logics 53 3.1 Epistemic doxastic languages . . . . . . . . . . . . . . . . . . . . . 53 3.2 Dynamic doxastic languages . . . . . . . . . . . . . . . . . . . . . 58 3.2.1 Interpreting dynamic modalities . . . . . . . . . . . . . . . 59 3.2.2 Completeness via recursion axioms . . . . . . . . . . . . . 60 3.3 Doxastic epistemic temporal languages . . . . . . . . . . . . . . . 62 3.3.1 Simple doxastic epistemic temporal languages . . . . . . . 63 3.3.2 Branching-time doxastic temporal languages . . . . . . . . 64 3.3.3 Defining the frame conditions for priority update . . . . . 65 3.3.4 A first bit of axiomatics . . . . . . . . . . . . . . . . . . . 70 3.3.5 Variations and extensions of the language . . . . . . . . . 71 3.3.6 Correspondence for doxastic and dynamic formulas . . . . 73 3.4 Axiomatizing protocols-based dynamic logics of belief revision . . 74 3.4.1 Dynamic logic of protocol-based belief revision . . . . . . . 75 3.4.2 Proving axiomatic completeness. . . . . . . . . . . . . . . . 77 3.4.3 More languages . . . . . . . . . . . . . . . . . . . . . . . . 85 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4 Agreement Theorems in Dynamic-Epistemic Logic 89 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.2.1 Epistemic plausibility models . . . . . . . . . . . . . . . . 90 4.2.2 Doxastic-epistemic logic . . . . . . . . . . . . . . . . . . . 92 4.2.3 Information, priors, posteriors and agreement . . . . . . . 92 4.3 Static agreement and well-foundedness . . . . . . . . . . . . . . . 93 4.4 Expressive power and syntactic proofs . . . . . . . . . . . . . . . 96 4.5 Agreement via dialogues . . . . . . . . . . . . . . . . . . . . . . . 102 4.5.1 Agreement via conditioning . . . . . . . . . . . . . . . . . 102 4.5.2 Agreement via public announcements . . . . . . . . . . . . 105 4.5.3 Comparing agreement via conditioning and public announcements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.6 Definability of fixed points . . . . . . . . . . . . . . . . . . . . . . 109 4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5 Learning from the perspective of modal logics of belief change 115 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.2 Formal learning theory . . . . . . . . . . . . . . . . . . . . . . . . 116 5.3 Modal logics of belief change . . . . . . . . . . . . . . . . . . . . . 119 5.3.1 Temporal models and languages for belief change . . . . . 119 5.3.2 The dynamic approach . . . . . . . . . . . . . . . . . . . . 120 5.3.3 Connecting the temporal and the dynamic approach . . . . 121 5.4 Analyzing learnability in a DETL framework . . . . . . . . . . . . 122 5.4.1 Protocols that correspond to set learning . . . . . . . . . . 123 5.4.2 DETL characterization of finite identifiability . . . . . . . 123 5.4.3 Characterizing protocols that guarantee learnability . . . . 125 5.5 About multi-agent (interactive) learning . . . . . . . . . . . . . . 127 5.6 Conclusions and perspectives . . . . . . . . . . . . . . . . . . . . . 129 6 Strategic reasoning 131 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.2 Game structure and actual play . . . . . . . . . . . . . . . . . . . 132 6.3 Using the game structure as a model . . . . . . . . . . . . . . . . 135 6.3.1 Extensive games of imperfect information as ETL models . 135 6.3.2 Reasoning about games with a logic of programs . . . . . . 137 6.4 Solution concepts changing the models . . . . . . . . . . . . . . . 140 6.5 Past-oriented beliefs in equilibrium . . . . . . . . . . . . . . . . . 144 6.6 Future we can believe in . . . . . . . . . . . . . . . . . . . . . . . 146 6.6.1 Revising expectations . . . . . . . . . . . . . . . . . . . . . 148 6.6.2 Enriching the temporal structure . . . . . . . . . . . . . . 149 6.7 A dynamic approach to strategic reasoning . . . . . . . . . . . . . 151 6.7.1 Is backward induction logical? . . . . . . . . . . . . . . . . 151 6.7.2 Exploring the logical dynamics of backward induction . . . 152 6.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 7 Logics of cooperation: Expressivity and complexity 159 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 7.2 The models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 7.3 The notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 7.4 Modal languages and their expressivity . . . . . . . . . . . . . . . 167 7.5 Invariance and closure results . . . . . . . . . . . . . . . . . . . . 169 7.6 Modal definability . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 7.6.1 Defining local notions . . . . . . . . . . . . . . . . . . . . . 174 7.6.2 Defining global notions . . . . . . . . . . . . . . . . . . . . 176 7.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 8 Conclusion: reasoning about reasoning 179 A Some basics of interactive epistemology 183 B Some basics on modal definability and invariance 185 B.1 Distinguishing pointed models . . . . . . . . . . . . . . . . . . . . 185 B.2 Defining classes of frames . . . . . . . . . . . . . . . . . . . . . . . 187 C Additional proofs for Chapter 2 189 D Additional proofs for Chapter 4 193 E Additional proofs for Chapter 5 199 Samenvatting 217 Abstract 219 Resume 221