use crate::game::{Coalition, ExplicitGame, PlayerSet, SetFunction};
use crate::rng::SplitMix64;
use crate::solution::Guarantee;
pub fn shapley(game: &ExplicitGame) -> Vec<f64> {
let n = game.players();
let mut weights = vec![0.0; n];
let mut binomial = 1.0;
for (s, weight) in weights.iter_mut().enumerate() {
*weight = 1.0 / (n as f64 * binomial);
binomial = binomial * (n - 1 - s) as f64 / (s + 1) as f64;
}
marginal_sums(game, |size| weights[size])
}
pub fn banzhaf(game: &ExplicitGame) -> Vec<f64> {
let weight = 1.0 / (1u64 << (game.players() - 1)) as f64;
marginal_sums(game, |_| weight)
}
pub fn solidarity(game: &ExplicitGame) -> Vec<f64> {
let n = game.players();
let mut weights = vec![0.0; n + 1];
let mut binomial = 1.0;
for (s, weight) in weights.iter_mut().enumerate().skip(1) {
*weight = 1.0 / (n as f64 * binomial);
binomial = binomial * (n - s) as f64 / s as f64;
}
let mut values = vec![0.0; n];
for mask in 1..1u64 << n {
let coalition = Coalition(mask);
let value = game.value(coalition);
let size = coalition.len();
let average = coalition
.members()
.map(|k| value - game.value(Coalition(mask & !(1 << k))))
.sum::<f64>()
/ size as f64;
for i in coalition.members() {
values[i] += weights[size] * average;
}
}
values
}
pub fn normalize(values: &[f64]) -> Vec<f64> {
let total: f64 = values.iter().sum();
if total == 0.0 {
return values.to_vec();
}
values.iter().map(|v| v / total).collect()
}
fn marginal_sums(game: &ExplicitGame, weight: impl Fn(usize) -> f64) -> Vec<f64> {
let n = game.players();
let mut values = vec![0.0; n];
for mask in 0..(1u64 << n) - 1 {
let coalition = Coalition(mask);
let base = game.value(coalition);
let w = weight(coalition.len());
for (i, value) in values.iter_mut().enumerate() {
if mask >> i & 1 == 0 {
*value += w * (game.value(Coalition(mask | 1 << i)) - base);
}
}
}
values
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct Estimate {
pub(crate) values: Vec<f64>,
pub(crate) standard_errors: Vec<f64>,
pub(crate) evaluations: usize,
pub(crate) guarantee: Guarantee,
}
impl Estimate {
pub fn values(&self) -> &[f64] {
&self.values
}
pub fn into_values(self) -> Vec<f64> {
self.values
}
pub fn standard_errors(&self) -> &[f64] {
&self.standard_errors
}
pub fn evaluations(&self) -> usize {
self.evaluations
}
pub fn guarantee(&self) -> Guarantee {
self.guarantee
}
}
struct Accumulator {
count: usize,
mean: Vec<f64>,
squares: Vec<f64>,
}
impl Accumulator {
fn new(n: usize) -> Accumulator {
Accumulator {
count: 0,
mean: vec![0.0; n],
squares: vec![0.0; n],
}
}
fn add(&mut self, sample: &[f64]) {
self.count += 1;
let count = self.count as f64;
for ((mean, squares), &x) in self.mean.iter_mut().zip(&mut self.squares).zip(sample) {
let delta = x - *mean;
*mean += delta / count;
*squares += delta * (x - *mean);
}
}
fn finish(self, evaluations: usize) -> Estimate {
let count = self.count as f64;
let standard_errors = self
.squares
.iter()
.map(|s| {
if self.count > 1 {
(s / (count - 1.0) / count).sqrt()
} else {
f64::INFINITY
}
})
.collect();
Estimate {
values: self.mean,
standard_errors,
evaluations,
guarantee: Guarantee::Approximate,
}
}
}
pub fn shapley_sampling<G: SetFunction + ?Sized>(
game: &G,
permutations: usize,
seed: u64,
) -> Estimate {
let n = game.players();
let mut rng = SplitMix64::new(seed);
let mut accumulator = Accumulator::new(n);
let mut order: Vec<usize> = (0..n).collect();
let mut sample = vec![0.0; n];
let empty_value = game.value(&PlayerSet::empty(n));
for _ in 0..permutations {
for i in (1..n).rev() {
let j = rng.range(0, i as u64) as usize;
order.swap(i, j);
}
let mut coalition = PlayerSet::empty(n);
let mut previous = empty_value;
for &player in &order {
coalition.insert(player);
let current = game.value(&coalition);
sample[player] = current - previous;
previous = current;
}
accumulator.add(&sample);
}
accumulator.finish(1 + permutations * n)
}
pub fn banzhaf_sampling<G: SetFunction + ?Sized>(game: &G, samples: usize, seed: u64) -> Estimate {
let n = game.players();
let mut rng = SplitMix64::new(seed);
let mut accumulator = Accumulator::new(n);
let mut sample = vec![0.0; n];
for _ in 0..samples {
let mut coalition = PlayerSet::empty(n);
for i in 0..n {
if rng.next_u64() & 1 == 1 {
coalition.insert(i);
}
}
let base = game.value(&coalition);
for (i, marginal) in sample.iter_mut().enumerate() {
let mut other = coalition.clone();
other.toggle(i);
let flipped = game.value(&other);
*marginal = if coalition.contains(i) {
base - flipped
} else {
flipped - base
};
}
accumulator.add(&sample);
}
accumulator.finish(samples * (n + 1))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::generators;
fn assert_close(actual: &[f64], expected: &[f64], label: &str) {
for (a, e) in actual.iter().zip(expected) {
assert!((a - e).abs() < 1e-9, "{label}: {actual:?} != {expected:?}");
}
}
#[test]
fn shapley_is_efficient_and_symmetric() {
let game = generators::bnf(1, 6, 3).unwrap();
let phi = shapley(&game);
assert!((phi.iter().sum::<f64>() - game.value(game.grand())).abs() < 1e-9);
let symmetric = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 60.0, 60.0, 60.0, 72.0]).unwrap();
assert_close(&shapley(&symmetric), &[24.0; 3], "対称ゲーム");
}
#[test]
fn solidarity_is_efficient_and_differs_from_shapley_on_null_player() {
let game = ExplicitGame::from_lex(&[1.0, 0.0, 0.0, 1.0, 1.0, 0.0, 1.0]).unwrap();
assert_close(&shapley(&game), &[1.0, 0.0, 0.0], "Shapley 値");
assert_close(
&solidarity(&game),
&[11.0 / 18.0, 7.0 / 36.0, 7.0 / 36.0],
"solidarity 値",
);
let unanimity = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0]).unwrap();
assert_close(
&solidarity(&unanimity),
&[7.0 / 18.0, 7.0 / 18.0, 4.0 / 18.0],
"u_{1,2}",
);
let random = generators::bnf(1, 6, 7).unwrap();
let psi = solidarity(&random);
assert!((psi.iter().sum::<f64>() - random.value(random.grand())).abs() < 1e-9);
}
#[test]
fn banzhaf_of_majority_game() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]).unwrap();
assert_close(&banzhaf(&game), &[0.5; 3], "多数決");
assert_close(&normalize(&banzhaf(&game)), &[1.0 / 3.0; 3], "正規化");
}
#[test]
fn sampling_estimates_agree_with_exact_values() {
let game = generators::bnf(2, 8, 5).unwrap();
let exact_shapley = shapley(&game);
let exact_banzhaf = banzhaf(&game);
let shapley_estimate = shapley_sampling(&game, 20_000, 1);
let banzhaf_estimate = banzhaf_sampling(&game, 20_000, 2);
for i in 0..8 {
assert!(
(shapley_estimate.values[i] - exact_shapley[i]).abs()
< 5.0 * shapley_estimate.standard_errors[i]
);
assert!(
(banzhaf_estimate.values[i] - exact_banzhaf[i]).abs()
< 5.0 * banzhaf_estimate.standard_errors[i]
);
}
assert!(
(shapley_estimate.values.iter().sum::<f64>() - game.value(game.grand())).abs() < 1e-6
);
}
}