mod proof;
pub use proof::{Assume, Assumed, ConvexChecked, ConvexGame, Convexity, ProofKind, Proven};
use crate::game::allocation::allocation_defect;
use crate::game::{Coalition, ExplicitGame, default_tolerance};
pub fn is_superadditive(game: &ExplicitGame) -> bool {
let tolerance = default_tolerance(game);
let full = game.grand().0;
(1..=full).all(|union| {
let mut s = (union - 1) & union;
while s > 0 {
let t = union & !s;
if s < t
&& game.value(Coalition(union))
< game.value(Coalition(s)) + game.value(Coalition(t)) - tolerance
{
return false;
}
s = (s - 1) & union;
}
true
})
}
pub fn is_convex(game: &ExplicitGame) -> bool {
let tolerance = default_tolerance(game);
let n = game.players();
let full = game.grand().0;
(0..=full).all(|s| {
(0..n).all(|i| {
(0..n).all(|j| {
let (bi, bj) = (1u64 << i, 1u64 << j);
if i == j || s & (bi | bj) != 0 {
return true;
}
let without = game.value(Coalition(s | bi)) - game.value(Coalition(s));
let with = game.value(Coalition(s | bi | bj)) - game.value(Coalition(s | bj));
with >= without - tolerance
})
})
})
}
pub fn is_zero_monotonic(game: &ExplicitGame) -> bool {
let tolerance = default_tolerance(game);
let n = game.players();
let full = game.grand().0;
(1..=full).all(|s| {
(0..n).all(|i| {
let bit = 1u64 << i;
s & bit != 0
|| game.value(Coalition(s | bit))
>= game.value(Coalition(s)) + game.value(Coalition(bit)) - tolerance
})
})
}
pub fn is_in_core(game: &ExplicitGame, x: &[f64], tolerance: f64) -> bool {
if allocation_defect(game.players(), x).is_some() {
return false;
}
let total: f64 = x.iter().sum();
if (total - game.value(game.grand())).abs() > tolerance {
return false;
}
crate::game::excess_table(game, x)
.iter()
.all(|e| *e <= tolerance)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::generators;
#[test]
fn classifies_known_games() {
let convex = generators::random_convex(4, 1).unwrap();
assert!(is_convex(&convex));
assert!(is_superadditive(&convex));
assert!(is_zero_monotonic(&convex));
let majority = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]).unwrap();
assert!(is_superadditive(&majority));
assert!(!is_convex(&majority));
let broken = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 5.0, 0.0, 0.0, 4.0]).unwrap();
assert!(!is_superadditive(&broken));
assert!(!is_zero_monotonic(&broken));
}
#[test]
fn superadditive_generator() {
for seed in 0..5 {
let game = generators::random_superadditive(5, seed).unwrap();
assert!(is_superadditive(&game), "seed={seed}");
}
}
}