Как да разрежем справедливо торта
Двама млади компютърни учени измислиха как справедливо да разпределят тортата между произволен брой хора, решавайки проблем, с който математиците се борят от десетилетия. Тяхната работа изненада много изследователи, които смятаха подобно разделяне за принципно невъзможно.
Разделянето на пая е метафора за широк спектър от проблеми в реалния свят, включително разделянето на някакъв непрекъснат обект, било то торта или парче земя, между хора, които оценяват свойствата му по различен начин. Единият обича шоколадова глазура, другият иска кремави цветя. От библейски времена е известен алгоритъм за разделяне на такъв предмет между двама души, така че никой да не завижда на другия: единият разделя тортата на две равни части вместо него, а другият избира едната. В Битие Авраам (тогава известен като Аврам) и Лот използват този метод, за да разделят земята, като Авраам измисля разделението, а Лот избира между Йордан и Ханаан. През 60-те години на миналия век математиците измислиха алгоритъм за подобно разделяне на пая „без завист“ вече за трима души. Но досега най-доброто решение на проблема за повече от трима души е процедура, създадена през 1995 г. от политолога Стивън Брамс от Нюйоркския университет и математика Алън Тейлър от Юниън Колидж. Тя гарантираше „справедливо“ разделяне на пая, но с едно условие – процедурата да е „неограничена“, тоест броят на стъпките, необходими за разделянето, може да бъде произволно голям.
Алгоритъмът на Брамс-Тейлър беше наречен пробив по онова време, но „неговата неограниченост беше, според мен, голям недостатък“, казва Ариел Прокача, компютърен учен в университета Карнеги Мелън и един от създателите на Spliddit, безплатен онлайн инструмент засправедливо разпределение на различни задачи, от домакински задължения до съвместно наемане на апартамент.
През последните 50 години много математици и компютърни учени, включително Procaccia, се убедиха, че няма ограничен справедлив алгоритъм за разделяне на торта на n части.
„Именно този проблем ме насочи към царството на справедливите разделения“, казва Уолтър Стромквист, професор по математика в колежа „Брин Маур“ в Пенсилвания, който постигна доста добри резултати по задачата за рязане на торта през 1980 г. „През целия си живот си мислех, че ще се върна към този проблем в свободното си време и ще докажа, че подобно разширение на резултата е невъзможно по принцип.“
Алгоритъмът е изключително сложен. Разделянето на тортата между n участници може да изисква до n n n n n n стъпки с приблизително същия брой разрези. Дори за малък брой участници този брой надвишава броя на атомите във Вселената. Но изследователите вече имат идеи за опростяване и ускоряване на алгоритъма, според втори член на екипа, Харис Азиз, 35-годишен компютърен учен в Университета на Нов Южен Уелс, който работи за австралийския екип за изследване на данни Data61.
Изследователите на Equitable Division казват, че това е „далеч най-добрият резултат от десетилетия“, каза Прокача.
Алгоритъмът на Азиз и Макензи се основава на елегантна процедура, разработена независимо от математиците Джон Селфридж и Джон Конуей през 60-те години на миналия век за справедливо разделяне на торта между трима.
Ако Алис, Боб и Чарли (A, B, C) искат да споделят тортата, алгоритъмът започва с това, че Чарли разделя тортата на три парчета, които му се струват равни. Алис и Боб избират парчетата, които харесват. Ако теизберете различни парчета - готово, всеки получава това, което иска.
Ако Алис и Боб изберат едно и също парче, тогава Боб отрязва малко парче от това парче, така че парчето да е равно, от негова гледна точка, на друго парче от тортата, това, което Боб би избрал второ. Отрязаният остатък се отлага. Сега Алис трябва да избере най-доброто парче за себе си от останалите три, а след това Боб избира - с условието, че ще вземе парчето, отрязано от него, ако Алис не го избере. Чарли получава третото парче.
В резултат на това никой не ревнува никого. Алис избра първа. Боб получи едно от двете еднакво ценни за него парчета. Чарли получи едно от трите оригинални парчета, които сам изряза.
Останал е само малък фрагмент. Но може да се раздели, без да се стартира алгоритъмът отначало и без да се навлиза в безкраен цикъл от разфасовки и избори, тъй като Чарли така или иначе е доволен от своето парче - и дори ако този, който получи отрязаното парче, получи целия остатък в допълнение към него, това няма да изглежда нечестно за Чарли, защото отрязаното парче и остатъкът в сумата ще дадат парче торта, еквивалентно на неговото парче - в края на краищата той самият първоначално е тези парчета и sli ced. Азис и Макензи описват позицията на Чарли като "доминираща".
Сега, ако, например, Алис получи подрязана част, тогава Боб нарязва гарнитурите на три части, които са еквивалентни от негова гледна точка, Алис избира една от тези части за себе си, след това избира Чарли, след това Боб. Всички са доволни: Алис избра първа, Чарли получава по-добра фигура от Боб (и не го интересува колко е взела Алис), а от гледна точка на Боб и трите фигури са равни.
Брамс и Тейлър използваха свойството „доминиране“ (но с друго име), за да разработят своя алгоритъм от 1995 г., но не завършиха своя.идея преди появата на ограничен алгоритъм. През следващите 20 години никой не е постигнал по-добри резултати. „И не поради липса на опити“, казва Прокача.
Непрофесионални разделители за торта
Когато Азиз и Макензи (A&M) решиха да поемат това предизвикателство преди няколко години, те бяха нови в проблема със споделянето на тортата. „Нямахме толкова опит, колкото хората, които работиха упорито по него“, казва Азис. „Въпреки че това обикновено е недостатък, в нашия случай беше предимство, защото мислехме по различен начин.“
Те не показаха веднага как да разширят алгоритъма си до повече от четирима участници, но с ентусиазъм се заеха със задачата. „След като изпратихме документа с четирима участници, ние наистина искахме да продължим бързо, докато някой по-опитен и умен не го обобщи сам за случая с n участници“, казва Азис. И около година по-късно търсенето им се увенча с успех.
Подобно на алгоритъма Selfridge-Conway, протоколът A&M постоянно кани различни участници да нарежат тортата на n равни части, а други да режат и избират парчета от тортата. Но има и други стъпки в алгоритъма, като например периодична размяна на парчета торти по специален начин, за да се увеличи броят на доминиращите взаимоотношения между участниците.
Тези връзки позволяват на A&M да намали сложността на задачата. Ако, да речем, трима участници доминират над останалите, те вече могат да бъдат изпратени да изядат собствените си парчета от тортата - те ще бъдат щастливи, независимо кой ще получи останалите. След това остават по-малко участници и след ограничен брой такива стъпки всички са доволни и цялата торта се разделя.
„Поглеждайки назад към сложността на алгоритъма, не е изненадващо, че разработването му отне толкова много време“, казваПрокача. Но A&M вече вярват, че могат да опростят алгоритъма, така че да не изисква размяна на фигури и да отнема само n n n стъпки. Според Азис те вече работят върху тези резултати.
Брамс предупреждава, че дори по-опростен алгоритъм няма да има практическо приложение – все пак получените от участниците парчета торта ще включват много малки трохи от различни части на тортата. Този подход не е особено полезен, ако например разделяте земя.
Но за математиците и компютърните учени, изучаващи проблема, новият резултат "нулира цялата тема", казва Stromquist.
Сега, когато изследователите знаят, че една торта може да бъде разделена на ограничен брой стъпки, следващата стъпка, казва Прокача, е да разберат голямата разлика между горната граница на A&M за броя на стъпките и долната граница за това колко стъпки са необходими. Procaccia вече е доказал преди това, че алгоритъмът за справедливо разделяне на тортата не може да бъде завършен за по-малко от n 2 стъпки - но този брой стъпки е малък в сравнение с n n n n n n и дори n n n .
Азис казва, че сега изследователите трябва да разберат как да запълнят тази празнина. „Мисля, че може да се постигне напредък и на двата фронта.“