Max Home IndustryЕсли вы хотите найти способ разделить некоторые неделимые элементы между сущностями, то вот способ, который исключает зависть как результат. Предполагается, что это может быть хорошим способом разделить имущество во время развода — алгоритмы вмешиваются во все.
Уже существуют методы справедливого совместного использования ресурсов в распределенной системе. Самым известным из них является метод разделения торта «ты разрезаешь, я выбираю». Существуют также алгоритмы, которые позволяют разделить торт между несколькими участниками, так что каждый должен быть удовлетворен результатом в том смысле, что они чувствуют, что, возможно, они не получили столько торта, сколько хотели, но, по крайней мере, они получили столько, сколько их «противники».
Более сложная проблема, чем разделение непрерывного ресурса, — это разделение неделимых элементов между группой людей, каждый из которых присваивает элементам свой набор значений. В новой статье Стивена Брамса из Нью-Йоркского университета, Д. Марка Килгура из Университета Уилфрида Лорье и Кристиана Кламлера из Грацкого университета, опубликованная в этом месяце в «Уведомлениях Американского математического общества», описывается пара алгоритмов.
Первый ранее известный алгоритм, BT, заставляет двух игроков A и B делать независимый выбор наиболее предпочтительных элементов из набора элементов, которые еще предстоит выделить. Если A и B назовут два разных предмета, каждый из них получит желаемый предмет. Если они называют один и тот же предмет, то он помещается в стопку оспариваемых предметов, CP. Это продолжается до тех пор, пока все предметы не будут распределены или помещены в CP.
Этот алгоритм находит распределение, свободное от зависти (EF) в том смысле, что каждый игрок получает одинаковое количество элементов, и каждый игрок предпочитает подмножество элементов, которые у него есть. Идея EF на самом деле довольно тонкая. В основном это сводится к тому, что для каждого предмета А есть предмет из Б, который менее желателен.
Другой способ сказать это: если для каждого элемента x, который A имеет количество элементов, принадлежащих B, которое A предпочитает x, не больше, чем аналогичное количество элементов, которое A имеет и предпочитает x.
Важным моментом в назначении EF является то, что нет альтернативного назначения, которое обе стороны предпочли бы на основе своего рейтинга.
Например, если рейтинги следующие:
А: 1 2 3 4
А: 2 3 4 1
затем, используя алгоритм, A получает 1, а B — 2. Новый рейтинг:
А: 3 4
А: 3 4
Теперь у нас есть ничья, так что 3 попадает в CP, а также 4. Таким образом, окончательное распределение: A получает 1, а B получает 2, и два элемента не распределяются как CP = {3,4}
Этот алгоритм работает быстро и позволяет каждому человеку присваивать рейтинги по мере продвижения деления и, таким образом, учитывать изменение полезности, например Если у вас нет телевизора, нет смысла покупать игровую приставку. Большая проблема в том, что он не всегда находит максимальное назначение EF.
В документе представлен чуть более сложный алгоритм AL, который всегда будет находить максимальное назначение в том смысле, что не существует другого назначения EF, которое выделяет игрокам больше элементов.
Примерно алгоритм работает таким же образом до тех пор, пока не произойдет ничья, когда он попытается найти назначение связанного элемента либо A, либо B, и другому элементу, что приводит к назначению без зависти. То, как именно это делается, зависит от фактического тестирования тестового задания всех возможных элементов. Для этого игроки должны присвоить все свои рейтинги до начала процедуры распределения. Алгоритм работает за полиномиальное время, если вам нужно только одно максимальное присвоение. Если вы хотите увидеть все возможные максимальные назначения, то это экспоненциально.
Пока игроки присваивают предметам истинные рейтинги, более сложный алгоритм найдет максимальное присвоение EF. Интересно отметить, что по мере увеличения количества элементов вероятность полного присвоения EF приближается к единице.
Плохая новость в том, что можно обмануть.
Если вы солгаете о своем рейтинге, вы можете получить задание, которое при раскрытии истинного рейтинга вызовет зависть. Однако, как отмечают авторы, опасность заключается в том, что у вас не получится сработать идеально, потому что это зависит от рейтинга другого игрока, и вы можете оказаться в худшем положении. Лучшая стратегия — играть честно и в конечном итоге получить распределение без зависти.
«Во многих спорах, включая развод и раздел имущества, справедливым будет считаться только распределение, при котором участники спора получают примерно одинаковое количество предметов. Для этой цели хорошо подходят BT и AL, особенно когда они распределяют большую часть, если не все, В то время как BT является образцом простоты, AL, как мы показываем, применять не намного сложнее, что должно облегчить его принятие в качестве практичной процедуры ».
Поэтому в следующий раз, когда вы подадите на развод, не забудьте нанять не только юриста, но и программиста.