科目ナンバー

SG-IG5-7C41

履修条件・関連科目等

授業で使用する言語

日本語／英語

授業で使用する言語（その他の言語）

授業の概要

不確実性や複数の意思決定者を伴う最適化問題を対象に，アルゴリズムの設計・解析を学ぶ．オンラインアルゴリズムにおける競合比解析の基本手法の修得を目指す．さらに，選好付きマッチングと公平割当を取り上げ，メカニズム設計・配分設計の観点からアルゴリズム的手法の位置付けを学ぶ．

科目目的

本講義の目的は，不確実性や複数の意思決定者を伴う最適化問題に対するアルゴリズム的アプローチの基本を理解し，課題設定に応じて適切な設計方針を選択して解法を構成できる能力を養うことである．

到達目標

- オンラインアルゴリズムについて，競合比解析の枠組み理解し，アルゴリズムの性能を理論的に評価できる．
- メカニズム設計の観点から，効率性・公平性・戦略性などの性質を踏まえてアルゴリズム的手法の位置付けを説明できる．

授業計画と内容

1. ガイダンス
2. 乱択オフラインアルゴリズム1 (乱択クイックソート、最小カット問題)
3. 乱択オフラインアルゴリズム2 (同一性判定問題、Max-3SAT問題)
4. 決定性オンラインアルゴリズムの競合比解析1 (競合比の定義、スキーレンタル問題)
5. 決定性オンラインアルゴリズムの競合比解析2 (ページング問題、kサーバー問題)
6. 乱択オンラインアルゴリズムの競合比解析1 (Yaoの原理、スキーレンタル問題、ページング問題)
7. 乱択オンラインアルゴリズムの競合比解析2 (アドバーサリモデル)
8. 秘書問題
9. 預言者の不等式
10. 選好付きマッチング問題 (安定マッチングの基礎)
11. 選好付きマッチング問題 (安定マッチングの発展)
12. 住宅割当問題・市場問題
13. 公平割当問題
14. まとめ

授業時間外の学修の内容

授業終了後の課題提出

授業時間外の学修の内容（その他の内容等）

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

成績評価の方法・基準（備考）

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

実施しない

アクティブ・ラーニングの実施内容（その他の内容等）

授業におけるICTの活用方法

実施しない

授業におけるICTの活用方法（その他の内容等）

実務経験のある教員による授業

いいえ

【実務経験有の場合】実務経験の内容

【実務経験有の場合】実務経験に関連する授業内容

テキスト・参考文献等

References:
- Allan Borodin, Ran El-Yaniv: Online Computation and Competitive Analysis
- Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani: "Algorithmic Game Theory"
- Tim Roughgarden: "Twenty Lectures on Algorithmic Game Theory"

その他特記事項

参考URL