{"id":5531,"date":"2023-04-09T12:49:48","date_gmt":"2023-04-09T04:49:48","guid":{"rendered":"http:\/\/tsinghualogic.net\/JRC\/?page_id=5531"},"modified":"2023-06-30T16:53:50","modified_gmt":"2023-06-30T08:53:50","slug":"logicandgames","status":"publish","type":"page","link":"http:\/\/tsinghualogic.net\/JRC\/toss\/logicandgames\/","title":{"rendered":"<strong>Logic and Games<\/strong>"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"5531\" class=\"elementor elementor-5531\" data-elementor-settings=\"[]\">\n\t\t\t\t\t\t\t<div class=\"elementor-section-wrap\">\n\t\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-9eaec54 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9eaec54\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7dc3cc7\" data-id=\"7dc3cc7\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a3b0166 elementor-widget elementor-widget-heading\" data-id=\"a3b0166\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.5.6 - 28-02-2022 *\/\n.elementor-heading-title{padding:0;margin:0;line-height:1}.elementor-widget-heading .elementor-heading-title[class*=elementor-size-]>a{color:inherit;font-size:inherit;line-height:inherit}.elementor-widget-heading .elementor-heading-title.elementor-size-small{font-size:15px}.elementor-widget-heading .elementor-heading-title.elementor-size-medium{font-size:19px}.elementor-widget-heading .elementor-heading-title.elementor-size-large{font-size:29px}.elementor-widget-heading .elementor-heading-title.elementor-size-xl{font-size:39px}.elementor-widget-heading .elementor-heading-title.elementor-size-xxl{font-size:59px}<\/style><h5 class=\"elementor-heading-title elementor-size-default\">Course Description<\/h5>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7925f212 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7925f212\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-1486382a\" data-id=\"1486382a\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-438b0116 elementor-widget elementor-widget-text-editor\" data-id=\"438b0116\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.5.6 - 28-02-2022 *\/\n.elementor-widget-text-editor.elementor-drop-cap-view-stacked .elementor-drop-cap{background-color:#818a91;color:#fff}.elementor-widget-text-editor.elementor-drop-cap-view-framed .elementor-drop-cap{color:#818a91;border:3px solid;background-color:transparent}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap{margin-top:8px}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap-letter{width:1em;height:1em}.elementor-widget-text-editor .elementor-drop-cap{float:left;text-align:center;line-height:1;font-size:50px}.elementor-widget-text-editor .elementor-drop-cap-letter{display:inline-block}<\/style>\t\t\t\t<p><!-- wp:paragraph --><!-- \/wp:paragraph --><!-- wp:heading {\"level\":4} --><\/p>\n<p>This course will discuss the inter-connection between logic and games, focussing on both \u2018games for logic\u2019 and \u2018logic for games\u2019 perspectives. On one hand we will study various logical concepts that can be viewed as games, on the other hand, we will study various game-theoretic concepts from the logical viewpoint. A connection involving this dual dependency between logic and games will also be discussed. We will conclude with providing some current research directions in these areas.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:paragraph --><\/p>\n<ul>\n<li>Lecturer:<a href=\"https:\/\/www.isichennai.res.in\/~sujata\/\">Sujata Ghosh<\/a>\u00a0(Indian Statistical Institute) and Jeremy Seligman (Tsinghua University and University of Auckland)<\/li>\n<li>TA: Li Lei (\u674e\u78ca, lilei19@mails.tsinghua.edu.cn)\u00a0<\/li>\n<li>Time: 13:30-16:05, 26 June \u2013 30 June<\/li>\n<li>Venue:\u00a0\u4e09\u65593104<\/li>\n<li>Zoom ID:\u00a081707963268<\/li>\n<\/ul>\n<p><!-- \/wp:paragraph --><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-fc54a75 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fc54a75\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-9782440\" data-id=\"9782440\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1a29d47 elementor-widget elementor-widget-heading\" data-id=\"1a29d47\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h5 class=\"elementor-heading-title elementor-size-default\">Schedule<\/h5>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-425b85d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"425b85d\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-93b4879\" data-id=\"93b4879\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-087b88d elementor-widget elementor-widget-text-editor\" data-id=\"087b88d\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><strong>Day 1<\/strong>: We will first introduce some game-theoretic concepts with examples, to set the stage for our subsequent discussion. Then we will introduce first-order logic and propositional modal logic over graphs and certain games corresponding to distinct semantic concepts in logic.<\/p>\n<p><strong>Day 2<\/strong>: We will delve deeper into the \u2018games for logic\u2019 perspective and continue studying games related to the various semantic concepts, and describe the connection between the existence of winning strategies for players in the respective logic games vis-\u00e1-vis the corresponding query in the logic frameworks.<\/p>\n<p><strong>Day 3<\/strong>: We will shift our focus from \u2018games for logic\u2019 to \u2018logic for games\u2019 and introduce Parikh\u2019s game logic [8] and its variants to begin with. Then we will build up a connection between these game logics and the model-checking or the evaluation games we discussed earlier.<\/p>\n<p><strong>Day 4<\/strong>: We will merge the discussion on games, logics and graphs by presenting certain logics describing games on graphs, a topic that has picked up a renewed interest following van Benthem and Liu [10]. We will particularly focus on on cops and robber game and sabotage game.<\/p>\n<p><strong>Day 5<\/strong>: Before finishing, we concentrate on strategic reasoning in games on graphs and relevant logic frameworks. We will end with giving pointers to further challenges, especially involving studies on imperfect and incomplete information.<\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-249113c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"249113c\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b0f2cc3\" data-id=\"b0f2cc3\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1e5559b elementor-widget elementor-widget-heading\" data-id=\"1e5559b\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h5 class=\"elementor-heading-title elementor-size-default\">Background Knowledge\u200b<\/h5>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d3d56b3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d3d56b3\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e37ef01\" data-id=\"e37ef01\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c4b7e7e elementor-widget elementor-widget-text-editor\" data-id=\"c4b7e7e\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p>This course will only assume knowledge of basic propositional logic and will not assume any knowledge about concepts in game theory [5]. We will introduce the syntax of first order logic [1] and propositional modal logic [2]. We will mainly consider graphs as our models while we introduce these frameworks. For the first order logic part as well as the \u2018games for logic\u2019 part you can have a look at Models and Games, by\u00a0V\u00e4\u00e4n\u00e4nen [4]. A detailed analysis on both games for logic and logic for games can be found in Logic in Games, by van Benthem [3].<\/p>\n<p>In general, it would be helpful if you have some understanding about these logics beforehand. Also, we will mention several technical results involving axiom systems, completeness, decidability, satisfiability, model-checking, homomorphisms and isomorphisms, and bisimulation, among others. We will explain all these concepts in the course, but if you have not seen them before, it would be better to read them up from some logic book. All these concepts are explained in details in the book, Modal Logic, by Blackburn, de Rijke and Venema [2].<\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6e950da elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6e950da\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-918a399\" data-id=\"918a399\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-fd1acc3 elementor-widget elementor-widget-text-editor\" data-id=\"fd1acc3\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><strong>References:<\/strong><\/p>\n<p>A list of relevant books, research papers, tutorial articles is given below (to be updated as the course progresses).<\/p>\n<p>* Some text books on first-order and modal logics<\/p>\n<p>[1] A mathematical introduction to logic: H.B. Enderton, Academic Press, 2nd edition, 2001.<\/p>\n<p>[2] Modal logic: P. Blackburn, M. de Rijke and Y. Venema, Cambridge University Press, 2001.<\/p>\n<p>* Some text books on logic and games<\/p>\n<p>[3] Logic in games: J. van Benthem, The MIT Press, 2014.<\/p>\n<p>[4] Models and games: J. V\u00e4\u00e4n\u00e4nen, Cambridge University Press, 2011.<\/p>\n<p>* Some text books on game theory<\/p>\n<p>[5] A course in game theory: M.J. Osborne and A. Rubinstein, The MIT Press, 1994.<\/p>\n<p>[6] Game theory: A playful introduction: M. DeVos and D.A. Kent, AMS, 2016.<\/p>\n<p>* A tutorial article on logics, games and strategies<\/p>\n<p>[7] Strategies in games: A logic-automata study: S. Ghosh and R. Ramanujam, LNCS 7388, Springer, pp. 110-159, 2012.<\/p>\n<p>* Articles on game logics<\/p>\n<p>[8] The logic of games and its applications: R. Parikh, Annals of Discrete Mathematics, 24:111-140, 1985.<\/p>\n<p>[9] Logic games are complete for game logics: J. van Benthem, Studia Logica 75:183-203, 2003.<\/p>\n<p>* A recent article on logic and graph games<\/p>\n<p>[10] Graph games and logic design: J. van Benthem and F. Liu, Knowledge, Proof and Dynamics, Logic in Asia: Studia Logica Library, Springer, pp. 125-146, 2020.<\/p>\n<p>* On Cops and Robber games<\/p>\n<p>[11] The game of cops and robbers on graphs, A. Bonato and R.J. Nowakowski, AMS, 2011<\/p>\n<p>[12] A simple logic of the hide and seek game: D. Li, S. Ghosh, F. Liu and Y. Tu, Studia Logica, 2023.<\/p>\n<p>* On Sabotage games<\/p>\n<p>[13] An essay on sabotage and obstruction: J. van Benthem, LNCS 2605, pp. 268 &#8211; 276, 2005.<\/p>\n<p>[14] Modal logics of sabotage revisited: G. Aucher, J. van Benthem and D. Grossi, Journal of Logic and Computation 28(2):269-303, 2018.<\/p>\n<p>\u00a0<\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7b7617b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7b7617b\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-871e7cc\" data-id=\"871e7cc\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-370b181 elementor-widget elementor-widget-heading\" data-id=\"370b181\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h5 class=\"elementor-heading-title elementor-size-default\">Materials\n<\/h5>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6d0419d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6d0419d\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ca86e06\" data-id=\"ca86e06\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-54843aa elementor-widget elementor-widget-text-editor\" data-id=\"54843aa\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p>Please access the slides and accompanying handout through the following link: <a href=\"https:\/\/cloud.tsinghua.edu.cn\/d\/72ad90e4156d4b1389e4\/\">https:\/\/cloud.tsinghua.edu.cn\/d\/72ad90e4156d4b1389e4\/<\/a><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2dedaff elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2dedaff\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-94d5d7f\" data-id=\"94d5d7f\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-013d02c elementor-widget elementor-widget-heading\" data-id=\"013d02c\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h5 class=\"elementor-heading-title elementor-size-default\">Recordings<\/h5>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-04bbbb0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"04bbbb0\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-473fa3c\" data-id=\"473fa3c\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-be739e3 elementor-widget elementor-widget-text-editor\" data-id=\"be739e3\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<ul>\n<li><a href=\"https:\/\/www.bilibili.com\/video\/BV1Sm4y1a7yP\/?vd_source=fb9ec1a5fa103c470ae94d592a2f5c66\">Lecture-1<\/a><\/li>\n<li><a href=\"https:\/\/www.bilibili.com\/video\/BV1uF411o7J2\/?vd_source=fb9ec1a5fa103c470ae94d592a2f5c66\">Lecture-2 (Part I)<\/a> \u00a0 \u00a0<a href=\"https:\/\/www.bilibili.com\/video\/BV1BX4y1p7nQ\/?vd_source=fb9ec1a5fa103c470ae94d592a2f5c66\">Lecture-2 (Part II)<\/a><\/li>\n<li><a href=\"https:\/\/www.bilibili.com\/video\/BV1Rj411S7uy\/?spm_id_from=333.999.0.0&amp;vd_source=fb9ec1a5fa103c470ae94d592a2f5c66\">Lecture-3<\/a><\/li>\n<li><a href=\"https:\/\/cloud.tsinghua.edu.cn\/d\/72ad90e4156d4b1389e4\/\">Lecture-4 and Lecture-5<\/a><\/li>\n<\/ul>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Course Description This course will discuss the inter-c [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1854,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/pages\/5531"}],"collection":[{"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/comments?post=5531"}],"version-history":[{"count":28,"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/pages\/5531\/revisions"}],"predecessor-version":[{"id":6260,"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/pages\/5531\/revisions\/6260"}],"up":[{"embeddable":true,"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/pages\/1854"}],"wp:attachment":[{"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/media?parent=5531"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}