use crate::error::{Error, Result};
use crate::game::{Coalition, ExplicitGame, PlayerSet, SetFunction};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Domain {
Preimputation,
Imputation,
}
pub(crate) fn coalition_sums(x: &[f64]) -> Vec<f64> {
let size = 1usize << x.len();
let mut sums = vec![0.0; size];
for mask in 1..size {
let lowest = mask.trailing_zeros() as usize;
sums[mask] = sums[mask & (mask - 1)] + x[lowest];
}
sums
}
pub(crate) fn excess_table(game: &ExplicitGame, x: &[f64]) -> Vec<f64> {
assert_eq!(
x.len(),
game.players(),
"配分の長さ {} がプレイヤー数 {} と異なる",
x.len(),
game.players()
);
let mut excess = coalition_sums(x);
for (e, value) in excess.iter_mut().zip(game.values()) {
*e = value - *e;
}
excess
}
pub(crate) fn allocation_defect(n: usize, x: &[f64]) -> Option<String> {
if x.len() != n {
return Some(format!(
"配分の長さ {} がプレイヤー数 {n} と異なる",
x.len()
));
}
x.iter()
.position(|v| !v.is_finite())
.map(|i| format!("x_{i} = {} は有限でない", x[i]))
}
pub(crate) fn feasibility_violation<G: SetFunction + ?Sized>(
game: &G,
x: &[f64],
domain: Domain,
tolerance: f64,
) -> Option<String> {
let n = game.players();
if let Some(defect) = allocation_defect(n, x) {
return Some(defect);
}
let total: f64 = x.iter().sum();
let grand = game.value(&PlayerSet::grand(n));
if !at_most((total - grand).abs(), tolerance) {
return Some(format!(
"効率性を満たさない: x(N) = {total}, v(N) = {grand}"
));
}
if domain == Domain::Imputation {
for (i, xi) in x.iter().enumerate() {
let lower = game.value(&PlayerSet::singleton(n, i));
if !at_most(lower - tolerance, *xi) {
return Some(format!(
"個人合理性を満たさない: x_{i} = {xi} < v({{{i}}}) = {lower}"
));
}
}
}
None
}
fn at_most(a: f64, b: f64) -> bool {
a <= b
}
pub(crate) fn check_imputation_set<G: SetFunction + ?Sized>(
game: &G,
domain: Domain,
tolerance: f64,
) -> Result<()> {
let grand = PlayerSet::grand(game.players());
lower_bounds(game, &[grand], domain, tolerance).map(|_| ())
}
pub(crate) fn lower_bounds<G: SetFunction + ?Sized>(
game: &G,
blocks: &[PlayerSet],
domain: Domain,
tolerance: f64,
) -> Result<Option<Vec<f64>>> {
if domain == Domain::Preimputation {
return Ok(None);
}
let n = game.players();
let mut lower: Vec<f64> = (0..n)
.map(|i| game.value(&PlayerSet::singleton(n, i)))
.collect();
for block in blocks {
let sum: f64 = block.members().map(|i| lower[i]).sum();
let gap = sum - game.value(block);
if gap > tolerance {
return Err(Error::EmptyImputationSet);
}
if gap > 0.0 {
let share = gap / block.len() as f64;
for i in block.members() {
lower[i] -= share;
}
}
}
Ok(Some(lower))
}
pub(crate) fn block_lower_bounds(
game: &ExplicitGame,
blocks: &[Coalition],
domain: Domain,
tolerance: f64,
) -> Result<Option<Vec<f64>>> {
let n = game.players();
let blocks: Vec<PlayerSet> = blocks
.iter()
.map(|&block| PlayerSet::from_coalition(n, block))
.collect();
lower_bounds(game, &blocks, domain, tolerance)
}