マトロイド上の最小基ゲーム
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,重み関数ω:E〓Rを持つマトロイドM=(E,I)上で最小基ゲーム(E,c)を導入し,協力ゲームにおける解の概念に対する計算の複雑性について議論する.ここで,最小基ゲームの特性関数c:2^E〓Rは,c(S)=S⊆E上の基(base)の最小重みとして定義される.最小基ゲームは,その特殊な場合として,辺に重みを持つグラフ上の辺にプレイヤーが位置するような最小生成木ゲームを含む.コア,シャープレイ値などの解の概念をマトロイド理論におけるいくつかの問題に帰着することにより次の結果を得た.(1)最小基ゲーム(E,c)のコアが非空である必要十分条件は,マトロイドMが負の重みを持つ要素のみから成るサーキットを持たないことである.コアが空でないとき,E上の任意の最小基から,コアに属する1つの配分が得られる.(2)最小基ゲームの劣加法性あるいは,凹性は(独立判定性)オラクル多項式時間で調べられる.(3)最小基ゲームのτ-値が定義できる必要十分条件は,マトロイドMが負の重みを持つ要素のみから成るサーキソトを持たないことである。最小生成木ゲームのτ-値は,多項式時間で求めることができる.一方,最小基ゲームのτ-値を計算するオラクル多項式時間アルゴリズムは存在しない.(4)最小生成木ゲームのシャープレイ値の計算は,#P-完全であり,最小基ゲームのシャープレイ値を計算するオラクル多項式時間アルゴリズムは存在しない.
- 社団法人電子情報通信学会の論文
- 1994-07-25
著者
関連論文
- コンフリクト解消のアルゴリズム
- 給油施設操業スケジューリング (企業事例)
- 特集にあたって (ユーザのための数理計画応用)
- 多次元直方体被覆問題および充足可能性問題を解くアルゴリズム
- 緩和法による演繹データベースの問合せ評価
- 多変数同世代問題に対する問い合わせ評価法
- 多変数同世代問題に対する問合せ評価法
- 緩和法による演繹データベースの問い合わせ評価
- 多変数線形再帰型演繹データベースに対する逆数え上げ評価法
- 自己双対正論理関数の分解について
- 格子型光波網におけるパス割り当て問題に関する考察
- Serializable Classesの構造について(計算機構に関する数学的基礎理論とその応用)
- 先読みスケジューラによる分散型データベースシステムの並行処理制御(計算アルゴリズムと計算量の基礎理論)
- 版数制限をもつ先読みスケジュ-ラ
- グラフパッキング問題の計算複雑度(計算機科学の基礎理論とその応用)
- 内点法
- ランダム有向グラフにおける到達可能性と推移閉包の大きさについて
- 関係の推移閉包の大きさの近似的推定法
- 演えきデータベースにおける質問処理コストの近似的評価法
- Complexity of the Optimum Join Order Problem in Deductive Databases
- 辺連結度増加関数をO^^〜(mn)時間で計算するアルゴリズム
- 離散最適化とその応用 : 第5回公平分割と公平割当
- 豊島産業廃棄物不法投棄問題についてのコンフリクト解析
- Equilibrium Analysis for a Migration Model (Mathematical Decision Making under uncertainty and ambiguity)
- 公平分割とその手順
- 初等的フローゲームの凸性について(計算量理論とアルゴリズム論文小特集)
- The Existence of Equilibrium in Symmetric Arbitration Games FOA and DOA
- フローゲームの凸性について(ゲーム理論(2))
- Mark-Choose-Cut Algorithms for Fair and Strongly Fair Division
- Arbitration Under Different Information
- Research on Empty-Core Games
- 最終ダブルオファー仲裁(FDOA)の均衡戦略の解析について(ゲーム理論(1))
- マトロイド上の最小基ゲーム
- Double-Offer Bargaining Rule
- Offer Analysis for the Arbitration Procedure FDOA(MATHEMATICAL OPTIMIZATION AND ITS APPLICATIONS)
- Further Analysis of the Arbitration Procedure FDOA
- Intrinsic Gap and Final-Double-Offer Arbitration
- Arbitration for Bayesian Collective Choice Problem
- Intrinsic Gap and Final-Double-Offer Arbitration
- 多次元コスト関数をもつ有限オートマトンについて (情報科学の数学的基礎理論と応用)
- ある種の平面有向ネットワークの多品種流問題について(計算アルゴリズムと計算量の基礎理論)
- タブー探索による直交ラテン方陣の構成(連続と離散の最適化数理)
- 中間経由節点をもつKサーバー問題(計算機構とアルゴリズム)
- 最小容量カットアルゴリズムのプログラムによる効率の良い実現法
- 多重グラフにおける(λ+1)-カット
- 領域制約の下でのゲーム木探索(計算アルゴリズムと計算量の基礎理論)
- ゲーム木探索法SSSの非劣性について(計算アルゴリズムの基礎理論)
- 無向グラフ上の辺分離問題を解く簡単なO(mn)時間アルゴリズム
- 高信頼性ユニットからなる並-直列システムの漸近的に最適な保全政策(信頼性)
- 経済状態を考慮したアメリカンオプションの最適行使問題(ポートフォリオ)
- 33. 線形計画問題の高速解法 (アルゴリズムの最近の動向)
- Learning Algorithms for 2 × 2 Stochastic Games with Incomplete Information
- グラフ上の搬送スケジューリング問題の計算の複雑さについて(スケジューリング(2))
- グラフ上の搬送スケジューリング問題の計算の複雑さについて
- 遺伝アルゴリズムにおける交叉法に対する一考察(計算量理論)
- 1機械スケジューリング問題に対するSSDP法(動的計画法)
- 部分定義論理関数の正論理関数とHorn関数における関数分解について
- サブツアー交換交叉に対する二つのコメント
- サブツアー交換交叉に対する2つのコメント
- 不完全例題に対するプール的解析
- 鎖パッキング問題について(アルゴリズムの数学的基礎理論とその応用)
- ジャンケンのトーナメント表現と意味のある拡張(アルゴリズムと計算量理論)
- T-混合カットにおける領域間連結度の性質(グラフ・ネットワーク(5))
- 最小カット問題の簡潔かつ構成的な証明
- 平面グラフにおける辺遊離操作と辺連結度増大問題について
- Primal-Dual Proximal Point Algorithm for Multicommodity Network Flow Problems(MATHEMATICAL OPTIMIZATION AND ITS APPLICATIONS)
- Arbitrations when players have different information
- The Existence of Equilibrium in Symmetric Arbitration Games FOA and DOA(宮田亘朗教授記念号)
- 非線形最小費用流問題に対する双対ニュートン法(決定理論とその周辺)
- 年齢に依存した費用を持つ小修理・取替え問題についてII(信頼性)
- 年齢に依存した費用を持つ小修理・取替え問題について(信頼性)
- 平均費用規範最適小修理・取替え問題について(最適化理論とその関連分野)
- ある信頼性システムに対する修理限界取替え政策の最適性について(マルコフ解析)
- 平均費用規範最適小修理・取替え問題について(マルコフ解析)
- 多項過程モデルによるルックバックオプションの価格の上・下界評価(数理計画モデルにおける最適化理論)
- 多項過程モデルによるルックバックオプションの価格の上・下界評価(金融)
- 組合せ最適化ゲーム
- 反復ラインダイグラフの深さの浅い独立全域木
- 資産の収益率の相関がある構造を持つポートフォリオ選択問題について(資金・資本の流れ)
- ポートフォリオ選択問題における投資家の危険回避性と初期の富の影響(ポートフォリオ)
- ポートフォリオ選択問題における資産の収益率の確立順序(最適化の数理とその応用)
- グラフのサム数に対する上下界について
- 多期間ポートフォリオ選択問題における分離定理(計画数学とその関連分野)
- リーダー選出問題における時間最小アルゴリズムについて(計算アルゴリズムと計算量の基礎理論)
- 格子型光波ネットワークの再構成アルゴリズムについて
- 光波ネットワークのノード再配置アルゴリズムについて
- 双方向マンハッタン・ストリート・ネットワークの網再構成について
- データの論理的解析とブール関数
- データの論理的解析とブール関数
- 部分定義論理関数の内核関数と外核関数
- 2-単調正論理関数の同定問題に対する単純な高速アルゴリズム
- 論理関数の内包関数と外包関数について
- 不完全に定義された正論理関数の最大潜伏度について
- 正論理関数の最大潜伏度について(計算機構とアルゴリズム)
- On Chamberlinian-Ricardian trade patterns with many industries
- 大規模非線形計画問題に対する逐次2次計画分解法