確率過程としての乱択計算論

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

アルゴリズム設計において，乱択化（randomization）は理論的にも実用上も不可欠な基本技法である．本課題は，「ランダムネスは計算にどのように寄与するか？」という問いに対し，とくに計算効率に焦点を当てた理論発展を目的とする．決定性計算を決定性過程と捉え，同様に乱択計算を確率過程と捉えて，決定性過程と確率過程の対比をもってランダムネスの計算効率への寄与を測る点が本課題の特色である．この目的に沿って，決定性過程と確率過程を対比する技術の開発，この技術に関連する応用または基礎研究に取り組み，また，計算効率にとどまらない乱択計算論の新展開も目指す．ゲーム論における繰り返しゲームの確率過程解析を動機として，非推移的サイコロの研究に取り組んだ．非推移的サイコロは，サイコロの目が一般化されたサイコロの組で，サイコロの組を上手に設計すると，Efron's diceで知られる例のように，強弱関係が非推移的になることが知られる．本研究ではまず，一般化じゃんけんにおけるゲーム論的に無駄な手の議論を参考に，非推移的サイコロにおけるゲーム論的に無駄なサイコロ（戦略）について議論した．そして，繰り返しゲームの解析の準備として，ある種の公平性の下，非推移的サイコロが非自明な均衡をもつための条件について明らかにした．得られた成果をAAAI 2021で発表した．このほか，決定論的カオスの計算量に関する研究や動的グラフ上のランダムウォークの研究なども推進し，萌芽的成果を得た．