Artificial Computational Intelligence

Hidden Markov Model Algorithms and Multi-Agent Decision Making

Published: 2026-08-16

Level: postgraduate

Audience: Postgraduate students in Artificial Intelligence and Computational Intelligence

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

D-Separation and Variable Elimination — covered in Lecture 13 (probabilistic inference in Bayesian networks)
Bayesian Networks and Approximate Inferencing — covered in Lecture 13 (prior sampling, rejection sampling, likelihood weighting)
Temporal Data and the Markov Assumption — covered in Lecture 14 (first-order Markov models, transition probability matrices)
Hidden Markov Models — covered in Lecture 14 (urn game, TPM, EPM, HMM diagram construction)
Forward Propagation Algorithm — covered in Lecture 14 (basic forward propagation computation)
HMM Query Types — covered in Lecture 14 (filtering, prediction, smoothing, Viterbi)

15.1 Course Context and Module Overview

15.1.1 Course Progression Recap

Hook: Why does a lecture on Hidden Markov Models and game theory appear at the end of an AI course? Because temporal reasoning and multi-agent decision making are where the pieces come together — representing uncertainty over time and coordinating multiple decision-makers are two of the hardest problems in AI.

Before diving into new material, the professor provides a comprehensive recap of the entire course structure to contextualize where Module 6 (temporal reasoning) fits within the broader AI curriculum. This recap is not just historical — it shows how each module builds on the previous one, forming a layered understanding of intelligent agents.

The course began with the foundational question of what constitutes AI and its different forms, organized into four quadrants. A significant portion of the early modules (roughly four to five classes) treated AI as a search problem, covering uninformed search, informed search, A* search, local search, and game playing through adversarial search. After the mid-semester break, the course shifted from the "AI" component to the "Computational Intelligence" component — focusing on how agents store information and infer new knowledge.

Module 4 covered knowledge representation using logic. The earliest form used propositional logic, which offered low ambiguity compared to plain English. Once knowledge was represented, inference techniques could be applied: truth tables, theorem proving, the DPLL algorithm, and combinations of converting queries into CNF form with negation/contradiction and unit resolution. These techniques remain relevant today — even modern frontier models and LLMs can benefit from logic-based approaches when building small, domain-specific systems.

Propositional logic had limitations: it could not represent quantifiers like "for all" or "there exists." This motivated the move to first-order logic (also called predicate logic), which could represent richer information. Inference on predicate logic could proceed by converting to propositional logic and applying existing techniques, or directly through forward and backward chaining.

Module 5 addressed uncertainty by introducing probabilistic representation and reasoning through Bayesian networks. The learning objectives were: (1) given a plain English description, draw the Bayesian network for representation, and (2) perform inferencing using exact methods (enumeration, variable elimination) or approximate methods (prior sampling, rejection sampling, likelihood weighting). Two types of queries were distinguished: joint probability (straightforward — use the chain rule with network values) and conditional probability (requires conversion using alpha normalization, marginalization over hidden variables, then solving).

Variable elimination was specifically designed for dependent variables: when a query variable depends on other nodes, those parent nodes are eliminated so the query variable becomes independent and can be answered directly.

Module 6 introduced temporal reasoning — uncertainty over time series or temporal data. This is where the current lecture sits.

Intuition + Analogy: Think of the course as building a toolbox. Early modules gave you tools for finding paths (search) and representing facts (logic). Later modules added tools for handling uncertainty (probability). Now we're adding tools for uncertainty that changes over time (temporal models) and for situations where multiple agents interact (game theory). Each new tool builds on the previous ones — you need probability to handle uncertainty, and you need uncertainty to handle time.

Course Structure Summary:

Modules 1-3: AI as search — uninformed, informed, adversarial
Module 4: Knowledge representation — propositional logic, first-order logic, inference
Module 5: Uncertainty — Bayesian networks, exact and approximate inference
Module 6: Temporal reasoning — Hidden Markov Models, filtering, Viterbi, multi-agent decision making

Visual Intuition: Imagine a pyramid. At the base is search (finding paths). Above that is logic (representing facts). Then probability (handling uncertainty). At the top is temporal reasoning (uncertainty over time) and multi-agent systems (multiple decision-makers). Each layer depends on the layers below it.

Recap + Bridge: The course has systematically built from simple deterministic problems (search) through logical representation and probabilistic reasoning to the current frontier: reasoning about uncertain processes that evolve over time and involve multiple interacting agents. This lecture begins Module 6 with Hidden Markov Models, which extend Bayesian networks to temporal sequences, and then introduces game theory for multi-agent decision making.

15.2 Hidden Markov Models: Foundation and Five Query Types

15.2.1 The Markov Property

Hook: Imagine predicting tomorrow's weather. Do you need to know what the weather was like ten years ago, or just the last few days? The Markov property says that for many systems, only the recent past matters — the distant history can be ignored.

The Markov property captures the idea that what affects a system today depends only on the recent past, not on distant history. In many real-world scenarios, knowing what happened yesterday or two days ago is sufficient — one does not need to look back years of data. This assumption simplifies reasoning about temporal processes enormously, because we don't need to track the entire history of the system.

The order of a Markov model determines how far back it looks:

First-order Markov: considers only time $t - 1$
Second-order Markov: considers $t - 1$ and $t - 2$
Third-order Markov: considers three previous time steps

For this course, first-order Markov models are used exclusively, though second-order examples were shown for illustration.

Intuition + Analogy: Think of a Markov model like a game of "telephone" where each person only listens to the previous person. The message (state) at step $t$ depends only on what was said at step $t - 1$ , not on what was said three steps back. This "memoryless" property is what makes Markov models tractable — we don't need to remember the entire conversation.

Two key matrices define a Markov model:

The transition probability matrix (TPM) — captures probabilities of moving between hidden states. For a system with $N$ states, the TPM is an $N \times N$ matrix where entry $A_{ij}$ gives the probability of moving from state $i$ to state $j$ . Each row sums to 1.
The emission probability matrix (EPM) — captures probabilities of observing evidence given a hidden state. For $N$ hidden states and $M$ possible observations, the EPM is an $N \times M$ matrix where entry $B_{ij}$ gives the probability of observing evidence $j$ when in state $i$ . Each row sums to 1.

A Markov diagram (finite state diagram) and its corresponding TPM convey the same information in different forms. Students should be able to convert between these representations in both directions. The diagram shows states as nodes and transitions as directed edges labeled with probabilities; the matrix organizes the same probabilities in a table.

Formalization: A first-order Markov process satisfies: $P (X_{t} ∣ X_{0 : t - 1}) = P (X_{t} ∣ X_{t - 1})$ where $X_{t}$ is the state at time $t$ . This is the Markov assumption: the future is conditionally independent of the past given the present.

Worked Example: Consider a simple weather model with two states: Sunny (S) and Rainy (R). The TPM might be: $A = [P (S ∣ S) P (S ∣ R) P (R ∣ S) P (R ∣ R)] = [0.8 0.4 0.2 0.6]$ This means: if today is sunny, there's an 80% chance tomorrow is sunny and 20% chance of rain. If today is rainy, there's a 40% chance of sun tomorrow and 60% chance of continued rain. Each row sums to 1.

Assumptions & Scope: The Markov assumption is often an approximation. Real-world systems may have longer-term dependencies. Two ways to improve accuracy: (1) increase the order of the model (e.g., second-order), or (2) increase the set of state variables to capture more context. However, higher-order models require more parameters and data.

15.2.2 Hidden Markov Models (HMM)

An HMM models situations where certain events are unobserved (hidden) while other events are observed (evidence). The classic teaching example involves three urns (baskets), each containing two colors of balls (orange and blue). A facilitator first picks a basket (hidden — you do not know which), then draws a ball and shows it (observed — you see the color). The basket selection follows the TPM; the ball color follows the EPM.

Intuition + Analogy: Imagine you're in a room with three curtains. Behind each curtain is a basket of colored balls. A helper picks a basket (you can't see which), draws a ball, and shows it to you. You see the ball's color (evidence) but not which basket it came from (hidden state). Over time, you see a sequence of ball colors and try to figure out which baskets were chosen. That's an HMM — you observe evidence, but the underlying states are hidden.

Real-world applications of HMMs include:

Grammarly and word prediction tools — predicting the next word based on previous words
Natural language processing (NLP) — a complete field built on HMM principles, including part-of-speech tagging and named entity recognition
Speech recognition — converting audio signals to text by modeling phonemes as hidden states and acoustic features as observations
Machine translation — aligning words across languages
Bioinformatics — gene prediction and protein structure analysis

The fundamental structure: there are unobserved events occurring, and a set of observed things happening. Given what has been observed and what remains unobserved, the agent can perform reasoning. The key insight is that the hidden states follow a Markov process, and the observations depend only on the current hidden state (sensor Markov assumption).

HMM Definition: An HMM is defined by:

State set $S = {s_{1}, s_{2}, \dots, s_{N}}$ — the hidden states
Observation set $O = {o_{1}, o_{2}, \dots, o_{M}}$ — the possible observations
Initial state distribution $π$ — probabilities of starting in each state
Transition probability matrix $A$ — probabilities of moving between states
Emission probability matrix $B$ — probabilities of observations given states

Together, these are often denoted as $λ = (A, B, π)$ .

Worked Example (Urn Problem): Three urns (U1, U2, U3) with different ball compositions:

U1: 60% orange, 40% blue
U2: 30% orange, 70% blue
U3: 50% orange, 50% blue

TPM (basket transitions): $A = 0.5 0.2 0.3 0.3 0.6 0.3 0.2 0.2 0.4$ EPM (ball colors given baskets): $B = 0.6 0.3 0.5 0.4 0.7 0.5$ where columns represent orange and blue respectively. If we observe sequence [orange, blue], what's the probability? This requires forward propagation (covered in Section 15.3).

15.2.3 The Five Types of HMM Queries

Understanding the five query types is critical because each serves a different real-world purpose:

Hook: Given a sequence of observations, what can we learn about the hidden states? The answer depends on the question we ask. There are five fundamentally different questions we can ask of an HMM, each with its own algorithm.

Type 1: Probability of Evidence (Forward Propagation) Given a sequence of observed evidence, what is the probability that this exact sequence occurred? Example: "What is the probability of observing sunny, sunny, rainy over three days?" Answer is a single probability value. This is useful for anomaly detection — if a sequence has very low probability, something unusual may be happening.

Type 2: Filtering Given all evidence up to and including the current day, what is the hidden variable on the current (last) day? Example: "Given that days 1, 2, 3 were sunny, sunny, rainy — what was the pressure on day 3?" Answer is a single hidden state (e.g., "high pressure" or "low pressure"). Filtering is used in real-time tracking — determining the current state as new evidence arrives.

Type 3: Prediction Given all evidence up to today, what will the hidden variable be in the future? Example: "What will the hidden variable be on day 5, given evidence through day 3?" This is prediction — looking forward from the current time. (Not on the exam per the professor, but understanding the concept is important.) Prediction is used in weather forecasting and stock market prediction.

Type 4: Smoothing Given all evidence, what was the hidden variable at some point in the past? Example: "Given days 1 through 5, what was the hidden variable on day 2?" This is looking backward into the middle of the sequence. (Not on the exam.) Smoothing is used in offline analysis — reconstructing past states after all data is collected.

Type 5: Viterbi's Algorithm (Most Likely Explanation) Given a sequence of evidence, what is the most likely sequence of hidden variables for ALL days? Example: "Given sunny, sunny, rainy, tell me what the hidden variable was on day 1, day 2, AND day 3." Answer is a set (vector) of hidden states — one per day. This is fundamentally different from the other four types, which return a single probability value. Viterbi is used in speech recognition (finding the most likely word sequence) and gene finding (finding the most likely gene structure).

Query Type Summary:

Forward Propagation → Probability of evidence sequence
Filtering → Current hidden state (last day)
Prediction → Future hidden state
Smoothing → Past hidden state
Viterbi → Most likely hidden state sequence

Q: Are HMM prediction and smoothing in the syllabus, or are we expected to solve questions on them? A: No, not really. The professor wants students to understand what these query types mean and how they relate, but questions will not be asked directly on prediction and smoothing. Only filtering and Viterbi's algorithm are exam-relevant. However, understanding all five types helps see the big picture.

Pitfalls: A common mistake is confusing filtering with Viterbi. Filtering asks "what is the hidden state on the last day?" while Viterbi asks "what is the most likely hidden state for every day?" Filtering gives a single state; Viterbi gives a sequence.

Recap + Bridge: The Markov property allows us to model temporal processes with limited memory. HMMs extend this by adding hidden states and observations. There are five fundamental queries we can ask of an HMM, each with its own purpose. The next sections will detail the algorithms for the three exam-relevant types: forward propagation, filtering, and Viterbi.

15.3 Forward Propagation Algorithm: Detailed Worked Example

15.3.1 The Problem Setup

Hook: Given a sequence of observations (like sunny, sunny, rainy), what is the probability that this exact sequence occurred? Forward propagation answers this by building up the probability step by step, day by day.

The question asks: "What is the probability that the sequence of observations was SSR (sunny, sunny, rainy)?"

The hidden variables are pressure states: low pressure (L) or high pressure (H). The initial probability is 50-50 for L and H (since no initial probability distribution was explicitly given). The emission and transition probabilities come from the provided matrices.

Intuition + Analogy: Think of forward propagation like tracking a ball rolling through a maze. At each day (time step), the ball can be in one of two rooms (L or H). We calculate the probability of the ball being in each room based on where it was yesterday and what we observed today. At the end, we add up the probabilities of all possible paths that could have produced the observed sequence.

Problem Setup Details:

Observation sequence: SSR (sunny, sunny, rainy)
Hidden states: L (low pressure), H (high pressure)
Initial probabilities: $P (L) = 0.5$ , $P (H) = 0.5$ (assumed equal when not specified)
Transition probabilities (TPM):

$A = [P (L ∣ L) P (L ∣ H) P (H ∣ L) P (H ∣ H)] = [0.5 0.5 0.5 0.5]$ (Note: The actual TPM values from the lecture diagram may differ; these are illustrative.)

Emission probabilities (EPM):

$B = [P (sunny ∣ L) P (sunny ∣ H) P (rainy ∣ L) P (rainy ∣ H)] = [0.2 0.6 0.8 0.4]$

15.3.2 Day 1 Computation

The first observation is sunny. Starting with equal initial probabilities:

$P (L) = 0.5$ , $P (H) = 0.5$

The emission probabilities for "sunny" given each pressure state come from the EPM:

$P (sunny ∣ L) = 0.2$
$P (sunny ∣ H) = 0.6$

Computing the first-day node values:

For L: $P (L) \times P (sunny ∣ L) = 0.5 \times 0.2 = 0.1$
For H: $P (H) \times P (sunny ∣ H) = 0.5 \times 0.6 = 0.3$

These values (0.1 and 0.3) are stored at the first-day nodes.

Formula for Day 1: $f_{1} (i) = π (i) \times P (e_{1} ∣ i)$ where $f_{1} (i)$ is the forward variable for state $i$ at time 1, $π (i)$ is the initial probability of state $i$ , and $P (e_{1} ∣ i)$ is the emission probability of the first observation given state $i$ .

Normalization note: The professor demonstrated normalization at this step purely for teaching purposes. Normalization means dividing each value by the sum: for L, $\frac{0.1}{0.1 + 0.3} = 0.25$ ; for H, $\frac{0.3}{0.1 + 0.3} = 0.75$ . However, for the forward propagation algorithm, normalization is optional — if you choose to normalize, you must normalize at every step; if you choose not to, you skip it at every step. This is a critical rule.

Scope: Normalization is optional for forward propagation but mandatory for filtering (Section 15.4). If you normalize at any step, you must normalize at all steps. Partial normalization is never acceptable.

15.3.3 Day 2 Computation

The second observation is also sunny. On day 2, there are two possible hidden states (L and H), and each can be reached from either L or H on day 1. This creates a tree with four paths and two destination nodes.

For the day-2 L node, two arrows converge:

Arrow from day-1 L: $P (L)_{day1} \times P (L ∣ L) \times P (sunny ∣ L)$

= $0.1 \times 0.5 \times 0.2 = 0.01$

Arrow from day-1 H: $P (H)_{day1} \times P (L ∣ H) \times P (sunny ∣ L)$

= $0.3 \times 0.5 \times 0.2 = 0.03$

The three components of each formula correspond to: (1) the previous node's answer (forward propagation), (2) the transition probability from the TPM, and (3) the emission probability from the EPM.

For the day-2 H node, two arrows converge:

Arrow from day-1 L: $P (L)_{day1} \times P (H ∣ L) \times P (sunny ∣ H)$

= $0.1 \times 0.5 \times 0.6 = 0.03$

Arrow from day-1 H: $P (H)_{day1} \times P (H ∣ H) \times P (sunny ∣ H)$

= $0.3 \times 0.5 \times 0.6 = 0.09$

Adding the arrows: For each node, the two incoming path values are added because we want the total probability of reaching that state regardless of which previous state we came from. The question only cares about "sunny, sunny" — not about which pressure state caused each sunny day.

Day-2 L total: $0.01 + 0.03 = 0.04$
Day-2 H total: $0.03 + 0.09 = 0.12$

Formula for Day 2: $f_{2} (j) = i \in {L, H} \sum f_{1} (i) \times P (j ∣ i) \times P (e_{2} ∣ j)$ where $f_{2} (j)$ is the forward variable for state $j$ at time 2. The sum is over all possible previous states $i$ . This is the recursive step of forward propagation.

Worked Example (Day 2):

For L: $0.1 \times 0.5 \times 0.2 + 0.3 \times 0.5 \times 0.2 = 0.01 + 0.03 = 0.04$
For H: $0.1 \times 0.5 \times 0.6 + 0.3 \times 0.5 \times 0.6 = 0.03 + 0.09 = 0.12$
Total so far (if we added): $0.04 + 0.12 = 0.16$ (but we don't add yet)

15.3.4 Day 3 Computation

The third observation is rainy. Again, two possible hidden states (L and H), each reachable from L or H on day 2. The structure mirrors day 2, but now uses $P (rainy ∣ L)$ and $P (rainy ∣ H)$ from the EPM.

For the day-3 L node:

From day-2 L: $P (L)_{day2} \times P (L ∣ L) \times P (rainy ∣ L)$

= $0.04 \times 0.5 \times 0.8 = 0.016$

From day-2 H: $P (H)_{day2} \times P (L ∣ H) \times P (rainy ∣ L)$

= $0.12 \times 0.5 \times 0.8 = 0.048$

Sum: $0.016 + 0.048 = 0.064$

For the day-3 H node:

From day-2 L: $P (L)_{day2} \times P (H ∣ L) \times P (rainy ∣ H)$

= $0.04 \times 0.5 \times 0.4 = 0.008$

From day-2 H: $P (H)_{day2} \times P (H ∣ H) \times P (rainy ∣ H)$

= $0.12 \times 0.5 \times 0.4 = 0.024$

Sum: $0.008 + 0.024 = 0.032$

After computing and adding the incoming paths:

Day-3 L value: 0.064
Day-3 H value: 0.032

Final step for forward propagation: ADD these two values (not compare): $0.064 + 0.032 = 0.096$

This is the answer — the probability of observing the sequence SSR is 0.096.

Pitfall: A common mistake is to compare the final values (like in filtering) instead of adding them. Forward propagation asks for the probability of the evidence sequence, which requires summing over all possible hidden state sequences. Adding the final values gives the total probability.

15.3.5 Formula Structure Summary

Every formula in the forward propagation follows this pattern: $Node value = from previous node P (previous state) \times from TPM P (current state ∣ previous state) \times from EPM P (observation ∣ current state)$

The first component comes from the previous step's computed answer (hence "forward propagation"). The second component comes from the transition probability matrix. The third component comes from the emission probability matrix. When multiple arrows converge on a single node, the values are summed.

General Forward Propagation Formula: $f_{t} (j) = [i = 1 \sum N f_{t - 1} (i) \times A_{ij}] \times B_{j} (e_{t})$ where:

$f_{t} (j)$ is the forward variable for state $j$ at time $t$
$N$ is the number of hidden states
$A_{ij}$ is the transition probability from state $i$ to state $j$
$B_{j} (e_{t})$ is the emission probability of observation $e_{t}$ given state $j$
The sum is over all possible previous states $i$

15.3.6 Student Questions on Forward Propagation

Q: Why do we add both the L and H values at the final step instead of just picking one? A: Both paths represent the same evidence sequence SSR. The question asks for the total probability of observing SSR regardless of which hidden state produced each day. Path through L gives one probability, path through H gives another — both are valid routes to SSR, so we add them to get the total probability.

Q: Why didn't we do normalization in this problem? A: Normalization is optional for the forward propagation algorithm. If you choose to normalize, you must do it at every step. If you choose not to normalize, you skip it at every step. Either approach gives the correct final answer — the professor showed normalization in the first step purely for teaching purposes.

15.3.7 Extending the Problem

If the question adds a fourth observation (e.g., SSR → SSR + sunny), you simply add another layer of nodes to the diagram. The computation proceeds identically — compute two formulas per node, add them, and continue. The previous work (days 1-3) remains valid and does not need recomputation.

However, if a change occurs in the middle of the sequence (e.g., changing day 2 from sunny to rainy, making it SRSR), the entire problem must be redrawn from the point of change onward. The previous work from day 1 remains valid, but everything after the changed observation must be recomputed.

Pitfall: When extending a problem, you don't need to recompute earlier days. But if you change an observation in the middle, you must recompute from that point onward.

15.3.8 When Forward Propagation is Used

Forward propagation answers: "Given a bunch of evidence in a specific order, what is the probability of that exact sequence occurring?" It does NOT tell you the hidden states — it only gives a probability number.

Exam-style example: "A student performed well in EC1, poorly in EC2, and well in EC3. What is the probability of this grade pattern?" The hidden variable is effort/concentration; the evidence is the grades.

Recap + Bridge: Forward propagation computes the probability of an observed sequence by building up the probability day by day, summing over all possible hidden state paths. The algorithm is recursive: each day's values depend on the previous day's values, the TPM, and the EPM. The final answer is the sum of the probabilities for all possible hidden states on the last day. This is the foundation for filtering (Section 15.4) and Viterbi (Section 15.5), which modify the final step or the intermediate steps.

15.4 Filtering Algorithm

15.4.1 What Filtering Asks

Hook: You're tracking the weather over three days: sunny, sunny, rainy. You want to know: "On day 3, was it a low-pressure day or a high-pressure day?" Filtering answers exactly this question — it gives you the most likely hidden state on the last day, given all evidence up to that day.

Filtering answers: "Given all evidence up to and including the current (last) day, what was the hidden variable on that last day?" It does not ask about future days (that is prediction) or about past days (that is smoothing).

Example: Three days of evidence are SSR. On day 3, it rained. Was day 3 a low-pressure day or a high-pressure day? Filtering answers this question.

Intuition + Analogy: Think of filtering like a doctor diagnosing a patient based on symptoms up to today. The doctor doesn't care about symptoms from a week ago (smoothing) or what symptoms might appear tomorrow (prediction). The doctor wants to know: "Given all symptoms so far, what is the most likely condition today?" That's filtering.

Formal Definition: Filtering computes the belief state $P (X_{t} ∣ e_{1 : t})$ — the posterior probability distribution over the hidden state at time $t$ given all evidence from time 1 to $t$ . This is also called state estimation.

15.4.2 Filtering Procedure

Filtering uses the same forward propagation algorithm with two key differences:

Difference 1: Normalization is mandatory at every step. Unlike forward propagation where normalization is optional, filtering requires normalization at every time step. This ensures the probabilities sum to 1 at each step, which is necessary for the final comparison.

Difference 2: The final step uses comparison, not addition. Instead of adding the two final node values (as in forward propagation), you compare them and pick the one with the higher probability. The hidden state corresponding to the higher probability is your answer.

Filtering Algorithm (Recursive): The filtering algorithm is a recursive procedure that maintains a belief state at each time step:

Prediction step: Project the belief state forward:

$P (X_{t + 1} ∣ e_{1 : t}) = x_{t} \sum P (X_{t + 1} ∣ x_{t}) P (x_{t} ∣ e_{1 : t})$ This uses the transition model to predict the next state.

Update step: Incorporate the new evidence:

$P (X_{t + 1} ∣ e_{1 : t + 1}) = α P (e_{t + 1} ∣ X_{t + 1}) P (X_{t + 1} ∣ e_{1 : t})$ where $α$ is a normalization constant ensuring the probabilities sum to 1. This uses the sensor model to update the belief based on the new observation.

The algorithm alternates between prediction and update at each time step.

15.4.3 Worked Filtering Example

Using the same SSR evidence:

Day 1: Initial probabilities 0.5, 0.5. Multiply by emission probabilities for sunny:

L: $0.5 \times 0.2 = 0.1$
H: $0.5 \times 0.6 = 0.3$

Normalize: $P (L) = \frac{0.1}{0.4} = 0.25$ , $P (H) = \frac{0.3}{0.4} = 0.75$

Day 1 Computation:

Unnormalized: L = 0.1, H = 0.3
Sum = 0.4
Normalized: L = 0.25, H = 0.75

Day 2: Compute the two incoming paths for each node (same formulas as forward propagation):

Using unnormalized values from day 1:

For L on day 2: from L path = $0.1 \times 0.5 \times 0.2 = 0.01$ ; from H path = $0.3 \times 0.5 \times 0.2 = 0.03$

Sum = $0.01 + 0.03 = 0.04$

For H on day 2: from L path = $0.1 \times 0.5 \times 0.6 = 0.03$ ; from H path = $0.3 \times 0.5 \times 0.6 = 0.09$

Sum = $0.03 + 0.09 = 0.12$

Normalize: $P (L) = \frac{0.04}{0.16} = 0.25$ , $P (H) = \frac{0.12}{0.16} = 0.75$

Day 2 Computation:

Unnormalized: L = 0.04, H = 0.12
Sum = 0.16
Normalized: L = 0.25, H = 0.75

Day 3 (the day filtering asks about): Evidence is rainy. Compute incoming paths:

Using unnormalized values from day 2:

For L on day 3: from L path = $0.04 \times 0.5 \times 0.8 = 0.016$ ; from H path = $0.12 \times 0.5 \times 0.8 = 0.048$

Sum = $0.016 + 0.048 = 0.064$

For H on day 3: from L path = $0.04 \times 0.5 \times 0.2 = 0.008$ ; from H path = $0.12 \times 0.5 \times 0.2 = 0.024$

Sum = $0.008 + 0.024 = 0.032$

Normalize: $P (L) = \frac{0.064}{0.096} = 0.6667$ , $P (H) = \frac{0.032}{0.096} = 0.3333$

Day 3 Computation:

Unnormalized: L = 0.064, H = 0.032
Sum = 0.096
Normalized: L ≈ 0.6667, H ≈ 0.3333

Final comparison: Between L (≈0.667) and H (≈0.333), the maximum is L with ≈0.667. Therefore, on day 3, the most likely hidden variable was a low pressure day.

Pitfall: The exact computed values depend on the specific TPM and EPM values used in the lecture's diagram. The values above use the TPM and EPM from Section 15.3. If the lecture diagram uses different values, the numbers will differ. Always use the values provided in the problem statement.

15.4.4 Why Filtering Uses Comparison

The key insight: forward propagation adds the final nodes because the question asks for "probability of the entire evidence sequence" — both paths through L and through H contribute to that total probability. Filtering asks "what was the hidden state on the last day?" — so instead of adding, you compare and pick the state with the higher probability.

Without normalization, the maximum would remain the maximum regardless. But normalization is still done at every step in filtering for two reasons: (1) the initial 0.5/0.5 assumption needs accounting for, and (2) during comparisons, we want properly scaled values.

Filtering vs Forward Propagation:

Forward Propagation: Computes $P (e_{1 : t})$ — the probability of the evidence sequence. Final step: ADD terminal node values.
Filtering: Computes $P (X_{t} ∣ e_{1 : t})$ — the probability distribution over the hidden state at time $t$ . Final step: COMPARE and pick MAX.

Both use the same recursive computation; the difference is in the final step and normalization requirements.

Scope: Filtering is used in real-time tracking applications where you need to estimate the current state as new evidence arrives. It's an online algorithm — it doesn't need to reprocess all data from the beginning.

Recap + Bridge: Filtering is forward propagation with mandatory normalization at every step and a final comparison instead of addition. It gives the most likely hidden state on the last day. If you need the most likely hidden state for every day, you need Viterbi's algorithm (Section 15.5).

15.5 Viterbi's Algorithm (Most Likely Explanation)

15.5.1 What Viterbi Asks

Hook: Given a sequence of observations (sunny, sunny, rainy), what is the most likely sequence of hidden states (pressure levels) for all three days? Viterbi's algorithm answers this by finding the single most likely path through the hidden states.

Viterbi's algorithm answers: "Given a sequence of evidence, what is the most likely sequence of hidden variables for ALL days?" This is fundamentally different from filtering, which only asks about the last day.

Example: Given SSR evidence, Viterbi produces a pattern like HHL (high, high, low) — telling you the hidden variable for each day, not just the last one.

Q: If we are asked to predict the sequence of transitions, do we get the highest probability path like HHL? A: That is Viterbi's algorithm. Forward propagation gives the probability of the evidence sequence. Filtering gives the hidden variable for the last day. Viterbi gives the hidden variable for every day.

Formal Definition: Viterbi computes: $ar g x_{1 : t} max P (x_{1 : t} ∣ e_{1 : t})$ —the sequence of hidden states $x_{1}, x_{2}, \dots, x_{t}$ that maximizes the posterior probability given the evidence sequence $e_{1}, e_{2}, \dots, e_{t}$ .

15.5.2 Viterbi Procedure

Viterbi also builds on forward propagation, with one key difference at every step:

At each step, instead of summing the incoming paths, pick the maximum and eliminate the lower-probability path.

This is a "pruning" strategy — at every node, only the most promising path survives. The algorithm maintains, for each state at each time, the probability of the most likely path that ends in that state.

Viterbi Algorithm (Recursive): Let $v_{t} (j)$ be the probability of the most likely path ending in state $j$ at time $t$ .

Initialization:

$v_{1} (j) = π (j) \times P (e_{1} ∣ j)$

Recursion:

$v_{t} (j) = i max [v_{t - 1} (i) \times A_{ij}] \times P (e_{t} ∣ j)$ where the max is over all possible previous states $i$ . We also keep track of which previous state $i$ achieved the maximum (for backtracking).

Termination:

The most likely final state is $ar g max_{j} v_{t} (j)$ .

Backtracking:

Trace back through the stored previous states to recover the full sequence.

15.5.3 Worked Viterbi Example

Using the same SSR evidence:

Day 1: Identical to forward propagation and filtering.

L: 0.1, H: 0.3
Normalize: L = 0.25, H = 0.75

Day 1 Computation:

Unnormalized: L = 0.1, H = 0.3
Normalized: L = 0.25, H = 0.75

Day 2 — L node: Two incoming paths:

From L: $0.1 \times 0.5 \times 0.2 = 0.01$
From H: $0.3 \times 0.5 \times 0.2 = 0.03$
Pick max: 0.03 (the path from H wins; eliminate the path from L)

Day 2 — H node: Two incoming paths:

From L: $0.1 \times 0.5 \times 0.6 = 0.03$
From H: $0.3 \times 0.5 \times 0.6 = 0.09$
Pick max: 0.09 (the path from H wins; eliminate the path from L)

Day 2 Computation:

For L: max(0.01, 0.03) = 0.03 (came from H)
For H: max(0.03, 0.09) = 0.09 (came from H)

Day 3: Compute for L and H nodes using the surviving values from day 2. Again, pick the max at each node.

For L: max( $0.03 \times 0.5 \times 0.8$ , $0.09 \times 0.5 \times 0.8$ ) = max(0.012, 0.036) = 0.036 (came from H)
For H: max( $0.03 \times 0.5 \times 0.2$ , $0.09 \times 0.5 \times 0.2$ ) = max(0.003, 0.009) = 0.009 (came from H)

Day 3 Computation:

For L: max(0.012, 0.036) = 0.036 (came from H)
For H: max(0.003, 0.009) = 0.009 (came from H)

Final step: For each day, compare the L and H values and select the larger one:

Day 1: H (0.3) > L (0.1) → H
Day 2: H (0.09) > L (0.03) → H
Day 3: H (0.009) > L (0.036)? Wait, L (0.036) > H (0.009) → L

Answer: HHL — the most likely explanation is high pressure on days 1 and 2, low pressure on day 3.

Pitfall: The final step compares values at each day independently. Don't assume the same state wins every day. You must compare L vs H for each day separately.

15.5.4 The Elimination Trick

In Viterbi, you can eliminate the weaker path at each step before computing the next day. This is a computational shortcut. The professor notes that you could also sum the values (like filtering), normalize, and then pick max values at the end — you would get the same answer. But the elimination approach is more efficient because there is no point in carrying forward a path that will never be the maximum.

Intuition + Analogy: Think of Viterbi like a tournament. At each day, each state (L or H) has two "contenders" coming from the previous day. We keep only the strongest contender (highest probability) and eliminate the weaker one. By the end, we have a single champion path that is the most likely sequence.

15.5.5 Summary Table: Forward Propagation vs Filtering vs Viterbi

Algorithm	Query Type	Normalization	Final Step
Forward Propagation	Probability of evidence sequence	Optional (if done, must do in ALL steps)	ADD the two final node values
Filtering	Hidden variable on last day	Mandatory at every step	COMPARE the two final nodes, pick MAX
Viterbi	Most likely sequence of hidden variables	Optional at first step; at each intermediate step, pick MAX instead of summing	COMPARE each day's L vs H, pick MAX for each day

Algorithm Selection Guide:

Forward Propagation: "What is the probability of seeing this sequence?"
Filtering: "What is the hidden state on the last day?"
Viterbi: "What is the most likely hidden state sequence for all days?"

Recap + Bridge: Viterbi finds the most likely hidden state sequence by maximizing at each step instead of summing. It's like forward propagation with a "winner-take-all" strategy. The elimination trick makes it efficient by pruning weak paths early. This completes the three core HMM algorithms. The next section applies these to a complete word problem.

15.6 Student Behavioral Analysis: Complete Word Problem

15.6.1 Problem Statement

Hook: A professor wants to analyze student behavior over three semesters. The observed grades are bad, good, bad (BGB). What was the most likely sequence of concentration levels (low or high) for each semester? This is a classic HMM word problem that tests your ability to extract TPM, EPM, and initial probabilities from text.

The problem describes a learning analytics scenario:

Low concentration leads to low grades 80% of the time
High concentration leads to good grades 95% of the time
60% of the time, students with low concentration realize the problem and decide to concentrate more for upcoming exams
30% of the time, students who are already concentrated remain concentrated (proactively prepared)
At course enrollment, 90% of students are willing to concentrate more

An agent must perform learner behavioral analysis. The observed evidence (grades) is given as BGB (bad, good, bad). Find the most likely explanation of student behavior.

Problem Type: This is a Viterbi query because it asks for "the most likely explanation of student behavior" — meaning the sequence of hidden states (concentration levels) for each semester, not just the probability or the last semester's state.

15.6.2 Building the Emission Probability Matrix (EPM)

The evidence is grades: bad or good. The hidden variable is concentration level: low concentration (LC) or high concentration (HC).

From the problem statement:

"Low concentration leads to low grades in 80% of time" → $P (bad ∣ L C) = 0.8$
"High concentration produces good grades in 95% of time" → $P (good ∣ H C) = 0.95$

Each column must sum to 1:

$P (good ∣ L C) = 1 - 0.8 = 0.2$
$P (bad ∣ H C) = 1 - 0.95 = 0.05$

Emission Probability Matrix (EPM): $B = [P (bad ∣ L C) P (good ∣ L C) P (bad ∣ H C) P (good ∣ H C)] = [0.8 0.2 0.05 0.95]$ Rows represent observations (bad, good), columns represent hidden states (LC, HC). Each column sums to 1.

	LC	HC
Bad grade	0.8	0.05
Good grade	0.2	0.95

Pitfall: A common mistake is to confuse rows and columns. The EPM should have observations as rows and hidden states as columns. Each column must sum to 1 because given a hidden state, the probabilities of all possible observations must sum to 1.

15.6.3 Building the Transition Probability Matrix (TPM)

The hidden variable transitions describe concentration changes over semesters:

"60% of the time, students with low concentration decide to concentrate more" → $P (H C ∣ L C) = 0.6$
Therefore $P (L C ∣ L C) = 1 - 0.6 = 0.4$
"30% of the time, students are always prudent and proactively prepared with concentration" → $P (H C ∣ H C) = 0.3$
Therefore $P (L C ∣ H C) = 1 - 0.3 = 0.7$

Transition Probability Matrix (TPM): $A = [P (L C ∣ L C) P (H C ∣ L C) P (L C ∣ H C) P (H C ∣ H C)] = [0.4 0.6 0.7 0.3]$ Rows represent current state, columns represent next state. Each row sums to 1.

	LC (t-1)	HC (t-1)
LC (t)	0.4	0.7
HC (t)	0.6	0.3

Pitfall: The TPM is often confused with the EPM. The TPM describes transitions between hidden states (concentration changes), while the EPM describes how hidden states produce observations (concentration affects grades). Read the problem carefully to distinguish what is observable (grades) from what is hidden (concentration).

15.6.4 Initial Probability

"At the start of the course enrollment, 90% of students are willing to concentrate" → $P (H C)_{initial} = 0.9$ , $P (L C)_{initial} = 0.1$ .

Initial Probability Distribution: $π = [P (L C) P (H C)] = [0.1 0.9]$

Q: Should we use 0.5/0.5 as initial probabilities if not specified? A: When initial probabilities are given in the problem, you must use the given values. The 0.5/0.5 default only applies when no initial distribution is stated. Some students incorrectly use 0.5/0.5 and get zero marks because they ignored the given initial distribution.

15.6.5 Solving with Viterbi's Algorithm

The evidence is BGB (bad, good, bad) — three semesters. The question asks for "the most likely explanation of student behavior," which is a Viterbi query because it requests the sequence of hidden variables (concentrated or not for each semester), not just a probability or a single day's state.

Step-by-Step Viterbi Solution:

Day 1 (Bad grade):

For LC: $v_{1} (L C) = π (L C) \times P (bad ∣ L C) = 0.1 \times 0.8 = 0.08$
For HC: $v_{1} (H C) = π (H C) \times P (bad ∣ H C) = 0.9 \times 0.05 = 0.045$
Normalize (optional): LC = 0.08/0.125 = 0.64, HC = 0.045/0.125 = 0.36
Day 1 winner: LC (0.08 > 0.045)

Day 2 (Good grade):

For LC:
From LC: $0.08 \times 0.4 \times 0.2 = 0.0064$
From HC: $0.045 \times 0.7 \times 0.2 = 0.0063$
Max: 0.0064 (came from LC)
For HC:
From LC: $0.08 \times 0.6 \times 0.95 = 0.0456$
From HC: $0.045 \times 0.3 \times 0.95 = 0.012825$
Max: 0.0456 (came from LC)
Day 2 winner: HC (0.0456 > 0.0064)

Day 3 (Bad grade):

For LC:
From LC: $0.0064 \times 0.4 \times 0.8 = 0.002048$
From HC: $0.0456 \times 0.7 \times 0.8 = 0.025536$
Max: 0.025536 (came from HC)
For HC:
From LC: $0.0064 \times 0.6 \times 0.05 = 0.000192$
From HC: $0.0456 \times 0.3 \times 0.05 = 0.000684$
Max: 0.000684 (came from HC)
Day 3 winner: LC (0.025536 > 0.000684)

Backtracking:

Day 3: LC (came from HC on day 2)
Day 2: HC (came from LC on day 1)
Day 1: LC

Most likely sequence: LC → HC → LC

Interpretation: The most likely explanation is that the student started with low concentration (LC), improved to high concentration (HC) in the second semester, but then dropped back to low concentration (LC) in the third semester. This matches the observed grades: bad (low concentration), good (high concentration), bad (low concentration).

Key exam guidance: "Creating TPM and EPM is 60% of the problem from word." If you get the TPM and EPM wrong, all subsequent computations use wrong data and receive zero marks. Reading the question carefully and correctly constructing the matrices is the most critical step.

Recap + Bridge: This complete word problem demonstrates the entire process: extracting TPM, EPM, and initial probabilities from text, identifying the query type (Viterbi), and solving step-by-step. The key is careful matrix construction and correct algorithm application. The next sections shift to multi-agent decision making, which uses different concepts but similar strategic thinking.

15.7 Multi-Agent Decision Making: Introduction

15.7.1 Why Multi-Agent Systems Matter

Hook: Most real-world AI problems involve multiple agents interacting. A self-driving car must predict what other drivers will do. A team of robots must coordinate to complete a task. A cybersecurity system must defend against multiple intelligent adversaries. Multi-agent decision making is where AI meets the real world.

AI is no longer limited to solving problems in isolation. Most real-world applications involve multiple agents interacting. Modern examples include agent-based software engineering systems where multiple LLM-powered agents (coding agent, testing agent, reviewer agent) work in tandem to create software.

Real-world: In industry, systems like "Agent TKI" involve multiple tool-calling agents powered by LLMs working together — one for coding, one for testing, one for reviewing. This is a multi-agent system, and it is the reality of most industry applications today.

Other multi-agent domains:

Autonomous driving — multiple autonomous and human-driven vehicles sharing the road
Robot soccer — multiple robotic players coordinating
Cybersecurity — defending against multiple intelligent adversaries
Chess and board games — classic adversarial multi-agent scenarios
Online marketplaces — buyers and sellers negotiating prices
Climate agreements — multiple nations cooperating on emissions

The connection to earlier modules: game playing (adversarial search) from the earlier part of the course was already a multi-agent concept. The minimax algorithm from Section 6.3 is a game-theoretic algorithm for two-player zero-sum games.

Intuition + Analogy: Think of multi-agent systems like a team sport. Each player (agent) has their own goals and strategies, but the outcome depends on everyone's actions. A soccer player must predict what opponents will do, coordinate with teammates, and choose the best action given what everyone else might do. That's multi-agent decision making.

15.7.2 Game Theory: Definition and Purpose

Game theory is the mathematical study of strategic decision making among multiple rational agents whose outcomes depend on the actions chosen by all participants. Unlike optimization problems with a single decision maker, game theory considers situations where every player's decision affects every other player's outcome.

Formal Definition: Game theory is the study of strategic interactions where the outcome for each participant depends on the actions of all. It provides mathematical tools for analyzing situations where agents must make decisions that affect each other.

Game theory helps AI agents answer three fundamental questions:

What should I do?
What will my opponent do?
What is the best possible response?

These three questions are the crux of any multi-agent decision system.

Real-world: In autonomous driving, if another car brakes suddenly, what should you do? Your decision depends on predicting their next move and finding your best response — all three questions in action.

Game Theory in AI: Game theory serves two main purposes in AI:

Agent design: Using game theory to compute the best strategy for an agent given that other agents are rational.
Mechanism design: Designing the rules of the game so that when each agent maximizes its own utility, the collective good is maximized.

15.7.3 Elements of a Game

Every game has these components:

Players — the agents (companies, robots, humans, software agents). Denoted $N = {1, 2, \dots, n}$ .
Actions — available moves (move left, raise, fold, attack, defend). For player $i$ , the set of actions is $A_{i}$ .
Strategies — the plan describing what a player does in each situation. A pure strategy is a deterministic choice; a mixed strategy is a probability distribution over actions.
Payoffs (utilities) — the reward for outcomes (winning, profit, utility value). For player $i$ , the payoff function is $u_{i} : A_{1} \times A_{2} \times \dots \times A_{n} \to R$ .
Information — what players know about the game state (complete, partial, or imperfect). Complete information means all players know the game structure; perfect information means all players observe all moves.

Game Representation: A game can be represented in two main forms:

Normal form (strategic form): A payoff matrix showing utilities for each combination of actions. Used for simultaneous games.
Extensive form: A game tree showing the sequence of moves, information sets, and payoffs. Used for sequential games.

Key insight: Two players can choose the same action but receive different payoffs, because payoffs depend on the combination of actions chosen by all players. Example: two companies both raising prices might yield different profits depending on the magnitude of each raise.

Important distinction: A rational agent is not the same as a selfish agent. A rational player selects actions that maximize their own benefit, but this may include cooperation if cooperation yields a higher profit for both. Rational does not mean selfish — sometimes a rational player cooperates when the cooperative outcome is better for everyone.

Pitfall: Assuming rationality means selfishness. In game theory, rational agents maximize their own payoff, which may involve cooperation if cooperation yields higher payoffs. Rational agents can cooperate, compete, or mix strategies depending on the game structure.

Recap + Bridge: Multi-agent systems involve multiple agents interacting strategically. Game theory provides the mathematical framework for analyzing such interactions. The three fundamental questions (what should I do, what will opponents do, what's the best response) guide agent design. The next sections explore different types of games and strategies.

15.8 Types of Games

15.8.1 Zero-Sum vs Non-Zero-Sum Games

Hook: In chess, if I win, you lose. In a business partnership, we can both win. The structure of payoffs determines the type of game and the strategies that make sense.

In a zero-sum game, one player's gain is exactly the other player's loss. The total payoff across all players is constant. Mathematically, for two players: $u_{1} (a_{1}, a_{2}) + u_{2} (a_{1}, a_{2}) = c for all a_{1} \in A_{1}, a_{2} \in A_{2}$ where $c$ is a constant (often normalized to 0).

Examples of zero-sum games: chess, tic-tac-toe, checkers, poker (if we consider only the money exchanged).

In a non-zero-sum game, both players can win, both can lose, or outcomes can be mixed. The total payoff is not fixed.

Examples of non-zero-sum games: trade negotiations, climate agreements, traffic management, business partnerships.

Zero-Sum vs Non-Zero-Sum:

Zero-sum: One player's gain = another player's loss. Total payoff constant.
Non-zero-sum: Both can win, both can lose, or mixed outcomes. Total payoff varies.

Example: Consider two companies deciding whether to advertise:

Both advertise: each gets 5 units of profit
Neither advertises: each gets 8 units
One advertises, other doesn't: advertiser gets 10, non-advertiser gets 2

Total payoff varies: 10, 16, 12, 12. This is non-zero-sum.

15.8.2 Cooperative vs Non-Cooperative Games

In cooperative games, players work together toward shared goals. Examples: team sports (cricket, football), multi-robot coordination.

In non-cooperative games, players act independently, each pursuing their own interests. Examples: chess, poker.

Cooperative vs Non-Cooperative:

Cooperative: Players can form binding agreements and coordinate strategies.
Non-cooperative: Players cannot make binding agreements; each acts independently.

Exam note: Poker is non-cooperative with imperfect information — players do not know each other's cards.

Are all zero-sum games non-cooperative? Generally yes, because in zero-sum games, one player's gain is another's loss, so cooperation doesn't help. But there can be exceptions (e.g., team-based zero-sum games).

Pitfall: Confusing "non-cooperative" with "competitive." Non-cooperative simply means no binding agreements are possible; players may still choose to cooperate if it's in their self-interest.

15.8.3 Game Representations

Several representation formalisms exist:

Game tree: A tree structure showing all possible states and moves. This was already encountered in the adversarial search / minimax module. Each node represents a game state, edges represent moves, and leaves represent outcomes with payoffs.

Payoff matrix: A table showing utilities for each combination of player actions. Example: if Player A chooses A1 or A2, and Player B chooses B1 or B2, the matrix shows the resulting payoff for each combination.

Payoff Matrix Example: | | B1 | B2 | |---|---|---| | A1 | (3, 2) | (1, 1) | | A2 | (0, 3) | (2, 2) | Where (x, y) means Player A gets x, Player B gets y.

Extensive form: An advanced version of the game tree that includes:

Decision nodes — where a player makes a choice
Chance nodes — where outcomes depend on random events (rolling a die, drawing a card)

If a node depends on drawing a heart vs spade, the path taken depends on chance — this is captured in the extensive form.

Finite state machines: States represent game positions; transitions represent moves. Useful for repeated games like the prisoner's dilemma.

Representation Selection:

Normal form (payoff matrix): For simultaneous games where players move at the same time.
Extensive form (game tree): For sequential games where players move one after another.
Finite state machines: For repeated games where history matters.

Recap + Bridge: Games can be classified along two main dimensions: zero-sum vs non-zero-sum (payoff structure) and cooperative vs non-cooperative (agreement possibilities). Different game types require different solution concepts. The next section introduces the Prisoner's Dilemma, a classic non-zero-sum non-cooperative game that illustrates Nash equilibrium.

15.9 Prisoner's Dilemma and Nash Equilibrium

15.9.1 The Prisoner's Dilemma

Hook: Two criminals are arrested and held in separate rooms. Each can either stay silent or confess. If both stay silent, they each get 1 year. If one confesses and the other stays silent, the confessor goes free and the silent one gets 15 years. If both confess, they each get 10 years. What should they do? This is the Prisoner's Dilemma, a foundational example in game theory.

Two suspects (Alan and Ben) are arrested for the same crime and held in separate rooms. Each can either stay silent or confess.

The payoff matrix (in years of jail):

	Ben Silent	Ben Confesses
Alan Silent	Alan: 1, Ben: 1	Alan: 15, Ben: 0
Alan Confesses	Alan: 0, Ben: 15	Alan: 10, Ben: 10

Payoff Matrix Interpretation:

(Alan Silent, Ben Silent): Both get 1 year — cooperative outcome
(Alan Confesses, Ben Silent): Alan goes free, Ben gets 15 years — temptation to betray
(Alan Silent, Ben Confesses): Alan gets 15 years, Ben goes free — sucker's payoff
(Alan Confesses, Ben Confesses): Both get 10 years — Nash equilibrium

15.9.2 The Dilemma Logic

Alan's reasoning:

If Ben confesses: Alan gets 10 years (by confessing) vs 15 years (by staying silent) → confess is better
If Ben stays silent: Alan gets 0 years (by confessing) vs 1 year (by staying silent) → confess is better

Regardless of what Ben does, confessing is Alan's best strategy. The same logic applies to Ben. So both confess, and both get 10 years.

But if both had stayed silent, they would each get only 1 year. This is the dilemma: individual rationality leads to a collectively suboptimal outcome.

Dominant Strategy: A strategy is dominant if it is the best choice regardless of what other players do. In the Prisoner's Dilemma, confessing is a dominant strategy for both players.

Worked Example:

Alan's perspective:
If Ben stays silent: Confess → 0 years, Silent → 1 year. Confess is better.
If Ben confesses: Confess → 10 years, Silent → 15 years. Confess is better.
Confess is dominant for Alan.
Ben's perspective: Symmetric reasoning → Confess is dominant for Ben.
Outcome: Both confess → (10, 10)
Pareto optimal: Both silent → (1, 1) — better for both, but not stable.

15.9.3 Nash Equilibrium

The Nash equilibrium is the "no regret" solution for any game. It is not necessarily optimal, but it ensures no player gets the worst outcome. After reaching Nash equilibrium, no player can improve their outcome by unilaterally changing their strategy.

Nash Equilibrium Definition: A set of strategies $(s_{1}^{*}, s_{2}^{*}, \dots, s_{n}^{*})$ is a Nash equilibrium if for every player $i$ : $u_{i} (s_{i}^{*}, s_{- i}^{*}) \geq u_{i} (s_{i}, s_{- i}^{*}) for all s_{i} \in A_{i}$ where $s_{- i}^{*}$ denotes the strategies of all players except $i$ . No player can improve their payoff by changing only their own strategy.

Connection to minimax: The minimax algorithm never promised the best outcome, but it promised you would never reach the worst outcome. That guarantee is essentially Nash equilibrium applied to adversarial search.

The Nash equilibrium for the prisoner's dilemma is (confess, confess) with (10, 10) — both players confess. Neither can improve by switching to silence (they would get 15 years instead).

Pitfall: Nash equilibrium is not necessarily the best outcome for all players. In the Prisoner's Dilemma, (confess, confess) is a Nash equilibrium, but (silent, silent) would be better for both. However, (silent, silent) is not stable because each player has an incentive to deviate.

15.9.4 Trust and Game Theory

The prisoner's dilemma illustrates the fundamental challenge of trust in multi-agent systems. After both get 10 years, they walk toward jail discussing what could have been:

"If we had collaborated, we'd each get 1 year."
"But if I had stayed silent, you would have betrayed me — I'd get 15 years. At least now I'm only getting 10."

This tension — whom to trust, when to cooperate, when to compete — is the core of game theory and multi-agent decision making.

Intuition + Analogy: The Prisoner's Dilemma is like two companies deciding whether to undercut each other's prices. If both keep prices high, both profit. If one undercuts, they steal market share. If both undercut, both make less profit. The rational choice (undercut) leads to a worse outcome for both — just like both prisoners confessing.

Key Concepts from Prisoner's Dilemma:

Dominant strategy: Best choice regardless of opponent's action
Nash equilibrium: No player can improve by unilaterally changing strategy
Pareto optimal: No player can be made better off without making another worse off
Dilemma: Individual rationality can lead to collective suboptimality

Recap + Bridge: The Prisoner's Dilemma shows how individual rationality can lead to collectively suboptimal outcomes. Nash equilibrium is the "no regret" solution where no player can improve by changing only their own strategy. The next section explores a concrete game example (Mora) to illustrate these concepts.

15.10 The Mora Game Example

15.10.1 Game Description

Hook: Mora is a hand game where two players simultaneously show fingers and shout numbers. It's a simple game that illustrates key game theory concepts: non-zero-sum payoffs, no cooperation, and the weakness of pure strategies.

Mora is a hand game (described as a Russian game). In "five-finger Mora," two players simultaneously show some number of fingers on one hand while shouting out a number. If the number you shout equals the sum of fingers both players show, you win.

Example: If you shout "7" and you show 2 fingers while your opponent shows 5, then 2+5=7 and you win. But if you shouted "8," you lose.

Game Structure:

Players: Two
Actions: Show 1-5 fingers, shout a number (typically 2-10)
Simultaneous: Both act at the same time
Payoff: Win if your shouted number equals the sum of both fingers shown

15.10.2 Why Mora Illustrates Game Theory Concepts

With a two-finger variant (each player shows 1 or 2 fingers), the possible sums are 2, 3, or 4. Each player simultaneously calls out a number and shows fingers.

Two-Finger Mora Payoff Matrix: Let's denote actions as (fingers shown, number called). Possible actions: (1,2), (1,3), (2,3), (2,4).

If Player A chooses (1,2) and Player B chooses (1,2): Sum = 1+1=2, both called 2, both win. If Player A chooses (1,2) and Player B chooses (2,3): Sum = 1+2=3, Player B called 3, B wins.

Non-zero-sum: If both players call "2" and both show 1 finger, both win. Two players can win simultaneously. This is non-zero-sum because the total payoff is not constant.

No cooperation possible: Since both act simultaneously and independently, there is no way to coordinate. This makes it a non-cooperative game.

Pure strategy weakness: If you always call "2" with 1 finger, your opponent can predict and exploit this. Similarly, in hand cricket, if you always play 6, the opponent catches on.

Pitfall: Using a pure strategy (always the same action) makes you predictable. Your opponent can observe your pattern and exploit it. This is why mixed strategies (randomizing actions) are important.

15.10.3 Connection to Real Games

The Mora example illustrates how predicting an opponent's fixed strategy creates vulnerability. This connects to the goalkeeper analogy: a goalkeeper who always dives left can be exploited by a striker who always shoots right.

Intuition + Analogy: Mora is like rock-paper-scissors: if you always throw rock, your opponent will always throw paper. The solution is to randomize your choices so your opponent can't predict you. This is the essence of mixed strategies.

Lessons from Mora:

Non-zero-sum: Both players can win (or lose) simultaneously.
Non-cooperative: No coordination possible.
Pure strategies are exploitable: Fixed patterns can be predicted and countered.
Mixed strategies needed: Randomization prevents exploitation.

Recap + Bridge: Mora illustrates key game theory concepts: non-zero-sum payoffs, non-cooperative structure, and the weakness of pure strategies. The next section formalizes pure vs mixed strategies and shows how mixed strategies introduce unpredictability.

15.11 Pure Strategy vs Mixed Strategy

15.11.1 Pure Strategy

Hook: If you always play rock in rock-paper-scissors, your opponent will always play paper. Pure strategies are predictable. Mixed strategies introduce randomness to prevent exploitation.

A pure strategy assumes every player always chooses one specific action. The problem: the opponent can observe patterns and exploit them. Pure strategies are not always optimal because they become predictable.

Real-world analogy: A goalkeeper who always dives left. After observing this pattern, the striker will always shoot right, rendering the goalkeeper's strategy ineffective.

Pure Strategy: A deterministic choice of action. Player $i$ 's pure strategy is a single action $a_{i} \in A_{i}$ . The weakness: predictable and exploitable.

Pitfall: Using a pure strategy in repeated games makes you predictable. Your opponent can learn your pattern and always counter it. This is why mixed strategies are essential in many games.

15.11.2 Mixed Strategy

A mixed strategy is a probability distribution over multiple pure strategies. Instead of always choosing action A, a player might choose A with 70% probability and B with 30% probability.

Formally: if a player has two actions, rather than always choosing action 1, the player assigns probability $p$ to action 1 and $1 - p$ to action 2. This introduces unpredictability.

Mixed Strategy: A probability distribution over pure strategies. Player $i$ 's mixed strategy is $σ_{i} = (p_{1}, p_{2}, \dots, p_{∣ A_{i} ∣})$ where $p_{k} \geq 0$ and $\sum_{k} p_{k} = 1$ .

For the Mora example: with probability $p$ , show one finger; with probability $1 - p$ , show two fingers. The opponent cannot reliably predict your move.

Worked Example (Goalkeeper):

Pure strategy: Always dive left → Striker always shoots right → Goalkeeper fails.
Mixed strategy: Dive left with 60% probability, right with 40% → Striker can't predict → Goalkeeper has better chance.
Optimal mixed strategy: Find $p$ that makes the striker indifferent between shooting left or right.

Intuition + Analogy: Mixed strategies are like rolling dice before each move. Instead of always doing the same thing, you randomize so your opponent can't predict you. The art is choosing the right probabilities so that your opponent has no profitable counter-strategy.

15.11.3 Parameterized Games

In parameterized games, the fixed probabilities in the game tree are replaced with unknown variables (like $p$ and $q$ ). These unknowns can later be solved for actual probability values. This is a way to analyze games symbolically before committing to specific mixed strategies.

Parameterized Games: Replace fixed probabilities with variables to analyze games symbolically. Solve for optimal mixed strategies by finding values that make opponents indifferent.

Finding Optimal Mixed Strategy: To find the optimal mixed strategy, use the indifference principle: choose probabilities that make your opponent indifferent between their actions. If your opponent is indifferent, they have no profitable deviation, which is a Nash equilibrium.

Recap + Bridge: Pure strategies are predictable and exploitable. Mixed strategies introduce randomness to prevent exploitation. The optimal mixed strategy often makes the opponent indifferent between their actions. The next section explores how strategies evolve in repeated games.

15.12 Game Strategies in Repeated Games

15.12.1 One-Shot vs Repeated Games

Hook: In a one-shot game, you play once and it's over. In a repeated game, you play many times, and your past actions affect future interactions. Repeated games allow for strategies that build trust, punish defection, and reward cooperation.

A one-shot game is played once and is over. A repeated game is played multiple times, with history influencing future decisions. In repeated games, past actions matter — players remember what happened before.

One-Shot vs Repeated:

One-shot: Single interaction, no history, no future consequences.
Repeated: Multiple interactions, history matters, reputation effects.

Real-world: Online marketplaces involve repeated interactions. A seller's reputation from past transactions influences future buyer behavior. Memory of past actions is essential.

Intuition + Analogy: One-shot games are like a single interview: you put your best foot forward and it's over. Repeated games are like a long-term relationship: your past actions build trust or distrust, and future interactions depend on that history.

15.12.2 Strategy Types for Repeated Games

When designing agents for repeated interactions, several strategies are available:

Strategy Types:

Hawk: Always aggressive, never cooperate. Good for adversarial roles.
Dove: Always cooperative, seek mutual benefit. Good for collaborative roles.
Grim: Cooperate until opponent defects, then never cooperate again.
Tit-for-tat: Start cooperating, then mirror opponent's previous action.
Tit-for-tat (reversed): Variation with different retaliation patterns.

Hawk strategy: The player is always aggressive — attacking, looking for flaws, never compromising. A reviewer agent in software engineering would use a hawk strategy: relentlessly finding bugs in code without softening criticism.

Dove strategy: The player prefers cooperation, avoids unnecessary conflict, and seeks mutual benefit. A testing agent might use a dove strategy — if one agent finds one bug, another finds a different bug, distributing effort cooperatively.

Grim strategy: Start cooperating, but if the opponent ever defects, switch to permanent retaliation. This is a "forgiving but not forgetful" strategy — it punishes defection severely but is otherwise cooperative.

Tit-for-tat: Start cooperating, then mirror whatever the opponent did in the previous round. If they cooperated, you cooperate next time. If they defected, you defect next time. This strategy is simple, forgiving, and retaliatory.

Tit-for-tat (reversed): A variation where the retaliation and cooperation patterns differ from standard tit-for-tat.

Tit-for-tat Example:

Round 1: Cooperate (start nice)
Round 2: Opponent defects → You defect
Round 3: Opponent cooperates → You cooperate
Round 4: Opponent defects → You defect
Pattern: Mirror opponent's previous action

Real-world agent design: When building multi-agent systems, each agent's strategy is like a persona. A technical architect reviewing code should be hawk-like (attack mode, finding flaws). A testing agent could be dove-like (cooperative, distributed effort). The choice of strategy depends on the agent's role and the system's goals.

Pitfall: Choosing the wrong strategy for the role. A hawk strategy in a collaborative team leads to conflict. A dove strategy in an adversarial setting leads to exploitation. Match the strategy to the game structure and agent role.

Strategy Selection Guide:

Adversarial roles (reviewer, auditor): Hawk strategy
Collaborative roles (team member, partner): Dove strategy
Repeated interactions with trust: Tit-for-tat
High-stakes, no second chances: Grim strategy

Exam note: Expect short questions (1-2 marks) like: "If there is a reviewer agent, should it use hawk or dove strategy?" or "Given a use case, what type of game is it — cooperative or non-cooperative, zero-sum or non-zero-sum?"

Recap + Bridge: Repeated games allow for strategies that build trust and punish defection. Hawk, dove, grim, and tit-for-tat are common strategies, each suited to different roles and game structures. The choice of strategy depends on whether the game is cooperative or adversarial, one-shot or repeated. This completes the game theory portion of the lecture. The next sections provide exam guidance and industry applications.

15.13 Exam Guidance Summary

15.13.1 HMM Algorithms (Core Exam Content)

Exam note: Three algorithms are exam-relevant: Forward Propagation, Filtering, and Viterbi's Algorithm. Prediction and smoothing are NOT exam topics, but understanding what they mean is expected.

Forward propagation: Given evidence sequence, compute its probability. Normalize optionally (if done, do it everywhere). Final step: ADD the two terminal node values
Filtering: Given evidence, find hidden variable on last day. Normalize MANDATORY at every step. Final step: COMPARE and pick MAX
Viterbi: Given evidence, find most likely hidden variable sequence. At each step, pick MAX instead of summing (eliminate weaker path). Final: compare each day's values, pick max

Algorithm Quick Reference: | Algorithm | Question | Normalization | Final Step | |-----------|----------|---------------|------------| | Forward Propagation | Probability of sequence | Optional | ADD | | Filtering | Hidden state last day | Mandatory | COMPARE | | Viterbi | Most likely sequence | Optional | COMPARE each day |

15.13.2 TPM and EPM Construction

Exam note: "Creating TPM and EPM is 60% of the problem from word." If matrices are wrong, all subsequent work receives zero marks.

Each column in EPM must sum to 1
Read the problem carefully to distinguish what is observable (goes to EPM) vs unobservable (goes to TPM)
TPM: transitions between hidden states (rows sum to 1)
EPM: observations given hidden states (columns sum to 1)

15.13.3 Initial Probabilities

Exam note: When initial probabilities are given, USE THEM (do not default to 0.5/0.5). The 0.5/0.5 default only applies when nothing is specified.

The 90% initial willingness to concentrate means $P (H C) = 0.9$ , $P (L C) = 0.1$

15.13.4 Normalization Rules

Normalization Rules:

If you normalize at any step, normalize at ALL steps
If you skip normalization, skip it at ALL steps
Partial normalization is never acceptable
For forward propagation: normalization is optional
For filtering: normalization is mandatory

15.13.5 Multi-Agent and Game Theory (Theory Content)

Exam note: Game theory questions will be short (1-2 marks): identify game type, strategy type, or relate to a use case.

Know the difference between cooperative and non-cooperative games
Know zero-sum vs non-zero-sum games
Understand hawk, dove, grim, and tit-for-tat strategies
Be able to identify which strategy suits which agent role
Prisoner's dilemma illustrates Nash equilibrium — not necessarily on the exam, but demonstrates the concept
Mixed strategy introduces probability to avoid predictability

15.13.6 Exam Logistics

Exam Logistics:

EC3 (final exam) covers all 16 sessions — the complete course
90% of marks come from post-mid-semester topics; 10% from pre-mid-semester
Open book with the recommended textbook (Russell & Norvig) in original book form only — no printouts, no spiral-bound copies
The professor will upload watermark PPTs and a formula summary slide after the final class
Prepare as if it is a closed-book exam; the open-book option is a bonus for topics you are unsure about
The recommended textbook (Russell & Norvig) is available as an Indian/eastern economy edition for approximately 600-800 rupees

15.13.7 Problem-Solving Advice

Problem-Solving Guide:

For word problems: carefully extract TPM, EPM, and initial probabilities from the text before solving
"The moment you talk about 'most likely explanation,' it is Viterbi"
If only the last day's hidden variable is asked, it is filtering
If the probability of an evidence sequence is asked, it is forward propagation

15.14 Key Industry Applications

15.14.1 HMM Applications in Industry

Real-World Connection: HMMs are not just theoretical constructs — they power many everyday technologies. From autocorrect on your phone to speech recognition in virtual assistants, HMMs are the hidden engines behind many AI applications.

HMMs in NLP: Grammarly, word prediction tools, machine translation, and speech recognition all use HMM principles. These systems model language as a sequence of hidden states (words, parts of speech) that produce observations (characters, sounds).
Agent-based software engineering: Multi-agent systems with coding, testing, and reviewing agents working in tandem — powered by LLMs and tool calling. This is the reality of modern software development, where multiple AI agents collaborate to create, test, and review code.
Autonomous driving: Multi-agent decision making where multiple vehicles (human or autonomous) must coordinate and predict each other's actions. Game theory helps autonomous vehicles anticipate what other drivers will do and choose safe, efficient responses.

15.14.2 Game Theory Applications in Industry

Real-World Connection: Game theory is not just for board games — it underpins many real-world systems where multiple agents interact strategically. From cybersecurity to online marketplaces, game theory provides the mathematical foundation for strategic decision making.

Cybersecurity: Adversarial game theory for defense against intelligent threats. Security systems must anticipate what attackers will do and choose optimal defense strategies.
Online marketplaces: Repeated games where seller reputation and past interactions influence current decisions. Platforms like eBay and Amazon use reputation systems that are essentially repeated game mechanisms.
Robotics: Multi-robot coordination (cooperative games) for tasks like robot soccer, warehouse automation, and search-and-rescue operations.
Logic-based AI in modern systems: Even with LLMs and frontier models, propositional and predicate logic remain viable for building small, domain-specific knowledge systems within organizations. Logic-based systems provide explainability and reliability that pure machine learning approaches may lack.

Industry Applications Summary:

HMMs: NLP, speech recognition, bioinformatics, autonomous systems
Game Theory: Cybersecurity, marketplaces, robotics, multi-agent coordination
Logic-based AI: Domain-specific knowledge systems, explainable AI

ACI Lecture 15 notes · Hidden Markov Model Algorithms and Multi-Agent Decision Making

Artificial Computational Intelligence· postgraduate· 2026-08-16

Sections Breakdown

1Course Context and Module Overview

Comprehensive recap of the entire AI course structure, showing how Module 6 (temporal reasoning and multi-agent decision making) builds on previous modules covering search, logic, and probabilistic reasoning.

2Hidden Markov Models: Foundation and Five Query Types

Introduces the Markov property, defines HMMs with TPM and EPM, and explains the five types of HMM queries: forward propagation, filtering, prediction, smoothing, and Viterbi.

3Forward Propagation Algorithm: Detailed Worked Example

Detailed worked example of forward propagation for computing the probability of an observed sequence (SSR) using a trellis diagram, with step-by-step computations for each day.

4Filtering Algorithm

Filtering computes the most likely hidden state on the last day given all evidence up to that day. Uses forward propagation with mandatory normalization at every step and final comparison instead of addition.

5Viterbi's Algorithm (Most Likely Explanation)

Viterbi finds the most likely sequence of hidden states for all days by maximizing at each step instead of summing, using a pruning strategy to eliminate weak paths.

6Student Behavioral Analysis: Complete Word Problem

Complete word problem demonstrating extraction of TPM, EPM, and initial probabilities from text, then solving with Viterbi to find most likely concentration sequence (LC→HC→LC).

7Multi-Agent Decision Making: Introduction

Introduces multi-agent systems and game theory as the mathematical study of strategic decision making among multiple rational agents. Covers the three fundamental questions and elements of a game.

8Types of Games

Classifies games along two dimensions: zero-sum vs non-zero-sum (payoff structure) and cooperative vs non-cooperative (agreement possibilities). Covers game representations: payoff matrix, game tree, extensive form.

9Prisoner's Dilemma and Nash Equilibrium

Prisoner's Dilemma illustrates how individual rationality leads to collective suboptimality. Nash equilibrium is the 'no regret' solution where no player can improve by unilaterally changing strategy.

10The Mora Game Example

Mora is a hand game illustrating non-zero-sum payoffs, non-cooperative structure, and the weakness of pure strategies. Shows why mixed strategies are needed.

11Pure Strategy vs Mixed Strategy

Pure strategies are predictable and exploitable. Mixed strategies are probability distributions over actions that introduce unpredictability. Parameterized games use variables to find optimal mixed strategies.

12Game Strategies in Repeated Games

Repeated games allow strategies that build trust and punish defection. Hawk (aggressive), dove (cooperative), grim (punish forever), tit-for-tat (mirror) strategies suited to different roles.

13Exam Guidance Summary

Exam guidance covering HMM algorithms, TPM/EPM construction, normalization rules, game theory concepts, exam logistics, and problem-solving advice.

14Key Industry Applications

Industry applications of HMMs (NLP, speech recognition, autonomous driving) and game theory (cybersecurity, marketplaces, robotics, logic-based AI).

Postgraduate students in Artificial Intelligence and Computational Intelligence

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Course Context and Module Overview

Must-know: Module 6 covers temporal reasoning (HMMs) and multi-agent decision making, building on Bayesian networks from Module 5.

⚠️ Top pitfall: Confusing the progression: search → logic → probability → temporal/multi-agent.

Self-check: What module precedes temporal reasoning in the course structure?

Connects to: 15.2

Hidden Markov Models: Foundation and Five Query Types

Must-know: Five HMM query types: forward propagation (probability of evidence), filtering (current hidden state), prediction (future state), smoothing (past state), Viterbi (most likely sequence). Only filtering and Viterbi are exam-relevant.

$P (X_{t} ∣ X_{0 : t - 1}) = P (X_{t} ∣ X_{t - 1})$

⚠️ Top pitfall: Confusing filtering with Viterbi: filtering gives hidden state on last day, Viterbi gives most likely sequence for all days.

Self-check: What is the difference between filtering and Viterbi?

Connects to: 15.3, 15.4, 15.5

Forward Propagation Algorithm: Detailed Worked Example

Must-know: Forward propagation computes probability of evidence sequence by summing over all hidden state paths. Normalization is optional (if done, must do at every step). Final step: ADD terminal node values.

$f_{t} (j) = [i = 1 \sum N f_{t - 1} (i) \times A_{ij}] \times B_{j} (e_{t})$

⚠️ Top pitfall: Comparing final values instead of adding them. Forgetting that normalization is optional.

Self-check: What is the final step in forward propagation?

Connects to: 15.4, 15.5

Filtering Algorithm

Must-know: Filtering gives hidden state on last day. Normalization mandatory at every step. Final step: COMPARE and pick MAX.

$P (X_{t + 1} ∣ e_{1 : t + 1}) = α P (e_{t + 1} ∣ X_{t + 1}) P (X_{t + 1} ∣ e_{1 : t})$

⚠️ Top pitfall: Forgetting normalization is mandatory. Comparing wrong values. Using unnormalized values for comparison.

Self-check: What is the final step in filtering?

Connects to: 15.3, 15.5

Viterbi's Algorithm (Most Likely Explanation)

Must-know: Viterbi gives most likely hidden state sequence for all days. At each step, pick MAX instead of summing. Final: compare each day's values, pick max for each day.

$v_{t} (j) = i max [v_{t - 1} (i) \times A_{ij}] \times P (e_{t} ∣ j)$

⚠️ Top pitfall: Confusing with filtering (last day only). Forgetting to compare for each day independently.

Self-check: What is the final step in Viterbi?

Connects to: 15.3, 15.4, 15.6

Student Behavioral Analysis: Complete Word Problem

Must-know: TPM/EPM construction is 60% of the problem. Use given initial probabilities (not 0.5/0.5). Viterbi for 'most likely explanation' queries.

$B = [0.8 0.2 0.05 0.95], A = [0.4 0.6 0.7 0.3], π = [0.1 0.9]$

⚠️ Top pitfall: Confusing TPM and EPM. Using 0.5/0.5 initial probabilities when given. Wrong matrix orientation.

Self-check: What is the most likely concentration sequence for grades BGB?

Connects to: 15.3, 15.4, 15.5

Multi-Agent Decision Making: Introduction

Must-know: Game theory studies strategic decision making. Three questions: what should I do, what will opponents do, what's the best response. Rational ≠ selfish.

⚠️ Top pitfall: Assuming rational agents are selfish. Confusing normal form and extensive form representations.

Self-check: What are the three fundamental questions game theory helps answer?

Connects to: 15.8, 15.9

Types of Games

Must-know: Zero-sum: one player's gain = another's loss. Non-zero-sum: both can win/lose. Cooperative: binding agreements possible. Non-cooperative: no binding agreements.

$u_{1} (a_{1}, a_{2}) + u_{2} (a_{1}, a_{2}) = c$

⚠️ Top pitfall: Confusing non-cooperative with competitive. Assuming all zero-sum games are non-cooperative.

Self-check: Is chess zero-sum or non-zero-sum? Cooperative or non-cooperative?

Connects to: 15.9, 15.10

Prisoner's Dilemma and Nash Equilibrium

Must-know: Prisoner's Dilemma: both confess (Nash equilibrium) even though both silent would be better. Nash equilibrium: no player can improve by changing only their own strategy.

$u_{i} (s_{i}^{*}, s_{- i}^{*}) \geq u_{i} (s_{i}, s_{- i}^{*}) for all s_{i} \in A_{i}$

⚠️ Top pitfall: Confusing Nash equilibrium with optimal outcome. Assuming rational agents always cooperate.

Self-check: What is the Nash equilibrium in the Prisoner's Dilemma?

Connects to: 15.7, 15.8, 15.10

The Mora Game Example

Must-know: Mora: non-zero-sum, non-cooperative, pure strategies exploitable. Mixed strategies needed.

⚠️ Top pitfall: Using pure strategies (fixed patterns) that can be predicted and exploited.

Self-check: Why are pure strategies weak in Mora?

Connects to: 15.8, 15.11

Pure Strategy vs Mixed Strategy

Must-know: Pure strategy: deterministic, predictable. Mixed strategy: probability distribution, unpredictable. Optimal mixed strategy makes opponent indifferent.

$σ_{i} = (p_{1}, p_{2}, \dots, p_{∣ A_{i} ∣})$

⚠️ Top pitfall: Using pure strategies in repeated games. Not randomizing enough.

Self-check: What is the difference between pure and mixed strategies?

Connects to: 15.10, 15.12

Game Strategies in Repeated Games

Must-know: Hawk: aggressive, adversarial. Dove: cooperative. Grim: cooperate until defection, then punish forever. Tit-for-tat: mirror opponent's previous action.

⚠️ Top pitfall: Choosing wrong strategy for the role. Hawk in collaborative teams, dove in adversarial settings.

Self-check: Which strategy would you use for a code reviewer agent?

Connects to: 15.8, 15.11

Exam Guidance Summary

Must-know: Three HMM algorithms: forward propagation (probability), filtering (last day), Viterbi (sequence). TPM/EPM construction is 60% of problem. Normalization rules.

⚠️ Top pitfall: Wrong TPM/EPM construction. Using 0.5/0.5 when initial probabilities given. Partial normalization.

Self-check: Which algorithm gives the hidden state on the last day?

Connects to: 15.3, 15.4, 15.5

Key Industry Applications

Must-know: HMMs: NLP, speech recognition, autonomous driving. Game theory: cybersecurity, marketplaces, robotics.

⚠️ Top pitfall: Thinking these are only theoretical concepts.

Self-check: Name one industry application of HMMs and one of game theory.

Connects to: 15.2, 15.7

Previous LectureLecture 14 · Temporal Models and Hidden Markov Models

Next LectureLecture 01 · Big Data Analytics — Course Introduction and Core Foundations

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.