Это мог быть эпизод на MTV «Реальный мир»: Четыре друга двигаются в дом, имеющий четыре комнаты различных размеров. Не кажется справедливым для них всех заплатить ту же арендную плату. Там некоторый путь состоит в том, чтобы разделить арендную плату так, чтобы никто не чувствовал себя обсчитанным?
К сожалению для любителей драмы и конфликта, математики теперь доказали, что распределение «без завистей» арендной платы всегда существует – и они написали компьютерную программу, находящую его.Фрэнсис Су, математик в Колледже Харви Мадда в Клермонте, Калифорния, начал думать о проблеме арендованного отделения, когда друг нашел себя в ситуации просто описанным. Он знал о подобной загадке, названной «сокращающей пирог проблемой», в которой несколько человек пытаются разделить пирог на путь, делающий всех счастливыми. Когда существует два человека, раствор легок: Один человек режет пирог, другой выбирает, таким образом, ни один не может утверждать, что они получили мошенничество.
В 1992, политолог Нью-Йоркского университета Стивен Брэмс и Колледж Союза, Нью-Йорк, математик Алан Тейлор разработал первый метод без завистей, работающий на любое число людей. Их подход, однако, не очень практичен: могли бы требоваться миллиарды сокращений. «Это опустошило бы пирог, когда Вы сделаны», говорит Су.Для проблемы арендованного отделения Су полагал, что это будет достаточно хорошо для производства раствора, который был почти, если не абсолютно, без завистей.
Его Справедливый Калькулятор Отделения работает, неоднократно опрашивая каждого соседа по комнате, на которой комнате они выбрали бы, если бы арендные платы были разделены определенными способами. По многим итерациям схема становится ближе и ближе к отделению, которым все довольны. Хотя это – простая идея, твердая часть доказывает математически, что это всегда работает.
Решающий компонент доказательства является результатом комбинаторной топологии, названной аннотацией Спернера, методом для решения сложных наборов уравнений, которые исследователи выкладывают в проблеме этого месяца американской Mathematical Monthly.«Люди спрашивают меня, разве Вам не мог сойти с рук больше, если бы Вы не отвечали на вопросы правдиво?» Су говорит. «Ответ да, но если Вы будете правдивы, то Вам гарантируют раствор без завистей, даже если все остальные будут лежать». Единственный случай, в котором терпит неудачу алгоритм, – то, если существует комната настолько плохо, что один из соседей по комнате даже не возьмет его бесплатно. (В этом случае Су предлагает искать менее придирчивого соседа по комнате.)
Математики говорят, что метод должен быть применим ко многим системам урегулирования конфликтов кроме арендованного отделения. «Мне интересной вещью об этом является философия», говорит Майкл Старбирд, математик в университете Техаса, Остина. «Вместо того, чтобы спорить друг с другом о системах ценностей, Вы объявляете свою собственную систему ценностей и позволяете третьему лицу найти средний путь».