Обобщение №4. Все монотонные избирательные системы 
, это такие и только такие избирательные системы 
, которые задаются множествами 
и 
подмножеств из множества избирателей 
. Если за кандидата 
проголосовали все члены некоторого множества избирателей 
, тогда и только тогда этот кандидат попадает в итоговый список. При этом множества 
и 
обладают свойством [1]: 
и 
.
Доказательство. Из свойства [1] следует то, что любая избирательная система 
монотонна. Таким образом, любая избирательная система 
монотонна.
Для любой монотонной избирательной системы 
можно составить множество решающих коалиций 
и 
, т. к. избирателей конечное число 
конечное число подмножеств избирателей. А если 
монотонна, то из этого следует, что 
и 
будут удовлетворять свойству [1]. Теорема доказана.
Принцип парных сравнений
Пусть существует профиль голосования u и некоторое дерево, в каждой конечной вершине которого записан какой-то кандидат. При этом все кандидаты записаны ровно по одному разу.
Будем определять победителя следующим образом: возьмем два соседних листа этого дерева и определим промежуточного победителя среди 2 кандидатов, записанных в выбранных вершинах, по принципу большинства. Этого промежуточного победителя запишем в вершину-родитель рассматриваемых листов, а сами листы сотрем. Будем повторять эту операцию, пока не останется только один кандидат – победитель выборов.
Такую избирательную систему назовем бесповторным двоичным деревом.
Теорема о парных сравнениях
Бесповторное двоичное дерево с числом кандидатов более четырех не может удовлетворять принципу единогласия.
Доказательство. Очевидно, что при числе кандидатов более четырех, у рассматриваемой избирательной системы будет существовать поддерево глубины 4. Рассмотрим его.
Рассмотрим следующий профиль голосования:
a избирателей – A, D, C, B
b избирателей – С, В, А, D
с избирателей – B, A, D, C
где (b+c)>a; (a+b)>c; (a+c)>b. То, что такие три числа существуют можно легко доказать, сказав что всегда существует невырожденный треугольник с заданным периметром и целыми сторонами. Таким образом при данном профиле голосования побеждает D, что противоречит свойству единогласия, т. к. все избиратели поставили A выше D в своих бюллетенях. Теорема доказана.
Неманипулируемые системы
Возьмем избирательную систему S, определяющую по профилю голосования единственного победителя. Путь есть 2 профиля голосования — u и v, и пусть в v все избиратели кроме одного проголосовали так же, как и в u, а один — по-другому.
Избирательная система S неманипулируема, если S(u) не хуже чем S(v) для этого избирателя в плане его бюллетеня в профиле u.
Теорема о неманипулируемых системах
Неманипулируемые нейтральные избирательные системы с тремя или более кандидатами — это только диктура.
План доказательства
Пусть S неманипулируема. Через Т обозначим коалицию избирателей.
Доказать, что свойства 1)-2) коалиции Т равносильны и что из них следует свойство 3): Если u: T X\T , то S(u)=AA B
B A
... ...
Существует профиль u вида: T X\T
... ...
такой, что S(u)=A A B
... ...
B A
... ...
3) Для всякого профиля такого вида S(u)≠B
2. Пусть W — множество всех коалиций, удовлетворяющих свойствам 1)-3) хотя бы для одной пары (A, B). 
– коалиция, содержащая минимальное число избирателей. Доказать, что 
состоит из 1 избирателя.
3. Доказать, что 
удовлетворяет свойствам 1)-3) для любой пары кандидатов (A, B).
4. Доказать, что 
– диктатор.
Теорема о неманипулируемых системах. Введем определение строго монотонной избирательной системы S.
Пусть есть 2 профиля голосования: u и v такие, что на множестве X\{А} u=v и при переходе от u к v позиции А не ухудшаются ни для одного избирателя. Тогда скажем, что профиль u поднимает кандидата a по сравнению с u.
Избирательная система S строго монотонна тогда и только тогда, когда (v поднимает А по сравнению с u) 
(либо S(v)=А, либо S(v)=S(u)). Очевидно, что неманипулируемые и строго монотонные системы – это одно и то же. Далее в доказательстве мы будем работать только со строго монотонными избирательными системами.
Сначала докажем равносильность свойств коалиций избирателей 1) и 2). Пусть для коалиции Т выполнено свойство 1) при некотором профиле голосования u. Тогда очевидным образом для коалиции Т при профиле u выполняется и свойство 2).
Пусть теперь для коалиции Т при профиле голосования u выполнено свойство 2). Докажем, что для этой коалиции также выполнено свойство 1). Возьмем профиль голосования 2) и будем опускать во всех бюллетенях всех кандидатов кроме A и B до тех пор, пока не преобразуем профиль 2) в профиль 1). Так как S строго монотонна, после каждого такого опускания, победителем при новом профиле останется кандидат А. Таким образом равносильность свойств 1) и 2) доказана.
Докажем, что из свойств 1)-2) следует свойство 3). Путь это не так, и существует такой профиль голосования 2), в котором побеждает кандидат B, а в профиле голосования 1) побеждает кандидат А. Но это очевидным образов противоречит свойству 2), равносильному свойству 1). Утверждение доказано от противного.
Коалицию избирателей Т, удовлетворяющую любому из свойств 1)-2) относительно хотя бы одной пары кандидатов (A, B) назовем решающей коалицией. Рассмотрим множество всех решающих коалиций W и решающую коалицию М, содержащую минимальное число избирателей. Докажем три леммы:
Лемма 1. Коалиция M состоит ровно из одного избирателя d.
Лемма 2. Избиратель d образует решающую коалицию для любой пары кандидатов (A, B).
Лемма 3. Избиратель d и есть диктатор.
Докажем Лемму 1 от противного. Пусть выбранная коалиция M является решающей относительно пары кандидатов (A, B) и в нее входит хотя бы два избирателя. Рассмотрим три группы избирателей: 1) D={d} (она состоит только из одного произвольно выбранного избирателя), 2) M \ D (все избиратели из M кроме d) и 3) X \ M (все избиратели, не входящие в коалицию M). Поскольку число кандидатов не меньше трёх, мы можем рассмотреть ещё одного кандидата C.
Предположим, что избиратели из каждой группы расставили кандидатов в следующем порядке:
D 1)A B … С …
M \ D 2)… С … A B
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
