The Workshop will take place in Oost-Indisch Huis, room E0.02 (VOC room), Oude Hoogstraat 24 (the entrance `Bushuis’ is around the corner at Kloveniersburgwal 48):
Monday, December 2nd
08:45 – 9:00 Welcome and Coffee
09:00 – 9:10 Opening Words: Sonja Smets
Morning Session 1, chair: Sonja Smets
09:10 – 09:55 Christian List, What matters and how it matters: a choice-theoretic representation of moral theories (abstract)
In this talk (based on joint work with Franz Dietrich), I will present a new approach to the formal representation of moral theories, drawing on recent results concerning reason-based rationalisations of choice functions. For the choice-theoretic background, see pdf
09:55 – 10:40 Erik Olsson, Trust and the value of overconfidence: A Bayesian perspective on social network communication (abstract)
The paper presents and defends a Bayesian theory of trust in social networks. In the first part of the paper, we provide justifications for the basic assumptions behind the model, and we give reasons for thinking that the model has plausible consequences for certain kinds of communication. In the second part of the paper we investigate the phenomenon of overconfidence. Many psychological studies have found that people think they are more reliable than they actually are. Using a simulation environment that has been developed in order to make our model computationally tractable we show that in our model inquirers are indeed sometimes better off from an epistemic perspective overestimating the reliability of their own inquiries. We also show, by contrast, that people are rarely better off overestimating the reliability of others. On the basis of these observations we formulate a novel hypothesis about the value of overconfidence.This is joint work with Aron Vallinder.
10:40 – 11:00 Coffee break
Morning Session 2, chair: Paolo Galeazzi
11:00 – 11:45 Jeroen Bruggeman, Social networks and gossip (slides)
11:45 – 14:00 Lunch break
Afternoon Session 1, chair: Nina Gierasimczuk
A variety of socio-informational phenomena based on social proof turn out being notorious variants of each other – in particular BBC – bystanders, bandwagons and cascades. The modular structure of these phenomena is unravelled together with the public signals that (partially) drive them. But public signals may unfortunately be ambiguous – and that complicate matters for real.
In social network theory, (linear deterministic) threshold models, generalized from the work of Granovetter and Schelling, have received much attention in the last decade. Such standard threshold models are meant to capture the spread, or diffusion, of a behavior in a social network where agents are influenced by the choices of their neighbors. The fundamental assumption is that given enough of your neighbors adopt a given behavior, then so will you. Analyses of threshold models then allow one to answer questions about e.g. what small set of agents to initially influence to obtain a maximum spread of behavior through a given network. Threshold models have been used to study a wide variety of phenomena, including contagion, diffusion of medical and technologies innovations, and in viral marketing.In this talk, it is argued that there is however a very prominent type of behavior which cannot reasonably be modeled using standard threshold models, namely the sharing of information. As an alternative, a slightly more complex model type is introduced, and it is argued that it overcomes the primary problem of the standard threshold models in relation to modeling information sharing. The two model types are compared, and it is shown that the introduced model is not reducible to a standard threshold model. The talk is based on work in progress, and further results are TBA.
15:10 – 15:55 Alexandru Baltag & Sonja Smets, Modal logics for social networks (abstract)
I introduce a number of modal formalisms capturing various dynamic-informational features of social networks, e.g: socially-induced adoption of new opinions or fashions leading to trends and cascades; the epistemic potential of an agent or group of agents within a given network; the social-epistemic power of an agent or group etc.
15:55 – 16:10 Coffee break
Afternoon Session 2, chair: Zoé Christoff
Modal logics of knowledge model uncertainty. Logics of awareness model incompleteness (as in vocabulary restriction) – a topic considered of great interest in economics. I have been working on these matters with Tim French (Perth), Fernando Velazquez (Sevilla), and Yi Wang (Bergen). We compare different epistemic notions in the presence of awareness of propositional variables: the logics of implicit knowledge (in which explicit knowledge is definable as implicit knowledge plus awareness), explicit knowledge, and speculative knowledge. Speculative knowledge goes back to the motivation in Levesque’s ‘A Logic of Implicit and Explicit Belief’: one can speculate over variables of which one is unaware, e.g. if you are unaware of p, then p v ~p is still speculatively known by you. A cornerstone of our framework is the notion of awareness bisimulation – this is the proper notion of structural similarity on the structures enriched with awareness of propositional variables proposed by Fagin and Halpern in ‘Belief, awareness, and limited reasoning’. A more ‘standard’ sort of bisimulation is also suitable for these logics. We provide correspondence between bisimulation and modal equivalence on image-finite models for these logics. The logic of speculative knowledge is equally expressive as the logic of explicit knowledge, and the logic of implicit knowledge is more expressive than both. The logics have complete axiomatizations. Dynamics can also be added: any conceivable change of knowledge or awareness can be modelled in this setting. The dynamic versions of all three logics are, surprising, equally expressive.
We introduce a new topological semantics for belief logics in which the belief modality is interpreted as the closure of the interior operator. We show that our semantics validates the axioms of Stalnaker’s combined system of knowledge and belief (presented in his paper `On Logics of Knowledge and Belief’), in fact, that it constitutes the most general extensional semantics validating these axioms. We further prove that in this semantics the logic KD45 is sound and complete with respect to the class of extremally disconnected spaces and compare our proposal to the topological interpretation of belief in terms of the derived set operator. We also explore topological analogues of static and dynamic belief change by providing topological semantics for conditional belief and update modalities.This is joint work with Alexandru Baltag, Nick Bezhanishvili and Sonja Smets.
Dynamic epistemic logic (DEL) provides a very expressive framework for multi-agent planning that can deal with nondeterminism, partial observability, sensing actions, and arbitrary nesting of beliefs about other agents’ beliefs. However, as I will show in my talk, this expressiveness comes at a price. The planning framework is undecidable, even if we allow only purely epistemic actions (actions that change only beliefs, not ontic facts). Undecidability holds already in the S5 setting with at least 2 agents, and even with 1 agent in S4. It shows that multi-agent planning is robustly undecidable if we assume that agents can reason with an arbitrary nesting of beliefs about beliefs. We also prove a corollary showing undecidability of the DEL model checking problem with the star operator on actions (iteration).This is joint work with Guillaume Aucher.
18:05 – 18:15 Coffee break
18:15 – 19:00 Jan van Eijck, Elements of Epistemic Crypto Logic (abstract)
The talk presents an extension of DEL (dynamic epistemic logic) intended for model checking of cryptographic protocols. Key elements are a feasible epistemic representation of knowledge of large integers, using register models, and exchange of such knowledge over a network. I will demonstrate how the approach can be used for model checking Diffie-Helman key exchange and similar protocols.
Tuesday, December 3rd
08:45 – 09:00 Coffee
Morning Session 1, chair: Jens U. Hansen
09:00 – 09:45 Rineke Verbrugge, Reasoning about other minds: From logic and computational models to the lab (abstract)
Nowadays, computer programs work together in multi-agent systems. In the future, people will cooperate with these programs, for example in healthcare, international negotiations, and rescue missions. Software agents, the artificial members of the team, often reason based on formal logics. Usually they are capable of an arbitrary amount of recursion: “I believe that Alice believes that I believes that she wrote a novel under pseudonym”… and so onwards, for every order of theory of mind. However, humans lose track of such reasoning after a few levels. If software agents work together with human teammates, it is very important that they take into account the limits of social cognition of their human counterparts. Otherwise an international negotiation, for example, fails, even when it has potential for a win-win solution. In a time-critical rescue mission, a software agent may depend on a human teammate’s action that never occurs.
In this talk, I discuss several strands of research related to recursive theory of mind: empirical research to understand children’s and adults’ limitations and strengths in higher-order social reasoning; and computational cognitive models to investigate whether smart birds need to reason about other birds’ knowledge at all in order to safeguard their food from theft, and to investigate under what evolutionary pressures higher-order theory of mind may have evolved.
In the talk I will ask the question about computational feasibility of the formalisms concerned with intelligent interactions. Classifying epistemic problems in the terms of their complexity is an important first step to map the feasibility border and identify parameters that play a central role for the complexity of human epistemic reasonings. I will argue that in order to make the connection with cognitive science real, we may need a perspective shift: from the complexity analysis focused on the modeler’s point of view to the study of complexity of epistemic tasks from the perspective of (bounded) agents involved.
10:30 – 10:40 Coffee break
Morning Session 2, chair: Rasmus K. Rendsvig
This is joint work with Adam Brandenburger.
Epistemic game theory is that part of game theory that explicitly takes into account the knowledge and beliefs of the players involved in a game. In formal epistemology literature there are at least two main multi-agent frameworks to model agents’ knowledge and beliefs in interactive situations. The first one, mainly used in logic and computer science, is built around the concept of Kripke model, a possible worlds model with one epistemic accessibility relation for each agent involved in the interaction; the other one, used in game theory and economics, is the type space, where each player has a set of types that specify her possible beliefs. The aim of the talk will be to compare these two different frameworks from a game theoretical point of view, i.e., when used to represent the epistemic situation of the players in a game.
11:50 – 13:15 Lunch break
Afternoon Session, chair: Thomas Bolander
In everyday life we typically do not reason about all events that have happened in the past, nor about all possible future events that could happen. Instead, we often reason only about some events in the recent past and near future to make our decisions. In this talk we take this viewpoint seriously, and try to incorporate this idea of local reasoning into the study of dynamic games. We assume that a player, whenever he is about to make a choice, only reasons about some past choices of his opponents, and about some choices his opponents could make in the future – not necessarily about all. We then develop a reasoning concept that is based on this idea of local reasoning. It turns out that forward induction reasoning and backward induction reasoning can be viewed as two extreme cases of this concept. More precisely, forward induction reasoning results if we assume that players always reason about all past and future choices of their opponents, whereas backward induction reasoning results if we assume that players only reason about future opponents’ choices – not about past choices. We also deliver an iterative procedure that can be used to compute those strategies that players can choose if they reason in accordance with the concept we propose.This is joint work with Elias Tsakas.
We discuss reasoning with strategies. We propose logics that analyze basic game-theoretic reasoning, and identify challenges for new research, some of them close to home.
19:30 Workshop dinner
Wednesday, December 4th
8:45 – 9:00 Coffee
Morning Session 1, chair: Jakub Szymanik
09:00 – 09:45 Jeremy Seligman, Social network dynamics (abstract)
Making friends and enemies involves a transformation of social networks, of a kind that can be and has been studied in a number of paradigms, within social psychology and economics. In this talk I will be sketching some ideas for a logic-based approach. The central idea is that, since a social network is a relational structure, we can immediately define a class of operators for reasoning about transformations of the network. These operators induce a dynamical system, whose behavior can also be analyzed logically. I will also reflect on ways of representing network games more generally.
In situations of social interaction the flow of information can be an extremely complex matter. Moreover, there are several perspectives on can take on the involved flow of information. For instance, one can take an “agent-local” perspective focusing on how the individual agents process information. On the other hand, one can also take a more “birds-eye” perspective and consider how information flows relative to the entire social network of agents.Both perspectives are valuable and can provide important insights about social-informational phenomena such as pluralistic ignorance, for instance. For this reason, we introduce a formal logical framework to talk about social networks and their dynamics that falls in-between the two perspectives. Even though our logic does not take into account the most complex models of belief revision of the individual agents, we claim that the logic provides a simple but extremely flexible framework to reason about social networks and their dynamics in a variety of interesting cases.
In this talk I will introduce our logical framework as well as provide a few examples of its usefulness to problems from the network science literature. This is joint work with Zoé Christoff, who will tell you much more about how to apply the framework to the phenomenon of pluralistic ignorance.
This is joint work with Jens Ulrik Hansen, who will have introduced, in the previous talk, our general framework for modeling properties repartition changes within social network structures.
In this talk, I will show how to model the social phenomenon of pluralistic ignorance in this framework and will discuss the fragility and the robustness of the phenomenon. Given a certain type of agents (that is, given a particular influence rule), I will show how the question of whether pluralistic ignorance dissolves into a state where all agents express their true private belief (i.e, are sincere) can be reduced to checking simple properties of the initial model.
10:55 – 11:10 Coffee break
Morning Session 2, chair: Rineke Verbrugge
11:10 – 11:55 Kevin Kelly, A computational learning semantics for common inductive knowledge (abstract)
Backwards induction in the muddy children problem requires common knowledge that the father can be trusted and backwards induction in the centipede game requires common knowledge of mutual rationality. Traditional epistemic logic explains neither what constitutes such knowledge nor how a computationally bounded agent could possibly acquire it. One idea is that such knowledge is based induction from past experience and reputation. I will present a new modal semantics of inductive knowledge in which agents are computable learners who alter their belief in sentences at successive moments in light of new inputs from the world, which may depend on the prior beliefs of other agents. Inductive knowledge is modeled as stable true belief from which error would have been eliminated eventually. Traditional theses of epistemic logic such as “if you know that p then you know that you know that p” are re-interpreted in terms of conditional feasibility: there exists a computable inferential strategy that turns an arbitrary learning strategy that knows that p into a learning strategy that also knows that p. Under that re-interpretation, S4 is valid, but no standard extension on the way to S5 is valid. In multi-agent systems, similar arguments yield that expert, rote instruction to a gullible audience suffices for the emergence of common inductive knowledge (as opposed to mere, common true belief) in the community. The expert instructor is not essential. Common inductive knowledge (e.g., of the father’s veridicality or of other players’ rationality) can emerge through mutual inductive inference based on the actions of the other agents.
Learning and learnability have been long standing topics of interests within the linguistic, computational, and epistemological accounts of inductive inference. In this talk I will overview the links between logics for social dynamics of information and (computational) learning theory. The aim is to shed light on some renewed research agendas in logic as the study of information processing in the context of learning. This proximity will be examined with respect to learning and belief revision, updating and efficiency, and with respect to how learnability fits together with the scheme of dynamic epistemic logic.
The results mentioned in this talk come from joint work with Sonja Smets and Alexandru Baltag, Dick de Jongh, and Cédric Dégremont, respectively.
In the talk I will explain how finite identifiability can be used to study the problem of conclusive knowledge update. I will introduce preset learners, learning functions that explicitly use conclusive symptoms, as well as the concept of fastest learner, who comes up with the right conjecture on any input string that objectively leaves only the right choice. We will see how minimal symptoms influence the speed of finite identification.
The results presented in this talk come from a joint work with Nina Gierasimczuk.
12:55 – 15:00 Lunch break
Afternoon Session 1, chair: Vincent F. Hendricks
In the present talk we outline several results obtained together with my co-authors that we consider relevant for detecting social dynamics of information change. First, the internet provides billions of documents and trying to establish semantic relations between the names of common objects is important. We survey results how to cluster the web-distance of names of common objects.Second, the internet may be thought of a vast graph, where social dynamics may be hidden in its subgraphs. There is some evidence that one can reflect about subgraphs by testing some of their properties. Several results towards a logical classification of the testable properties are presented.
Third, we shortly outline some very recent results concerning a new type of learning algorithms which is based on the concept of ultrametrics. This concept may lead to new family of indeterminate algorithms, but may have other applications as well.
This is joint work with Jan Poland, Charles Jordan and Rusins Freivalds, respectively.
Amongst the frameworks that deal with information change, we consider more specifically belief revision, answer-set programming and formal learning theory, and show how they can all be viewed as special cases of a generalized logical setting where ordinals are used to refine the model-theoretic and proof-theoretic notions of compactness and inference, respectively. Noting that all these frameworks revolve around the concept of “non-contradiction”, we examine the dual concept of “confirmation” in the context of the well-founded semantics and show how ordinals can be used again to index the modal operators in a generalization of modal logic where the interpretations are sets of rank kappa (kappa an ordinal) rather than sets of “urelements”. We draw relationships with the ordinal truth-values of Rondogiannis and Wadge and the presentation of the well-founded semantics as a game between two agents. Both uses of ordinals capture the notion of “degree of belief”; in the first case due to a lack of information, which decreases over time and brings ordinals down; in the second case due to a lack of “trust” in the information, which increases over time and brings ordinals up.
16:35 – 16:45 Coffee break
Afternoon Session 2, chair: Amanda Friedenberg
This talk is within the domain of computability-theoretic learning theory. It will feature two areas involving reactive learnees (not the more typically studied cases of passive learnees). Presented will be motivated theorems about each of: learning secrets interactively and learning to coordinate behavior. Shown will be theorems about cases where interacting learner and learnee can learn programs for each others elicited behavior and also one-sided cases where only one can learn the elicited behavior of the other. Shown too will be interpreted theorems about the algorithmic employment of a few random bits (fair coin tosses) to achieve coordination not achievable entirely deterministically algorithmically.
The talk also features learning winning strategies for reactive process-control games by watching the behavioral responses (not the algorithms) of experts/masters (importantly, possibly plural) of such games. This is interesting since, for example, human masters of complex motor tasks do not have verbalizable knowledge of their internal algorithms for these tasks, but usable, discretized data from their performances can be obtained (to help learn winning strategies). A trivial example of a reactive process control game is pole balancing: the balancer loses iff the pole falls over. Keeping a nuclear plant from blowing up would be a more practical example (albeit minimally involving complex motor skills). This part of the talk will feature build up to and presentation of relevant theorems each supplemented by brief comparisons with roughly correspondent, empirical, machine-learning studies involving the behavioral-cloning of human expert(s).
17:30 – 17:45 Closing Remarks: Sonja Smets