PaperlayerView exact revision on arXiv

Source-linked AI summary

Reasoning about Causality in Games

Lewis Hammond, James Fox, Tom Everitt, Ryan Carey, Alessandro Abate, Michael Wooldridge

arXiv:2301.02324v2cs.AIcs.GTcs.MA

TL;DR

The paper addresses the lack of a formal framework combining causal and game-theoretic reasoning. It introduces causal games and mechanised games, defines causal queries across predictions, interventions, and counterfactuals, and relates the framework to existing game-theoretic and causal models.

  • Problem

    Causal and game-theoretic reasoning are individually established, but their combination lacks a formal framework for analysing multi-agent systems with strategic behaviour.

  • Method

    The paper introduces structural causal games, extending causal models and multi-agent influence diagrams, plus mechanised games for encoding dependencies between decision rules and game distributions.

  • Results

    Causal games provide a unifying formalism supporting predictions, interventions, and counterfactuals while enabling comparisons with existing formalisms and applications such as incentives, fairness, blame, and intention.

  • Takeaways & Limitations

    The framework supports formal causal analysis of systems containing multiple self-interested agents and can express causal effects that generally cannot be computed without a formal causal model.

  • Takeaways & Limitations

    Counterfactual computation requires resolving how stochastic decision rules are represented and how beliefs about counterfactual policy profiles are updated from actual-world evidence.

Abstract

from arXiv · show

Causal reasoning and game-theoretic reasoning are fundamental topics in artificial intelligence, among many other disciplines: this paper is concerned with their intersection. Despite their importance, a formal framework that supports both these forms of reasoning has, until now, been lacking. We offer a solution in the form of (structural) causal games, which can be seen as extending Pearl's causal hierarchy to the game-theoretic domain, or as extending Koller and Milch's multi-agent influence diagrams to the causal domain. We then consider three key questions: i) How can the (causal) dependencies in games - either between variables, or between strategies - be modelled in a uniform, principled manner? ii) How may causal queries be computed in causal games, and what assumptions does this require? iii) How do causal games compare to existing formalisms? To address question i), we introduce mechanised games, which encode dependencies between agents' decision rules and the distributions governing the game. In response to question ii), we present definitions of predictions, interventions, and counterfactuals, and discuss the assumptions required for each. Regarding question iii), we describe correspondences between causal games and other formalisms, and explain how causal games can be used to answer queries that other causal or game-theoretic models do not support. Finally, we highlight possible applications of causal games, aided by an extensive open-source Python library.

Notation

The notation defines the paper’s graph, variable, probability, policy, intervention, and rationality symbols. It also distinguishes decision-rule variables, mechanism variables, and rationality relations.

  • The notation uses V and v for random variables and their instantiations, with bold symbols denoting sets and their joint instantiations.
  • Graph notation includes Pa_V, Ch_V, Anc_V, Desc_V, and Fa_V for parents, children, ancestors, descendants, and family.
  • Policy notation distinguishes behavioural policies π_i, pure policies ˙π_i, mixed policies μ_i, and behavioural strategy profiles π and σ.
  • Mechanism notation includes Π_D for decision-rule variables, Θ_V for parameter variables, and M_V for mechanism variables.
  • Rationality notation includes R, r_D, rRG, and R(mM) for rationality relations, decision-specific relations, relevance graphs, and rational outcomes.

1 Introduction

The paper addresses the missing formal integration of causal and strategic reasoning by introducing causal games as a unified framework. Its contributions cover mechanised dependencies, causal queries, equilibrium refinements, comparisons with existing models, and applications.

  • 1 Introduction: Causal games address incentives, fairness, blame, and intention, while related graphical game models generally lack rigorous causal reasoning.
  • 1 Introduction: Causal games unify causal and game-theoretic reasoning by extending Pearl’s causal hierarchy to strategic interactions and MAIDs to causal models.
  • 1.1 Contributions: Mechanised MAIDs represent dependencies among decision rules and game parameters, while R-relevance generalises strategic relevance across decision-making principles.
  • 1.1 Contributions: The paper derives sound and complete graphical criteria for identifying variables relevant when agents best respond to one another.
  • 1.1 Contributions: Causal games support conditional, interventional, and counterfactual queries that quantify over equilibria and allow rational agents to adapt strategies to environmental changes.
  • 1.1 Contributions: The paper introduces subgames and subgame-perfectness and trembling-hand-perfectness refinements for MAIDs, finding more subgames than corresponding EFGs and thereby ruling out more non-credible threats.

2 Background

The background develops Pearl’s causal hierarchy, Bayesian and causal Bayesian networks, structural causal models, interventions, counterfactuals, and game-theoretic representations through EFGs and MAIDs. It also introduces strategic relevance and equilibrium existence results used later.

  • Causal Models: Pearl’s hierarchy progresses from associational prediction to interventional reasoning and counterfactual reasoning, with stricter assumptions at each level.
  • Association: Bayesian networks factorise joint distributions according to DAG structure, while d-separation identifies conditional independencies implied by that structure.
  • Intervention: Associational models generally cannot answer intervention questions; causal Bayesian networks interpret directed edges causally and modify distributions under interventions.
  • Intervention: Hard interventions sever incoming edges and set variables to fixed values, whereas soft interventions replace conditional distributions with new intervention-specific distributions.
  • Counterfactuals: Counterfactual queries combine evidence about the actual world with a hypothetical modified world and generally require structural causal models.
  • Structural Causal Models: Markovian SCMs assume one exogenous parent per variable and mutually independent exogenous variables, with deterministic conditional distributions for endogenous variables.
  • Multi-Agent Influence Diagrams: Strategic relevance and s-reachability identify decision-rule dependencies under a rationality assumption, while the relevance graph records these dependencies across decisions.
  • Multi-Agent Influence Diagrams: MAIDs encode agents’ information and decisions graphically; sufficient recall guarantees at least one Nash equilibrium in behavioural policies.

3 Mechanised MAIDs and Relevance

Mechanised MAIDs make implicit dependencies between agents’ decision rules, game parameters, and outcome distributions explicit, enabling principled relevance analysis for causal reasoning in games.

  • 3 Mechanised MAIDs and Relevance: Mechanised MAIDs extend MAIDs with representations of decision rules and parameters plus dependencies describing how these mechanism variables depend on one another.They are introduced as a foundation for causal reasoning in games and for subgames in MAIDs.
  • 3 Mechanised MAIDs and Relevance: Each decision variable receives a decision-rule parent and each non-decision variable receives a parameter parent, collectively representing the mechanisms that set game variables.Additional edges can encode decision rules selected as functions of game parameterisation and other agents’ decision rules.
  • 3 Mechanised MAIDs and Relevance: Given parameters and a policy profile, the mechanised MAID induces the same distribution over object-level variables as the original MAID.The mechanism-variable values determine either CPDs for non-decision variables or decision rules for decision variables.
  • 3 Mechanised MAIDs and Relevance: R-rational outcomes define a set of induced distributions, providing a principled and general representation of non-deterministic decision-making as a set of Bayesian networks.Rationality relations characterize how decision rules are generated and can support deductions from graphical structure.
  • Rational Outcomes: The framework accommodates boundedly rational agents through approximate equilibrium conditions, such as policies whose deviations improve expected utility by at most ϵ > 0.The choice of rationality relation determines the degree of rationality represented.
  • Relevance: R-relevance identifies mechanism variables whose values can affect rational responses, allowing irrelevant edges to be removed and yielding an R-minimal mechanised graph and R-relevance graph.For natural rationality relations, graphical criteria can identify relevance soundly and completely; R-reachability provides the corresponding pruning procedure.

4 Causality in Games

Causal games extend game-theoretic models across associational, interventional, and counterfactual reasoning, while mechanised games represent dependencies between agents’ decision rules and game distributions. The framework distinguishes pre-policy from post-policy queries and supports predictions, interventions, and counterfactuals under different assumptions.

  • Causal hierarchy: Causal games (CGs) and structural causal games (SCGs) extend MAIDs to interventions and counterfactuals, respectively, generalising causal models to strategic multi-agent settings.Predictions remain at the associational level, whereas interventions and counterfactuals require the higher causal levels.
  • Causal hierarchy: Predictions, interventions, and counterfactuals occupy different levels of the causal hierarchy and therefore require different game models.Predictions can use mechanised MAIDs; interventions require CGs, and counterfactuals require SCGs.
  • Mechanised games: Mechanised games support both post-policy queries over object-level variables and pre-policy queries over mechanism variables before policies are fixed.This distinction is central for representing whether agents can adjust their decision rules in response to changes.
  • Interventions: Interventions are unified by severing incoming edges to the intervened variable, while pre-policy interventions on decision rules replace the corresponding rationality relation.The framework propagates pre-policy effects through the mechanisms by which agents select decision rules.
  • Counterfactuals: Counterfactual computation in SCGs requires resolving how stochastic decision rules map to structural functions and how policy beliefs update between actual and counterfactual worlds.A one-to-one correspondence between stochastic and deterministic decision rules supports extending SCM counterfactuals to games.

5 Solution Concepts and Subgames

This section develops Nash-equilibrium and subgame concepts for MAIDs, showing when behavioural equilibria exist and how MAID structure supports richer subgame analysis than EFGs. It also extends MAIDs with subgame-perfect and trembling-hand-perfect equilibrium refinements.

  • 5.1 Nash Equilibria: The warehouse-robot example computes expected payoffs over four action combinations in a reduced EFG obtained by marginalising the chance variable for breakages.The example’s Nash equilibrium has robot one move quickly and robot two patrol regardless of robot one’s action.
  • 5.1 Nash Equilibria: With perfect recall, every MAID has a behavioural-policy Nash equilibrium, and sufficient recall is enough to guarantee at least one subgame-perfect equilibrium.The paper further characterises subgame-perfect equilibria as the rational outcomes induced by the corresponding mechanised model.
  • 5.1 Nash Equilibria: Behavioural-policy Nash equilibria are not guaranteed in MAIDs, but sufficient recall guarantees their existence, even though sufficient recall is weaker than perfect recall.Perfect recall implies sufficient recall, whereas the converse need not hold.
  • 5.2 Subgames: MAID subgames generalise EFG subgames: their structure depends on the rationality relation, and conditional independencies can expose more independently solvable subgames.R-subgames can support equilibrium refinement, reduce equilibrium-computation costs, and isolate agents’ decision-making.
  • Identifying More Subgames in MAIDs: MAIDs can identify proper subgames that equivalent EFGs cannot, because conditional dependencies may make variables irrelevant to later decisions while preserving the game’s payoff structure.In the modified hiring example, the EFG has no proper subgames, whereas the equivalent MAID has three proper s-subdiagrams, each yielding two s-subgames.
  • 5.3 Equilibrium Refinements: The section introduces subgame-perfectness and trembling-hand perfectness for MAIDs, and shows that a subgame-perfect profile need not be trembling-hand perfect.In the warehouse example, trembles select a trembling-hand-perfect profile in which robot one chooses the quick action.

6 Connections to EFGs

The paper connects MAIDs and EFGs through conversion procedures and shows that key game-theoretic concepts are preserved, while MAIDs can provide computational and structural advantages. Causal interpretations of EFGs remain limited for interventions and counterfactuals.

  • MAID to EFG: The maid2efg procedure constructs game trees by splitting variables in topological order, labeling chance branches from CPDs and decision nodes with available actions.Nodes for the same decision variable share an information set when their ancestor values agree on the variable’s parents; different topological orders can yield different EFGs.
  • Representation and efficiency: MAIDs can represent games using at most the space of EFGs and often exponentially less, while reduced EFGs can marginalize irrelevant variables without changing equilibrium computation.The reduced representation for one example has 22 rather than 23 leaves, and its information remains sufficient for computing equilibria.
  • EFG to MAID: The efg2maid procedure uses intervention sets to recover a unique canonical MAID from an EFG, restoring variable identity that tree representations can obscure.In an EFG, whether nodes represent the same variable may depend on external domain knowledge; intervention sets formalize this correspondence.
  • Equivalence results: MAID–EFG conversions preserve equivalence and transfer Nash equilibrium, subgame-perfect, and trembling-hand-perfect concepts under natural mappings.The correspondence is formalized through equivalence results, including bidirectional preservation for Nash and trembling-hand-perfect equilibria and transfer of subgame-perfect equilibria from MAIDs to EFGs.
  • Equivalence results: MAIDs may expose more subgames than corresponding EFGs, making subgame-perfectness stricter and potentially ruling out additional non-credible threats.This stronger criterion can exclude threats that do not belong to a particular EFG subgame, and the paper links the additional subgames to more efficient equilibrium computation.
  • Causal reasoning in EFGs: EFGs admit a causal interpretation for some interventions, but their total ordering restricts available interventions and leaves some probabilistic or causal queries undefined.Counterfactual queries are not invariant to tree representation; placing exogenous stochasticity at the top and using deterministic endogenous strategies can address this difficulty.

7 Applications

The paper applies causal games to a UK home-insurance case study, using market data to model firms and customers and quantify a proposed intervention. The analysis confirms some FCA hypotheses, rejects others under the model, and shows how alternative interventions and richer multi-agent concepts can be represented.

  • UK Home Insurance Case Study: The case study models a duopolistic insurance market with two pricing firms and customers who differ in switching costs, parameterised using UK market data.Firms choose premiums based on the customer’s current provider, while customers choose whether to renew or switch according to type and costs.
  • The Proposed Intervention: Representing the FCA intervention in a causal game makes its qualitative hypotheses formally testable under a pure THPE assumption with p = 0.6.The model quantifies causal effects that generally cannot be evaluated without a formal causal model.
  • Results: Firms charge marginal-cost prices to new customers and higher renewal prices, while the intervention changes pricing to £288 for firm one and £250 for firm two.These equilibria hold for every rational outcome considered after intervention.
  • Results: 0%, 43.2%, 28.8%, or 72% of savvy customers switch before intervention, whereas after intervention switching is restricted to 0% or 43.2%.The intervention removes incentives for customers already with the second firm to switch; the switching measure is defined by Prπ(D3 = i | C = 3 −i).
  • Results: The intervention confirms the first pricing hypothesis but contradicts its claim that renewing customers pay less: renewal prices rise from £244 to £250 or £288.High switching costs of £38 and 28% inert customers make exploiting customers who do not switch more profitable than lowering prices to attract rivals’ customers.
  • Further Applications: Causal games can extend multi-agent incentive, fairness, blame, and intent analyses beyond existing single-agent or single-decision settings.The framework supports strategy-level and pre-policy interventions and can represent richer blame and intent concepts involving multiple agents.

8 Discussion

The discussion argues that causal games provide a general framework combining strategic interaction with causal analysis, while clarifying trade-offs against causal models, settable systems, and extensive-form games. Their benefits include equilibrium-aware causal queries, explicit dependency structure, and compact representations, but some specialized refinements remain better supported by EFGs.

  • Overall Comparison: Causal games address a gap left by prior frameworks that did not capture game-theoretic and causal features together in a general, principled way.They are presented as a unifying formalism for reasoning about causality in games.
  • Causal Models: Unlike standard causal models, causal games represent rational self-interested agents whose decision mechanisms can violate independent causal mechanisms.Mechanised games explicitly encode dependencies between mechanism variables associated with agents’ decision rules.
  • Settable Systems: Compared with settable systems, causal games naturally support equilibrium multiplicity and strategic analysis, whereas settable systems focus on lower-level algorithmic details.Settable systems duplicate intervenable variables to handle cycles but do not capture the multiplicity of equilibria emphasized here.
  • Cyclic and Relational Models: Causal games retain multiple equilibria through non-deterministic mechanisms, extending cyclic causal models to a relational setting while targeting game-theoretic equilibrium dependencies.The paper cautions that these specific cyclic dependencies are not intended to model arbitrary dynamical systems.
  • MAIDs and Equilibrium Concepts: Building on MAIDs gives causal games Nash equilibria, subgames, and equilibrium refinements while remaining compatible with probabilistic graphical models.These game-theoretic concepts are not supported by other causal models in the same way.
  • Comparison with EFGs: DAG-based causal games support causal queries, explicit dependencies between decision rules, and representations that can be exponentially smaller than equivalent extensive-form games.R-relevance graphs and d-separation can expose more subgames and significantly reduce solution complexity.
  • Limitations: Extensive-form games remain preferable for exotic equilibrium refinements, while causal games are not necessarily appropriate for arbitrary dynamical systems.The paper also notes that some dependency structures may limit efficiency for pre-strategy queries.
  • Future Directions: Future work targets multi-agent incentives, mechanism interventions, multi-agent counterfactual fairness, and explanations involving blame and intent.The paper presents causal games and its codebase as a foundation for further research, emphasizing generality, explainability, and succinctness.

A Proofs

The paper gives constructive encodings between MAIDs and extensive-form games, preserving agents, variable structure, probabilities, information, and utilities. The constructions also establish partial-distribution behavior for non-decision variables.

  • MAID to EFG: A MAID-to-EFG encoding creates a symmetric tree whose paths split on selected chance and decision variables in topological order.Chance variables become chance nodes, decision variables become the corresponding agents’ nodes, and path labels record variable instantiations.
  • MAID to EFG: Chance-node probabilities are obtained by querying the corresponding MAID CPDs using each node’s instantiation label, which reduces to parent values in a Bayesian network.Decision actions use the corresponding decision-variable domains, while information sets group nodes with matching decision variables and parent instantiations.
  • EFG to MAID: The reverse EFG-to-MAID construction initializes the graph from the tree, merges variables according to intervention sets, and defines CPDs from edge-label probabilities.Utility variables are constructed from leaf payoffs, and undefined non-decision contexts receive null or zero values as appropriate.
  • EFG to MAID: The resulting CPDs form a partial distribution over the MAID’s non-decision variables.Decision-rule parameterizations can affect other variables only in decision contexts associated with positive-probability paths under some strategy.

Section 3

Section 3 characterizes how mechanism variables can be relevant to decision rules and establishes a graphical criterion for that relevance. It also relates stochastic decision rules to deterministic rules through an auxiliary random field.

  • Relevance: A mechanism variable MV is RBR-relevant to decision rule ΠD exactly when it is m-separated from neither descendant utilities conditional on D and PaD nor PaD itself.This criterion is called RBR-reachability and is stated as the disjunction of the two corresponding graphical dependencies.
  • Soundness: The soundness argument shows that if MV is not RBR-reachable from ΠD, changing MV cannot change the relevant distributions used to evaluate ΠD.The relevant distributions are Prπ(u | d, paD; θ) and Prπ(paD; θ), so the decision-rule evaluation is independent of MV.
  • Completeness: The completeness argument constructs parameterizations where a reachable mechanism variable changes a decision context or descendant utility, making it relevant to the decision rule.The construction first uses binary variables and then extends to arbitrary domains by labeling two values as 0 and 1.
  • Decision-rule representation: There is a one-to-one correspondence between stochastic decision rules and deterministic rules augmented with an independent random field.The mapping uses the random field to sample actions according to the stochastic rule while preserving the associated decision behavior.

Section 5

Section 5 studies equilibrium existence and refinements in MAIDs under recall assumptions. Behavioral-policy Nash equilibrium may fail without additional structure, but perfect or sufficient recall restores existence and supports subgame-perfect reasoning.

  • Nash equilibrium: A behavioral-policy Nash equilibrium is not guaranteed to exist in a MAID.The paper contrasts this with the existence result obtained under perfect recall.
  • Nash equilibrium: With perfect recall, every mixed policy for an agent has an outcome-equivalent behavioral policy, yielding a behavioral-policy Nash equilibrium in any MAID.The equivalence preserves the joint distribution over variables and therefore expected utilities; Nash’s theorem supplies the mixed-policy equilibrium.
  • Recall conditions: Perfect recall implies sufficient recall, but sufficient recall does not imply perfect recall.The distinction is established through the structure of decision-rule dependencies and an example with sufficient but imperfect recall.
  • Subgame perfection: Any MAID with sufficient recall has at least one subgame-perfect equilibrium in behavioral policies, and its SPEs coincide with the rational outcomes RSP(mM).The proof proceeds through an ordering of s-subdiagrams and backward induction over the induced subgames.

Section 6

Section 6 proves that the MAID and extensive-form-game constructions preserve strategic structure and equilibrium behavior. The correspondence extends from Nash equilibrium to subgame-perfect and trembling-hand-perfect equilibrium, with subgames mapped to s-subgames.

  • Equivalence: The MAID-to-EFG and EFG-to-MAID constructions produce equivalent models under a natural mapping between strategies and policies.The reverse construction is deterministic, yielding a unique canonical MAID from an EFG.
  • Nash equilibrium: A strategy profile is an NE in the EFG exactly when every corresponding policy profile is an NE in the MAID.The correspondence preserves expected utilities, while differences on infeasible decision contexts have no effect.
  • Subgames: Every EFG subgame corresponds to an equivalent MAID s-subgame under the natural mapping, up to constant utility differences.The associated variable set is closed under the dependencies required for an s-subdiagram, and a consistent setting of variables outside it selects the subgame.
  • Equilibrium refinements: The equilibrium correspondence extends to subgame-perfect and trembling-hand-perfect equilibrium.SPE correspondence is stated in one direction for the mapped models, whereas THPE correspondence is stated in both directions.

No Nash Equilibrium in Behavioural Policies

The example shows that insufficient recall can eliminate Nash equilibria in behavioural policies, even though mixed-policy equilibria still exist. The construction is represented equivalently as a MAID and an EFG.

  • No Nash Equilibrium in Behavioural Policies: Insufficient recall prevents behavioural-policy Nash equilibrium in this MAID, although Nash’s theorem guarantees an equilibrium in mixed policies.Agent 1’s s-relevance graph is cyclic, violating sufficient recall; the example therefore separates mixed-policy existence from behavioural-policy existence.
  • No Nash Equilibrium in Behavioural Policies: No pure-policy equilibrium exists because each candidate pure policy induces a best response that makes the other agent want to deviate.Agent 1 cannot use the two off-diagonal policies, while the remaining policies induce opposing best responses between the agents.
  • No Nash Equilibrium in Behavioural Policies: The behavioural-policy proof parameterizes agent 1’s decision rules by p and q, then derives incompatible constraints on those probabilities.The constraints imply (2p − 1)^2 < 0, a contradiction, so no behavioural-policy NE exists.
  • No Nash Equilibrium in Behavioural Policies: A mixed-policy Nash equilibrium nevertheless exists at µ = (µ1_1/2, µ2_1/2), with both agents randomizing over their supported pure policies.Indifference conditions yield probability 1/2 for the relevant policies, while the other pure policies receive no positive probability.

C.1 Creating MAIDs

The PyCID workflow constructs MAIDs by specifying graph edges, agent decision and utility variables, domains, and conditional-probability or utility functions. Its examples show how these elements are encoded programmatically and visualized.

  • C.1 Creating MAIDs: A MAID is initialized with graph edges, dictionaries identifying agents’ decision and utility variables, and a drawing method for visualizing the model.PyCID’s MAID class inherits from pgmpy’s BayesianModel class and distinguishes chance, decision, and utility variables graphically.
  • C.1 Creating MAIDs: MAID parameterization assigns domains to decision variables and CPDs to chance and utility variables.The examples use binary decision variables, a Bernoulli chance variable, and Python functions for utility and conditional-probability specifications.
  • C.1 Creating MAIDs: The supplied examples encode game-specific mechanisms directly as functions, including chance behavior conditioned on decisions and utilities computed from decisions and outcomes.Example 2 defines B from D1, while U1 and U2 are specified as functions of the agents’ decisions and relevant variables.

C.2 Computing Equilibria

PyCID computes equilibria directly for several MAID representations and exploits proper s-subgames to reduce equilibrium-search complexity. In a matching-pennies-like family, this yields a large runtime advantage over equivalent EFG representations.

  • C.2 Computing Equilibria: PyCID finds pure NEs and SPEs natively, and computes two-agent behavioural NEs and SPEs by converting MAIDs to normal-form games and using Nashpy.SPE search proceeds backward through a topological ordering of the MAID’s s-subdiagrams, solving each s-subgame in turn.
  • C.2 Computing Equilibria: MAIDs expose each matching-pennies pair as a proper s-subgame, enabling the unique behavioural SPE to be solved locally before solving the full game.The subgames yield agents randomizing equally between heads and tails; the first agent then optimally chooses heads in the full game.
  • C.2 Computing Equilibria: For the nine-agent matching-pennies-like game, MAID equilibrium computation is three orders of magnitude faster than EFG computation.The comparison uses PyCID and Gambit, with mean runtimes over seven runs.
  • C.2 Computing Equilibria: MAIDs can contain more subgames than corresponding EFGs, while every EFG subgame is guaranteed to remain a subgame in its corresponding MAID.When neither representation has proper subgames, their equilibrium-computation times are comparable.
Loading 2301.02324v2…