中間投票ルール

中央値投票ルールまたは中央値メカニズムは、1 次元の領域に沿ったグループ意思決定のルールです。各人が自分の理想の値を書き留めて投票し、ルールによって (基本メカニズムでは) すべての投票の中央値となる単一の値が選択されます。

グループによる意思決定のシナリオの多くは、1 次元の領域を伴います。いくつかの例を以下に示します。

• 市議会議員は市の年間予算の総額を決定しなければなりません。
• 同じオフィスで働く複数の人が、エアコンの温度を決める必要があります。
• 学童の親は、年間の学校休暇の長さを決めるべきです。
• 住民は、一次元的な道路沿いのどこに施設を設置するかを決定する必要があります。

各メンバーは、自分の「ピーク」と呼ばれる理想的な決定を念頭に置いています。各エージェントは、実際の金額が自分のピークにできるだけ近くなることを望んでいます。

決定する簡単な方法は、平均投票ルールです。各メンバーにピークを尋ね、すべてのピークの平均を取ります。ただし、このルールは簡単に操作できます。たとえば、アリスのピークが 30、ジョージのピークが 40、チャナのピークが 50 であるとします。すべての投票者が実際のピークを報告すると、実際の量は 40 になります。しかし、アリスは操作して、自分のピークは実際には 0 であると言う可能性があります。その場合、平均は 30 になり、これがアリスの実際のピークです。したがって、アリスは操作によって利益を得ています。同様に、ピークが結果と異なるエージェントには、操作して偽のピークを報告するインセンティブがあります。

対照的に、中央値ルールは、実際の予算をすべての投票の中央値で決定します。この単純な変更により、ルールは戦略不可能になります。つまり、投票者が偽のピークを報告しても利益を得ることはできません。上記の例では、中央値は 40 で、アリスが 0 を報告しても 40 のままです。実際、アリスの真のピークは中央値より低いため、アリスによる偽の報告によって中央値が下がる可能性はありません。アリスは中央値を上げることしかできませんが、それによってアリスの立場は悪くなります。

中央値投票ルールは、エージェントが単一のピークを持つ選好を持つあらゆる設定で成立します。これは、ピークp _iを持つ各エージェントiに対して、次のような選択肢の線形順序付けが存在することを意味します。

• p _i > a > bの場合、エージェント i は b よりも a を好みます。
• b > a > p _iの場合、エージェント i は b よりも a を好みます。

このような線形順序が存在すると、この線形順序に沿ってピークを順序付けることで、任意のピーク セットの中央値を計算できます。

単一のピークは、選択肢間の特定の距離の尺度を意味するものではなく、ピークの両側にある選択肢についても何も意味しないことに注意してください。特に、a > p _i > b の場合、エージェントは b よりも a を好むか、a よりも b を好む可能性があります。

1,..., nの 各エージェントiは、 p _iの値を報告するよう求められます。値はp ₁ ≤ ... ≤ p _nの昇順でソートされます。基本的なメカニズムでは、 nが奇数の場合に選択される値はp _(n+1)/2で、これは値の中央値に等しくなります ( nが偶数の場合、選択される値はp _n/2です)。

選択 = 中央値( p ₁、...、p _n )。

中央値ルールが戦略的に不可能であることの証明は次のとおりです。

• まず、ピークが中央値を下回る投票者について考えてみましょう。低いピークを報告しても中央値は変わりません。高いピークを報告すれば、中央値は変わらないか、または中央値が上がります。いずれの場合も、投票者は得をしません。
• 同様に、ピークが中央値を上回る有権者について考えてみましょう。より高いピークを報告しても中央値は変わりません。より低いピークを報告した場合、中央値は変わらないか、中央値は下がります。いずれの場合も、有権者は得をしません。

同様の推論を用いると、中央値ルールはグループ戦略不可能性であることも証明できる。つまり、いかなる連合も、他の連合に損害を与えることなく、一方の連合の効用を向上させるような協調的な操作を行うことはできない。

中央値ルールは、唯一の戦略不可能なルールではありません。市民の投票に依存しない固定投票を追加することで、代替ルールを構築できます。これらの固定投票は「ファントム」と呼ばれます。ファントムのすべてのセットに対して、実際の投票 + ファントムのセットの中央値を選択するルールは、グループ戦略不可能です。

たとえば、投票数が 30、40、50 であるとします。ファントムがない場合、中央値ルールでは 40 を選択します。0 に 2 つのファントムを追加すると、中央値ルールでは 30 を選択します。100 に 2 つのファントムを追加すると、中央値ルールでは 50 を選択します。20 と 35 に中央値を追加すると、中央値ルールでは 35 を選択します。

すべての投票が 0 から 100 の間であると仮定した場合の、ファントム中央値ルールの特殊なケースをいくつか示します。

• 0 にn -1 個のファントムがある場合、中央値ルールはすべての実際の投票の最小値を返します。
• 100 のファントムがn -1 個ある場合、中央値ルールはすべての実際の投票の最大値を返します。
• 50 にn -1 個のファントムがある場合、一部の理想点が 50 を上回り、一部が 50 を下回ると、中央値ルールは 50 を返します。それ以外の場合は、50 に最も近い投票を返します。

ムーラン^[1]は以下の特徴を証明した。

• ルールが、最大でn -1 個のファントムを持つ中央値ルールと同等である場合、そのルールはすべての単一ピークの好みに対して匿名、戦略不可能、パレート効率的です。
• ルールは、最大でn +1 個のファントムを持つ中央値ルールと同等である場合、すべての単一ピークの好みに対して匿名かつ戦略不可能です。
• ルールがすべての単一ピークの選好に対して戦略証明可能であるのは、次の形式のミニマックスルールと同等である場合に限ります。2 ⁿ個のパラメータがあり、投票者の任意のサブセットSに対してb _{S が}あります。ルールは、 S 内のすべてのサブセットSの最大値 ( S内のすべての投票者のピークとb _S ) の最小値を返します。^{[説明が必要]}

ムーランの特徴付けは、「ピークのみ」のルール、つまりn個のピークのみに依存するルールのみを考慮しています。チン^{[2]は、戦略証明}と連続性を持つすべてのルールは、「ピークのみ」でなくても、拡張された中央値ルールであることを証明しました。つまり、 ^2n個のパラメータ を持つ中央値ルールの変形で記述できます。

Moulin の特徴付けでは、ルールがすべての単一ピークの好みを処理する必要があります。他のいくつかの研究では、単一ピークの好みのサブセットのみを処理するルールが許可されています。

• BergaとSerizawa ^{[3] ：第3節}では、ルールが最小限に豊富な選好のみを扱うことを許可しています。彼らは、このより小さな領域でも、戦略的証明ルールはまさに一般化された中央値ルールであることを証明しています。
• MassoとMoreno ^[4]は、対称的な単一ピークの選好のみを扱うルールを許可しています（対称性とは、結果がピークの反対側にある場合でも、ピークから遠い結果はピークに近い結果よりも好まれないことを意味します）。この小さなドメインでの戦略不可能なメカニズムのクラスは、一般化された中央値ルールのクラスよりも厳密に大きいです。特に、ルールは不連続点によって乱される可能性があります。彼らの結果により、実現可能性の制約を扱うルールを設計できます。
• ボーダーとジョーダン^{[5] ：第3節、第4節、第5節}では、 2次の選好のみを扱う規則が許される。1次元の設定では、これは という形式の効用関数と同等である。この領域では、彼らは、全会一致の基準を尊重するあらゆる戦略証明可能な規則は妥協しない、つまり、エージェントのピークが結果の右側にあり、エージェントがピークをさらに右に移動しても結果は変わらない、左の場合も同様であることを証明している。逆に、あらゆる妥協しない規則は戦略証明可能である。彼らは、規則が妥協しないのは、最大で2 ⁿ人のファントム投票者（つまり、どの投票者のピークでなくても選出される可能性のあるポイントが最大で2 ^{n人）を持ち、その}選出対応（各プロファイルを、ピークが選出される実数+ファントム投票者のインデックスの集合にマッピングする）が閉じたグラフ を持つ場合であることを証明している。系として、あらゆる妥協しない規則は連続である。しかし、差別化も可能な妥協のないルールは独裁的でなければなりません。${\displaystyle u_{i}(x)=-|x-p_{i}|}$

BergaとSerizawa ^{[3] ：第4節では}、戦略証明が可能で、かつ彼らが「拒否権なし」と呼ぶ条件を満たすルールを求めている。つまり、いかなる個人も、何らかの選好を表明することで、結果となる選択肢を避けることはできないということである。彼らは、一般化中央値ルールを「最小限に豊富な領域」における唯一の戦略証明ルールであると特徴づけている。彼らは、「拒否権なし」条件を満たす戦略証明ルールの存在を可能にする最小限に豊富な領域を含む唯一の最大領域が、凸選好の領域であることを証明した。

バルベラ、グル、スタッケッティ^[6]も、単峰性の選好と中央値投票ルールの概念を多次元設定に一般化しています。

バルベラとジャクソン^[7]は、最大集合に2つの選択肢が含まれる可能性がある 弱単峰性の選好に対する戦略的証明ルールを特徴付けた。

ムーランは、単一プラトー選好に関する戦略的証明ルールを特徴づけた。これは、各エージェントが理想的な点の区間全体を持つことが許される単一ピークの一般化である。^[8]

ボーダーとジョーダン^{[5] ：第6節、第7節では、}単峰性の選好と中央値投票ルールの概念を多次元の設定（星型の選好を参照）に一般化している。彼らは3つの選好のクラスを検討している。

• 分離可能（、各v _i,jは単峰性の効用関数）${\displaystyle u_{i}(x)=\sum _{j=1}^{m}u_{i,j}(x_{j})}$
• 二次方程式（ここでAは対称正定値行列）${\displaystyle u_{i}(x)=-(xp)^{T}A(xp)}$
• それらの交差は分離可能な二次関数（、ここでa _i,jは正の定数）です。${\displaystyle u_{i}(x)=-\sum _{j=1}^{m}a_{i,j}\cdot (x_{j}-p_{j})^{2}}$

二次の非分離領域では、戦略証明可能なメカニズムは独裁的なものだけです。しかし、分離可能な領域では、各座標に 1 つずつ、1 次元の戦略証明可能なメカニズムから構成される多次元の戦略証明可能なメカニズムが存在します。

1954年、イラン石油コンソーシアムはイランの年間総石油生産量を決定するために中央値のようなルールを採用しました。毎年、各メンバー企業の役割は、総生産量に対する固定シェアによって重み付けされました。選択された生産量xは、xのレベルに投票したメンバーのシェアの合計が少なくとも70％になる最高レベルでした。^{[9] ：103-108}

中間投票者定理は、各エージェントが選択肢に対する自分の完全な順位を報告する順位付け投票メカニズムに関連しています。この定理によれば、エージェントの好みが単一のピークを持つ場合、すべてのコンドルセ法で、中間投票者（ピークがすべてのピークの中間である投票者に最も近い候補者）が好む候補者が常に選択されます。

最高中央値投票ルールは、各候補者に対する判断 (スコア) を投票者に求めることで、同じ投票ルールを選挙に適用する試みです。ただし、中央値投票ルールの戦略不可能な性質は、各候補者の最終スコアに対して投票者が単一のピークを持つ好みを持っていない限り、候補者の選択には適用されません。これは表現投票の合理的なモデルかもしれませんが、投票者が選挙の 結果(勝者)に対して単一のピークを持つ好みを持っている状況では、ルールは戦略不可能ではありません。

ギバード・サッタースウェイト定理によれば、3 つ以上の選択肢に対する戦略不可能なルールはすべて独裁制でなければならない。中央値ルールは、戦略不可能であり独裁制ではないため、この定理と明らかに矛盾している。実際、矛盾はない。ギバード・サッタースウェイト定理は、選好ドメイン全体に作用するルール (つまり、任意の選好ランキング セットを処理できる投票ルール) にのみ適用される。対照的に、中央値ルールは、制限された選好ドメイン、つまり単一ピークの選好のドメインにのみ適用される。

ダメットとファークハーソンは投票ゲームにおける安定性の十分条件を提示している。^{[10] [さらなる説明が必要]}