Search for: All records

We show that it is possible to understand and identify a decision maker’s subjective causal judgements by observing her preferences over interventions. Following Pearl [2000, DOI: doi.org/10.1017/S0266466603004109 ], we represent causality using causal models (also called structural equations models), where the world is described by a collection of variables, related by equations. We show that if a preference relation over interventions satisfies certain axioms (related to standard axioms regarding counterfactuals), then we can define (i) a causal model, (ii) a probability capturing the decision-maker’s uncertainty regarding the external factors in the world and (iii) a utility on outcomes such that each intervention is associated with an expected utility and such that intervention A is preferred to B iff the expected utility of A is greater than that of B. In addition, we characterize when the causal model is unique. Thus, our results allow a modeler to test the hypothesis that a decision maker’s preferences are consistent with some causal model and to identify causal judgements from observed behavior. 

We focus on explaining image classifiers, taking the work ofMothilal et al. 2021 (MMTS) as our point of departure. We observe that, although MMTS claim to be using the definition of explanation proposed by Halpern 2016, they do not quite do so. Roughly speaking, Halpern’s definition has a necessity clause and a sufficiency clause. MMTS replace the necessity clause by a requirement that, as we show, implies it. Halpern’s definition also allows agents to restrict the set of options considered.While these difference may seem minor, as we show, they can have a nontrivial impact on explanations.We also show that, essentially without change, Halpern’s definition can handle two issues that have proved difficultfor other approaches: explanations of absence (when, for example, an image classifier for tumors outputs “no tumor”) and explanations of rare events (such as tumors). 

Abraham, Dolev, Geffner, and Halpern [ 1 ] proved that, in asynchronous systems, a (k, t)-robust equilibrium for n players and a trusted mediator can be implemented without the mediator as long as n > 4( k+t ), where an equilibrium is ( k, t )-robust if, roughly speaking, no coalition of t players can decrease the payoff of any of the other players, and no coalition of k players can increase their payoff by deviating. We prove that this bound is tight, in the sense that if n ≤ 4( k+t ) there exist ( k, t )-robust equilibria with a mediator that cannot be implemented by the players alone. Even though implementing ( k, t )-robust mediators seems closely related to implementing asynchronous multiparty ( k+t )-secure computation [ 6 ], to the best of our knowledge there is no known straightforward reduction from one problem to another. Nevertheless, we show that there is a non-trivial reduction from a slightly weaker notion of ( k+t )-secure computation, which we call ( k+t )-strict secure computation , to implementing ( k, t )-robust mediators. We prove the desired lower bound by showing that there are functions on n variables that cannot be ( k+t )-strictly securely computed if n ≤ 4( k+t ). This also provides a simple alternative proof for the well-known lower bound of 4 t +1 on asynchronous secure computation in the presence of up to t malicious agents [ 4 , 8 , 10 ]. 

We introduce a theoretical model of information acquisition under resource limitations in a noisy environment. An agent must guess the truth value of a given Boolean formula \( \varphi \) after performing a bounded number of noisy tests of the truth values of variables in the formula. We observe that, in general, the problem of finding an optimal testing strategy for \( \varphi \) is hard, but we suggest a useful heuristic. The techniques we use also give insight into two apparently unrelated but well-studied problems: (1) rational inattention , that is, when it is rational to ignore pertinent information (the optimal strategy may involve hardly ever testing variables that are clearly relevant to \( \varphi \) ), and (2) what makes a formula hard to learn/remember. 

Generalized structural equations models (GSEMs) 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 for SEMs. Considering GSEMs helps clarify what properties Halpern's axioms capture. 

Consider a bank that uses an AI system to decide which loan applications to approve. We want to ensure that the system is fair, that is, it does not discriminate against applicants based on a predefined list of sensitive attributes, such as gender and ethnicity. We expect there to be a regulator whose job it is to certify the bank's system as fair or unfair. We consider issues that the regulator will have to confront when making such a decision, including the precise definition of fairness, dealing with proxy variables, and dealing with what we call allowed variables, that is, variables such as salary on which the decision is allowed to depend, despite being correlated with sensitive variables. We show (among other things) that the problem of deciding fairness as we have defined it is co-NP-complete, but then argue that, despite that, in practice the problem should be manageable. 

Although the definition of sequential equilibrium can be applied without change to games of imperfect recall, doing so leads to arguably inappropriate results. We redefine sequential equilibrium so that the definition agrees with the standard definition in games of perfect recall while still giving reasonable results in games of imperfect recall. The definition can be viewed as trying to capture a notion of ex ante sequential equilibrium. The picture here is that players choose their strategies before the game starts and are committed to it, but they choose it in such a way that it remains optimal even off the equilibrium path. A notion of interim sequential equilibrium is also considered.