Розв'язання типових завдань для проведення голосувань за допомогою програмування

Вступ

Актуальність теми: На сьогоднішній день більшість суспільних рішень приймається на основі голосування. Голосуванням вибираються президенти, народні депутати, голосуванням приймаються рішення у Верховній Раді, на засіданнях Вчених рад університету і факультетів, на засіданнях кафедр, при прийнятті рішень Державною екзаменаційною комісією, у студентських колективах. Це є приклад чистих суспільних продуктів, що вибираються на основі голосування без побічних платежів.

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

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

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

Якщо кандидатів тільки два, то звичайне правило голосування більшістю голосів безперечно є найбільш справедливим методом. Цей принцип більшості - вихідний пункт процесу демократичного прийняття рішень. Він був явно сформульований два сторіччя тому, а його основа є набагато більш древньою. Аксіоматична формалізація принципу більшості запропонована Меєм.

Мета роботи: розглянути методи голосуванння та програмно реалізувати метод Кондорсе, метод Борда та правило паралельного виключення; зробити порівняння цих методів.

І. Теоретична частина

§ 1.1 Огляд методів голосування та їх характеристика

Існує багато методів голосування, щоб визначити переможця. Опишемо методи, що широко використовуються на практиці. Нехай N= - множина «виборців», А={a, b, c,…}={} - множина «кандидатів». Кожен виборець задає «індивідуальну перевагу» на множині кандидатів у вигляді строгого ранжування, тобто задає лінійний порядок L (A) (повне, транзитивне, асиметричне бінарне відношення). Система всіх індивідуальних переваг називається профілем. Розглянемо наступний профіль:

Рис.1

Цей профіль містить інформацію про те, що 5 перших виборців на перше місце поставили кандидата a, на друге — d, на третє - c, а на четверте (останнє) — b. Аналогічно наступні три виборці розташували кандидатів у послідовності a, d, b, c і т.д. Отже, маємо n=17 виборців і m=4.

Правило (метод) відносної більшості. Для заданого профілю: на перше місце 8 виборців поставили кандидата a (= 8), 5 виборців — b (= 5) і 4 виборці c (= 4),. Перемагає той кандидат, за якого проголосувала більшість виборців (у даному випадку — a, випадок рівності голосів поки що не розглядаємо).

Цей метод вважається більш зручнішим, тому що, якщо за певного кандидата проголосувала абсолютна більшість, тобто більше половини виборців (часто говорять — «50% +1»), то він і перемагає.

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

Для нашого випадку, у другий тур проходять кандидати a і b. Після відсіювання інших кандидатів (тому — «відносна більшість з вибуванням»), маємо такий випадок: переваги виборців після першого туру за визначенням не змінюються.

У другому турі = 8, = 9, тобто перемагає кандидат b, перемагає «абсолютно», набираючи більше половини голосів, тому метод і називається методом «абсолютної більшості». Зауважимо, що випадок рівності ми поки що виключаємо. Не розглядається і випадок «голосування» проти обох, як і при виборах президента України.

Правило Борда («підрахунку очок»). У цьому правилі за останнє місце кандидата йому нараховується 0 балів (очок), за передостаннє - 1 бал, …, за перше — (m-1). Розглянемо профіль :

Маємо:=24, =22, =27, =29.

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

Правило Кондорсе. За цим правилом «переможцем» оголошується той кандидат, що «перемагає» всіх інших у попарних порівняннях. Так, у попередньому профілі: 8 виборців поставило кандидата a вище за b, 9 виборців поставило a нище за b (позначимо це через відношення: a: b=8:9). Маємо: b: c=8:9; c: d=9:8; a: c=8:9; b: d=5:12; a: d=8:9. Єдиний кандидат, який «перемагає» всіх інших — це кандидат c.

Узагальнимо правило Борда й Кондорсе.

Задамо не спадаючу послідовність дійсних чисел,. Виборці ранжують кандидатів, причому балів дається за останнє місце, за передостаннє і т.д. Вибирається кандидат з максимальною сумою балів. Тим самим отримуємо «узагальнене правило Борда», або «метод голосування з підрахуванням балів».

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

Цікаво порівняти правила Кондорсе й Борда (узагальнене правило Борда). У певному сенсі вони є несумісними.

Найчастіше використовують два наступні правила, що узагальнюють метод Кондорсе.

Правило Сімпсона. Позначимо через S (a, x) число виборців, для яких кандидат, а кращий за х, ax. Оцінкою Сімпсона кандидата, а називається число. Переможцем Сімпсона називається кандидат (кандидати) з найвищою оцінкою Сімпсона. Наприклад, маємо профіль:

«a"=min{14,8}=8 ПЕРЕМОЖЕЦЬ «a» ;

«b"=min{15,7}=7 ;

«c"=min{13,6}=6.

Правило Копленда. Аналогічно, K (a, x) число виборців, для яких кандидат, а кращий за х, ax. Порівняємо кандидата, а з будь-яким іншим кандидатом x. Припишемо K (a, x)=1, якщо для виборців a кращий за x, інакше і. Оцінка Копленда кандидата a. Переможцем Копленда (переможцем за Коплендом) називається кандидат (кандидати) з найвищою оцінкою Копленда.

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

Голосування з послідовним виключенням. Задається послідовність кандидатів, наприклад, аbcd. Перші два кандидати порівнюються між собою, і за правилом більшості виключається один з них. Той кандидат, що залишився, порівнюється з наступним і т.д. При рівності голосів залишається, наприклад, «лівий» кандидат.

За таким методом у конгресі США організовується «процес поправок» (а — поправка до закону, b — поправка до поправки, с — початкова редакція, d — status quo). Цей метод, очевидно, є методом типу Кондорсе: якщо, а — переможець Кондорсе, то він і виграє. Очевидно, також, що метод не є нейтральним — порядок виключення («порядок денний») впливає на результат. Нехай маємо наступний профіль:

Для послідовності (аbсd) переможець буде d, для (аbdс) — с, (аdbс) — b, (bdас) — а. Отже, «голова» (той, хто визначає порядок денний) може впливати на результат (хоча, звичайно, не для всякого профілю). Цікаво відмітити також, що цей метод може порушувати й оптимальність за Парето — коли кандидат a для всіх кращий від кандидата b, а це означає, що b не може бути обраний.

Розглянемо далі профіль: для послідовності (аbсd) переможцем буде кандидат d, хоча кандидат, а для всіх виборців кращий за b.

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

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

Правило паралельного виключення. Для заданої послідовності кандидатів, наприклад, аbсd, за правилом більшості порівнюється (а з b) і (c з d) («півфінал»), потім переможці у парах порівнюються між собою («фінал»). Цей метод є методом правила Кондорсе, у випадку відсутності рівності при попарних порівняннях він зберігає оптимальність за Парето. (Якщо рівності можливі, то оптимальність за Парето може порушуватись).

§ 1.2 Парадокси голосування

Правило Кондорсе видається вельми логічним — переможець перемагає всіх інших у єдиноборствах. Шахіст, що переміг усіх інших претендентів у мікроматчах (скажімо з двох партій) — безумовно найкращий. Та й при формуванні індивідуальної переваги виборець попарно порівнює (свідомо чи підсвідомо) кандидатів. Але, у мене виникло запитання: «Як бути, якщо кожен з кандидатів у когось перемагає, а комусь програє?» У цьому випадку за визначенням переможця за Кондорсе (переможця Кондорсе) не існує. Це один з так званих «парадоксів голосування». Найпростіший випадок маємо при n=m=3: для першого виборця a кращий за b і c, b кращий за c (позначимо це таким чином: a? b?c); для другого b? с?а; для третього c? a?b. Цей профіль називається «циклом Кондорсе». Маємо — a: b=2:1; a: c=1:2; b: c=2:1(у кожного по одному виграшу і по одному програшу). Наведені вище правила голосування (чи подібні до них) застосовуються у житті, всі є досить логічними, кожне з них має свої «переваги». Але їх застосування до одного і того ж профілю (Рис.1) дає абсолютно різні результати! Це другий «парадокс голосування».

Розглянемо знаменитий «парадокс Ерроу» (Р.Ерроу, американський математик, економіст, лауреат Нобелівської премії), з якого власне і почалась сучасна теорія голосування.

Теорема 3.1 («парадокс Ерроу», 1951 р.) Єдиним колективним порядком, що задовольняє аксіомам А1- А4, є «диктаторський», тобто існує виборець kN такий, що колективний порядок співпадає з його індивідуальним порядком.

Парадокс Ерроу у свій час вразив науковий світ, згадаймо, якою була геополітична карта світу у 1951 р. Можливо, він дає пояснення, за рахунок чого наша цивілізація пройшла через диктаторські режими (а у деяких країнах світу диктатура ще й зараз існує). Якщо a=b, то b=a, тобто теорема Ерроу стверджує не лише те, що колективний порядок «задається» індивідуальним порядком «диктатора», але й те, що індивідуальний порядок деякого виборця («прихованого диктатора») співпадає з колективним порядком. У такій інтерпретації теорема Ерроу стверджує про існування «провидців» (колективного вибору). Це і є свобода вибору, що дається людині Богом — вибрати «диктаторів» чи «провидців».

Доведення теореми.

Визначення 3.1 Будь-яка підмножина M множини виборців N називається коаліцією. Коаліція M називається Kвирішальною для кандидата, а проти кандидата b тоді і тільки тоді, коли з того, що всі члени коаліції M ставлять, а вище за b, а всі виборці, що до M не входять, ставлять b вище за a, випливає, що a b. Цей факт записується як M=K (a, b). Тобто, M=K (a, b)(? і М? N: ab? j NМ: аb? ab).

Визначення 3.2 Якщо для будь-яких двох кандидатів a і b, коаліція M є Kвирішальною для a проти b, то ця коаліція називається просто Kвирішальною. Тобто, M=K (a, b) ,? a, b A. Зауважимо, що вся множина N є Kвирішальною (у силу А3). Порожня множина не маже бути Kвирішальною для, а проти b, ні для яких, а і b. Якщо ніхто не ставить, а вище за b, тобто у всіх b >а, то знову у силу А3: bа, і не може бути ab.

Лема 3.1 Існує пара кандидатів (а, b) для якої знайдеться коаліція L, що складається з одного виборця {l} така, що L= K (a, b).

Доведення. Позначимо через T множину таких коаліцій M, для кожної з яких існує пара (a, b), така, що М=К (a, b). Множина Т не порожня, оскільки N? Т. Візьмемо у T коаліцію L, що містить найменшу кількість виборців. Оскільки Т? ?, то L має не менше за одного виборця (). Нехай. Розіб'ємо L на дві не порожні підмножини, що не перетинаються: одна L'={l} з одного елемента, інша L''={l} - з усіх останніх. Розглянемо профіль, заданий таблицею:

Оскільки коаліція L — К-вирішальна, то ab. Якщо сb, то L'' є Квирішальною c проти b. Але в L'' менше виборців, ніж у множині L, яка за визначенням мінімальна. Отже, с не може бути гіршим за b, звідси (у силу аксіоми повноти А1) bc. a b, b c і за аксіомою транзитивності А2 — a с. Але це означає, що L' є К-вирішальною для, а проти с, що суперечить мінімальності L.

Лему доведено.

Лема 3.2 Коаліція L={l}, існування якої доведено у лемі 3.1 є Квирішальною.

Доведення. Нехай с — довільний кандидат. Розглянемо профіль 1: Оскільки, {l}= К (a, b), то аb. З аксіоми одностайності А3 випливає bc. У свою чергу (з аксіоми А2), aс. З аксіоми незалежності А4 маємо, що aс незалежно від b, звідки {l}= К (a, с).

Аналогічно, для будь-якого кандидата d, розглянувши профіль 2 можна довести, що d с. Отже, {l}= К (с, d)? с, d.

Лема 3.3 Описаний у лемі 3.2 виборець l — диктатор.

Доведення. Розглянемо профіль …a…c…b…, де деякі виборці ставлять с вище за, а і b, а всі інші кандидати розташовуються довільно. Оскільки коаліція L={l} є K-вирішальною, то ac, за аксіомою А3: cb, за аксіомою А2: аb. Виключаючи кандидата с, у силу аксіоми незалежності А4, маємо: ab і ab, незалежно від розташування, а і b у перевагах інших виборців.

Лему доведено.

Теорему Ерроу доведено.

§ 1.3 Основні аксіоми та теореми для правил голосування

Задамо «розумні апріорні» вимоги до колективного ранжування у вигляді аксіом.

Аксіома А1 (повнота): Для будь-яких кандидатів a і b колективний порядок установлює, що або a? b, або а=b, або a? b (скорочено —? a, b A: (a?b)V (а=b)V (a?b)).

Аксіома А2 (транзитивність):? a, b, c A (ab)?(bc) ?ac.

Аксіома А3 (одностайність): якщо для всіх виборців ab, то й у колективному порядку також ab (? і N: ab? ab). Цю аксіому можна назвати двома назвами: «паретовість», «ефективність».

Аксіома А4 (незалежність): Розташування будь-яких двох кандидатів a і b у колективному порядку залежить лише від їх взаємного розташування в індивідуальних порядках і не залежить від розташування інших кандидатів.

Відмова від першої аксіоми може привести до ситуації - «вибори не відбулися», відмова від транзитивності теж виглядає досить дивною, порушення аксіоми одностайності однозначно свідчить про «фальсифікацію» виборів, відмова від аксіоми незалежності приводить до можливості маніпулюванням шляхом зняття чи введення кандидатів (положення кандидатів a і b у колективному порядку, наприклад, аb не повинно залежати від індивідуальної переваги у вигляді c? a?b, чи взагалі у відсутності кандидата c).

Теорема 3.2. (Фішберн [1973]). Існують профілі, при яких переможець Кондорсе не може бути переможцем Борда ні при якій системі балів. Розглянемо профіль:

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

Теорема залишається справедливою і для випадку не спадаючої послідовності балів. «Найменш» відомий приклад для цього випадку містить 17 виборців і 3 кандидати. Нехай > Тут також, а — переможець Кондорсе, але маємо: і оскільки число невід'ємне, додатне.

Множина кандидатів, яка може бути вибрана при деякому методі підрахунку легко описується. Для даного профілю і даного кандидата, а будуємо вектор Г (а) наступним чином :

(а) — це число виборців, у яких a має перше місце;

(а) — число виборців, у яких a має перші два місця і т.д.

Тоді кандидат, а не може бути переможцем ні при якому узагальненому методі Борда, якщо вектор Г (а) за Парето переважає над вектором Г (b) для деякого іншого кандидата b. Більше того, можна показати, що a є переможцем за правилом підрахунку очок тоді і тільки тоді, коли вектор Г (а) є слабо оптимальним за Парето (не існує кандидата b, для якого (b) >(a) для). Якщо система балів утворює строгу послідовність то переможець a узгоджується з «простою» оптимальністю за Парето. Зауважимо, що за методом Кондорсе (найгірший) переможець не може бути найгіршим (переможцем) за правилом Борда, як не може мати місця для правила відносної більшості (див. профіль на рис.1). Ці твердження випливають з того, що переможець за правилом Борда має у середньому найбільше число виборців, що його підтримують у «бінарних дуелях» з іншими кандидатами.

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

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

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

Не можна, звичайно, відмовитись і від аксіоми А3 одностайності (оптимальності за Парето), тому узагальнимо її наступним чином :

Аксіома А3* (ефективність): Якщо кандидат, а для всіх виборців кращий за кандидата b, то b не може бути вибраним.

Розглянуті вище правила Борда, Копленда й Сімпсона анонімні, нейтральні й оптимальні за Парето. Те ж саме справедливо і для будь-якого правила голосування з підрахунком балів, якщо останні різні), при рівності балів оптимальність за Парето може порушуватись. Якщо ж нам необхідно виділити єдиного кандидата (при застосуванні правил підрахунку очок методом Копленда або Сімпсона), то у загальному випадку це не можливо зробити без порушення або анонімності, або нейтральності. Це стає очевидним, якщо розглянути метод Кондорсе: abc, bca, сab. Якщо при анонімному нейтральному і однозначному правилі голосування вибирається, наприклад, a то при перестановці a і b, b і c, c і a (у результаті отримаємо профіль: bca, сab, abc), з одного боку, (за анонімністю) переможцем повинен залишатись a, з іншого, (за нейтральністю) переможцем повинен стати с (оскільки ми поміняли «імена» a і с).

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

Наступний «критерій» — властивість монотонності. Він говорить про те, що більша підтримка кандидата не може зменшити його шанси бути вибраним. Ця властивість називається позитивним оберненим зв’язком.

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

Всі правила підрахунку очок, а також правила Копленда й Сімпсона є монотонними. Що до правила відносної більшості з вибуванням, то воно не є монотонним.

Розглянемо два профілі:

Другий профіль відрізняється від першого лише останнім стовпчиком, в якому положення, а у порівнянні з b покращується. Перевіримо, що для першого профілю переможцем за правилом відносної більшості з вибуванням є а, а для другого профілю b. Покращення позиції а призводить до його поразки! Можна уявити гіпотетичну ситуацію, в якій перший профіль — «істинний» (відповідає індивідуальним перевагам виборців, у другому профілі - «підкуплені» два виборці міняють свою перевагу між, а і b. Резюме — голосуйте чесно!

Не є монотонним і правило (метод) альтернативних голосів.

Наступна властивість вперше була введена Сміттом і Янгом і відома, як аксіома Янга про поповнення.

Аксіома А8 (поповнення (однозначні правила голосування)): Дві групи виборців N1 і N2, що не перетинаються, вибирають одного і того ж кандидата, а з множини А. Тоді виборці з множини N= також вибирають а. У цій властивості говориться про те, що множина виборців розбивається на територіальні дільниці, або проект закону розглядається у підкомісіях.

Поповнення (відображення голосування). Нехай виборці з вибирають кандидатів з А, з — з, ,. Тоді виборці з N= виберуть кандидатів з .

Теорема 3.3 (Янг [1975]). Усі правила голосування, що базуються на підрахунку балів, задовольняють аксіомі поповнення. Якщо при рівності очок вибір відбувається на основі фіксованого порядку на А, то відповідні правила також задовольняють аксіоми поповнення. Правило Кондорсе (або його узагальнення: коли вибирається переможець Кондорсе, якщо останній існує) не задовольняє аксіомі поповнення.

Аксіома А9 (участь): Нехай кандидат A вибирається виборцями з N. Нехай до множини виборців добавляється новий виборець i (i). Тоді виборці з N повинні вибрати або або кандидата, який для агента i є строго кращим за

Переможця за Кондорсе для наведеного профілю не існує, переможцем за Сімпсоном є кандидат

Нехай до розгляненого профілю добавляться ще 4 виборці з перевагами: c? a?b?d. Для нового профілю переможцем буде b). Отже, чотирьом новим виборцям треба відмовитися від участі у виборах, щоб переміг кандидат a!

Теорема 3.4 (Мулен [1986]). Для всіх правил голосування з підрахунком очок, коли при рівності очок вибір відбувається за допомогою заданого порядку на A, аксіома участі виконується. Якщо A має хоча б чотири кандидати, то для правил типу Кондорсе не задовольняється аксіома участі.

Для формування результатів голосування використаємо ще одну аксіому.

Аксіома 10 (неперервність). Нехай виборці з вибирають кандидатів a з А, з — b A, a. Тоді існує (досить велике) натуральне число m, таке що (m вибере а.

Ця вимога є досить «м'якою», якщо група виборців є досить малою, тому вона не повинна впливати на результат виборів, що визначається m — «дуелями» групи виборців. Ця аксіома гарантує відсутність диктатора.

Теорема 3.5 (Янг [1975]). Відображення голосування базується на правилі підрахунку балів тоді і тільки тоді, якщо воно задовольняє наступним чотирьом аксіомам: анонімності, нейтральності, поповнення й неперервності.

Доведення цієї теореми (що є характеризацією правила підрахунку очок) є вельми складним.

Не дивлячись на складності, що виявлені вище для методів типу Кондорсе, вони широко застосовуються на практиці.

При голосуванні за правилом відносної більшості з вибуванням, іноді буває доцільно віддати свій голос не найкращому для себе кандидату, а деякому іншому: якщо я знаю, що найкращий для мене кандидат, а все рівно не пройде, оскільки кандидати b і c однозначно наберуть більше голосів, то я краще допоможу тому кандидату з b, c, котрий для мене має більші переваги. Природно виникає питання — чи існує «захищене від маніпулювання» правило голосування, тобто таке правило, що кожний виборець, знаходячись у кабіні для голосування, завжди міг вказати свій приоріет правдиво? У випадку бінарного вибору голосуванням за правилом відносної більшості є, очевидно неманіпульованим. Якщо кандидатів не менше трьох, то єдиним неманіпульованим правилом голосування є диктаторське правило. Цей результат, аналогічний теоремі Ерроу, був доведений Гіббартом і Саттертвайтом. Зрозуміло, що диктаторське правило не може бути прийнятим, як найбільш несправедливе (для абсолютної більшості людей). Однак, для будь-якого недиктаторського правила голосування існує профіль переваг, при якому деякому агенту вигідно не повідомляти правдиво свої переваги. Таким чином, голосування не є механізмом збору інформації про переваги виборців, що заслуговує на довіру. Але що ж робити? Як подолати негативний результат Гіббарта — Саттертвайта? Головною особливістю цієї теореми є те, що будь-який профіль переваги є допустимим «входом» для правил голосування. Якщо можна із змістовних міркувань обмежити область переваг, то загроза маніпуляцій, можливо, зникне. Наприклад, нехай профіль переваг змінюється в області, у котрій переможець Кондорсе завжди існує. Тоді голосування за правилом більшості (що вибирає у точності переможця Кондорсе) є захищеним від маніпулювання.

На завершення, сформулюємо теорему Гіббарта — Саттертвайта строго. Нехай L (A) — множина лінійних порядків на скінченій множині кандидатів A (повних, транзитивних, асиметричних відношень на A). Нехай N — скінчена множина виборців. Думка виборця записується з допомогою функції корисності, що відображає порядок на, А (байдужості виключаються). Наприклад, для івиборця кандидат a на першому місці, bна другому і т.д.

Правило голосування є однозначне відображення S, що ставить кожному профілю результат виборів S. Нехай S є відображенням «на»: для кожного, а існує такий профіль u, що S (u)=a (ніякий кандидат не може бути апріорі відкинутим).

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

Теорема 3.6 (Гіббарт [1973], Саттертвайт [1975]). Якщо має більше двох кандидатів, то правило S є захищеним від маніпулювання тоді і тільки тоді, коли воно є диктаторським: S= для деякого агента диктатора, де для

§ 1.4 Узагальнена порівняльна характеристика методів голосування

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

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

Є дві аксіоми, що призводять до критики правил Кондорсе. На цих аксіомах заснована характеристика методів голосування. Ці аксіоми порівнюють кандидатів, обраних різноманітними групами виборців. Вони називаються властивостями поповнення й участі. Поповнення означає, що якщо дві групи виборців, що не перетинаються, обирають одного і того ж самого кандидата а, то об'єднання цих двох виборчих органів підтвердить обрання а.

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

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

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

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

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

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

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

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

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

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

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

ІI. Практична частина

2.1 Постановка задачі

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

2.2 Алгоритм реалізації

1) Метод паралельного виключення.

Для визначення переможця заданої послідовності кандидатів, наприклад, з аbсd, будемо порівнювати (а з b) і (c з d) («півфінал»), потім переможців з цих пар теж порівняємо між собою («фінал») і отримаємо єдиного переможця. 2) Метод Кондорсе.

Попарно порівнюються кандидати у профілю. Виграє той кандидат, що перемагає всіх інших у цих попарних порівняннях.

3) Метод Борда.

Кожному учаснику будемо нараховувати бали (очки) відповідно до даних рейтингів. За останнє місце 0 балів (очок), за передостаннє - 1 бал, …, за перше — (m-1) бал. Переможе той кандидат, що набере найбільшу кількість балів.

2.3 Інструкція для користувача

При запуску програми в середовищі Delphi з’явиться вікно (форма), в якому ми задаємо кількість кандидатів, кількість різних ранжувань кандидатів. Для спрощення обчислень, кандидатів можемо позначити буквами латинського алфавіту: a, b, c, d…

Заповняємо профіль. На вкладці у основному меню вибираємо метод, за допомогою якого потрібного визначити переможця. На формі буде виведено повідомлення з ім'ям переможця, якщо ж переможця не можна визначити за даним методом, то виведеться «» .

2.4 Контрольні приклади

1) Нехай нам потрібно провести голосування про обрання старости групи студентів 2-го курсу Математичного факультету спеціальності «Прикладна математика». Зі списку кандидатів виборцям (студентам) потрібно поставити на перше місце того кандидата, який би на їхню думку найкраще виконував усі зобов’язання старости (це буде 1-ше місце), комусь віддати 2-ге і т.д. У голосуванні будуть приймати участь 4 кандидати та 20 виборців.

Розглянемо список кандидатів:

a) Герич Вікторія;

b) Корник Іван;

c) Пивкач Ольга;

d) Маховський Іван;

Заповнимо профіль:

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

2) Всі студенти Математичного факультету на 2-му курсі повинні обрати кафедру, на якій вони зможуть спеціалізуватися та продовжувати своє навчання на 3−5 курсі. Для цього ми проведемо голосування, за допомогою якого буде легко визначити, хто зі студентів (виборців) якій кафедрі більше за все віддає перевагу. Кожний виборець повинен поставити на перше місце таку кафедру, яка найбільш йому підходить, на друге місце — іншу кафедру і т.д. У голосуванні будуть приймати участь 4 кафедри та 20 студентів.

Розглянемо список кафедр :

a) Кібернетика та прикладна математика;

b) Cистемний аналіз;

c) Диференціальні рівняння;

d) Алгебра;

Заповнимо профіль:

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

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

Розглянемо такі заняття:

a) Музика;

b) Рукоділля;

c) Театр і кіно;

d) Спорт;

Заповнимо профіль:

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

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

Розглянемо предмети:

a) Програмування;

b) Дискретна математика;

c) Теоретична механіка;

d) Архітектура ПК і мереж;

Заповнимо профіль :

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

Висновки

В цій курсовій роботі було проведено огляд та характеристику методів голосування. Докладніше розглянуто методи Кондорсе, Борда та метод паралельного виключення. Було запрограмовано всі ці методи за допомогою програми Delphi, в якій проводились всі розрахунки щодо визначення переможця. За допомогою цієї програми розв’язують типові задачі для проводження голосувань. Також було проведено «реальне» голосування між студентами Математичного факультету на різні теми, що хвилюють теперішніх студентів.

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

З цього всього можна зробити такий висновок:

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

Список використаної літератури

1. Волошин О. Ф., Мащенко С. О. «Методи рекомендацій до виконання практичних і лабораторних робіт з теорії прийняття рішень» Київ: ВПЦ «Київський університет», 2001р.-46с.

2. Макаров И. М., Виноградская Т. М. и др. «Теория выбора и принятия решений Учебное пособие» 1982р.-328с.

3. Мулен Э. «Кооперативное принятие решений: Аксиомы и модели» Москва, Мир, 1991р.-446 с.

4.Агбук В. А. «Економіко-математичні методи» СПб: Cоюз

5. Миркин Б. «Проблема групового выбора"Москва, Наука. 1974р.-96с.

6. Ковальченко І.Д. «Математичні методи в соціально-економічних дослідженнях"Москва, Наука. 1981р.

7. Зарічний М.М. «Елементи теорії соціального вибору"Львів, 2001р.-160с.

8. Мулен Э. «Теория игр с примерами из математической экономики» Мир, 1985р.-200с.

9. Вольский В. И., Лезина З. М. «Голосование» Наука, 1991р.;

Додаток

type

TForm1 = class (TForm)

StringGrid1: TStringGrid;

SpinEdit1: TSpinEdit;

SpinEdit2: TSpinEdit;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

StringGrid2: TStringGrid;

Label4: TLabel;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

Procedure SpinEdit1Change (Sender: TObject);

Procedure SpinEdit2Change (Sender: TObject);

Procedure N1Click (Sender: TObject);

Procedure N2Click (Sender: TObject);

Procedure N3Click (Sender: TObject);

Procedure N4Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

Var

Form1: TForm1;

Mk:array ['a'.'z'] of integer;

Mhol:array of integer;

Mrang:array of array of char;

k_rrang, k_kand:integer;

implementation

{$R *.dfm}

Procedure GetData;

Var i, j: integer;

begin

k_rrang:=Form1.SpinEdit2.Value;

k_kand:=Form1.SpinEdit1.Value;

SetLength (Mhol, k_rrang+1);

SetLength (Mrang, k_kand+1,k_rrang+1);

for i:=1 to k_rrang do

begin

Mhol[i]: =strtoint (Form1.StringGrid2.Cells[i-1,0]);

end;

for i:=1 to k_kand do

begin

for j:=1 to k_rrang do

begin

Mrang[i, j]: =Form1.StringGrid1.Cells[j-1,i-1][1];

end;

end;

end;

Procedure TForm1. SpinEdit1Change (Sender: TObject);

begin

StringGrid1.RowCount:=SpinEdit1.Value;;

end;

Procedure TForm1. SpinEdit2Change (Sender: TObject);

begin

StringGrid2.ColCount:=SpinEdit2.Value;

StringGrid1.ColCount:=SpinEdit2.Value;

end;

{==============Borda==============}

Function Borda: char;

Var c, ostk, im_max:char;

i, j: integer;

begin

ostk:=chr (ord ('a')-1+k_kand);

for c:='a' to ostk do

Mk[c]: =0;

for j:=1 to k_rrang do

begin

for i :=1 to k_kand do

begin

Mk[Mrang[i, j]]: =Mk[Mrang[i, j]]+(k_kand-i)*Mhol[j];

end;

end;

im_max:='a';

for c:='b' to ostk do

if Mk[c]>Mk[im_max] then

im_max:=c;

j:=0;

for c:='a' to ostk do

if Mk[c]=Mk[im_max] then

j:=j+1;

if j=1 then

Result:=im_max

else

Result:='-';

end;

{============ Kondorse ==============}

function Porivn (im1,im2:char; ns: integer):integer;

Var i: integer;

begin

i:=1;

while (Mrang[i, ns]<>im1)and (Mrang[i, ns]<>im2) do i:=i+1;

if Mrang[i, ns]=im1 then Result:=1

else Result:=2;

end;

Procedure GetSp (im1,im2:char; var kh1, kh2:integer);

Var i, j: integer;

begin

kh1:=0; kh2:=0;

for j :=1 to k_rrang do

begin

if Porivn (im1,im2,j)=1 then

kh1:=kh1+Mhol[j]

else

kh2:=kh2+Mhol[j];

end;

end;

Function Kondorse: char;

Var pc, c, ostk, im_max:char;

i, j, k1,k2:integer;

begin

ostk:=chr (ord ('a')-1+k_kand);

for c:='a' to ostk do

begin

pc:='a';

while pc<=ostk do

begin

if pc<>c then

begin

GetSp (c, pc, k1, k2);

if k2>k1 then

break

else

pc:=succ (pc);

end

else

pc:=succ (pc);

end;

if pc>ostk then

begin

Result:=c;

Exit;

end;

end;

Result:='-';

end;

{============ Paraleljne vukljuchenja ==============}

Function ParalVukl: char;

Var fin: array of char;

kf, i, k1,k2,j:integer;

im1,im2:char;

begin

kf:=k_kand div 2;

SetLength (fin, kf+1);

for i:=1 to kf do

begin

im2:=chr (ord ('a')-1+2*i);

im1:=pred (im2);

GetSp (im1,im2,k1,k2);

if k1>=k2 then fin[i]: =im1 else fin[i]: =im2;

end;

{————————-}

for i:=1 to kf do

begin

j:=1;

while j<=kf do

begin

if j<>i then

begin

GetSp (fin[i], fin[j], k1, k2);

if k2>k1 then

break

else

j:=j+1;

end

else j:=j+1;

end;

if j>kf then

begin

Result:=fin[i];

Exit;

end;

end;

Result:='-';

end;

{================================}

Procedure TForm1. N1Click (Sender: TObject);

var c: char;

begin

GetData;

c:=Borda;

if c='-' then

ShowMessage ('Переможця знайти неможливо.')

else

ShowMessage ('Переможцем за методом Борда є кандадат: '+c);

end;

{================================}

Procedure TForm1. N2Click (Sender: TObject);

var c: char;

begin

GetData;

c:=Kondorse;

if c='-' then

ShowMessage ('Переможця знайти неможливо.')

else

ShowMessage ('Переможцем за методом Кондорсе є кандадат: '+c);

end;

Procedure TForm1. N3Click (Sender: TObject);

var c: char;

begin

GetData;

c:=ParalVukl;

if c='-' then

ShowMessage ('Переможця знайти неможливо.')

else

ShowMessage ('Переможцем за методом паралельного виключення є кандадат: '+c);

end;

Procedure TForm1. N4Click (Sender: TObject);

begin

Close;

end;

End.