nach oben

Minds and Machines

Erschienen in:

01.03.2013

Reasoning About Agent Types and the Hardest Logic Puzzle Ever

verfasst von: Fenrong Liu, Yanjing Wang

Erschienen in: Minds and Machines | Ausgabe 1/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we first propose a simple formal language to specify types of agents in terms of necessary conditions for their announcements. Based on this language, types of agents are treated as ‘first-class citizens’ and studied extensively in various dynamic epistemic frameworks which are suitable for reasoning about knowledge and agent types via announcements and questions. To demonstrate our approach, we discuss various versions of Smullyan’s Knights and Knaves puzzles, including the Hardest Logic Puzzle Ever (HLPE) proposed by Boolos (in Harv Rev Philos 6:62–65, 1996). In particular, we formalize HLPE and verify a classic solution to it. Moreover, we propose a spectrum of new puzzles based on HLPE by considering subjective (knowledge-based) agent types and relaxing the implicit epistemic assumptions in the original puzzle. The new puzzles are harder than the previously proposed ones in the literature, in the sense that they require deeper epistemic reasoning. Surprisingly, we also show that a version of HLPE in which the agents do not know the others’ types does not have a solution at all. Our formalism paves the way for studying these new puzzles using automatic model checking techniques.

Vorheriger Artikel An Ontology-Based Approach to Metaphor Cognitive Computation

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Boolos credits Raymond Smullyan as the originator of the puzzle and John McCarthy for adding the twist of ja and da.

Since D’s type is irrelevant, we omit it in the model.

Truth values of epistemic formulas may not be preserved after announcement. For a study in the setting of PAL , we refer to (van Ditmarsch and Kooi 2006) and (Holliday and Icard III 2010).

We conjecture that \({\tt PALT}^{\bf T}\) is at least exponentially more succinct than \({\tt PAL}^{\bf T},\) but leave the proof for future work.

See (van Benthem and Minică 2009) for a similar composition issue in dynamic-epistemic logics of questions and answers.

See (Wang 2011a, b) for other applications of the context dependent semantics in DEL.

I.e., (Q∪ F, δ) is an acyclic graph where each node except r has one and only one u-predecessor for each \(u\in{\bf U}, \) and r can reach all other nodes.

We adopt the name of the lemma from (Rabern and Rabern 2008).

A subjective bluffer is the same as an objective one.

We conjecture that even when D can ask questions privately, the puzzle \({({\mathfrak{M}}_1,\theta)}\) still does not have any solution.

Interested readers may consult (Blackburn et al. 2002) for the preservation result of positive formulas in the standard setting of modal logic.

For instance, according to the semantics when s is in the shape of \({\tt STT}\_\_{\tt JA}, \lambda(A,s)(I(s,\phi, ja),A)=K_A\phi\). Therefore when answering ja, the updated model keeps the worlds satisfying \(K_A\phi\land{\tt STT}(A)\).

Blackburn, P., de Rijke, M., & Venema, Y. (2002). Modal logic. Cambridge University Press, Cambridge

Boolos, G. (1996). The hardest logic puzzle ever. The Harvard Review of Philosophy, 6, 62–65.MathSciNet

Clarke, E. M., Grumberg, O., & Peled, D. A. (1999). Model Checking. Cambridge, MA: The MIT Press.

French, T., van der, Hoek, W., Iliev, P., & Kooi, B. P. (2011). Succinctness of epistemic languages. In: T. Walsh (Ed.) Proceedings of the twenty-second international joint conference on artificial intelligence (IJCAI), pp 881–886.

Gerbrandy, J., & Groeneveld, W. (1997). Reasoning about information change. Journal of Logic, Language and Information 6(2), 147–169.MathSciNetMATHCrossRef

Holliday, W., & Icard III. T. (2010). Moorean phenomena in epistemic logic. In: Advances in modal logic, pp 178–199.

Liu, F. (2004). Dynamic variations: Update and revision for diverse agents. Master’s thesis, MoL-2004-05. ILLC, University of Amsterdam.

Liu, F. (2009). Diversity of agents and their interaction. Journal of Logic,Language and Information, 18(1), 23–53.MathSciNetMATHCrossRef

Lutz, C. (2006). Complexity and succinctness of public announcement logic. In: P. Stone, G. Weiss (Eds.) Proceedings of the fifth international joint conference on autonomous agents and multiagent systems (AAMAS ’06), (pp. 137–143). New York, NY: ACM.

Minică, S. (2011). Dynamic logic of questions. PhD thesis, Universiteit van Amsterdam.

Plaza, J. (2007). Logics of public communications. Synthese, 158(2), 165–179.MathSciNetMATHCrossRef

Rabern, B., & Rabern, L. (2008). A simple solution to the hardest logic puzzle ever. Logic and Analysis, 68, 105–112.MathSciNetMATH

Smullyan, R. (1978). What is the name of this book. Englewood Cliffs, NJ: Prentice-Hall.MATH

Uzquiano, G. (2010). How to solve the hardest logic puzzle ever in two questions. Logic and Analysis, 70, 39–44.MathSciNetMATH

van Benthem, J., & Minică, S. (2009). Toward a dynamic logic of questions. In: X. He, J. F. Horty, E. Pacuit (Eds.), Proceedings of the 2nd international workshop on logic, rationality and interaction (LORI-II), vol. 5834, (pp. 27–41). Berlin: Springer, FoLLI-LNAI.

van Ditmarsch, H. (2011). The Ditmarsch tale of wonders—dynamics of lying. Manuscript.

van Ditmarsch, H., & Kooi, B. (2006). The secret of my success. Synthese, 153(2), 339–347MathSciNetCrossRef

van Ditmarsch,H. van der Hoek,W., & Kooi, B. (2007) Dynamic epistemic logic. Berlin: Springer.

van Ditmarsch, H., van Eijck, J., Sietsma, F., & Wang, Y. (2011). On the logic of lying. In: J. van Eijck, R. Verbrugge (Eds.), Games, actions and social software, (pp 41–72). Berlin: Springer.

Wang, Y. (2011a). On axiomatizations of PAL. In: H. van Ditmarsch, J. Lang,S. Ju (Eds.), Proceedings of the 3nd international workshop on logic, rationality and interaction (LORI-III), vol. 6953, pp. 314–327. Berlin: Springer, FoLLI-LNAI.

Wang, Y. (2011b). Reasoning about protocol change and knowledge. In: M. Banerjee, A. Seth (Eds.), Proceedings of the 4th Indian conference on logic and its applications (ICLA), vol 6521, pp. 189–203. Berlin: Springer, LNCS.

Wheeler, G. R., & Barahona, P. (2012). Why the hardest logic puzzle ever cannot be solved in less than three questions. Journal of Philosophical Logic, 41(2), 493–503.MathSciNetMATHCrossRef

Wintein, S. (2011). On the behavior of true and false. Minds and Machines, 22(1), 1–24.CrossRef

Titel: Reasoning About Agent Types and the Hardest Logic Puzzle Ever
verfasst von: Fenrong Liu
Yanjing Wang
Publikationsdatum: 01.03.2013
Verlag: Springer Netherlands
Erschienen in: Minds and Machines / Ausgabe 1/2013
Print ISSN: 0924-6495
Elektronische ISSN: 1572-8641
DOI: https://doi.org/10.1007/s11023-012-9287-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2013

Proof Systems for Planning Under Cautious Semantics

Preferential Semantics for Plausible Subsumption in Possibility Theory

Logic and AI in China: An Introduction

Variable-Centered Consistency in Model RB

An Ontology-Based Approach to Metaphor Cognitive Computation

A Lewisian Logic of Causal Counterfactuals