pub(crate) mod allocation;
pub(crate) mod coalition;
pub mod exact;
pub mod oracle;
mod player_set;
pub(crate) mod subsets;
pub use allocation::Domain;
pub(crate) use allocation::excess_table;
pub use coalition::{Coalition, binary_to_lex};
pub use player_set::{PlayerSet, SetFunction, value_scale};
use crate::error::{Error, Result};
pub const MAX_PLAYERS: usize = 30;
#[derive(Clone, Debug, PartialEq)]
pub struct ExplicitGame {
players: usize,
values: Vec<f64>,
}
impl ExplicitGame {
pub fn from_binary(values: &[f64]) -> Result<ExplicitGame> {
let players = coalition::players_from_len(values.len())?;
check_players(players)?;
if let Some(pos) = values.iter().position(|v| !v.is_finite()) {
return Err(Error::InvalidArgument(format!(
"{} 番目の値が有限でない",
pos + 1
)));
}
let mut all = Vec::with_capacity(values.len() + 1);
all.push(0.0);
all.extend_from_slice(values);
Ok(ExplicitGame {
players,
values: all,
})
}
pub fn from_lex(values: &[f64]) -> Result<ExplicitGame> {
ExplicitGame::from_binary(&coalition::lex_to_binary(values)?)
}
pub fn from_fn(
players: usize,
mut value: impl FnMut(Coalition) -> f64,
) -> Result<ExplicitGame> {
check_players(players)?;
let values: Vec<f64> = (1..(1u64 << players))
.map(|mask| value(Coalition(mask)))
.collect();
ExplicitGame::from_binary(&values)
}
pub fn tabulate<G: SetFunction + ?Sized>(game: &G) -> Result<ExplicitGame> {
let n = game.players();
if n == 0 || n > MAX_PLAYERS {
return Err(Error::TooManyPlayers {
players: n,
max: MAX_PLAYERS,
});
}
let mut set = PlayerSet::grand(n);
ExplicitGame::from_fn(n, |coalition| {
set.assign(coalition);
game.value(&set)
})
}
pub fn subgame(&self, members: Coalition) -> Result<ExplicitGame> {
let members: Vec<usize> = members.members().collect();
ExplicitGame::from_fn(members.len(), |sub| {
self.value(Coalition::embed(&members, sub.0))
})
}
pub fn map_values(&self, mut f: impl FnMut(Coalition, f64) -> f64) -> Result<ExplicitGame> {
ExplicitGame::from_fn(self.players, |coalition| {
f(coalition, self.value(coalition))
})
}
pub fn with_value(&self, coalition: Coalition, value: f64) -> Result<ExplicitGame> {
self.map_values(|s, v| if s == coalition { value } else { v })
}
pub fn parse_lines(text: &str) -> Result<ExplicitGame> {
ExplicitGame::from_binary(&parse_values(text)?)
}
pub fn parse_lines_lex(text: &str) -> Result<ExplicitGame> {
ExplicitGame::from_lex(&parse_values(text)?)
}
pub fn to_lines(&self) -> String {
let mut out = String::new();
for value in &self.values[1..] {
out.push_str(&value.to_string());
out.push('\n');
}
out
}
pub fn players(&self) -> usize {
self.players
}
pub fn grand(&self) -> Coalition {
Coalition::grand(self.players)
}
pub fn value(&self, coalition: Coalition) -> f64 {
self.values[coalition.index()]
}
pub fn values(&self) -> &[f64] {
&self.values
}
pub fn singleton_values(&self) -> Vec<f64> {
(0..self.players)
.map(|i| self.value(Coalition::singleton(i)))
.collect()
}
pub fn max_abs_value(&self) -> f64 {
self.values.iter().fold(0.0, |acc, v| acc.max(v.abs()))
}
pub fn dual(&self) -> ExplicitGame {
let grand = self.values.len() - 1;
let total = self.values[grand];
ExplicitGame {
players: self.players,
values: (0..self.values.len())
.map(|mask| total - self.values[grand & !mask])
.collect(),
}
}
pub fn negated(&self) -> ExplicitGame {
ExplicitGame {
players: self.players,
values: self.values.iter().map(|v| -v).collect(),
}
}
}
pub fn default_tolerance(game: &ExplicitGame) -> f64 {
1e-7 * game.max_abs_value().max(1.0)
}
pub(super) fn check_players(players: usize) -> Result<()> {
if players > MAX_PLAYERS {
return Err(Error::TooManyPlayers {
players,
max: MAX_PLAYERS,
});
}
Ok(())
}
pub fn parse_values(text: &str) -> Result<Vec<f64>> {
let mut values = Vec::new();
for (index, line) in text.lines().enumerate() {
let line = line.trim();
if line.is_empty() || line.starts_with('#') {
continue;
}
let value = if line.contains('/') {
exact::parse_rational(line)
.map(|q| exact::to_f64(&[q])[0])
.map_err(|err| Error::Parse {
line: index + 1,
message: format!("数値として読めない: {line:?} ({err})"),
})?
} else {
line.parse::<f64>().map_err(|err| Error::Parse {
line: index + 1,
message: format!("数値として読めない: {line:?} ({err})"),
})?
};
values.push(value);
}
Ok(values)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn parses_bnf_format() {
let game = ExplicitGame::parse_lines("1\n2\n# comment\n3\n\n4\n5\n6\n7\n").unwrap();
assert_eq!(game.players(), 3);
assert_eq!(game.value(Coalition::from_players(&[0, 1])), 3.0);
assert_eq!(game.value(game.grand()), 7.0);
assert_eq!(ExplicitGame::parse_lines(&game.to_lines()).unwrap(), game);
}
#[test]
fn lex_and_binary_inputs_agree() {
let lex = ExplicitGame::from_lex(&[1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0]).unwrap();
let binary = ExplicitGame::from_binary(&[1.0, 2.0, 4.0, 3.0, 5.0, 6.0, 7.0]).unwrap();
assert_eq!(lex, binary);
}
#[test]
fn reports_parse_error_line() {
let err = ExplicitGame::parse_lines("1\nx\n3\n").unwrap_err();
assert!(matches!(err, Error::Parse { line: 2, .. }));
}
}