use std::cmp::Ordering;
use num_traits::{One, Signed, Zero};
use crate::Domain;
use crate::error::{Error, Result};
use crate::game::exact::{ExactGame, Rational, format_rational, to_f64, to_rational};
use crate::game::excess_table;
use crate::game::{Coalition, ExplicitGame};
use crate::linalg::Span;
use crate::rational::{ExactEchelon, Inserted, indicator, simplex};
#[derive(Clone, Debug)]
#[non_exhaustive]
pub struct ExactReport {
pub allocation: Vec<Rational>,
pub satisfied: bool,
pub reason: Option<String>,
pub levels_checked: usize,
}
impl ExactReport {
fn fail(allocation: Vec<Rational>, reason: String, levels_checked: usize) -> ExactReport {
ExactReport {
allocation,
satisfied: false,
reason: Some(reason),
levels_checked,
}
}
}
pub fn certify(game: &ExplicitGame, x: &[f64], domain: Domain) -> Result<ExactReport> {
certify_exact(&ExactGame::from_explicit(game)?, x, domain)
}
pub fn certify_exact(exact: &ExactGame, x: &[f64], domain: Domain) -> Result<ExactReport> {
let game = exact.to_explicit()?;
let tolerance = 1e-6 * game.max_abs_value().max(1.0);
match recover_allocation(&game, exact, x, domain, tolerance)? {
Some(allocation) => Ok(kohlberg_exact(exact, &allocation, domain)),
None => Ok(ExactReport::fail(
Vec::new(),
"超過の段から厳密な配分を一意に復元できない".into(),
0,
)),
}
}
pub fn recover_allocation(
game: &ExplicitGame,
exact: &ExactGame,
x: &[f64],
domain: Domain,
tolerance: f64,
) -> Result<Option<Vec<Rational>>> {
let n = game.players();
if x.len() != n {
return Err(Error::InvalidArgument(format!(
"配分の長さ {} がプレイヤー数 {n} と異なる",
x.len()
)));
}
let full = (1usize << n) - 1;
let excess = excess_table(game, x);
let mut order: Vec<usize> = (1..full).collect();
order.sort_by(|a, b| excess[*b].total_cmp(&excess[*a]));
let mut groups: Vec<Vec<usize>> = Vec::new();
let mut span = Span::new(n);
span.insert(&vec![1.0; n]);
let lower_bound: Vec<usize> = match domain {
Domain::Imputation => (0..n)
.filter(|&i| (x[i] - game.value(Coalition::singleton(i))).abs() <= tolerance)
.collect(),
Domain::Preimputation => Vec::new(),
};
for &i in &lower_bound {
span.insert_coalition(Coalition::singleton(i));
}
let mut start = 0;
while start < order.len() && !span.is_full() {
let head = excess[order[start]];
let mut end = start;
while end < order.len() && excess[order[end]] >= head - tolerance {
span.insert_coalition(Coalition(order[end] as u64));
end += 1;
}
groups.push(order[start..end].to_vec());
start = end;
}
if !span.is_full() {
return Ok(None);
}
let unknowns = n + groups.len();
let mut echelon = ExactEchelon::default();
let mut push = |mut row: Vec<Rational>, rhs: Rational| -> bool {
row.push(rhs);
!matches!(echelon.insert(row, unknowns), Inserted::Inconsistent)
};
let grand = Coalition::grand(n);
let mut efficiency = indicator(grand, n);
efficiency.resize(unknowns, Rational::zero());
if !push(efficiency, exact.value(grand).clone()) {
return Ok(None);
}
for &i in &lower_bound {
let mut row = vec![Rational::zero(); unknowns];
row[i] = Rational::one();
if !push(row, exact.value(Coalition::singleton(i)).clone()) {
return Ok(None);
}
}
for (k, group) in groups.iter().enumerate() {
for &mask in group {
let coalition = Coalition(mask as u64);
let mut row = indicator(coalition, n);
row.resize(unknowns, Rational::zero());
row[n + k] = Rational::one();
if !push(row, exact.value(coalition).clone()) {
return Ok(None);
}
}
}
if echelon.rank() != unknowns {
return Ok(None);
}
let mut solution = vec![Rational::zero(); unknowns];
for (pivot, row) in &echelon.rows {
solution[*pivot] = row[unknowns].clone();
}
solution.truncate(n);
Ok(Some(solution))
}
pub fn kohlberg_exact(game: &ExactGame, x: &[Rational], domain: Domain) -> ExactReport {
let n = game.players();
let grand = Coalition::grand(n);
let total = x.iter().fold(Rational::zero(), |acc, v| acc + v);
if &total != game.value(grand) {
return ExactReport::fail(
x.to_vec(),
format!(
"効率性を満たさない: x(N) = {}, v(N) = {}",
format_rational(&total),
format_rational(game.value(grand))
),
0,
);
}
let mut at_lower_bound: Vec<Coalition> = Vec::new();
if domain == Domain::Imputation {
for (i, xi) in x.iter().enumerate() {
let lower = game.value(Coalition::singleton(i));
match xi.cmp(lower) {
Ordering::Less => {
return ExactReport::fail(
x.to_vec(),
format!("個人合理性を満たさない: x_{i} < v({{{i}}})"),
0,
);
}
Ordering::Equal => at_lower_bound.push(Coalition::singleton(i)),
Ordering::Greater => {}
}
}
}
let full = (1usize << n) - 1;
let mut sums = vec![Rational::zero(); full + 1];
for mask in 1..=full {
let lowest = mask.trailing_zeros() as usize;
sums[mask] = &sums[mask & (mask - 1)] + &x[lowest];
}
let excess: Vec<Rational> = (0..=full)
.map(|mask| game.value(Coalition(mask as u64)) - &sums[mask])
.collect();
let mut order: Vec<usize> = (1..full).collect();
order.sort_by(|a, b| excess[*b].cmp(&excess[*a]));
let mut collection: Vec<Coalition> = Vec::new();
let mut span = ExactEchelon::default();
let mut levels_checked = 0;
let mut start = 0;
while start < order.len() {
let level = excess[order[start]].clone();
let mut end = start;
while end < order.len() && excess[order[end]] == level {
let coalition = Coalition(order[end] as u64);
collection.push(coalition);
span.insert(indicator(coalition, n), n);
end += 1;
}
levels_checked += 1;
if !is_balanced(&collection, &at_lower_bound, n) {
return ExactReport::fail(
x.to_vec(),
format!("超過 {} 以上の提携族が平衡でない", format_rational(&level)),
levels_checked,
);
}
if span.rank() == n {
break;
}
start = end;
}
ExactReport {
allocation: x.to_vec(),
satisfied: true,
reason: None,
levels_checked,
}
}
fn is_balanced(collection: &[Coalition], optional: &[Coalition], n: usize) -> bool {
let extra: Vec<Coalition> = optional
.iter()
.filter(|c| !collection.contains(c))
.copied()
.collect();
let columns: Vec<Coalition> = collection.iter().chain(&extra).copied().collect();
let mut rows = Vec::with_capacity(n);
let mut rhs = Vec::with_capacity(n);
for i in 0..n {
let mut row: Vec<Rational> = columns
.iter()
.map(|c| {
if c.contains(i) {
Rational::one()
} else {
Rational::zero()
}
})
.collect();
row.push(-Rational::one()); rows.push(row);
let count = collection.iter().filter(|c| c.contains(i)).count();
rhs.push(-Rational::from_integer(num_bigint::BigInt::from(count)));
}
simplex::is_feasible(&rows, &rhs)
}
pub fn max_difference(a: &[Rational], b: &[f64]) -> Result<f64> {
let mut worst = Rational::zero();
for (x, y) in a.iter().zip(b) {
let difference = (x - to_rational(*y)?).abs();
if difference > worst {
worst = difference;
}
}
Ok(to_f64(&[worst])[0])
}
#[cfg(test)]
mod tests {
use super::*;
use crate::nucleolus;
fn r(numerator: i64, denominator: i64) -> Rational {
Rational::new(numerator.into(), denominator.into())
}
#[test]
fn recovers_exact_ferguson_nucleolus() {
let game = ExplicitGame::from_lex(&[-1.0, 0.0, 1.0, 3.0, 4.0, 2.0, 5.0]).unwrap();
let x = nucleolus::nucleolus(&game).unwrap().allocation;
let report = certify(&game, &x, Domain::Imputation).unwrap();
assert!(report.satisfied, "{report:?}");
assert_eq!(report.allocation, vec![r(8, 3), r(2, 3), r(5, 3)]);
}
#[test]
fn rejects_non_nucleolus_exactly() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 4.0, 0.0, 0.0, 4.0]).unwrap();
let exact = ExactGame::from_explicit(&game).unwrap();
assert!(kohlberg_exact(&exact, &[r(2, 1), r(2, 1), r(0, 1)], Domain::Imputation).satisfied);
let report = kohlberg_exact(&exact, &[r(1, 1), r(3, 1), r(0, 1)], Domain::Imputation);
assert!(!report.satisfied);
let tiny = r(1, 1_000_000_000_000);
let report = kohlberg_exact(
&exact,
&[r(2, 1) + &tiny, r(2, 1) - &tiny, r(0, 1)],
Domain::Imputation,
);
assert!(!report.satisfied);
}
}