Exploring Complex Systems Modeling with MAIDs, GDS & cadCAD

Multi-Agent Influence Diagram (MAID), Generalized Dynamical Systems (GDS), & Complex Adaptive Dynamics Computer-Aided Design (cadCAD)

This series of four interactive workshops explores the compatibility and synergies of three interconnected modeling frameworks. It develops a conversational framework to explore and consider theoretical and practical applications for model and tool selection and their use together for rigorous, coherent, and efficient modeling of complex systems.

Led by Octopus, a Blockscience Research Engineer, this workshop series is designed to be broadly accessible to researchers, engineers, and teams comfortable with scientific computing in Python and familiar with or interested in modeling dynamic games. Required mathematical literacy includes linear algebra, dynamical systems, and event-driven systems. Knowledge of real analysis, optimization, the existence and uniqueness of equilibria, multi-agent systems, and potential games will aid your understanding.

In this post, we first provide a brief introduction to each of the three modeling tools: Multi-Agent Influence Diagrams (MAIDs), General Dynamical Systems (GDS), and complex adaptive dynamics Computer-Aided Design (cadCAD). Next, we provide a chronological overview of the series's four (4) workshops, with links to additional resources.

• Workshop 1: Introduction & Overview
• Workshop 2: Explorations & Connections
• Workshop 3: Agents, Strategies, & Equilibria
• Workshop 4: The Modeling Process & Future Directions

Caveat

⚠️ Throughout the series, you may notice that we touch on relevant technical concepts and alternative approaches only briefly, choosing to focus on the application of MAIDS to inform modular model structures and optimization problems. For example, in the third workshop, we avoid established algorithms for finding Nash Equilibria. Instead, we focus on finding Nash Equilibria via optimization processes, treating this as a black-box optimization problem without a special structure.

Multi-Agent Influence Diagrams (MAIDs)

MAIDs are a diagram syntax useful for representing processes that can be understood as multi-stage games. As diagrammatic models of multi-stage games, they represent - agents, state variables, decision rules, chance processes, and utilities.

Introduced in the paper "Multi-Agent Influence Diagrams for Representing and Solving Games" by Koller and Milch (2003), MAIDS builds on prior work, including influence diagrams, which are themselves generalizations of Bayesian networks. Both influence diagrams and Bayesian networks typically examine randomized probability distributions that consider the actions of one agent. Intended to capture the influence between multiple agents, MAIDs extend on previous models in two ways; MAIDs deal with discrete agents rather than just one overall process and look at decisions they might make in response to different events. 

The traditional representations of games using the extensive form or the strategic form obscure much of the structure of real-world games. In this paper, we propose a graphical representation for noncooperative games—multi-agent influence diagrams (MAIDs). The basic elements in the MAID representation are variables, allowing an explicit representation of dependence, or relevance, relationships among variables. We define a decision variable D′ as strategically relevant to D if, to optimize the decision rule at D, the decision maker needs to consider the decision rule at D′. We provide a sound and complete graphical criterion for determining strategic relevance. We then show how strategic relevance can be used to decompose large games into a set of interacting smaller games, which can be solved in sequence. We show that this decomposition can lead to substantial savings in the computational cost of finding Nash equilibria in these games.

Generalized Dynamical Systems (GDS)

Generalized Dynamical Systems (GDS) were introduced by Barbashian (1949), further developed by Roxin in 1967, and extensively researched here at BlockScience as a mathematical framework for applications in the emerging area of enforceable contracts.

Building upon control theory, the GDS framework provides a ‘template’ for dynamical systems whose states are influenced by decision-making. The approach emphasizes the impact of feasibility and admissibility of actions on solution trajectories instead of relying upon fixed (potentially restrictive) assumptions about decision-maker behavior.

In the first of three works, we consider a generalized dynamical system (GDS) extended from that initially proposed by [25, 24], where a data structure is mapped to itself, and the space of such mappings is closed under composition. We argue that GDS is the natural environment to consider questions arising from the computational implementation of autonomous and semi-autonomous decision problems with one or more constraints, nesting into one framework well-studied models of optimal control, system dynamics, agent-based modeling, and networks, among others. Particular attention is paid to mathematical constructions which support applications in mechanism design. The contingent derivative approach is defined, along with an associated metric, for which a GDS admits the study of existence of state trajectories that satisfy system constraints. The system may also be interpreted as a discretized version of a differential inclusion, allowing the characterization of the reachable subspaces of the state space, and locally controllable trajectories. The second and third parts in the three-part series are briefly described and cover applications and implementations, with the latter demonstrating explicitly how a GDS can be implemented as software using Complex Adaptive Dynamics Computer Aided Design (cadCAD) [30].

complex adaptive dynamics Computer-Aided Design (cadCAD)

Developed by Blockscience, cadCAD is an open-source Python package that assists in the processes of designing, testing, and validating complex systems through simulation.

Given a complex system model, cadCAD can simulate the impact that a set of actions might have on it. This helps users make informed, rigorously tested decisions on how best to modify or interact with the system to achieve their goals. cadCAD supports different system modeling approaches and can be easily integrated with common empirical data science workflows. Monte Carlo methods, A/B testing, and parameter sweeping features are natively supported and optimized.

Complex Adaptive Dynamics Computer-Aided Design (cadCAD) is a language for encoding Generalized Dynamical Systems (GDS) as computer programs. As a modeling framework, cadCAD is based on best practices from control systems engineering; this framework was designed by Michael Zargham, Markus Koch, and Matt Barlin in 2018 in order to bypass the need for powerful closed-source software such as Matlab/Simulink in their economic systems design work at BlockScience. The first implementation of cadCAD was developed by Joshua Jodesty, in parallel with the framework development. Python was chosen for the initial implementation due to the wide range of numerical computing tools already available in Python's open-source data science ecosystem. The Python implementation of cadCAD was Open Sourced in partnership with the Commons Stack in 2019 and has since exploded in use, most notably amongst cryptoeconomic systems designers and token engineers. As of May 2021, there are multiple implementations of cadCAD. This specification was written in part to document the unifying principles for multiple cadCAD implementations spanning Python, Javascript, and Rust and in part to serve as the basis for a new Julia implementation of cadCAD for which Emanuel Lima is the lead developer.

Workshop 1: Introduction & Overview

Workshop 1 introduces MAIDs, GDS, and cadCAD modeling tools. The Killer Tree scenario from Koller and Milch (2003) introduces MAID diagrammatic syntax. The resulting underlying graph is then used to begin exploring the connections between the three different types of modeling frameworks, with a focus on their use within Blockscience's work.

PART I: Multi-Agent Influence Diagrams (MAIDs)
[00:00:00] Introduction Overview & Goals
[00:03:10] Killer Tree Scenario: Meet Alice & Bob
[00:06:20] Killer Tree Scenario: MAIDs Representation
[00:08:30] Killer Tree Scenario: Discussion of Diagrammatic Syntax
[00:10:58] Killer Tree Scenario: Discussion of Utility Function & Total Utility
[00:14:54] Discussion: Modeling Perspectives and the Role of Nature
[00:18:02] Alt MAID Representation
[00:19:01] MAID Mathematical Definition
[00:20:35] MAID application to Graphs & Hypergraphs
[00:23:25] Discussion: MAIDs Where to Next?

PART II: Generalized Dynamical Systems (GDS)
[00:34:17] Choices of State Space
[00:41:18] Modeling Decisions & Trade-Offs
[00:43:08] Incorporating Time in Dynamic Systems
[00:43:48] Generalized Dynamical Systems and Input Spaces
[00:46:02] Time, Events & Parallel Processing
[00:51:40] Reconciling Models & Information Flow
[00:55:24] Translating MAIDs to GDS Models

PART III Complex Adaptive Dynamics Computer-Aided Design (cadCAD)
[00:59:28]Structuring cadCAD Models from MAIDS
[01:04:51] The Role of Domain Experts in Modeling
[01:05:25] The Importance of Modularization in Modeling
[01:07:25] System Identification & Observing Behavior
[01:13:33] Final Thoughts and Future Directions

Workshop 2: Explorations & Connections

Workshop 2 takes a more technical look at complex system modeling in terms of both theoretical mathematics and practical coding. The mathematical perspective establishes a rigorous footing for the idea of connections between MAIDS, Influence Diagrams, and Bayesian Networks. The practical approach considers tools to make coding simulations more reliable, fast, and translatable between different models.

PART I: Review of MAID Graph Structure
[00:00:00] Practical & Theoretical Approaches
[00:01:47] MAIDS Graph Structure
[00:05:50] Technical Discussion
[00:08:33] Distinctions GDS & MAIDS
[00:11:20] Bayesian Networks (MAIDS) vs Dynamical Systems (GDS)
[00:17:12] Model & Tool Selection

PART II: Theoretical Foundations
[00:20:36] MAIDs as a Generalization of Influence Diagrams
[00:27:12] Lenses: Category Theory & Mathematical Modeling
[00:37:10] Choice in Modeling Transformations
[00:40:55] Practical Application: Utility in Decentralized Protocols
[00:43:43] Aggregation
[00:47:00] Bayesian Networks: Conditional Probability Distribution
[00:51:18] Conditional Independence
[00:58:52] Causal Inference & Modeling
[01:01:55] Active & Blocked Paths

PART III: Practical Applications
[01:08:47] Engineering for Uncertainty
[01:11:19] Directional Separation
[01:14:06] Compute Directional Separation
[01:16:05] Sanity Checks & Cross-Validation
[01:17:11] MSML as a Rosetta Stone
[01:19:29] Causality & System Identification
[01:24:35] Concluding Thoughts and Future Directions

Workshop 3: Agents, Strategies, & Equilibria

Workshop 3 focuses on the notion of a game strategy profile, wherein the strategy chosen by each player ultimately determines the agent utilities and possible game outcomes. Workshop participants discuss theoretical and practical optimization approaches with pgmpy & cadCAD. We show how to determine a Bayesian Network using the Killer Tree MAID and use pgmpy to sketch the algorithm for finding a Nash Equilibrium as described by Koller and Milch. See ⚠️Caveat

PART I: Multi-Agent Influence Diagrams (MAID) Review
[00:00:00] Introduction
[00:00:43] Review of Multi-Agent Influence Diagrams (MAIDs)
[00:01:27] Killer Tree Scenario: Alice & Bob's Decision-Making Scenario
[00:02:21] Clarifications & Underlying Graph Structure of a MAID

PART II: Decision Rules, Strategies & Optimization
[00:06:18] Decision Rules & Strategies
[00:07:31] Interactive Q&A on Decision Rules
[00:19:39] Understanding Strategy Profiles
[00:21:50] Conditional Probability Distributions
[00:25:47] Connecting MAIDS Agent Strategies & GDS
[00:27:19] Optimization & Strategy Selection
[00:35:06] Modeling Decisions in Utilities, Strategy Profiles & Optimization.
[00:43:01] Understanding Decision Rules & Strategies
[00:44:06] Control Policies & Observable States
[00:45:06] Challenges in Traditional Economic Game Theory
[00:47:13] Equilibrium in Control Theory
[00:48:38] Nash Equilibrium & Strategy Updates
[00:51:10] Dynamical Systems
[00:55:43] Starting Points, Strategy & Maximizing Utility Value

PART III: Coding Optimization
[01:00:07] Determine Bayesian Network using MAIDS
[01:01:54] Implementing Bayesian Networks in Python
[01:05:18] Conditional Probability Distributions
[01:11:35] Optimizing Decision Rules
[01:16:37] Algorithm for Finding Nash Equilibrium
[01:19:29] Multi-Scale Evolving Systems & Network Games
[01:26:39] Concluding Thoughts & Future Directions

Workshop 4: The Modeling Process & Future Directions

Workshop 4 explores how MAIDs can inform cadCAD models, emphasizing a standardized structure for policy functions and state update functions, a process that offers a template for encapsulating agent logic, enabling greater abstraction and testability. In this way, MAIDs could allow non-coders to participate actively in creating the cadCAD model structure or aid translation by AI. See ⚠️Caveat

PART I: Introduction & MAIDs Review
[00:00:00] Introduction and Greetings
[00:00:00] Session Overview and Background
[00:00:48] Multi-Agent Influence Diagrams (MAIDs)
[00:03:46] Personal Background and Research Approach
[00:05:34] Undergraduate Research and Team Building
[00:07:14] MAIDs in Mathematical Pedagogy

PART II: MAIDS Informed CAD CAD Frameworks & Code Structures
[00:10:25] Modeling Frameworks & CAD CAD
[00:16:37] What MAID representations enable
[00:18:45] CAD CAD Modeling
[00:20:09] Value of Qualitative Representations & Graph Structure of MAIDs
[00:21:43] Translating MAIDs to cadCAD Model Structure
[00:22:50] cadCAD Partial State Update Blocks
[00:24:32] Modeling Process

PART III: MAIDS Informed Agent-Based Approach to cadCAD
[00:28:36] Coding Framework for cadCAD
[00:31:20] Connection to MSML
[00:33:42] Agent Decisions
[00:35:25] Agent Strategy
[00:36:10] Agent Utility Functions
[00:37:14] Possibilities of Agent Structure
[00:42:06] Discussion: Q&A
[00:44:26] cadCAD World Model
[00:46:46] Board Game Analogy: MAIDS & cadCAD
[00:49:24] Complexity in State Space & Rule Sets
[00:51:54] Decision Rules & Strategy Space
[00:54:52] Agent-Based Modeling & Network Policies
[00:58:13] Agent Modeling as a Philosophy
[00:59:21] Space & Time, Agents & Abstract Patterns
[01:01:48] GDS & Mapping the Admissible Action Space
[01:02:53] GDS for Non-Trivial Choice
[01:06:05] Combining Rules into Strategies
[01:07:13] Agents as Parameters
[01:08:40] Parameters to Simulations to Experiments
[01:09:16] Designing Experiments
[01:09:56] Philosophical Questions on Passive Agents

PART IV: Applied & Future Directions
[01:14:43] Practical Engineering Application
[01:16:14] The Search for Nash Equilibrium
[01:21:55] Learning Rules & Second Order Systems
[01:23:21] Dynamic Games & Strategy Updates
[01:31:17] Final Thoughts & Future Directions

Future Directions: Thoughts & Questions

These workshops raised a number of possibilities and intriguing questions that we hope to explore more in the future.

• How can the Agent-Based principles of MAIDs be used to structure cadCAD models, especially for teams that need structured low-demand coding practices?
• How do we operationalize the structure of MAIDs as (hyper)graphs for structural search and long-term organizational memory?
• How can optimization and search be used to improve the spaces of Games and Agents and find parameter settings efficiently?
• How can we better use modeling to understand the inherent geometry of both the map and the territory it hopes to represent?

Acknowledgments

A massive thank you, Octopus! for developing and leading this workshop series. Thank you, workshop participants, for asking questions, challenging ideas, and sharing your perspectives, which helped to make this an interactive and collaborative learning experience. Dr. Zargham and Dr. Shorish for the domain expertise upon which we built. RJ Cordes for informing the workshops and the Communications team for publishing. And you! Thank you for watching and reading, learning, and sharing—all of us nodes in the open-source knowledge networks of our collective future.

About BlockScience

BlockScience® is a complex systems engineering, R&D, and analytics firm that integrates ethnography, applied mathematics, and computational science. We analyze and design safe and resilient socio-technical systems, and with deep expertise in market design, distributed systems, and AI, we provide systems engineering services to a wide range of for-profit, non-profit, academic, and government clients.