use num_traits::{FromPrimitive, Num, Signed};
use crate::error::{Error, Result};
use crate::game::oracle::{MaxMerge, OracleGame};
use crate::game::subsets::SubsetsByWeight;
use crate::game::{PlayerSet, SetFunction};
use crate::properties::{ConvexGame, Proven};
pub trait Amount: Clone + PartialOrd + Num + Signed + FromPrimitive {}
impl<T: Clone + PartialOrd + Num + Signed + FromPrimitive> Amount for T {}
fn is_finite_amount<T: Amount>(value: &T) -> bool {
value.clone() - value.clone() == T::zero()
}
pub(crate) fn validate<T: Amount>(estate: &T, claims: &[T]) -> Result<T> {
if !is_finite_amount(estate) || !claims.iter().all(is_finite_amount) {
return Err(Error::InvalidArgument("遺産と請求は有限の値".into()));
}
if claims.iter().any(|d| *d < T::zero()) {
return Err(Error::InvalidArgument("請求は非負".into()));
}
let total = claims.iter().cloned().fold(T::zero(), |acc, d| acc + d);
if *estate < T::zero() || *estate > total {
return Err(Error::InvalidArgument(
"遺産は 0 以上、請求の総和以下 (破産問題の前提)".into(),
));
}
Ok(total)
}
fn equal_awards<T: Amount>(amount: T, caps: &[T]) -> Vec<T> {
let n = caps.len();
let mut order: Vec<usize> = (0..n).collect();
order.sort_by(|&a, &b| caps[a].partial_cmp(&caps[b]).expect("比較できる値"));
let mut shares = vec![T::zero(); n];
let mut remaining = amount;
for (position, &i) in order.iter().enumerate() {
let left = T::from_usize(n - position).expect("人数を数として表せる");
let even = remaining.clone() / left;
if caps[i] <= even {
shares[i] = caps[i].clone();
remaining = remaining - caps[i].clone();
} else {
for &j in &order[position..] {
shares[j] = even.clone();
}
break;
}
}
shares
}
pub fn constrained_equal_awards<T: Amount>(estate: T, claims: &[T]) -> Result<Vec<T>> {
validate(&estate, claims)?;
Ok(equal_awards(estate, claims))
}
pub fn constrained_equal_losses<T: Amount>(estate: T, claims: &[T]) -> Result<Vec<T>> {
let total = validate(&estate, claims)?;
let losses = equal_awards(total - estate, claims);
Ok(claims
.iter()
.cloned()
.zip(losses)
.map(|(d, l)| d - l)
.collect())
}
pub fn talmud_rule<T: Amount>(estate: T, claims: &[T]) -> Result<Vec<T>> {
let total = validate(&estate, claims)?;
let two = T::from_u8(2).expect("2 を表せる");
let halves: Vec<T> = claims.iter().map(|d| d.clone() / two.clone()).collect();
if estate.clone() * two.clone() <= total {
Ok(equal_awards(estate, &halves))
} else {
let losses = equal_awards(total - estate, &halves);
Ok(claims
.iter()
.cloned()
.zip(losses)
.map(|(d, l)| d - l)
.collect())
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct BankruptcyGame {
estate: f64,
claims: Vec<f64>,
total: f64,
}
impl BankruptcyGame {
pub fn new(estate: f64, claims: Vec<f64>) -> Result<BankruptcyGame> {
if estate < 0.0 || claims.iter().any(|d| *d < 0.0 || !d.is_finite()) || !estate.is_finite()
{
return Err(Error::InvalidArgument("遺産と請求は非負の有限値".into()));
}
let total: f64 = claims.iter().sum();
if !total.is_finite() || estate > total {
return Err(Error::InvalidArgument(format!(
"遺産 {estate} が請求の総和 {total} を超える (破産問題の前提は遺産 <= 請求の総和)"
)));
}
Ok(BankruptcyGame {
estate,
claims,
total,
})
}
pub fn claims(&self) -> &[f64] {
&self.claims
}
pub fn estate(&self) -> f64 {
self.estate
}
pub fn nucleolus(&self) -> Result<Vec<f64>> {
talmud_rule(self.estate, &self.claims)
}
}
impl SetFunction for BankruptcyGame {
fn players(&self) -> usize {
self.claims.len()
}
fn value(&self, coalition: &PlayerSet) -> f64 {
let inside: f64 = coalition.members().map(|i| self.claims[i]).sum();
(self.estate - self.total + inside).max(0.0)
}
}
impl ConvexGame for BankruptcyGame {
type Proof = Proven;
}
impl OracleGame for BankruptcyGame {
fn excess_order<'a>(&'a self, x: &'a [f64]) -> Box<dyn Iterator<Item = (PlayerSet, f64)> + 'a> {
let n = self.players();
assert_eq!(
x.len(),
n,
"配分の長さ {} がプレイヤー数 {n} と異なる",
x.len()
);
let negative: Vec<f64> = x.iter().map(|v| -v).collect();
let gains: Vec<f64> = self.claims.iter().zip(x).map(|(d, v)| d - v).collect();
let zero_part = SubsetsByWeight::new(&negative, 0.0);
let positive_part = SubsetsByWeight::new(&gains, self.estate - self.total);
Box::new(MaxMerge::new(zero_part, positive_part).filter(|(set, _)| set.is_proper()))
}
fn scale(&self) -> f64 {
self.estate
.max(self.claims.iter().cloned().fold(0.0, f64::max))
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::game::exact::Rational;
use crate::generators;
fn q(numerator: i64, denominator: i64) -> Rational {
Rational::new(numerator.into(), denominator.into())
}
#[test]
fn talmud_cases() {
let claims = [100.0, 200.0, 300.0];
assert_eq!(talmud_rule(200.0, &claims).unwrap(), vec![50.0, 75.0, 75.0]);
assert_eq!(
talmud_rule(300.0, &claims).unwrap(),
vec![50.0, 100.0, 150.0]
);
let exact: Vec<Rational> = [100, 200, 300].iter().map(|d| q(*d, 1)).collect();
assert_eq!(talmud_rule(q(100, 1), &exact).unwrap(), vec![q(100, 3); 3]);
}
#[test]
fn equal_awards_and_losses() {
let claims = [10.0, 30.0, 60.0];
assert_eq!(
constrained_equal_awards(50.0, &claims).unwrap(),
vec![10.0, 20.0, 20.0]
);
assert_eq!(
constrained_equal_losses(50.0, &claims).unwrap(),
vec![0.0, 10.0, 40.0]
);
}
#[test]
fn boundary_estates() {
let claims = [4.0, 1.0, 7.0];
assert_eq!(talmud_rule(0.0, &claims).unwrap(), vec![0.0; 3]);
assert_eq!(talmud_rule(12.0, &claims).unwrap(), claims.to_vec());
assert_eq!(talmud_rule(6.0, &claims).unwrap(), vec![2.0, 0.5, 3.5]);
assert!(talmud_rule(13.0, &claims).is_err());
assert!(talmud_rule(-1.0, &claims).is_err());
assert!(talmud_rule(1.0, &[2.0, -1.0]).is_err());
}
#[test]
fn matches_explicit_bankruptcy_game() {
let claims = vec![30.0, 70.0, 10.0, 55.0, 20.0];
let oracle = BankruptcyGame::new(100.0, claims.clone()).unwrap();
let explicit = generators::bankruptcy(100.0, &claims).unwrap();
let x = [10.0, 35.0, 0.0, 40.0, 15.0];
let from_oracle: Vec<(PlayerSet, f64)> = oracle.excess_order(&x).collect();
let from_explicit: Vec<(PlayerSet, f64)> = explicit.excess_order(&x).collect();
assert_eq!(from_oracle.len(), 30);
assert!(from_oracle.windows(2).all(|w| w[0].1 >= w[1].1 - 1e-12));
for ((_, a), (_, b)) in from_oracle.iter().zip(&from_explicit) {
assert!((a - b).abs() < 1e-9);
}
for (set, e) in &from_oracle {
assert!((oracle.value(set) - set.sum(&x) - e).abs() < 1e-9);
}
}
}