ність за Парето може порушуватися.
Бінарним деревом на А є таке кінцеве дерево, у якому кожній нефінальной вершині (включно початкову) відповідають рівно дві наступні, а кожній фінальної вершині (у якої немає наступних) приписаний кандидат (елемент із A), причому кожен кандидат з'являється принаймні в одній фінальній вершині.
Серед бінарних дерев найпростішими є ті, в яких кожен кандидат приписаний рівно одній вершині. Назвемо їх деревами без повторних виключень. p> Лемма 2.1 (А) Якщо А складається з трьох кандидатів, то дерево після послідовного виключення є єдиним безповторних деревом. Відповідне правило голосування оптимально за Парето (при нашій умові, що всі порівняння по більшості суворі). (B) Якщо А складається з чотирьох кандидатів, тобто тільки два безповторних дерева: послідовне виключення і рівнобіжне виключення. Перше з них порушує оптимальність за Парето, а останнє - ні. (C) Якщо А містить п'ять або більше кандидатів, то будь-яке виключення по безповторному дереву призводить до обрання кандидата для деяких профілів, у що домінується за Парето. p> Існує бінарне дерево, визначене для довільної кількості учасників, що дозволяє уникнути обох цих небезпек. Відповідні послідовні виключення породжують оптимальне за Парето, анонімне і монотонне правило голосування. Це дерево називається деревом багатоетапного виключення. p> Для кожного конкретного упорядкування кандидатів існує по одному такому дереву. Позначимо через Г p (1,2, ... , Р) дерево, яке відповідає порядку A = {1,2 ..., р}. Визначимо його індуктивно за розміром А :
В
Так, для трьох і чотирьох кандидатів одержуємо:
В
При р кандидатах утворюються 2p-l фінальні вершини; кандидат 1 приписаний 2p-2 фінальним вершинам, а кандидат р тільки однієї. Тим не менше для обрання навіть кандидату р потрібно перемогти в р-1 дуелях (хоча йому можливо доведеться по нескольку раз зіткнутися з тим самим опонентом). Хоча дерево багатоетапного виключення велике, його рішення (тобто обчислення кандидата, який виграє) може бути отримане за допомогою дуже простого алгоритму.
Теорема 2.4 (Шепсл і Вейнгаст [1984]). p> Задані дерево багатоетапного виключення Г p (1,2, ..., р і профіль переваги, яке відповідає мажоритарному турніру Т. Кандидат а * може бути знайдений за таким алгоритмом:
(12)
Слідство теореми 2.4.
Кандидат а, що вибирається по дереву багатоетапного виключення з турніром Т, задовольняє умові:
для будь-якого b ГЋ А , b В№ а:
{ аТb } і/або { для деякого з , АТС и сTb }. (14)
У Зокрема, а оптимальний за Парето. Більш того, дерево багатоетапного виключення породжує монотонний метод голосування.
Серед заможних за Кондорсе правил голосування ми виявили три методи, які задо...
