mod exact;
mod kohlberg;
use exact::certify_tolerance;
pub use exact::{
ExactReport, certify, certify_exact, kohlberg_exact, max_difference, recover_allocation,
};
pub use kohlberg::{KohlbergReport, kohlberg};
use crate::Domain;
use crate::error::{Error, Result};
use crate::game::allocation::feasibility_violation;
use crate::game::exact::{ExactGame, Rational, to_f64};
use crate::game::{ExplicitGame, PlayerSet, SetFunction, value_scale};
use crate::linalg::max_abs_difference;
use crate::nucleolus::{self, Options};
use crate::rng::SplitMix64;
use crate::solution::{Guarantee, Solution, Unverified};
pub const MAX_CERTIFY_PLAYERS: usize = 20;
pub const MAX_PAIR_CHECK_PLAYERS: usize = 26;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct VerifyOptions {
pub pairs: usize,
pub seed: u64,
}
impl Default for VerifyOptions {
fn default() -> VerifyOptions {
VerifyOptions { pairs: 8, seed: 0 }
}
}
#[derive(Clone, Debug, PartialEq)]
pub enum Check {
Certified { exact: Vec<Rational> },
Refuted(String),
Undecided(String),
}
#[derive(Clone, Debug, PartialEq)]
pub enum Verified {
Certified(Solution),
Refuted { solution: Solution, reason: String },
Undecided {
solution: Unverified<Solution>,
reason: String,
},
}
impl Unverified<Solution> {
pub fn verify<G: SetFunction + ?Sized>(
self,
game: &G,
options: VerifyOptions,
) -> Result<Verified> {
let solution = self.peek();
let check = check(game, &solution.allocation, solution.domain, options)?;
Ok(self.conclude(check))
}
pub fn verify_exact(self, game: &ExactGame, options: VerifyOptions) -> Result<Verified> {
let solution = self.peek();
let check = check_exact(game, &solution.allocation, solution.domain, options)?;
Ok(self.conclude(check))
}
fn conclude(self, check: Check) -> Verified {
match check {
Check::Certified { exact } => {
let mut solution = self.accept_unverified();
solution.allocation = to_f64(&exact);
solution.guarantee = Guarantee::Certified;
Verified::Certified(solution)
}
Check::Refuted(reason) => Verified::Refuted {
solution: self.accept_unverified(),
reason,
},
Check::Undecided(reason) => Verified::Undecided {
solution: self,
reason,
},
}
}
}
pub fn check<G: SetFunction + ?Sized>(
game: &G,
x: &[f64],
domain: Domain,
options: VerifyOptions,
) -> Result<Check> {
let n = game.players();
check_length(n, x)?;
if n <= MAX_CERTIFY_PLAYERS {
let explicit = ExplicitGame::tabulate(game)?;
let exact = ExactGame::from_explicit(&explicit)?;
let tolerance = certify_tolerance(&explicit);
if let Some(refuted) = check_feasibility(&explicit, x, domain, tolerance) {
return Ok(refuted);
}
certify_small(&explicit, &exact, x, domain, tolerance)
} else if n <= MAX_PAIR_CHECK_PLAYERS {
let tolerance = 1e-6 * value_scale(game);
if let Some(refuted) = check_feasibility(game, x, domain, tolerance) {
return Ok(refuted);
}
Ok(check_pairs(game, x, domain, tolerance, options))
} else {
Ok(Check::Undecided(format!(
"{n} 人は検証できる人数 ({MAX_PAIR_CHECK_PLAYERS}) を超える"
)))
}
}
pub fn check_exact(
exact: &ExactGame,
x: &[f64],
domain: Domain,
_options: VerifyOptions,
) -> Result<Check> {
let explicit = exact.to_explicit()?;
check_length(explicit.players(), x)?;
let tolerance = certify_tolerance(&explicit);
match check_feasibility(&explicit, x, domain, tolerance) {
Some(refuted) => Ok(refuted),
None => certify_small(&explicit, exact, x, domain, tolerance),
}
}
fn certify_small(
explicit: &ExplicitGame,
exact_game: &ExactGame,
x: &[f64],
domain: Domain,
tolerance: f64,
) -> Result<Check> {
let report = certify_exact(exact_game, x, domain)?;
if report.satisfied {
return Ok(Check::Certified {
exact: report.allocation,
});
}
let reference = nucleolus::nucleolus_with(explicit, Options::new(explicit, domain))?;
let exact_reference = certify_exact(exact_game, &reference.allocation, domain)?;
let (distance, threshold, basis) = if exact_reference.satisfied {
(
max_difference(&exact_reference.allocation, x)?,
tolerance,
"厳密に検証した仁",
)
} else if kohlberg(explicit, &reference.allocation, domain)?.satisfied {
let distance = max_abs_difference(&reference.allocation, x);
(distance, 100.0 * tolerance, "浮動小数点で検証した仁")
} else {
return Ok(Check::Undecided("候補も基準の仁も検証に合格しない".into()));
};
Ok(if distance > threshold {
Check::Refuted(format!(
"{basis}との差が {distance:e} ある ({})",
report.reason.unwrap_or_default()
))
} else {
Check::Undecided(format!(
"{basis}との差 {distance:e} は許容誤差以下だが、候補は厳密な検証に合格しない"
))
})
}
fn check_length(n: usize, x: &[f64]) -> Result<()> {
if x.len() != n {
return Err(Error::InvalidArgument(format!(
"配分の長さ {} がプレイヤー数 {n} と異なる",
x.len()
)));
}
Ok(())
}
fn check_feasibility<G: SetFunction + ?Sized>(
game: &G,
x: &[f64],
domain: Domain,
tolerance: f64,
) -> Option<Check> {
feasibility_violation(game, x, domain, tolerance).map(Check::Refuted)
}
pub(crate) fn max_surplus_exhaustive<G: SetFunction + ?Sized>(
game: &G,
x: &[f64],
i: usize,
j: usize,
) -> f64 {
let n = game.players();
let others: Vec<usize> = (0..n).filter(|&k| k != i && k != j).collect();
let mut best = f64::NEG_INFINITY;
for mask in 0u64..(1u64 << others.len()) {
let mut members = vec![i];
members.extend(
others
.iter()
.enumerate()
.filter(|(bit, _)| mask >> bit & 1 == 1)
.map(|(_, &k)| k),
);
let set = PlayerSet::from_players(n, &members);
best = best.max(game.value(&set) - set.sum(x));
}
best
}
fn check_pairs<G: SetFunction + ?Sized>(
game: &G,
x: &[f64],
domain: Domain,
tolerance: f64,
options: VerifyOptions,
) -> Check {
let n = game.players();
let mut rng = SplitMix64::new(options.seed);
for _ in 0..options.pairs {
let i = rng.range(0, n as u64 - 1) as usize;
let mut j = rng.range(0, n as u64 - 2) as usize;
if j >= i {
j += 1;
}
let (forward, backward) = (
max_surplus_exhaustive(game, x, i, j),
max_surplus_exhaustive(game, x, j, i),
);
for (a, b, gap) in [(i, j, forward - backward), (j, i, backward - forward)] {
let at_lower = domain == Domain::Imputation
&& x[b] <= game.value(&PlayerSet::singleton(n, b)) + tolerance;
if gap > tolerance && !at_lower {
return Check::Refuted(format!(
"組 ({a}, {b}) でカーネル条件が成り立たない: s_ab - s_ba = {gap:e}"
));
}
}
}
Check::Undecided(format!(
"{} 組でカーネル条件の反例は見つからなかった (正しいとは確定しない)",
options.pairs
))
}