Takahashi SATOSHI (高橋 里司)

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業, Category: 基盤研究(B), Fund Type: competitive_research_funding, Overall Grant Amount: - (direct: 13880000, indirect: 4164000)
交通渋滞において，交通網全体の混雑度を測ることは交通政策立案上重要である.その上で，混雑の適切な分散により混雑の緩和を実現する施 策が必要である.この問題の解決のために，混雑の均衡状態を分析する利己的経路選択ゲームによるモデル化を用いた分析や，公共政策のため のインセンティブ設計などを行う必要がある.本研究の目的は，(1)利己的経路選択ゲームを現実の交通をモデル化できるように拡張し，(2)そ の均衡状態を効率よく計算できるアルゴリズムを開発し，(3)適切な交通政策を立案できる機構を構築することである.

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業, Category: 基盤研究(B), Fund Type: -, Overall Grant Amount: - (direct: 12800000, indirect: 3840000)
本研究の目的は、(1)利己的経路選択ゲームを現実の交通をモデル化できるように拡張し、(2)その均衡状態を効率よく計算できるアルゴリズムを開発し、(3)適切な交通政策を立案できる機構を構築することである。本年度は、（1）都市交通における駐車場マッチング問題、（2）数理最適化を用いたメカニズムデザインの応用、（3）グラフニューラルネットワークを用いた情報推薦モデルの構築、の3つのテーマについて、研究を実施した。
（1）について、都市部における渋滞原因の1つとして、駐車場の探索に時間がかかるという問題がある。近年では、駐車場とユーザのマッチングが研究されているが、実用化の側面での研究は少ない。本研究では、Deferred Acceptance Algorithm（DAA）とBoston Algorithm（BA）の2種類のマッチングアルゴリズムの性能評価を行った。DAAは安定マッチングを出力するアルゴリズムとして知られてる。一方、BAはアルゴリズムが単純で高速に動作するが、安定マッチングの保証はない。一般にユーザはマッチング結果全体を観測することができないため、BAでも実用に耐えうると考えられる。評価実験では、動的環境でのマッチング成立率、成立までの時間を評価し、BAの有用性を明らかにした。
(2)について、数理最適化を用いたメカニズムの解析手法の応用として、クラウドファンディングに対するメカニズムの解析を行った。結果として、経済的に望ましい性質を有するメカニズムの存在性を示すことができた。本手法を経路選択における渋滞緩和メカニズムに適用し、解析することを考えている。
(3)について、グラフニューラルネットワークを用いたSession baed recommendationの新しいモデルを提案した。ECサイトの購買データを用いた評価では、既存手法よりも推薦精度が向上することを示した。

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3500000, indirect: 1050000)
There are two major achievements in this project. The first one is to show that the upper bound of the iterations of Facial Reduction Algorithms (FRA) applied to a (nonlinear) cone containing polyhedral cones, depends only on that of the nonlinear part; in other words, we can safely ignore the polyhedral cones at least from the viewpoint of FRA. The other is to extend two of Chubanov's algorithms proposed for homogeneous LPs using projection and rescaling to symmetric cones and semi-infinite polyhedral cones, respectively. For these algorithms, we implemented them only for the semidefinite programming problem and conducted numerical experiments. The latter algorithm evaluates the number of iterations using the "volume" of the feasible region as the conditional number. Especially if if the condition number is zero, then FRA, the main theme of this project, should be applied to the conic programming problem.