ジジイですか？いいえ、２３歳です。

Roughgarden AGT本のChapter 17がよくわからない．どうもこの人はオンラインアルゴリズムになると説明が雑になるようだ．referenceに挙げられていた，Cesa-Bianchi 2006, 2007あたりを見るとよいのだろうか．

以下，よくわからない点を列挙．

*  adversaryの

昨日からずっと苦しんできたのがやっと解決したので、備忘録がわりに書いておく。

問題：macOS Sierraにアップデートしたら（？）Jupyter notebookの挙動がおかしくなった。

具体的にはnbextensionsが上手く機能しなくなった。local8888/nbextensionsにアクセスしようとしても404 not foundと出る。しかし一方で、以前作ったノートブックの拡張機能が微妙に残っていたり（foldingはできる）新しく作ったノートブックもfoldingができたり、markdownで何か書くたびに「python markdown latex \alpha^2」みたいなかんじの謎の行が逐一追加されるし・・・　と散々な状況だった。

解決策：Python環境を一から作り直した

1.

brew unlink pyenv

brew uninstall pyenv

brew install pyenv

pyenv install anaconda3-***

と前回学んだ方法を試すが、以前としてnbextensionsは使えない。

2.

jupyter notebookを起動するときに出ているエラーメッセージを参考にすることに（このメッセージ自体は以前から出ていたが、そのときは問題なかった）

error loading nbextensions みたいなのが出ていた。(ログ残しとけばよかった・・・)みた感じ、nbextensionsを起動するときに参照する場所がおかしい。

まず、これは関係ないかもしれないが、~/Library/Jupyterを消す（ここのファイルにアクセスするようなエラーメッセージが出ていたが、そもそもpyenv内で完結してないのがおかしい。pyenvを使い始める前の設定が残っていたのかも）

その次にbrew uninstall pyenvとしてpyenvを一旦消す。

次に、キャッシュ等をお掃除する。（多分これが効いた）

rm -rf ~/.local

rm -rf ~/.cache

rm -rf ~/.jupyter

rm -rf ~/.ipython

その上で再度pyenv+anacondaをインストール。

3.

いろいろ調べていたら、そもそも最新版ではanaconda+nbextensionsは相性が悪いらしい。

http://qiita.com/Tsutomu-KKE@github/items/1326e05eb992a8aa849d

ここを参考に

conda install -y -c conda-forge jupyter_nbextensions_configurator jupyter_contrib_nbextensions

としたらnbextensionsが使えるようになった。長い闘いだった・・・

（別のところではanaconda-nb-extensions

https://github.com/Anaconda-Platform/anaconda-nb-extensions

を推奨していたが、これは上手く動かなかった）

補足：

http://qiita.com/toohsk/items/69eaf2ff9283ad1d1345

途中で出た謎のエラー（pyenv uninstall anaconda**でいらないanacondaを消した後に、pyenv install anaconda3-**しようとしたら怒られた）への対処法はこのページの一番下の記述が参考になった。

ダニエルのスライドにあった証明がわかりにくすぎた（結局、一部間違ってるという結論に達した [10/13追記: 今日授業の後に質問してみたら、Danielは「increasingでなくてもmonotoneならよいのでは？確認してみるよ〜」と言っていた。）ので、自分なりにきちんと書き直してみたのだけれど、証明から得るものが多くて面白かったのでメモしておく。

まず、証明において記法はとても大事。オークションメカニズムAと均衡戦略βを任意にとってきていて、なにがその二つに依存しているのか（利得・期待し支払い・勝利確率は全て依存しているはず）を明確にしないと証明の途中で混乱する。

均衡戦略βは、対称であるだけでなく、増加関数である必要がある。でないと勝利確率Pの計算が複雑に。

収入同値定理の証明は極めて一般化しやすい。「利得＝勝利確率×（評価額ー支払額）＝勝利確率×評価額（期待利得）ー期待支払」を元に計算していくのだが、多少設定が変わっても根本のこの構造は変わらない。新しいオークション制度の期待収入について考える場合は、standard auctionにおける証明のどの部分が変わるか意識すればよい。

収入同値定理によれば、「プレイヤーの期待支払額＝勝利確率×自分の評価額が最大だという条件下での二番目に大きい評価額の期待値」となる。これを元に、いろいろなオークションの最適戦略が計算できる（左辺の期待支払額がどう変わるかを考えれば良い。）

「繰り返しゲーム」とあるけど、経済学でいう”繰り返しゲーム”ではなく、時間を入れたゲーム（展開系ゲーム）のことを指しているらしい。

3.1 ゲームの必勝法？

「一度に三つまでの数字が言えて、先に25言ったら負け」ゲームとその必勝法を例に、「二人・完全情報・決定的」な「ゲームには必勝法が存在し、先手必勝か後手必勝か引き分けかのいずれかが成立」であることが紹介される

（関係ないけど、これ、飲み会で馬鹿な人相手にやったら無限に酒飲ませられる気がする。）

3.2 ゲームの木

サイズが小さいゲームなら、ゲームの木を書いて後ろ向きに愚直に解けば必勝法がわかる。

3.3 負けにくい手を探す：ミニマックス法

サイズが大きいとき：静的評価関数（ゲームの途中状態の良さを評価）を定義し、評価値の大きいノードを選ぶようにする。これをMIN-MAX法という。評価関数の定義の仕方・先読みの深さ等の問題がある。（cf:水平線効果：先読みの深さを一定にしてしまうと、将来の損失が不可避の場合でも、本質的でない先延ばしの手を選んでしまう？）

3.4 ミニマックス法の高速化：アルファ・ベータ探索

略。分枝限定法と似てる気が。不必要なノードを展開しない。

3.5 略

3.6 失敗しないプランを探す：自然を相手に挑戦

体調を崩してしまい、長らく放置してしまった。

「点から平面への最短の線は垂線」という直感を一般化したい。

Pre-Hilbert Space: 線形空間に内積を入れたもの。内積からノルムが定義されるのでノルム空間でもある。Cauchy-Schwarzの不等式。中線定理。数列空間や関数空間の場合は、p=2のときに内積がdef可。

Hilbert Space: 完備。

直交性: 内積により直交性が定義される。ピタゴラスの定理。射影定理（証明は中線定理によってコーシー列を作る。なので、完備・閉が条件。）

直交補空間: 直交分解可能の証明には射影定理を用いる。なので、完備・閉が条件。

Gram-Schmidt: 正規直交系の構成法。pre-Hilbert上で成立。

今日から読み始めた。安田先生のHPhttps://sites.google.com/site/yosukeyasuda2/home/lecture/auction16に紹介があって知った本。

いくつかの均衡概念が紹介されている。

支配戦略均衡：（相手の合理性を考えずとも）「自分の合理性のみで自分のとる行動が決められる」という意味で最も要請の少ない均衡

反復支配戦略均衡：自分に加えて相手の合理性も仮定する必要がある。いつでも戦略が逐次消去できるとは限らないので、常に存在するとは限らない。

ミニマックス戦略：上の２つの均衡が存在しなくても、ゼロサムかつ鞍点が存在するゲームならば、お互いに最悪のケースの損を少なくするのが最適。

ナッシュ均衡：混合戦略まで許せば（唯一とは限らないが）常に存在。しかし、繰り返しの結果混合戦略に収束するかは自明ではない。（例えば、「お互いに利得が微増する方向に戦略を変化させる」と考えると、力学系のような図が描けるが、周回する可能性がある。）

ーーー

・均衡概念の比較は、昔学んだことはあるのだろうけど、改めて意識できてよかった。

・ミニマックス戦略は大事大事と言われている割によくわかってないのだけれど、鞍点と関係があると知れた。「線形計画法と関連させて理解できる」とどこかで読んだので、いつかそっちの方向からも理解すべきだなあ。

7:00起床、まばたきしたら9:00に。まあよしとしよう。

長野でゼミ合宿、からの母方の実家に寄ってじさまばさまに会って帰京。

ゼミ合宿：案外みなさん運動できる人種でびっくり。人狼を初めてプレイしたけど、みんなの思考の速さに全くついていけず。「多数決は票割れに弱いのでボルダルールにしましょう（冗談）」とかゲーム中にさらっというあたり、みなさんきちんと勉強しているんだなぁふへぇ・・・ってかんじ。特に何をしたわけでもなかったけど、のんびりしたよい合宿でした。

帰省：帰国後初めてじさまばさまに会った。とても喜んでくれたので行ってよかった。どちらも歳の割には元気な方だと思うのだけれど、声も腕も細くなっていたり、食事後に飲む薬ができていたり、やっぱり老けたなあという感じ。近頃は人と話す機会もめっきり減って、あまり料理もしなくなってきたらしい。お願いだからボケないでほしいなぁ。

おべんきょ：結局集合と位相の勉強は終わらず。（松坂の４章まで読んだ。）来月に持ち越し。Luenbergerもゼミが始まる前に４章まで読もうと思っていたけど、今晩３章まで読めるかどうか。集中してさほど詰まらずに読めた場合、一時間で５ページくらい読めるということがわかった。週に一章読むとして、教科書を読み進めるだけで加藤ゼミに8時間程割く必要があるらしい。

「8:00起床、からのyoutubeとニコニコでモー娘。動画を漁っていたら午前を溶かす。」というお決まりのアレをキメてしまった。夏休み途中からついてしまったこの悪癖、どうにかしないとマジで身を滅ぼしかねない。

「休日は駒場で勉強してるよ〜」と昨晩あんたんから聞いたので、午後は駒場へ。結構集中したはずなのに全然進まず。最近はもっぱら松坂の集合位相ばかりやって、たまにLuenbergerと『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』をちまちま進めようとしてるけど、どれも全然進まない。