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

Обидва ці правила заможні за Кондорсе.

Оптимальність за Парето. Якщо кандидат а для всіх кращий від кандидата 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 як множину найкращих для себе результатів.

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

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

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

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

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

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

(a) Для всіх правил голосування з підрахунком очок, коли при рівності очок вибір здійснюється за допомогою заданого порядку на А, виконується аксіома участі.

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

Безперервність. Нехай виборці з N1 обирають кандидата а з A, а група N2, що не пересікається з N1, обирає іншого кандидата b. Тоді існує достатньо велике число m дублів групи виборців N1, таке що комбінована група виборців (mN1)ÈN2 обере а.

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

анонімність, нейтральність,

аксіома поповнення і безперервність.

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

У цьому процесі поправок нехай а - поправка, b - поправка до поправки, с - вихідна пропозиція, d - status quo.

Цей метод задовольняє аксіомі спроможністі за Кондорсе: якщо а - переможець за Кондорсе, то він виграє. Насправді спроможність при порівняннях за правилом більшості справедлива в ширшому змісті.

Спроможність за Смітом. Якщо множина А кандидатів розбивається на дві підмножини В1, B2, що не перетинаються, і кожний кандидат b1ÎВ1 виграє (за суворою більшістю) у будь-якого кандидата b2ÎВ2, то повинний бути обраний результат із В1.

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

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

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

Бінарним деревом на А є таке кінцеве дерево, у котрому кожній нефінальній вершині (включаючи початкову) відповідають рівно дві наступні, а кожній фінальній вершині (у котрої немає наступних) приписаний кандидат (елемент із A), причому кожний кандидат з'являється принаймні в одній фінальній вершині.

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

Лема 2.1

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

(b) Якщо А складається з чотирьох кандидатів, тобто тільки два безповторних дерева: послідовне виключення і рівнобіжне виключення. Перше з них порушує оптимальність за Парето, а останнє - ні.

(c) Якщо А містить п'ять або більше кандидатів, то будь-яке виключення по безповторному дереву призводить до обрання кандидата для деяких профілі,в що домінується за Парето.

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

Для кожного конкретного упорядкування кандидатів існує по одному такому дереву. Позначимо через Гp(1,2,... ,р) дерево, що відповідає порядку A={1,2,... ,р}. Визначимо його індуктивно за розміром А:

 Так, для трьох і чотирьох кандидатів одержуємо:

		Г4(1,2,3)

 При р кандидатах утворюються 2p-l фінальні вершини; кандидат 1 приписаний 2p-2 фінальним вершинам, а кандидат р тільки однієї. Тим не менше для обрання навіть кандидату р потрібно перемогти в р-1 дуелях (хоча йому можливо прийдеться по декілька разів зіткнутися з тим самим опонентом).

Хоча дерево багатоетапного виключення велике, його рішення (тобто обчислення кандидата, що виграє) може бути отримане за допомогою дуже простого алгоритму

Теорема 2.4 (Шепсл і Вейнгаст [1984]).

Задані дерево багатоетапного виключення Гp(1,2,... ,р) і профіль переваги, що відповідає мажоритарному турніру Т. Кандидат а* може бути знайдений за таким алгоритмом:

                         (12)

Наслідок теореми 2.4. Кандидат а, що вибирається по дереву багатоетапного виключення з турніром Т, задовольняє умові:

для будь-якого bÎА, b¹а:

{аТb} і/або {для деякого с, аТс і сTb}.                (14)

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

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

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

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

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

Як Борда, так і Кондорсе зауважили, що правило відносної більшості може призводити до обрання поганого кандидата, точніше такого кандидата, що у парному порівнянні за правилом більшості програє будь-якому іншому кандидату.

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

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