Реферат: Модель колективного вибору

Реферат: Модель колективного вибору

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

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

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

Кафедра ІСМ

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

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

на тему

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

Виконала:

студентка гр. ІСМ-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

ВСТУП

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

За рівнем складності це є задача Р-типу. Час розв’язку даної задачі становить t0=a0+a1x+… +anxn і залежить від кількості груп виборців та кількості кандидатів.

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

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

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

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

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

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

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

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

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

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

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

Правило відносної більшості. Кожний виборець віддає свої голос найкращому для себе кандидату. Обирається кандидат, згаданий у найбільшій кількості бюлетенів. Це правило може суперечити думці більшості (див. 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 і виграє а (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 як множину найкращих для себе результатів.

Теорема 2.1 (Янг [1975])

(a) Всі відображення голосування, засновані на підрахунку очок (підмножини кандидатів, що вибирають, із найбільшою сумарною кількістю очок), задовольняють аксіомі поповнення. Якщо при рівності очок вибір проводиться на основі фіксованого порядку на А, то відповідні правила голосування також задовольняють аксіомі поповнення.

(b) Не існує заможного за Кондорсе правила голосування (або відображення голосування), яке б задовольняло аксіомі поповнення.

Аксіома участі. Нехай кандидат а вибирається з множини А виборцями з N. Розглянемо далі виборця i поза N. Тоді виборці з NÈ{i} повинні обрати або а, або кандидата, що для агента i строго краще а.

Це означає, що якщо додатковий голос дійсно змінює результат виборів, то це може бути тільки на руку “ключовому” виборцю.

Теорема 2.2 (Мулен [1986с])

Страницы: 1, 2