Системи голосування і теорія ігор. Частина перша: парадокси і властивості

Який зробити наступний хід, якщо невідома гра?

Міст шпигунів.

Невеличка передмова

Проблема узгодженої поведінки та ухвалення рішень великими колективами ключова для всієї історії людства. Якщо дивитись під цим кутом зору, то значні історичні зміни були наслідком розвитку або появи нового типу взаємодії між рядовими учасниками процесу. Делегування права ухвалення рішень (навіть і не добровільне) за ієрархією дозволила організувати великі імперії Сходу і Єгипту. Відповідним було і обгрунтування. Наприклад, світогляд персів уявляв світ ареною боротьби Добра і Зла, де цар на чолі бюрократії намагається привнести порядок та наблизити перемогу, тому невиконання рішення старшого за посадою було, взагалі кажучи, військовим злочином. Власне якість рішення визначалась місцем в ієрархії — цар не помиляється.

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

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

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

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

Теорія ігор і системи голосування

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

Для визначення гри необхідно задати три речі: гравців, їх стратегії і їх виграші. На роль гравців виникає дві можливості: кандидати та виборці. Ідеальною була б модель де були б і ті і інші, але розв'язати таку модель буде вже неможливо. Модель з кандидатами-гравцями пов'язана з теоремою про медіанного виборця (там виборці вважаються розподіленими вздовж певної осі, наприклад, праві — ліві). Інший підхід полягає у розгляді системи з точки зору виборців. Кандидати тут вважаються фіксованими альтернативами, які вибирають гравці. Їх вплив — це їх голос, поданий за певного кандидата (або ранжування всіх кандидатів). Результат буде залежати від обраної системи голосування, а виграш гравця це перемога кандидата який йому більше подобається.

Приклад. Шестеро виборців (їм відповідають стовпці) мають наступні уподобання щодо напоїв:

NB Тут число — порядковий номер виборця. В усіх інших прикладах — кількість виборців.

Як їм вибрати один напій? Або, більш загально, як агрегувати уподобання групи людей? В ідеалі ми шукаємо функцію, яка відображає всі уподобання в один вектор-результат, наприклад:

Якщо ми говоримо про вибори, то в даному конкретному прикладі перемагає один варіант, який стоїть на першому місці — тобто сік. Якщо ж нас цікавить весь вектор, то в загальному формулюванні така функція називається функцією соціального вибору. В цьому випадку виборці 5 і 6 найбільш задоволені — виграла альтернатива, яка є їх першим вибором. Виборці 3 і 4 помірно задоволені — виграв їх другий вибір. Виборці 1 і 2 зовсім незадоволені. Будемо вимірювати задоволеність-незадоволеність цілими числами, наприклад виграші в даній ситуації будуть такі

1 і 2 — 0 балів

4 і 3 — 1 бал

6 і 5 — 2 бали

Отже, виникає природна постановка гри. Гравці — виборці, дії — вибір кандидата у бюлетені, виграш — місце переможця в особистих уподобаннях. Чим вище, тим краще. І тут виникає дві проблеми:

1. Зрозуміло, що результат буде залежати від системи голосування, тобто механізму агрегації. Очевидно, що деякі системи кращі за інших, яка з них найкраща для конкретного випадку або взагалі? І які властивості має хороша система?
2. Найпростішою стратегією виборців є «щире голосування», тобто голосування за найвищу можливу альтернативу зі своїх уподобань. Однак не все так просто, іноді гравці можуть забезпечувати собі кращий кінцевий результат проголосувавши за іншу альтернативу. Це вимагає точного знання уподобань інших та системи голосування і називається «стратегічним голосуванням».

NB Далі ми розглянемо «ідеальний світ» де виборці голосують щиро, тобто вибирають свій перший можливий варіант. Це зроблено з метою продемонструвати принципові можливості систем голосування і поведінки виборців.

Дві альтернативи

Випадок двох можливих альтернатив найпростіший.

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

І результат, який був отриманий в 1952 році Кеннетом Меєм звучить так (у спрощеній формі):

Для ситуації двох альтернатив абсолютна більшість є єдиною системою, яка забезпечує наступні властивості:

• вона відноситься до всіх виборців однаково;
• вона відноситься до альтернатив однаково;
• вона монотонна: якщо один з виборців забере свій голос у програвшого кандидата і передасть його переможцю, то результат буде той самий.

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

Три і більше альтернативи

Теорема дала надію що такий самий трюк можна провернути і для більшої кількості альтернатив (тобто сформулювати систему властивостей і виділити виборчі процедури, які їм задовольняють). Але виявилось, що для трьох і більше альтернатив метод абсолютної більшості просто далеко не завжди визначає переможця. Це явно не те, що б ми хотіли від виборчої системи. Отже, властивість 1: Виборча система має завжди визначати переможця. Найближча до абсолютної більшості (для 3 і більше альтернатив) є відносна більшість.

Відносна більшість це правило, за яким перемагає той, хто набрав більшість перших місць у уподобаннях виборців. Відносна більшість теж практично завжди визначає переможця. Чому ж не використовувати її?

Розглянемо новорічний приклад.

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

Але виявляється, що ця система вразлива до численних парадоксів:

• Парадокс абсолютного лузера. Абсолютна більшість (4 з 7) вважають холодець найгіршим вибором!
• Залежність від нерелевантних альтернатив. Якщо виявиться, що оселедця немає і шубу приготувати неможливо, то переможе олів'є.
• Парадокс переможця за Кондорсе (про цю систему буде в наступній частині). Якщо ми спробуємо проголосувати пари альтернатив, то отримаємо наступний результат: холодець — шуба (3 виборців вважають, що холодець краще (третій стовпчик таблиці), виборці з першого і другого стовпчика вважають, що шуба краще — в сумі це 4 голоси. Отже 3 проти 4, перемагає шуба), шуба — олів'є (5 vs 2), холодець — олів'є (3 vs 4). Тобто шуба попарно перемагає будь-яку іншу альтернативу (є переможцем за Кондорсе), але програє в результаті.
• Також ця система вразлива до стратегічного голосування. Якщо двоє перших виборців вирішать: Та ну його те олів'є, ми будемо голосувати за шубу, щоб тільки не холодець. Тобто відхилення від щирого голосування (за перший вибір) дає їм більший виграш.
• Ну і звичайно можлива ситуація, коли невелика група вибирає переможця, оскільки інші поділені між конкуруючими кандидатами.

Відносна більшість з двома турами

Логічно запитати, а давайте якось «підкрутимо» цю відносну більшість щоб було краще. Наприклад, візьмемо відносну більшість з другим туром — дуже знайома нам система. Але вона теж вразлива до великої кількості парадоксів і маніпуляцій (тут опишемо лише декілька).

Приклад. Вибори на острові Скарбів.

Доктор Лівсі є переможцем Кондорсе. Дійсно:

Доктор Лівсі — Джим (9 : 8)

Доктор Лівс — Капітан Смолет (9 : 8)

Але в другий тур проходять (рахуємо перші місця) Джим і Капітан Смолет (по 6).

В другому турі розгромно перемагає Капітан (11 : 6) (Парадокс переможця за Кондорсе)

А от якщо Джим зніме кандидатуру, то все вирішиться в першому турі.

Доктор Лівсі — Капітан Смолет (9 : 8). (Залежність від нерелевантних альтернатив)

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

Ну тепер в другий тур проходять вже Доктор Лівсі і Капітан Смолет, тому Доктор Лівсі стає переможцем. Ще раз: ми додали голосів переможцю, а він в результаті програв!

Отже, додамо у перелік бажаних властивостей

• властивість 2. Монотонність (М).
• властивість 3. Переможець за Кондорсе (ПК). Якщо є єдиний переможець попарних голосувань, то він має бути переможцем.
• властивість 4. Незалежність від нерелевантних альтернатив (ННА)

Парування з вибуванням.

Парування з вибуванням застосовується, наприклад, в американському конгресі при розгляді законопроектів. Існує чіткий порядок, який визначає як проходить законопроект. Для такої системи можливий парадокс другорядного переможця — це ситуація, коли результатом голосування є альтернатива, яку всі вважають гіршою за іншу. Звучить дивно? Припустимо, що троє учасників зібрались випити і вибирають між чотирма варіантами. Їх відношення до них задається так:

Перший: горілка < пиво < коньяк < вино

(тобто вино на першому місці, коньяк на другому і т.д.)

Другий: пиво < коньяк < вино < горілка

Третій: коньяк < вино < горілка < пиво

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

1. Спочатку вони голосують вино чи горілка. Двоє вважають, що горілка краще за вино, тому вино відпадає.
2. Далі горілку голосують проти пива. Двоє вважають, що пиво краще за горілку, тому залишається пиво.
3. Нарешті пиво проти коньяку. Двоє вважають, що коньяк краще, отже всі йдуть пити коньяк.

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

Властивість яка порушується тут називається Парето оптимальність. Це п'ята властивість яку б ми хотіли бачити в ідеальній системі голосування.

(далі будуть інші, більш складні системи голосування)

UPD. частина два

частина три