Sequential proportional approval voting (Sequential PAV)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/09/04 15:31 UTC 版)
「approval voting」の記事における「Sequential proportional approval voting (Sequential PAV)」の解説
トルバルド・ティエレが20世紀初頭に発明し、スウェーデンで1909年以降の短期間だけ使用された。投票者の「満足度」の総和を最も増加させる候補者を1人ずつ当選させていく方法である。 具体的な当選者決定の手続きは次のようになる。PAVと同様に「満足度」を表す数列 s 0 , s 1 , s 2 , … {\displaystyle s_{0},s_{1},s_{2},\dots } を1つ決め、候補者全員の集合を C {\displaystyle C} 、投票者 i {\displaystyle i} が是認した候補者の集合を A i {\displaystyle A_{i}} 、当選が確定した候補者の集合を W {\displaystyle W} と表す。また、 | X | {\displaystyle |X|} は集合 X {\displaystyle X} の要素数、 1 c ∈ X {\displaystyle 1_{c\in X}} は c ∈ X {\displaystyle c\in X} のとき 1 {\displaystyle 1} 、そうでないとき 0 {\displaystyle 0} となる関数を表すとする。 はじめは誰の当選も確定していないので W = ∅ {\displaystyle W=\varnothing } (空集合) とする W {\displaystyle W} にまだ入っていない各候補者 c {\displaystyle c} を新たに当選としたときの「満足度」の増加 ∑ i ( s | A i ∩ W | + 1 − s | A i ∩ W | ) ⋅ 1 c ∈ A i {\displaystyle \sum _{i}(s_{|A_{i}\cap W|+1}-s_{|A_{i}\cap W|})\cdot 1_{c\in A_{i}}} を計算する 上で計算した「満足度」の増加が最大となる候補者 c ∗ {\displaystyle c^{*}} を W {\displaystyle W} に追加する W {\displaystyle W} に入っている候補者が規定の当選者数に達していたら終了する。そうでなければ2つ上に戻って繰り返す この手続きは前項のPAVにおける「満足度」の総和を最大化する問題の近似アルゴリズムになっていて、近似比は 1 − 1 e {\displaystyle 1-{\frac {1}{e}}} である。 Sequential PAVの例を次に示す。候補者はA,B,C,Dの4人でこのうち2人が当選するとする。満足度は s n = 1 + 1 2 + ⋯ + 1 n {\displaystyle s_{n}=1+{\frac {1}{2}}+\dots +{\frac {1}{n}}} によって定義されるとし、投票は次のようであったとする。 是認する候補の集合ABACBCD投票数10 8 7 6 4 1人目としてA, B, C, Dそれぞれを当選としたときに増加する「満足度」はそれぞれ A 10+8=18 B 10+7=17 C 8+6=14 D 4 であるから、最初に当選するのはAである。2人目としてB, C, Dそれぞれを当選としたときに増加する「満足度」はそれぞれ B 10/2+7=12 C 8/2+6=10 D 4 であるから、2人目の当選はBである。よってAとBが当選となる。
※この「Sequential proportional approval voting (Sequential PAV)」の解説は、「approval voting」の解説の一部です。
「Sequential proportional approval voting (Sequential PAV)」を含む「approval voting」の記事については、「approval voting」の概要を参照ください。
Sequential proportional approval voting (Sequential PAV)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/25 04:22 UTC 版)
「認定投票」の記事における「Sequential proportional approval voting (Sequential PAV)」の解説
トルバルド・ティエレが20世紀初頭に発明し、スウェーデンで1909年以降の短期間だけ使用されていた選挙制度である。 この方式だと票の重さは当選を出す度に w n = 1 + 1 2 + ⋯ + 1 n {\displaystyle w_{n}=1+{\frac {1}{2}}+\dots +{\frac {1}{n}}} で逓減されいくと定義される。 Sequential PAVの例を次に示す。候補者はA,B,C,Dの4人でこのうち2人が当選するとし、投票は次のようであったとする。 是認する候補の集合ABACBCD投票数10 8 7 6 4 1人目の当選を決めるスコアはA, B, C, Dそれぞれ A 10+8=18 B 10+7=17 C 8+6=14 D 4 であるから、最初に当選するのはAである。2人目の当選を決めるスコアはB, C, Dそれぞれ B 10/2+7=12 C 8/2+6=10 D 4 であるから、2人目の当選はBである。よってAとBが当選となる。 またこの手続きはOWAを用いた分析によると、前項のPAVにおける「満足度」の総和を最大化する問題の近似アルゴリズムになっていて、近似比は 1 − 1 e {\displaystyle 1-{\frac {1}{e}}} であるとする見解もある。
※この「Sequential proportional approval voting (Sequential PAV)」の解説は、「認定投票」の解説の一部です。
「Sequential proportional approval voting (Sequential PAV)」を含む「認定投票」の記事については、「認定投票」の概要を参照ください。
- Sequential proportional approval votingのページへのリンク
