離散最適化基礎論
2012年度後学期
金曜4限
岡本 吉央
テーマ：ゲーム理論における離散構造とアルゴリズム
期末試験
- 日時：2月15日 (金) 14:40〜16:10
- 場所：西2-101
- 問題
- 採点：1問20点満点，合計120点満点．成績はmin{100, 素点}に基づいて報告．
- 得点分布
- 解説と講評
- 本来の期末試験は2/15に実施したもので，都合の悪い学生のために2/13と2/19にも実施しました．
- 2/13と2/19に実施したものについては，個人特定があるので，回答状況についてはコメントしません．
- 2/13実施分
- 問題1：ナッシュ均衡の計算（双行列ゲーム）．3次元の多面体と2次元の多面体を描いて解くか，Lemke-Howson法を適用する．
- 問題2：ナッシュ均衡の計算（完全情報展開形ゲーム）．後ろ向き帰納法で解く．
- 問題3：凸集合の性質．定義に基づいて証明する．
- 問題4：コアの図示．
- 問題5：割当ゲームのコア．
- 問題6：オークションの耐戦略性．耐戦略性を満たさないことを示す例を作ればよい．
- 2/15実施分
- 問題1：ナッシュ均衡の計算（2人ゼロ和ゲーム）．2x2のゲームなので，卍のような図を描いて解くのが簡単．多面体を描いて解いてももちろんよいですが，時間がかかったかもしれないです．多面体を描いて解いたとき，一番下にある端点以外にもナッシュ均衡があることに注意．
- 問題2：ナッシュ均衡の確認（展開形ゲーム）．与えられた展開形ゲームを標準化して，ナッシュ均衡に対する必要十分条件を書いて，それを満たすようなuとvを見つければOK．uとvをちゃんと見つけるところまでいけば満点ですが，「存在する」とだけ書いてあるのは少し減点．
- 問題3：凸集合の性質．定義に基づいて証明する．これはちゃんとできてる人とできてない人の差が大きかったです．
- 問題4：経路選択ゲームと無秩序の代償．(2)で得られた解がナッシュ均衡になっていない解答が多く見られました．(2)で得られた解がナッシュ均衡であることを議論することも本来は必要ですが，それがなくても減点をしないことにしました．
- 問題5：0，1，-1だけを成分として持つ行列の行列式．これはちょっと難しい証明問題ですけど，証明の流れが大体あってる解答にはおおきく部分点を与えました．完答できている人は全体で満点の人です．
- 問題6：割当ゲームのコア．全体合理性，個人合理性，提携合理性の式を書けばよいです．割当ゲームなので，提携合理性については売り手1人買い手1人から成る提携だけを考えればよいです．
- 2/19実施分
- 問題1：ナッシュ均衡の計算（2人ゼロ和ゲーム）．3次元の多面体と2次元の多面体を描いて解く．
- 問題2：ナッシュ均衡の計算（完全情報展開形ゲーム）．後ろ向き帰納法で解く．
- 問題3：凸多面体の基礎．数えるだけ．
- 問題4：経路選択ゲームと無秩序の代償．講義でやった通り丁寧に計算すればよいです．
- 問題5：コアの図示．
- 問題6：Böhm-Bawerkの馬市場．講義でやった通り需要曲線と供給曲線を描く．
- 得点分布は3回分を合わせたもので，先行履修の人も含んでいます．0点の人はすべて期末試験を受けていない人です．
- 成績はAが14人，Bが4人，Cが3人，Dが11人 (内未受験者7人) です．
- 全体的な印象ですが，問題の数や計算の量が多い割に，全体的によくできているという印象を持ちました．特に，はじめの2問はよくできていました．コアに関する問題もよくできていて，この3問が完璧にできれば単位は取れています．
資料
コメント
- (13) オークション理論
- コメントありがとうございました．
- 来年度は離散最適化特論もお願いします．--- 離散最適化特論はありません．来年度も離散最適化基礎論です．やることは今年度と違うものにする予定ですが．
- わかったようでわからない...．単位が取れるように頑張ります．また来週お願いします．---わからないのは私の力不足です．でも，単位がとれるように頑張って下さい．
- 先行履修の単位の評価は学務情報システムを参照するとよいのですか？ ---たぶんそうですが，私の成績報告は先行履修の学生に対しては紙で行うことになっています (通常は学務情報システムから行います)．なので，もしかしたら先行履修の評価はすぐに学務情報システムに反映されないかもしれないです．教務課で確認して下さい．
- 前回の質問に対する回答で「連絡先を〜」とあったので提出するレポートの表紙にメールアドレスを載せたのですが，これでよいのでしょうか？ --- はい．添削しましたら連絡します．
- (12) 特性関数形ゲーム：離散構造とアルゴリズム (2)
- コメントありがとうございました．
- 買い手と売り手の利得の集合がコアの要素であるかどうか注意します．---はい，実生活にどんどんゲーム理論を取り入れていって下さい．
- 需要，供給曲線がどういう物なのかはじめてわかりました．需要が極めて少ないときは，供給も減るので結果的に高くなるのかなとも思いました．---バランスをとるように供給側が行動をするという次の段階があればそうなりますね．
- 単位が...欲しいです．問題のレポートは講義やオフィスアワー以外でも提出できますか？ ---はいできます．連絡先を書いておいてもらえれば，添削後に連絡します．
- 来週の授業で演習問題を出されると，レポートにして先生に添削してもらうのが難しくなるのですが，それでも演習問題はやるのでしょうか？ ---はいやります．添削必要な場合は直接提出して下さい．連絡先を書いておいてもらえれば，添削後に連絡します．
- 例年ではどの程度不可の人が出るのですか？ ---この授業は今回初めてなのでわかりません．そして，おそらく来年度は違うことをやるので，来年度に今年度のことが参考になることもありません．
- また来週お願いします．---はい，よろしくお願いします．
- (11) 特性関数形ゲーム：離散構造とアルゴリズム (1)
- コメントありがとうございました．
- 割当問題の制約を表す不等式系の係数行列がちょっとうまく理解できなかったので復習します．---後半急いだという認識がありますので，復習をお願いします．
- テストに関しては2/5,6の卒研発表にかぶらなければ基本的に大丈夫です．---すいません，説明が悪かったかもしれません．試験は2/15に行いますが，その日に都合が悪い人は別の日にもやります，ということです．
- 工事で道が封鎖されているので，授業に遅れる人が多いようです．多分．---なるほど．あの通行止めはちょっと不便ですが仕方ないですね．
- また来週お願いします．---はいよろしくお願いします．
- (10) 特性関数形ゲーム：基礎概念
- コメントを書いてもらう紙を持ってき忘れました．すいません．
- (9) 経路選択ゲーム
- コメントありがとうございました．
- 「社会的最適解と個人的最適解」という言葉が妙に印象に残りました．---社会全体の視点と個人の視点のバランスを取るというのが大事なんでしょうね．
- 「社会的最適解＝神，行政など第3者視点で全体の利益重視 (多少の被害者を出してよい (犠牲者？))」，「唯一の純粋ナッシュ均衡＝少しでも自分の被害を抑えたい個人の視点」，このような感じですか？ ---そうですね．特に「多少の被害者を出してよい」というところは社会的余剰を利得の和として定義したことに見られますね．そのため，利得の再分配を行うような仕組みが必要になったりして，それが協力ゲームの話に続いていきます．
- アメリカでは携帯電話の通信料金に対して従量制を用いていますが，これも全体的な通信環境の改善が目的とみればPigouの課税の一種と考えられますか？ ---携帯電話の従量制については携帯電話キャリアの収益が絡んでいるので，Pigou課税とは違うような気がします．Pigou課税は公共政策として課されるものを指すことが多い気がします．
- 43, 44の例では，結局純粋ナッシュ均衡での社会的余剰が変わらず社会的最適解の社会的余剰が減っています．純粋ナッシュ均衡での社会的余剰を増やすようにすることは一般にできないのでしょうか？ ---課金をするのではなくて賞を与えるという方向は考えられます．ただし，賞を与えるための財源が必要となりますが．
- 複雑な系で実際にナッシュ均衡や社会的余剰を求めるのは難しいと思いました． ---そうですね．そこにコンピュータサイエンスが様々な貢献をできる余地があると思います．
- 1ヵ月後にお会いしましょう！よいおとしを．--- よいおとしを．
- これまでで一番面白かったです．また来年．--- よいおとしを．
- 冬休みに単位取れるようにがんばります．たぶん．よいお年を．--- よいおとしを．
- (8) 展開形ゲーム：離散構造とアルゴリズム (2)
- コメントありがとうございます．
- 授業とは全く関係ないのですがpptはTeXのBeamer，図はTgifで作ってらっしゃるのですか？馬鹿なことを聞いてもうしわけないですが．--- スライドはLaTeXのbeamerスタイルを使っています．図はipeというアプリケーションで描いてます．ちなみに「ppt」はMS PowerPointを指します．
- 都知事選，衆院選と選挙が最近話題なので，暇があったら「選挙とゲーム理論」に関する話もお聞きしたいです．--- そうですね．協力ゲームの話をするときに触れたいと思います．
- n次式を1次に落せるのが面白いなと思いました．--- ここがトリックですね．
- ナッシュは何を見たんですか？また来週． --- 何を見たんでしょう．また来週．
- (7) 展開形ゲーム：離散構造とアルゴリズム (1)
- コメントありがとうございます．
- スライド31/43の例で，player 1がUを選んだ目の前でplayer 2がUを選ぶのは勇気が必要だと思いました．---なるほど．そういう視点は面白いですね．
- 今日の授業と最近読んだゲーム理論の本から「順序」の重要性がわかってきました．復習します．---順序はいろんなところで出てきます．特に，どの順番でいろんなものを好むのかという「選好」は意思決定における重要な構成要素です．この授業ではあまり選好自体を深く扱いませんが，それを数値に変換したものを利得として表現していると思ってもらってもよいと思います．
- 最初，自分の前の行動を覚えていないという状況が想像しにくかったですが，仲間の行動がわからないチーム戦と考えればわかりやすいと個人的に思いました．---そうですね．そのような解釈もありますね．
- 多変数関数を線形変換するなら，カーネル法は使えないのですか？---はい，使えます．ただし，そのときの変数の数が多くなってしまうのが欠点です．もともと，変数の数がn個あって，最大次数がdの場合には，カーネル法による線形化では変数の数がnのd乗個ぐらいになってしまいます．実際，これをナイーブに行うと，普通に標準化することと同じになってしまい，何も得をしなくなってしまうという困ったことになってしまいます．なので，次回は完全記憶ゲームに特化したうまい方法を紹介します．
- また来週．じゃなくて再来週．---じゃなくて3週間後です．
- (6) 展開形ゲーム：基礎概念
- コメントありがとうございます．
- 囲碁，将棋ときて，チェスはどうなんでしょうか．後，オセロなどは？---囲碁も将棋も完全情報ゲームですが，チェスやオセロもそうです．実は，解析の難しさで並べると囲碁＞将棋＞チェス＞オセロなので，そういう意味では，研究としてオセロやチェスはすごく進んでいます．いま，コンピュータソフトで人間に勝てないものをオセロなら割と簡単に作れるそうです．
- 後ろ向き帰納法がいろんな意味で面白いと思った．---ゴールから先に見て全体の戦略を決めるという例ですね．実生活でも応用できそうです．
- スライド44，Pr[u2で1がU]の分母はPUUU+PUUD→PUUU+PUDU，Pr[u2で1がD]の分母はPUDU+PUDD→PUUD+PUDDじゃないんですか？？？---ここは分かりにくかったかもしれません．PUUDとかのUUDはプレイヤー1による戦略の選択です．プレイヤー2の部分は考えていないです．はじめの「U」が初手 (つまりv1での選択)，2つ目の「U」はプレイヤー2が戦略をUを選択した後のプレイヤー1にとっての2手目 (つまりu2での選択，u1ではないです)，3つ目の「D」はプレイヤー2が戦略をDを選択した後のプレイヤー1にとっての2手目 (つまりu3での選択) を表しています．なので，ここの記述はただしいです．おそらく，u2にたどり着くまでのv1とu1における戦略の選択を見てるのだと思いますが，u1はプレイヤー2の情報集合なので，プレイヤー1の戦略を考えるときには見ないのです．
- スライド45で例えばPUUUはv1=Uと分かっているので，PUU*の様にU1を不定としてとっても良いような気がします．---すいません，ちょっと意味が分からないです．直接質問してもらうか，次回もう一度コメントとしてお願いします．
- ゲーム理論では最終的な利得は分かっていると考えているのでしょうか？---分かっていると考えないこともあり，そのような場合には情報完備ではなくなります．
- (5) 戦略形2人ゲーム：離散構造とアルゴリズム
- コメントありがとうございます．件数が減ってきていてさみしいので，どしどしください．
- ゲーム理論における未解決問題はどれくらいあるのですか？具体例もできれば知りたいです．---たくさんあります．未解決問題が学術分野を牽引しているといっても過言ではありません．特に離散構造に関係する問題で，講義で既に扱った内容で理解できるものを1つだけ挙げます．退化のない双行列ゲームに混合ナッシュ均衡はたくさんある可能性がありますが，最大いくつありえるのでしょうか？これが分かっていません．行列の大きさがn×nであるとして，Keiding (1997) は退化のない双行列ゲームの混合ナッシュ均衡の数が (だいたい) 2.598n以下に必ずなることを指摘しました．(「だいたい」というのはこれに定数とか多項式が掛ってることを意味します．) また，von Stengel (1999) は退化のない双行列ゲームで混合ナッシュ均衡の数が (だいたい) 2.414nになるものを作りました．つまり，混合ナッシュ均衡の最大数は (だいたい) 2.414nと2.598nの間にあることまでは分かってるのですが，その間のどこに真実があるのかは誰も知りません．他にも，このページの下に「オンライン文献」として挙げている「Algorithmic Game Theory」の中にはたくさんの未解決問題が挙げられています．
- 村松先生と同じ服来てませんでした…!?---同じ服ではないですが，同じ色でしたね．
- また来週---また来週．
- (4) 戦略形2人ゼロ和ゲーム：離散構造とアルゴリズム (2)
- コメントありがとうございます．
- 電気消してくだされ〜〜 ---これは講義中に指摘してもらえるとありがたかったです．
- パワポが見にくい．---PowerPointではないのですが，それはともかく，照明のことだったとしたら講義中に指摘してもらえるとありがたかったです．そうでない場合は，もう少し具体的に指摘してもらえれば対処できますので，お願いします．
- 論理的でよく分かりやすかった．主問題→双対問題への変形がミソですね．---そうですね，そこがミソですね．
- たぶんないんだろうけど，主問題の最適値と双対問題の最適値が等しくない場合のときの議論がなくて，気持ち悪かった．---それは説明していませんでした．実は，線形計画問題では，主問題と双対問題が最適解を持てば，その最適値が必ず一致することが知られています．これは線形計画問題の強双対性と呼ばれているものなのですが，この授業の範囲を外れるので省略します．線形計画法に関する教科書には必ず書いてある内容なので，興味があればそちらを見てみて下さい．
- 単体法の他の活用例，参考書籍等紹介頂きたいです．---単体法は線形計画問題を解くための1つのアルゴリズムに過ぎず，単体法自身が活用されるというよりは，線形計画問題が活用される，という認識の方がよいと思います．次の本には線形計画問題に限らず，いろいろな種類の最適化問題の活用例が示されています．
- 藤澤克樹，梅谷俊治，「応用に役立つ50の最適化問題」，朝倉書店，2009年．
- 去年の前期に村松先生が担当したとある授業では，こちらの単体法とは微妙にやり方が違う単体法を習ったのですが，その単体法を用いて今回の問題を解いても良いでしょうか？---はい，よいです．
- 非常に濃い内容だったので復習します．--はい，復習をお願いします．
- 次回，単体法を用いて，ゼロ和ゲームではない問題に取り組んでいくという事でとても楽しみにしています．---はい，お楽しみに．
- また来週．---また来週
- (3) 戦略形2人ゼロ和ゲーム：離散構造とアルゴリズム (1)
- コメントありがとうございます．
- 第2回の演習問題が開けません．---すみません．いま対応しました．開けると思います．
- 行列から2つの最適化問題を作る方法がよくわかりませんでした．---ここが今日のポイントだったので要復習ですね．期待利得を書き下して，それをxかyで整理します．そこから最小化問題を作る，という流れですね．まずは期待利得を書き下すところから始めて下さい．
- 再提出したい問題と新しく提出したい問題はひとつのレポートにまとめても良いでしょうか？---はい，よいです．
- 期末テストで色鉛筆とかを使って良いのですか？---はい，よいです．
- フォン・ノイマンの定理の証明について概要だけでも説明していただけないでしょうか．---次回時間がありそうだったらやってみます．
- フォン・ノイマンの様になりたいです．．．---フォン・ノイマンはゲーム理論だけではなく，量子力学の数学的基礎を作ったり，プログラム内蔵方式の電子計算機を作ったり，マージソートを発明したり，モンテカルロ法を考案したり，いろいろとしていますね．周りにいた人も天才だと呼んでいたようです．
- 条件付き最大/最小問題では，よくラグランジュ未定乗数法をつかうが，今回の講義ではそれが出ていない．ラグランジュ未定乗数法と，この講義とは直接的な関係はないのか？と思いました．---短い答えは「関係あります」です．まず，今日の部分は図を描いて解ける内容なので，ラグランジュ未定乗数法は使っていません．次回図を描けないところの話をしますが，そのときにラグランジュ未定乗数法と深く関係のある手法を使います．しかし，見た目上は全く違います．ラグランジュ未定乗数法の関係については少しややこしいので触れないつもりでいます．
- イラスト一件．
- (2) 戦略形ゲーム：基礎概念
- コメントありがとうございました．提出数がかなり減りました．どしどしお寄せ下さい．
- 今回の講義は，ナッシュ均衡以降の解説は分かりやすかった．しかし，抽象概念 (定義等) の理解が難しい．---凸多面体はまだ定義しか出てきていないので，定義だけではなかなか有用性が分からないですね．次回から徐々にでてくるので，その中で概念に慣れていけると思うので，少々お待ちを．
- 混合ナッシュ均衡の求め方を覚えることができました．男女の争いの場合は，相手が2/3以上の確率で自分の好きじゃない方を選ぶ場合は自分が相手に合わせた方が良いと解釈しました．---その通りですね．それが最適反応戦略になっている，というわけです．
- 混合戦略において，戦略や利得の取り方は自由度が大きいと思われます．これらの値を決める方法は，研究者個人に委ねられるのでしょうか，それとも，学会などの話し合いや，実例からの推定などで決めるのでしょうか？---「研究者個人に委ねられている」が最も近いです．そういう意味では，利得が何であるのか定めることには恣意が入り込む余地があります．また，混合戦略の解釈自体にもまた議論があり，人によっては混合戦略を認めないという立場を取ったりしています．そのため，純粋ナッシュ均衡が存在する戦略形ゲームに関する研究も深く進んでいます．
- 提出したレポートの解が間違っていた場合に答えは何らかの形で教えて貰えるのですか？もし，そうでなければ再提出は可能なのですか？---「答えが何らかの形で提示されるわけではないが，再提出は可能」というのが質問に対する直接の回答になります．
- 電気つけてもらったので，板書がよく見えました．---ありがとうございます．前回のコメントが活きました．
- また来週．---また来週．
- (1) ゲーム理論はじめの一歩
- コメントありがとうございました
- 囚人のジレンマで2人黙っていれば罪にならないと言っていましたよ---すいません，言ったことが間違いです．罪になるけど軽く済む，が正しいです．
- 板書をするときは電気をつけてほしい．暗くてちょっと見にくいです---ありがとうございます．スイッチが教壇から遠いのが難点なので，ボランティアを募る必要がありそうです．
- 演習時間が短かった---すいません，次回はなんとか15分確保します．
- 超平面やアフィン空間や凸集合など，初めて聞く概念が多々ありましたが，理解することができました．ただ，今回の速さのままですと今後理解が追いつかなくなることがあるかもしれません---今日は速かったですね．すいません．初回は準備することがたくさんあって速くなってしまいがちです．次回は少なめにしてみます．
- なかなか面白そうでした---面白くなるようにやっていきますのでよろしくお願いします．
- 説明が丁寧でわかりやすかったです---どうもありがとうございます．
- 数学用語の解説が有り，助かります．次回もよろしくお願いします．---数学のことばを忘れることはよくあると思うので，できるだけ補足することにします．
- 集合記号の読み方と，その使い方を明確にしてほしい．例えば，∀，∃，⊆，∈，などの意味を記号ではなく，日本語で．そして，これらの記号の使い方を明確に---これらは一応「離散数学」でやっている前提ですが，補足はしていきます．使い方は明確な (つまり，あいまいさなく行っている) ので，見直してみて下さい．
- とてもわかりやすかったです．でも，アフィン空間がうまく理解できなかったので復習します---ぜひ復習をお願いします．
- ある論文では最適化問題とゲーム理論は別分野として扱っていました．先生的にはこの考えはどう思いますか？---「分野」というのはあいまいな概念で，その境界を明確に定めることは難しいですが，最適化とゲーム理論が関係していることは確かです．ゲーム理論は多主体が関わる最適化問題に関わる理論を一部に含みます．また，ゲーム理論の問題を最適化の手法で解決することもあります．あまり「分野」という枠にとらわれない方がよいのかもしれません．
- iOS，AndroidどちらであってもAdobe Readerだと1部のページが見られないようです．他のアプリだと表示されるんですかね．---すいません，Androidとか持ってないので調べられないです．GoodReaderはどうでしょうか？ (有料ですが，うまく見れる保証を私がしてるわけではないので，自己責任でお願いします．)
- また来週---また来週．
- イラスト1件．
スケジュール (予定)
- 10/5 (1) ゲーム理論はじめの一歩
- 10/12 (2) 戦略形ゲーム：基礎概念
- 10/19 (3) 戦略形2人ゼロ和ゲーム：離散構造とアルゴリズム (1) (すなわち，線形計画法)
- 10/26 (4) 戦略形2人ゼロ和ゲーム：離散構造とアルゴリズム (2) (すなわち，線形計画法)
- 11/2 (5) 戦略形2人非ゼロ和ゲーム：離散構造論とアルゴリズム
- 11/9 (6) 展開形ゲーム：基礎概念
- 11/16 (7) 展開形2人完全記憶ゲーム：離散構造論
- 11/23 休講 (調布祭)
- 11/30 休講 (国内出張)
- 12/7 (8) 展開形2人完全記憶ゲーム：アルゴリズム
- 12/14 (9) 経路選択ゲーム
- 12/21 休講 (海外出張)
- 12/28 冬季休業
- 1/4 冬季休業
- 1/11 (10) 特性関数形ゲーム：基礎概念
- 1/18 休講 (センター試験準備)
- 1/25 (11) 特性関数形ゲームのコア：離散構造論
- 2/1 (12) 特性関数形ゲームのコア：アルゴリズム
- 2/8 (13) トピック
- 2/15 期末試験
オンライン文献
- Nisan, Roughgarden, Tardos, Vazirani (eds.):
"Algorithmic Game Theory," CUP, 2007.
http://www.cs.huji.ac.il/~noam/books.php の一番下
- Shoham, Leyton-Brown:
"Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations," CUP, 2009.
http://www.masfoundations.org/index.html の一番上の「eBook Download」
- 横尾 真, 岩崎 敦, 櫻井 祐子, 岡本 吉央：『計算機科学者のためのゲーム理論入門』シリーズ．コンピュータ ソフトウェア
[Teaching Top]
[Top]
okamotoy@uec.ac.jp
