最大宝くじ

最大抽選とは確率的投票ルールを指します。この方法では優先投票を使用し、大多数の有権者が他の候補者よりも弱く好む候補者の確率分布（または線形結合）を返します。 ^[1]

最大くじは、望ましい特性を幅広く満たしている。コンドルセの勝者が存在する場合は確率 1 で選出し^[1]、スミス集合外の候補者を選出することはない^[1]。さらに、強化^[2] 、参加^[3]、クローンの独立性^[2]も満たしている。すべての最大くじを返す確率投票ルールは、強化、コンドルセ一貫性、クローンの独立性 [2] を満たす唯一のルールである。最大^{くじをトップランクにする}社会福祉関数は、アローの無関係な選択肢の独立性とパレート効率性^[4]を使用して独自に特徴付けられている。

最大くじは標準的な戦略不可能性の概念を満たしていません。アラン・ギバードは、ランダム独裁だけが戦略不可能性および事後効率性を満たすことができることを示したからです。 ^[5]また、最大くじは確率において非単調です。つまり、投票者がこの選択肢をランク付けすると、選択肢の確率が下がる可能性があります。^[1]しかし、それらは相対的単調性を満たしています。つまり、が に対して改善されても、の確率に対するの確率は下がりません。^[6]${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

最大宝くじのサポートは、必須セットまたは超党派の集団は、詳細に研究されてきた。^{[7][8][9][10]}

最大くじは、1965年にフランスの数学者で社会科学者のジェルマン・クレヴェラスによって初めて提案され^[11]、ピーター・フィッシュバーンによって普及しました。^{[1]それ以来、経済学者、 [8]}数学者、^{[1] [12]}政治学者、哲学者、^[13]コンピューター科学者によって何度も再発見されてきました。^[14]

最大の宝くじに収束するいくつかの自然なダイナミクスは、生物学、物理学、化学、機械学習の分野で観察されています。^{[15] [16] [17]}

この投票システムへの入力は、エージェントの結果に対する順序的な選好（選択肢に対するくじではない）で構成されるが、くじの集合に関する関係は次のように構築できる。 およびが選択肢に対するくじである場合、分布で選択された結果と分布で選択された結果との直接投票における勝利マージンの期待値が正である場合。言い換えれば、無作為に選択された投票者が、 からサンプリングされた選択肢をからサンプリングされた選択肢よりも好む可能性の方が、その逆の場合よりも高い場合である。^[4]この関係は必ずしも推移的ではないが、常に少なくとも 1 つの最大要素を許容する。 ${\displaystyle p}$${\displaystyle q}$${\displaystyle p\succ q}$${\displaystyle p}$${\displaystyle q}$${\displaystyle p\succ q}$${\displaystyle p}$${\displaystyle q}$

同点の結果、このような最大くじが複数存在する可能性もある。しかし、投票者の数が奇数の場合、最大くじは一意である。^[18]同じ議論により、トーナメントゲームを解く唯一の最大くじのサポートを取ることで、超党派集合は一意に定義される。^[8]

最大宝くじは、ペアワイズ多数決マージンによって与えられる対称ゼロ和ゲームの混合最大戦略（またはナッシュ均衡）と同等である。そのため、2つの政党間の選挙競争の観点から自然な解釈が可能であり^[19]、線形計画法によって多項式時間で計算することができる。

3 つの選択肢に対して次の好みを持つ 5 人の有権者がいるとします。

• 投票者 2 人:${\displaystyle a\succ b\succ c}$
• 投票者 2 人:${\displaystyle b\succ c\succ a}$
• 投票者 1 人:${\displaystyle c\succ a\succ b}$

有権者のペアワイズ選好は、次の歪対称行列で表すことができます。ここで、行と列のエントリは、を好む有権者の数からを好む有権者の数を引いたものを表します。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle y}$${\displaystyle x}$

${\displaystyle {\begin{matrix}{\begin{matrix}&&a\quad &b\quad &c\quad \\\end{matrix}}\\{\begin{matrix}a\\b\\c\\\end{matrix}}{\begin{pmatrix}0&1&-1\\-1&0&3\\1&-3&0\\\end{pmatrix}}\end{matrix}}}$

この行列はゼロサムゲームとして解釈でき、、、のときに一意のナッシュ均衡（またはミニマックス戦略）が成立します。定義により、これは上記の選好プロファイルの一意の最大抽選でもあります。この例は、コンドルセ勝者が存在しないように慎重に選択されています。多くの選好プロファイルではコンドルセ勝者が存在します。その場合、一意の最大抽選によりコンドルセ勝者に確率 1 が割り当てられます。上記の例の最後の投票者が選択肢を交換し、彼の選好関係で がコンドルセ勝者となり、確率 1 で選択されます。 ${\displaystyle p}$${\displaystyle p(a)=3/5}$${\displaystyle p(b)=1/5}$${\displaystyle p(c)=1/5}$${\displaystyle a}$${\displaystyle c}$${\displaystyle a}$

• vote.ml (最大抽選を計算するウェブサイト)