use crate::game::{Coalition, ExplicitGame, excess_table};
pub fn excesses(game: &ExplicitGame, x: &[f64]) -> Vec<(Coalition, f64)> {
excess_table(game, x)
.into_iter()
.enumerate()
.skip(1)
.map(|(mask, e)| (Coalition(mask as u64), e))
.collect()
}
pub fn excess_order(game: &ExplicitGame, x: &[f64]) -> Vec<(Coalition, f64)> {
let mut order = excesses(game, x);
order.pop(); order.sort_by(|a, b| b.1.total_cmp(&a.1).then_with(|| a.0.cmp(&b.0)));
order
}
pub fn excess(game: &ExplicitGame, coalition: Coalition, x: &[f64]) -> f64 {
game.value(coalition) - coalition.sum(x)
}
pub fn max_surplus(game: &ExplicitGame, x: &[f64]) -> Vec<Vec<f64>> {
let n = game.players();
max_surplus_flat(game, x)
.chunks(n)
.map(<[f64]>::to_vec)
.collect()
}
pub(crate) fn max_surplus_flat(game: &ExplicitGame, x: &[f64]) -> Vec<f64> {
let n = game.players();
let excess = excess_table(game, x);
let full = (1usize << n) - 1;
let mut surplus = vec![f64::NEG_INFINITY; n * n];
let mut order: Vec<u32> = (1..full as u32).collect();
let mut remaining = n * (n - 1);
let mut scanned = 0;
let mut k = (4 * n * n).min(order.len());
while remaining > 0 && scanned < order.len() {
let rest = &mut order[scanned..];
let take = k - scanned;
let by_excess_desc = |a: &u32, b: &u32| excess[*b as usize].total_cmp(&excess[*a as usize]);
if take < rest.len() {
rest.select_nth_unstable_by(take - 1, by_excess_desc);
}
rest[..take].sort_unstable_by(by_excess_desc);
for &mask in &order[scanned..k] {
let e = excess[mask as usize];
let inside = Coalition(u64::from(mask));
let outside = inside.complement(n);
for i in inside.members() {
let row = &mut surplus[i * n..(i + 1) * n];
for j in outside.members() {
if row[j] == f64::NEG_INFINITY {
row[j] = e;
remaining -= 1;
}
}
}
if remaining == 0 {
break;
}
}
scanned = k;
k = (4 * k).min(order.len());
}
surplus
}
#[cfg(test)]
fn max_surplus_naive(game: &ExplicitGame, x: &[f64]) -> Vec<f64> {
let n = game.players();
let excess = excess_table(game, x);
let full = (1usize << n) - 1;
let mut surplus = vec![f64::NEG_INFINITY; n * n];
for (mask, &e) in excess.iter().enumerate().take(full).skip(1) {
let inside = Coalition(mask as u64);
let outside = inside.complement(n);
for i in inside.members() {
for j in outside.members() {
surplus[i * n + j] = surplus[i * n + j].max(e);
}
}
}
surplus
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn partial_sort_matches_definition() {
use crate::generators;
for kind in 1..=4 {
for n in 4..=9 {
let game = generators::bnf(kind, n, 3).unwrap();
let x = crate::kernel::equal_surplus_division(&game);
assert_eq!(
max_surplus_flat(&game, &x),
max_surplus_naive(&game, &x),
"type {kind} n={n}"
);
}
}
}
#[test]
fn surplus_of_three_player_game() {
let game = ExplicitGame::from_binary(&[0.0, 0.0, 4.0, 0.0, 0.0, 0.0, 4.0]).unwrap();
let x = [1.0, 3.0, 0.0];
let s = max_surplus(&game, &x);
assert_eq!(s[0][2], 0.0);
assert_eq!(s[2][0], 0.0);
assert_eq!(s[0][1], -1.0);
assert_eq!(s[1][0], -3.0);
assert_eq!(s[0][0], f64::NEG_INFINITY);
}
#[test]
fn excesses_list_nonempty_coalitions_in_bit_order() {
let game = ExplicitGame::from_binary(&[0.0, 0.0, 4.0, 0.0, 0.0, 0.0, 4.0]).unwrap();
let all = excesses(&game, &[1.0, 3.0, 0.0]);
assert_eq!(all.len(), 7);
assert_eq!(all[0], (Coalition::from_players(&[0]), -1.0));
assert_eq!(all[2], (Coalition::from_players(&[0, 1]), 0.0));
assert_eq!(all[6], (Coalition::grand(3), 0.0));
}
}