LOGICS FOR AGENTS WITH BOUNDED RATIONALITY Zhisheng Huang December 18, 2002
LOGICS FOR AGENTS WITH BOUNDED RATIONALITY
Zhisheng Huang
LOGICS FOR AGENTS WITH BOUNDED RATIONALITY
ILLC Dissertation Series 1994-10
For further information about ILLC-publications, please contact Institute for Logic, Language and Computation Universiteit van Amsterdam Plantage Muidergracht 24 1018 TV Amsterdam phone: +31-20-5256090 fax: +31-20-5255101 e-mail:
[email protected]
Logics for Agents with Bounded Rationality
Academisch Proefschrift ter verkrijging van de graad van doctor aan de Universiteit van Amsterdam, op gezag van de Rector Magnificus Prof.dr P.W.M. de Meijer in het openbaar te verdedigen in de Aula der Universiteit (Oude Lutherse Kerk, ingang Singel 411, hoek Spui) op donderdag 15 december 1994 te 12.00 uur door
Zhisheng Huang geboren te Fujian, China.
Promotor: Dr. Peter van Emde Boas Faculteit Wiskunde en Informatica Universiteit van Amsterdam Plantage Muidergracht 24 1018 TV Amsterdam Co-Promotor: Dr. Michael Masuch Center for Computer Science in Organization and Management (CCSOM) Faculteit der Politieke en Sociaal-Culturele Wetenschappen Universiteit van Amsterdam Oude Turfmarkt 151 1012 GC Amsterdam
c 1994 by Zhisheng Huang Copyright Cover design by Zhisheng Huang ISBN: 90–74795–13–7
Contents
Acknowledgments
1
1 Introduction 1.1 Main Work and its Significance . . . . . . . . . . . . . . . . . . . . . 1.2 Organizations of This Thesis . . . . . . . . . . . . . . . . . . . . . . .
3 3 5
I
9
Logics for Belief Dependence
2 Bounded Rationality and Belief Dependence 2.1 Bounded Rationality: the wide interpretation . . . . . . 2.2 Belief Dependence . . . . . . . . . . . . . . . . . . . . . 2.2.1 Compartmentalized Information and Incorporated 2.2.2 The Roles of Source Indexing of Information . . . 2.3 Logics of Knowledge and Belief and Logical Omniscience 2.3.1 General Logic of Knowledge and Beliefs . . . . . . 2.3.2 The Problem of Logical Omniscience . . . . . . . 2.4 Syntactic Considerations for Logics of Belief Dependence 2.5 General Scenario . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11 11 13 13 15 16 16 18 23 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 v
vi
Contents
4 Semantic Models 4.1 L-Model of Belief Dependence: an approach based on temic logic . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 D-Model of Belief Dependence: a syntactic approach . 4.2.1 Semantics . . . . . . . . . . . . . . . . . . . . . 4.2.2 Soundness and Completeness . . . . . . . . . . 4.2.3 Decidability and Complexity . . . . . . . . . . . 4.3 Lij-Model: An Adapted Possible World Approach . . . 4.3.1 Semantics and Lij Logics . . . . . . . . . . . . 4.3.2 Decidability and Complexity . . . . . . . . . . . 4.4 A Brief Comparison . . . . . . . . . . . . . . . . . . . .
37 general epis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .