Тут так само не вказується, що робити при рівності очок, тобто також може порушуватись умова нейтральності.

Охарактеризуємо вище поставлену задачу.

Її критерієм якості є максимізація оцінки Копледа (Борда).

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

За рівнем складності це є задача Р-типу. Час розв’язку даної задачі становить t₀ =a₀ +a₁ x+… +a_n xⁿ і залежить від кількості груп виборців та кількості кандидатів.

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

Оптимальність за Парето:

Якщо кандидат a для всіх кращий від кандидата b , то b не може бути обраний.

Анонімність:

Імена виборців не мають значення – якщо два виборці поміняються голосами, то результат виборів не зміниться.

Нейтральність:

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

Монотонність:

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

2 Формальна постановка задачі

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

Опишемо методи голосування, які можуть використовуватись для розв’язання даної задачі і наведемо ряд основних визначень і теорем.

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

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

Ми не уточнюємо, що робити при рівності очок.

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

для всякого b ¹ а виборців , що вважають а кращим за b , більше , ніж тих , хто вважає , що b кращим за а .

Заможне за Кондорсе правило вибирає переможця за Кондорсе , якщо такий існує .

Відсутність переможця за Кондорсе є знаменитим “парадоксом голосування”. Як часто може спостерігатися парадокс голосування? У загальному випадку ймовірність p (p , n ) того, що переможця за Кондорсе не існує при р кандидатах і п виборцях, зростає по р і зростає по числу виборців від п до n +2. Це може бути перевірене на основі обчислення p (п , р) для малих значень п і р , але в загальному випадку це твердження залишається недоведеним припущенням.

Парадокс голосування стає майже достовірною подією, коли число кандидатів стає достатньо великим при фіксованому п . Якщо число виборців стає достатньо великим при фіксованому р , то гранична ймовірністьp (p ) може бути оцінена за Фішберн [1984]:

яка справедлива з точністю до половини відсотка при р £50.

Визначення 2.3. Правила голосування з підрахунком очок.

Фіксуємо послідовність дійсних чисел , що не спадає

s₀ £s₁ £…£s_p-1 при s₀ <s_p-1 .

Виборці ранжують кандидатів , причому s₀ очок дається за останнє місце , s₁ - за передостаннє і так далі . Обирається кандидат із максимальною сумою очок .

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