use std::collections::HashMap;
use super::oracle;
use crate::Domain;
use crate::error::{Error, Result};
use crate::game::oracle::OracleGame;
use crate::game::{PlayerSet, SetFunction};
use crate::nucleolus::{LeastCore, NucleolusResult};
use crate::rng::SplitMix64;
use crate::solution::Guarantee;
fn finite(value: f64) -> Result<f64> {
if value.is_finite() {
Ok(value)
} else {
Err(Error::InvalidArgument(format!(
"提携の値 {value} が有限の数ではない"
)))
}
}
#[derive(Clone, Debug)]
pub struct SampledGame {
players: usize,
coalitions: Vec<PlayerSet>,
values: HashMap<PlayerSet, f64>,
grand_value: f64,
scale: f64,
}
impl SampledGame {
pub fn sample<G: SetFunction + ?Sized>(
game: &G,
pairs: usize,
seed: u64,
) -> Result<SampledGame> {
let n = game.players();
if n < 2 {
return Err(Error::InvalidArgument("2 人以上が必要".into()));
}
let mut rng = SplitMix64::new(seed);
let mut coalitions: Vec<PlayerSet> = Vec::new();
for i in 0..n {
let single = PlayerSet::singleton(n, i);
coalitions.push(single.complement());
coalitions.push(single);
}
for _ in 0..pairs {
let mut set = PlayerSet::empty(n);
for i in 0..n {
if rng.next_u64() & 1 == 1 {
set.insert(i);
}
}
if set.is_proper() {
coalitions.push(set.complement());
coalitions.push(set);
}
}
SampledGame::from_coalitions(game, coalitions)
}
pub(crate) fn from_coalitions<G: SetFunction + ?Sized>(
game: &G,
coalitions: Vec<PlayerSet>,
) -> Result<SampledGame> {
let n = game.players();
let mut values: HashMap<PlayerSet, f64> = HashMap::new();
let mut unique: Vec<PlayerSet> = Vec::new();
let add =
|set: PlayerSet, values: &mut HashMap<PlayerSet, f64>, unique: &mut Vec<PlayerSet>| {
if set.universe() != n {
return Err(Error::InvalidArgument("提携の人数がゲームと異なる".into()));
}
if set.is_proper() && !values.contains_key(&set) {
let value = finite(game.value(&set))?;
values.insert(set.clone(), value);
unique.push(set);
}
Ok(())
};
for i in 0..n {
let single = PlayerSet::singleton(n, i);
add(single.complement(), &mut values, &mut unique)?;
add(single, &mut values, &mut unique)?;
}
for set in coalitions {
add(set.complement(), &mut values, &mut unique)?;
add(set, &mut values, &mut unique)?;
}
let grand_value = finite(game.value(&PlayerSet::grand(n)))?;
let scale = values
.values()
.fold(grand_value.abs(), |acc, v| acc.max(v.abs()));
Ok(SampledGame {
players: n,
coalitions: unique,
values,
grand_value,
scale,
})
}
pub fn evaluations(&self) -> usize {
self.coalitions.len() + 1
}
pub fn coalitions(&self) -> &[PlayerSet] {
&self.coalitions
}
}
impl SetFunction for SampledGame {
fn players(&self) -> usize {
self.players
}
fn value(&self, coalition: &PlayerSet) -> f64 {
if coalition.is_empty() {
return 0.0;
}
if coalition.is_full() {
return self.grand_value;
}
*self
.values
.get(coalition)
.expect("サンプルしていない提携の値は使わない (補集合も含めてサンプルしている)")
}
}
impl OracleGame for SampledGame {
fn excess_order<'a>(&'a self, x: &'a [f64]) -> Box<dyn Iterator<Item = (PlayerSet, f64)> + 'a> {
let mut order: Vec<(PlayerSet, f64)> = self
.coalitions
.iter()
.map(|set| (set.clone(), self.values[set] - set.sum(x)))
.collect();
order.sort_by(|a, b| b.1.total_cmp(&a.1).then_with(|| a.0.cmp(&b.0)));
Box::new(order.into_iter())
}
fn scale(&self) -> f64 {
self.scale
}
}
#[derive(Clone, Debug)]
#[non_exhaustive]
pub struct SampledNucleolus {
pub(crate) allocation: Vec<f64>,
pub(crate) epsilon: f64,
pub(crate) levels: Vec<f64>,
pub(crate) evaluations: usize,
pub(crate) guarantee: Guarantee,
}
impl SampledNucleolus {
pub fn allocation(&self) -> &[f64] {
&self.allocation
}
pub fn into_allocation(self) -> Vec<f64> {
self.allocation
}
pub fn epsilon(&self) -> f64 {
self.epsilon
}
pub fn levels(&self) -> &[f64] {
&self.levels
}
pub fn evaluations(&self) -> usize {
self.evaluations
}
pub fn guarantee(&self) -> Guarantee {
self.guarantee
}
}
pub fn nucleolus<G: SetFunction + ?Sized>(
game: &G,
pairs: usize,
seed: u64,
domain: Domain,
) -> Result<SampledNucleolus> {
let sampled = SampledGame::sample(game, pairs, seed)?;
let result: NucleolusResult =
oracle::nucleolus_with(&sampled, domain, oracle::default_tolerance(&sampled))?;
Ok(SampledNucleolus {
epsilon: result.levels.first().copied().unwrap_or(0.0),
allocation: result.allocation,
levels: result.levels,
evaluations: sampled.evaluations(),
guarantee: Guarantee::Approximate,
})
}
pub fn least_core<G: SetFunction + ?Sized>(
game: &G,
pairs: usize,
seed: u64,
domain: Domain,
) -> Result<(LeastCore, usize)> {
let sampled = SampledGame::sample(game, pairs, seed)?;
let mut least = oracle::least_core(&sampled, domain)?;
least.guarantee = Guarantee::Approximate;
Ok((least, sampled.evaluations()))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::generators;
use crate::nucleolus;
#[test]
fn all_coalitions_give_exact_nucleolus() {
for kind in [1, 2, 4] {
let game = generators::bnf(kind, 6, 3).unwrap();
let n = game.players();
let all: Vec<PlayerSet> = (1u64..(1 << n) - 1)
.map(|mask| PlayerSet::from_coalition(n, crate::Coalition(mask)))
.collect();
let sampled = SampledGame::from_coalitions(&game, all).unwrap();
assert_eq!(sampled.evaluations(), (1 << n) - 1);
for domain in [Domain::Imputation, Domain::Preimputation] {
let expected =
nucleolus::nucleolus_with(&game, nucleolus::Options::new(&game, domain))
.unwrap()
.allocation;
let actual = oracle::nucleolus_with(&sampled, domain, 1e-7 * game.max_abs_value())
.unwrap()
.allocation;
for (a, e) in actual.iter().zip(&expected) {
assert!(
(a - e).abs() < 1e-6 * game.max_abs_value(),
"type{kind} {domain:?}"
);
}
}
}
}
#[test]
fn rejects_non_finite_values() {
struct Broken;
impl SetFunction for Broken {
fn players(&self) -> usize {
4
}
fn value(&self, coalition: &PlayerSet) -> f64 {
if coalition.len() == 2 { f64::NAN } else { 1.0 }
}
}
assert!(SampledGame::sample(&Broken, 20, 0).is_err());
}
#[test]
fn samples_are_closed_under_complement() {
let game = generators::bnf(1, 8, 0).unwrap();
let sampled = SampledGame::sample(&game, 50, 1).unwrap();
for set in sampled.coalitions() {
assert!(sampled.coalitions().contains(&set.complement()));
}
assert!(sampled.evaluations() > 16);
}
}