数理マジック，マッチング理論（4年ゼミ）

一人目，数理マジック．
ここしばらくはダウン・アンダーといったカードディールの方法について追っている．
前回まで操作の長さが「ダウン・アンダー」といった長さ２のものを考え，
この場合には2進数表記が有効に働いて
最後にどのカードが残るかなど色々と説明ができた．
今回から「ダウン・アンダー・アンダー(DUU)」などといった，
冪乗枚数で区切ると説明がつくタイプでないものを考えてきてもらった．
どうやらDUU単一では法則が見えない感じなのだが，
UDUやUUDを並べて書くとアルゴリズム的には法則が見えてくる．
しかし，何かまだ場当たり的なので，もう少し様々な場合について調べてもらうことに．
その際，Scratchで実験できると良いだろう，とちょっくら作ってみた．

二人目，マッチング理論．
1対多バージョンのマッチング理論に入って，
今回はこの場合でのDAアルゴリズムによるマッチングの安定性について．
こちらは1対1と並行した証明が可能だった．
次に，DAが片側最良マッチングであることの証明と，
このアルゴリズムが耐戦略性を持つことについて．
ただ，一時，耐戦略性の定義を巡って路頭に迷いかける．
要は選好組に対してマッチングを対応させる写像がNash均衡点を持つ，
という意味なのだが，選考組については何ら条件がなく，
どんな選考組もNash均衡点になってしまうのでは？
という勘違いだった．
実際には均衡点の比較自体に選考組を使っているから，
大丈夫なんだ，ってことになった．
では次回までにきちんと見てきてもらおう．
あ，その際，以前卒論に追われて
どさくさ紛れに買ったテキストが有効だと気づき，早速貸し出した．

マーケットデザイン入門―オークションとマッチングの経済学

メカニズムデザイン―資源配分制度の設計とインセンティブ