NISHIO Hirokazu[日本語][English]

Quadratic Votingはなぜ平方根を取るのか

2023-07-13 Quadratic Votingはなぜ平方根を取るのか

image

  • 既存のAかBかを選ぶ二択投票において、投票者は+1か-1の投票しかできない($v_i \in {-1, +1}$)
    • それを足し合わせたもの$\sum_i v_i$が0より大きければAの勝ち
  • でも人によって「どれくらい強くその結果を望んでいるのか」$u_i$は異なる
    • 投票者は+1か-1の投票しかできない($v_i \in {-1, +1}$)
    • その結果「Aであることがとても大事なんだ！」($u_i = +10$)の人と「どっちでもいいけど、どっちかといったらBかな〜」($u_i = -1$)の人の投票が同じ力を持ち相殺する
    • よくないね！
  • そこで「どれくらい強くその結果を望んでいるのか」$u_i$を表明させることにする
    • しかし素朴に「どれくらい強い？」と聞いたら多い数を答えた方が自分の望む結果になる確率が高まるのでみんな上限いっぱいの強さを主張して実質一人一票になってしまう
    • だから「強さ」を大きくすることに対してコスト$c(v_i)$の支払いを要求する
    • このコストをどう設計するのが「良い」かなというのがこの論文のトピック
  • まず「良さ」を定義する必要がある
    • robustly optimal:$ \sum v_i$ と $ \sum u_i$ が同じ符号であること
    • つまり票数を足し合わせた場合の判断結果と、「気持ちの強さ」を考慮して足し合わせた場合の判断結果が一致すること
  • Mueller (1973) と Laine (1977)が提案したmarginal pivotality of votes $p$に全員同意しているとする
    • 1票入れた時の結果が変わる確率
    • この仮定はかなり強い仮定だと思う
    • 多分入れないと解が出ないんだと思う
  • この場合の合理的な投票数は$2u_i pv_i − c (v_i)$を最大化するものになる
    • なぜこうなるのかは書いてない
      • (のでmarginal pivotalityに関する他の論文にあるのだろう)
      • 追記:
        • 2はcの部分で吸収されるのでどうでもいい、結果Aの効用が$+u_i$でBの効用が$-u_i$だから2倍になる
        • pは「1票あたりのpivotality」なので$pv_i$がpivotalityになり、$u_i$を掛けることで期待効用になる
    • Slideでナッシュ均衡を使って説明してる
    • リンク切れてた、論文はこれ(著者の名前が同じなので): Nash Equilbria for Quadratic Voting
  • これらの仮定を置いた場合、cが二次関数である場合に限りrobustly optimalになることが証明できる
    • 証明は別紙で展開されていて、本文では簡単に要約している
    • 簡単に言えば
      • $2u_i pv_i − c (v_i)$が最大化されているのだからvで微分すれば0になる
      • $2pu_i = c(v_i)'$が成り立つ
      • robustly optimalであるためには$u_i \propto v_i$(比例する)のが都合がいい
      • そうなるのは$c$が二次関数の時だけ

具体例

  • 3人の投票者がいて、気持ちの強さが+2, -1, -1であるとする
  • 一人一票の投票ならマイナスが2票でマイナスの勝ち
  • QVの場合は気持ちの強さに比例した投票が行われてプラスマイナスゼロで均衡すると考える
    • この時プラスの人は4のコスト支払いをしている
      • 若干直感的でないように思う
      • (人は「気持ちの強さ」と「支払う額」を同一視しがち)
  • 1ドル1票などの、固定コストの場合(=票数とコストが比例する場合)
    • プラス側はマイナス側よりも一票に大きな効用を感じている
    • どちらの一票も同じ価格なので、マイナス側が一票を買うケースでは、プラス側も買う
    • このことにより全員が合理的に振る舞った場合にはマイナス側が勝つことはなく、それを予見できる十分賢いマイナス側エージェントは無意味な票を買わない
    • プラス側が最小単位の票を買って「最も気持ちの強い人による独裁制」になる

コストの払い方に関して補足

  • コストをどう払うのかは少なくとも2通りのメジャーな実装がある
  • 1: 金で払う
  • 2: 参加者に例えば99票与えて、それを投票する
    • 台湾総統杯ハッカソンなど
    • これは「投票締め切り時刻に消滅する譲渡不能な仮想通貨を定額配布してそれで支払わせる」に相当する
    • 99などの数には本質的な意味はなく、単に大部分の投票者にとって「実数値で投票」は理解しにくいので見た目を変えてあるだけ
    • 通貨が投票にしか使えないことにより、残すインセンティブがないので参加者はみんな与えられた量を使い切り、1と違って全員の消費コストがイコールになる
    • この手法は「票v」ではなく「コストc(v)」を「票」と読んでいるので「平方根を取る」という表現になる
  • 元々この論文は1をイメージしていた
  • 一方で「投票参加者にリアルマネーの支払いをさせる」という特徴によって実社会応用の困難があって、2が生まれた
  • 1にはのちにQuadratic Fundingと呼ばれるようになったので、逆にQuadratic Votingと行った場合に2を指しているケースが増えた

image ver.1

2023-07-13 image

(C)NISHIO Hirokazu / Converted from Markdown (ja)
Source: [GitHub] / [Scrapbox]