mod set;
pub use set::{KernelPiece, KernelSet, MAX_KERNEL_SET_PLAYERS, Row, SetOptions, kernel_set};
use crate::Domain;
use crate::error::{Error, Result};
use crate::game::allocation::{check_imputation_set, feasibility_violation};
use crate::game::{Coalition, ExplicitGame, default_tolerance};
use crate::solution::Guarantee;
use crate::surplus::max_surplus_flat;
#[derive(Clone, Copy, Debug, PartialEq)]
#[non_exhaustive]
pub struct TransferOptions {
pub tolerance: f64,
pub max_iterations: usize,
}
impl TransferOptions {
pub fn for_game(game: &ExplicitGame) -> TransferOptions {
TransferOptions {
tolerance: 0.01 * default_tolerance(game),
max_iterations: 1_000_000,
}
}
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct KernelResult {
pub(crate) allocation: Vec<f64>,
pub(crate) iterations: usize,
pub(crate) violation: f64,
pub(crate) converged: bool,
pub(crate) guarantee: Guarantee,
}
impl KernelResult {
pub fn allocation(&self) -> &[f64] {
&self.allocation
}
pub fn into_allocation(self) -> Vec<f64> {
self.allocation
}
pub fn iterations(&self) -> usize {
self.iterations
}
pub fn violation(&self) -> f64 {
self.violation
}
pub fn converged(&self) -> bool {
self.converged
}
pub fn guarantee(&self) -> Guarantee {
self.guarantee
}
}
pub fn kernel_violation(game: &ExplicitGame, x: &[f64], domain: Domain) -> f64 {
best_transfer(game, x, domain).map_or(0.0, |(_, _, delta)| 2.0 * delta)
}
pub fn is_in_kernel(game: &ExplicitGame, x: &[f64], domain: Domain, tolerance: f64) -> bool {
x.len() == game.players()
&& feasibility_violation(game, x, domain, tolerance).is_none()
&& kernel_violation(game, x, domain) <= tolerance
}
pub fn equal_surplus_division(game: &ExplicitGame) -> Vec<f64> {
let singles = game.singleton_values();
let surplus = game.value(game.grand()) - singles.iter().sum::<f64>();
let share = surplus / game.players() as f64;
singles.iter().map(|v| v + share).collect()
}
pub fn kernel_point(
game: &ExplicitGame,
domain: Domain,
start: Option<&[f64]>,
options: TransferOptions,
) -> Result<KernelResult> {
check_imputation_set(game, domain, options.tolerance)?;
let mut x = match start {
Some(start) => start.to_vec(),
None => equal_surplus_division(game),
};
if x.len() != game.players() {
return Err(Error::InvalidArgument(format!(
"初期配分の長さ {} がプレイヤー数 {} と異なる",
x.len(),
game.players()
)));
}
if let Some(reason) = feasibility_violation(game, &x, domain, options.tolerance) {
return Err(Error::InvalidArgument(format!("初期配分が不正: {reason}")));
}
let mut iterations = 0;
loop {
let transfer = best_transfer(game, &x, domain);
let violation = transfer.map_or(0.0, |(_, _, delta)| 2.0 * delta);
if violation <= options.tolerance || iterations >= options.max_iterations {
return Ok(KernelResult {
allocation: x,
iterations,
violation,
converged: violation <= options.tolerance,
guarantee: if violation <= options.tolerance {
Guarantee::Exact
} else {
Guarantee::Approximate
},
});
}
let (i, j, delta) = transfer.expect("violation > 0 なら支払いが存在する");
x[i] += delta;
x[j] -= delta;
iterations += 1;
}
}
fn best_transfer(game: &ExplicitGame, x: &[f64], domain: Domain) -> Option<(usize, usize, f64)> {
let n = game.players();
let surplus = max_surplus_flat(game, x);
let mut best: Option<(usize, usize, f64)> = None;
for i in 0..n {
for j in 0..n {
if i == j {
continue;
}
let mut delta = (surplus[i * n + j] - surplus[j * n + i]) / 2.0;
if domain == Domain::Imputation {
delta = delta.min(x[j] - game.value(Coalition::singleton(j)));
}
if delta > 0.0 && best.is_none_or(|(_, _, current)| delta > current) {
best = Some((i, j, delta));
}
}
}
best
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn pair_game_kernel() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 4.0, 0.0, 0.0, 4.0]).unwrap();
let result = kernel_point(
&game,
Domain::Imputation,
None,
TransferOptions::for_game(&game),
)
.unwrap();
assert!(result.converged);
assert!(is_in_kernel(
&game,
&result.allocation,
Domain::Imputation,
1e-6
));
for (a, e) in result.allocation.iter().zip([2.0, 2.0, 0.0]) {
assert!((a - e).abs() < 1e-6);
}
}
#[test]
fn rejects_unbalanced_point() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 4.0, 0.0, 0.0, 4.0]).unwrap();
assert!(!is_in_kernel(
&game,
&[1.0, 3.0, 0.0],
Domain::Imputation,
1e-6
));
assert!(
(kernel_violation(&game, &[1.0, 3.0, 0.0], Domain::Imputation) - 2.0).abs() < 1e-12
);
}
}