use crate::error::{Error, Result};
use crate::game::{Coalition, ExplicitGame};
use crate::values;
fn adjacency(players: usize, edges: &[(usize, usize)]) -> Result<Vec<u64>> {
let mut neighbors = vec![0u64; players];
for &(a, b) in edges {
if a >= players || b >= players || a == b {
return Err(Error::InvalidArgument(format!(
"辺 ({a}, {b}) の端点が範囲外か、自己ループ"
)));
}
neighbors[a] |= 1 << b;
neighbors[b] |= 1 << a;
}
Ok(neighbors)
}
fn components(mask: u64, neighbors: &[u64]) -> Vec<Coalition> {
let mut rest = mask;
let mut parts = Vec::new();
while rest != 0 {
let start = rest.trailing_zeros() as usize;
let mut component = 1u64 << start;
let mut frontier = component;
while frontier != 0 {
let v = frontier.trailing_zeros() as usize;
frontier &= frontier - 1;
let fresh = neighbors[v] & mask & !component;
component |= fresh;
frontier |= fresh;
}
rest &= !component;
parts.push(Coalition(component));
}
parts
}
pub fn graph_restricted(game: &ExplicitGame, edges: &[(usize, usize)]) -> Result<ExplicitGame> {
let n = game.players();
let neighbors = adjacency(n, edges)?;
let restricted: Vec<f64> = (1..1u64 << n)
.map(|mask| {
components(mask, &neighbors)
.into_iter()
.map(|c| game.value(c))
.sum()
})
.collect();
ExplicitGame::from_binary(&restricted)
}
pub fn myerson(game: &ExplicitGame, edges: &[(usize, usize)]) -> Result<Vec<f64>> {
Ok(values::shapley(&graph_restricted(game, edges)?))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::generators;
fn assert_close(actual: &[f64], expected: &[f64]) {
for (a, e) in actual.iter().zip(expected) {
assert!((a - e).abs() < 1e-9, "{actual:?} != {expected:?}");
}
}
#[test]
fn complete_graph_gives_shapley_value() {
let game = generators::bnf(1, 5, 2).unwrap();
let edges: Vec<(usize, usize)> = (0..5)
.flat_map(|a| (a + 1..5).map(move |b| (a, b)))
.collect();
assert_close(&myerson(&game, &edges).unwrap(), &values::shapley(&game));
}
#[test]
fn line_graph_three_player_majority() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]).unwrap();
let restricted = graph_restricted(&game, &[(0, 1), (1, 2)]).unwrap();
assert_eq!(restricted.value(Coalition::from_players(&[0, 2])), 0.0);
assert_close(
&myerson(&game, &[(0, 1), (1, 2)]).unwrap(),
&[1.0 / 6.0, 2.0 / 3.0, 1.0 / 6.0],
);
}
#[test]
fn glove_game_on_a_path_matches_myerson_package_example() {
let glove = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 1.0, 0.0, 1.0]).unwrap();
assert_close(
&myerson(&glove, &[(0, 1), (1, 2)]).unwrap(),
&[0.5, 0.5, 0.0],
);
}
#[test]
fn isolated_player_receives_standalone_value() {
let game = generators::bnf(1, 4, 9).unwrap();
let x = myerson(&game, &[(0, 1), (1, 2)]).unwrap();
assert!((x[3] - game.value(Coalition::singleton(3))).abs() < 1e-9);
}
#[test]
fn invalid_edges_are_rejected() {
let game = generators::bnf(1, 3, 0).unwrap();
assert!(myerson(&game, &[(0, 3)]).is_err());
assert!(myerson(&game, &[(1, 1)]).is_err());
}
}