_{Міністерство} освіти України

Державний університет

“Львівська політехніка”

Кафедра ІСМ

КУРСОВА РОБОТА

з предмету “Методи підтримки прийняття рішень”

на тему

“Модель колективного вибору
рішень”

Виконала:

студентка гр. ІСМ-5М

Шаховська Наталя

Залікова книга: № 9517007

Перевірив:

доц. Катренко А. В.

Львів – 1999Кафедра “Інформаційні системи та мережі”

Фах “Інтелектуальні системи прийняття рішень”

Базовий напрямок “Комп’ютерні науки”

1. ЗАВДАННЯ НА КУРСОВУ РОБОТУ

з предмету “Методи підтримки прийняття рішень”

студентки гр. ІСМ-5М

Шаховської Наталі

1. Тема: “Модель колективного вибору рішень”

2. Завдання: розробити програму для демонстрації роботи одного з методів голосування.

3. Зміст пояснювальної записки.

1 Змістовна постановка задачі

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

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

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

4.1 Визначення переможця Борда

4.2 знаходження оцінки Копленда

4.3 Алгоритм визначення переможця за правилами Борда чи Копленда

5 Опис програми

5.1 Вибір технології програмування

5.2 Структура програми

5.3 Інструкція користувачеві

6 Контрольний приклад

Висновки

1. Перелік графічного матеріалу.

Кількість малюнків – 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

2. ВСТУП

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

Починаючи з політичної філософії Просвітництва, вибір правил голосування був головною етичною проблемою, пов'язаною з додатками, що далеко йдуть, для функціонування більшості політичних інститутів. Дебати про справедливість різноманітних методів голосування почалися з досліджень де Борда [1781] і Кондорсе [1785]. У 1952 році Ерроу запропонував формальну модель, що протягом трьох десятиліть аналізувалася в численних роботах математичної орієнтації по так званому колективному виборі.

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

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

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

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

2. ЗМІСТОВНА ПОСТАНОВКА ЗАДАЧІ

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

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

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

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

Нехай дано як контрольний приклад наступний профіль для 9 виборців і 5-ти кандидатів:

У кожному стовпці кандидати розташовані у порядку зменшення їх значущості для кожної групи виборців. Тобто, для першого стовпця (групи виборців, що складається з однієї людини) можна визначити переваги наступним чином: група виборців, що складається з однієї особи, вважає кандидата a найкращим. На другому місці вони ставлять кандидата b, на третьому місці c і т.д. аналогічно кандидати ранджовані у кожній групі.

Завдання: визначити єдиного переможця виборів.

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

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

Визначимо правило Копленда.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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