研究展示

コミュニケーションと計算の科学

07

みんなが協力せず勝手に急ぐとどうなる？

混雑ゲームの均衡計算

どんな研究

道路や通信などのネットワークでは、ある辺（リンク）を使う人が多いほどその辺は混雑し、コスト（所要時間）が大きくなります。ネットワークの各利用者が経路（辺の組合せ）を選ぶ際に、誘導や制御がなく各々自分勝手にコストが小さい経路を選ぶ場合、どの辺がどの程度混雑するか計算できます。

どこが凄い

素朴な方法では、全ての経路について確率の計算をすることになりますが、経路の数が膨大なため実用上は不可能でした。私たちは二分決定グラフとよばれるデータ構造を用いて経路の集合を小さく表現することで、計算を高速化し、実用的な大きさのネットワークでの計算を可能にしました。

めざす未来

本技術により、道路や通信のネットワークの混雑状況を簡単に予測できるようになり、ネットワークの設計に役立ちます。また、本技術における「辺」は「アイテム」、「辺の組合せ」は「アイテムの組合せ」と一般化でき、経済学などの一般的な場合におけるゲーム理論的解析にも役立つと考えられます。

関連文献

  1. K. Nakamura, S. Sakaue, N. Yasuda, “Practical Frank-Wolfe method with decision diagrams for computing Wardrop equilibrium of combinatorial congestion games,” in Proc. 34th AAAI Conference on Artificial Intelligence （AAAI）, 2020.

ポスター

展示説明ムービー

動画の公開は終了いたしました。ご了承くださいますようお願いいたします。

連絡先

中村 健吾 （Kengo Nakamura） 協創情報研究部 言語知能研究グループ
Email: