use std::fmt;
use crate::Domain;
use crate::error::{Error, Result};
use crate::game::{Coalition, ExplicitGame};
use crate::nucleolus::{self, NucleolusResult, Options};
use crate::values;
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct CoalitionStructure {
players: usize,
blocks: Vec<Coalition>,
}
impl fmt::Display for CoalitionStructure {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let blocks: Vec<String> = self.blocks.iter().map(Coalition::to_string).collect();
f.pad(&blocks.join(" "))
}
}
impl CoalitionStructure {
pub fn new(players: usize, blocks: &[Vec<usize>]) -> Result<CoalitionStructure> {
if players > 64 {
return Err(Error::TooManyPlayers { players, max: 64 });
}
let mut seen = 0u64;
let mut coalitions = Vec::with_capacity(blocks.len());
for block in blocks {
if block.is_empty() {
return Err(Error::InvalidArgument("空のブロック".into()));
}
let mut mask = 0u64;
for &i in block {
if i >= players || seen >> i & 1 == 1 || mask >> i & 1 == 1 {
return Err(Error::InvalidArgument(format!(
"プレイヤー {i} が範囲外か、2 つ以上のブロックに属する"
)));
}
mask |= 1 << i;
}
seen |= mask;
coalitions.push(Coalition(mask));
}
if seen != Coalition::grand(players).0 {
return Err(Error::InvalidArgument(
"どのブロックにも属さないプレイヤーがいる".into(),
));
}
Ok(CoalitionStructure {
players,
blocks: coalitions,
})
}
pub fn grand(players: usize) -> CoalitionStructure {
CoalitionStructure {
players,
blocks: vec![Coalition::grand(players)],
}
}
pub fn singletons(players: usize) -> CoalitionStructure {
CoalitionStructure {
players,
blocks: (0..players).map(Coalition::singleton).collect(),
}
}
pub fn blocks(&self) -> &[Coalition] {
&self.blocks
}
fn check(&self, game: &ExplicitGame) -> Result<()> {
if game.players() != self.players {
return Err(Error::InvalidArgument(format!(
"提携構造の人数 {} がゲームの人数 {} と異なる",
self.players,
game.players()
)));
}
Ok(())
}
}
fn factorials(n: usize) -> Vec<f64> {
let mut f = vec![1.0; n + 1];
for k in 1..=n {
f[k] = f[k - 1] * k as f64;
}
f
}
pub fn aumann_dreze(game: &ExplicitGame, structure: &CoalitionStructure) -> Result<Vec<f64>> {
structure.check(game)?;
let mut value = vec![0.0; game.players()];
for &block in structure.blocks() {
let shapley = values::shapley(&game.subgame(block)?);
for (i, phi) in block.members().zip(shapley) {
value[i] = phi;
}
}
Ok(value)
}
pub fn owen(game: &ExplicitGame, unions: &CoalitionStructure) -> Result<Vec<f64>> {
unions.check(game)?;
let m = unions.blocks().len();
let fm = factorials(m);
let mut value = vec![0.0; game.players()];
for (k, &union) in unions.blocks().iter().enumerate() {
let others: Vec<Coalition> = unions
.blocks()
.iter()
.enumerate()
.filter(|(l, _)| *l != k)
.map(|(_, c)| *c)
.collect();
let members: Vec<usize> = union.members().collect();
let b = members.len();
let fb = factorials(b);
for &i in &members {
let mates: Vec<usize> = members.iter().copied().filter(|&j| j != i).collect();
let mut total = 0.0;
for chosen in 0u64..(1 << others.len()) {
let r = chosen.count_ones() as usize;
let q = Coalition::union_of(&others, chosen).0;
let outer = fm[r] * fm[m - r - 1] / fm[m];
for sub in 0u64..(1 << mates.len()) {
let t = sub.count_ones() as usize;
let inner = fb[t] * fb[b - t - 1] / fb[b];
let s = q | Coalition::embed(&mates, sub).0;
total += outer
* inner
* (game.value(Coalition(s | 1 << i)) - game.value(Coalition(s)));
}
}
value[i] = total;
}
}
Ok(value)
}
pub fn nucleolus(
game: &ExplicitGame,
structure: &CoalitionStructure,
domain: Domain,
) -> Result<NucleolusResult> {
structure.check(game)?;
nucleolus::nucleolus_with_structure(game, structure.blocks(), Options::new(game, domain))
}
pub fn quotient_game(game: &ExplicitGame, unions: &CoalitionStructure) -> Result<ExplicitGame> {
unions.check(game)?;
ExplicitGame::from_fn(unions.blocks().len(), |chosen| {
game.value(Coalition::union_of(unions.blocks(), chosen.0))
})
}