実現可能な配分メカニズム理論の構築

今年度得られた研究成果は大きく分けて以下の三つにまとめられます。第一に、前年度から行っていた提携構造が交差族をなす協力ゲームの仁を計算するアルゴリズムについて、ポリマトロイド理論の論文を読み、研究の理論的基礎を補強しました。さらに、前年度に得られた、交差族上の協力ゲームの仁の多項式時間可解性の結果に加え、非負の仁を計算する多項式時間アルゴリズムの存在を示しました。第二に、既存の配分方法を定義する制約の中で、取り除いても最終的な配分結果に影響しない(冗長な)制約について調べました。その結果、協力ゲームの代表的な配分方法の一つであるコアにおいて、ある制約が冗長であれば、安定集合についても冗長であることがわかりました。この結果により、安定集合の特徴付けがより容易になったと考えられます。次に、仁についてもある制約が冗長である十分条件を得ました。この結果は、Huberman(1980)において既に示されていることですが、より明瞭な証明を提示できたことに意義があります。第三に、グループ同士の繋がりと個々人の繋がりの二つのコミュニケーション構造を考慮したモデルについて、各グループの部分集合が他のグループと提携可能であると仮定して、そのようなモデルにおける配分方法の性質について明らかにしました。ネットワークの中心性分析への応用を想定して、提案する配分方法の対称性やNull player axiomなどを満たすことを示しました。

今年度得られた研究成果は大きく分けて以下の三つにまとめられます。第一に、前年度から行っていた提携構造が交差族をなす協力ゲームの仁を計算するアルゴリズムについて、ポリマトロイド理論の論文を読み、研究の理論的基礎を補強しました。さらに、前年度に得られた、交差族上の協力ゲームの仁の多項式時間可解性の結果に加え、非負の仁を計算する多項式時間アルゴリズムの存在を示しました。第二に、既存の配分方法を定義する制約の中で、取り除いても最終的な配分結果に影響しない(冗長な)制約について調べました。その結果、協力ゲームの代表的な配分方法の一つであるコアにおいて、ある制約が冗長であれば、安定集合についても冗長であることがわかりました。この結果により、安定集合の特徴付けがより容易になったと考えられます。次に、仁についてもある制約が冗長である十分条件を得ました。この結果は、Huberman(1980)において既に示されていることですが、より明瞭な証明を提示できたことに意義があります。第三に、グループ同士の繋がりと個々人の繋がりの二つのコミュニケーション構造を考慮したモデルについて、各グループの部分集合が他のグループと提携可能であると仮定して、そのようなモデルにおける配分方法の性質について明らかにしました。ネットワークの中心性分析への応用を想定して、提案する配分方法の対称性やNull player axiomなどを満たすことを示しました。