Как лучше всего нарезать торт? Если вы не профессиональный свадебный планировщик, то наверняка не часто размышляли над таким вопросом. Вы можете подумать, что ответ довольно прост. Нужно просто посчитать количество гостей, сидящих за столом, и поделить десерт на одинаковые куски. Всевозможные диеты и аллергии на глютен могут усложнить ваши вычисления, но в конечном счете этот процесс вряд ли покажется сложным математическим действием.
Тем не менее, как бы парадоксально это ни звучало, речь идет именно о высшей математике, и вы определенно забыли задать себе несколько важных вопросов.
К примеру, гарантирует ли ваш способ нарезки торта, что никто не покинет вечеринку, почувствовав себя обделенным? Предприняли ли вы какие-то шаги, дабы убедиться в том, что каждый посетитель будет в равной степени удовлетворен своим отдельно взятым ломтиком?
Как видите, сейчас мы говорим не просто о торте. В контексте решения проблемы «справедливого распределения», затрагивающей математику, политологию и экономику, торт представляет собой нечто большее, чем обыкновенный десерт. Торт — это многоэтажный дом с квартирами, которые следует разделить между придирчивыми жильцами. Торт — это бракоразводный процесс с высокими отступными. Торт — это охваченная гражданской войной страна.
Начиная с XVII века, теоретики занимаются разработкой методов, которые бы позволяли делить необходимые нам вещи в соответствии с жестким формализмом математики и нашими субъективными представлениями о справедливости. Все это время торт использовался в качестве мощной метафоры для всего ценного, исчерпаемого и делимого в этом мире.
И теперь, с учетом последних достижений в области теории справедливого распределения (fair division theory) и информатики, все больше исследователей хотят сделать эти методы доступными для неосведомленной общественности. Чтобы всего одним нажатием кнопки вы могли бы порезать торт как настоящий математик.
Принцип справедливого деления
Детям уже давно известен лучший способ разделить объект на две части. Этот метод называется «Я разделяю, ты выбираешь», и вы наверняка использовали этот алгоритм справедливого деления в далеком детстве. Гениальность данного подхода заключается не только в том, что он достаточно прост для применения, но и в том, что при определенных обстоятельствах он дает объективные результаты.
Человек, применяющий его, знает, что другой выберет себе лучший кусок, поэтому старается разрезать торт (бутерброд или что-либо еще) как можно более справедливо. Таким образом, обе стороны гарантированно получают порции, которые, по их мнению, являются примерно одинаковыми.
Экономисты и математики нарекли этот метод «свободным от зависти» и таким определением они попали точно в цель. Если у вас есть ванильный торт, и вам нужно разделить его между двумя людьми, каждый из которых одинаково любит сладкое, то, чтобы никто не начал завидовать, торт нужно разделить пополам. Оба получат равный кусок торта, и никаких математических талантов для такого разделения не нужно.
Метод «Я разделяю, ты выбираешь» работает не только для материальных вещей (торты и арахисовое масло). Как показал популярный писатель Мартин Гарднер в 1978 году, домашние обязанности также можно распределить, если один человек делит каждую задачу на две части, а другой выбирает одну из них.
Этот метод также используется юристами. При заключении контрактов на совместную собственность, адвокаты часто прибегают к денежному аналогу принципа «Я разделяю, ты выбираешь». Когда люди при разводе делят собственность, один партнер называет цену, а другой решает, хочет ли он её выкупить или продать.
Как пишет Джеймс Ф. Ринг, «инициирующая сторона ставит своего противника в положение, когда наиболее разумная стратегия для него заключается в том, чтобы честно оценить собственность и закончить спор».
Ринг убедился в этом на собственном опыте. Являясь соучредителем Fair Outcomes, компании, специализирующейся на оказании помощи людям при разводах, Ринг и Стивен Брамс нашли множество применений метода «Я разделяю, ты выбираешь».
В обзоре способов справедливого разделения, опубликованных на сайте nautil.us, научный писатель Эрика Кларрайх приводит один любопытный пример. В случае спора при расторжении брака или отношений, алгоритм, который Ринг и Брамс называют «Справедливая покупка-продажа», предполагает, что каждый партнер одновременно называет свою цену.
«Если Джон предложит 110 000 долларов, а Джейн предложит 100 000 долларов, тогда Джон, предложивший более высокую цену может выкупить вещь у Джейн за 105 000 долларов», — объясняет Ринг. «Каждый участник в результате получает что-то — деньги или вещь — по цене, которая лучше, чем его предложение».
Этот метод нашел место даже в международном морском праве. В 1970-х годах, когда государства готовились к будущему, в котором подводная добыча ископаемых станет крупной отраслью, развивающиеся страны были обеспокоены тем, что технологически более развитые корпорации приобретут права на разработку наиболее ценных морских участков.
Решение было предложено и ратифицировано в Конвенции по морскому праву. Теперь, если компания хочет добывать ресурсы с морского дна, она должна сначала разделить участок на две части. После чего менее развитая сторона выбирает один из них.
«Свобода от зависти»
Но, как может сказать любой ученик начальной школы, существуют такие конфликты, справиться с которыми не в состоянии даже способ «Я разделяю, ты выбираешь».
Возвращаясь к кулинарной метафоре, представьте себе, что рассматриваемый торт не простой ванильный (допустим, вдоль левого края были размещены несколько кусочков клубники), и что голодные гости за столом имеют разные предпочтения (может быть, один человек предпочитает фрукты, а другой любит выпечку).
Если пирог будет делить любитель клубники, он может разделить его на две половины, оставив равное количество клубники на каждой. Так он получит свою долю фруктов независимо от выбора другого человека. Поскольку любитель выпечки собирается выбросить свою клубнику, для него тоже не имеет значения, какую половину выбрать. В результате никто не будет завидовать.
Но всё же есть кое-что неудовлетворительное в подобном исходе. В частности, экономисты назвали бы этот результат «неэффективным», потому что торт можно было разрезать таким образом, чтобы сделать по крайней мере одного из участников счастливее, не причинив никому вреда. В приведённом примере можно было сделать так: любитель ягоды мог поменять часть своего пирога на клубнику. Всем было бы лучше.
Значит, разделение было неправильным? Ведь лучше, если бы он оставил себе больше клубники?
Предположим другую ситуацию. Любитель клубники просто отсекает меньшую покрытую ягодами половину. Таким образом, он гарантированно получит либо меньший кусок с большим количеством ягоды (что было бы хорошо, потому что он любит клубнику), либо больший кусочек без ягод (что тоже неплохо, потому что, несмотря на отсутствие ягод, он все же получает больше пирога).
На этот раз выбор для его друга очевиден. Он выберет большую часть торта.
Теперь результат можно назвать эффективным, потому что кусочки торта нельзя было бы поменять, не сделав хотя бы одну из сторон неудовлетворенной. Более того, в результате никто никому не завидует. Ни у одной из сторон нет причин хотеть поменять свой кусок. В теории нет причин для зависти.
И тем не менее, сложность людской психологии запутывает математическую выстроенную модель человеческого поведения. Вышеприведенное решение теоретически может иметь последствия, противоречащие нашему чувству справедливости. Поклонник клубники в любом случае не проиграет (он получает кусочек, который, по его мнению, составляет 50% от стоимости торта), в то время как любитель торта получает большую часть торта, то есть выигрывает в сделке.
Как разделить торт между тремя и более людьми
Десятилетиями теоретики тщетно пытались найти справедливое решение проблемы деления. Ведь приглашение к столу дополнительных претендентов на торт вводит еще большую сложность.
В 1940-х годах польский профессор Хьюго Штайнхаус подошел к этому вопросу с математической строгостью. Спросив себя, существует ли вариант метода «Я разделяю, ты выбираешь» для трех или более человек, он в конечном итоге придумал то, что теперь называется «методом одинокого разделителя».
Проиллюстрируем его суть на примере. Представьте себе трех потенциальных покупателей торта. Один из них выбирается наугад. Он становится «одиноким разделителем», и его просят разделить торт на три части. Как и в случае с «Я разделяю, ты выбираешь», он не знает, какой кусочек ему суждено получить, и поэтому пытается разделить торт на три одинаково желаемых ломтика.
Остальным двум участникам, выборщикам, предлагается записать, какие из кусочков они бы хотели. Затем списки сравниваются. Если они хотят разные кусочки, то игра окончена: каждый из них получает то, что хотел, а первый разделитель получает третий кусок.
Если же выборщики хотят один кусок, то разделителю дается одна из двух не востребованных частей, а два оставшихся куска соединяются. Теперь у нас есть один маленький торт, два голодных конкурента и метод «Я разделяю, ты выбираешь», который и решит их проблему.
Метод Штайнхауса привлекательно прост и может быть расширен до более чем трех человек, но он не гарантирует результатов, в которых не было бы зависти. Для этого требуется более сложная математика.
Торт из треугольников
Фрэнсис Су получил докторскую степень по математике в Гарварде в конце 1990-х, когда Брэд Манн, его друг и кандидат в докторанты, пришел к нему со своей проблемой.
Как и большинство студентов в районе Кембриджа, Манн снимал тесный домик с несколькими знакомыми. Естественно, их мнения расходились в том, кто должен получить комнату больших размеров. Манн пришел к Су с вопросом, как выйти из тупика.
В то время как большинство из нас предложило бы бросить жребий, Су, который теперь является профессором в колледже Харви Мадд и Президентом Математической ассоциации Америки, предложил оригинальное решение.
«Когда он рассказал мне о своем затруднительном положении, я сказал:«Это математический вопрос!», — рассказывает Су. В частности, это был вопрос справедливого разделения.
Возможно, решение Су было не очень полезным для Манна, но спустя несколько лет Су опубликовал статью на эту тему, в которой он смог доказать, что в доме, разделенном в соответствии с его методом, комнаты и арендная плата могут быть разделены так, чтобы никого не обидеть.
Статью Су новаторской сделало то, что он использовал сложный математический аргумент 1920-х годов, названный «леммой Спернера». Изначально лемма не имела ничего общего с арендой или тортами. Она относилась к треугольникам.
Представим себе, что у вас есть большой треугольник, как на рисунке выше. Каждую из вершин треугольника обозначим числами (в данном случае 1, 2 и 3). Треугольник затем разделяется на ряд меньших треугольников, и их вершинам также присваиваются числа.
Но здесь есть сложность. Любая вершина вдоль края большего треугольника должна делиться своим числом с одной из двух точек в конце этого края. Например, в нижней части треугольника могут быть только 1 и 2, потому что они расположены между двумя точками большего треугольника, которые обозначены 1 и 2. Аналогично, левая сторона треугольника может иметь только метки 1 и 3, в то время как правая сторона получает только 2 и 3.
Согласно «лемме» (мини-теореме), если все вышеприведенные условия верны, то во всей сетке перекрещивающихся вершин должен быть хотя бы один треугольник, который имеет разные числа в каждой из трех его точек. На рисунке выше таковых три.
Какое это имеет отношение к ренте? В нахождении этой связи и заключалось прозрение Су.
В статье треугольник переосмысливается как все возможные комбинации цен на комнаты, разделенные между тремя комнатами. Например, точка в верхней части треугольника может представлять собой ситуацию, когда один из соседей оплачивает всю аренду в комнате А, а остальные не платят ничего за оставшиеся две комнаты В и С. Аналогично, точка в левом углу большого треугольника будет представлять собой ситуацию, когда житель комнаты B отдает всю арендную плату. Перемещение в центр треугольника соответствует более справедливым распределениям ренты между тремя комнатами.
Су назначил каждого из жителей дома «владельцем» вершины (ценовой комбинации).
Математический алгоритм решения проблемы Су начинается с вершины за пределами треугольника с вопроса: «Если бы ренту нужно было разделить в соответствии с этой ценовой схемой, в какой комнате ты бы жил?» В зависимости от ответа, этому пункту будет дано число (1, 2 или 3). Затем алгоритм может «переместиться» на новую комбинацию «цена и комната», расположенную глубже внутри треугольника, где тот же вопрос будет задан другому жильцу.
Процедура будет продолжаться до тех пор, пока не будет найдена схема ценообразования, в которой каждый житель согласится жить в разных комнатах при определенных ценах. Графически этот пункт будет существовать в треугольнике, в котором вершины были бы помечены разными цифрами. Помните, что согласно лемме Спернера такой треугольник должен существовать.Таким образом, гармония возможна.
Идея Су стала настоящим открытием. В 2014 году New York Times даже сделал калькулятор арендной платы, используя алгоритм Су.
«Алгоритма справедливости» не существует
Алгоритм Фрэнсиса Су не является единственным способом решить рассматриваемые проблемы.
В том же году группа ученых в Школе информатики Карнеги запустила Spliddit. Алгоритм Су является итеративным, требующим ввода повторных данных от каждого участника, и предлагает только «свободные от зависти» решения . А калькулятор аренды Spliddit, который отличается удобством, выдает решения, которые лишь «доказуемо справедливы».
Хотя первая версия данного калькулятора подражала алгоритму Су, разработанному в 2004 году, результаты, которые он производил, хотя и были свободными от зависти в математическом смысле, не всегда удовлетворяли людей на практике.
«Иногда у вас есть решения, которые удовлетворяют некоторой теоретической модели справедливости, но на практике справедливым вы интуитивно считаете другой расклад», — говорит руководитель проекта Ариэль Прокачча.
Он предлагает следующий пример. Представьте себе трехкомнатную квартиру, разделенную между тремя соседями. Арендная плата составляет 3 доллара. Первый житель заинтересован только в том, чтобы жить в первой комнате, второй интересуется только второй, а их сосед — третьей. Каждый человек согласен заплатить 3 доллара за свою комнату.
Одно из возможных решений заключалось бы в том, чтобы поместить каждого человека в комнату по его выбору и назначить всю сумму арендной платы первому жильцу. Второй и третий жильцы тогда заключат гораздо более выгодную сделку, но у первого соседа по дому нет причин возражать. Он платит 3 доллара — ровно столько, сколько он и хотел, ведь у него нет желания жить в другом месте дома.
«Это решение не должно вызвать зависти на уровне теории, но, очевидно, оно несправедливо», — говорит Прокачча. «Справедливо каждому поселиться в комнате, в которой он хочет жить, и платить 1 доллар».
Именно такого результата и пытается достичь алгоритм Spliddit. Во-первых, он пытается максимизировать разницу между тем, сколько житель готов заплатить за комнату, и тем, сколько он в конечном счете платит. Этот «излишек» показывает, насколько выгодна сделка для каждого жильца, и алгоритм гарантирует, что у каждого жильца в желаемой им комнате он будет выше, чем тот излишек, который у него был бы в другой комнате. Это удовлетворяет условию отсутствия зависти.
Но затем, пытаясь найти «интуитивно справедливое» решение, калькулятор находит комбинацию комнат, которые минимизируют разницу в излишках каждого жильца.
Короче говоря, алгоритм гарантирует, что каждый житель заключает выгодную сделку, которая не может быть намного выгоднее по сравнению с соседями.
С появлением Spliddit поменялся способ расчета тарифов на такси, кредитования, методики разделения задач. Одной из причин создания Spliddit было ознакомление широкой общественности с преимуществами математических методов решения проблем, связанных со справедливым разделением. Точно так же, как метод «Я разделяю, ты выбираешь», его алгоритм используется для урегулирования деловых конфликтов.
Создатель Spliddit надеется, что когда-нибудь компьютеры смогут находить решения в гораздо более сложных проблемах.
Высоких вам конверсий!
По материалам: priceonomics.com
