coopgame 0.2.0

TU協力ゲームの仁・プレ仁・カーネル・プレカーネルの計算と検証
Documentation

coopgame

TU 協力ゲームの仁・カーネル・Shapley 値などの解を計算し、検証する Rust ライブラリと CLI。

ブラウザで動かせるデモ: https://matsu7874.github.io/coopgame-demo/ (配分三角形、タルムードの遺産分割、議会の投票力、水道管の費用分担、どの解を使うかの早見図。ソースは coopgame-demo)

機能

  • 解を求める
    • 仁・プレ仁・最小コア (nucleolus)。有理数による厳密な計算にも対応 (nucleolus::exact)
    • カーネル・プレカーネルの 1 点 (kernel) と、6 人までの全体 (kernel::kernel_set)
    • Shapley 値・Banzhaf 値の厳密計算とサンプリング推定、solidarity 値 (values)
    • tau 値・Gately 点 (compromise)、通信グラフのもとでの Myerson 値 (communication)
    • 単純ゲームの投票力指数: Johnston・Deegan–Packel・Public Good (Holler)・Coleman (power)
    • per capita 仁・比例仁・modiclus・disruption nucleolus・anti-nucleolus (nucleolus::variants)
    • 提携構造のある解: Aumann–Drèze 値・Owen 値・提携構造つきの仁 (partition)
  • 結果を検証する
    • 仁の Kohlberg 基準と、有理数による厳密な検証 (verify)
    • カーネル条件 (kernel)・交渉集合への所属 (bargaining)
    • 凸性・コアなどゲームの性質 (properties)
    • 結果に付く保証の種類と事後検証 (verify、auto)
  • 大きいゲームを扱う
    • 全提携を列挙しないオラクル (game::oracle、nucleolus::oracle)
    • 凸ゲームの仁 (nucleolus::convex)
    • 提携のサンプリングによる近似 (nucleolus::sampled)
  • 特定のゲームを解く
    • 破産ゲーム (タルムード則)、空港ゲーム、最小全域木ゲーム、線形生産ゲーム、重み付き投票ゲーム、費用ゲーム (games)
  • 配分を分析する
    • 配分の説明と比較 (analysis::explain)、値の不確かさと感度 (analysis::uncertainty)
    • 3-4 人の配分集合の図 (analysis::plot)、性質の反例の探索 (analysis::search)
  • 入出力
    • 提携をプレイヤーの番号で書く JSON・CSV (io)、ランダムなゲームの生成 (generators)

プレイヤーは 0 始まりの番号だけで扱い、提携は {0, 2} の形で表示する (名前との対応は利用側で持つ。docs/api-overview.md)。

関数と手法の一覧は docs/api-overview.md、知りたいことから解を選ぶ早見図は docs/choosing.md にある。 LP ソルバーは純 Rust の microlp を使うので、外部のソルバーは不要。

インストール

ライブラリとして使う場合:

[dependencies]
coopgame = "0.2"

JSON・CSV でゲームを読み書きする io モジュールは、feature io で有効にする。

CLI (coopgame コマンド) を使う場合:

cargo install coopgame --features cli

使い方

use coopgame::{Domain, ExplicitGame, kernel, nucleolus, values, verify};

fn main() -> coopgame::Result<()> {
    // 3 人ゲームの特性関数 (辞書式順: {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2})
    let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 4.0, 0.0, 0.0, 4.0])?;

    let x = nucleolus::nucleolus(&game)?.into_allocation(); // 仁 [2, 2, 0]
    assert!(verify::kohlberg(&game, &x, Domain::Imputation)?.satisfied);
    assert!(kernel::is_in_kernel(&game, &x, Domain::Imputation, 1e-9));

    let phi = values::shapley(&game); // Shapley 値 [2, 2, 0]
    assert!(phi.iter().zip(&x).all(|(a, b)| (a - b).abs() < 1e-9));
    Ok(())
}

CLI では、1 行 1 値のファイルで特性関数を与える。

coopgame generate --type 1 --n 5 --seed 1 > v.txt   # ランダムなゲーム
coopgame nucleolus v.txt > sol.txt                   # 仁
coopgame verify v.txt sol.txt                        # Kohlberg 基準とカーネル条件で検証
coopgame shapley v.txt                               # Shapley 値

全てのサブコマンドは docs/cli.md、入力ファイルの並び順と JSON・CSV の形式は docs/input-format.md を参照。

ドキュメント

全ての文書の一覧は docs/README.md にある。 API リファレンスは docs.rs。

Python バインディング

python/ に PyO3 によるバインディングがある (PyPI の配布名は coopgame-py、import 名は coopgame)。 ビルド方法と API は python/README.md を参照。

コントリビューション

開発環境、テストの方針、リリースの手順は CONTRIBUTING.md にまとめている。

ライセンス

MIT License。LICENSE を参照。