Теорія ігор і системи голосування. Частина друга: Кондорсе проти Борда

Abstract
Про наукове суперництво видатних вчених, парадокс Кондорсе і його систему голосування. Про систему Борда, вченого, який придумав метр і як його виміряти та маніпуляції. Про систему голосування, яка використовується зараз в Linux та Wikipedia і скандал в Кірібаті.

«Я збирався сказати, — ображено мовив Додо, — що найкраща штука, щоб висохнути, це Партійні Перегони ... Додо усе влаштував… Спершу він намітив маршрут — таке собі коло («Насправді форма не має значення», — запевнив Додо), а тоді розташував усе товариство тут і там уздовж дистанції…. кожен починав бігти, коли йому спадало на думку, й так само сходив з дистанції, коли йому було до вподоби … після півгодинки біганини, коли всі вже майже повністю висохли, Додо несподівано вигукнув:— Перегони закінчено! Усі скупчилися довкола нього, відсапуючись та запитуючи: «Ну, так хто ж переміг?». Щоб відповісти на це запитання, Додо був змушений поринути в тяжкі роздуми й довгенько стояв, притиснувши пальця до чола … Перегодом Додо сказав:— УСІ перемогли, й усі мають отримати призи."
Аліса в Країні Див

У попередній публікації ми закінчили на ідеях, які важливо підкреслити:

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

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

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

Система Кондорсе

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

Марі Жан Антуан Ніколя де Каріта, маркіз де Кондорсе

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

Згадаємо приклад про напої з попередньої статті (без останнього виборця).

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

1. чай — кава;
2. чай — сік;
3. сік — кава.

Тепер кожну пару потрібно проголосувати.

Чай вище за каву у 2 виборців і нижче у 3, тобто рахунок у парі чай — кава 3:2.

Чай вище за сік у 3 виборців і нижче у 2, тобто рахунок у парі чай — сік 3:2.

Сік вище за каву у 2 виборців і нижче у 3, тобто рахунок у парі сік — кава 2:3.

В результаті чай перемагає в усіх парах, тому він має бути оголошеним переможцем. Це суть ідеї Кондорсе. Цей метод, як це часто буває, не був придуманий Кондорсе, він описаний ще в трудах Миколи Кузанського (1401 — 1464) в контексті виборів германських монархів. Заслуга Кондорсе в іншому: він сформулював проблему, яка отримала назву парадокс Кондорсе.

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

Нехай є рада (міста, села, області), яка ухвалює рішення щодо розподілу коштів. І склад ради такий: Ліва партія 3 місця, Центристи 4 місця, Права партія 5 місць. Є три можливих напрямки фінансування: здоров'я, безпека та освіта. У кожної партії є своє бачення важливості цих напрямків:

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

Очевидно, якщо поставити всі альтернативи на одне голосування (відносна більшість), то переможе безпека (5 голосів), в той же час 7 депутатів (більше половини) вважають, що здоров'я важливіше за безпеку, просто вони не можуть дійти згоди, фінансувати освіту чи здоров'я.

Застосуємо ідею Кондорсе, для цього утворимо пари.

Безпека перемагає освіту (9 : 3), і потім програє здоров'ю (7 : 5).

Освіта перемагає здоров'я (8 : 4).

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

здоров'я перемагає безпеку

безпека перемагає освіту

освіта перемагає здоров'я

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

Нагадую, що транзитивність — це властивість відношення (або системи уподобань), така, що якщо А краще за Б, а Б краще за В, то А краще за В.

Наприклад, відношення "більше" для дійсних чисел транзитивне. А відношення підлеглості у феодалізмі не завжди (оце саме "васал мого васала — не мій васал").

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

Реальні випадки парадоксу Кондорсе

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

Процедура ухвалення нового закону в американському Конгресі складна і формалізована. Один або декілька законів об'єднуються в білль, який передається на розгляд відповідному комітету. Далі депутати можуть подавати поправки до білля, поправки до існуючих поправок, альтернативний білль і поправки до альтернативного білля. Таким чином, протягом процедури розгляду в залі можливо ШІСТЬ різних потенційних законів: статус кво (те що зараз), рекомендований комітетом білль, білль з поправкою, білль з поправленою поправкою, альтернативний білль, альтернативний білль з поправкою.

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

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

1. Білль, що пропонується, перемагає статус кво
2. Поправка перемагає оригінальний білль
3. Поправка програє статусу кво

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

Одна з найбільш яскравих це Поправка Пауела (1956 рік). Президент Ейзенхауер зібрав 1.5 мільйона доларів (на той час значні кошти) на підтримку місцевих шкіл по усій країні. Вважалося, що білль має пройти, як ніж крізь масло: хто буде голосувати проти допомоги школам? Але Пауелл запропонував поправку, яка відсікала школи з сегрегацією від допомоги. Мотивація була наступна: південні штати не хочуть припиняти свою практику, отже федеральні кошти не повинні це підтримувати. Пауелл сам був афро-американцем і демократом. Він очолював комітет з освіти і висував цю поправку до всіх законів, що стосувались коштів федерального бюджету.

Адам Клейтон Пауелл молодший

Його поправка розколола конгрес. Частина республіканців і північних демократів голосували за неї (і цього вистачило для того, щоб вона вибила оригінальний білль), всі південні демократи були проти. Але потім білль з поправкою не отримав підтримки проти статус кво і загинув.

Система Борда

Найпринциповіший науковий суперник Кондорсе, Жан-Шарль шевалье де Борда був класичним вченим того часу: інженер, фізик, математик, геодезист і морський офіцер. Можливо, вершиною його діяльності було головування в комісії, де зібрались такі знаменитості: Лавуазьє, Кондорсе, Лаплас, Монж, Кулон та Лагранж. Мета комісії була стандартизувати систему вимірів. І саме Борда запропонував схему виміру і назву "метр". Взагалі Борда був більш інженерно-орієнтованим, тому він хотів привнести у вибори точність чисельних методів.

Жан-Шарль шевалье де Борда

Проблема, яку хотів розв'язати Борда, називається розщеплення голосів, тобто ситуація з прикладу попередньої статті:

Ми вже знаємо, що переможець за системою відносної більшості — холодець (3 голоси). Це сталось тому, що більша група виборців (4 голоса) поділена (розщеплена) між іншими альтернативами порівну.

Система голосування, яку запропонував Борда, є ефективним замінником голосування пар і полягає в обчисленні "рейтингу" альтернатив. Кожен виборець створює перелік: яка альтернатива на першому місці, яка на другому і т.д. Якщо у нас є m альтернатив, то за кожне перше місце альтернатива отримує m — 1 балів. За кожне друге m — 2 бал і т.д. За кожне останнє — 0 балів.

За системою Борда:

олів'є отримує 2 перших місця, 2 других місця і 3 третіх місця, тобто 2*2 + 2 = 6 балів.

шуба отримує 2 перших місця, 5 других місць, тобто 2*2 + 5 = 9 балів.

холодець отримує 3 перших місця, 5 останніх місць, тобто 3*2 = 6 балів.

Перемагає шуба (і вона є також переможцем за Кондорсе для цього прикладу).

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

Як і система Кондорсе, система Борда була придумана до нього. Є відомості, що вона застосовувалась в римському Сенаті в 2 ст. н.е. Пізніше ця система і система Кондорсе обговорювались в трактаті каталонського вченого Рамона Лулського "Мистецтво виборів" (1299).

Однак у цієї системи був суттєвий недолік, який Борда не помітив. Давайте розглянемо конкретний приклад. Припустимо, вибирається галузь для позачергового додаткового фінансування і депутати формують список пріоритетів.

За системою Борда результат наступний:

1. Армія 3*3 + 2*2 + 2 = 15 балів (3 перших місця, 2 других місця, 2 третіх місця)
2. Медицина 2*3 + 2*2 = 10 балів (2 перших місця, 2 других місця)
3. Культура 2*3 + 3 = 9 балів (2 перших місця, 3 третіх місця)
4. Наука 3*2 + 2 = 8 балів (3 других місця, 2 третіх місця)

Також можна зазначити, що армія — переможець за відносною більшістю. Переможця за Кондорсе немає.

Але тепер припустимо, що внаслідок якихось подій потреба в додатковому фінансуванні армії пропадає і вона зникає з цього переліку. Логічно припустити, що перше місце перейде до медицини? Давайте розберемось:

Медицина: два перших місця + два других місця + три третіх місця = 6 балів (для трьох альтернатив перше місце дає 2 бали)

Культура: два перших місця + три других місця + два третіх місця = 7 балів

Наука: три перших місця + два других місця + два третіх місця = 8 балів

І наука перемагає, хоча вона і була остання в попередньому раунді! (це мрії звичайно).

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

Тут всі не люблять холодець, у нього 0 балів. За системою Борда:

олів'є отримує 4*2 + 3 = 11.

шуба отримує 3*2 + 4 = 10.

Тобто олів'є перемагає, якщо все чесно. Але припустимо, що 3 останніх виборці, знаючи уподобання інших, поставили олів'є на останнє місце. В цьому разі:

олів'є отримує 4*2 = 8.

шуба отримує 3*2 + 4 = 10.

холодець отримує 3.

Перемагає шуба, і це настільки просто, що де б не застосовували цю систему, люди починали поводити себе цілком однотипно — топити найбільших конкурентів. Це сталося і на виборах нових академіків у Франції. Коли Борда повідомили про цю особливість, він вигукнув свою знамениту фразу: "Моя система призначена лише для чесних!". У 1800 році в Академію Наук завітав перший консул Наполеон Бонапарт. Йому вистачило 5 хвилин на ознайомлення і перше ж його рішення заміняло систему Борда на абсолютну більшість (якщо ніхто не набрав 50%+, місце залишалось незайняте).

Забуття і нове життя систем Борда і Кондорсе

Кондорсе загинув в результаті революції, яку він наближав і вітав. Його проект конституції з гарантією базових громадянських прав не сподобався Робесп'єру. Кондорсе також протестував проти страти королівської сім'ї. Таке якобинці не пробачили, Кондорсе був оголошений ворогом, переховувався в лісах. Врешті-решт, його спіймали і кинули у в'язницю, де він помер. Усе, що залишилось після, це книга, у якій система Кондорсе виявилася замкненою надовго.

Борда пережив терор і помер у віці 65 років в Парижі. Але його роботи з систем голосування теж були забуті.

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

Однак, декілька десятиліть тому ситуація змінилася. Зникла одна з перепон на шляху використання системи Кондорсе — витрати часу на процедури парування і підрахунок, які тепер можливо автоматизувати. Також утворилися добровільні об'єднання програмістів, які створювали вільні програмні продукти. Один з важливих елементів таких комьюніті — врахування голосу кожного учасника. У 2000 році комьюніті Debian project вирішило провести дослідження для визначення найкращої системи для внутрішнього голосування. Після трьох років Debian почав використовувати модифіковану систему Кондорсе, назва якої радує душу кожного кодера : cloneproof Schwartz sequential dropping, коротко CSSD або метод Шульце (там є перелік всіх середовищ, які використовують цей метод. І цей перелік вражає, зокрема там Debian, Ubuntu, TopCoder, Wikipedia (на деяких мовах), 11 піратських партій різних країн).

Метод Шульце працює, як Кондорсе за відсутності циклів. За наявності циклів він намагається відкинути "слабші" зв'язки. Урешті-решт, цикл розривається і залишається один переможець.

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

Система Борда принята офіційно у двох країнах: Науру і Кірібаті. Вона працює там з 70хх років і відмітилась декількома скандалами. Зокрема, на виборах 1991 року представники правлячої партії поставили свого головного конкурента на останнє місце. Тепер у вчених є предмет дослідження, як поводяться виборці в цих умовах, на цю тему навіть серйозні статті пишуть (наприклад така робота пруф). І все таки система Борда не популярна. Останнім крупним вченим, який наразі захищає її є Дональд Саарі. Його аргументація по суті базується на тому, що складні соціальні відносини не можна зводити до системи попарних "дуелей". Крім того, система Кондорсе так само вразлива до маніпуляцій і парадоксів (хоча те, що маніпулювати системою Борда легше, це факт). Можливо з часом щось зміниться і заочна дуель Кондорсе і Борда продовжиться.

(далі буде про Ерроу і його теорему)

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

частина три