メカニズムデザイン勉強会
書籍
メカニズムデザイン(書籍) 数学的にきちんとやる本
メカニズムデザインで勝つ 座談会の書き起こし的な本、内容はオークションに偏り
今回の流れ
メカニズムの定義からきちんとやると1時間使っても面白い話にたどり着けない気がするのでやりません
まず応用例をざっと眺める
具体的な問題の具体的なアルゴリズムを考える
そこから派生してオークションの話をします
その前に重要概念のザックリ説明
耐戦略的 see 耐戦略性の定義
嘘をついても得をしない仕組み(公明正大！)
効率的 see 効率性の定義
いい感じの仕組み(雑)
「誰も悪化させることなく、誰かをそれ以上改善することはできない」という帰結を導くことが出来る仕組み
メカニズムデザインの応用例
公共的意思決定
交換経済
オークション
公平分担
非分割財交換
マッチング
公共的意思決定
投票とか
詳しくは次回やります
交換経済
財の交換
ハーヴィッツ定理「効率性と個人合理性を満たす社会的選択関数はいずれも耐戦略性を満たさない」
戦略的操作は避けられないが、人数が多ければ戦略的操作の影響は減る
オークション
落札者と支払額を決める手続き
色々バリエーションはあるけど例:
ある一つの非分割財を、それの価値を最も高く評価してる人に売る
これは面白いので後でたくさん話す
公平分担
非分割財を金銭の移転を伴い配分する問題
例: 誰か一人がみんなのための仕事をし、他の人が対価を支払う
例: チームでモンスターを倒したらレアアイテムが出た、誰か一人がアイテムを受け取り、他のメンバーに対価を支払う
非分割財のオークションも金銭の移転を伴う
違いは
オークションの場合はアイテムを提供した「売り手」にお金がいく
公平分担は他の「受け取る可能性のあった人」にお金がいく
「非羨望的な資源配分は必ず効率的」(Svensson 1983)
効率性と耐戦略性が両立しない
効率性を水平性に弱めてもダメ
耐戦略性をベイジアン誘因両立性に弱めれば、非羨望性も満たす
非分割財交換
非分割財を金銭の移転を伴わずに交換する
例: 寮の部屋割りを交換する
Top Trading Cycleアルゴリズム(1974)
強コア配分を見つけ出す
強コア配分は効率性、個人合理性、耐戦略性を満たす唯一の社会選択関数である
Abdulkadiroglu and Sonmez (1999)
卒業生や新入生がいても大丈夫
このアルゴリズムが腎移植に応用されてる
非分割財交換: 非分割財を金銭の移転を伴わずに交換する
腎臓は非分割財
お金をやりとりしてはいけない想定
フィリピンでは臓器売買が認められてるけどね
交換？
腎移植の必要な家族のために腎臓を1つ提供する意思のある人がいる
しかし型が一致しなくて直接移植できない
ペア交換: (A,B)と(B,A)が互いにドナーを交換
リスト交換: (A,B)が腎移植待機リストの(,A)に腎臓を与える代わりに(,B)が待機者リストの優先権を得る
TTCの改良アルゴリズムで効率的で耐戦略的な交換が可能
マッチング
一対一マッチング 結婚問題 see 安定結婚問題 - Wikipedia
多対一マッチング 入学問題
ゲール＝シャプレーアルゴリズムが既に現実の問題解決に使われている。
研修医の病院割り当てや、早稲田大学の高校からの進学時の学部割り当て。
自身の選好を正直に表明することが支配戦略→耐戦略性がある
ここまでのまとめ
複数人の関係する問題についての意思決定の方法
いくつかの問題設定では「良い特徴をもった解が存在しない」ということが数学的に証明されてる
→条件をどこまで緩めれば解があるかが議論される
いくつかの問題では「良い特徴を持った解を導くアルゴリズム」が発見されている
→これを今の製品に応用することはありえる
「良い特徴」の一つが「耐戦略性」
嘘をついても得をしない
なのでみんな正直に行動する
個々人は「どういう嘘をつけば有利か？」を考える必要がなくなりコスト削減になる
サイボウズ的な表現をすればみんなを公明正大にする仕組み
問題設定
一人の赤ん坊がいる
二人の女A, Bがどちらも「私の子だ」と主張している
細かい設定: 真の母は1000万払ってでも子供を取り返したいと思っている、偽の母はそうではない
旧約聖書でのソロモン王の解決法
「子供を半分に切って二人で分けろ」
片方が母が「子供が死ぬよりはマシ」と相手に子供を差し出したので、そちらを真の母と認定した
このやり方はバレると使えなくなる
「差し出した方が真の母と認定される」ということが既知なら、真の母も偽の母も「子供を相手に！」と主張する
そもそも偽の母も子供の生存にゼロより大きな価値を感じてる可能性があり、その場合は偽の母も真の母同様に子供を差し出す可能性があった
西尾が今作った雑な決め方
子供は王のものとし、1000万で売る
真の母は1000万払って子供を買う
これで「真の母に子供を返す」は実現できるが1000万円負担させてしまうのが問題
後から返金するわけにもいかない
やはり「やり方がバレると使えなくなる」
返金されることが既知なら偽の母も「買いたい！」と言う
グレーザー=マーメカニズム(1989)
Aにどちらが真の母か聞く
Bだと答えたら子供はBのもの
Aだと答えたらBにどちらが真の母か聞く
Aだと答えたら子供はAのもの
Bだと答えたらBは1000万円を王に払って子供を得る、Aは多少の罰金を王に払う
実行するとどうなるか
Aが真の母である場合、Aが「自分が母だ」と答えるとBはそれを認める
なぜならBは1000万払いたくないから
Bが真の母である場合、Aは「Bが真の母だ」と答える
なぜならそうしなかった場合、Bが1000万払って子供を受け取り、自分は子供を得ることなく罰金だけ支払うハメになって損だから
どちらのケースも、誰も支払うことなく真の母に子供が渡る
三原=チン=ヤンメカニズム(2012)
子供をオークションにかける
オークションの敗者に少額の参加費支払いを課す
実行するとどうなるか
真の母はオークションに参加する
偽の母はオークションに参加しない
参加しても勝てない
何も得ることなく参加費を払うハメになる
これは損なので「オークションに参加しない」を選ぶ
真の母だけがオークションに参加するので不戦勝になる
オークションは割といろんな目的に応用しやすい？
オークション
非分割財を、その価値を最も高く評価している人に売りたい
しかしそれぞれの人が「どれくらいの価値だと評価しているか」は頭の中のことなので観測できない
=情報の非対称性がある
それぞれの人が利己的に振る舞った結果として「誰にいくらで売るか」が決まる仕組み(メカニズム)にしたい
封印型オークション
競りをやれば一番高く評価してる人がわかるが、そのためには時間的に同期することが必要
取引コストが大きい
代わりに各人が金額を書いた紙を箱に入れる仕組みでできないか？
一番大きな金額を書いた人を買い手に選ぶ
これはまあ自明
その人はいくら払うべき？
素朴に考えると書いた金額
それが本当に良い決定方法か？
オークションと耐戦略性
自分の評価してる額より高く入札しても損なので入札額を上げることはない
自分が二位以下の入札者である場合
どうせ買えないので下げることに損はない
自分が一位の入札者である場合
入札額を下げると、その分安く買えるので得
正直な評価額より低く入札するインセンティブが生まれてしまう！
=このメカニズムには耐戦略性がない
一番高い値段を入札した人が、二番目の人の入札金額を支払うオークション
耐戦略性の証明
各参加者の感じる価値v_i、入札額 b_iとする
自分以外の入札の最大値m_i = \max_{i\neq j} b_i とする
上記の図の通り、vi入札は他の入札に比べてイコールもしくは得である
よって感じた価値を正直に入札するのが最も良い(弱支配戦略である)
from ゲーム理論〔第3版〕 p.498
競り上げと第二価格オークション
実は競り上げと第二価格オークションは一致する
現実のオークションでは少し差がある
競り合ってるうちにヒートアップして冷静な時よりも高い価格をつけてしまう
競り上げの価格の刻み幅が大きいと誤差が大きくなる
他人の競り上げを見て「思ったより人気がある/ない」という情報を見て自分の評価額をアップデートする
人間は常に合理的に行動するわけではないので…
オークションその他の話題
価格の決定プロセスに透明性がある
この透明性が納得感に強く寄与する
例えば不動産の売却
複数の仲介業者に見積もりを取らせて、一番高かった業者に任せがち
しかし仲介業者は自分で買い取るわけではない
特殊な販路があれば別だが、もし買い手の集合に差がないとするなら「買い手の評価額の推定が下手で誤って高く推定した業者」を選ぶことになる
オークションでは価格を買い手の集団が直接決定するので、仲介業者の作為が入る余地がない(ように一見見える)
shill bidding
もし他人の入札価格を知りうる運営側の人間が入札に参加するなら、第二価格を釣り上げることができる
オークション後の執行
オークションで買い手が決まってから「やっぱ払いたくない」と言われると困る
自動的に実行されると良い
複数同質財オークション
例えば国債の発行など
同時競り上げオークション
異なる財を売りたい、例えば家を3軒売る
買い手は、例えば「家は一軒あれば十分」と思ってるかも知れない
→うっかり複数落札してしまうと困る
この時、個別のオークションを並列して行い、すべてが止まるまでビッドを受け付ける
オークションは契約付きマッチングモデル
同時競り上げ式オークションと安定マッチングのゲール＝シャプレーアルゴリズムは同じ構造
公共的意思決定
みんなで決める方法、投票など
詳しいことは次回やる
選択肢から一つ選ぶのではなくn段階評価する
中央値の一番高い候補を選ぶ
少し緩めた耐戦略性を満たす
という残念な結果をどう回避するかが研究されてる
確率的環境
平等確率独裁制
質疑
Q: メカニズムとアルゴリズムは同じ？
違う。
メカニズムは数学的なモデル see メカニズムの定義
「このモデルを仮定したら耐戦略性が満たされる決め方が存在する」などと議論する。
存在するのかしないのかが論点
数学的に解の存在が示せたとしても、その解を求める方法が存在するとは限らない。
実際トップトレーディングサイクルアルゴリズムがそう
シャプレーとスカーフがある数学的なモデルで都合の良い「決め方の数学的関数」が存在することを証明した
>強コア配分は効率性、個人合理性、耐戦略性を満たす唯一の社会選択関数である
その関数の具体的な計算方法を作ったのはゲール
存在だけではなく実際に構築する方法を見つけた
オークションを非集中的に行うことの難しさ
事前にデポジットを集めるとしたらその集める主体が信用されなければならない
オークションは主体が信用できる前提かも
人間が合理的でないと台無し？
少なくともオークションに関しては、合理的でない行動をする入札者は損をする
耐戦略性のあるメカニズムにおいては合理的に行動しない個人がいてもその個人が損をするだけなのでは
オークションにおいて、欲しくないのに一桁多く入札しちゃった人がいた場合「一番高く評価してる人に売る」という目的は達成できなくなるからやはり問題がある
投票と合理性に関して
メカニズムデザインによって「効率的」な解が得られるといっても、それは「個々人の好みが良い感じに満たされてる」というだけのことなので、個々人の好みが合理的でないなら合理的でない意思決定結果が得られる
ワクチンを打たずにパーティするのが好きな人ばかりの集団で投票をしたら、もちろんそれが選ばれる
この帰結が合理的かどうかはモデルの外の話
普通の多数決投票がメカニズムとして悪い点
ワクチン打ちたくない人が40%、打ちたい派が60%
「全員にワクチンを打ちます」の候補者が3人A,B,C、「全員にワクチンを打ちません」の候補者が1人D
この状況でA〜Cが各20%、Dが40%の得票でDが選ばれてみんなワクチン打たないことになる
多対一マッチング、多対多では？
決着した状態で1つの会社にN人の人が割り当てられてることを指して「多対一」という
マッチングの最中に多対多なのは一対一マッチングでも同じ
ヤフオク!の入札方法は「自動入札」と呼ばれるしくみ
上限額を入れておくと自動で競り上げる仕組み