use crate::error::{Error, Result};
use crate::game::{Coalition, ExplicitGame};
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct SimpleGame {
players: usize,
wins: Vec<bool>,
pub winning: Vec<Coalition>,
pub minimal_winning: Vec<Coalition>,
pub swings: Vec<u64>,
}
impl SimpleGame {
pub fn new(game: &ExplicitGame) -> Result<SimpleGame> {
let n = game.players();
let mut wins = vec![false; 1usize << n];
for mask in 1..1u64 << n {
let value = game.value(Coalition(mask));
wins[mask as usize] = if value == 1.0 {
true
} else if value == 0.0 {
false
} else {
return Err(Error::InvalidArgument(format!(
"単純ゲームではない: 提携 {} の値が {value} (0 か 1 のみ)",
Coalition(mask)
)));
};
}
for mask in 1..1u64 << n {
if let Some(i) = (0..n).find(|&i| {
mask >> i & 1 == 0 && wins[mask as usize] && !wins[(mask | 1 << i) as usize]
}) {
return Err(Error::InvalidArgument(format!(
"単調でない: 勝利提携 {} にプレイヤー {i} を加えると負ける",
Coalition(mask)
)));
}
}
let mut winning = Vec::new();
let mut minimal_winning = Vec::new();
let mut swings = vec![0u64; n];
for mask in 1..1u64 << n {
if !wins[mask as usize] {
continue;
}
let coalition = Coalition(mask);
let mut critical = 0;
for i in coalition.members() {
if !wins[(mask & !(1 << i)) as usize] {
swings[i] += 1;
critical += 1;
}
}
if critical == coalition.len() {
minimal_winning.push(coalition);
}
winning.push(coalition);
}
Ok(SimpleGame {
players: n,
wins,
winning,
minimal_winning,
swings,
})
}
pub fn players(&self) -> usize {
self.players
}
fn critical(&self, coalition: Coalition) -> Coalition {
Coalition(
coalition
.members()
.filter(|&i| !self.wins[(coalition.0 & !(1 << i)) as usize])
.fold(0, |mask, i| mask | 1 << i),
)
}
fn require_winning(&self) -> Result<()> {
if self.winning.is_empty() {
return Err(Error::InvalidArgument("勝利提携がない".into()));
}
Ok(())
}
pub fn johnston(&self) -> Result<Vec<f64>> {
self.require_winning()?;
let mut raw = vec![0.0; self.players];
for &coalition in &self.winning {
let critical = self.critical(coalition);
let share = 1.0 / critical.len() as f64;
for i in critical.members() {
raw[i] += share;
}
}
normalized(raw)
}
pub fn deegan_packel(&self) -> Result<Vec<f64>> {
self.require_winning()?;
let count = self.minimal_winning.len() as f64;
let mut index = vec![0.0; self.players];
for coalition in &self.minimal_winning {
let share = 1.0 / (coalition.len() as f64 * count);
for i in coalition.members() {
index[i] += share;
}
}
Ok(index)
}
pub fn public_good(&self) -> Result<Vec<f64>> {
self.require_winning()?;
let mut counts = vec![0.0; self.players];
for coalition in &self.minimal_winning {
for i in coalition.members() {
counts[i] += 1.0;
}
}
normalized(counts)
}
pub fn coleman_prevent(&self) -> Result<Vec<f64>> {
self.require_winning()?;
let count = self.winning.len() as f64;
Ok(self.swings.iter().map(|&s| s as f64 / count).collect())
}
pub fn coleman_initiative(&self) -> Result<Vec<f64>> {
let losing = (1u64 << self.players) - self.winning.len() as u64;
if losing == 0 {
return Err(Error::InvalidArgument("敗北提携がない".into()));
}
Ok(self
.swings
.iter()
.map(|&s| s as f64 / losing as f64)
.collect())
}
pub fn coleman_collectivity(&self) -> f64 {
self.winning.len() as f64 / (1u64 << self.players) as f64
}
}
fn normalized(values: Vec<f64>) -> Result<Vec<f64>> {
let total: f64 = values.iter().sum();
if total == 0.0 {
return Err(Error::InvalidArgument(
"全員の値が 0 で正規化できない".into(),
));
}
Ok(values.into_iter().map(|v| v / total).collect())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::ExplicitGame;
use crate::games::voting::WeightedVotingGame;
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-12, "{actual:?} != {expected:?}");
}
}
fn voting(weights: &[u64], quota: u64) -> SimpleGame {
let game =
ExplicitGame::tabulate(&WeightedVotingGame::new(weights.to_vec(), quota).unwrap())
.unwrap();
SimpleGame::new(&game).unwrap()
}
#[test]
fn weighted_voting_3_2_1_quota_4() {
let game = voting(&[3, 2, 1], 4);
assert_eq!(game.minimal_winning.len(), 2);
assert_eq!(game.swings, vec![3, 1, 1]);
assert_close(
&game.johnston().unwrap(),
&[2.0 / 3.0, 1.0 / 6.0, 1.0 / 6.0],
);
assert_close(&game.deegan_packel().unwrap(), &[0.5, 0.25, 0.25]);
assert_close(&game.public_good().unwrap(), &[0.5, 0.25, 0.25]);
assert_close(
&game.coleman_prevent().unwrap(),
&[1.0, 1.0 / 3.0, 1.0 / 3.0],
);
assert_close(&game.coleman_initiative().unwrap(), &[0.6, 0.2, 0.2]);
assert!((game.coleman_collectivity() - 3.0 / 8.0).abs() < 1e-12);
}
#[test]
fn public_good_index_can_violate_monotonicity_in_weights() {
let game = voting(&[35, 20, 15, 15, 15], 51);
let pgi = game.public_good().unwrap();
assert!(pgi[1] < pgi[2]);
}
#[test]
fn dummy_player_has_zero_power_in_every_index() {
let game = voting(&[4, 4, 4, 2, 2, 1], 12);
assert_eq!(game.swings[5], 0);
for index in [
game.johnston().unwrap(),
game.deegan_packel().unwrap(),
game.public_good().unwrap(),
game.coleman_prevent().unwrap(),
] {
assert_eq!(index[5], 0.0);
}
}
#[test]
fn non_simple_or_non_monotone_game_is_rejected() {
let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 0.5, 1.0, 1.0, 1.0]).unwrap();
assert!(SimpleGame::new(&game).is_err());
let game = ExplicitGame::from_lex(&[1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0]).unwrap();
assert!(SimpleGame::new(&game).is_err());
}
#[test]
fn indices_match_coopgame_examples() {
let game = voting(&[35, 20, 15, 15, 15], 51);
assert_close(
&game.deegan_packel().unwrap(),
&[
18.0 / 60.0,
9.0 / 60.0,
11.0 / 60.0,
11.0 / 60.0,
11.0 / 60.0,
],
);
assert_close(
&game.public_good().unwrap(),
&[4.0 / 15.0, 2.0 / 15.0, 0.2, 0.2, 0.2],
);
let game = voting(&[3, 2, 1, 1], 5);
assert_eq!(game.swings, vec![5, 3, 1, 1]);
assert_close(&game.coleman_prevent().unwrap(), &[1.0, 0.6, 0.2, 0.2]);
assert_close(
&game.coleman_initiative().unwrap(),
&[5.0 / 11.0, 3.0 / 11.0, 1.0 / 11.0, 1.0 / 11.0],
);
assert!((game.coleman_collectivity() - 5.0 / 16.0).abs() < 1e-12);
}
}