Який зробити наступний хід, якщо невідома гра?
Міст шпигунів.
Проблема узгодженої поведінки та ухвалення рішень великими колективами ключова для всієї історії людства. Якщо дивитись під цим кутом зору, то значні історичні зміни були наслідком розвитку або появи нового типу взаємодії між рядовими учасниками процесу. Делегування права ухвалення рішень (навіть і не добровільне) за ієрархією дозволила організувати великі імперії Сходу і Єгипту. Відповідним було і обгрунтування. Наприклад, світогляд персів уявляв світ ареною боротьби Добра і Зла, де цар на чолі бюрократії намагається привнести порядок та наблизити перемогу, тому невиконання рішення старшого за посадою було, взагалі кажучи, військовим злочином. Власне якість рішення визначалась місцем в ієрархії - цар не помиляється.
І мабуть найбільш відомими, хто вибився з цієї протореної колії, були греки. Сильно спрощуючи, ідея греків полягала в наступному: щоб ухвалити найкраще (оптимальне) рішення потрібно спочатку почути всі можливі, а потім проголосувати. Те рішення, яке обере більшість - найкраще. Інші народи правда казали, що грекам просто подобається триндіти в агорі замість того щоб боротись за перемогу Добра у вселенський битві, але грекам було все одно, результат на табло - персів вони перемогли.
Так чи інакше, саме греки (і потім римляни) прославили виборчі процедури, на сьогодні можна констатувати, що демократія хоч і погана штука, але краще поки що немає. Далі мова буде йти про виборчі системи, але з математичної точки зору. Виявляється, що, в певній мірі, повторюється ситуація з попередньої статті про американську конституцію, коли політики сформулювали умови виходячи з певних абстрактних понять про справедливість, загальність і того, як має бути влаштований конституційний устрій. А потім (після акуратної математичної формалізації) виявилось, що ці умови неможливо виконати (точно як у анекдоті про розумне, добре і вічне).
Закінчуючи передмову зазначу, що після того, як системи голосування увійшли в життя розвинутих країн важливим питанням стало можливість маніпуляцій або впливу на процес голосування з метою отримання бажаного результату. Така задача може формулюватись в термінах теорії ігор і це обумовлює назву.
Сьогодні покращені засоби доставки інформації пронизують кожну секунду існування де б ви не знаходились, і скоро кожна новина, подія та загалом будь-яка активність буде спробою маніпуляції і впливу на свідомість. Особливо це стосується сильних емоцій, бо так інформація запам’ятовується найкраще. Отже є сенс спокійно почати ab ovo.
Коли ми говоримо про теорію ігор у застосуванні до голосування, природно виникає питання: А в чому ж тут гра? Відповісти на це питання важливо для подальшої побудови моделі, яка (звичайно) буде спрощенням реального життя, і висновків, які можна зробити на її основі.
Для визначення гри необхідно задати три речі: гравців, їх стратегії і їх виграші. На роль гравців виникає дві можливості: кандидати та виборці. Ідеальною була б модель де були б і ті і інші, але розв’язати таку модель буде вже неможливо. Модель з кандидатами-гравцями пов’язана з теоремою про медіанного виборця (там виборці вважаються розподіленими вздовж певної осі, наприклад, праві - ліві). Інший підхід полягає у розгляді системи з точки зору виборців. Кандидати тут вважаються фіксованими альтернативами, які вибирають гравці. Їх вплив - це їх голос, поданий за певного кандидата (або ранжування всіх кандидатів). Результат буде залежати від обраної системи голосування, а виграш гравця це перемога кандидата який йому більше подобається.
Приклад. Шестеро виборців (їм відповідають стовпці) мають наступні уподобання щодо напоїв:
виборці | ||||||
1 | 2 | 3 | 4 | 5 | 6 | |
1 | чай | кава | чай | кава | сік | сік |
2 | кава | чай | сік | сік | кава | чай |
3 | сік | сік | кава | чай | чай | кава |
NB Тут число - порядковий номер виборця. В усіх інших прикладах - кількість виборців.
Як їм вибрати один напій? Або, більш загально, як агрегувати уподобання групи людей? В ідеалі ми шукаємо функцію, яка відображає всі уподобання в один вектор-результат, наприклад:
сік |
чай |
кава |
Якщо ми говоримо про вибори, то в даному конкретному прикладі перемагає один варіант, який стоїть на першому місці - тобто сік. Якщо ж нас цікавить весь вектор, то в загальному формулюванні така функція називається функцією соціального вибору. В цьому випадку виборці 5 і 6 найбільш задоволені - виграла альтернатива, яка є їх першим вибором. Виборці 3 і 4 помірно задоволені - виграв їх другий вибір. Виборці 1 і 2 зовсім незадоволені. Будемо вимірювати задоволеність-незадоволеність цілими числами, наприклад виграші в даній ситуації будуть такі
1 і 2 - 0 балів
4 і 3 - 1 бал
6 і 5 - 2 бали
Отже, виникає природна постановка гри. Гравці - виборці, дії - вибір кандидата у бюлетені, виграш - місце переможця в особистих уподобаннях. Чим вище, тим краще. І тут виникає дві проблеми:
NB Далі ми розглянемо “ідеальний світ” де виборці голосують щиро, тобто вибирають свій перший можливий варіант. Це зроблено з метою продемонструвати принципові можливості систем голосування і поведінки виборців.
Випадок двох можливих альтернатив найпростіший.
Нагадаємо, що Абсолютна більшість це правило, за яким перемагає той, хто набрав більше половини перших місць у уподобаннях виборців.
І результат, який був отриманий в 1952 році Кеннетом Меєм звучить так (у спрощеній формі):
Для ситуації двох альтернатив абсолютна більшість є єдиною системою, яка забезпечує наступні властивості:
Якщо кількість виборців непарна, то вона завжди забезпечує переможця. З практичної точки зору для великої кількості виборців вона забезпечує переможця і для парної кількості, оскільки точна рівність голосів має ймовірність дуже близьку до 0. В принципі правило абсолютної більшості використовували дуже давно, грецька демократія загалом була побудована на цьому правилі (з певними обмеженнями).
Теорема дала надію що такий самий трюк можна провернути і для більшої кількості альтернатив (тобто сформулювати систему властивостей і виділити виборчі процедури, які їм задовольняють). Але виявилось, що для трьох і більше альтернатив метод абсолютної більшості просто далеко не завжди визначає переможця. Це явно не те, що б ми хотіли від виборчої системи. Отже, властивість 1: Виборча система має завжди визначати переможця. Найближча до абсолютної більшості (для 3 і більше альтернатив) є відносна більшість.
Відносна більшість це правило, за яким перемагає той, хто набрав більшість перших місць у уподобаннях виборців. Відносна більшість теж практично завжди визначає переможця. Чому ж не використовувати її?
Розглянемо новорічний приклад.
виборці (кількість) | |||
2 | 2 | 3 | |
1 | олів’є | шуба | холодець |
2 | шуба | олів’є | шуба |
3 | холодець | холодець | олів’є |
Переможця за абсолютною більшістю не існує. За системою відносної більшості перемагає холодець.
Але виявляється, що ця система вразлива до численних парадоксів:
Логічно запитати, а давайте якось "підкрутимо" цю відносну більшість щоб було краще. Наприклад, візьмемо відносну більшість з другим туром - дуже знайома нам система. Але вона теж вразлива до великої кількості парадоксів і маніпуляцій (тут опишемо лише декілька).
Приклад. Вибори на острові Скарбів.
виборці (кількість) | ||||||
3 | 2 | 4 | 2 | 4 | 2 | |
1 | Доктор Лівсі | Доктор Лівсі | Капітан Смолет | Капітан Смолет | Джим | Джим |
2 | Капітан Смолет | Капітан Смолет | Доктор Лівсі | Джим | Доктор Лівсі | Капітан Смолет |
3 | Джим | Джим | Джим | Доктор Лівсі | Капітан Смолет | Доктор Лівсі |
Доктор Лівсі є переможцем Кондорсе. Дійсно:
Доктор Лівсі - Джим (9 : 8)
Доктор Лівс - Капітан Смолет (9 : 8)
Але в другий тур проходять (рахуємо перші місця) Джим і Капітан Смолет (по 6).
В другому турі розгромно перемагає Капітан (11 : 6) (Парадокс переможця за Кондорсе)
А от якщо Джим зніме кандидатуру, то все вирішиться в першому турі.
Доктор Лівсі - Капітан Смолет (9 : 8). (Залежність від нерелевантних альтернатив)
Найбільш вражає те, що ця система не є монотонною. Припустимо, що двоє останніх виборців вирішують збільшити свою підтримку Капітану і ставлять його на перше місце. Як зміниться результат?
Ну тепер в другий тур проходять вже Доктор Лівсі і Капітан Смолет, тому Доктор Лівсі стає переможцем. Ще раз: ми додали голосів переможцю, а він в результаті програв!
Отже, додамо у перелік бажаних властивостей
Парування з вибуванням застосовується, наприклад, в американському конгресі при розгляді законопроектів. Існує чіткий порядок, який визначає як проходить законопроект. Для такої системи можливий парадокс другорядного переможця - це ситуація, коли результатом голосування є альтернатива, яку всі вважають гіршою за іншу. Звучить дивно? Припустимо, що троє учасників зібрались випити і вибирають між чотирма варіантами. Їх відношення до них задається так:
Перший: горілка < пиво < коньяк < вино
(тобто вино на першому місці, коньяк на другому і т.д.)
Другий: пиво < коньяк < вино < горілка
Третій: коньяк < вино < горілка < пиво
І треба швидко знайти прийнятний для всіх варіант. Вони вирішують голосувати альтернативи попарно, відкидаючи ті, які набрали меншість голосів. Кожен голосує щиро, у відповідності до свого відношення.
Але чекайте, ВСІ троє насправді думають, що вино краще за коньяк! Виходить, що запропонована система голосування не змогла вибрати альтернативу, яку всі б хотіли більше ніж отриманий результат.
Властивість яка порушується тут називається Парето оптимальність. Це п’ята властивість яку б ми хотіли бачити в ідеальній системі голосування.
(далі будуть інші, більш складні системи голосування)
UPD. частина два
Коментарі доступні тільки зареєстрованим користувачам
вхід / реєстрація