use std::cell::Cell;
use crate::Domain;
use crate::error::{Error, Result};
use crate::game::{PlayerSet, SetFunction, value_scale};
use crate::properties::{ConvexGame, ProofKind};
use crate::solution::{Property, Solution};
use crate::submodular;
#[derive(Clone, Copy, Debug, PartialEq)]
#[non_exhaustive]
pub struct ConvexOptions {
pub tolerance: Option<f64>,
pub max_sweeps: usize,
pub max_sfm_iterations: usize,
}
impl Default for ConvexOptions {
fn default() -> ConvexOptions {
ConvexOptions {
tolerance: None,
max_sweeps: 10_000,
max_sfm_iterations: 100_000,
}
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
#[non_exhaustive]
pub struct ConvexStats {
pub sweeps: usize,
pub transfers: usize,
pub minimizations: usize,
pub evaluations: usize,
}
pub fn nucleolus<G: ConvexGame + ?Sized>(
game: &G,
) -> Result<<G::Proof as ProofKind>::Output<Solution>> {
Ok(nucleolus_with(game, ConvexOptions::default())?.0)
}
pub fn nucleolus_with<G: ConvexGame + ?Sized>(
game: &G,
options: ConvexOptions,
) -> Result<(<G::Proof as ProofKind>::Output<Solution>, ConvexStats)> {
let (allocation, stats) = prekernel_point(game, options)?;
let solution = Solution {
domain: Domain::Imputation,
allocation,
guarantee: G::Proof::guarantee(Property::Convex),
method: "convex-transfer",
};
Ok((G::Proof::wrap(solution, Property::Convex), stats))
}
fn max_surplus<G: SetFunction + ?Sized>(
game: &G,
x: &[f64],
i: usize,
j: usize,
tolerance: f64,
max_iterations: usize,
evaluations: &Cell<usize>,
) -> Result<f64> {
let n = game.players();
let others: Vec<usize> = (0..n).filter(|&k| k != i && k != j).collect();
let mut f = |set: &[bool]| {
let mut coalition = PlayerSet::singleton(n, i);
for (k, inside) in others.iter().zip(set) {
if *inside {
coalition.insert(*k);
}
}
evaluations.set(evaluations.get() + 1);
-(game.value(&coalition) - coalition.sum(x))
};
let minimum = submodular::minimize(others.len(), &mut f, tolerance, max_iterations)?;
let single = game.value(&PlayerSet::singleton(n, i)) - x[i];
Ok(single - minimum.value)
}
fn prekernel_point<G: SetFunction + ?Sized>(
game: &G,
options: ConvexOptions,
) -> Result<(Vec<f64>, ConvexStats)> {
let n = game.players();
if n == 0 {
return Err(Error::InvalidArgument("プレイヤーがいない".into()));
}
let total = game.value(&PlayerSet::grand(n));
let mut x = vec![total / n as f64; n];
let mut stats = ConvexStats::default();
if n == 1 {
return Ok((x, stats));
}
let scale = value_scale(game);
let tolerance = options.tolerance.unwrap_or(1e-9 * scale);
let sfm_tolerance = 1e-3 * tolerance;
let evaluations = Cell::new(0);
for _ in 0..options.max_sweeps {
stats.sweeps += 1;
let mut moved = false;
for i in 0..n {
for j in i + 1..n {
let forward = max_surplus(
game,
&x,
i,
j,
sfm_tolerance,
options.max_sfm_iterations,
&evaluations,
)?;
let backward = max_surplus(
game,
&x,
j,
i,
sfm_tolerance,
options.max_sfm_iterations,
&evaluations,
)?;
stats.minimizations += 2;
let gap = forward - backward;
if gap.abs() > tolerance {
x[i] += gap / 2.0;
x[j] -= gap / 2.0;
stats.transfers += 1;
moved = true;
}
}
}
if !moved {
stats.evaluations = evaluations.get();
return Ok((x, stats));
}
}
Err(Error::LimitExceeded(format!(
"transfer scheme が {} 周で収束しない",
options.max_sweeps
)))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::generators;
use crate::nucleolus;
use crate::properties::ConvexChecked;
#[test]
fn matches_lp_nucleolus_on_random_convex_games() {
for seed in 0..30 {
let n = 2 + (seed % 7) as usize;
let game = ConvexChecked::new(generators::random_convex(n, seed).unwrap())
.expect("凸ゲームを生成する");
let expected = nucleolus::nucleolus(game.game()).unwrap().allocation;
let (solution, stats) = nucleolus_with(&game, ConvexOptions::default()).unwrap();
let scale = game.game().max_abs_value().max(1.0);
for (a, e) in solution.allocation.iter().zip(&expected) {
assert!(
(a - e).abs() <= 1e-6 * scale,
"seed {seed} n={n}: {:?} != {expected:?} ({stats:?})",
solution.allocation
);
}
assert_eq!(
solution.guarantee,
crate::Guarantee::Proven(Property::Convex)
);
}
}
}