# 論文読み会　2020/05/08

背景：

候補者の数に対してそこから何人かを選ぶ有権者の数があまり多くないと言う現実がある．真のランキングを推定する時に各有権者から最も効率的に情報を引き出す投票メカニズムを使用することが不可欠である．
この研究では，各有権者ごとのランキング順位 を集計するポジションスコアリングルールを分析する．
第3章ではモデルを形式化する．
第4章では特定のスコアリングルールが最終的な結果の学習率にどのような影響をもたらすかを示す.
学習率を用いることで,どちらのスコアリングルールが優れているかを決定できる.
すべての候補者のランキングとその選挙で選ばれる候補者を特定することの両方を目標とする.
第5章一節では,学習率を用いてモデルを拡張子スコアリングルール館のランダム化が学習を向上させることができるか検討した. Ne-yo ノイズモデルを用いた時にはスコアリングルールが並んだのかが学習を早めるということはないことは分かった.
ノイズモデルを用いた時にはスコアリングルールが並んだのかが学習を早めるということはないことが分かった
5章第2節ではマローズモデルでパラメータを変えて検討している.
最終的に一人の当選者を特定することが目的であっても, 有権者に対しては候補者から一人を選ぶのではなく,候補者の好きな半分を特定するように求めるべきであることを発見した.

第6章では米国のいくつかの都市における実際の参加型予算編成選挙で実践的に提案アプローチを試した.
例えばある設定では有権者等に好きな候補者を一人選ぶように依頼した場合400人の有権者が投票した後では80%の確率で最良の候補者が特定される.
一方で有権者に好きなふたりの候補者を特定するように頼んだ場合, 400人の有権者が投票した後では99.9%の確率で最良の候補者が特定される.
このように理論的洞察を拡張してみると歴史的に見て選挙においては兄が効果的な学習には低すぎる値に設定されていることが分かった.

本研究は投票ルールの新井理論的分析と実務家が答えを求めているきめ細やかな設計上の疑問とのギャップを埋めるものである.

## 関連研究とのつながり

本研究は人々の好みを引き出すメカニズムに関するいくつかの研究の一部である.

### 投票ルールの学習特性に関して

マロウズモデルの下では、任意の固定KでのK-Approvalは指数関数的に多くの有権者を必要
(Caragiannis and Micha, 2017)

これらの研究は、候補者の数で漸近的な学習率の次数推定を提供しているが、与えられた選挙のための異なるルールやK-Approvalメカニズムの間の詳細な微分は不可能である。
本研究では後者を提供し、それが重要であることを示す。

### メカニズムを比較するための他のアプローチ

多くの研究では、漸近的に多くの票が与えられても異なる結果をもたらす可能性のあるメカニズムを比較するという公理的・計算的なアプローチがある．
本研究では、有権者がすべての候補者を見て部分的な順位付けを行い、異なるデザイン（例えば、3-Approvalと4-Approval）で有権者が提供できる順位付けの種類を制約する．

## モデル

- $M$ 個の候補 $C = \{1, \cdots , M\}$
- 通常は $i, j \in C$ で索引付けされる．
- $N$ 人の有権者 $V = \{1, \cdots, N\}$
- 各有権者は，確率質量関数 $F(\sigma)$ から候補の順位づけ $\sigma_{v}$ を行なう
- 引数とってそれに順位を与える関数 $F$
- $i \succ_{\sigma}j$ は，順位付け $\sigma$ 中で，$j$ よりも $i$ が優先されることを示す．
- $\sigma(i) = k$ は，$i$ が $k$ 番目の候補であることを示す
- 「真の」社会的選好 $\sigma ^{\ast}$ が存在し，各有権者の持つ順位付け $\sigma_{v}$ はノイズが乗ったサンプルである
- これを「 Mallow's Model 」と呼ぶ
- $F_{Mallows} (\sigma) \propto \phi^{d(\sigma, \sigma^{\ast})}$
- $d(\sigma, \sigma^{\ast})$ は順位間のケンダルの $\tau$ 距離
- $\sigma, \sigma^{\ast}$ と $\phi \in [ 0, 1 ]$ はノイズパラメータ
- $\phi$ が小さいほど、$\sigma^{\ast}$ 付近に $F$ が集中している
- 目標 $G$ は、候補者を $T$ 個の不連続な順序付き階層クラスの集合 $G = \{C_1, ... , C_T \}$ , $C = \bigcup^{T}_{t=1} C_t$ とする
- $t$ が小さいほど「社会的に好ましいと判断される」階層であると仮定
- 「よい候補者のグループ」「悪い候補者のグループ」「どうでもいい候補者のグループ」というように，集団ごとに順位を与える．

### Elicitation and Aggregation.

有権者は，誘導メカニズム $\beta$ を用いて投票を行う

- K-Ranking
- $M$ 人の候補者から $K$ 人選んで順位をつける
- すなわち $\{ (i, \sigma_{v} (i)) \colon \sigma_{v} (i) \leq K \}$ を明らかにする
- 候補者 $i$ は，ランク付けされていればスコア $s_{iv} = \beta \left( \sigma_{v}(i) \right)$ を受け取り，そうでなければ $s_{iv} = 0$ を受け取る

- K-Approval
- $M$ 人の候補者から $K$ 人選ぶだけ
- すなわち $\{ i \colon \sigma_{v} (i) \leq K \}$ を明らかにする
- 候補者 $i$ は，選ばれた場合にはスコア $s_{iv} = 1$ ，選ばれなかった場合にはスコア $s_{iv} = 0$ を受け取る

つまり，**有権者 $v$ さんが候補者 $i$ さんに順位 $\sigma_{v}(i)$ をつけるとき，誘導メカニズム $\beta$ はそれを引数としてスコア $s_{iv}$ を算出する．**

最終的に出力される結果 $Outcome$ は，以下のようになる．

- $N$ 人の有権者が投票したあと，候補者 $i$ の累積スコアは $s_{i}^{N} = \frac{1}{N} \sum_{v=1}^{N} s_v$ となる
- 候補者はスコアの降順で並べられ，順位 $\sigma ^N$ をとる
- 目標 $G$ に対応する $N$ 人の有権者の後の結果を $O^N(M, F, \beta, G)$ とする
- 候補者の人数 $M$
- 各有権者に固有の順位決定関数 $F$
- 候補者に得点 $s_{iv}$ を与えるスコアリングルール $\beta$
- 候補者の属する階層を理想的に定める $T$ 個の不連続な順序付き階層クラスの集合 $G$
- 候補者が $N$ 人の有権者から受け取るスコア $s^{N}_{i} \rightarrow \mathbb{E}_F \left[ s_{iv} \right] \triangleq s_i$
- このスコアは有権者数 $N \rightarrow \infty$ につれて，大数の法則で求められる

###

選挙の漸近的結果 $O^{\ast}$ は，採点ルール $\beta$ によって変化することがある．
例えば、有権者に好きな候補者を2人に絞るのと、好きな候補者を1人に絞るのとでは、勝者が異なる場合がある。