use crate::error::GtError;
use crate::game::{Node, NodeId, PlayerId, Rational, StrategyId, ValidExtensiveGame};
#[derive(Debug, Clone, PartialEq)]
pub struct SpeDeviation {
pub node: NodeId,
pub player: PlayerId,
pub from_action: StrategyId,
pub to_action: StrategyId,
pub gain: Rational,
}
#[derive(Debug, Clone, PartialEq)]
pub struct SpeVerifyResult {
pub holds: bool,
pub deviation: Option<SpeDeviation>,
}
pub fn verify_spe(
game: &ValidExtensiveGame,
profile: &[Vec<(NodeId, StrategyId)>],
) -> Result<SpeVerifyResult, GtError> {
game.require_perfect_information()?;
if profile.len() != game.n_players() {
return Err(GtError::InvalidPlanProfile {
player: 0,
reason: format!(
"a profile must give one plan per player: got {} plan(s) for {} player(s)",
profile.len(),
game.n_players()
),
});
}
let mut action_at: Vec<Option<StrategyId>> = vec![None; game.nodes().len()];
for (player, plan) in profile.iter().enumerate() {
for &(node, action) in plan {
if node >= game.nodes().len() {
return Err(GtError::InvalidPlanProfile {
player,
reason: format!(
"node {node} does not exist; this tree has {} node(s)",
game.nodes().len()
),
});
}
let Node::Decision { actions, .. } = &game.nodes()[node] else {
return Err(GtError::InvalidPlanProfile {
player,
reason: format!("node {node} is terminal, so no action can be fixed at it"),
});
};
if action >= actions.len() {
return Err(GtError::InvalidPlanProfile {
player,
reason: format!(
"node {node} has {} action(s), so action index {action} is out of range",
actions.len()
),
});
}
action_at[node] = Some(action);
}
}
for (id, node) in game.nodes().iter().enumerate() {
if let Node::Decision { player, .. } = node {
if action_at[id].is_none() {
return Err(GtError::InvalidPlanProfile {
player: *player,
reason: format!(
"a plan must fix an action at every decision node, and node {id} is unset"
),
});
}
}
}
let mut value: Vec<Option<Vec<Rational>>> = vec![None; game.nodes().len()];
for id in 0..game.nodes().len() {
continuation(game, id, &action_at, &mut value);
}
let value_at = |id: NodeId| -> &[Rational] {
value[id].as_deref().expect("computed for every node above")
};
for (id, node) in game.nodes().iter().enumerate() {
if let Node::Decision { player, actions } = node {
let current = action_at[id].expect("checked above");
let current_value = value_at(actions[current].1)[*player].clone();
for (a, (_, child)) in actions.iter().enumerate() {
if a == current {
continue;
}
let alternative = value_at(*child)[*player].clone();
if alternative > current_value {
return Ok(SpeVerifyResult {
holds: false,
deviation: Some(SpeDeviation {
node: id,
player: *player,
from_action: current,
to_action: a,
gain: alternative - current_value,
}),
});
}
}
}
}
Ok(SpeVerifyResult {
holds: true,
deviation: None,
})
}
fn continuation(
game: &ValidExtensiveGame,
id: NodeId,
action_at: &[Option<StrategyId>],
value: &mut Vec<Option<Vec<Rational>>>,
) {
if value[id].is_some() {
return;
}
let v = match game.node(id) {
Node::Terminal { .. } => game.terminal_payoffs(id).to_vec(),
Node::Decision { actions, .. } => {
let action = action_at[id].expect("validated: every decision node has an action");
let child = actions[action].1;
continuation(game, child, action_at, value);
value[child].as_ref().expect("just computed").clone()
}
};
value[id] = Some(v);
}
#[cfg(test)]
mod tests {
use super::*;
use crate::game::{ExtensiveGame, Node, PayoffKind, Player, ValidExtensiveGame};
use crate::solve::backward_induction::solve_backward_induction;
fn r(n: i64) -> Rational {
Rational::from_integer(n.into())
}
fn entry_deterrence() -> ValidExtensiveGame {
ValidExtensiveGame::validate(ExtensiveGame {
players: vec![
Player {
id: 0,
name: "Entrant".into(),
},
Player {
id: 1,
name: "Incumbent".into(),
},
],
root: 0,
nodes: vec![
Node::Decision {
player: 0,
actions: vec![("In".into(), 1), ("Out".into(), 2)],
},
Node::Decision {
player: 1,
actions: vec![("Fight".into(), 3), ("Accommodate".into(), 4)],
},
Node::Terminal {
payoffs: vec![0.0, 2.0],
}, Node::Terminal {
payoffs: vec![-1.0, -1.0],
}, Node::Terminal {
payoffs: vec![1.0, 1.0],
}, ],
information_sets: vec![vec![0], vec![1]],
payoff_kind: PayoffKind::Cardinal,
})
.expect("valid")
}
#[test]
fn the_backward_induction_solution_verifies() {
let g = entry_deterrence();
let spe = &solve_backward_induction(&g).expect("solved").solutions[0];
let result = verify_spe(&g, &spe.profile).expect("checked");
assert!(result.holds);
assert!(result.deviation.is_none());
}
#[test]
fn a_non_credible_threat_is_caught() {
let g = entry_deterrence();
let profile = vec![vec![(0, 1)], vec![(1, 0)]];
let result = verify_spe(&g, &profile).expect("checked");
assert!(!result.holds);
let dev = result.deviation.expect("a deviation exists");
assert_eq!(dev.node, 1);
assert_eq!(dev.player, 1);
assert_eq!(dev.from_action, 0); assert_eq!(dev.to_action, 1); assert_eq!(dev.gain, r(2)); }
#[test]
fn an_on_path_deviation_is_caught() {
let g = entry_deterrence();
let profile = vec![vec![(0, 1)], vec![(1, 1)]];
let result = verify_spe(&g, &profile).expect("checked");
assert!(!result.holds);
let dev = result.deviation.expect("a deviation exists");
assert_eq!(dev.node, 0);
assert_eq!(dev.player, 0);
assert_eq!(dev.from_action, 1); assert_eq!(dev.to_action, 0); assert_eq!(dev.gain, r(1)); }
#[test]
fn every_backward_induction_solution_verifies_on_a_deeper_tree() {
let g = ValidExtensiveGame::validate(ExtensiveGame {
players: vec![
Player {
id: 0,
name: "P0".into(),
},
Player {
id: 1,
name: "P1".into(),
},
],
root: 0,
nodes: vec![
Node::Decision {
player: 0,
actions: vec![("A".into(), 1), ("B".into(), 2)],
},
Node::Decision {
player: 1,
actions: vec![("L".into(), 3), ("R".into(), 4)],
},
Node::Decision {
player: 1,
actions: vec![("L".into(), 5), ("R".into(), 6)],
},
Node::Terminal {
payoffs: vec![2.0, 1.0],
},
Node::Terminal {
payoffs: vec![0.0, 3.0],
},
Node::Terminal {
payoffs: vec![4.0, 0.0],
},
Node::Terminal {
payoffs: vec![1.0, 2.0],
},
],
information_sets: vec![vec![0], vec![1], vec![2]],
payoff_kind: PayoffKind::Cardinal,
})
.expect("valid");
let result = solve_backward_induction(&g).expect("solved");
assert!(!result.solutions.is_empty());
for spe in &result.solutions {
let checked = verify_spe(&g, &spe.profile).expect("checked");
assert!(checked.holds, "rejected an SPE: {:?}", spe.profile);
}
}
#[test]
fn an_off_path_suboptimal_action_is_still_caught() {
let g = ValidExtensiveGame::validate(ExtensiveGame {
players: vec![
Player {
id: 0,
name: "A".into(),
},
Player {
id: 1,
name: "B".into(),
},
],
root: 0,
nodes: vec![
Node::Decision {
player: 0,
actions: vec![("In".into(), 1), ("Out".into(), 2)],
},
Node::Decision {
player: 1,
actions: vec![("L".into(), 3), ("R".into(), 4)],
},
Node::Terminal {
payoffs: vec![9.0, 0.0],
}, Node::Terminal {
payoffs: vec![0.0, 1.0],
}, Node::Terminal {
payoffs: vec![0.0, 5.0],
}, ],
information_sets: vec![vec![0], vec![1]],
payoff_kind: PayoffKind::Cardinal,
})
.expect("valid");
let profile = vec![vec![(0, 1)], vec![(1, 0)]];
let result = verify_spe(&g, &profile).expect("checked");
assert!(
!result.holds,
"off-path suboptimality breaks subgame perfection"
);
let dev = result.deviation.expect("a deviation exists");
assert_eq!(dev.node, 1);
assert_eq!(dev.gain, r(4)); }
#[test]
fn imperfect_information_is_rejected() {
let g = ValidExtensiveGame::validate(ExtensiveGame {
players: vec![
Player {
id: 0,
name: "A".into(),
},
Player {
id: 1,
name: "B".into(),
},
],
root: 0,
nodes: vec![
Node::Decision {
player: 0,
actions: vec![("A".into(), 1), ("B".into(), 2)],
},
Node::Decision {
player: 1,
actions: vec![("L".into(), 3), ("R".into(), 4)],
},
Node::Decision {
player: 1,
actions: vec![("L".into(), 5), ("R".into(), 6)],
},
Node::Terminal {
payoffs: vec![0.0, 0.0],
},
Node::Terminal {
payoffs: vec![0.0, 0.0],
},
Node::Terminal {
payoffs: vec![0.0, 0.0],
},
Node::Terminal {
payoffs: vec![0.0, 0.0],
},
],
information_sets: vec![vec![0], vec![1, 2]],
payoff_kind: PayoffKind::Cardinal,
})
.expect("structurally valid");
let profile = vec![vec![(0, 0)], vec![(1, 0), (2, 0)]];
assert!(matches!(
verify_spe(&g, &profile),
Err(GtError::ImperfectInformationUnsupported { .. })
));
}
#[test]
fn a_profile_of_the_wrong_arity_is_rejected() {
let g = entry_deterrence();
let err = verify_spe(&g, &[vec![(0, 0)]]).unwrap_err();
assert!(
matches!(err, GtError::InvalidPlanProfile { player, ref reason }
if player == 0 && reason.contains("one plan per player")),
"got {err:?}"
);
}
#[test]
fn a_profile_missing_a_node_is_rejected() {
let g = entry_deterrence();
let err = verify_spe(&g, &[vec![(0, 0)], vec![]]).unwrap_err();
assert!(
matches!(err, GtError::InvalidPlanProfile { player, ref reason }
if player == 1 && reason.contains("node 1")),
"got {err:?}"
);
}
#[test]
fn a_node_id_out_of_range_is_rejected() {
let g = entry_deterrence();
let err = verify_spe(&g, &[vec![(99, 0)], vec![(1, 0)]]).unwrap_err();
assert!(
matches!(err, GtError::InvalidPlanProfile { player, ref reason }
if player == 0 && reason.contains("99")),
"got {err:?}"
);
}
#[test]
fn an_action_index_out_of_range_is_rejected() {
let g = entry_deterrence();
let err = verify_spe(&g, &[vec![(0, 0)], vec![(1, 99)]]).unwrap_err();
assert!(
matches!(err, GtError::InvalidPlanProfile { player, ref reason }
if player == 1 && reason.contains("99")),
"got {err:?}"
);
}
}