use std::fmt::Write as _;
use crate::Domain;
use crate::error::{Error, Result};
use crate::game::excess_table;
use crate::game::{Coalition, ExplicitGame, default_tolerance};
use crate::nucleolus;
#[derive(Clone, Copy, Debug, PartialEq)]
#[non_exhaustive]
pub struct ExplainOptions {
pub levels: usize,
pub max_listed: usize,
pub tolerance: Option<f64>,
}
impl Default for ExplainOptions {
fn default() -> ExplainOptions {
ExplainOptions {
levels: 3,
max_listed: 10,
tolerance: None,
}
}
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct Level {
pub excess: f64,
pub count: usize,
pub coalitions: Vec<Coalition>,
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct PlayerReport {
pub player: usize,
pub payoff: f64,
pub standalone: f64,
pub gain: f64,
pub worst_with: (Coalition, f64),
pub worst_without: (Coalition, f64),
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct Report {
pub allocation: Vec<f64>,
pub efficiency_gap: f64,
pub max_excess: f64,
pub least_core_epsilon: f64,
pub in_core: bool,
pub levels: Vec<Level>,
pub players: Vec<PlayerReport>,
}
fn check_length(game: &ExplicitGame, x: &[f64]) -> Result<()> {
if x.len() != game.players() {
return Err(Error::InvalidArgument(format!(
"配分の長さ {} がプレイヤー数 {} と異なる",
x.len(),
game.players()
)));
}
Ok(())
}
pub fn report(game: &ExplicitGame, x: &[f64], options: ExplainOptions) -> Result<Report> {
let n = game.players();
check_length(game, x)?;
let tolerance = options
.tolerance
.unwrap_or_else(|| 10.0 * default_tolerance(game));
let full = game.grand().0;
let excess = excess_table(game, x);
let mut order: Vec<u64> = (1..full).collect();
order.sort_by(|a, b| {
excess[*b as usize]
.total_cmp(&excess[*a as usize])
.then(a.cmp(b))
});
let mut levels: Vec<Level> = Vec::new();
for &mask in &order {
let value = excess[mask as usize];
match levels.last_mut() {
Some(level) if level.excess - value <= tolerance => {
level.count += 1;
if level.coalitions.len() < options.max_listed {
level.coalitions.push(Coalition(mask));
}
}
_ => {
if levels.len() == options.levels {
break;
}
levels.push(Level {
excess: value,
count: 1,
coalitions: vec![Coalition(mask)],
});
}
}
}
let max_excess = order
.first()
.map_or(f64::NEG_INFINITY, |&mask| excess[mask as usize]);
let efficiency_gap = x.iter().sum::<f64>() - game.value(game.grand());
let least_core_epsilon = nucleolus::least_core(game, Domain::Preimputation)?.epsilon;
let players = (0..n)
.map(|i| {
let worst = |contains: bool| {
(1..=full)
.filter(|&mask| (mask >> i & 1 == 1) == contains && (mask != full || !contains))
.map(|mask| (Coalition(mask), excess[mask as usize]))
.max_by(|a, b| a.1.total_cmp(&b.1).then(b.0.0.cmp(&a.0.0)))
.unwrap_or((Coalition(0), f64::NEG_INFINITY))
};
let standalone = game.value(Coalition::singleton(i));
PlayerReport {
player: i,
payoff: x[i],
standalone,
gain: x[i] - standalone,
worst_with: worst(true),
worst_without: worst(false),
}
})
.collect();
Ok(Report {
allocation: x.to_vec(),
efficiency_gap,
max_excess,
least_core_epsilon,
in_core: efficiency_gap.abs() <= tolerance && max_excess <= tolerance,
levels,
players,
})
}
pub fn render(report: &Report) -> String {
let mut out = String::new();
let _ = writeln!(out, "配分:");
for p in &report.players {
let _ = writeln!(
out,
" プレイヤー {}: {:.6} (単独の値 {:.6}、協力による増分 {:+.6})",
p.player, p.payoff, p.standalone, p.gain
);
}
if report.efficiency_gap.abs() > 1e-9 {
let _ = writeln!(
out,
"注意: 配分の和が v(N) と {:+.6} 異なる (配分になっていない)",
report.efficiency_gap
);
}
let _ = writeln!(out, "\n安定性:");
let _ = writeln!(
out,
" 最大の不満 (超過) は {:.6}。{}",
report.max_excess,
if report.in_core {
"どの提携も離脱して得をしないので、コアに属する。"
} else {
"正の超過を持つ提携は離脱すると得をするので、コアに属さない。"
}
);
let _ = writeln!(
out,
" 最小コアの値は {:.6}。最大の不満をこれより下げられる配分はない{}。",
report.least_core_epsilon,
if (report.max_excess - report.least_core_epsilon).abs()
<= 1e-7 * report.max_excess.abs().max(1.0)
{
" (この配分は最大の不満を最小にしている)"
} else {
""
}
);
let _ = writeln!(out, "\n不満の大きい提携 (超過の大きい順の段):");
for (k, level) in report.levels.iter().enumerate() {
let listed: Vec<String> = level.coalitions.iter().map(Coalition::to_string).collect();
let more = if level.count > level.coalitions.len() {
format!(" ほか {} 個", level.count - level.coalitions.len())
} else {
String::new()
};
let _ = writeln!(
out,
" 段 {}: 超過 {:.6} の提携 {}{more}",
k + 1,
level.excess,
listed.join(" ")
);
}
let _ = writeln!(out, "\nプレイヤーごとの最も不満な提携:");
for p in &report.players {
let _ = writeln!(
out,
" プレイヤー {}: 含む提携 {} (超過 {:.6})、含まない提携 {} (超過 {:.6})",
p.player, p.worst_with.0, p.worst_with.1, p.worst_without.0, p.worst_without.1
);
}
out
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct Comparison {
pub allocation: Vec<f64>,
pub max_excess: f64,
pub in_core: bool,
pub blocking_coalitions: usize,
}
pub fn compare(game: &ExplicitGame, candidates: &[Vec<f64>]) -> Result<Vec<Comparison>> {
let tolerance = 10.0 * default_tolerance(game);
candidates
.iter()
.map(|x| {
check_length(game, x)?;
let all = excess_table(game, x);
let proper = &all[1..game.grand().index()];
let max_excess = proper.iter().copied().fold(f64::NEG_INFINITY, f64::max);
let efficiency_gap = x.iter().sum::<f64>() - game.value(game.grand());
Ok(Comparison {
allocation: x.clone(),
max_excess,
in_core: efficiency_gap.abs() <= tolerance && max_excess <= tolerance,
blocking_coalitions: proper.iter().filter(|&&e| e > tolerance).count(),
})
})
.collect()
}
pub fn render_comparison(rows: &[Comparison]) -> String {
let mut out = String::new();
let n = rows.first().map_or(0, |r| r.allocation.len());
let header: Vec<String> = (0..n).map(|i| format!("プレイヤー {i}")).collect();
let _ = writeln!(
out,
"解\t{}\t最大の不満\tコア\t離脱で得をする提携の数",
header.join("\t")
);
for (k, row) in rows.iter().enumerate() {
let values: Vec<String> = row.allocation.iter().map(|v| format!("{v:.6}")).collect();
let _ = writeln!(
out,
"{k}\t{}\t{:.6}\t{}\t{}",
values.join("\t"),
row.max_excess,
if row.in_core {
"属する"
} else {
"属さない"
},
row.blocking_coalitions
);
}
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn explains_nucleolus_of_pair_game() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 4.0, 0.0, 0.0, 4.0]).unwrap();
let x = nucleolus::nucleolus(&game).unwrap().allocation;
let report = report(&game, &x, ExplainOptions::default()).unwrap();
assert!(report.in_core);
assert!(report.max_excess.abs() < 1e-9);
assert!((report.least_core_epsilon - report.max_excess).abs() < 1e-9);
assert!(
report.levels[0]
.coalitions
.contains(&Coalition::from_players(&[0, 1]))
);
let text = render(&report);
assert!(text.contains("コアに属する"), "{text}");
assert!(text.contains("{0, 1}"), "{text}");
}
#[test]
fn detects_blocking_coalitions() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]).unwrap();
let rows = compare(&game, &[vec![1.0 / 3.0; 3], vec![0.5, 0.5, 0.0]]).unwrap();
assert!(!rows[0].in_core && !rows[1].in_core);
assert_eq!(rows[0].blocking_coalitions, 3);
assert_eq!(rows[1].blocking_coalitions, 2);
assert!((rows[0].max_excess - 1.0 / 3.0).abs() < 1e-9);
let report = report(&game, &[0.5, 0.5, 0.0], ExplainOptions::default()).unwrap();
assert!((report.players[2].worst_with.1 - 0.5).abs() < 1e-9);
}
}