دانلود کتاب 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