Модель колективного вибору (стр. 2 из 7)
За рівнем складності це є задача Р-типу. Час розв’язку даної задачі становить t0=a0+a1x+… +anxn і залежить від кількості груп виборців та кількості кандидатів.
Знаходження переможця за правилами Копленда і Борда є найпростішими за своєю структурою, оптимальні за Парето, анонімні, нейтральні (якщо не вказувати, що робити при рівності очок). Крім того, правило Борда иакож задовольняє аксіомі участі і поповнення (вони будуть розглянуті у наступному розділі).
Оптимальність за Парето:
Якщо кандидат 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. Правила голосування з підрахунком очок.
Фіксуємо послідовність дійсних чисел , що не спадає
s0£s1£…£sp-1 при s0<sp-1.
Виборці ранжують кандидатів, причому s0 очок дається за останнє місце, s1 - за передостаннє і так далі. Обирається кандидат із максимальною сумою очок.
Визначення 2.4. Правило Копленда. Порівняємо кандидата а з будь-яким іншим кандидатом х. Нарахуємо йому +1, якщо для більшості а краще за х,-1, якщо для більшості х краще за а, і 0 при рівності. Сумуючи загальну кількість очок по всім х, х¹а, одержуємо оцінку Копленда для а. Обирається кандидат, названийпереможцем за Коплендом, із найвищою з таких оцінок.
Визначення 2.5. Правило Сімпсона. Розглянемо кандидата а, будь-якого іншого кандидата х і позначимо через N(a,x) число виборців, для котрих а краще за х. Оцінкою Сімпсона для а називається мінімальне з чисел N(a,x) по всім х, х¹а. Обирається кандидат, названийпереможцем за Сімпсоном, із найвищою такою оцінкою.
Обидва ці правила заможні за Кондорсе.
Оптимальність за Парето. Якщо кандидат а для всіх кращий від кандидата b, то b не може бути обраним.
Анонімність. Імена виборців не мають значення: якщо два вибореці поміняються голосами, то результат виборів не зміниться.
Нейтральність. Імена кандидатів не мають значення. Якщо ми поміняємо місцями кандидатів а і b у перевазі кожного виборця, то результат голосування зміниться відповідно (якщо раніш вибирався а, то тепер буде вибиратися b і навпаки; якщо вибирався деякий х, відмінний від а і b, то він же і буде обраний).
Правила Копленда і Сімпсона оптимальні за Парето, анонімні і нейтральні, якщо ми розглядаємо їх як відображення, що ставлять у відповідність кожному профілю переваг підмножину переможців. Анонімність і нейтральність очевидні. Перевірити, що множини переможців за Борда (Коплендом, Сімпсоном) містять тільки оптимальні за Парето результати, достатньо просто. Так, оцінка Сімпсона кандидату, що домінується за Парето, дорівнює нулю, а для оптимального за Парето кандидата вона позитивна.
Монотонність. Припустимо, що а вибирається (серед переможців) при даному профілі і профіль змінюється тільки так, що положення а поліпшується, а відносне порівняння пари будь-яких інших кандидатів для будь-якого виборця залишається незмінним. Тоді а як і раніше буде обраний (знову серед переможців) для нового профілю.
Всі правила підрахунку очок, а також правила Копленда і Сімпсона є монотонними.
Відносна більшість із вибуванням. У першому раунді кожний виборець подає один голос за одного кандидата. Якщо кандидат набирає сувору більшість голосів, то він і обирається. У противному випадку в другому турі проводиться голосування за правилом більшості з двома кандидатами, що набрали найбільшу кількість голосів у першому турі.
Прихильники цього методу підтверджують, що він майже так само простий, як і правило відносної більшості (виборцям не потрібно повідомляти повне ранжування кандидатів), і виключає марнотратні вибори. При звичайному правилі відносної більшості, якщо я голосую за кандидата, що одержує маленьку підтримку, то мій голос буде марним. Проте при вибуванні в мене є ще один шанс вплинути на результат. Проте цей метод не є монотонним, як показують такі два профілі з 17 виборцями:
| Профіль А | Профіль B | ||||||
| 6 | 5 | 4 | 2 | 6 | 5 | 4 | 2 |
| a | c | b | b | a | c | b | a |
| b | a | c | a | b | a | c | b |
| c | b | a | c | c | b | a | c |
При профілі А в другий тур проходять а і b і виграє а (11 голосів проти 6). Профіль В такий же за одним винятком. У двох виборців перевага b>a>с змінюється на перевагу а>b>с, тобто для них тепер а краще за b.Тепер у другий тур проходять а і с, причому виграє с (9 голосів проти 8). Таким чином, поліпшення позиції кандидата а призводить до його поразки!
Метод альтернативних голосів. Виключимо спочатку тих, хто одержав найменшу кількість голосів. Потім порахуємо голоси для кандидатів, що залишилися, і знову виключимо невдах. Будемо повторювати цю операцію доти, поки не залишиться один кандидат (або множина кандидатів із рівним числом голосів).
Тут головна увага приділяється тому, щоб не загубити ніякі голоси і кожному дати шанс підтримати кандидата, який подобається найбільше. У цьому підході повторно використовуються методи підрахунку очок для винятку кандидатів-невдах. На жаль, будь-яке правило, засноване на послідовному виключенні за методом підрахунку очок, повинне порушувати властивість монотонності для деяких профілів.
Поповнення (однозначні правила голосування). Дві групи виборців N1, N2, що не перетинаються, мають справу з тією ж множиною А кандидатів. Нехай виборці N1 і N2 вибирають того самого кандидата а.Тоді виборці N1ÈN2 також оберуть а з А.
Ця властивість є дуже обгрунтованою, коли єдиний виборчий орган розбитий на велику кількість підмножин, як у випадку регіональних асамблей і підкомітетів.
Поповнення (відображення голосування). Дві групи виборців N1, N2, що не перетинаються, мають справу з тією ж множиною А кандидатів. Нехай виборці Ni обирають підмножину Вi з А при i=1,2. Якщо В1 і B2 перетинаються, то виборці N1ÈN2 оберуть В1ÇB2як множину найкращих для себе результатів.