研究者詳細 - 田村　明久

競争的研究費の研究課題 - 田村　明久

分割表示 33 件中 1 - 20 件目／全件表示 >>

2021年07月

2025年03月

科学研究費助成事業, 平井広志, 田村明久, 河瀬康志, 挑戦的研究(萌芽), 補助金, 未設定

近年，その潜在的重要性が増してきた双方向市場のオークションに対する「真に使える」理論の創出を試みる．そのために現実世界の複雑な制約を考慮した汎用的なモデルや評価尺度の数学的定式化を行い，そのモデル・評価尺度のもとで，効率的なアルゴリズムの開発を行う．解析には，離散凸解析やポリマトロイドフロー等の離散最適化の高度な理論を駆使する．得られた成果は，国内・国際学会・査読付きジャーナルへの投稿をとおして世界に発信する．
本研究課題は、双方向市場におけるオークションに対し、現実的な制約を考慮した一般性の高いモデルのもとで優れたアルゴリズムの構築を目指すものである。特に、予算制約という実用上重要な制約に注目し、そのもとでの理論の深化に取り組んだ。こうしたオークションは、これまで可分財を対象とする多面体的クリンチングオークションというアルゴリズムにより発展してきたが、本研究課題では整数制約に対処することで、これを不可分財のモデルへと適用できるように拡張した。さらに、提案アルゴリズムにおける買い手の脱落について構造的な特徴付けを行うことで、パレート最適性・流動的余剰・社会的余剰に係る効率性の理論的保証をそれぞれ与えた。これらの成果をまとめた論文は、2024年度にアルゴリズム的ゲーム理論の主要誌の一つである ACM Transactions on Economics and Computation に掲載された。また、この論文の成果を土台として、より弱い仮定のもとで適用できて優れた性質を満たすアルゴリズムが研究協力者によって提案されている（現在投稿中）。さらに、2024年度には、ミクロ経済学の研究者を対象とする研究集会（第30回DCコンファレンス）において、共著者の招待講演の中でこれらの成果を発表することができ、経済学コミュニティへと本研究課題の成果を展開することができた。その他にも、研究協力者によってクリンチングオークションの効率性および収入の単調性に関する研究が進められた。2024年度には、予算が等しいという仮定のもとで、買い手がオンラインで到着する場合の単調性について新たな成果が得られた。こうした成果は、双方向市場と関係のあるソーシャルネットワーク上のオークションに応用できるものである。研究成果をまとめた論文は、マルチエージェント分野のトップ会議であるAAMAS 2025 に採択された。

インセンティブ設計科学の創出

2020年04月

2023年03月

科学研究費助成事業, 横尾真, 神取道宏, 田村明久, 関口格, 牧野和久, 川越敏司, 鹿島久嗣, 基盤研究(A), 補助金, 未設定

本研究では，種々のインセンティブ／誘因に対する人々の反応を解明すると共に，人々に適切なインセンティブを与えることにより，個人の目的と社会の目的を適切に調和させて持続可能な発展を可能とする社会制度の設計に関する「インセンティブ設計科学」と名付けた新しい文理融合型の学問領域を創出する．具体的には，中核となる人工知能／最適化技術に社会科学の知見を統合し，インセンティブ設計科学に関する理論構築，被験者実験による評価を行う．さらに，学校選択制，研修医マッチング，公共事業入札，周波数オークションなどの応用分野において，政策提言とソフトウェアライブラリの開発準備，webアプリケーションの提供を行う．
2022年度および繰越の2023年度を合わせて18件の査読付き論文出版と，16件の学会発表 (内3件が招待講演) を行った．マッチンググループでは，両方向マッチングにおいて，学校の定員が外生的に与えられるのではなく，資源割当によって内生的に与えられるモデルを提案し，公平性と効率性を高いレベルで両立可能な耐戦略的なメカニズムを設計した．本成果は人工知能分野のトップジャーナルであるArtificial Intelligence に採録されている．オークショングループでは，ソーシャルネットワークを通じて，メカニズムの参加者を募り，その際に本来はライバルとなり得る他の参加者をメカニズムに招待する誘因を与え，耐戦略性を満たす交換メカニズムを設計した．本成果はエージェント分野の最難関の国際会議である Int. Conf. on Autonomous Agents and Multiagnt Systems (AAMAS) において論文が採録されている．人工知能／最適化グループでは，最適化問題を解く際に敵対者が存在し，解の一部を改竄する可能性がある状況で，改竄の影響を最小限に留めることを目的とする，敵対者が存在する場合のMaxSAT問題についての理論的検討を行った．本成果は人工知能分野の難関国際会議であるPacific Rim International Conference on Artificial Intelligence (PRICAI)に採録されている．行動／実験経済学グループでは，両方向マッチングにおいて参加者が複数のタイプに分割され，タイプごとの上下限制約が存在する場合のメカニズムについて実験的考察を行った．
令和4年度が最終年度であるため、記入しない。
令和4年度が最終年度であるため、記入しない。

マーケットデザインの実践的理論の構築

2017年04月

2020年03月

九州大学, 横尾真、神取道宏, 櫻井祐子, 船木由喜彦, 田村明久, 東藤大樹, 安田洋祐, 関口格, 岩崎敦, 基盤研究(A), 補助金, 研究分担者

平成29年度は主に，(a) TTCメカニズムの一般化，(b) 一般化受入保留メカニズムの代替メカニズムの提案，(c) 繰返しオークションにおける協調行動の解析，および (d) 均衡解析プログラムの拡張の4つの課題に関して研究を推進した．本年度の成果は，招待講演3件，論文出版10件，国際会議発表19件，および国際共同研究2件に上る．
課題 (a) では，TTC の拡張に成功し，初期保有がある環境において下限制約を満足するマッチングメカニズムを提案した．提案メカニズムは耐戦略性とパレート効率性を厳密な意味で満足する一方で，既存のメカニズムの単純な拡張と比較すると，期待値的により公平なマッチングを保証する．本研究成果は，人工知能分野で最も権威ある論文誌である Artificial Intelligence より出版されている．また，国際共同研究として複数の初期保有があるケースへのTTCの拡張を行い，その成果が国際論文誌 Journal of Artificial Intelligence Research に採択されている．
課題 (b) では，割当数の比率に関する制約を新たに考案し，一般化受入保留メカニズムを拡張することによって，この制約の下で公平なマッチングを保証するメカニズムを設計した．本研究成果は，エージェント分野で最も権威ある国際会議であるAAMAS-2018にて報告予定である．さらに，割当制約の一般化についても，計画を前倒して検討を開始しており，既にいくつかの成果を得ている．
課題 (c) および (d) では，均衡検証プログラムを，他者の行動の（不完全な）観測の構造がサイクルを構成するケースに対して拡張し，新たな均衡戦略の発見に成功した．本研究成果は国際ワークショップ AGT-2017 にて報告し，フィードバックを経て現在英文論文誌への投稿を準備中である．
各研究課題について，計画した内容を順調に達成できた．また，課題 (a) では副次的な成果として，TTC の異なる拡張に成功し，その成果が人工知能分野の一流論文誌である JAIR に採択されるなど，計画以上に進展している．さらに課題 (b) では，予想以上に順調に研究が進んだことから，計画を前倒しし，平成30年度に予定していた研究を既に開始している．特に，割当制約の一般化について，既にいくつかの結果を得ており，こちらも計画以上に進展している．
平成30年度は，平成29年度の研究成果を拡張・一般化するとともに，割当制約の一般化（担当：マッチング理論班・検証班），三角取引の均衡解析（担当：設計班・オークション理論班），離散構造上の社会選択（担当：設計班・検証班・マッチング理論班）の3つの研究項目に取り組む．設計したメカニズムは，アルゴリズムとして定式化し，ソースコードを公開する．得られた研究成果は，学術論文として，計算機科学・経済学分野の論文誌や，AAMAS/AAAI/IJCAI などの国際会議録より出版し，関連研究コミュニティに発信する．メカニズムの設計が計画どおりに進まない場合には，既存の様々なメカニズムの評価を重点的に行う．特に，検証班を中心とする被験者実験によって，現行の制度と既存のメカニズムにおける人間の振舞いの違いを洗い出し，ゲーム理論の均衡概念の実問題・各事例における信頼性を詳細に議論する．また，既存メカニズムの実行時間を計算複雑性の理論に基づいて明らかにし，大規模な問題への適用を可能にする近似アルゴリズムの提案を行う．

複雑な制約下での離散資源配分問題：離散凸解析を武器としての探求

2016年04月

2020年03月

文部科学省・日本学術振興会, 科学研究費助成事業, 田村　明久、野寺隆, 基盤研究(C), 補助金, 研究代表者

本研究課題は，離散凸解析という良い離散構造をもつ枠組みを武器として，離散的な配分において，プレイヤーが複数存在する状況下で，プレイヤー全体やその部分集合が設定する複雑な制約を満たしつつ，個々のプレイヤーが満足する配分とは何かという解概念とそれを求めるアルゴリズムを研究し，現実問題へフィードバックすることを目的としている.
平成29年度については，武器である離散凸解析の強化という意味で，昨年度提案した整凸関数のサブクラス（離散中点凸関数）についてさらに研究を進め，2近傍定理とよぶ性質を明らかにし，離散中点凸関数に関する最小化アルゴリズムを構築した．昨年度示したスケーリングに関して閉じている性質，近接定理と合わせて論文としてまとめ学術雑誌に投稿した．また，研究集会でもこの成果を発表した．
またTTC（トップトレーディングサイクルメカニズム）に離散凸解析を導入したメカニズムを開発した研究成果が査読付き国際会議であるThe 7th International COnference on Autonomous Agents and Multiagent Systems に採択された．
学術雑誌に投稿した2編の論文「学生にグループ分けのある学科配属問題 - 離散凸解析の適用例」と「Scaling, proximity, and optimization of integrally convex functions」がそれぞれ掲載または掲載受理となった．また前者の研究において作成したプログラムが平成29年度にも利用され，現実へのフィードバックという意味においても貢献した．
学術雑誌に投稿した論文については掲載または掲載受理となり，離散凸解析の強化という意味で取り組んだ研究も最小化アルゴリズム構築まで至り，学術雑誌に投稿した．現実へのフィードバックも継続中であり，おおむね順調に進展している．
平成30年度以降の当初予定の研究（テーマ1c）「3つのM#凹関数を用いたモデルに対する完全なアルゴリズムの構築」，(テーマ1d)「M#凹関数を用いたモデルに対する代替性への拡張」，（テーマ3）「複雑な制約下での戦略的頑健性をもつアルゴリズム設計」を推進するとともに，昨年度から取り組んだ「離散凸解析の強化」についても（テーマ4）「他の離散資源配分問題への適用」を念頭に研究を進める．

持続可能な発展のための資源配分メカニズム設計理論の構築

2012年05月

2017年03月

九州大学, 横尾真、神取道宏, 田村明久, 船木由喜彦, 関口格, 坂井豊貴, 平山勝敏, 尾山大輔, 安田洋祐, 岡本吉央, 岩崎敦, 川崎雄二郎, 小野廣隆, 櫻井祐子, 東藤大樹, 上田俊, 伊藤孝行, 小島武仁, 小原一郎, 基盤研究(S), 補助金, 研究分担者

本研究プロジェクトでは、我が国の持続可能な発展のために、計算機科学とミクロ経済学の技術を統合／発展させ、経済的、社会的、環境的な観点からの要求をバランスした、希少な資源の望ましい配分を実現するメカニズムの設計理論を構築することを目的としている。具体的には、資源配分メカニズムの設計、解析、表現技術に関して研究を推進し、特に、制約付き両方向マッチングにおけるメカニズム設計、ノイズのある繰り返しゲームの均衡解析、協力ゲームに関する表現技術に関して顕著な成果が得られている（査読付き国際会議87件、国際論文誌74件、国内論文誌11件、著書8件、教科書の執筆4件、招待講演40件）。

グラフの因子，マイナー，部分グラフに関する極値問題の総合的研究

2012年04月

2017年03月

科学研究費助成事業, 太田克弘, 藤沢潤, 田村明久, 石井一平, 小田芳彰, 山下登茂紀, 榎本彦衛, 小関健太, 土屋翔一, 野口健太, 佐久間雅, 基盤研究(B), 補助金, 未設定

極値グラフ理論の問題は，グラフ H を固定するとき，与えられたグラフ G が H と同型な部分グラフを含むための辺数あるいは最小次数に関する最善の十分条件を求めることである．本研究では，因子問題，マイナー，部分グラフに関する問題を統一的な視点から俯瞰することにより，新たな問題提起を行い，展開研究を行った．とくに，森グラフの極値問題，弦付きサイクルやシータグラフを点素に見つける問題，マッチング拡張性などを重点的に扱った．また，グラフ理論の大きな未解決問題の一つであるHadwiger予想との関連において，グラフのρ彩色の概念を導入し，次数列に関するHadwiger予想の簡潔な証明を与えた．

数論的アルゴリズムの研究を通したエルゴード理論の新たな展開

2012年04月

2016年03月

科学研究費助成事業, 仲田均, 厚地淳, 田村要造, 田村明久, 福山克司, 夏井利恵, 浜正樹, 井上賀絵, 石川史郎, 盛田健彦, 江居宏美, 基盤研究(B), 補助金, 未設定

エルゴード理論の研究はその初期から現在に至るまで数論の研究と密接な関わり合いを持ってきた。とりわけ、実数の2進あるいは10進展開や連分数展開の研究は依然として多くの未解決な問題があり、また一方で情報科学における暗号理論、通信理論などからの要請による新しい研究課題も多く存在する。本研究では連分数展開などの収束、近似の問題あるいはユークリッドアルゴリズムの計算コストの評価を確率論的に取扱い、新たな知見を得ることができた。また、一様分布論など関連する周辺分野についてもいくつかの新しい結果を得た。

離散構造の導入による離散資源配分問題の深化

2012年04月

2015年03月

文部科学省・日本学術振興会, 科学研究費助成事業, 田村　明久、太田克弘，小田芳彰，南美穂子, 基盤研究(B), 補助金, 研究代表者

学生の学科への配属や研修医の病院への配属の決定という離散資源配分問題は実用性の高い重要な問題である．グラフ構造や離散凸解析などの離散構造を導入し，安定マッチングモデルを一般化して適用範囲の広い離散資源配分問題を構築し，その解析を行うことを目的とした．
包括的な離散資源配分問題に対する戦略的頑健性をもつメカニズムの構築，安定マッチングモデル（2部グラフ上のモデル）の一般の有向グラフへの拡張等の研究を実施し，雑誌論文6編，投稿中の論文2編，執筆中論文2編の成果を得た．

離散凸パラダイムによる最適化統一理論

2009年04月

2015年03月

東京大学, 室田一雄、田村明久, 岩田覚, 塩浦昭義, 森口聡子, 垣村尚徳, 小林佑輔, 土村展之, 基盤研究(B), 補助金, 研究分担者

工学や社会科学の諸分野における最適化の理論と応用を「離散凸パラダイム」によって統合する研究を行った．離散凸解析の理論と応用を，連続・離散軸，凸・非凸軸，分野横断軸，の３つの観点から整理することによって，個々の数理的技法や応用諸問題の相互関係を明確にし，数理の深化，応用の開拓，ソフトウェアの整備の３つの観点から研究を行い，新たな展開を達成した．とくに，数理の深化については，Ｌ凸関数最小化アルゴリズムの詳細な解析やＤＣ計画の枠組みの提示などの成果をあげた．

アルゴリズムのエルゴード理論的研究

2009年

2011年

科学研究費助成事業, 仲田均, 田村明久, 厚地淳, 田村要造, 夏井利恵, 勝良健史, 宮崎琢也, 浜正樹, 石川史郎, 福山克司, 吉田雅通, 江居宏美, 盛田健彦, 井上賀絵, 基盤研究(B), 補助金, 未設定

数論に現れるアルゴリズムを中心にその可測力学系としての性質を研究し、エルゴード理論、ディオファンタス近似論、一様分布論の新しい研究成果を導き出した。とりわけ、非アルキメデス的数体上の非同次ディオファンタス近似論、非アルキメデス数体を係数とする多項式に対するユークリッドアルゴリズムの計算回数の評価、区間交換に対するRauzy inductionのエルゴード理論的性質、実数に関する多次元連分数アルゴリズム、一様分布の誤差の広がりに関して新しい所見を得た。

禁止マイナーによって特徴づけされたグラフに関する研究

2008年

2011年

科学研究費助成事業, 太田克弘, 田村明久, 小田芳彰, 石井一平, 中本敦浩, 山下登茂紀, 藤沢潤, 基盤研究(B), 補助金, 未設定

与えられたグラフの部分グラフから,辺の縮約を繰り返して得られるグラフを,元のグラフのマイナーと呼ぶ.平面グラフなど重要なグラフの族はマイナーに関して閉じており,禁止マイナーによって特徴づけされる.これまでに知られていた平面グラフなどにおける閉路,全域木,因子に関する問題を,禁止マイナーの観点から拡張することを行った.とくに完全2部グラフをマイナーとして含まないグラフのタフネス,全域木に関する性質で顕著な成果が上がった.加えて,禁止部分グラフによる同種の問題にも成果があった。

離散凸パラダイムの深化と拡大

2006年

2008年

東京大学, 室田一雄、田村明久, 岩田覚, 土村展之, 森口聡子, 塩浦昭義, 基盤研究(B), 補助金, 研究代表者

経済学,システム工学,最適化理論,アルゴリズム理論などの広汎な分野における基礎的諸問題に関わる離散構造を,離散凸性という横断的視点から整理し,「離散凸」という新しいパラダイムを確立し,それを広範囲の応用分野に浸透させる研究を行った.「離散凸パラダイム」の横糸を成す,構造定理やアルゴリズムを代表とする離散関数に関する数理の研究と,縦糸を成す,諸応用分野における具体的な諸問題に対する研究を行った.

連続体現象における非線形諸問題の数学解析

2006年

2008年

科学研究費助成事業, 谷温之, 前島信, 下村俊, 野寺隆, 田村明久, 吉沢正紹, 石川史郎, 井口達雄, 高山正宏, 杉浦壽彦, 伊藤成治, 田中尚人, 伊藤弘道, 伊藤成治, 田中尚人, 伊藤弘道, 基盤研究(B), 補助金, 未設定

連続体および連続体近似できる自然現象の数理モデル方程式を数学解析し, 次のような研究成果が得られた(主要なもののみ記す).
(1) Navier-Stokes方程式, Stokes 方程式に対して, 区分的に連続な境界を持つ領域, 角領域での強解の一意存在 ; (2) Navier-Stokes方程式に対して, 滑り境界条件(Navier型, 閾値型) 下での強解の一意存在 ; (3) 水の波(渦なし非圧縮Euler方程式の自由境界問題) の長波近似, 浅水波近似の正当化 ; (4) 自己重力作用下での流体星(化学的に活性な圧縮性粘性流体) の1次元問題および3次元球対称問題の滑らかな時間大域解の一意存在 ; (5) 弾性体に対するいくつかの亀裂問題の可解性.

離散凸解析を用いた数理経済モデル

2005年04月

2006年03月

慶応工学会, 研究援助費, 田村　明久, 補助金, 研究代表者

大規模離散最適化問題の劣モジュラ的構造に基づく解析と高速アルゴリズム開発

2004年

2007年

京都大学, 藤重悟、田村明久, 牧野和久, 平井広志, 基盤研究(B), 補助金, 研究分担者

平成16年度〜19年度に亘る本研究において,劣モジュラ的な新しい構造の発見,知見及び新しい効率的なアルゴリズムの開発などの多くの成果が得られた.主要な成果としては,以下のものが挙げられる.
1.離散凹関数と上下限付き手付を導入することにより,安定結婚モデルや割当モデルの統一モデルを提案し,さらにはこのモデルが常に安定な解を持つことを構成的に示した.この統一モデルは既存の多くのモデルを包含するものであり,既存のモデルの有する離散構造の本質を明らかにした.
2.木構造ネットワークにおける動的フローと施設配置問題を複合した1-センター問題の動的フロー版として考えられる問題に対して,動的に構造変更が可能な平衡2分木である区間木を用いた高速アルゴリズムを導出した.
3.劣モジュラ関数を一般化した双劣モジュラ関数を最小化する多項式時間アルゴリズムを求め,さらに,その強多項式時間アルゴリズムを初めて構築した.
4.木構造ネットワークに対する単調なmin-max型連結分割問題の初めての多項式時間アルゴリズムを開発した.また,単調でない場合のmin-max型連結分割問題,min-sum型連結分割問題は,NP困難であることを示した.
5.グラフ上の半教師付き学習のための学習機械「電気回路判別器」を提案した.この判別器は非線形電気回路理論に基づいて構成され,データセットを電位の符号によって分類するものである.
6.ネットワーク設計問題として広く研究されているソース配置問題や外部ネットワーク問題などの自然な拡張として最小横断問題を考察し,ある種の劣モジュラ的な条件の下での最小横断問題に対する多項式時間アルゴリズムを開発した.また,このアルゴリズムを用いることで無向ネットワークにおける外部ネットワーク問題も効率的に解けることを示した.

幾何的配置問題の計算量限界と近似可能性の研究

2004年

2007年

科学研究費助成事業, 加藤直樹, 田村明久, 大崎純, 瀧澤重志, 特定領域研究, 補助金, 未設定

1.前年度に開発した無交差ラーマングラフをすべて列挙するアルゴリズムにおいて、実用的な観点から、出力されるグラフのクラスに制限を課した列挙アルゴリズムを開発した。一つは最大次数の上限が与えられている場合で、もう一つはあらかじめ辺集合を指定し、それらを含まないグラフに限定するものである。これらは、いずれも計算困難であることが予想されるが、実用的なアルゴリズムを開発した。
2.逆探索法によって列挙された静定構造物(ラーマングラフ)に対して,節点座標と部材断面積を連続変数として,指定された性能(大変形挙動)を満たすコンプライアントメカニズムを求めた。また,節点数と計算量の関係を検討し,最適な解を求める際の計算量限界を明らかにした。
3.無交差全域木の高速列挙アルゴリズムを開発した。その計算時間の理論的性能評価とともに、計算機実験をおこない、その実用的な性能を評価した。
4.火災等の発生時における建物内部から安全な外部への最適避難経路(最大移動時間最小化問題)や、津波や大地震発生時に安全な建物・地域への最適避難経路を求める問題を考察した。実用的な観点から、格子状ネットワーク、木構造ネットワークに限定し、通路幅一定、途中での枝分かれを許さない、経路が交差しない等の制約下での最適経路群を求めた。またGISや実データを利用し、通行可能経路が確率的に定まるような実際的な問題への導入も検討した。
5.LRTなどを模した線的施設配置問題について研究した。駅と線路からなる平面上の全域木において、利用者の総移動時間を最小化するような、ネットワークのトポロジーを求めるヒューリスティクスを開発した。

離散凸解析におけるアルゴリズムの研究

2003年04月

2005年03月

文部科学省・日本学術振興会, 科学研究費助成事業, 田村　明久、藤重悟，室田一雄，太田克弘, 基盤研究(C), 補助金, 研究代表者

本研究課題では、「M2凸関数最小化に対する多項式時間の開発」、「連続M凸関数最小化と連続L凸関数最小化に対する解法の研究」、「離散凸解析と効率的に解ける凸関数最小化問題との関連性の解明」という3つの研究目的を設定した。
第1の目的に関しては、研究分担者である室田と岩田、森口が、等価な問題であるM凸劣モジュラ流問題に対する多項式時間解法を開発した。
第2の目的については、研究を継続中である。
第3の目的に対しては、関連した幾つかの研究成果を得た。大きく分けて2つの流れができた。
第1の流れは、マッチングモデルと呼ばれる数理経済モデルにM凹評価関数を導入することで、既存の多くのモデルを含む幾つかのモデルを提案した(主に研究代表者の田村と分担者の藤重が担当)。さらにM2凸関数最小化アルゴリズムのアイデアを応用することで、これらのモデルに安定マッチングが常に存在することを構成的に示した。また、この構成法は擬似多項式時間アルゴリズムとなっており、実効定義域が0-1超立方体に含まれるとする多くの既存のモデルの状況では多項式時間アルゴリズムとなる。また、田村とFarooqはM凸関数の持つ数理経済的特性についての研究も付随して行った。
第2の流れとして、室田はジャンプシステム上にM凸性という概念を拡張し、その最小性基準を示し、最小化アルゴリズムを提案した。ジャンプシステム上のM凸関数最小化やその拡張は今後も引き続き研究するべき課題である。
その他として、田村はM凸関数最小化問題に対し、座標軸ごとにスケーリング係数を独立して持たせるという今までにないアイデアを用いて多項式時間解法を開発した。

離散凸パラダイムの確立

2003年

2005年

東京大学, 室田一雄、田村明久, 岩田覚, 土村展之, 塩浦昭義, 松浦史郎, 基盤研究(B), 補助金, 研究分担者

本研究課題の目的は,経済学,システム工学,オペレーションズ・リサーチ,最適化理論,アルゴリズム理論などの広汎な分野における基礎的諸問題に関わる離散構造を,離散凸性という横断的視点から整理し,「離散凸」という新しいパラダイムを確立することにある.本研究課題では下記に挙げた研究成果を得ることが出来た.いずれの研究成果も査読つき国際会議や学術雑誌に採択されている.
(1)離散双対性に関わる最適化問題,とくに,M凸関数を目的関数に含む劣モジュラ流問題に対して,容量スケーリング手法に基づくアルゴリズムを提案した.一般のM凸劣モジュラ流問題に対して,このアルゴリズムはこれまでで最良の時間計算量をもつ.
(2)離散凸解析の枠組みとは独立に研究されてきたマルチモジュラー性という概念が,実質的にL凸性と等価な概念であることを示した.この結果をふまえ,整数格子点上で定義されたマルチモジュラー関数に対する離散分離定理などの諸性質を導いた.
(3)2次のM凸関数と木距離の間の密接な関係を示した.より具体的には,2次のM凸関数のヘッセ行列は実質的に木距離行列(にマイナスを掛けたもの)であることを証明した.
(4)整凸集合上の離散不動点定理を与えた.これは,数理経済学における一般均衡理論ならびに非協力ゲームへの応用をもつ.
(5)M凸関数の概念が,数理経済学で良く知られた粗代替性や単改良性と等価であることを明らかにした.
(6)離散凸解析の数理経済学への応用として,複数の不可分財と貨幣からなる市場において競争均衡が存在するための条件を与えるなどの理論構築を行うとともに,競争均衡を求めるアルゴリズムをM凸劣モジュラ流問題の枠組みを利用して開発した.

半正定値計画の組合せ最適化への応用と解法の研究

2001年04月

2002年03月

文部科学省・日本学術振興会, 科学研究費助成事業, 田村　明久、降旗大介，藤江哲也，室田一雄，大浦拓也, 基盤研究(C), 補助金, 研究代表者

研究実績は以下のとおり.
本研究課題では、半正定値計画問題と離散凸解析に関連したいくつかの結果を得た。これらの結果は、International Symposium on Algorithms and Computation, Conference on Integer Programming and Combinatorial Optimizationなどの国際会議で成果発表をするとともに学術雑誌に投稿し、その内の幾つかは掲載あるいは掲載予定となった。ここでは、これらの結果の内7つについて概要を説明する。
1)藤江と田村は、最大重み安定集合問題の凸緩和の理論を一般化安定集合問題へと拡張し、さらに最大重み安定集合問題での幾つかの結果に対する簡単な証明を与えた。
2)室田らは、群論的対称性を持つ半正定値計画問題に対して内点法が求める解も群論的対称性を持つことを示した。
3)室田らは、行列の疎性を生かした半正定値計画問題に対する技法を提案した。
4)室田と田村は、M凸劣モジュラ流問題を利用することで、ある種の経済モデルの競争均衡の存在判定を効率的に行なうアルゴリズムを構築した。
5)田村は、M凸関数最小化問題に対する新たなスケーリング技法とこれを用いた効率的なアルゴリズムを構築した。
6)田村と室田は、M2凸関数、L2凸関数といった各種の離散凸関数に対する近接定理を示した。
7)田村は2つのL凸関数の合成和として定義されるL2凸関数に対して、合成和を等号で達成するような新たなL凸関数の合成和が存在することを示した。この性質を用いることで、L2凸関数に関する近接性などの諸性質が容易に証明できる。

離散最適化における準凸性の理論の構築と社会工学への応用

2001年

2003年

京都大学, 室田一雄、塩浦昭義, 田村明久, 萌芽研究, 補助金, 研究分担者

まず,数理経済学における離散凸関数の応用について研究を進めた.不可分な財を含む経済均衡モデルにおいて,供給者の費用関数がM凸関数かつ消費者の効用関数がM凹関数の場合に競争均衡が存在することが,研究代表者らの昨年度までの研究において証明されていた.本年度はさらにこの研究を進めて,競争均衡を実際に求める方法について検討し,多項式時間で競争均衡が求められることを示した.具体的には,競争均衡を求める問題を元にしてM凸劣モジュラ流問題をつくり,これを既存の多項式時間アルゴリズムで解いて得られた出力を適切に変換することで競争均衡が得られる,という手法である.これはM凸劣モジュラ流問題の応用としても興味深い結果である.
次に,最適配分問題に対する効率的な解法の研究を行った.生産ラインでのバッファ配分や労働力・資源の配分など,生産システム設計の際に頻繁に現れる最適配分問題は,離散準凸性の理論を適用しやすい問題の一つである.離散準凸関数の理論を踏まえて,現実に現れる最適配分問題を定式化し,その離散構造を明らかにすると共に効率的な解法を提案した,具体的には,劣モジュラ制約の元での最適配分問題に対するHochbaumの高速解法がなぜうまく働くのかを離散凸性の視点から検討し,その結果を元にM凸関数に対する高速な最小化アルゴリズムを提案した.
また,dial-a-ride transit system, isotone regressionなどに応用をもつ,双対最小費用流問題について研究を進めた.この問題が準L凸関数最小化問題の特殊ケースである,という事実を踏まえ,既存の解法を見直し,準L凸関数に対する解法へと拡張した.

　前のページ - 次のページ　

田村 明久

競争的研究費の研究課題 - 田村 明久

田村　明久

競争的研究費の研究課題 - 田村　明久