ip68_LocationGame

第68回土木計画学研究発表会・秋大会での発表資料です。「立地行動における相互動学的意思決定とその解空間の性質」

Transcript

1. ⽴地⾏動における相互動学的意思決定と その解空間の性質 東京⼤学博⼠1年 増⽥ 慧樹 ⽻藤 英⼆ 2023年11⽉26⽇ (⽇) 第68回⼟⽊計画学研究発表会・秋⼤会@東京都⽴⼤学
2. • コンパクトシティの推進、災害の激甚化 ⽴地の規制・誘導施策 (⽴地適正化計画、災害危険区域、拠点再配置) 2 背景 例2. 洪⽔浸⽔想定区域内での⼈⼝増 (⽇本経済新聞, 2023.08.24) 浸⽔想定区域には市街地が形成さ れており、居住誘導区域から外す ことは現実的でない ⾏政は今後も居住誘導区域の利便性 を⾼める施策を打つだろう ⾏政・計画者 住⺠ 計画者と住⺠の相互の読み合いの結果、都市計画と⽴地が均衡に達する 異なる均衡がどのような場合に現れるのか 最適な都市計画はどのようなものか 例1. 南海トラフ地震の津波浸⽔想定区域内からの⾃主的な⼈⼝流出 (⽥中, 2013) 災害に安全な地域の需要が増えそ うなので、⾼台の住宅開発を⾏う 津波浸⽔想定区域内は、津波への不 安が⼤きいので、⾼台へ移転する ⾏政・計画者 住⺠
3. • 計画者 (供給)と住⺠ (需要)の相互作⽤ = ネットワークデザイン問題 • 朝倉 (1988): 計画者をleader, 旅⾏者をfollowerとするStackelbergゲーム → ⼆段階最適化として記述 3 理論的な背景 旅⾏者 (follower)の最適な経路選択𝒚を所与とした 計画者 (leader)の道路容量𝑪𝒂 の最適化 min 𝑪 $ " 𝑉 " # ⋅ 𝑡" 𝑉 " #, 𝐶" s. t. 𝑽′ = argmin 𝑽 $ " 4 % &! 𝑡" 𝑥, 𝐶" 𝑑𝑥 (上位問題: 総旅⾏時間最⼩化) (下位問題: 利⽤者均衡、⾏動モデル) 計画者の道路容量𝐶" を所与とした 旅⾏者 (follower)の経路選択𝒚 → Stackelberg均衡解 計画者は、旅⾏者の経路選択を⾒越した上で、最適な道路容量を決定 • ライドシェア市場 (Cai et al., 2023)、鉄道事業 (Li et al., 2023)など多主体間の 競合、再帰的意思決定の分析
4. • Stackelbergゲームは、⼀段階の相互作⽤しか扱わない = 住⺠は計画者の計画を先読みしない ← 実際は、住⺠は政策を予想し期待を形成（相互性） 4 Research gap 計画者 住⺠ 先読み Stackelberg 計画者 先読み … ⾏政は今後も居住誘導区域の利便性 を⾼める施策を打つだろう Stackelbergゲームを多期間に拡張し、計画者と住⺠の相互動学的な 意思決定を、展開形ゲームとして記述 → 均衡における⽴地、最適な計画を分析 • Stackelbergゲームは、時系列の意思決定ではない = 住⺠・計画者の決定変数に順序や時間は考慮されない ←住⺠や計画者の利得は、⽴地場所だけでなく「⽴地タイミング」 にも影響を受ける（動学性）
5. • 都市計画における多主体・時系列の意思決定 → 状態空間の爆発 5 理論的な背景 その2 ⼤規模な⽴地⾏動の展開形ゲームに対し、マルチエージェント強化学習 を適⽤ ← 多主体の意思決定過程と整合するフレームワーク 多主体の意思決定の均衡との関連付けはなされていない 最適な都市計画の時系列的な分析はなされていない → 深層強化学習により価値関数・⽅策を近似し、最適都市計画を提案 • AI-based urban planning (Zheng et al., 2023) 深層強化学習により⼟地利⽤と道路網の最適化。多主体×, 時系列×。 • AI Agent as Urban Planner (Qian et al., 2023) マルチエージェント強化学習 (MARL)を⽤いて、計画者、デベロッパー、住⺠の⽴ 地⾏動を記述。多主体◦, 時系列×。 • AI Economist (Zheng et al., 2022) MARLにより政府と住⺠の先読みを記述、最適課税を計算。多主体◦, 時系列◦。
6. 相⼿の⾏動に依存 • 問題設定: 災害リスク地域における都市施設配置と居住地選択 • 2地域 (High land, Low land)、2プレーヤー (Government, Residents) • 利得 6 ⽴地⾏動の展開形ゲームの記述 H (High) L (Low) 計画者 住⺠ 施設配置 居住 𝑢'() 𝒔 = 𝛽*(+, × ⾼台開発コスト + 𝛽 -.+/ '() × 住⺠の総リスク • ⾼台Hに初めに⽴地した プレーヤーに開発コスト • 低地Lが中⼼市街地 𝑢-0+ 𝒔 = 𝛽*(+, × ⾼台開発コスト + 𝛽-.+/ -0+ × 住⺠の総リスク +𝛽1.+, × 低地市街地からの距離 + 𝛽2-(3. × 都市施設との距離
7. • ゲーム⽊ 7 ⽴地⾏動の展開形ゲームの記述 計画者 住⺠ H L H L H L 𝑢'() 𝑢-0+ 𝑢'() 𝑢-0+ 𝑢'() 𝑢-0+ 𝑢'() 𝑢-0+ max 𝒈 𝑢'() 𝒈, 𝒓′ s. t. 𝒓′ = argmax 𝒓 𝑢-0+(𝒈, 𝒓) 先読み Stackelbergゲームの場合 ②計画者は、住⺠の反応を⾒越して ⾏動を決定 ① 住⺠は、計画者がH,Lの⾏動を 取ったそれぞれの場合について、 利得を最⼤化
8. • ゲーム⽊ 8 ⽴地⾏動の展開形ゲームの記述 多期間に拡張した展開形ゲーム 計画者 住⺠ H L H L H L 先読み 先読み 先読み ① 住⺠は各局⾯について ⾏動を最適化 ② 計画者は各局⾯について ⾏動を最適化 ③ 住⺠は各局⾯について ⾏動を最適化 ④ 計画者は初⼿の⾏動を最適化 後向き帰納法 均衡概念: 各プレーヤーは各局⾯で最適反応をとる = 部分ゲーム完全均衡 完備情報・完全情報 (合理性)を仮定: ・全プレーヤーは、プレーヤー集合、状態遷移、⾏動空間、利得などのルールを保持 ・全プレーヤーは、それ以前に⾏われた全ての意思決定の内容を観察できる
9. 2選択肢 (H, L), 3期 (3回ずつ⾏動) の均衡解の種類をパラメータ空間で表⽰ • Stackelberg均衡: 配置・居住する3箇所を同時に選択 (LHH, HHH) (HHH, HHH) (HHH, HHH) (LHH,HHH) (LLH,HHH) (HHH,HHH) 住⺠のリスク認知 低 住⺠のリスク認知 中 住⺠のリスク認知 ⾼ 住⺠の施設への近さ 重視 ⼤ ⾼台開発コスト max #!,#",## 𝑢%&' 𝒈, 𝒓′ s. t. 𝒓′ = argmax (!,(",(# 𝑢)*+ (𝒈, 𝒓) 9 静的なStackelberg均衡の場合 (LLL, LLL) (LLL, HHH) (LLL, LLL) (LLL, LLL) • 住⺠のリスク認知 低・中 : ⾼台開発コスト ⼩ & 住⺠が施設近さを重視 → ⾼台集中 それ以外 → 低地集中 住⺠は計画者の⾼台開発を予想、計画者は施設供給による需要誘発を予想 → 需要と供給の戦略的相補性 → Positive feedbackにより複数均衡
10. • 配置・居住する3箇所を、配置→居住→配置→居住→…と逐次的に決定 → 均衡における⽴地場所の組合せは、Stackelberg均衡とほぼ同じ 10 動的な部分ゲーム完全均衡 (LLL, LLL) (HLH, HHH) (LHH, HHH) (LLH, HHH) (HLL, HHH) (LLL, HHH) 住⺠の施設への近さ 重視 ⼤ ⾼台開発コスト (LLL, LLL) (LLL, LLL) 住⺠のリスク認知 低 住⺠のリスク認知 中 住⺠のリスク認知 ⾼ (HHH, HHH) 静的なStackelberg均衡に⽐べ、相互・動学的な意思決定を表現可能 • 住⺠のリスク認知 中・⾼ : 計画者が⾼台に施設配置するタイミングが異なる • ⾼台開発コスト⼩ & 住⺠が施設への近さを重視 → 計画者が先に⾼台に施設配置し、住⺠の⽴地を誘導
11. • ⾏動空間・期間数が増えると、考慮すべきゲームの状態空間が膨⼤に → 後向き帰納法により最適反応を列挙することは困難 → Multi-Agent強化学習 (MARL)の適⽤ 深層学習により各プレイヤーの状態価値関数と⽅策を近似 11 計算規模の拡張 – Multi-Agent強化学習の利⽤ ① ⽊探索 ② 各盤⾯の評価値と⽅策を学習 a1 aʌ1 a2 aʌ2 ɾɾɾ ܭըऀ ॅຽ ɾɾɾ ɾɾɾ ɾɾɾ ɾɾɾ ɾɾɾ ɾɾɾ 報酬 𝑣 ゲーム終了 • 汎⽤ボードゲームAI AlphaZero (Silver et al., 2018) ① モンテカルロ⽊探索により、各盤⾯の差し⼿と勝敗データを収集 （盤⾯ = 都市空間上の施設配置と居住⽴地、勝敗: 利得の増加度の⼤きい⽅が勝利） ②各盤⾯の勝率と⽅策を深層ニューラルネットワークで学習
12. • 学習済みのAlphaZeroは、各盤⾯ (都市空間の⽴地状況)における、計画者 と住⺠の最適な⽴地⾏動を計算する → 将来まで⾒越した互いの最適反応 → 巨⼤な展開形ゲームにおける部分ゲーム完全均衡の計算に等しい 12 AlphaZeroの解釈 ܭըऀ ॅຽ ɾɾɾ ɾɾɾ ɾɾɾ ɾɾɾ ɾɾɾ ɾɾɾ 最適反応 AlphaZeroの計算結果は、完備情報・完全情報下での⽴地均衡解 都市空間の各⽴地パターンにおける計画者・住⺠の最適な⽴地⾏動 後向き帰納法 AlphaZero H L H L H L
13. 計画者: AlphaZeroによる最適⽴地 住⺠: 1期先の利得を最⼤化する貪欲戦略 最適戦略において、 • 計画者は早期に⾼台に施設配置することで、 住⺠の⽴地を⾼台に誘導。 利得: 計画者(最適) -78.6, 住⺠(貪欲) -66.48 13 AlphaZeroの学習結果 ⼩ ⼤ リ ス ク 中⼼市街地
14. 計画者:1期先の利得を最⼤化する貪欲戦略 住⺠: AlphaZeroによる最適⽴地 最適戦略において、 • 計画者は早期に⾼台に施設配置することで、 住⺠の⽴地を⾼台に誘導。 利得: 計画者(最適) -78.6, 住⺠(貪欲) -66.48 • 住⺠は中⼼市街地周辺の⽴地と、⾼台への⾃ 主的な移転 利得: 計画者(貪欲) -98.4, 住⺠(最適) -62.98 14 AlphaZeroの学習結果 ⼩ ⼤ リ ス ク 中⼼市街地 ⼩ ⼤ リ ス ク 中⼼市街地 改善
15. 15 結論 • 計画者の都市施設配置、住⺠の居住地選択における相互・動学的な意思決 定を展開形ゲームを⽤いて記述。 • 利得が互いの⾏動に影響 → 相⼿の⽴地を誘導するような⾏動が⾒られた • 静的なStackelberg均衡に⽐べ、均衡における⽴地タイミングを分析可能 → 静的なネットワークデザイン問題の動学化 • 計算規模拡⼤に対し、部分ゲーム完全均衡と整合的なMulti-Agent強化学習 を適⽤ → 複雑な⾏動空間・多期間のモデルへの拡張可能性 ＜今後の課題＞ • 相互動学的な展開形ゲームの解析的な記述 → 動学的最適化・微分ゲーム • 完全情報の仮定の緩和 → 不完全情報ゲームの均衡との⽐較 • ⼆⼈ゼロサムゲームではない、⼀般的なMulti-Agent強化学習への発展 ← 学習の安定化のための技術
16. • ⽥中正⼈. (2013). 南海・東南海地震の激甚被害が想定される沿岸地域の⾃主的な⾼所移転の実態とその背景-和 歌⼭県串本町の事例を通して. 地域安全学会論⽂集, 21, 251-258. • 市街地内の⽔没危険地域で⼈⼝増 20年で60万⼈ ⾏政の居住誘導も 広域避難の体制必要.⽇本経済新聞. 2023- 08-24, ⽇経電⼦版, https://www.nikkei.com/article/DGXZQOUE221DL0S3A520C2000000/, 参照2023-11-19 • 朝倉康夫. 利⽤者均衡を制約とする交通ネットワーク の最適計画モデル. ⼟⽊計画学研究・論⽂集, 6:1–19, 1988. • Cai, Z., Mo, D., Tang, W., Chen, Y., & Chen, X. (. (2023). A two-period game-theoretical model for heterogeneous ride-sourcing platforms with asymmetric competition and mixed fleets. Transportation Research Part E: Logistics and Transportation Review, 178, 103279. https://doi.org/10.1016/j.tre.2023.103279 • Li, D., Islam, D. M. Z., Robinson, M., Song, D., Dong, J., & Reimann, M. (2023). Network revenue management game in the railway industry: Stackelberg equilibrium, global optimality, and mechanism design. European Journal of Operational Research, 312(1), 240-254. https://doi.org/10.1016/j.ejor.2023.06.044 • Zheng, Y., Lin, Y., Zhao, L., Wu, T., Jin, D., & Li, Y. (2023). Spatial planning of urban communities via deep reinforcement learning. Nature Computational Science, 1-15. • Qian, K., Mao, L., Liang, X., Ding, Y., Gao, J., Wei, X., ... & Li, J. (2023). AI Agent as Urban Planner: Steering Stakeholder Dynamics in Urban Planning via Consensus-based Multi-Agent Reinforcement Learning. arXiv preprint arXiv:2310.16772. • Zheng, S., Trott, A., Srinivasa, S., Parkes, D. C., & Socher, R. (2022). The AI Economist: Taxation policy design via two-level deep multiagent reinforcement learning. Science Advances. https://doi.org/abk2607 • Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., Lillicrap, T., Simonyan, K., & Hassabis, D. (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science. https://doi.org/aar6404 16 参考⽂献
17. Appendix
18. 各プレーヤーの合理性の変化 → 計画者の利得の変化？ • AlphaZero: 完全合理性の仮定 • Greedy: 1期先の利得を最⼤にする貪欲なプレーヤー 18 計画者と住⺠の合理性 • 住⺠が限定合理的な場合に AlphaZeroによる最適⽴地は 利得を増加させる • 住⺠が完全合理的な場合は 利得は増加しない ←パラメータ設定の影響も 住⺠の合理性ごとの計画者の利得
19. 19 計画者: AlphaZero vs 住⺠: AlphaZero
20. 20 計画者: Greedy vs 住⺠: Greedy
21. • コンパクトシティの推進、災害の激甚化 ⽴地の規制・誘導施策 (⽴地適正化計画、災害危険区域、逆線引き) 21 背景 例2. 洪⽔浸⽔想定区域内での⼈⼝増 (⽇本経済新聞, 2023.08.24) (浸⽔想定区域に)すでに市街地が形成されてお り、居住誘導区域から外すことは現実的でない 浸⽔想定区域だが、⾏政が居住誘導区域に設定し たので、今後も資産価値は増加するだろう ⾏政・計画者 住⺠ 例1. 南海トラフ地震の津波浸⽔想定区域内からの⾃主的な⼈⼝流出 (⽥中, 2013) 互いの⾏動の読み合い・相互作⽤ 計画者と住⺠の間の読み合いの結果、都市計画と⽴地⾏動が均衡に達している どのような場合にそれぞれの均衡が現れるのか 最適な都市計画はどのようなものか
22. 1. 背景 • 都市のコンパクト化・災害の激甚化→⽴地を誘導・制限する施策（⽴地適正化、災害危険区域、逆線引きの設定） • 浸⽔区域で⼈⼝が何万⼈増えた→⾏政:災害危険区域に設定しても移転は進まなさそう、住⺠:⾏政は既成市街地を⾒捨てないだろう→互いの読み合いに よって⽴地施策 (計画)と⽴地⾏動が均衡に落ち着いている • ⼀⽅で、南海トラフの想定被害地域では住⺠が⾃主的に⾼台に抜けて⾏っている地域も • では、どのような場合にそれぞれの均衡が現れるか、最適な⽴地計画はどのようなものかを解明する 2. 理論的背景 (Stackelberg) • 計画者 (供給)と経済主体 (需要)の相互作⽤は、Network Design Problemの枠組みで議論 • 朝倉 道路投資最適化を上位: 計画者の離散最適化、下位:旅⾏者の⾏動モデルとする⼆段階最適化として定式化 (Stackelbergゲーム) → ⽴地計画でいうと、上位:施策ゾーンの最適化、下位;居住地選択モデル • Bell 悲観的な旅⾏者の経路選択⾏動として信頼性分析に応⽤した • ライドシェア市場、鉄道市場など多主体の競合、再帰的な意思決定の表現に多く⽤いられている 3. 機械学習ベースの⼿法 (Computer-based Urban Planning, AI-economist)これをどう組み込むか。パラメタ設定は適当で、理論的な均衡の分析はない 4. Research gap • Stackelbergゲームは⼀段階の相互作⽤。住⺠が政府の計画を先読みすることはない→住⺠の側も政府の⾏動を合理的に予測するのでは？ cf) ルーカス批判、 合理的期待形成 ⽅針: 相互動学的な意思決定の表現に、Stackelbergゲームを多期間に拡張した展開形ゲームを採⽤。→⽴地計画の均衡を分析 状態数が膨⼤に→ゲームの⼤規模化に対応するため、MARLを⽤いる 5. 展開型ゲームの構造 • 問題設定: 災害危険区域における、⾏政の災害危険区域設定と、住⺠の居住地選択（状態と⾏動の定義）。利得の設定、パラメータを変えて均衡を⾒る • まずStackelbergのゲーム⽊ • 多期間に拡張した展開形ゲームのゲーム⽊ • 情報の仮定→完備情報と完全情報 6. 部分ゲーム完全均衡 • 均衡の定義は、部分ゲーム完全均衡。定義は、ゲーム⽊の各頂点でプレーヤーの戦略が最適反応となっている戦略の組のこと。全ての部分ゲームにおける純 粋戦略ナッシュ均衡。 • 解法: 後向き帰納法。⼀番最後の部分ゲームから順番に最適反応を決めていく（2選択3期でdemonstration） 7. 均衡解の分析 • まずStackelbergの均衡解 • 次に展開形ゲームの均衡解→あるパラメタ組み合わせで別の結果→解釈・考察 → 静的なStackelberg均衡と先読みと逐次選択を仮定した部分ゲーム完全均衡で⽴地の均衡が異なる→最適な計画も異なる →順番も最適化することの重要性。HLLとLLHの利得の違い 8. ⼤規模化・AlphaZeroの説明 • ⾏動空間、期間数が増えるとゲームの状態空間が膨⼤に→後向き帰納法による列挙は困難 • MARLによる状態価値、⽅策関数の近似。 • AlphaZeroの説明。Self-play with MCTSとDNNの学習の繰り返し。 9. AlphaZeroの結果とその解釈 • myopic, 少し先読み、AlphaZeroな住⺠に対する（合理性を変化）、計画者のAlphaZero, Stackelberg, ランダム？の政策の計画者の利得の⽐較 • 結果の解釈。先に計画者が⽴地することで住⺠を引き出している。 10. 結論・今後の発展の⽅向性 • ⼀般的なNDPの動学的な発展として • 居住地選択と⽴地計画の内⽣性を考慮した居住地選択モデルへの発展可能性 • 微分ゲーム • 不完全情報ゲーム 11. Appendix • 先読みを仮定する妥当性（high stakes, repetition + 不動産AI?） 22 ⾻⼦