777 research outputs found
Actual Causation and the Art of Modeling
No full text[Introduction] In The Graduate, Benjamin Braddock (Dustin Hoffman) is told that the future can
be summed up in one word: “Plastics”. One of us (Halpern) recalls that in roughly
1990, Judea Pearl told him that the future was in causality. Pearl’s own research
was largely focused on causality in the years after that; his seminal contributions
are widely known. We were among the many influenced by his work. We discuss one
aspect of it, actual causation, in this article, although a number of our comments
apply to causal modeling more generally
Distributed Computing Meets Game Theory: Fault Tolerance and Implementation with Cheap Talk (Invited Talk)
No full textTraditionally, work in distributed computing has divided the agents into "good guys" and "bad guys". The good guys follow the protocol; the bad guys do everything in their power to make sure it does not work. By way of contrast, game theory has focused on "rational" agents, who try to maximize their utilities. Here I try to combine these viewpoints. Specifically, following the work of Abraham et al. [I. Abraham et al., 2006], I consider (k,t)-robust protocols/strategies, which tolerate coalitions of rational players of size up to k and up to t malicious players. I focus in particular on the problem that economists have called implementing a mediator. That is, can the players in the system, just talking among themselves (using what economists call "cheap talk") simulate the effects of the mediator (see, e.g., [I. Barany, 1992; E. Ben-Porath, 2003; Forges, 1990; D. Gerardi, 2004; Y. Heller, 2005; A. Urbano and J. E. Vila, 2002; A. Urbano and J. E. Vila, 2004]). In computer science, this essentially amounts to multiparty computation [O. Goldreich et al., 1987; A. Shamir et al., 1981; A. Yao, 1982]. Ideas from cryptography and distributed computing allow us to prove results on how many agents are required to implement a (k,t)-robust mediator just using cheap talk. These results subsume (and, in some cases, correct) results from the game theory literature.
The results of Abraham et al. [I. Abraham et al., 2006] were proved for what are called synchronous systems in the distributed computing community; this is also the case for all the results in the economics literature cited above. In synchronous systems, communication proceeds in atomic rounds, and all messages sent during round r are received by round r + 1. But many systems in the real world are asynchronous. In an asynchronous setting, there are no rounds; messages sent by the players may take arbitrarily long to get to their recipients. Markets and the internet are best viewed as asynchronous. Blockchain implementations assume partial synchrony, where there is an upper bound on how long messages take to arrive. The partial synchronous setting already shows some of the difficulty of moving away from synchrony: An agent i can wait to take its action until it receives a message from j (on which its action can depend). This cannot happen in a synchronous setting. Abraham, Dolev, Geffner, abnd Halpern [I. Abraham et al., 2019] extend the results on implementing mediators to the asynchronous setting
Using Counterfactuals in Knowledge-Based Programming
No full text: We show how counterfactuals can be added to the framework of knowledgebased programs of Fagin, Halpern, Moses, and Vardi [1995, 1997]. We show that counterfactuals allow us to capture in a natural way notions like minimizing the number of messages that are sent, whereas attempts to formalize these notions without counterfactuals lead to some rather counterintuitive behavior. We also show how knowledge-based programs with counterfactuals can capture subgame-perfect equilibria in games of perfect information. 1 Introduction Knowledge-based programs, first introduced in [Halpern and Fagin 1989] and further developed by Fagin, Halpern, Moses, and Vardi [1995, 1997], are intended to provide a high-level framework for the design and specification of protocols. Their key feature is that of allowing explicit tests for knowledge. Thus, a knowledge-based program might have the form if K(x = 0) then y := y + 1 else skip; where K(x = 0) should be read as "you know x = 0" and skip is the actio..
Actual Causality
No full textCausality plays a central role in the way people structure the world; we constantly seek causal explanations for our observations. But what does it even mean that an event C “actually caused” event E? The problem of defining actual causation goes beyond mere philosophical speculation. For example, in many legal arguments, it is precisely what needs to be established in order to determine responsibility. The philosophy literature has been struggling with the problem of defining causality since Hume. In this book, Joseph Halpern explores actual causality, and such related notions as degree of responsibility, degree of blame, and causal explanation. The goal is to arrive at a definition of causality that matches our natural language usage and is helpful, for example, to a jury deciding a legal case, a programmer looking for the line of code that cause some software to fail, or an economist trying to determine whether austerity caused a subsequent depression. Halpern applies and expands an approach to causality that he and Judea Pearl developed, based on structural equations. He carefully formulates a definition of causality, and building on this, defines degree of responsibility, degree of blame, and causal explanation. He concludes by discussing how these ideas can be applied to such practical problems as accountability and program verification.</p
On the Relationship between Strand Spaces and
No full textthis paper appears in the Proceedings of the 8th ACM Conference on Computer and Communications Security, 2001. Supported in part by NSF under grant IRI96 -25901 and IIS-0090145 and by ONR under grants N00014-00-1-03-41 and N00014-01-10-511, and by the DoD Multidisciplinary University Research Initiative (MURI) program administered by the ONR under grant N00014-01-1-0795. Authors' address: J. Y. Halpern, Department of Computer Science, Cornell University, Ithaca, NY 14853, email: [email protected], home page: http://www.cs.cornell.edu/home/halpern, R. Pucella, Department of Computer Science, Cornell University, Ithaca, NY 14853, email: [email protected]
Reasoning about Causal Models with Infinitely Many Variables
No full textGeneralized structural equations models (GSEMs) (Peters and Halpern 2021), are, as the name suggests, a generalization of structural equations models (SEMs). They can deal with (among other things) infinitely many variables with infinite ranges, which is critical for capturing dynamical systems. We provide a sound and complete axiomatization of causal reasoning in GSEMs that is an extension of the sound and complete axiomatization provided by Halpern (2000) for SEMs. Considering GSEMs helps clarify what properties Halpern's axioms capture
A Note on Unawareness
No full textModica and Rustichini [1994] provided a logic for reasoning about knowledge where agents may be unaware of certain propositions. However, their original approach had the unpleasant property that nontrivial unawareness was incompatible with partitional information structures. More recently, Modica and Rustichini [1999] have provided an approach that allows for nontrivial unawareness in partitional information structures. Here it is shown that their approach can be viewed as a special case of a general approach to unawareness considered by Fagin and Halpern [1988]. 1 Introduction The standard approach to reasoning about knowledge [Fagin, Halpern, Moses, and Vardi 1995] implicitly assumes that agents are (commonly known to be) aware of all the relevant propositions. However, in decision theory under uncertainty, we must often deal with unforeseen contingencies. (See [Dekel, Lipman, and Rusticchini 1997] for a discussion of issues related to unforeseen contingencies and further references..
- …
