use microlp::{Problem, Variable};
use crate::Domain;
use crate::error::{Error, Result};
use crate::game::allocation::lower_bounds;
use crate::game::scale::normalizer;
use crate::game::{Coalition, ExplicitGame, PlayerSet, default_tolerance};
use crate::linalg::{Span, indicator};
use crate::lp::{self, Cmp, Counter};
use crate::solution::Guarantee;
pub const MAX_MODICLUS_PLAYERS: usize = 7;
#[derive(Clone, Debug, PartialEq)]
pub struct Complaint {
pub coefficients: Vec<f64>,
pub constant: f64,
pub weight: f64,
}
impl Complaint {
pub fn value(&self, x: &[f64]) -> f64 {
(self.constant - dot(&self.coefficients, x)) / self.weight
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct Feasible {
pub total: f64,
pub lower: Option<Vec<f64>>,
pub constraints: Vec<(Vec<f64>, f64)>,
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct LexicographicResult {
pub(crate) allocation: Vec<f64>,
pub(crate) levels: Vec<f64>,
pub(crate) lp_solves: usize,
pub(crate) guarantee: Guarantee,
}
impl LexicographicResult {
pub fn allocation(&self) -> &[f64] {
&self.allocation
}
pub fn into_allocation(self) -> Vec<f64> {
self.allocation
}
pub fn levels(&self) -> &[f64] {
&self.levels
}
pub fn lp_solves(&self) -> usize {
self.lp_solves
}
pub fn guarantee(&self) -> Guarantee {
self.guarantee
}
}
pub fn lexicographic_minimum(
players: usize,
feasible: &Feasible,
complaints: &[Complaint],
tolerance: f64,
) -> Result<LexicographicResult> {
if players == 0 {
return Err(Error::InvalidArgument("プレイヤーが 0 人".into()));
}
if complaints.iter().any(|c| {
c.coefficients.len() != players
|| !c.weight.is_finite()
|| c.weight <= 0.0
|| !c.constant.is_finite()
}) {
return Err(Error::InvalidArgument(
"不満の係数の長さがプレイヤー数と異なるか、重みが正でない".into(),
));
}
let constants = complaints
.iter()
.map(|c| c.constant)
.chain(std::iter::once(feasible.total))
.chain(feasible.lower.iter().flatten().copied())
.chain(feasible.constraints.iter().map(|(_, b)| *b))
.filter(|v| v.is_finite())
.fold(0.0, |acc: f64, v| acc.max(v.abs()));
let weights = complaints.iter().fold(0.0, |acc: f64, c| acc.max(c.weight));
let (value_divisor, weight_divisor) = (normalizer(constants), normalizer(weights));
let normalized_feasible = Feasible {
total: feasible.total / value_divisor,
lower: feasible
.lower
.as_ref()
.map(|lower| lower.iter().map(|v| v / value_divisor).collect()),
constraints: feasible
.constraints
.iter()
.map(|(a, b)| (a.clone(), b / value_divisor))
.collect(),
};
let normalized_complaints: Vec<Complaint> = complaints
.iter()
.map(|c| Complaint {
coefficients: c.coefficients.clone(),
constant: c.constant / value_divisor,
weight: c.weight / weight_divisor,
})
.collect();
let mut solver = Lexicographic {
n: players,
feasible: &normalized_feasible,
complaints: &normalized_complaints,
tolerance: tolerance / value_divisor,
open: (0..complaints.len()).collect(),
fixed: Vec::new(),
span: Span::new(players),
counter: Counter::default(),
};
solver.span.insert(&vec![1.0; players]);
solver.drop_determined();
let mut result = solver.run()?;
for value in &mut result.allocation {
*value *= value_divisor;
}
for level in &mut result.levels {
*level *= value_divisor / weight_divisor;
}
Ok(result)
}
struct Lexicographic<'a> {
n: usize,
feasible: &'a Feasible,
complaints: &'a [Complaint],
tolerance: f64,
open: Vec<usize>,
fixed: Vec<(usize, f64)>,
span: Span,
counter: Counter,
}
impl Lexicographic<'_> {
fn run(mut self) -> Result<LexicographicResult> {
if let Some(point) = self.single_point() {
return Ok(LexicographicResult {
allocation: point,
levels: Vec::new(),
lp_solves: 0,
guarantee: Guarantee::Exact,
});
}
let mut levels = Vec::new();
let mut allocation = match self.open.is_empty() {
true => self.any_feasible()?,
false => Vec::new(),
};
while !self.open.is_empty() {
let (level, x) = self.minimize_max_complaint()?;
levels.push(level);
self.fix_tight(level, &x)?;
self.drop_determined();
allocation = x;
}
if !self.span.is_full() && !self.is_unique()? {
return Err(Error::InvalidArgument(
"不満の係数が R^n を張らず、辞書式最小の配分が一意に定まらない".into(),
));
}
Ok(LexicographicResult {
allocation,
levels,
lp_solves: self.counter.solves,
guarantee: Guarantee::Exact,
})
}
fn single_point(&self) -> Option<Vec<f64>> {
let lower = self.feasible.lower.as_ref()?;
let sum: f64 = lower.iter().sum();
let magnitude = lower
.iter()
.fold(self.feasible.total.abs(), |acc, v| acc.max(v.abs()));
let rounding = 4.0 * f64::EPSILON * self.n as f64 * magnitude;
let feasible = (sum - self.feasible.total).abs() <= rounding
&& self
.feasible
.constraints
.iter()
.all(|(a, b)| dot(a, lower) >= b - self.tolerance);
feasible.then(|| lower.clone())
}
fn drop_determined(&mut self) {
let span = &self.span;
let complaints = self.complaints;
self.open
.retain(|&k| !span.contains(&complaints[k].coefficients));
}
fn add_domain(&self, problem: &mut Problem, objective: Option<&[f64]>) -> Vec<Variable> {
let x: Vec<Variable> = (0..self.n)
.map(|i| {
let lower = self
.feasible
.lower
.as_ref()
.map_or(f64::NEG_INFINITY, |lower| lower[i]);
let coefficient = objective.map_or(0.0, |a| a[i]);
problem.add_var(coefficient, (lower, f64::INFINITY))
})
.collect();
lp::add(
problem,
x.iter().map(|&var| (var, 1.0)).collect(),
Cmp::Eq,
self.feasible.total,
);
for (a, b) in &self.feasible.constraints {
lp::add(problem, terms(&x, a), Cmp::Ge, *b);
}
for &(k, level) in &self.fixed {
let complaint = &self.complaints[k];
lp::add(
problem,
terms(&x, &complaint.coefficients),
Cmp::Eq,
complaint.constant - complaint.weight * level,
);
}
x
}
fn any_feasible(&mut self) -> Result<Vec<f64>> {
let mut problem = lp::minimize();
let x = self.add_domain(&mut problem, None);
let solution = self
.counter
.solve(&problem)?
.ok_or_else(|| Error::InvalidArgument("配分の集合が空".into()))?;
Ok(x.iter().map(|&var| solution[var]).collect())
}
fn is_unique(&mut self) -> Result<bool> {
for i in 0..self.n {
let mut direction = vec![0.0; self.n];
direction[i] = 1.0;
let mut range = [0.0; 2];
for (slot, sign) in [1.0, -1.0].into_iter().enumerate() {
let mut problem = lp::maximize();
let objective: Vec<f64> = direction.iter().map(|d| sign * d).collect();
let x = self.add_domain(&mut problem, Some(&objective));
self.add_open_rows(&mut problem, &x, Row::Unbounded);
match self.counter.solve_bounded(&problem)? {
Some(solution) => range[slot] = sign * solution.objective(),
None => return Ok(false),
}
}
if range[0] - range[1] > 10.0 * self.tolerance {
return Ok(false);
}
}
Ok(true)
}
fn add_open_rows(&self, problem: &mut Problem, x: &[Variable], row: Row) {
for &k in &self.open {
let complaint = &self.complaints[k];
let mut row_terms = terms(x, &complaint.coefficients);
let rhs = match row {
Row::WithLevel(t) => {
row_terms.push((t, complaint.weight));
complaint.constant
}
Row::Unbounded => continue,
Row::AtMost { level, relax } => {
complaint.constant - complaint.weight * level - relax
}
};
lp::add(problem, row_terms, Cmp::Ge, rhs);
}
}
fn minimize_max_complaint(&mut self) -> Result<(f64, Vec<f64>)> {
let mut problem = lp::minimize();
let x = self.add_domain(&mut problem, None);
let t = problem.add_var(1.0, (f64::NEG_INFINITY, f64::INFINITY));
self.add_open_rows(&mut problem, &x, Row::WithLevel(t));
let solution = self
.counter
.solve_bounded(&problem)?
.ok_or_else(|| Error::Numerical("不満の最大値が下に有界でない".into()))?;
Ok((solution[t], x.iter().map(|&var| solution[var]).collect()))
}
fn maximize_direction(&mut self, a: &[f64], level: f64) -> Result<(f64, Vec<f64>)> {
let mut problem = lp::maximize();
let x = self.add_domain(&mut problem, Some(a));
let relax = 0.01 * self.tolerance;
self.add_open_rows(&mut problem, &x, Row::AtMost { level, relax });
let solution = self
.counter
.solve_bounded(&problem)?
.ok_or_else(|| Error::Numerical("確定判定の LP が非有界".into()))?;
Ok((
solution.objective(),
x.iter().map(|&var| solution[var]).collect(),
))
}
fn deviation(&self, k: usize, x: &[f64], level: f64) -> f64 {
let complaint = &self.complaints[k];
complaint.constant - dot(&complaint.coefficients, x) - complaint.weight * level
}
fn fix_tight(&mut self, level: f64, x: &[f64]) -> Result<()> {
let tight: Vec<usize> = self
.open
.iter()
.copied()
.filter(|&k| self.deviation(k, x, level).abs() <= self.tolerance)
.collect();
let mut not_fixed = vec![false; tight.len()];
let mut progressed = false;
for position in 0..tight.len() {
let k = tight[position];
let complaint = &self.complaints[k];
if not_fixed[position] || self.span.contains(&complaint.coefficients) {
continue;
}
let fixed_value = complaint.constant - complaint.weight * level;
let (max_value, witness) = self.maximize_direction(&complaint.coefficients, level)?;
if max_value <= fixed_value + self.tolerance {
self.fixed.push((k, level));
self.span.insert(&complaint.coefficients);
progressed = true;
} else {
for (later, flag) in tight.iter().zip(not_fixed.iter_mut()).skip(position + 1) {
if self.deviation(*later, &witness, level) < -self.tolerance {
*flag = true;
}
}
}
}
if !progressed {
return Err(Error::Numerical(format!(
"不満の最大値 {level} の段で確定する不満が見つからない (許容誤差 {} を見直す)",
self.tolerance
)));
}
let fixed: Vec<usize> = self.fixed.iter().map(|&(k, _)| k).collect();
self.open.retain(|k| !fixed.contains(k));
Ok(())
}
}
#[derive(Clone, Copy)]
enum Row {
WithLevel(Variable),
AtMost { level: f64, relax: f64 },
Unbounded,
}
fn terms(x: &[Variable], a: &[f64]) -> Vec<(Variable, f64)> {
x.iter()
.zip(a)
.filter(|(_, coefficient)| **coefficient != 0.0)
.map(|(&var, &coefficient)| (var, coefficient))
.collect()
}
fn dot(a: &[f64], b: &[f64]) -> f64 {
a.iter().zip(b).map(|(p, q)| p * q).sum()
}
fn proper_coalitions(game: &ExplicitGame) -> impl Iterator<Item = Coalition> {
(1..game.grand().0).map(Coalition)
}
fn feasible_set(game: &ExplicitGame, domain: Domain) -> Result<Feasible> {
let grand = PlayerSet::grand(game.players());
Ok(Feasible {
total: game.value(game.grand()),
lower: lower_bounds(game, &[grand], domain, default_tolerance(game))?,
constraints: Vec::new(),
})
}
fn excess_complaint(game: &ExplicitGame, coalition: Coalition, weight: f64) -> Complaint {
Complaint {
coefficients: indicator(coalition, game.players()),
constant: game.value(coalition),
weight,
}
}
#[cfg(test)]
fn nucleolus_by_complaints(game: &ExplicitGame, domain: Domain) -> Result<LexicographicResult> {
let feasible = feasible_set(game, domain)?;
let complaints: Vec<Complaint> = proper_coalitions(game)
.map(|s| excess_complaint(game, s, 1.0))
.collect();
lexicographic_minimum(
game.players(),
&feasible,
&complaints,
default_tolerance(game),
)
}
pub fn per_capita_nucleolus(game: &ExplicitGame, domain: Domain) -> Result<LexicographicResult> {
let feasible = feasible_set(game, domain)?;
let complaints: Vec<Complaint> = proper_coalitions(game)
.map(|s| excess_complaint(game, s, s.len() as f64))
.collect();
lexicographic_minimum(
game.players(),
&feasible,
&complaints,
default_tolerance(game),
)
}
pub fn disruption_nucleolus(game: &ExplicitGame) -> Result<LexicographicResult> {
let n = game.players();
let tolerance = default_tolerance(game);
if !crate::nucleolus::has_nonempty_core(game)? {
return Err(Error::InvalidArgument(
"disruption nucleolus はコアが空でないゲームに限る".into(),
));
}
let total = game.value(game.grand());
let mut feasible = Feasible {
total,
lower: None,
constraints: Vec::new(),
};
let mut complaints = Vec::new();
for s in proper_coalitions(game) {
feasible.constraints.push((indicator(s, n), game.value(s)));
let gap = total - game.value(s) - game.value(Coalition(game.grand().0 & !s.0));
if gap > tolerance {
complaints.push(excess_complaint(game, s, gap));
}
}
lexicographic_minimum(n, &feasible, &complaints, tolerance)
}
pub fn anti_prenucleolus(game: &ExplicitGame) -> Result<crate::nucleolus::NucleolusResult> {
crate::nucleolus::prenucleolus(&game.dual())
}
pub fn anti_nucleolus(game: &ExplicitGame) -> Result<crate::nucleolus::NucleolusResult> {
let utopia: f64 = crate::compromise::utopia_payoffs(game).iter().sum();
let total = game.value(game.grand());
if utopia > total + default_tolerance(game) {
return Err(Error::InvalidArgument(format!(
"anti-imputation の集合が空: 理想の支払い v(N) - v(N \\ {{i}}) の和 {utopia} が v(N) = {total} を超える"
)));
}
crate::nucleolus::nucleolus(&game.dual())
}
pub fn proportional_nucleolus(game: &ExplicitGame, domain: Domain) -> Result<LexicographicResult> {
if game.values().iter().any(|v| *v < 0.0) {
return Err(Error::InvalidArgument(
"比例仁は非負のゲーム (全ての v(S) >= 0) に限る".into(),
));
}
let mut feasible = feasible_set(game, domain)?;
let mut complaints = Vec::new();
for s in proper_coalitions(game) {
let value = game.value(s);
if value > 0.0 {
complaints.push(excess_complaint(game, s, value));
} else {
feasible
.constraints
.push((indicator(s, game.players()), 0.0));
}
}
lexicographic_minimum(
game.players(),
&feasible,
&complaints,
default_tolerance(game),
)
}
pub fn modiclus(game: &ExplicitGame) -> Result<LexicographicResult> {
let n = game.players();
if n > MAX_MODICLUS_PLAYERS {
return Err(Error::TooManyPlayers {
players: n,
max: MAX_MODICLUS_PLAYERS,
});
}
let coalitions: Vec<Coalition> = proper_coalitions(game).collect();
let mut complaints = Vec::with_capacity(coalitions.len() * coalitions.len());
for &s in &coalitions {
for &t in &coalitions {
if s == t {
continue;
}
let coefficients = indicator(s, n)
.iter()
.zip(indicator(t, n))
.map(|(a, b)| a - b)
.collect();
complaints.push(Complaint {
coefficients,
constant: game.value(s) - game.value(t),
weight: 1.0,
});
}
}
lexicographic_minimum(
n,
&feasible_set(game, Domain::Preimputation)?,
&complaints,
default_tolerance(game),
)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{generators, nucleolus};
fn assert_close(actual: &[f64], expected: &[f64], tolerance: f64) {
assert_eq!(actual.len(), expected.len());
for (a, e) in actual.iter().zip(expected) {
assert!((a - e).abs() <= tolerance, "{actual:?} != {expected:?}");
}
}
#[test]
fn unit_weights_give_the_nucleolus() {
for kind in 1..=4 {
for n in [3, 5, 7] {
let game = generators::bnf(kind, n, 2).unwrap();
let tolerance = 1e-6 * game.max_abs_value().max(1.0);
for domain in [Domain::Imputation, Domain::Preimputation] {
let expected = match nucleolus::nucleolus_with(
&game,
nucleolus::Options::new(&game, domain),
) {
Ok(result) => result.allocation,
Err(Error::EmptyImputationSet) => continue,
Err(err) => panic!("{err}"),
};
let actual = nucleolus_by_complaints(&game, domain).unwrap().allocation;
assert_close(&actual, &expected, tolerance);
}
}
}
}
#[test]
fn proportional_rejects_negative_games() {
let game = ExplicitGame::from_lex(&[-1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 2.0]).unwrap();
assert!(proportional_nucleolus(&game, Domain::Imputation).is_err());
}
#[test]
fn non_spanning_complaints_are_rejected() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0]).unwrap();
let err = proportional_nucleolus(&game, Domain::Imputation).unwrap_err();
assert!(matches!(err, Error::InvalidArgument(_)), "{err}");
}
#[test]
fn disruption_nucleolus_matches_coopgame_example() {
let game = ExplicitGame::from_lex(&[
0.0, 0.0, 0.0, 0.0, 2.0, 3.0, 4.0, 1.0, 3.0, 2.0, 8.0, 11.0, 6.5, 9.5, 14.0,
])
.unwrap();
let x = disruption_nucleolus(&game).unwrap().allocation;
for (a, e) in x.iter().zip([3.193548, 4.754839, 2.129032, 3.922581]) {
assert!((a - e).abs() < 1e-6, "{x:?}");
}
let empty = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 80.0, 80.0, 80.0, 90.0]).unwrap();
assert!(disruption_nucleolus(&empty).is_err());
}
#[test]
fn anti_prenucleolus_of_bankruptcy_example() {
let v = ExplicitGame::from_lex(&[0.0, 0.0, 10.0, 30.0, 70.0, 90.0, 150.0]).unwrap();
let w = ExplicitGame::from_lex(&[60.0, 80.0, 120.0, 140.0, 150.0, 150.0, 150.0]).unwrap();
assert_eq!(v.dual().values(), w.values());
assert_eq!(w.dual().values(), v.values());
let expected = [30.0, 40.0, 80.0];
let close = |x: &[f64]| x.iter().zip(&expected).all(|(a, e)| (a - e).abs() < 1e-6);
assert!(close(
&crate::nucleolus::prenucleolus(&v).unwrap().allocation
));
assert!(close(&anti_prenucleolus(&w).unwrap().allocation));
assert!(close(&anti_nucleolus(&w).unwrap().allocation));
assert!(!close(
&crate::nucleolus::prenucleolus(&w).unwrap().allocation
));
}
#[test]
fn anti_prenucleolus_maximizes_the_smallest_excess() {
for seed in 0..5 {
let game = crate::generators::bnf(1, 5, seed).unwrap();
let min_excess = |x: &[f64]| {
proper_coalitions(&game)
.map(|s| crate::surplus::excess(&game, s, x))
.fold(f64::INFINITY, f64::min)
};
let anti = anti_prenucleolus(&game).unwrap().allocation;
let pre = crate::nucleolus::prenucleolus(&game).unwrap().allocation;
let shapley = crate::values::shapley(&game);
assert!(min_excess(&anti) >= min_excess(&pre) - 1e-6);
assert!(min_excess(&anti) >= min_excess(&shapley) - 1e-6);
}
}
}