A study on practical algorithms for combinatorial optimization based on approximate submodularity

点击翻译按钮获取中文摘要

初年度は、近似的劣モジュラ性と深い繋がりをもつ、ゲームのsmoothnessについて研究した。ゲームのsmoothnessとは、任意の実行可能解において、各プレイヤーの逸脱が最適値との距離を十分に縮めるという性質である。この性質は、ある一定の条件下において、局所探索のための近似的劣モジュラ性（localizability）と等価である。本研究では、情報がプレイヤー間で共有されていないゲーム（ベイジアンゲーム）において、smoothnessが満たされていれば、ある種のダイナミクスの収束先が近似的に最適であることを示した。このダイナミクスは、同じゲームを何度も繰り返す中で、各プレイヤーがオンライン学習のアルゴリズムに従って戦略を更新することで得られる。各プレイヤーがuntruthful swap regretと呼ばれる量を最小化すれば、このダイナミクスはコミュニケーション均衡（coordination mechanismとも呼ばれる）へと収束することを示した。untruthful swap regretを劣線形に抑える効率的なアルゴリズムを提案し、このアルゴリズムによって達成されるオーダーがそれ以上改善できないことも証明した。収束先のprice of anarchyがsmoothnessによって抑えられることから、このダイナミクスをシミュレートすることで、近似的に最適な均衡が計算できることが示唆される。この技術は、例えば既存のメカニズムから近似的に最適なメカニズムを導出するのに利用できると期待される。また、劣モジュラ最適化に関する書籍（相馬輔氏、宮内敦史氏との共著）を出版した。