Logics for Agents with Bounded Rationality [PhD Thesis]

1 Introduction 3
1.1 Main Work and its Significance . . . . . . . . . . . . . . . . . . . . . 3
1.2 Organizations of This Thesis . . . . . . . . . . . . . . . . . . . . . . . 5
I Logics for Belief Dependence 9
2 Bounded Rationality and Belief Dependence 11
2.1 Bounded Rationality: the wide interpretation . . . . . . . . . . . . . 11
2.2 Belief Dependence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Compartmentalized Information and Incorporated Information 13
2.2.2 The Roles of Source Indexing of Information . . . . . . . . . . 15
2.3 Logics of Knowledge and Belief and Logical Omniscience . . . . . . . 16
2.3.1 General Logic of Knowledge and Beliefs . . . . . . . . . . . . . 16
2.3.2 The Problem of Logical Omniscience . . . . . . . . . . . . . . 18
2.4 Syntactic Considerations for Logics of Belief Dependence . . . . . . . 23
2.5 General Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Formalizing Belief Dependence 27
3.1 Several Plausible Systems . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.1 Belief Dependence Systems Based on the Epistemic Operator
and the Dependency Operator . . . . . . . . . . . . . . . . . . 27
3.1.2 Belief Dependence System Based on Sub-belief Operator . . . 29
3.2 Formalizing Suspicion and Other Features . . . . . . . . . . . . . . . 31
3.3 Formalizing Indirect Dependence . . . . . . . . . . . . . . . . . . . . 34
4 Semantic Models 37
4.1 L-Model of Belief Dependence: an approach based on general epistemic
logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 D-Model of Belief Dependence: a syntactic approach . . . . . . . . . 39
4.2.1 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2.2 Soundness and Completeness . . . . . . . . . . . . . . . . . . 41
4.2.3 Decidability and Complexity . . . . . . . . . . . . . . . . . . . 44
4.3 Lij-Model: An Adapted Possible World Approach . . . . . . . . . . . 46
4.3.1 Semantics and Lij Logics . . . . . . . . . . . . . . . . . . . . 46
4.3.2 Decidability and Complexity . . . . . . . . . . . . . . . . . . . 48
4.4 A Brief Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5 Belief Dependence, Revision, and Persistence 55
5.1 Belief Maintenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2 A Bit of Belief Revision Theories . . . . . . . . . . . . . . . . . . . . 56
5.3 Belief Maintenance Under the Framework of Logics of Belief Dependence 58
5.4 Types of Belief Maintenance Operation . . . . . . . . . . . . . . . . . 59
5.5 A Belief Maintenance Strategy Using Logics of Belief Dependence . . 61
5.5.1 Update Strategies . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.5.2 Role Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.5.3 Roles and Credibilities . . . . . . . . . . . . . . . . . . . . . . 64
5.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6 Information Acquisition from a Multi-agent Environment 67
6.1 Schoenmakers Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2 Combining Information from Multiple Agents; the triviality result . . 69
6.3 Information Acquisition in a Belief Dependence Framework . . . . . . 74
6.4 Almost Safety . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.5 Almost Safety on Belief Maintenance Operation . . . . . . . . . . . . 79
6.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7 Conclusions and Further Work 85
7.1 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
7.2 Further Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
7.2.1 More General Semantic Models . . . . . . . . . . . . . . . . . 85
7.2.2 Other Complexity Problems . . . . . . . . . . . . . . . . . . . 86
7.2.3 Alternative Almost Safety Belief Maintenance Operations . . . 87
II Action Logics for Agents with Bounded Rationality 89
8 Introduction 91
8.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
8.2 General Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . 92
8.3 Conditional and Update . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.3.1 Counterfactuals and Conditional Logic . . . . . . . . . . . . . 95
8.3.2 Reasoning about Actions . . . . . . . . . . . . . . . . . . . . . 97
8.3.3 Update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
9 Preference Logics 99
9.1 Preferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
9.2 A Preference Logic Based on the Notion of Minimal Change . . . . . 101
9.2.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
9.2.2 Formal Semantics (MCP-Semantics) . . . . . . . . . . . . . . 102
9.2.3 An Axiomatic Characterization of Preference Relations . . . . 104
9.3 From Preference Statements to Preferences on Possible Worlds . . . . 109
9.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
9.4.1 Other Approaches to Preference Logic . . . . . . . . . . . . . 113
9.4.2 Counterexamples . . . . . . . . . . . . . . . . . . . . . . . . . 114
9.5 Transitivity of Preferences . . . . . . . . . . . . . . . . . . . . . . . . 115
10 ALX1: A Propositional ALX Logic 119
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
10.2 Formal Syntax and Semantics . . . . . . . . . . . . . . . . . . . . . . 119
10.2.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
10.2.2 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
10.3 Formal Properties of ALX1 . . . . . . . . . . . . . . . . . . . . . . . 123
10.4 Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
10.5 The Finite Model Property of ALX1 . . . . . . . . . . . . . . . . . . 134
10.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
10.6.1 Goodness, Badness and Indifference . . . . . . . . . . . . . . . 145
10.6.2 Preferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
10.6.3 Minimal Change and Actions . . . . . . . . . . . . . . . . . . 147
11 ALX3: A Multi-agent ALX Logic 155
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
11.2 Formal Syntax and Semantics . . . . . . . . . . . . . . . . . . . . . . 155
11.2.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
11.2.2 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
11.3 Formal Properties of ALX3 . . . . . . . . . . . . . . . . . . . . . . . 160
11.3.1 Soundness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
11.3.2 More Properties about Action Operators . . . . . . . . . . . . 161
11.4 Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
11.5 More Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
11.5.1 Necessity and Possibility . . . . . . . . . . . . . . . . . . . . . 174
11.5.2 Beliefs and Knowledge . . . . . . . . . . . . . . . . . . . . . . 178
11.6 Application of ALX3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
11.6.1 Second Order Quantifier on Preference Formulas . . . . . . . . 179
11.6.2 Agents and Accessible States . . . . . . . . . . . . . . . . . . 184
11.6.3 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11.6.4 Power . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
11.6.5 Cooperation and Coordination . . . . . . . . . . . . . . . . . . 191
11.7 Comparing ALX with Other Action Logics . . . . . . . . . . . . . . . 192
11.7.1 Other Action Logics . . . . . . . . . . . . . . . . . . . . . . . 192
11.7.2 Expressibility in Other Action Logics . . . . . . . . . . . . . . 193
11.7.3 Avoidance of Counterintuitive Properties . . . . . . . . . . . . 194
11.7.4 Comparison by Examples . . . . . . . . . . . . . . . . . . . . 195
11.8 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
11.8.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
11.8.2 Bounded Rationality . . . . . . . . . . . . . . . . . . . . . . . 196
Bibliography 199
Index 206
List of symbols 210
Samenvatting 213