Парадоксы демократического голосования

Тема навеяна веткой В Кремле читают Мисту? (Путин поставит веб-камеры на выборах)
Заранее извиняюсь, статья в вордовском файле, а тут индексы не делаются. Если за латинской буквой стоит цифра - это индекс. Если цифра перед латинской буквой - это обычное число.

1. Введение
Демократия - это проблема выбора, т.е. голосования: выбирается 1 кандидат из множества альтернатив, поэтому имеет место поговорка: «Демократия - искусство политического маневрирования».
Но вот выборы прошли, а число недовольныхмного, вполне сравнимо с числом довольных.
Выбор - всегда несправедливый именно с т.з. демократии. Это главный парадокс.
2. Правила голосования.
Пусть имеется N избирателей и mкандидатов для выбора.
m = {a, b, c, …}
N = {1, 2, 3, …,N}
Предпочтение - ‘один кандидат лучше второго’ всегда индивидуально, знак “≻”.
Например, избиратель предпочитает: a≻b≻c N>>m.
Профиль голосования - свод систем индивидуальных предпочтений.
N = 17 (×10^6, например)
m = {a, b, c, d}, m = 4. N>>m.
5: a≻d≻c≻b;
3: a ≻ d ≻ b ≻ c;
5: b ≻ c ≻ d ≻ a;
4: c≻d≻b≻a.
Профиль А:
Количество голосов = количество избирателей
Кандидаты (предпочтения)
5 3 5 4
-------------------------
a a b c
d d c d
c b d b
b c a a

Правила голосования (демократического)
П1. Правило относительного большинства.
Каждый избиратель отдает ровно 1 голос за своего кандидата. Побеждает тот, кто получает наибольшее количество голосов.
Для Профиля А:
na = 8; nb = 5; nc = 4.Побеждает ‘a’!!!
П2. Правило абсолютного большинства.
Каждый избиратель отдает 1 голос за одного кандидата. Побеждает кандидат набравший более 50% голосов. Если при голосовании никто не набирает абсолютного большинства голосов, то проводится второй тур, в который выходят два кандидата, набравшие большинство голосов. Во втором туре побеждает тот, кто набирает большинство голосов.
Для Профиля А:
Iтур: na = 8; nb = 5; nc = 4
17/2 = 8,5. Т.е. нужен II тур.
Число избирателей
Кандидаты
5 3 5 4
-------------------------
a a b b
b b a a

na = 8, nb = 9. Побеждает ‘b’!!!
П3. Правило Борда.
Жан-Поль Борда (1733 - 1799 гг.) - французский революционер, физик, геодезист, академик. Систему голосования предложил при Революции. Сейчас она используется в спортивных соревнованиях.
Каждый избиратель дает 0 очков кандидату, находящемуся на последнем месте, 1 очко - кандидату, находящемуся на предпоследнем месте, 2 очка - третьему с конца и т.д. Побеждает кандидат с максимальной суммой очков.
Замечание: в спорте наоборот, очки - “штрафные” и побеждает тот, у кого минимальное количество очков.

Для Профиля А:
Число избирателей
Очки за места
5 3 5 4
-------------------------
3 a a b c
2 d d c d
1 c b d b
0 b c a a

Число очков:
na = 5×3 + 3×3 + 5×0 + 4×0 = 24
nb = 5×0 + 3×1 + 5×3 + 4×1 = 22
nc = 5×1 + 3×0 + 5×2 + 4×3 = 27
nd = 5×2 + 3×2 + 5×1 + 4×2 = 29Побеждает ‘d’!!!
П4. Правило Кондорсе.
Жан Антуан Никола маркиз де Кондорсе (1746 - 1794 гг.) - друг д’Аламбера, Дидро, Вольтера. Энциклопедист, социолог. Математик, политик. 1776 - член Санкт-Петербургской Академии наук, исключен в 1792 г. Екатериной II (политические взгляды). Погиб в лесу (волки), спасаясь от гильотины. Был жирондистом.
Правило Кондорсе: победителем является тот кандидат, который выигрывает в парных сражениях у других кандидатов.
Для Профиля А:
c≻ a = 9 : 8
c ≻ b= 9 : 8
c ≻ d= 9 : 8 Побеждает ‘c’!!!
П5. Правило подсчета очков.
Пусть число кандидатов - m.
ЧислаS1, S2, …, Smтакие, что 0 = S1 ≤ S2 ≤ … ≤Sm, где Sm> 0 (целые).
Избиратели дают S1 “очков” самым последним кандидатам, S2 = предпоследним, S3 - третьим с конца и т.д. Sm - получают первые кандидаты. Побеждает кандидат, набравший Sm (max) число очков.
Правило 5 обобщает (все) другие 1-3:
Например,
1) S1 = S2 = … = Sm-1 = 0, Sm = 1
- правило относительного большинства №1 и №2.
2) S1 = 0, S2 = 1 ,…, Sm = (m-1)
- правило Борда.
3. Правила голосования.
Первые четыре правила дают четыре различных представления о понятии “наилучший кандидат” и, следовательно “наилучший выбор”.
Но каждый из них может привести к разным результатам! Победитель по одному правилу ≠ победителю по другому правилу.
Пример, профиль А:
Правило 1 - победитель ‘a’,
Правило 2 - победитель ‘b’,
Правило 3 - победитель ‘c’,
Правило 4 - победитель ‘d’.
При любом выборе - выбор плохой с точки зрения “оставшихся” (несогласных), которых большинство.
Правило 5 более гибкое и при выборе шкалы {S1 … Sm} может “покрыть” все правила№№ 1-4.
Правило 4 (Кондорсе):

S 5 3 5 4
-------------------------
16 a a b c
9 d d c d
4 c b d b
0 b c a a

S1 = 0; S2 = 22 = 4; S3 = 32 = 9; S4 = 42 = 16;

na = 5×16 + 3×16 + 5×0 + 4×0 = 128;
nb = 5×0 + 3×4 + 5×16 + 4×4 = 108;
nc = 5×4 + 3×0 + 5×9 + 4×16 = 129;
nd = 5×9 + 3×9 + 5×4 + 4×9 = 128.
Побеждает ‘c’!!!
Но все же правило №5 существенно отличается от правила №1 (абсолютного большинства) и правила №4 (Кондорсе). Об этом отличие говорят леммы:
Лемма 1.Существуют такие профили голосования, что победитель по правилу абсолютного большинства не может быть победителем ни при каком подсчете очков.
Лемма 2.Существуют такие профили голосования, что победитель по правилу Кондорсе не может быть победителем ни при каком подсчете очков.
ДОКАЗАТЕЛЬСТВО ЛЕММ.
Лемма 1.
Рассмотрим профиль А. По правилу №2 (абсолютного большинства) победителем является кандидат ‘b’.m = 4.
Каждому присвоим очки: 0 = S1≤S2≤S3≤S4> 0.
Профиль А:
Количество голосов = количество избирателей
Предпочтение кандидатов
5 3 5 4 S
-------------------------
a a b c S4
d d c d S3
c b d b S2
b c a a S1 = 0

Число очков каждого кандидата по таблице:
na = 5S4 + 3S4 = 8S4
nb = 5S4 + 3S2 + 4S2 = 5S4 + 7S2
nc = 4S4 + 5S3 + 5S2
nd = 5S3 + 3S3 + 4S3 +5S2 = 12S3 + 5S2
Если ‘b’ победитель, то nb>na, nc, nd
nb - na = 5S4 + 7S2 - 8S4 = -3S4 + 7S2> 0
nb - nc = 5S4 + 7S2 - 4S2 - 4S4 - 5S3 - 5S2 = S4 - 5S3 + 2S2> 0
-3S4 + 7S2> 0 → S2> S4
S4 - 5S3 + 2S2> 0 → S4> 5S3 - 2S2
S2> 5S3 - 2S2
S2 + 2S2> 5S3
S2 = S2> 5 S3
S2> S3
НоS3≥ S2, т.е. S3≥ S2
Или, еслиS3≠ 0
1 > ≈ 1,154, что не верно!!!
Т.е. ‘b’ не может быть победителем по числу очков. Доказано!

Лемма 2.
Рассмотрим другой профиль голосования - В.
Количество голосов
Предпочтение кандидатов
3 6 4 4 S
-------------------------
c a b b S3
a b a c S2
b c c a S1 = 0

По правилу №4:
Пара (a, b): (3 + 6) = 9 : (4 + 4) = 8 a≻b = 9 : 8
Пара (a, c): (6 + 4) = 10 : (3 + 4) = 7 a≻c = 10 : 7
Т.е. по правилу №4 (Кондорсе) победил кандидат ‘a’.
Подсчитаем очки кандидатов:
na = 3S2 + 6S3 + 4S2 = 7S2 + 6S3
nb = 6S2 + 4S3 + 4S3 = 6S2 + 8S3
nc = 3S3 + 4S2 = 4S2 + 3S3
nb - na = 2S3 - S2 = S3 + (S3 - S2) > 0
S3> 0, (S3 - S2) > 0.
Т.е. ‘a’ проигрывает ‘b’ по очкам при любых целых Si. Доказано!