use crate::Domain;
use crate::error::{Error, Result};
use crate::game::allocation::feasibility_violation;
use crate::game::excess_table;
use crate::game::{Coalition, ExplicitGame, default_tolerance};
use crate::linalg::Span;
use crate::lp::{self, Cmp, Counter};
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct KohlbergReport {
pub satisfied: bool,
pub reason: Option<String>,
pub levels_checked: usize,
pub lp_solves: usize,
}
pub fn kohlberg(game: &ExplicitGame, x: &[f64], domain: Domain) -> Result<KohlbergReport> {
let tolerance = default_tolerance(game) * 10.0;
let n = game.players();
if x.len() != n {
return Err(Error::InvalidArgument(format!(
"配分の長さ {} がプレイヤー数 {n} と異なる",
x.len()
)));
}
let fail = |reason: String| KohlbergReport {
satisfied: false,
reason: Some(reason),
levels_checked: 0,
lp_solves: 0,
};
if let Some(reason) = feasibility_violation(game, x, domain, tolerance) {
return Ok(fail(reason));
}
let excess = excess_table(game, x);
let full = (1usize << n) - 1;
let mut order: Vec<usize> = (1..full).collect();
order.sort_by(|a, b| excess[*b].total_cmp(&excess[*a]));
let at_lower_bound: Vec<Coalition> = match domain {
Domain::Imputation => (0..n)
.filter(|&i| x[i] <= game.value(Coalition::singleton(i)) + tolerance)
.map(Coalition::singleton)
.collect(),
Domain::Preimputation => Vec::new(),
};
let mut counter = Counter::default();
let mut collection: Vec<Coalition> = Vec::new();
let mut span = Span::new(n);
let mut levels_checked = 0;
let mut start = 0;
while start < order.len() {
let level = excess[order[start]];
let mut end = start;
while end < order.len() && excess[order[end]] >= level - tolerance {
let coalition = Coalition(order[end] as u64);
collection.push(coalition);
span.insert_coalition(coalition);
end += 1;
}
if end == start {
return Err(Error::Numerical(format!(
"超過 {level} の段を作れない (比較できない値がある)"
)));
}
levels_checked += 1;
if !is_balanced(&collection, &at_lower_bound, n, &mut counter)? {
return Ok(KohlbergReport {
satisfied: false,
reason: Some(format!("超過 {level} 以上の提携族が平衡でない")),
levels_checked,
lp_solves: counter.solves,
});
}
if span.is_full() {
break;
}
start = end;
}
Ok(KohlbergReport {
satisfied: true,
reason: None,
levels_checked,
lp_solves: counter.solves,
})
}
fn is_balanced(
collection: &[Coalition],
optional: &[Coalition],
n: usize,
counter: &mut Counter,
) -> Result<bool> {
let mut problem = lp::minimize();
let mu = problem.add_var(1.0, (0.0, f64::INFINITY));
let mut weights = Vec::with_capacity(collection.len() + optional.len());
for coalition in collection {
weights.push((*coalition, problem.add_var(0.0, (1.0, f64::INFINITY))));
}
for coalition in optional {
if !collection.contains(coalition) {
weights.push((*coalition, problem.add_var(0.0, (0.0, f64::INFINITY))));
}
}
for player in 0..n {
let mut terms: Vec<_> = weights
.iter()
.filter(|(coalition, _)| coalition.contains(player))
.map(|(_, var)| (*var, 1.0))
.collect();
terms.push((mu, -1.0));
lp::add(&mut problem, terms, Cmp::Eq, 0.0);
}
Ok(counter.solve(&problem)?.is_some())
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn accepts_nucleolus_and_rejects_other_points() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 4.0, 0.0, 0.0, 4.0]).unwrap();
assert!(
kohlberg(&game, &[2.0, 2.0, 0.0], Domain::Imputation)
.unwrap()
.satisfied
);
let report = kohlberg(&game, &[1.0, 3.0, 0.0], Domain::Imputation).unwrap();
assert!(!report.satisfied);
let report = kohlberg(&game, &[2.0, 2.0, 1.0], Domain::Imputation).unwrap();
assert!(report.reason.unwrap().contains("効率性"));
}
#[test]
fn majority_game() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]).unwrap();
let third = 1.0 / 3.0;
assert!(
kohlberg(&game, &[third; 3], Domain::Preimputation)
.unwrap()
.satisfied
);
assert!(
!kohlberg(&game, &[0.5, 0.25, 0.25], Domain::Preimputation)
.unwrap()
.satisfied
);
}
}