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