2

Г_p(1,2,...,р-1)

Г_p(1,2,...,(р-2),p)

Г₂(1,2)

Г_p(1,2,...,р)

Так, для трьох і чотирьох кандидатів одержуємо:

1

1

2

3

1

2

3

1

2

1

1

4

Г₄(1,2,3,4)

Г₄(1,2,3)

При р кандидатах утворюються 2p-l фінальні вершини; кандидат 1 приписаний 2p-2 фінальним вершинам, а кандидат р тільки однієї. Тим не менше для обрання навіть кандидату р потрібно перемогти в р-1 дуелях (хоча йому можливо прийдеться по декілька разів зіткнутися з тим самим опонентом).

Хоча дерево багатоетапного виключення велике, його рішення (тобто обчислення кандидата, що виграє) може бути отримане за допомогою дуже простого алгоритму

Теорема 2.4 (Шепсл і Вейнгаст [1984]).

Задані дерево багатоетапного виключення Г_p(1,2,... ,р) і профіль переваги, що відповідає мажоритарному турніру Т. Кандидат а^* може бути знайдений за таким алгоритмом:

(12)

Наслідок теореми 2.4. Кандидат а, що вибирається по дереву багатоетапного виключення з турніром Т, задовольняє умові:

для будь-якого bА, bа:

{аТb} і/або {для деякого с, аТс і сTb}. (14)

Зокрема, а оптимальний за Парето. Більш того, дерево багатоетапного виключення породжує монотонний метод голосування.

Серед заможних за Кондорсе правил голосування ми виявили три методи, що задовольняють основним вимогам оптимальності за Парето, анонімності і монотонності: множина переможців за Коплендом, множина переможців за Сімпсоном і дерево багатоетапного виключення. Перші два нейтральні, але можуть виділяти декількох переможців (додаткове правило при рівності очок порушить нейтральність). Зауважимо, що переможець при багатоетапному виключенні знаходиться швидше, оскільки алгоритм (12) у середньому потребує порівняння не більше половини від усіх p(p-l) пар. У той же час для визначення переможців за Коплендом і Сімпсоном потрібно провести весь турнір порівнянь за правилом більшості.

2. Математичні методи розв’язку

У попередньому розділі були описані методи підрахунку очок і основні вимоги до них. Порівняємо ці методи.

Як було зазначено, найлегшим серед них, але й найгіршим, є правило відносної більшості. Можна переконатись, що насправді воно суперечить думці більшості. Тому воно не може бути вибране для комп’ютерної реалізації.

Як Борда, так і Кондорсе зауважили, що правило відносної більшості може призводити до обрання поганого кандидата, точніше такого кандидата, що у парному порівнянні за правилом більшості програє будь-якому іншому кандидату.

Для того щоб перебороти цю хибу, Кондорсе і Борда запропонували відмовитися від правила відносної більшості, причому кожний із них запропонував своє правило замість даного. Кондорсе запропонував вибирати кандидата, що перемагає будь-якого іншого кандидата в парному порівнянні, якщо такий переможець за Кондорсе існує. Борда запропонував приписати очко кожному кандидату, який лінійно зростає у залежності від його рангу в перевазі виборця. Потім він запропонував обрати кандидата, що одержав найбільшу сумарну кількість очок в усіх виборців. Ці дві ідеї породжують два найбільше важливих сімейств правил голосування.

Результати цих правил голосування можуть сильно відрізнятися за властивостями. Однією із таких властивостей є аксіома монотонності. Правило голосування називається монотонним, якщо кандидат залишається обраним при посиленні його підтримки (тобто коли відносна позиція даного кандидата у чиїхось перевагах поліпшується, а відносні позиції інших кандидатів не змінюються). Всі методи підрахунку очок є монотонними, але деякі відомі методи, що виникають із підрахунку очок, не є такими. Прикладами таких правил служать дуже популярне правило відносної більшості з вибуванням і метод альтернативних голосів.

Є дві аксіоми, що призводять до критики заможних за Кондорсе правил (оскільки дані правила порушують ці аксіоми). З іншого боку, на цих аксіомах заснована характеризація методу підрахунку очок. Ці аксіоми порівнюють кандидатів, обраних різноманітними групами виборців. Вони називаються властивостями поповнення й участі. Поповнення означає, що якщо дві групи виборців , що не перетинаються, (наприклад, сенат і палата представників) обирають того самого кандидата а, то об'єднання цих двох виборчих органів підтвердить обрання а. Участь означає, що виборець не може виграти, утримуючись від голосування, у порівнянні з можливістю брати участь у голосуванні і висловити свої переваги. Будь-яке заможне за Кондорсе правило порушує обидві ці аксіоми. На противагу цьому правила підрахунку очок характеризуються властивістю поповнення (теорема Янга) і задовольняють аксіомі участі. Теорема Янга в даний час є найістотнішим доказом у підтримку методів підрахунку очок, зокрема системи очок Борда.

Заможні за Кондорсе правила голосування усе ж надзвичайно популярні, зокрема, завдяки простоті доведення парного порівняння за правилом більшості. Відповідний клас заможних за Кондорсе методів заснований на послідовних порівняннях за правилом більшості. Законопроект і численні поправки до нього в конгресі США голосуються саме у такий спосіб. Відомий метод послідовного винятку може порушувати умову оптимальності за Парето. Інші методи, засновані на бінарних деревах парних порівнянь за правилом більшості, суперечать аксіомі монотонності. Найпростіше правило, що засноване на послідовному порівнянні і є оптимальним за Парето і монотонним, називається багатоетапним методом винятку. При використанні цього методу потрібно менше парних порівнянь, ніж в інших, концептуально більш простих методах, наприклад у правилі Копленда. За останнім правилом обирається той, хто виграє більшість парних дуелей. Таким чином, голосування, засноване на послідовних парних порівняннях, може задовольняти найбільше важливим аксіоматичним вимогам, але тільки в тому випадку, якщо ми акуратно виберемо цю послідовність.

Правила Борда, відносної більшості та антибільшості являють собою приклади правил голосування з підрахунком очок. Проте правило антибільшості явно не є монотонне, а правило відносної більшості – несправедливе.

Переможець Борда не може бути найгіршим за Кондорсе, так як він є кандидатом, що має найвищий середній бал. За цим правилом завжди знаходяться оптимальний за Парето переможець або їх множина. Прикладами заможних за Кондорсе правил є правила Копленда та Сімпсона. Так само, як і правило Борда або будь-який інший метод підрахунку очок, ці правила вибирають для кожного профілю підмножину переможців, яка може складатись з декількох кандидатів, що одержали однакову оцінку.

Як вже було зазначено, правила голосування повинні бути монотонні, оптимальні за Парето, антонімні і нейтральні. Всі правила голосування з підрахунком очок, крім правила антибільшості, є оптимальні за Парето, монотонні, анонімні і нейтральні, якщо ми не вказуємо, що робити при рівності очок. Крім того, правила голосування повинні задовольняти аксіомі участі та поповнення. Метод Борда відноситься до цих правил (це було показано у попередньому розділі).

Правила Борда і Копленда, як зазначає Мулен, спираючись на практику, не дуже части призводять до рівності очок [1, ст. 299], тому у цьому ракурсі є найкращими. Проте методи Кондорсе, до яких відноситься і правило Копленда, для деяких профілів може не задовольняти аксіомі участі.

Наступною групою правил є правила, засновані на послідовному виключенні за методом підрахунку очок (відносна більшість з вибуванням, метод альтернативних голосів). Проте ці правила, як і будь-які інші методи з вибуванням кандидатів, порушують властивість монотонності для деяких профілів.

Метод рівнобіжного виключення вибирає оптимальний за Парето результат у (найбільше поширеному) випадку, коли при бінарних виборах немає рівностей. Проте якщо рівності можливі, то оптимальність за Парето може порушуватися.

Незважаючи на вище перераховані труднощі, спроможність за Кондорсе, широко відома у якості демократичного принципу, в той час як правило Борда “приховує” справжні симпатії виборців за математичною формулою.

До заможних до Кондорсе правил відносять також наступні методи голосування:

а) голосування з послідовним винятком. За очевидних причин це правило не є нейтральним і оптимальним за Парето, так як порядок виключень впливає на результат голосування. Визначаючи порядок денний, голова фактично контролює процес виборів. Проте це правило досить широко використовується Конгресом США;

б) правило рівнобіжного виключення. Воно породжує дерево без повторних виключень і вимагає проведення цілої низки мажоритарних турнірів. Як було доведено в попередньому розділі, бінарне дерево може дати оптимальне за Парето правило голосування тільки у складнішому випадку, ніж безповторне дерево. Також може порушуватись монотонність;

в) дерево багатоетапних виключень. Цей метод забезпечує проведення наполовину меншої кількості мажоритарних турнірів, ніж метод Копленда. Воно має великий розмір. Кандидатам, можливо, потрібно брати участь у дуелях з тим самим опонентом по декілька разів. Проте його алгоритм є досить простим. Дерево багатоетапного виключення породжує оптимальний за Парето і монотонний метод голосування. Завжди знаходиться єдиний переможець, а не множина. Проте цей метод породжує всі труднощі, які пов’язані з використанням бінарних дерев.

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

Серед заможних за Кондорсе правил голосування ми виявили три методи, що задовольняють основним вимогам оптимальності за Парето, анонімності і монотонності: множина переможців за Коплендом, множина переможців за Сімпсоном і дерево багатоетапного виключення. Серед методів підрахунку очок найкращим виявився метод визначення переможця за Борда. Заможні за Кондорсе правила застосовані на парному порівнянні кандидатів за правилом відносної більшості. Для пересічного виборця вони є найбільш зрозумілими.

Правило Борда задовольняє аксіомі участі та поповнення, але приховує за математичною формулою справжні переваги виборців.

Для програмної реалізації виберемо один з методів Копленда як найпростіший і для порівняння визначимо переможця за Борда.

Приведемо ще раз правила Копленда і Борда для того, щоб перейти до формулювання алгоритму програми.

Правило Борда. Кожний виборець повідомляє свої переваги, ранджуючи р кандидатів від кращого до гіршого (байдужність забороняється). Кандидат не одержує очок за останнє місце, одержує одне очко за передостаннє і так далі, одержує р-1 очок за перше місце. Перемагає кандидат із найбільшою сумою очок. Він називається переможцем за Борда.

Правило Копленда. Порівняємо кандидата а з будь-яким іншим кандидатом х. Нарахуємо йому +1, якщо для більшості а краще за х, -1, якщо для більшості х краще за а, і 0 при рівності. Сумуючи загальну кількість очок по всім х, ха, одержуємо оцінку Копленда для а. Обирається кандидат, названий переможцем за Коплендом, із найвищою з таких оцінок.

Вважаємо, що вхідними даними задачі є вже згрупована інформація: сформовані групи виборців з однаковими у кожній групі рангами переваг. Проте допускається і занесення інформації кожним виборцем окремо.

2. Опис алгоритму

У даному розділі наводяться алгоритми для знаходження переможців виборів.