Міністерство освіти України
Державний університет
“Львівська політехніка”
Кафедра ІСМ
КУРСОВА РОБОТА
з предмету “Методи підтримки прийняття рішень”
на тему
“Модель колективного вибору
рішень”
Виконала:
студентка гр. ІСМ-5М
Шаховська Наталя
Залікова книга: № 9517007
Перевірив:
доц. Катренко А. В.
Львів – 1999
Кафедра “Інформаційні системи та мережі”
Фах “Інтелектуальні системи прийняття рішень”
Базовий напрямок “Комп’ютерні науки”
з предмету “Методи підтримки прийняття рішень”
студентки гр. ІСМ-5М
Шаховської Наталі
1. Тема: “Модель колективного вибору рішень”
2. Завдання: розробити програму для демонстрації роботи одного з методів голосування.
3. Зміст пояснювальної записки.
1 Змістовна постановка задачі
2 Формальна постановка задачі
3 Математичні методи розв’язку
4 Опис алгоритму
4.1 Визначення переможця Борда
4.2 знаходження оцінки Копленда
4.3 Алгоритм визначення переможця за правилами Борда чи Копленда
5 Опис програми
5.1 Вибір технології програмування
5.2 Структура програми
5.3 Інструкція користувачеві
6 Контрольний приклад
Висновки
4. Перелік графічного матеріалу.
Кількість малюнків – 5.
Завдання видане: 10.09.99
Завдання видав: доц. Катренко А. В. ______________________
Завдання прийняла: Шаховська Наталя ______________________
Львів – 99
ЗМІСТ
Вступ____________________________________________________________________ 4
1 Змістовна постановка задачі____________________________________________ 6
2 Формальна постановка задачі__________________________________________ 10
3 Математичні методи розв’язку________________________________________ 18
4 Опис алгоритму______________________________________________________ 23
4.1 Визначення переможця Борда_________________________________________ 23
4.2 Знаходження оцінки Копленда________________________________________ 25
4.3 Алгоритм визначення переможця за правилами Борда чи Копленда________ 28
5 Опис програми________________________________________________________ 31
5.1 Вибір технології програмування_______________________________________ 31
5.2 Структура програми_________________________________________________ 33
5.3 Інструкція користувачеві_____________________________________________ 35
6 Контрольний приклад_________________________________________________ 37
Висновки_________________________________________________________________ 39
Список літератури_______________________________________________________ 40
Додатки_________________________________________________________________ 41
Програма______________________________________________________________ 41
Результати роботи програми______________________________________________ 45
| “Демократія як метод керування використовує результати суспільних рішень громадян на виборах і рішень законодавців у представницьких органах” (Рікер [1982]). |
Більшість суспільних розподілених рішень (таких, як податки і суспільні витрати) приймається на основі голосування. Вибори також використовуються для поповнення багатьох суспільних закладів. Тут ми маємо важливі приклади чистих суспільних продуктів (наприклад, усі громадяни даного міста без яких-небудь винятків беруть участь у “споживанні” свого мера), що вибираються на основі голосування і без побічних платежів.
Починаючи з політичної філософії Просвітництва, вибір правил голосування був головною етичною проблемою, пов'язаною з додатками, що далеко йдуть, для функціонування більшості політичних інститутів. Дебати про справедливість різноманітних методів голосування почалися з досліджень де Борда [1781] і Кондорсе [1785]. У 1952 році Ерроу запропонував формальну модель, що протягом трьох десятиліть аналізувалася в численних роботах математичної орієнтації по так званому колективному виборі.
Формально правило голосування вирішує задачу колективного ухвалення рішення, у котрої декілька індивідуальних агентів (виборців) повинні спільно вибрати один із декількох результатів (також званих кандидатами), щодо котрих їхні думки розходяться. Будемо припускати, що кінцева множина N виборців повинна обрати одного кандидата з кінцевої множини А. Для простоти припустимо, що індивідуальні думки (або переваги) не припускають випадків байдужності. Кожна така перевага є довільним лінійним порядком на А.
Правило голосування вибирає кандидата на основі повідомлених порядкових переваг і тільки на основі цих переваг. У цьому істотна відмінність від моделей, у яких гроші й інші продукти дозволяли здійснювати довільно малі компенсації для агентів. Голосування не припускає поступки між двома кандидатами інакше, ніж за рахунок можливого обрання третього кандидата.
Якщо кандидатів тільки два, то звичайне правило голосування більшістю голосів безперечно є найбільш справедливим методом. Цей принцип більшості - вихідний пункт процесу демократичного прийняття рішень. Він був явно сформульований два сторіччя тому, а його основа є набагато більш древньою. Аксіоматична формалізація принципу більшості запропонована Меєм.
Розгляду методів голосування і втіленню у програму одного з них і присвячена дана курсова робота. Буде проведена порівняльна характеристика різних методів голосування, і за допомогою контрольного прикладу продемонстрована робота одного з них.
Завдання, яке ставиться переді мною у даній курсовій роботі – забезпечити процес виборів, тобто кінцева множина N виборців повинна обрати одного кандидата з кінцевої множини А. Обов’язковою умовою є обрання єдиного кандидата. Для простоти припустимо, що індивідуальні думки (або переваги) не припускають випадків байдужності. Кожна така перевага є довільним лінійним порядом на А (тобто повне транзитивне й асиметричне бінарне відношення). Це припущення не призводить до істотних втрат загальності.
Формально правило голосування вирішує задачу колективного ухвалення рішення, у котрої декілька індивідуальних агентів (виборців) повинні спільно вибрати один із декількох результатів (також званих кандидатами), щодо котрих їхні думки розходяться.
Правило голосування являє собою систематичне рішення, яке у всій повноті опирається на індивідуальні думки. Позначимо через L(А) множину лінійних порядків на А,тоді правило голосування є відображенням L(А)N в А. Те, що правило голосування може бути визначене для будь-якої мислимої конфігурації переваг, виражає фундаментальний принцип свободи думок: кожний виборець має право ранджувати кандидатів будь-яким чином. Проте в деяких моделях голосування, що містять економічні змінні або невизначені результати, можна припускати, що переваги виборців задовольняють деякій загальній умові. Це особливо зручно при стратегічному аналізі голосування і при агрегуванню переваг.
Правило голосування вибирає кандидата на основі повідомлених порядкових переваг і тільки на основі цих переваг. У цьому істотна відмінність від моделей, у яких гроші й інші продукти дозволяли здійснювати довільно малі компенсації для агентів. Голосування не припускає поступки між двома кандидатами інакше, ніж за рахунок можливого обрання третього кандидата.
Нехай дано як контрольний приклад наступний профіль для 9 виборців і 5-ти кандидатів:
| 1 | 4 | 1 | 3 |
| abcde | cdbea | eadbc | eabdc |
У кожному стовпці кандидати розташовані у порядку зменшення їх значущості для кожної групи виборців. Тобто, для першого стовпця (групи виборців, що складається з однієї людини) можна визначити переваги наступним чином: група виборців, що складається з однієї особи, вважає кандидата a найкращим. На другому місці вони ставлять кандидата b, на третьому місці c і т.д. аналогічно кандидати ранджовані у кожній групі.
Завдання: визначити єдиного переможця виборів.
Існує багато способів визначення переможця. Вони будуть описані і відповідним чином порівняні у наступних розділах.
Зазначимо зараз, що дана курсова робота присвячена розгляду і втіленню у програму метода Копленда і порівнянню отриманого результату із результатом за методом Борда.
Визначимо правило Копленда.
Порівняємо кандидата a з будь-яким іншим кандидатом x. Нарахуємо йому +1, якщо для більшості a краще за x, -1, якщо для більшості x краще за a, і 0 при всіх x, x¹a, одержуємо оцінку Копленда для a. Обираємо кандидат, названий переможцем за Коплендом, із найвищою такою оцінкою [див. 1, ст. 321].
В даному правилі не вказано, що робити у тому випадку, коли знайдуться два або більше кандидати з однаковою оцінкою Копленда. Припустимо, що обереться той кандидат, ім’я і прізвище якого стоїть найближче за списком. Це припущення порушує правило нейтральності [див. 1, ст. 329], але, як буде доведено у наступних розділах, кожне правило голосування Копленда є найбільш наочним і легким для комп’ютерної реалізації.
Правило Борда: кожний виборець повідомляє свої переваги, ранджуючи p кандидатів від найкращого до найгіршого (байдужість забороняється). Кандидат не одержує очок за останнє місце, одержує одне очко за передостаннє місце і т.д., одержує p-1 очко за перше місце. Перемагає кандидат із найбільшою сумою очок. Він називається переможцем за Борда.
Тут так само не вказується, що робити при рівності очок, тобто також може порушуватись умова нейтральності.
Охарактеризуємо вище поставлену задачу.
Її критерієм якості є максимізація оцінки Копледа (Борда).
Обмеженнями виступають переваги виборців і їх ранджування кандидатів. Як буде вказано далі, фактично потрібно накладати також обмеження і на кількість виборців та кількість кандидатів. Проте це обмеження не є суттєвим, так як завжди при голосуванні можна провести поділ на округи.