pub mod convex;
pub mod exact;
pub mod oracle;
pub mod sampled;
pub mod variants;
use microlp::{Problem, Solution, Variable};
use crate::Domain;
use crate::error::{Error, Result};
use crate::game::allocation::{block_lower_bounds, coalition_sums};
use crate::game::{Coalition, ExplicitGame, default_tolerance};
use crate::linalg::Span;
use crate::lp::{self, Cmp, Counter};
use crate::solution::Guarantee;
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
#[non_exhaustive]
pub enum Method {
Full,
#[default]
ConstraintGeneration,
}
#[derive(Clone, Copy, Debug, PartialEq)]
#[non_exhaustive]
pub struct Options {
pub domain: Domain,
pub tolerance: f64,
pub method: Method,
}
impl Options {
pub fn new(game: &ExplicitGame, domain: Domain) -> Options {
Options {
domain,
tolerance: default_tolerance(game),
method: Method::default(),
}
}
fn divided_by(self, divisor: f64) -> Options {
Options {
tolerance: self.tolerance / divisor,
..self
}
}
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct NucleolusResult {
pub(crate) allocation: Vec<f64>,
pub(crate) levels: Vec<f64>,
pub(crate) lp_solves: usize,
pub(crate) rows_added: usize,
pub(crate) guarantee: Guarantee,
}
impl NucleolusResult {
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 rows_added(&self) -> usize {
self.rows_added
}
pub fn guarantee(&self) -> Guarantee {
self.guarantee
}
pub(crate) fn scaled_by(mut self, factor: f64) -> NucleolusResult {
for value in self.allocation.iter_mut().chain(self.levels.iter_mut()) {
*value *= factor;
}
self
}
pub(crate) fn into_solution(
self,
domain: Domain,
method: &'static str,
) -> crate::solution::Solution {
crate::solution::Solution {
domain,
allocation: self.allocation,
guarantee: self.guarantee,
method,
}
}
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct LeastCore {
pub(crate) epsilon: f64,
pub(crate) allocation: Vec<f64>,
pub(crate) guarantee: Guarantee,
}
impl LeastCore {
pub fn epsilon(&self) -> f64 {
self.epsilon
}
pub fn allocation(&self) -> &[f64] {
&self.allocation
}
pub fn into_allocation(self) -> Vec<f64> {
self.allocation
}
pub fn guarantee(&self) -> Guarantee {
self.guarantee
}
}
pub fn nucleolus(game: &ExplicitGame) -> Result<NucleolusResult> {
nucleolus_with(game, Options::new(game, Domain::Imputation))
}
pub fn prenucleolus(game: &ExplicitGame) -> Result<NucleolusResult> {
nucleolus_with(game, Options::new(game, Domain::Preimputation))
}
pub fn nucleolus_with(game: &ExplicitGame, options: Options) -> Result<NucleolusResult> {
let (normalized, divisor) = game.normalized();
let options = options.divided_by(divisor);
let result = Sequential::new(&normalized, options)?.run()?;
Ok(result.scaled_by(divisor))
}
pub(crate) fn nucleolus_with_structure(
game: &ExplicitGame,
blocks: &[Coalition],
options: Options,
) -> Result<NucleolusResult> {
let (normalized, divisor) = game.normalized();
let options = options.divided_by(divisor);
let lower = block_lower_bounds(&normalized, blocks, options.domain, options.tolerance)?;
if blocks.iter().all(|block| block.len() == 1) {
return Ok(NucleolusResult {
allocation: game.singleton_values(),
levels: Vec::new(),
lp_solves: 0,
rows_added: 0,
guarantee: Guarantee::Exact,
});
}
let result = Sequential::with_blocks(&normalized, options, blocks, lower).run()?;
Ok(result.scaled_by(divisor))
}
pub fn least_core(game: &ExplicitGame, domain: Domain) -> Result<LeastCore> {
let (normalized, divisor) = game.normalized();
let options = Options::new(game, domain).divided_by(divisor);
let mut solver = Sequential::new(&normalized, options)?;
if solver.n == 1 {
return Ok(LeastCore {
epsilon: f64::NEG_INFINITY,
allocation: vec![game.value(game.grand())],
guarantee: Guarantee::Exact,
});
}
let (epsilon, allocation) = solver.minimize_max_excess()?;
Ok(LeastCore {
epsilon: epsilon * divisor,
allocation: allocation.iter().map(|v| v * divisor).collect(),
guarantee: Guarantee::Exact,
})
}
pub fn has_nonempty_core(game: &ExplicitGame) -> Result<bool> {
let least = least_core(game, Domain::Preimputation)?;
Ok(least.epsilon <= default_tolerance(game))
}
#[derive(Clone, Copy)]
enum RowForm {
WithLevel(Variable),
AtMost(f64),
}
struct Sequential<'a> {
game: &'a ExplicitGame,
options: Options,
n: usize,
lower: Option<Vec<f64>>,
blocks: Vec<Coalition>,
determined: Vec<bool>,
fixed: Vec<(Coalition, f64)>,
span: Span,
counter: Counter,
rows_added: usize,
pool: Vec<Coalition>,
in_pool: Vec<bool>,
}
impl<'a> Sequential<'a> {
fn new(game: &'a ExplicitGame, options: Options) -> Result<Sequential<'a>> {
let blocks = [game.grand()];
let lower = block_lower_bounds(game, &blocks, options.domain, options.tolerance)?;
Ok(Sequential::with_blocks(game, options, &blocks, lower))
}
fn with_blocks(
game: &'a ExplicitGame,
options: Options,
blocks: &[Coalition],
lower: Option<Vec<f64>>,
) -> Sequential<'a> {
let n = game.players();
let grand = game.grand();
let mut determined = vec![false; 1 << n];
determined[0] = true;
let mut span = Span::new(n);
let mut fixed = Vec::with_capacity(blocks.len());
for &block in blocks {
determined[block.index()] = true;
span.insert_coalition(block);
fixed.push((block, game.value(block)));
}
let mut solver = Sequential {
game,
options,
n,
lower,
blocks: blocks.to_vec(),
determined,
fixed,
span,
counter: Counter::default(),
rows_added: 0,
pool: Vec::new(),
in_pool: vec![false; 1 << n],
};
for i in 0..n {
let single = Coalition::singleton(i);
solver.remember(single);
solver.remember(Coalition(grand.0 & !single.0));
}
solver.mark_span_determined();
solver
}
fn run(&mut self) -> Result<NucleolusResult> {
if self.n == 1 {
return Ok(NucleolusResult {
allocation: vec![self.game.value(self.game.grand())],
levels: Vec::new(),
lp_solves: 0,
rows_added: 0,
guarantee: Guarantee::Exact,
});
}
self.pin_single_point_blocks();
if self.span.is_full() {
return Ok(NucleolusResult {
allocation: self
.lower
.clone()
.expect("1 点に決まるのは配分集合の場合だけ"),
levels: Vec::new(),
lp_solves: 0,
rows_added: 0,
guarantee: Guarantee::Exact,
});
}
let mut levels = Vec::new();
let mut allocation = Vec::new();
while !self.span.is_full() {
let (level, x) = self.minimize_max_excess()?;
levels.push(level);
self.fix_tight_coalitions(level, &x)?;
self.mark_span_determined();
allocation = x;
}
Ok(NucleolusResult {
allocation,
levels,
lp_solves: self.counter.solves,
rows_added: self.rows_added,
guarantee: Guarantee::Exact,
})
}
fn pin_single_point_blocks(&mut self) {
let Some(lower) = self.lower.clone() else {
return;
};
for block in self.blocks.clone() {
let singles: f64 = block
.members()
.map(|i| self.game.value(Coalition::singleton(i)))
.sum();
if block.len() < 2 || singles < self.game.value(block) {
continue;
}
for i in block.members().take(block.len() - 1) {
let single = Coalition::singleton(i);
self.fixed.push((single, lower[i]));
self.span.insert_coalition(single);
}
}
self.mark_span_determined();
}
fn tolerance(&self) -> f64 {
self.options.tolerance
}
fn remember(&mut self, coalition: Coalition) {
if !coalition.is_empty() && !self.in_pool[coalition.index()] {
self.in_pool[coalition.index()] = true;
self.pool.push(coalition);
}
}
fn is_open(&self, coalition: Coalition) -> bool {
!self.determined[coalition.index()]
}
fn open_coalitions(&self) -> impl Iterator<Item = Coalition> + '_ {
self.determined
.iter()
.enumerate()
.filter(|(_, determined)| !**determined)
.map(|(mask, _)| Coalition(mask as u64))
}
fn mark_span_determined(&mut self) {
for mask in 1..self.determined.len() {
if !self.determined[mask] && self.span.contains_coalition(Coalition(mask as u64)) {
self.determined[mask] = true;
}
}
}
fn add_players(&self, problem: &mut Problem, objective: Option<Coalition>) -> Vec<Variable> {
(0..self.n)
.map(|i| {
let lower = self
.lower
.as_ref()
.map_or(f64::NEG_INFINITY, |lower| lower[i]);
let coefficient = match objective {
Some(s) if s.contains(i) => 1.0,
_ => 0.0,
};
problem.add_var(coefficient, (lower, f64::INFINITY))
})
.collect()
}
fn add_fixed(&self, problem: &mut Problem, x: &[Variable]) {
for &(coalition, value) in &self.fixed {
lp::add(problem, lp::coalition_expr(x, coalition), Cmp::Eq, value);
}
}
fn row(
&self,
x: &[Variable],
form: RowForm,
coalition: Coalition,
) -> (Vec<(Variable, f64)>, f64) {
let mut terms = lp::coalition_expr(x, coalition);
let value = self.game.value(coalition);
match form {
RowForm::WithLevel(t) => {
terms.push((t, 1.0));
(terms, value)
}
RowForm::AtMost(bound) => (terms, value - bound),
}
}
fn solve_rows(
&mut self,
build: impl Fn(&Self) -> (Problem, Vec<Variable>, RowForm),
seed: &[Coalition],
) -> Result<(Solution, Vec<Variable>, RowForm)> {
if self.options.method == Method::ConstraintGeneration
&& let Some(solved) = self.solve_lazily(&build, seed)?
{
return Ok(solved);
}
let (mut problem, x, form) = build(self);
for coalition in self.open_coalitions() {
let (terms, rhs) = self.row(&x, form, coalition);
lp::add(&mut problem, terms, Cmp::Ge, rhs);
}
let solution = self
.counter
.solve(&problem)?
.ok_or_else(|| Error::Numerical("LP が実行不可能".into()))?;
Ok((solution, x, form))
}
fn solve_lazily(
&mut self,
build: &impl Fn(&Self) -> (Problem, Vec<Variable>, RowForm),
seed: &[Coalition],
) -> Result<Option<(Solution, Vec<Variable>, RowForm)>> {
for &coalition in seed {
self.remember(coalition);
}
let (mut problem, x, form) = build(self);
let mut in_lp = vec![false; 1 << self.n];
for &coalition in &self.pool {
if self.is_open(coalition) {
let (terms, rhs) = self.row(&x, form, coalition);
lp::add(&mut problem, terms, Cmp::Ge, rhs);
in_lp[coalition.index()] = true;
}
}
let mut solution = match self.counter.solve_bounded(&problem)? {
Some(solution) => solution,
None => return Ok(None),
};
let slack = 1e-3 * self.tolerance();
let batch = 4 * self.n;
loop {
let values: Vec<f64> = x.iter().map(|&var| solution[var]).collect();
let sums = coalition_sums(&values);
let bound = match form {
RowForm::WithLevel(t) => solution[t],
RowForm::AtMost(bound) => bound,
};
let mut violated: Vec<(f64, Coalition)> = self
.open_coalitions()
.filter(|s| !in_lp[s.index()])
.filter_map(|s| {
let violation = self.game.value(s) - sums[s.index()] - bound;
(violation > slack).then_some((violation, s))
})
.collect();
if violated.is_empty() {
return Ok(Some((solution, x, form)));
}
violated.sort_by(|a, b| b.0.total_cmp(&a.0));
for &(_, coalition) in violated.iter().take(batch) {
let (terms, rhs) = self.row(&x, form, coalition);
solution = lp::add_to_solution(solution, terms, Cmp::Ge, rhs)?;
in_lp[coalition.index()] = true;
self.remember(coalition);
self.rows_added += 1;
}
}
}
fn minimize_max_excess(&mut self) -> Result<(f64, Vec<f64>)> {
let build = |this: &Self| {
let mut problem = lp::minimize();
let x = this.add_players(&mut problem, None);
let t = problem.add_var(1.0, (f64::NEG_INFINITY, f64::INFINITY));
this.add_fixed(&mut problem, &x);
(problem, x, RowForm::WithLevel(t))
};
let (solution, x, form) = self.solve_rows(build, &[])?;
let RowForm::WithLevel(t) = form else {
unreachable!("最大超過の最小化は WithLevel の行を使う")
};
let allocation = x.iter().map(|&var| solution[var]).collect();
Ok((solution[t], allocation))
}
fn maximize_coalition(&mut self, target: Coalition, level: f64) -> Result<(f64, Vec<f64>)> {
let bound = level + 0.01 * self.tolerance();
let build = |this: &Self| {
let mut problem = lp::maximize();
let x = this.add_players(&mut problem, Some(target));
this.add_fixed(&mut problem, &x);
(problem, x, RowForm::AtMost(bound))
};
let complement = Coalition(self.game.grand().0 & !target.0);
let (solution, x, _) = self.solve_rows(build, &[target, complement])?;
let allocation: Vec<f64> = x.iter().map(|&var| solution[var]).collect();
Ok((solution.objective(), allocation))
}
fn fix_tight_coalitions(&mut self, level: f64, x: &[f64]) -> Result<()> {
let sums = coalition_sums(x);
let tight: Vec<Coalition> = self
.open_coalitions()
.filter(|s| {
let excess = self.game.value(*s) - sums[s.index()];
(excess - level).abs() <= self.tolerance()
})
.collect();
if tight.is_empty() {
return Err(Error::Numerical(format!(
"最大超過 {level} を達成する提携が見つからない"
)));
}
let mut not_fixed = vec![false; tight.len()];
let mut progressed = false;
for k in 0..tight.len() {
if not_fixed[k] || self.span.contains_coalition(tight[k]) {
continue;
}
let target = tight[k];
let fixed_sum = self.game.value(target) - level;
let (max_sum, witness) = self.maximize_coalition(target, level)?;
if max_sum <= fixed_sum + self.tolerance() {
self.fixed.push((target, fixed_sum));
self.span.insert_coalition(target);
progressed = true;
if self.span.is_full() {
break;
}
} else {
let witness_sums = coalition_sums(&witness);
for (later, flag) in tight.iter().zip(not_fixed.iter_mut()).skip(k + 1) {
let excess = self.game.value(*later) - witness_sums[later.index()];
if excess < level - self.tolerance() {
*flag = true;
}
}
}
}
if !progressed {
return Err(Error::Numerical(format!(
"最大超過 {level} の段で確定する提携が見つからない(許容誤差 {} を見直す)",
self.tolerance()
)));
}
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::generators;
fn assert_close(actual: &[f64], expected: &[f64]) {
assert_eq!(actual.len(), expected.len());
for (a, e) in actual.iter().zip(expected) {
assert!((a - e).abs() < 1e-6, "{actual:?} != {expected:?}");
}
}
#[test]
fn detects_empty_core() {
assert!(has_nonempty_core(&generators::random_convex(4, 1).unwrap()).unwrap());
let majority = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]).unwrap();
assert!(!has_nonempty_core(&majority).unwrap());
}
#[test]
fn symmetric_game_splits_equally() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 60.0, 60.0, 60.0, 72.0]).unwrap();
assert_close(&nucleolus(&game).unwrap().allocation, &[24.0, 24.0, 24.0]);
assert_close(
&prenucleolus(&game).unwrap().allocation,
&[24.0, 24.0, 24.0],
);
}
#[test]
fn pair_game() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 4.0, 0.0, 0.0, 4.0]).unwrap();
let result = nucleolus(&game).unwrap();
assert_close(&result.allocation, &[2.0, 2.0, 0.0]);
assert!((result.levels[0] - 0.0).abs() < 1e-9);
}
#[test]
fn bankruptcy_nucleolus_is_talmud_rule() {
let claims = [100.0, 200.0, 300.0];
for (estate, expected) in [
(100.0, [100.0 / 3.0, 100.0 / 3.0, 100.0 / 3.0]),
(200.0, [50.0, 75.0, 75.0]),
(300.0, [50.0, 100.0, 150.0]),
] {
let game = generators::bankruptcy(estate, &claims).unwrap();
assert_close(&nucleolus(&game).unwrap().allocation, &expected);
}
}
#[test]
fn prenucleolus_can_leave_imputation_set() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 5.0, 10.0, 5.0, 5.0, 12.0]).unwrap();
assert_close(&prenucleolus(&game).unwrap().allocation, &[4.25, 4.25, 3.5]);
assert_close(&nucleolus(&game).unwrap().allocation, &[3.5, 3.5, 5.0]);
}
#[test]
fn empty_imputation_set_is_error() {
let game = ExplicitGame::from_lex(&[3.0, 3.0, 3.0, 6.0, 6.0, 6.0, 8.0]).unwrap();
assert_eq!(nucleolus(&game), Err(Error::EmptyImputationSet));
assert!(prenucleolus(&game).is_ok());
}
#[test]
fn least_core_of_game_with_empty_core() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]).unwrap();
let least = least_core(&game, Domain::Preimputation).unwrap();
assert!((least.epsilon - 1.0 / 3.0).abs() < 1e-9);
assert_close(&least.allocation, &[1.0 / 3.0; 3]);
}
}