use crate::analysis::explain::{self, ExplainOptions};
use crate::error::{Error, Result};
use crate::game::{Coalition, ExplicitGame};
use crate::rng::SplitMix64;
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct Distribution {
pub mean: Vec<f64>,
pub std: Vec<f64>,
pub quantiles: Vec<(f64, Vec<f64>)>,
pub samples: usize,
pub failures: usize,
}
const QUANTILES: [f64; 3] = [0.05, 0.5, 0.95];
pub fn monte_carlo(
samples: usize,
seed: u64,
mut sample: impl FnMut(&mut SplitMix64) -> Result<ExplicitGame>,
mut solve: impl FnMut(&ExplicitGame) -> Result<Vec<f64>>,
) -> Result<Distribution> {
let mut rng = SplitMix64::new(seed);
let mut allocations: Vec<Vec<f64>> = Vec::with_capacity(samples);
let mut failures = 0;
let mut players: Option<usize> = None;
for _ in 0..samples {
let game = sample(&mut rng)?;
let n = *players.get_or_insert(game.players());
if game.players() != n {
return Err(Error::InvalidArgument(format!(
"標本のゲームの人数 {} が最初の標本の人数 {n} と異なる",
game.players()
)));
}
match solve(&game) {
Ok(x) if x.len() != n => {
return Err(Error::InvalidArgument(format!(
"解いた配分の長さ {} がプレイヤー数 {n} と異なる",
x.len()
)));
}
Ok(x) => allocations.push(x),
Err(_) => failures += 1,
}
}
summarize(&allocations, failures)
}
fn summarize(allocations: &[Vec<f64>], failures: usize) -> Result<Distribution> {
let Some(first) = allocations.first() else {
return Err(Error::InvalidArgument(format!(
"解けた標本がない ({failures} 個とも失敗)"
)));
};
let n = first.len();
let count = allocations.len() as f64;
let mean: Vec<f64> = (0..n)
.map(|i| allocations.iter().map(|x| x[i]).sum::<f64>() / count)
.collect();
let std: Vec<f64> = (0..n)
.map(|i| {
if allocations.len() < 2 {
return 0.0;
}
let squares: f64 = allocations.iter().map(|x| (x[i] - mean[i]).powi(2)).sum();
(squares / (count - 1.0)).sqrt()
})
.collect();
let quantiles = QUANTILES
.iter()
.map(|&q| {
let values = (0..n)
.map(|i| {
let mut column: Vec<f64> = allocations.iter().map(|x| x[i]).collect();
column.sort_by(f64::total_cmp);
let rank =
((q * (column.len() - 1) as f64).round() as usize).min(column.len() - 1);
column[rank]
})
.collect();
(q, values)
})
.collect();
Ok(Distribution {
mean,
std,
quantiles,
samples: allocations.len(),
failures,
})
}
#[derive(Clone, Debug, PartialEq)]
pub struct IntervalGame {
lower: ExplicitGame,
upper: ExplicitGame,
}
impl IntervalGame {
pub fn new(lower: ExplicitGame, upper: ExplicitGame) -> Result<IntervalGame> {
if lower.players() != upper.players() {
return Err(Error::InvalidArgument("下限と上限の人数が異なる".into()));
}
if lower
.values()
.iter()
.zip(upper.values())
.any(|(l, u)| l > u)
{
return Err(Error::InvalidArgument(
"下限が上限を超える提携がある".into(),
));
}
Ok(IntervalGame { lower, upper })
}
pub fn around(game: &ExplicitGame, relative: f64) -> Result<IntervalGame> {
if !(relative.is_finite() && relative >= 0.0) {
return Err(Error::InvalidArgument("相対誤差は非負の有限値".into()));
}
let shift = |sign: f64| game.map_values(|_, v| v + sign * relative * v.abs());
IntervalGame::new(shift(-1.0)?, shift(1.0)?)
}
pub fn lower(&self) -> &ExplicitGame {
&self.lower
}
pub fn upper(&self) -> &ExplicitGame {
&self.upper
}
pub(crate) fn sample(&self, rng: &mut SplitMix64) -> Result<ExplicitGame> {
self.lower
.map_values(|s, l| l + (self.upper.value(s) - l) * rng.next_f64())
}
}
pub type Solver = Box<dyn FnMut(&ExplicitGame) -> Result<Vec<f64>>>;
pub const SOLVERS: [&str; 3] = ["nucleolus", "prenucleolus", "shapley"];
pub fn solver(name: &str) -> Option<Solver> {
match name {
"nucleolus" => Some(Box::new(|g: &ExplicitGame| {
Ok(crate::nucleolus::nucleolus(g)?.allocation)
})),
"prenucleolus" => Some(Box::new(|g: &ExplicitGame| {
Ok(crate::nucleolus::prenucleolus(g)?.allocation)
})),
"shapley" => Some(Box::new(|g: &ExplicitGame| Ok(crate::values::shapley(g)))),
_ => None,
}
}
pub fn interval_monte_carlo(
game: &IntervalGame,
samples: usize,
seed: u64,
solve: impl FnMut(&ExplicitGame) -> Result<Vec<f64>>,
) -> Result<Distribution> {
monte_carlo(samples, seed, |rng| game.sample(rng), solve)
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct Influence {
pub coalition: Coalition,
pub sensitivity: Vec<f64>,
}
impl Influence {
pub fn magnitude(&self) -> f64 {
self.sensitivity.iter().fold(0.0, |acc, s| acc.max(s.abs()))
}
}
pub fn influence(
game: &ExplicitGame,
coalitions: &[Coalition],
delta: f64,
mut solve: impl FnMut(&ExplicitGame) -> Result<Vec<f64>>,
) -> Result<Vec<Influence>> {
if !(delta.is_finite() && delta > 0.0) {
return Err(Error::InvalidArgument("delta は正の有限値".into()));
}
let n = game.players();
for coalition in coalitions {
if coalition.is_empty() {
return Err(Error::InvalidArgument(
"空の提携の値は 0 に固定なので動かせない".into(),
));
}
if !coalition.is_subset(game.grand()) {
return Err(Error::InvalidArgument(format!(
"提携 {coalition} に人数 {n} 以上の番号がある"
)));
}
}
let check = |x: Vec<f64>| -> Result<Vec<f64>> {
if x.len() != n {
return Err(Error::InvalidArgument(format!(
"解いた配分の長さ {} がプレイヤー数 {n} と異なる",
x.len()
)));
}
Ok(x)
};
coalitions
.iter()
.map(|&coalition| {
let shifted =
|sign: f64| game.with_value(coalition, game.value(coalition) + sign * delta);
let plus = check(solve(&shifted(1.0)?)?)?;
let minus = check(solve(&shifted(-1.0)?)?)?;
Ok(Influence {
coalition,
sensitivity: plus
.iter()
.zip(&minus)
.map(|(p, m)| (p - m) / (2.0 * delta))
.collect(),
})
})
.collect()
}
pub fn key_coalitions(game: &ExplicitGame, x: &[f64], levels: usize) -> Result<Vec<Coalition>> {
let report = explain::report(
game,
x,
ExplainOptions {
levels,
max_listed: usize::MAX,
tolerance: None,
},
)?;
let mut coalitions: Vec<Coalition> = report
.levels
.into_iter()
.flat_map(|level| level.coalitions)
.collect();
coalitions.push(game.grand());
Ok(coalitions)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{nucleolus, values};
fn four_player() -> ExplicitGame {
ExplicitGame::from_lex(&[
0.0, 0.0, 0.0, 0.0, 5.0, 5.0, 8.0, 9.0, 10.0, 8.0, 13.0, 15.0, 16.0, 17.0, 21.0,
])
.unwrap()
}
fn solve_nucleolus(game: &ExplicitGame) -> Result<Vec<f64>> {
Ok(nucleolus::nucleolus(game)?.allocation)
}
#[test]
fn zero_width_interval_has_no_spread() {
let game = four_player();
let interval = IntervalGame::around(&game, 0.0).unwrap();
let distribution = interval_monte_carlo(&interval, 5, 1, solve_nucleolus).unwrap();
let expected = solve_nucleolus(&game).unwrap();
for ((mean, std), e) in distribution
.mean
.iter()
.zip(&distribution.std)
.zip(&expected)
{
assert!((mean - e).abs() < 1e-9);
assert!(*std < 1e-9);
}
assert_eq!(distribution.samples, 5);
}
#[test]
fn spread_grows_with_uncertainty() {
let game = four_player();
let narrow = interval_monte_carlo(
&IntervalGame::around(&game, 0.01).unwrap(),
100,
2,
solve_nucleolus,
)
.unwrap();
let wide = interval_monte_carlo(
&IntervalGame::around(&game, 0.1).unwrap(),
100,
2,
solve_nucleolus,
)
.unwrap();
for i in 0..4 {
assert!(wide.std[i] > narrow.std[i]);
let (low, high) = (&wide.quantiles[0].1, &wide.quantiles[2].1);
assert!(low[i] <= wide.mean[i] && wide.mean[i] <= high[i]);
}
}
#[test]
fn nucleolus_depends_only_on_binding_coalitions() {
let game = four_player();
let x = solve_nucleolus(&game).unwrap();
let key = key_coalitions(&game, &x, 1).unwrap();
let binding = influence(&game, &key, 1e-4, solve_nucleolus).unwrap();
assert!(binding.iter().any(|i| i.magnitude() > 0.1));
let slack = influence(&game, &[Coalition::singleton(0)], 1e-4, solve_nucleolus).unwrap();
assert!(slack[0].magnitude() < 1e-6);
}
#[test]
fn shapley_sensitivity_matches_weights() {
let game = four_player();
let s = Coalition::from_players(&[0, 1]);
let result = influence(&game, &[s], 0.5, |g| Ok(values::shapley(g))).unwrap();
let inside = 1.0 * 2.0 / 24.0; let outside = -2.0 * 1.0 / 24.0; let expected = [inside, inside, outside, outside];
for (a, e) in result[0].sensitivity.iter().zip(expected) {
assert!((a - e).abs() < 1e-9, "{:?}", result[0].sensitivity);
}
}
#[test]
fn key_coalitions_of_one_player_game() {
let game = ExplicitGame::from_lex(&[1.0]).unwrap();
let key = key_coalitions(&game, &[1.0], 2).unwrap();
assert_eq!(key, vec![game.grand()]);
}
}