Голосуємо методом Шульце, або Як працює онлайн-сервіс для колективних рішень

Привіт, мене звати Денис Потапов. Я сіньйор Python-девелопер у Virtasant, але сьогодні хочу розповісти про свій пет-проєкт — онлайн-опитування glagoly.com. Ми вже деякий час використовуємо сервіс у своїй невеликій волонтерській спільноті — і на мій смак, працює він краще звичних опитувань у Telegram.

Стаття нижче буде передовсім цікава тим, що я познайомлю вас із голосуванням методом Шульце (Schulze method, вікі, wiki), і спробую переконати в його перевагах. Сподіваюсь, цей сервіс допоможе вам зрівняти гострі організаційні кути як в роботі, так і у волонтерстві, та приймати колективні рішення менш стресово.

Які є голосування

Тож, якщо для планування зустрічей ви використовуєте doodle.com або голосування у Telegram, спробуйте використати новий підхід. Ключова відмінність цього інструменту — він базується на методі Шульце:

• Голосування схваленням (Approval voting, wiki) — коли кожен ставить декілька галочок навпроти запропонованих варіантів, і переможець обирається більшістю голосів (галочок).
• За методом Шульце кожен ставить число навпроти запропонованих варіантів. Результати визначаються за кількістю переваг. Тобто скільки людей поставили одному варіанту вищу оцінку, ніж іншому. Це — спрощений опис, але нижче буде приклад розрахунку.

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

Приклад

Отже, ви плануєте зустріч та обираєте день. На зустріч хочуть прийти 9 людей:

• двоє прихильників п’ятниці. Кожен з них вважає, що п’ятниця — кращий варіант, якщо ні — то їм без різниці, субота чи неділя;
• четверо прихильників неділі, що обирають неділю, та їм все одно до п’ятниці і суботи;
• троє прихильників суботи, вони обирають суботу, але якщо ні — то краще вже п’ятниця, аніж неділя.

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

Голосування схваленням

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

Голосування

Прихильникам п’ятниці проголосувати просто: вони поставлять галочку за п’ятницю і проігнорують суботу і неділю:

В таблицю результатів піде: 2 галочки за п’ятницю і 0 за суботу і неділю.

Аналогічно проголосують прихильники неділі:

В таблицю результатів піде: 4 галочки за неділю, і 0 за п’ятницю і суботу.

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

В таблицю результатів піде: 3 галочки за суботу, і 0 за неділю. Що вони поставлять навпроти п’ятниці буде залежати не від вподобань, а від зовнішніх факторів:

• doodle дозволяє ставити проміжну галочку (if-need-be). Як її рахувати залежить від організатора опитування;
• там де поставити проміжну галочку неможливо, кількість галочок буде залежати від внутрішнього відчуття учасників.

Підрахунок результатів

Таблиця результатів буде виглядати наступним чином:

Простим підрахунком більшості галочок перемагає неділя. Хоча остаточні результати будуть різнитися:

• Якщо учасники поставили проміжні галочки, то результати залежать від організатора. Якщо він чи вона вважає, що 3 проміжні галочки більше ніж різниця в 2 звичайні галочки, то перемагає п’ятниця.
• Скоріше всього прихильники суботи вдадуться до тактичного голосування (wiki). До того як проголосувати, вони подивляться, чи влаштовують їх результати, і в залежності від цього, поставлять чи знімуть галочку навпроти п’ятниці (їх запасний варіант).

Метод Шульце

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

Голосування

Для прихильників п’ятниці в голосуванні мало що зміниться в порівнянні з голосуванням схваленням. Вони поставлять якесь число, наприклад +3, біля п’ятниці, і проігнорують суботу і неділю:

Конкретні числа тут не важливі (можна було б обрати +1 та −1). Важливо, що вони оцінюють п’ятницю вище ніж суботу і неділю, та однаково оцінюють два останні варіанти.

Аналогічно проголосують прихильники неділі:

Для прихильників суботи, процесс голосування спроститься. Адже вони точно можут описати свій вибір. Вони поставлять більше число для суботи, менше для п’ятниці і проігнорують неділю.

Знову ж таки, числа можуть бути довільними і навіть різними для кожного учасника. Головне те, що у кожному голосі субота краще п’ятниці, а п’ятниця краще неділі.

Підрахунок результатів

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

Число біля стрілки показує, скільки учасників вважає, що один варіант краще іншого. Наприклад, стрілка від п’ятниці до суботи показує — 2 особи проголосували, що п’ятниця краще ніж субота (прихильники п’ятниці). А зворотна стрілка (виділена жирним) вказує, що 3 людей вважають, що субота краще п’ятниці.

На першому кроці залишимо лише ребра-переможці. Тобто з двох ребер А→Б і Б→А залишимо те, де прихильників більше:

І ми тут бачимо, що простим підрахунком визначити переможця неможливо. В нас є цикл уподобань, п’ятниця краще неділі, неділя краще суботи, а субота краще п’ятниці. Це приклад парадоксу Кондорсе (вікі, wiki), відповідно до якого групові вподобання можуть містити цикли, навіть коли вподобання кожно учасника, очевидно, циклів не містять.

Метод Шульце вирішує проблему пошуку переможця рахуючи «силу шляху». Сила шляху — сила найслабшої ланки, від варіанту А до варіанту Б. Наприклад, визначимо силу шляху від п’ятниці до суботи і навпаки:

• В нас один шлях від п’ятниці до суботи — через неділю. І його сила, найменше число з двох ребер: від п’ятниці до неділі (5) та від неділі до суботи (4).
• Від суботи до п’ятниці в нас теж всього один шлях і його сила відповідає силі ланки (3).

В нашому простому випадку (по одному шляху від кожної вершини до кожної) легко розрахувати всі сили шляхів:

Переможцем буде п’ятниця, варіант, що має сильніші шляхи до всіх інших варіантів. В свої статті Шульце (arxiv.org), доводить, що такий варіант буде знайдений (якщо це взагалі можливо).

Висновки

Навіть в такому простому випадку, метод Шульце має кілька переваг.

• Прихильникам суботи легше проголосувати, адже вони можуть точно передати свої вподобання. Для інших учасників процес голосування суттєво не змінюється, просто замість галочки вони ставлять +1.
• Результати голосування однозначні і залежать лише від уподобань учасників. І не залежать від способу підрахунку голосів організатором голосування.

P.S. Верифікація

Оскільки вручну результати голосування перевірити важко, то код підрахунку переможців у глаголі — відкритий. А юніт-тести (github) взяті з прикладів у оригінальній статті Шульце.