use microlp::Variable;
use crate::Domain;
use crate::error::{Error, Result};
use crate::game::allocation::feasibility_violation;
use crate::game::{Coalition, ExplicitGame, default_tolerance};
use crate::lp::{self, Cmp, Counter};
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct Objection {
pub objector: usize,
pub target: usize,
pub coalition: Coalition,
pub payoff: Vec<f64>,
pub margin: f64,
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct BargainingReport {
pub objection: Option<Objection>,
pub lp_solves: usize,
}
impl BargainingReport {
pub fn is_member(&self) -> bool {
self.objection.is_none()
}
}
pub fn check(
game: &ExplicitGame,
x: &[f64],
domain: Domain,
tolerance: f64,
) -> Result<BargainingReport> {
let n = game.players();
if x.len() != n {
return Err(Error::InvalidArgument(format!(
"配分の長さ {} がプレイヤー数 {n} と異なる",
x.len()
)));
}
if let Some(reason) = feasibility_violation(game, x, domain, tolerance) {
return Err(Error::InvalidArgument(format!("配分が不正: {reason}")));
}
let mut counter = Counter::default();
let grand = game.grand();
for objector in 0..n {
for target in 0..n {
if objector == target {
continue;
}
for mask in 1..grand.0 {
let coalition = Coalition(mask);
if !coalition.contains(objector) || coalition.contains(target) {
continue;
}
let excess = game.value(coalition) - coalition.sum(x);
if excess <= tolerance {
continue;
}
if let Some((margin, payoff)) =
best_objection(game, x, objector, target, coalition, &mut counter)?
&& margin > tolerance
{
return Ok(BargainingReport {
objection: Some(Objection {
objector,
target,
coalition,
payoff,
margin,
}),
lp_solves: counter.solves,
});
}
}
}
}
Ok(BargainingReport {
objection: None,
lp_solves: counter.solves,
})
}
pub fn is_in_bargaining_set(game: &ExplicitGame, x: &[f64], domain: Domain) -> Result<bool> {
Ok(check(game, x, domain, 10.0 * default_tolerance(game))?.is_member())
}
fn best_objection(
game: &ExplicitGame,
x: &[f64],
objector: usize,
target: usize,
coalition: Coalition,
counter: &mut Counter,
) -> Result<Option<(f64, Vec<f64>)>> {
let n = game.players();
let mut problem = lp::maximize();
let y: Vec<Option<Variable>> = (0..n)
.map(|k| {
coalition
.contains(k)
.then(|| problem.add_var(0.0, (f64::NEG_INFINITY, f64::INFINITY)))
})
.collect();
let delta = problem.add_var(1.0, (f64::NEG_INFINITY, f64::INFINITY));
let members: Vec<(Variable, f64)> = y.iter().flatten().map(|&var| (var, 1.0)).collect();
lp::add(&mut problem, members, Cmp::Eq, game.value(coalition));
for (k, var) in y.iter().enumerate() {
if let Some(var) = var {
lp::add(
&mut problem,
vec![(*var, 1.0), (delta, -1.0)],
Cmp::Ge,
x[k],
);
}
}
for mask in 1..=game.grand().0 {
let counter_coalition = Coalition(mask);
if !counter_coalition.contains(target) || counter_coalition.contains(objector) {
continue;
}
let mut terms: Vec<(Variable, f64)> = Vec::new();
let mut outside = 0.0;
for k in counter_coalition.members() {
match y[k] {
Some(var) => terms.push((var, 1.0)),
None => outside += x[k],
}
}
terms.push((delta, -1.0));
lp::add(
&mut problem,
terms,
Cmp::Ge,
game.value(counter_coalition) - outside,
);
}
Ok(counter.solve(&problem)?.map(|solution| {
let payoff = (0..n)
.map(|k| y[k].map_or(x[k], |var| solution[var]))
.collect();
(solution[delta], payoff)
}))
}
#[cfg(test)]
mod tests {
use super::*;
fn majority() -> ExplicitGame {
ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]).unwrap()
}
#[test]
fn three_player_majority_game() {
let game = majority();
assert!(is_in_bargaining_set(&game, &[1.0 / 3.0; 3], Domain::Imputation).unwrap());
let report = check(&game, &[0.5, 0.5, 0.0], Domain::Imputation, 1e-9).unwrap();
let objection = report.objection.expect("正当な異議がある");
assert_eq!((objection.objector, objection.target), (2, 0));
assert_eq!(objection.coalition, Coalition::from_players(&[1, 2]));
let report = check(&game, &[0.6, 0.4, 0.0], Domain::Imputation, 1e-9).unwrap();
let objection = report.objection.expect("正当な異議がある");
assert_eq!((objection.objector, objection.target), (1, 0));
assert_eq!(objection.coalition, Coalition::from_players(&[1, 2]));
assert!(objection.payoff[1] > 0.4 && objection.payoff[2] > 0.4);
}
#[test]
fn rejects_infeasible_allocations() {
let game = majority();
assert!(check(&game, &[0.5, 0.5], Domain::Imputation, 1e-9).is_err());
assert!(check(&game, &[0.5, 0.6, 0.0], Domain::Imputation, 1e-9).is_err());
assert!(check(&game, &[1.5, -0.5, 0.0], Domain::Imputation, 1e-9).is_err());
assert!(check(&game, &[1.5, -0.5, 0.0], Domain::Preimputation, 1e-9).is_ok());
}
}