use crate::error::GtError;
use crate::game::{Node, NodeId, PlayerId, Rational, StrategyId, ValidExtensiveGame};
#[derive(Debug, Clone, PartialEq)]
pub struct SpeSolution {
pub profile: Vec<Vec<(NodeId, StrategyId)>>,
pub path: Vec<(NodeId, StrategyId)>,
pub terminal_payoffs: Vec<Rational>,
}
#[derive(Debug, Clone, PartialEq)]
pub struct NodeDecision {
pub node: NodeId,
pub player: PlayerId,
pub chosen: Vec<StrategyId>,
pub pruned: Vec<StrategyId>,
pub action_values: Vec<Vec<Rational>>,
}
#[derive(Debug, Clone, PartialEq)]
pub struct BackwardInductionResult {
pub solutions: Vec<SpeSolution>,
pub node_log: Vec<NodeDecision>,
}
#[derive(Clone)]
struct SubtreeOption {
value: Vec<Rational>,
assign: Vec<(NodeId, StrategyId)>,
path: Vec<(NodeId, StrategyId)>,
}
pub fn solve_backward_induction(
game: &ValidExtensiveGame,
) -> Result<BackwardInductionResult, GtError> {
game.require_perfect_information()?;
let mut node_log = Vec::new();
let options = solve_node(game, game.root(), &mut node_log);
node_log.sort_by_key(|d| d.node);
let n_players = game.n_players();
let solutions = options
.into_iter()
.map(|opt| SpeSolution {
profile: regroup_by_player(game, &opt.assign, n_players),
path: opt.path,
terminal_payoffs: opt.value,
})
.collect();
Ok(BackwardInductionResult {
solutions,
node_log,
})
}
fn solve_node(
game: &ValidExtensiveGame,
id: NodeId,
log: &mut Vec<NodeDecision>,
) -> Vec<SubtreeOption> {
match game.node(id) {
Node::Terminal { .. } => vec![SubtreeOption {
value: game.terminal_payoffs(id).to_vec(),
assign: vec![],
path: vec![],
}],
Node::Decision { player, actions } => {
let player = *player;
let child_options: Vec<Vec<SubtreeOption>> = actions
.iter()
.map(|(_, child)| solve_node(game, *child, log))
.collect();
let action_values: Vec<Vec<Rational>> = child_options
.iter()
.map(|opts| opts[0].value.clone())
.collect();
let best = action_values
.iter()
.map(|v| v[player].clone())
.max()
.expect("a decision node has at least one action");
let mut chosen = Vec::new();
let mut pruned = Vec::new();
for (a, v) in action_values.iter().enumerate() {
if v[player] == best {
chosen.push(a);
} else {
pruned.push(a);
}
}
log.push(NodeDecision {
node: id,
player,
chosen,
pruned,
action_values,
});
let mut result = Vec::new();
for combo in cartesian_options(&child_options) {
let best_here = combo
.iter()
.map(|o| o.value[player].clone())
.max()
.expect("a decision node has at least one action");
let mut merged_assign = Vec::new();
for o in &combo {
merged_assign.extend(o.assign.iter().cloned());
}
for (a, o) in combo.iter().enumerate() {
if o.value[player] == best_here {
let mut assign = merged_assign.clone();
assign.push((id, a));
let mut path = vec![(id, a)];
path.extend(o.path.iter().cloned());
result.push(SubtreeOption {
value: o.value.clone(),
assign,
path,
});
}
}
}
dedup_options(&mut result);
result
}
}
}
fn cartesian_options(children: &[Vec<SubtreeOption>]) -> Vec<Vec<SubtreeOption>> {
let mut out: Vec<Vec<SubtreeOption>> = vec![vec![]];
for opts in children {
let mut next = Vec::with_capacity(out.len() * opts.len());
for prefix in &out {
for o in opts {
let mut row = prefix.clone();
row.push(o.clone());
next.push(row);
}
}
out = next;
}
out
}
fn dedup_options(opts: &mut Vec<SubtreeOption>) {
type Key = (
Vec<Rational>,
Vec<(NodeId, StrategyId)>,
Vec<(NodeId, StrategyId)>,
);
let mut seen: Vec<Key> = Vec::new();
opts.retain(|o| {
let mut assign = o.assign.clone();
assign.sort();
let key = (o.value.clone(), assign, o.path.clone());
if seen.contains(&key) {
false
} else {
seen.push(key);
true
}
});
}
fn regroup_by_player(
game: &ValidExtensiveGame,
assign: &[(NodeId, StrategyId)],
n_players: usize,
) -> Vec<Vec<(NodeId, StrategyId)>> {
let mut profile: Vec<Vec<(NodeId, StrategyId)>> = vec![Vec::new(); n_players];
for &(node, action) in assign {
if let Node::Decision { player, .. } = game.node(node) {
profile[*player].push((node, action));
}
}
for plan in &mut profile {
plan.sort_by_key(|(n, _)| *n);
}
profile
}
#[cfg(test)]
mod tests {
use super::*;
use crate::game::{ExtensiveGame, Node, PayoffKind, Player, ValidExtensiveGame};
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_unique_spe_is_enter_and_accommodate() {
let result = solve_backward_induction(&entry_deterrence()).expect("solved");
assert_eq!(result.solutions.len(), 1);
let spe = &result.solutions[0];
assert_eq!(spe.profile[0], vec![(0, 0)]); assert_eq!(spe.profile[1], vec![(1, 1)]); assert_eq!(spe.path, vec![(0, 0), (1, 1)]);
assert_eq!(spe.terminal_payoffs, vec![r(1), r(1)]);
}
#[test]
fn the_node_log_records_pruned_branches() {
let result = solve_backward_induction(&entry_deterrence()).expect("solved");
let incumbent = result
.node_log
.iter()
.find(|d| d.node == 1)
.expect("node 1 logged");
assert_eq!(incumbent.player, 1);
assert_eq!(incumbent.chosen, vec![1]); assert_eq!(incumbent.pruned, vec![0]); assert_eq!(incumbent.action_values[0], vec![r(-1), r(-1)]);
assert_eq!(incumbent.action_values[1], vec![r(1), r(1)]);
}
#[test]
fn the_node_log_is_ordered_by_node_id() {
let result = solve_backward_induction(&entry_deterrence()).expect("solved");
let ids: Vec<_> = result.node_log.iter().map(|d| d.node).collect();
assert_eq!(ids, vec![0, 1]);
}
#[test]
fn a_tie_yields_multiple_spe() {
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![("Go".into(), 1)],
},
Node::Decision {
player: 1,
actions: vec![("L".into(), 2), ("R".into(), 3)],
},
Node::Terminal {
payoffs: vec![1.0, 0.0],
},
Node::Terminal {
payoffs: vec![5.0, 0.0],
},
],
information_sets: vec![vec![0], vec![1]],
payoff_kind: PayoffKind::Cardinal,
})
.expect("valid");
let result = solve_backward_induction(&g).expect("solved");
assert_eq!(result.solutions.len(), 2, "player 1 indifferent -> two SPE");
let payoffs: Vec<_> = result
.solutions
.iter()
.map(|s| s.terminal_payoffs.clone())
.collect();
assert!(payoffs.contains(&vec![r(1), r(0)]));
assert!(payoffs.contains(&vec![r(5), r(0)]));
}
#[test]
fn an_off_path_tie_still_multiplies_the_solution_set() {
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![3.0, 0.0],
}, Node::Terminal {
payoffs: vec![1.0, 7.0],
}, Node::Terminal {
payoffs: vec![1.0, 7.0],
}, ],
information_sets: vec![vec![0], vec![1]],
payoff_kind: PayoffKind::Cardinal,
})
.expect("valid");
let result = solve_backward_induction(&g).expect("solved");
assert_eq!(result.solutions.len(), 2);
for spe in &result.solutions {
assert_eq!(spe.path, vec![(0, 1)], "every SPE takes Out");
assert_eq!(spe.terminal_payoffs, vec![r(3), r(0)]);
assert_eq!(spe.profile[1].len(), 1);
assert_eq!(spe.profile[1][0].0, 1);
}
let off_path: Vec<_> = result.solutions.iter().map(|s| s.profile[1][0].1).collect();
assert!(off_path.contains(&0) && off_path.contains(&1));
}
#[test]
fn every_solution_fixes_an_action_at_every_decision_node() {
let g = entry_deterrence();
let result = solve_backward_induction(&g).expect("solved");
for spe in &result.solutions {
for p in 0..g.n_players() {
let owned = g.decision_nodes_of(p);
let planned: Vec<_> = spe.profile[p].iter().map(|(n, _)| *n).collect();
assert_eq!(planned, owned, "player {p} plan must cover all own nodes");
}
}
}
#[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");
match solve_backward_induction(&g) {
Err(GtError::ImperfectInformationUnsupported { information_set }) => {
assert_eq!(information_set, 1);
}
other => panic!("expected ImperfectInformationUnsupported, got {other:?}"),
}
}
#[test]
fn a_root_terminal_has_one_trivial_solution() {
let g = ValidExtensiveGame::validate(ExtensiveGame {
players: vec![Player {
id: 0,
name: "A".into(),
}],
root: 0,
nodes: vec![Node::Terminal { payoffs: vec![7.0] }],
information_sets: vec![],
payoff_kind: PayoffKind::Cardinal,
})
.expect("valid");
let result = solve_backward_induction(&g).expect("solved");
assert_eq!(result.solutions.len(), 1);
assert_eq!(result.solutions[0].terminal_payoffs, vec![r(7)]);
assert!(result.solutions[0].path.is_empty());
assert!(result.node_log.is_empty());
}
#[test]
fn a_three_level_tree_folds_correctly() {
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_eq!(result.solutions.len(), 1);
let spe = &result.solutions[0];
assert_eq!(spe.path, vec![(0, 1), (2, 1)]);
assert_eq!(spe.terminal_payoffs, vec![r(1), r(2)]);
assert_eq!(spe.profile[1], vec![(1, 1), (2, 1)]);
}
}