Теорія ігор і системи голосування. Частина третя: Теорема Ерроу — неможливість чи можливість?

Коли ціле — більше, ніж сума частин

Відблиск неможливості

Кеннет Ерроу з дитинства любив читати. Коли його карали за щось і за американською традицією того часу зачиняли в кімнаті, він спокійно брав з полички том енциклопедії і поринав у читання. Тому з часом йому придумали інше покарання: виганяли з дому гратися на вулиці. Ерроу був студентом Оскара Моргенштерна (одного з батьків теорії ігор), досліджував економіку. Але найважливішим моментом його життя стало отримання роботи у RAND. (RAND — науково-дослідний відділ корпорації Douglas Aircraft, який вербував на роботу найперспективніших вчених того часу. Така собі перша в світі спроба зробити фабрику досліджень).

Там працювали Нейман і Неш, Айзекс і Белман. Там народився системний аналіз, лінійне і динамічне програмування, метод Монте-Карло та інші. Цікаво, що більша частина отриманих досліджень була «побічним ефектом», який виникав від співробітництва і спілкування такої кількості яскравих науковців.

Ерроу взяли на позицію статистика-математика для дослідження розташування американських підводних човнів з ядерними ракетами, але про цю роботу нічого особливо невідомо. Одного разу Олаф Хелмер (логік і філософ) висловив у розмові з Ерроу таку проблему:

«Сполучені Штати Америки — це абстракція. А от люди, виборці — це реальність, їх цінності впливають на вибори і рішення. Але яким чином цінності окремих особистостей формують цінності країни?». Ерроу відповів: «Та це досить просто, я читав нещодавно щось на цю тему, думаю, що можна застосувати певні механізми агрегації». Хелмер запропонував йому написати щось на цю тему.

Коли Кеннет сів за роботу, він зрозумів, що не все так просто. Поступово робота захопила його, і в 1948 році він нарешті презентував свій результат. Пізніше цей результат став основою його дисертаційної роботи, книги, яка стала найцитованішою роботою за все його життя, і однією з причин присудження нобелівки з економіки. Ідея була проста: сформулювати декілька очевидних математичних властивостей систем голосування, і знайти ті системи, які їм задовільняють. Результат був несподіваним: для пари дуже простих властивостей єдина система, яка підходила, була диктатура. Коли Ерроу додав властивість «і щоб не диктатура», жодної системи не залишилося.

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

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

Так нерідко зустрічаються коментарі в дусі: «Ідеальна (або справедлива) система голосування не існує» або «Теорема Ерроу прирікає нас на диктатуру» і навіть «Демократія неможлива, і це довів Ерроу».

Давайте розбиратися, що ж доведено.

Теорема Ерроу

Перед формулюванням теореми важливо визначити припущення і їх значення.

1. Кожен виборець має повні транзитивні уподобання. Повнота означає, що виборець має визначити відношення до всіх альтернатив. Транзитивність означає, що якщо А краще за Б, а Б краще за В, то обов'язково А краще за В.
2. Вимагається транзитивність результату виборів. По суті, це означає, що виборча система повертає упорядкований список альтернатив, вершина якого — переможець. Таким чином, забороняються цикли в результуючому векторі і завжди є переможець.

Ці два стартові припущення цілком зрозумілі. Далі йдуть ще дві властивості.

1. Парето. Якщо ВСІ виборці вважають альтернативу А кращою за альтернативу Б, то в результаті альтернатива А має бути краще за альтернативу Б. Зокрема, якщо всі вважають, що кандидат П краще всіх інших, то він і має перемогти.
2. Незалежність від нерелевантних альтернатив (ННА). Це мабуть найбільш важлива властивість. Формальне визначення таке: співвідношення між А та Б в результуючому векторі має визначатись тільки відношенням виборців до А та Б, наявність чи відсутність інших альтернатив не має на це впливати. По суті питання ілюстрацією є історія (не знаю, наскільки реальна) про філософа Сідні Моргенбессера, відомого своєю дотепністю, якому офіціант запропонував на вибір десерт: яблучний або чорничний пиріг. Моргенбессер вибрав яблучний. Через декілька хвилин офіціант підійшов знову і сказав: «Вибачте, я не помітив, що у нас є ще вишневий пиріг». На що філософ незворушно відповів: «У цьому разі я буду чорничний». (більше історій тут) Очевидно, що вишневий пиріг є нерелевантним для вибору між яблучним і чорничним, але його наявність спричинила зміну вибору. Ерроу вимагає у системи виборів бути незалежною від таких впливів.

Нарешті ми можемо сформулювати велику і жахливу її.

Теорема Ерроу. Для ситуації трьох і більше альтернатив єдина система голосування, що задовольняє властивостям Парето та Незалежності від нерелевантних альтернатив є диктатура.

Ця теорема дійсно «вибухнула» в 50-і роки. Нечасто ціла область науки виникає від одного негативного результату. Чому негативного? Бо Ерроу додав ще одну властивість, яку б ми хотіли від результату «і щоб була не диктатура», тоді виходить, що жодна система не підходить. Результатом стала поширена думка, сформульована Самуельсоном (також нобеліатом з економіки): «Ерроу показав раз і назавжди, що ідеальна система голосування неможлива».

Але диявол в деталях, як і завжди.

Той, хто в деталях

По-перше, теорема Ерроу стосується лише ситуацій, коли альтернатив більше двох. Другий тур президентських виборів, голосування законів (де альтернативи — «за» і «проти»), голосування за умов двопартійної системи (коли всі інші — малопопулярні) не потрапляє під дію цієї теореми.

По-друге, диктатура за Ерроу — це не стариган у військовій формі а-ля Зімбабве. Тут швидше диктатура в класично-римському стилі: коли все погано, то призначаємо диктатора. Як він скаже, так і буде. Тобто диктатура в цій теоремі означає, що вибирається один виборець, уподобання якого і дорівнюють функції соціального вибору. Цікаво, що диктатура в цьому розуміння є цілком «законним» способом визначення переможця. Дійсно:

1. Вона завжди дає результат і цей результат завжди транзитивний.
2. Виконується властивість Парето. Є такий жарт про Радянський союз з американської книжки про вибори: «Якщо всі (з диктатором Сталіним включно) голосують, щоб народ отримав безкоштовну горілку, то всі отримують горілку. Якщо всі, крім Сталіна, хочуть безкоштовну горілку, то це вже зовсім інша історія.» Але, як видно з цього жарту, Парето для диктатури виконується.
3. ННА також виконується для диктатури, тому що по суті колективний вибір зводиться до індивідуального. А індивідуальні уподобання є транзитивними.

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

По-четверте, Ерроу ніяк не враховує можливість маніпуляцій або стратегічного голосування. У його теоремі вважається, що виборці голосують щиро.

Нарешті головний результат теореми можна сформулювати так: будь-яка існуюча система, яка не диктатура (і задовольняє вхідним визначенням), ДЛЯ ЯКОГОСЬ ВИПАДКУ не є Парето або ННА. Але ж це не означає завжди, в цьому і є відмінність математики від життя. Якщо ми зрозуміємо, що іноді (наприклад раз на 100 років) у нас буде порушуватись одна з властивостей, можливо, це не так і погано? Наприклад, одне дослідження 1992 року показало, що з 14270 трійок кандидатів тільки 71 створили цикли. Тобто, груба ймовірність парадоксу Кондорсе 1 з 200, не так вже й багато.

Отже, досить багато АЛЕ перед тим, як оголошувати про неможливість демократії. Тим не менше, сила теореми не стільки в тому, що вона визначила неможливість «ідеальної» системи голосування, а у виявленні ПРОБЛЕМИ соціального вибору. Група раціональних людей не може визначити правило агрегації їхніх уподобань навіть для досить «простих вимог» до цього правила. Я взяв «прості вимоги» у лапки, оскільки, на думку Дональда Саарі, ННА насправді є дуже суворим обмеженням. Але перед тим як описати його розуміння проблеми з теоремою Ерроу опишемо ще декілька результатів, що виникли після появи теореми про неможливість.

Терема Сена і інші парадоксальні результати

Теорема Сена

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

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

• Професор Копитко вирішує, що А краще за Б у конярстві;
• Обоє одноголосно вирішують, що Б краще за В взагалі;
• Професор Прополіс вирішує, що В краще за А в бджільництві.

Отримуємо не транзитивну систему уподобань А краще Б, Б краще В, В краще А…

Теорема Сена. Для системи з трьох і більше альтернатив не існує системи ухвалення рішень, яка б задовільняла властивостям Парето та Мінімального лібералізму.

Список Ліста

Філософ Крістофер Ліст запропонував ще один парадокс. Отже, приклад.

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

Приклад рішення щодо іспитів

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

Парадокс Анскомб

Елізабет Анскомб, — британський філософ, учениця Вітгенштейна. Парадокс Анскомб формулюється так:

Чи можливо, щоб більшість була у меншості по більшості питань? Виявляється — так, це можливо.

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

Виборці А, Б, В складають більшість, яка підтримує спільну позицію більшістю по всіх питаннях (2 проти 1), але які програють меншості Г і Д по всіх питаннях.

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

Суть проблеми

Виявляється, що всі ці парадокси є проявами старого знайомого — парадоксу Кондорсе, або циклу Кондорсе. Цикл, тобто ситуація, коли для групи виборців А краще за Б, Б краще за В і В краще за А є природним наслідком зростання розмірності. Це головна ідея Дональда Саарі, який досліджує це у своїх книгах. Справа в тому, що для двох альтернатив простір рішень є одномірним, точка відповідає рішенню більшості виборців. А якщо ми додамо ще одну пару, простір стає вже ЧОТИРИВИМІРНИМ, оскільки для коректного представлення відношення потрібно задати відношення виборців для кожної з чотирьох можливих пар.

Для того, щоб побороти це «прокляття розмірності» Ерроу і запропонував властивість ННА, яка фактично розриває зв'язки між парами і зводить задачу до ситуації, коли вони мають бути незалежні — кінцевий результат для кожної пари залежить лише від відношення до цієї пари. Але нічого не буває безкоштовно і за це довелось заплатити скороченням можливих функцій соціального вибору до однієї — диктатури. (Навіть найкращий з можливих Кондорсе-методів, метод Шульце, порушує ННА). Тобто, це типова ситуація, коли ціле (відношення групи виборців до альтернатив) є більш складним об'єктом ніж просто набір пар відношень.

Власне це і є інтерпретація теореми Ерроу від Саарі (і вона видається мені обгрунтованою). Ерроу намагався звести складне переплетення соціальних зв'язків до незалежної системи пар і отримав у результаті неможливість системи голосування, складнішої за диктатуру. Можливо не потрібно зводити все до системи незалежних пар? Можливо властивість ННА не має такого вже значення? І тоді ми можемо знайти інший варіант голосування, який би враховував «волю виборців»?

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

Інші варіанти

Чи можливі інші варіанти, які б обходили умови теореми Ерроу? Так, такі системи є:

• Approval voting. Голосування схвалення, коли кожен з виборців вибирає всіх кандидатів, які йому подобаються (і іноді також всіх, які не подобаються).
• Інтервальне голосування, коли виборці оцінюють альтернативу за шкалою. Так працює Амазон і IMDB.
• Зважене голосування, коли у одного виборця не один голос.

P.S. Всі імена кафедр, професорів, коней і бджіл, що зустрічаються у цій публікації є вигаданими. Будь-які збіги випадкові.

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

частина два