Veto voting

In social choice theory, veto voting is a method of voting by which individual voters, or coalitions of voters, can veto a certain number of outcomes that they dislike. The veto power of a coalition is the number of candidates it can veto. The veto core is the set of outcomes that are not vetoed. The idea was introduced by Dennis C. Mueller in 1978,^[1] and refined by Herve Moulin^[2][3] and several later authors.^{[4][5][6][7][8]}

Suppose a group of voters has to choose one out of several possible outcomes (also called: candidates). Each voter has a total order over the candidates. Two considerations in selecting the winning outcome is respecting the will of the majority, and protecting the minorities. These considerations might be contradictory.

For example,^[9] suppose 100 voters have to choose one out of three outcomes. 60 voters prefere A to B to C; 40 voters prefer B to C to A. The majority principle would select A, who is supported by a strict majority of voters (this outcome is also the Condorcet winner). But the minority principle says that A should not be elected, as he is opposed by 40% of the voters, whereas B is a reasonable compromise for all voters. The minority principle makes sense in settings such as selecting a time for a meeting: it is better to select a time that is reasonable (if not perfect) for all voters, than to select a time that is optimal for 60% and impossible for 40%.

Veto voting is a voting method that implements the minority principle by letting individuals and groups of voters a predefined amount of veto power, by which they can eliminate outcomes that they strongly oppose.

Mueller^[1] introduced the first veto voting method, in the context of deciding how many public goods to produce. His method consists of two steps. In step 1, each voter makes a proposal. Together with the status quo, the number of possible outcomes is n+1. In step 2, the voters are ordered randomly, and each voter in turn eliminates one outccome. Finally, a single outcome remains, and this outcome is implemented. Mueller shows that, given the voters' incentives, the winning proposal tends to contain an equal sharing of the potential gains.

Mueller's method cannot be used in general voting settings, as usually the number of candidates is not exactly n+1. Another disadvantage of it is that the outcome might depend on the ordering of voters, that is, it is not an anonymous procedure.

Moulin^[2] extended the idea of veto voting by giving veto powers to coalitions, rather than just individuals. Formally, a veto function is a function that assigns, to each subset of voters, a number in {0,1,...,m-1} (where m is the number of candidates), called its veto power, which represents the number of candidates this coalition is allowed to veto. An anonymous veto function is a veto function that satisfies Anonymity, that is, does not distinguish apriori between voters. Thus, the veto power of a coalition depends only on the coalition size. An anonymous veto function is required to be a superadditive set function.

Given a veto function v, an outcome x is blocked by a coalition T of voters if there exists a subset B of outcomes such that (i) all members of T prefer every outcome in B to x; (ii) the veto power v(T) is at least m-|B|, that is, the coalition T can force an outcome of B by vetoing all other outcomes. An outcome x is called stable if it is not blocked by any coalition. The veto core of v is the set of stable outcomes.

The special case of one outcome per voter corresponds to giving every coalition a veto power equal to its size, v(T) = |T|.

Consider the following veto function (defined for odd n, for convenience):

• Each coalition of size more than n/2 has the maximum voting power: v(T)=m-1;
• Each coalition of size less than n/2 has no voting power: v(T)=0.

بناءً على هذه الدالة، يُعتبر الخيار x غير مُتاح إذا وفقط إذا كانت هناك أغلبية مطلقة من الناخبين تُفضّل خيارًا آخر عليه . بعبارة أخرى، يكون الخيار مستقرًا إذا وفقط إذا كان خيارًا فائزًا وفقًا لمعيار كوندورسيه . قد يكون جوهر هذه الدالة فارغًا، حيث لا تحتوي بعض الخيارات على خيار فائز وفقًا لمعيار كوندورسيه - وهذا ما يُعرف بمفارقة كوندورسيه .

اقترح ناكامورا ^{[ 10 ]} صيغةً معدلةً لمبدأ الأغلبية، حيث يمتلك الائتلاف حق النقض الكامل ( m -1) إذا كان يضم أكثر من نسبة معينة f من الناخبين، حيث يمكن أن تختلف f عن 1/2. وقد أثبت أنه إذا وفقط إذا كانت f > 1-1/ m ، حيث m هو عدد المرشحين، فسيكون هناك دائمًا نتيجة مستقرة واحدة على الأقل. تكمن المشكلة في أنه عادةً ما يكون هناك العديد من النتائج المستقرة. على سبيل المثال، إذا كان هناك m = 10 نتائج، فلن يتمكن من نقض مرشح إلا ائتلاف يضم أكثر من 90% من الناخبين، وهو أمر نادر الحدوث. غالبًا ما يضم جوهر حق النقض جميع المرشحين m .

اقترح مولان ^{[ 2 ]} مبدأ حق النقض النسبي كبديل لكلا شكلي مبدأ الأغلبية. يمنح هذا المبدأ كل ائتلاف حق نقض يتناسب مع حجمه. وبشكل أدق، يمتلك الائتلاف T الذي يضم t ناخبًا حق نقض.${\displaystyle \left\lceil {\frac {mt}{n}}\right\rceil -1}$، والتي تكون دائمًا بين m * t / n -1 و m*t / n ، حيث m هو عدد المرشحين و n هو عدد الناخبين.

يمكن التعبير عن دالة النقض هذه بمعاملات بيزو . ليكن r و c عددين صحيحين بحيث: r * n = c * m - gcd ( m , n ). عندئذٍ تكون دالة النقض المذكورة أعلاه مساوية لـ${\displaystyle \left\lfloor {\frac {r\cdot t}{c}}\right\rfloor }$.

جوهر حق النقض النسبي هو جوهر حق النقض لدالة حق النقض النسبي. ويكون جوهر حق النقض النسبي دائمًا غير فارغ. البرهان بنائي ويستخدم إجراء نقض متسلسل، موضح أدناه .

علاوة على ذلك، تمنح دالة الفيتو النسبي أكبر قوة فيتو ممكنة لضمان نتيجة مستقرة؛ فكل دالة فيتو أخرى تضمن نتيجة مستقرة، يجب أن تمنح على الأكثر نفس قوة التصويت لجميع التحالفات، وقوة تصويت أقل لبعض التحالفات، مما يعني أن نواة الفيتو قد تكون أكبر. وبالتالي، تحقق دالة الفيتو النسبي أصغر نواة فيتو غير فارغة من بين جميع دوال الفيتو المجهولة. ^{[ 2 ] : النظرية 1.} نوضح البرهان للحالة الخاصة التي يكون فيها m = n . في هذه الحالة، تكون دالة قوة الفيتو ببساطة v( t ) = t - 1. لنفترض أننا نمنح تحالفًا واحدًا قوة فيتو أكبر، على سبيل المثال، يحصل تحالف بحجم k على قوة فيتو k. نُنشئ ملفًا شخصيًا بتفضيلات "دائرية": يُفضّل العميل 1 المرشحين 1>2>...>m، ويُفضّل العميل 2 المرشحين 2>3>...>m>1، وهكذا. ولإثبات أن النواة غير فارغة، نُبيّن أن كل نتيجة يُمكن رفضها من قِبل تحالف ما. هنا، جميع النتائج متناظرة، لذا يكفي إثبات ذلك للنتيجة m. في الواقع، يمتلك التحالف المُكوّن من العملاء 1،...،k حق النقض k، ويُفضّلون جميعًا المرشحين k،...،m-1 على m، لذا يُمكنهم رفض المرشحين k، m،1،...،k-1.

بدلاً من تحديد دالة حق النقض مسبقاً ثم تصميم قاعدة لتطبيقها، يمكن اتباع نهج معاكس: بمعرفة قاعدة تصويت موجودة، يتم حساب حق النقض لكل ائتلاف. بصورة رسمية، ^{[ 3 ]} بمعرفة قاعدة اختيار اجتماعي R، فإن حق النقض لائتلاف T هو أكبر عدد صحيح k بحيث، لكل مجموعة جزئية B تحتوي على k نتيجة على الأكثر ، يمكن لأعضاء T التصويت بطريقة لا يتم فيها انتخاب أي عضو من B.

قام هالبرن وبروكاسيا وسوكسومبونغ ^{[ 11 ]} بتوسيع مفهوم حق النقض النسبي من الاقتراع الترتيبي إلى اقتراع الموافقةالفكرة هي منح المزيد من السلطة للناخبين الأكثر "مرونة"، أي الذين يوافقون على نسبة أكبر من الناخبين.

بصورة رسمية، لأي قيمة s في الفترة (0,1)، يُعتبر الناخب المرن s ناخبًا يوافق على s * m مرشحًا على الأقل. أما التحالف المرن ( r , s) فهو تحالف يضم r * m ناخبًا على الأقل، كل منهم مرن s .

بالنسبة لقاعدة التصويت ذات الفائز الواحد، فإن ضمان ( r , s ) هو ضمانٌ بأن أي ائتلاف T مرن ( r , s ) سيوافق على الفائز. بالنسبة للقاعدة R، فإن FVR( R , s ) هو أصغر قيمة لـ r التي تضمن القاعدة عندها ضمان ( r , s ). وقد تم إثبات الضمانات التالية لقواعد الفائز الواحد : ^{[ 11} ] ^{: القسم 2}

• بالنسبة لقاعدة التصويت بالموافقة (النفعية) ، فإن FVR(R,s) = 1/(1+ s ) لجميع قيم s.
• بالنسبة لقاعدة التصويت بالموافقة المرجحة بالقوة ، حيث يكون وزن كل ناخب يتمتع بمرونة f هو f ^p لبعض القوة p > 0، فإن FVR(R,s) =${\displaystyle {\frac {1}{1+{\frac {(s(1+p))^{1+p}}{p^{p}}}}}}$.
• For threshold approval voting rule, which counts only the votes of s₀-flexible voters for some fixed threshold s₀, FVR(R,s₀) = 1-s₀, but the guarantees to other values of s might be much worse.
• The harmonic-weighted approval voting rule, where the weight of each voter with flexibility f is 1/(1-f), FVR(R,s) = 1-s for every s, and this is the best possible guarantee for every s. Hence, the harmonic-weighted approval voting rule is optimal with respect to the FVR guarantee. The rule guarantees to each group of (1-s)*n voters who are all s-flexible, that at least one voter of the group approves the winner.

For a multi-winner voting rule, an (r,s,t)-guarantee is a guarantee that, in any (r,s)-flexible coalition, at least one member approves at least t winners. The following are proved for multi-winner rules:^[11]:Sec.3

• There is a lower bound for FVR(r,s,t,m), but it is much more complex than the lower bound of 1-s for single-winner voting.
• For any fixed k and t, there exists a rule that yields the optimal guarantee simultaneously for all s and m. Similarly to the single-winner case, the rule works by assigning a weight to each voter, and selecting a candidate with the highest total weight. But here the weight changes dynamically as more candidates are selected.
• On the other hand, if k, m and s are fixed, no rule is simultaneously optimal for all t.
• The FVR guarantee is not compatible with justified representation guarantees: for every k>1, there exists some s such that no rule for selecting a committee of size k is both FVR-optimal for (s,1) and satisfies JR.

• Sequential elimination method