Як справедливо порізати торт
Двоє молодих вчених, фахівців у галузі інформатики, вигадали, як чесно поділити торт між будь-якою кількістю людей, вирішивши завдання, над яким математики билися десятиліттями. Їхня робота здивувала багатьох дослідників, які вважали такий поділ неможливим у принципі.
Поділ пирога - це метафора для широкого кола реальних завдань, що включають розподіл якогось безперервного об'єкта, чи то торт, чи наділ землі, між людьми, які по-різному оцінюють його властивості. Одному подобається шоколадне покриття, інший хоче отримати кремові квіточки. З біблійних часів відомий алгоритм поділу такого об'єкта між двома людьми, такий, щоб ніхто не заздрив іншому: одна людина ділить торт на дві рівні для неї частини, а інша вибирає одну з них. У Книзі Буття Авраам (тоді ще відомий як Аврам) і Лот використовували цей метод для поділу землі, коли Авраам вигадував поділ, а Лот вибирав між Йорданом і Ханааном. У 1960-х математики вигадали алгоритм для подібного поділу пирога «без заздрості» вже для трьох осіб. Але досі найкращим рішенням завдання для кількості людей більше трьох була процедура, створена в 1995 політологом Стівеном Брамсом [Steven Brams] з Нью-Йоркського університету і математиком Аланом Тейлором [Alan Taylor] з Юніон-коледжу. Вона гарантувала «справедливу» поділку пирога, але з однією умовою – процедура була «необмеженою», тобто кількість кроків, необхідна для розподілу, могла виявитися як завгодно більшою.
Алгоритм Брамса-Тейлора свого часу був названий проривним, але «його необмеженість, на мою думку, була великим недоліком», каже Аріель Прокаччіа [Ariel Procaccia], фахівець з інформатики з Університету Карнегі-Меллон, один із творців Spliddit, безкоштовного онлайн- інструменту длясправедливого поділу різних завдань, від домашніх обов'язків до плати за спільну оренду квартири.
За останні 50 років багато математиків та фахівців з інформатики, включаючи Прокаччіа, переконали себе, що обмеженого справедливого алгоритму по розділу торта на n частин не існує.
"Саме це завдання привело мене в область справедливих поділів", - каже Уолтер Стромквіст [Walter Stromquist], професор математики в Коледжі Бріна Мавра в Пенсільванії, який досяг непоганих результатів у задачі поділки торта в 1980. "Все життя я думав, що я це завдання у вільний час і доведу, що таке розширення результату неможливе в принципі».
Алгоритм надзвичайно складний. Розділ торта між n учасниками може вимагати до n n n n n кроків, з приблизно такою ж кількістю розрізів. Навіть для невеликої кількості учасників це число перевищує кількість атомів у Всесвіті. Але дослідники вже мають ідеї щодо спрощення та прискорення алгоритму, за словами другого учасника команди, Харіса Азіза [Haris Aziz], 35-річного фахівця з інформатики з Університету Нового Південного Уельсу, який працює в австралійській групі дослідження даних Data61.
Фахівці, які досліджують теорію справедливого поділу, за словами Прокаччіа, вважають це однозначно найкращим результатом за десятиліття.
Алгоритм Азіза та Макензі заснований на елегантній процедурі, незалежно придуманій математиками Джоном Селфріджем [John Selfridge] та Джоном Конвеєм у 1960-х, що дозволяє справедливо розділити торт на трьох.
Якщо Аліса, Боб та Чарлі (A, B, C) хочуть розділити торт, алгоритм починається з того, що Чарлі ділить торт на три шматки, які для нього виглядають рівноцінними. Аліса і Боб вибирають шматки, які їм подобаються. Якщо вониоберуть різні шматки - вуаля, кожен отримує те, що хотів.
Якщо Аліса і Боб виберуть один шматок, тоді Боб відрізає невелику частину від цього шматка так, щоб шматок став рівноцінний, на його думку, іншому шматку торта – тому, який би Боб вибрав у другу чергу. Відрізаний залишок відкладається. Тепер Аліса повинна вибрати найкращий для себе шматок з трьох, а потім вибирає Боб - з умовою, що він візьме обрізаний ним шматок, якщо Аліса його не вибере. Чарлі отримує третій шматок.
У результаті ніхто нікому не заздрить. Аліса вибирала першу. Боб отримав один із двох однаково цінних для нього шматків. Чарлі отримав один із трьох початкових шматків, які він різав сам.
Залишається лише невеликий відрізаний залишок. Але його можна розділити, не починаючи алгоритм спочатку і не потрапляючи в нескінченний цикл обрізань і виборів, оскільки Чарлі в будь-якому випадку задоволений своїм шматком - і навіть якби той, кому дістався обрізаний шматок, отримав би на додачу до нього весь залишок цілком, Чарлі це не виглядало б нечесним, тому що обрізаний шматок і залишок у сумі дадуть шматок торта, еквівалентний його шматку - адже він спочатку сам ці шматки і нарізав. Азіз і Макензі описують таке становище Чарлі, як «домінуючий».
Тепер, якщо, наприклад, Алісі дістався шматок обрізаний, то Боб ріже обрізки на три частини, еквівалентні з його точки зору, Аліса з цих шматків вибирає один собі, потім вибирає Чарлі, потім Боб. Всі щасливі: Аліса вибирала першою, Чарлі отримує шматок краще, ніж у Боба (і йому все одно, скільки взяла Аліса), а з погляду Боба всі три шматки рівноцінні.
Брамс і Тейлор використовували властивість «домінування» (але з іншим ім'ям) для розробки свого алгоритму 1995, але вони не дотиснули своюідею до появи обмеженого алгоритму. У наступні 20 років ніхто не досяг найкращих результатів. «І не через брак спроб», як каже Прокаччіа.
Непрофесійні дільники тортів
Коли Азіз і Макензі (АіМ) вирішили взятися за це завдання кілька років тому, вони були новачками в задачі торта. «У нас не було стільки досвіду, як у людей, які інтенсивно працювали над нею, - каже Азіз. – Хоча зазвичай це недолік, у нашому випадку він був перевагою, оскільки ми думали інакше».
Їм не вдалося відразу показати, як розширити свій алгоритм на число учасників, більше чотирьох, але вони з ентузіазмом зайнялися цим завданням. «Після відправлення роботи, що стосувалася чотирьох учасників, ми дуже хотіли якнайшвидше продовжити роботу, поки хтось досвідченіший і розумніший не узагальнить її самостійно до випадку з n учасниками», - говорить Азіз. І приблизно через рік їхні пошуки мали успіх.
Як і алгоритм Селфріджа-Конвея, протокол АІМ постійно пропонує різним учасникам розрізати торт на n рівних частин, а іншим робити відрізи і вибирати шматки торта. Але в алгоритмі є інші кроки, наприклад періодичний обмін шматками тортів спеціальним чином, з метою збільшення кількості домінуючих взаємин між учасниками.
Ці відносини дозволяють АІМ зменшити складність завдання. Якщо, припустимо, три учасники домінують над рештою, їх уже можна відправляти їсти свої шматки торта – вони будуть задоволені незалежно від того, хто отримає залишки. Після цього залишається менше учасників, і після обмеженої кількості таких кроків усі залишаються задоволеними і весь торт виявляється поділений.
"Озираючись назад, на складність алгоритму, стає не дивно, що його розробка зажадала стільки часу", - кажеПрокаччіа. Але АіМ вже вважають, що можуть спростити алгоритм, щоб він не вимагав обміну шматками і проходив лише за n n n кроків. За словами Азіза, вони вже працюють над цими результатами.
Брамс попереджає, що й у простішого алгоритму не буде практичного застосування – адже шматки торта, отримані учасниками, включатимуть безліч дрібних крихт з різних частин торта. Такий підхід не дуже корисний, якщо ви, наприклад, проводите розділ землі.
Але для фахівців з математики та інформатики, які вивчають завдання, новий результат «обнуляє всю тему», каже Стромквіст.
Тепер, коли дослідникам відомо, що торт можна розділити за обмежену кількість кроків, наступним кроком, за словами Прокаччіа, буде розуміння великого розриву між верхнім обмеженням кількості кроків методом АіМ, і нижнім обмеженням необхідної кількості кроків. Прокаччіа вже довів раніше, що алгоритм справедливого поділу торта не може проходити менш ніж за n 2 кроків – але ця кількість кроків крихітна порівняно з n n n n n і навіть з n n n .
Азіз каже, що дослідники тепер мають зрозуміти, як скоротити цей розрив. «Думаю, що в обох напрямках може бути досягнуто прогресу».