Избирательные системы и их свойства Избирательные системы и их свойства А. Бочкарёв . Постановка задачи (стр. 5 )

1	2	3	…
1				…
2				…
…	…	…	…	…	…
				…
				…
…	…	…	…	…	…
				…

Заметим, что, поскольку избирательная система анонимна, эти профили голосования тождественны. Также заметим, что исходя из свойства единогласия данной избирательной системы, победителями в этих профилях могут быть только кандидаты .

Однако второй профиль голосования получается из первого перестановкой , где . Т. е. если при первом профиле победил кандидат ( из свойства единогласия избирательной системы) и только он, то во втором случае должен победить кандидат (или , если ) и только он. Но ведь два этих профиля тождественны исходя из анонимности избирательной системы, следовательно мы получили противоречие, и доказали, что анонимное нейтральное правило, удовлетворяющее свойству единогласия и дающее единственного победителя, существует только тогда, когда у числа избирателей нет простых делителей, не превосходящих числа кандидатов .

II. Докажем, что анонимное нейтральное правило, удовлетворяющее свойству единогласия и дающее единственного победителя, существует тогда, когда у числа избирателей нет простых делителей, не превосходящих числа кандидатов (достаточность условия).

Рассмотрим произвольный профиль голосования для произвольной избирательной системы, удовлетворяющей этому условию. Пусть избирателей поставили на первое место кандидата , – и т. д., –  .

Т. к. , где , то такие, что . Следовательно, можно выделить кандидатов, за которых было отдано наибольшее количество голосов. Остальных кандидатов просто вычеркнем из профиля голосования и повторим операцию. Таким образом, на каждом шаге мы будем избавляться от положительного количества кандидатов, следовательно, через конечное количество операций мы получим единственного победителя, что и требовалось доказать.

Теорема о единственном победителе №2. Анонимное нейтральное правило, дающее единственного победителя, существует тогда и только тогда, когда число кандидатов не может быть записано в виде суммы нескольких делителей числа избирателей , отличных от 1.

Доказательство.

I. Докажем, что анонимное нейтральное правило, дающее единственного победителя, существует только тогда, когда число кандидатов не может быть записано в виде суммы нескольких делителей числа избирателей , отличных от 1 (необходимость условия). Предположим, что это не так и что существует анонимная нейтральная избирательная система, дающая единственного победителя, для которой верно , где . Разделим кандидатов на разных по размеру групп, где i-тая группа будет состоять из кандидатов. Рассмотрим для такой i-той группы следующие 2 подпрофиля голосования (избирателей разделим на групп, по избирателей в каждой группе):

1	2	3	…
1				…
2				…
…	…	…	…	…	…
				…

Заметим, что, поскольку избирательная система анонимна, эти подпрофили голосования тождественны.

Однако второй подпрофиль голосования получается из первого перестановкой , где . Теперь рассмотрим 2 профиля голосования со всеми кандидатами, составленные один – из подпрофилей первого типа, а второй – второго. Очевидно, что если при первом профиле победил кандидат и только он, то во втором случае должен победить кандидат (или , если ) и только он. Но ведь два этих профиля тождественны исходя из анонимности избирательной системы, следовательно мы получили противоречие, и доказали, что анонимное нейтральное правило, дающее единственного победителя, существует только тогда, когда число кандидатов не может быть записано в виде суммы нескольких делителей числа избирателей , отличных от 1.

II. Докажем, что анонимное нейтральное правило, дающее единственного победителя, существует тогда, когда у числа избирателей нет простых делителей, не превосходящих числа кандидатов (достаточность условия).

Рассмотрим произвольный профиль голосования для произвольной избирательной системы, удовлетворяющей этому условию. Разделим кандидатов на групп по человек каждая, остаток из кандидатов отделим в последнюю группу. Т. к. не может быть записано в виде суммы нескольких делителей числа избирателей , отличных от 1, не делится на . В группе из выберем единственного победителя по схеме, использовавшейся в теореме 1(пункт II).