Маркіз з калькулятором
Ніколя де Кондорсе, математик і секретар Паризької академії наук, видав «Есей» про ймовірність рішень більшості за чотири роки до Французької революції. Звідти і назва парадоксу, і «переможець Кондорсе».
Оля, Марко й Ірина винаймають квартиру разом і обирають, що замовити на вечерю: піцу, суші чи вареники. Вирішують чесно, більшістю голосів, парами: дві страви змагаються, а переможниця виходить у фінал проти третьої. Ви головуєте й вирішуєте лише одне: які дві страви йдуть першими. Скількох із трьох страв ви можете зробити переможницею самим лише порядком голосувань?
Усі три. Більшість ставить піцу вище за суші, суші вище за вареники, а вареники вище за піцу. Це коло, як у грі «камінь, ножиці, папір»: кожна страва програє якійсь іншій. Хоч яку пару пустити першою, переможницю першого раунду б'є страва, яка чекала. Тож голова обирає переможця, коли вирішує, кого притримати до фіналу.
Цю задачу описав маркіз де Кондорсе 1785 року, коли шукав, як збори можуть ухвалювати рішення справедливо. Нижче вона в найменшому вигляді: троє людей і три варіанти.
Кожен упорядкував три страви від найбажанішої до найменш бажаної. Ці списки праворуч, і впродовж вечора вони не змінюються.
Голосують парами. Дві страви змагаються, і кожен голосує за ту, яка в його списку вище. Перемагає та, за яку щонайменше двоє з трьох. Переможниця виходить у фінал проти третьої страви, і переможниця фіналу їде до них на вечерю.
Ви не голосуєте й не вмовляєте. Ви лише оголошуєте, які дві страви змагаються першими, а яка чекає фіналу.
Скількох із трьох страв ви можете зробити переможницею, обираючи лише порядок голосувань?
Згори найбажаніша страва, знизу найменш бажана.
«Голосують чесно й більшістю. Від порядку нічого не залежить»
Більшість — найпростіше й найчесніше правило. Але чи завжди вона знає, чого хоче?
Оберіть відповідь. Вона зараховується одразу після кліку.
Передумати можна, але в статистику піде перший вибір.
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Спершу забудьте про порядок і проведіть усі три голосування один на один: піца проти суші, суші проти вареників, вареники проти піци. Хто виграє кожне?
Чи є страва, яка перемагає обидві інші один на один? Якщо є, порядок їй не страшний. А якщо немає?
Оберіть страву й спробуйте зробити її переможницею. Яка страва має вибути в першому раунді, щоб ваша вийшла сильнішою у фіналі? Коли ваша страва має голосувати?
Наступні раунди показують, як порядок голосувань обирає переможця: голосування, яке можна провести самому, свої компанії друзів, тисячі випадкових виборів і пояснення. Спершу відповісти в раунді 1 чи йти далі?
Ви обрали завжди показувати всі раунди.
Оберіть, яка страва чекає фіналу, і подивіться, хто за кого голосує. Спробуйте зробити переможницею кожну з трьох. А нижче складіть свою компанію з 3, 5 чи 7 людей і перевірте, чи є в неї коло.
Людей непарна кількість, тож у парі нічиїх не буває. Список кожного можна змінити.
Наша компанія підібрана навмисно. Як часто таке коло трапляється само собою? Комп'ютер дає кожному виборцеві випадковий список, усі шість порядків однаково ймовірні, і рахує, у якій частці виборів немає страви, що перемагає кожну іншу один на один. Саме тоді порядок голосувань може обирати переможця.
Після вашої відповіді тут з'явиться код симуляції, який можна запустити в себе.
Та сама симуляція коротко і без бібліотек. JavaScript запускається в консолі браузера (F12) або в Node, Python потребує лише стандартної бібліотеки.
// Кожен виборець ранжує m варіантів випадково й чесно. Як часто жоден варіант не перемагає всі інші в парних голосуваннях?
function noWinner(m, n, trials) {
let cycles = 0;
for (let t = 0; t < trials; t++) {
const wins = Array.from({ length: m }, () => Array(m).fill(0)); // wins[i][j]: скільки людей ставлять i вище за j
for (let v = 0; v < n; v++) {
const order = [...Array(m).keys()];
for (let i = m - 1; i > 0; i--) { const j = Math.floor(Math.random() * (i + 1)); [order[i], order[j]] = [order[j], order[i]]; }
for (let a = 0; a < m; a++) for (let b = a + 1; b < m; b++) wins[order[a]][order[b]]++;
}
// переможець Кондорсе має більшість проти кожного суперника
const hasWinner = wins.some((row, i) => row.every((w, j) => j === i || 2 * w > n));
if (!hasWinner) cycles++;
}
return cycles / trials;
}
const exact3 = { 3: 1 / 18, 5: 5 / 72, 7: 875 / 11664, 101: 0.086901 };
for (const n of [3, 5, 7, 101]) {
console.log('варіантів: 3, виборців:', n, '→ без переможця', (100 * noWinner(3, n, 20000)).toFixed(2) + '%', 'точно', (100 * exact3[n]).toFixed(2) + '%');
}
console.log('Межа для безлічі виборців (Ґільбо):', (100 * (1 / 4 - 3 / (2 * Math.PI) * Math.asin(1 / 3))).toFixed(2) + '%');
for (const m of [4, 5, 10]) {
console.log('варіантів:', m + ',', 'виборців: 101 → без переможця', (100 * noWinner(m, 101, 4000)).toFixed(1) + '%');
}
# Кожен виборець ранжує m варіантів випадково й чесно. Як часто жоден варіант не перемагає всі інші в парних голосуваннях?
import math, random
def no_winner(m, n, trials):
cycles = 0
for _ in range(trials):
wins = [[0] * m for _ in range(m)] # wins[i][j]: скільки людей ставлять i вище за j
for _ in range(n):
order = random.sample(range(m), m)
for a in range(m):
for b in range(a + 1, m):
wins[order[a]][order[b]] += 1
# переможець Кондорсе має більшість проти кожного суперника
has_winner = any(all(j == i or 2 * wins[i][j] > n for j in range(m)) for i in range(m))
if not has_winner:
cycles += 1
return cycles / trials
exact3 = {3: 1 / 18, 5: 5 / 72, 7: 875 / 11664, 101: 0.086901}
for n in [3, 5, 7, 101]:
print("варіантів: 3, виборців:", n, "→ без переможця", f"{100 * no_winner(3, n, 20000):.2f}%", "точно", f"{100 * exact3[n]:.2f}%")
print("Межа для безлічі виборців (Ґільбо):", f"{100 * (1 / 4 - 3 / (2 * math.pi) * math.asin(1 / 3)):.2f}%")
for m in [4, 5, 10]:
print("варіантів:", f"{m},", "виборців: 101 → без переможця", f"{100 * no_winner(m, 101, 4000):.1f}%")
Кожен із трьох друзів знає, чого хоче: його список послідовний. А от «більшість» — це щоразу інші двоє людей, і разом їхні рішення замикаються в коло.
Шар «На пальцях» приховано на всіх задачах.
Стрілка веде від переможця до переможеного. Піцу вище за суші ставлять Оля й Ірина, суші вище за вареники — Оля й Марко, вареники вище за піцу — Марко й Ірина. Кожна з трьох більшостей чесна, але це три різні пари людей, і разом вони дають коло.
Ця картка пояснює головне, але ще не все: чому саме голова обирає переможця, розповідає наступна.
Нехай вареники чекають, а першими йдуть піца й суші. Піца перемагає суші. Але піцу в колі б'є саме та страва, що чекала: вареники. І так з будь-якою парою: переможниця першого раунду — це завжди та страва, яку б'є третя.
| Чекає фіналу | Перший раунд | Переможець |
|---|
Отже, голова не вгадує й не вмовляє. Він просто обирає, кого притримати до кінця.
Якщо Оля любить піцу більше за суші, а суші більше за вареники, то й піцу вона любить більше за вареники. Так влаштована кожна людина. Здається, що й «воля більшості» має так поводитися. Але більшість — не людина: у кожній парі її складають інші люди. Кондорсе помітив, що навіть коли кожен голосує зв'язно, загальний результат може виявитися незв'язним.
Буває й інакше. Якщо одна страва перемагає кожну іншу один на один, її називають переможцем Кондорсе. Тоді порядок не важить: вона виграє будь-яке голосування, хоч першою, хоч останньою. Влада голови з'являється лише там, де такого переможця немає.
Шар «Строго» приховано на всіх задачах.
Список з трьох страв можна скласти 3 · 2 · 1 = 6 способами. Троє людей дають 6 · 6 · 6 = 216 різних компаній. Коло буває лише тоді, коли кожна страва стоїть у когось першою, у когось другою й у когось третьою, і списки йдуть «по колу», як у наших друзів.
Напрямків кола два: піца → суші → вареники → піца або навпаки. У кожному три списки, які можна роздати трьом людям 3 · 2 · 1 = 6 способами. Разом 2 · 6 = 12 компаній з колом, тобто 12/216 = 1/18 ≈ 5,6%. В інших 204 є переможець Кондорсе.
| людей | компаній | з колом | частка |
|---|---|---|---|
| 3 | 216 | 12 | 5,56% |
| 5 | 7776 | 540 | 6,94% |
| 7 | 279 936 | 21 000 | 7,50% |
| 9 | 10 077 696 | 785 820 | 7,80% |
| 101 | 6101 | – | 8,69% |
| безліч | – | – | 8,77% |
Кожен рядок пораховано точно: перебрано всі компанії, де кожен із шести списків однаково ймовірний. Частка росте повільно й упирається в 8,77%. Отже, навіть у великих виборах з трьома варіантами приблизно одні з одинадцяти не мають переможця Кондорсе.
Коло: x перемагає y, y перемагає z, z перемагає x. Перший раунд між x і y виграє x, а x програє z. Переможець порядку голосувань — завжди той, хто чекав.
Троє виборців, три варіанти: два напрямки кола, шість способів роздати три списки.
Межа для безлічі виборців (Ґільбо, 1952). Кожна з трьох пар — це майже нормальна величина, а дві пари з однією спільною стравою корелюють з коефіцієнтом −1/3.
Шар «Глибше» приховано на всіх задачах.
Може, винна саме парна схема, і треба просто взяти інше правило? Кеннет Ерроу 1951 року довів, що ні. Нехай правило перетворює списки виборців на спільний список і виконує три вимоги: якщо всі ставлять x вище за y, то й група теж; порядок x і y в спільному списку залежить лише від того, як люди ставлять x і y; немає диктатора, чий список завжди стає спільним. Для трьох і більше варіантів такого правила не існує.
Парадокс Кондорсе — найменший приклад того, що ламається: парна більшість задовольняє всі три вимоги, але не завжди дає список, бо ходить по колу.
Дункан Блек 1948 року знайшов важливий виняток. Нехай варіанти можна розставити на одній осі, скажімо, податок від низького до високого, і кожен виборець має на ній улюблену точку, а що далі від неї, то гірше. Тоді кола не буває, а переможцем Кондорсе стає улюблений варіант медіанного виборця. На цьому стоїть і задача про морозиво на пляжі.
Наші страви на одну вісь не ставляться: кожна з них у когось остання. Хоч яку страву поставити посередині, хтось ставить її на останнє місце, тобто любить обидва краї більше за середину.
Ще в XIII столітті філософ Рамон Льюль описував вибори для монастирів через порівняння кандидатів попарно. Маркіз де Кондорсе 1785 року в «Есеї про застосування аналізу до ймовірності рішень, ухвалених більшістю голосів» запропонував обирати того, хто перемагає кожного суперника один на один, і сам показав, що такого кандидата може не бути. Чарлз Доджсон, відомий як Льюїс Керролл, 1876 року в брошурі про голосування для оксфордського коледжу розбирав такі кола й пропонував, якщо вони не зникають, не обирати нікого. Його брошури забули майже на століття, доки їх не передрукував Дункан Блек. А Кеннет Ерроу перетворив це спостереження на теорему і 1972 року отримав Нобелівську премію з економіки разом із Джоном Гіксом.
З кожним новим варіантом коло трапляється частіше. Інші правила підрахунку не рятують. А порядок голосувань у парламентах колись уже поховав закон, який мав більшість.
Коли варіантів більше, голова ставить їх у чергу: перші двоє змагаються, переможець виходить проти наступного, і так до кінця. Натисніть на варіант на схемі, і сторінка знайде чергу, яка робить його переможцем, або скаже, що такої немає.
Переможцем можна зробити рівно ті варіанти, що входять у «верхнє коло»: найменшу групу, кожен член якої перемагає всіх поза нею. Якщо є переможець Кондорсе, ця група складається з нього одного. У симуляції з 1001 виборцем і випадковими списками переможця Кондорсе немає приблизно у 17,5% виборів з 4 варіантами, у 25% з 5, у 31% з 6 і в 49% з 10.
Коли варіантів безліч, наприклад податок і бюджет водночас, а переможця Кондорсе немає, Річард Маккелві 1976 року довів більше: ланцюжком чесних голосувань «більшістю» голова може довести збори від будь-якого варіанта до будь-якого іншого.
Ми звикли, що «вище за» діє ланцюжком: якщо x вище за y, а y вище за z, то x вище за z. Для зросту, ваги чи одного списку смаків так і є. Але «більшість віддає перевагу» складається з різних людей у різних парах, і ланцюжок рветься. Так само рветься «виграє в» у грі «камінь, ножиці, папір», у нетранзитивних кубиках чи в грі Пенні, де на кожну трійку монет є сильніша.
Тому в групі немає «справжнього» переможця, якого правило мало б лише знайти. Три чесні правила ліворуч дають на тих самих бюлетенях три різні поїздки, а парні дуелі не дають жодної: Одеса б'є Карпати, Львів б'є Одесу, а Карпати б'ють Львів. Обираючи правило, група вже обирає результат.
У Палаті представників США поправки голосують раніше за сам закон: спершу закон з поправкою проти закону без неї, потім переможець проти «нічого не ухвалювати». Порядок задають правила, а не голова, але працює він так само, як у нашій задачі.
1956 року Палата розглядала закон про федеральні гроші на будівництво шкіл. Конгресмен Адам Клейтон Павелл запропонував поправку: не давати грошей штатам, які не виконують рішень Верховного суду про скасування сегрегації в школах. Поправку прийняли 225 голосами проти 192, а потім увесь закон провалили 224 голосами проти 194. Перевірити можна в записах поіменних голосувань 84-го Конгресу.
Політолог Вільям Райкер 1958 року пояснив це колом трьох блоків, як на схемі ліворуч: кожен блок менший за половину палати, а будь-які два разом мають більшість. Його пояснення досі сперечаються: частина республіканців могла голосувати за поправку навмисно, щоб потопити закон, а Джеррі Макі в книжці «Democracy Defended» (2003) доводить, що справжнього кола не було. Але сама пастка реальна: поправку, яка робить закон неприйнятним для частини його прихильників, називають «поправкою-вбивцею».
Усюди, де рішення складають з попарних порівнянь, а переможця Кондорсе може не бути.
| Де | Що порівнюють парами | Що вирішує порядок |
|---|---|---|
| Комітети й парламенти | поправки, закон і «нічого» | порядок поправок і те, коли голосувати сам закон |
| Турніри на вибування | команди в матчах | сітка: якщо команди б'ють одна одну по колу, той, хто складає сітку, може вплинути на чемпіона |
| Вибори з рейтинговими бюлетенями | кандидати за бюлетенями | у виборах шкільного директора в окрузі 4 Окленда 2022 року переможця Кондорсе не було, і результат залежав від правила підрахунку |
| Розподіл місць | штати чи партії | інший парадокс справедливого правила: парадокс Алабами, де більший парламент забирає місце в штату |
Інші задачі, де розумні окремі рішення складаються в несподіваний спільний результат: парадокс Браєса, де нова дорога сповільнює всіх, і вгадай 2/3 середнього, де кожен мусить передбачити інших.
Ніколя де Кондорсе, математик і секретар Паризької академії наук, видав «Есей» про ймовірність рішень більшості за чотири роки до Французької революції. Звідти і назва парадоксу, і «переможець Кондорсе».
Чарлз Доджсон, автор «Аліси в Країні чудес», надрукував брошуру «A Method of Taking Votes on More than Two Issues» для зборів свого коледжу Крайст-Черч в Оксфорді. Якщо більшості ходили по колу, він радив не обирати нікого.
Кеннет Ерроу виклав теорему неможливості в книжці «Social Choice and Individual Values», що виросла з його дисертації. 1972 року він став наймолодшим на той час лауреатом Нобелівської премії з економіки.
Жорж-Теодюль Ґільбо 1952 року обчислив, як часто в дуже великих виборах із трьома варіантами й випадковими смаками немає переможця Кондорсе: 1/4 − (3/2π)·arcsin(1/3), трохи менше за кожні одинадцяті вибори.
5 липня 1956 року Палата представників США спершу прийняла поправку Павелла до закону про будівництво шкіл (225 проти 192), а потім відхилила сам закон: за нього проголосували лише 194, проти 224.
На виборах шкільного директора в окрузі 4 Окленда (Каліфорнія) переможця Кондорсе не було, показав математик Девід Маккюн. Ті вибори ще й спершу порахували з помилкою, і переможця остаточно визначив суд 2023 року.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Рівень «Шкільна математика» відповідає задачі?
Дякуємо! Це допоможе точніше ставити рівні.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.