Не-жадный алгоритм

В настоящее время существуют методы справедливого совместного использования ресурсов, на основе системы распределения. Наиболее известным является метод деления торта «Ты отрезаешь, я выбираю». Есть также алгоритмы, которые позволяют разделить торт между несколькими участниками так, что каждый должен быть доволен исходом в том смысле, что они чувствуют, что не могут съесть столько торта, сколько хотели, но, по крайней мере, они получили столько же, сколько и их «оппоненты».

Более сложной задачей, чем деление непрерывного ресурса, является задача распределения неделимых элементов среди группы людей, каждый из которых назначает свой набор значений для элементов. В новой статье Стивена Брамса (Нью-Йоркский университет), Д. Марка Килгура (университет Уилфрида Лорье) и Кристиана Клэмлера (Университет Граца), опубликованной в феврале 2014 года в «Notices of the American Mathematical Society» («Заметки Американского Математического сообщества»), излагается пара алгоритмов.

В первом уже известном алгоритме — ВТ (алгоритм был предложен Брамсом и Тейлором) — есть два игрока А и В, которые делают независимый выбор своих наиболее предпочтительных элементов в наборе элементов, которые пока не выделены. Если А и В выбирают два разных элемента, то каждый из них получит желаемое. Если они выбирают один и тот же элемент, то он помещается в спорную кучу (СР). Это продолжается до тех пор, пока все элементы не будут выделены или помещены в СР.

Представленный же алгоритм реализует не-жадное распределение (EF/Envy-free) в том смысле, что каждый игрок получает одинаковое количество элементов и каждый игрок предпочитает подмножество предметов, которым обладает.

Идея EF на самом деле довольно хитрая. В основном она сводится к тому, чтобы для каждого элемента, который есть у А, существует элемент у игрока В, который для него менее предпочтителен.
Можно сказать, что если для каждого элемента х, что есть у А, число элементов, принадлежащих В и которые А предпочитает х не больше, чем в аналогичном количестве элементов, которые есть у А и которые он предпочитает х.

Главным в EF является то, что нет никакого альтернативного решения, которое удовлетворило потребности обеих сторон, согласно их ранжированию.

Например, если ранжирование:

А: 1 2 3 4
В: 2 3 4 1

Затем с помощью алгоритма А получает 1 и В получает 2. В итоге получаем:

А: 3 4
В: 3 4

Теперь появляется камень преткновения, потому 3 переходит в CP, так же как и 4. Таким образом, окончательное распределение: А получает 1 и В получает 2 и два элемента помещаются в CP = {3,4}.
Этот алгоритм быстр, и это позволяет каждому человеку назначить рейтинг, который определяет, как будет протекать процесс распределения и, следовательно, учитывать изменения полезности: например, если вы не получите телевизор, нет никакого смысла в том, чтобы у вас была игровая консоль. Большая проблема алгоритма состоит в том, что он не всегда находит максимальное назначение EF.

В статье приведен несколько более сложный алгоритм, AL, который всегда найдет максимальное значение в том смысле, что нет другого EF распределения, что выделяет несколько элементов для игроков.
Алгоритм работает таким же образом, пока не появляется камень преткновения, когда он пытается найти распределение связанного с А или В элемента и другой элемент, который приведет к не-жадному распределению. Как именно это будет сделано, вопрос фактического поиска тестового распределения всех возможных пунктов. Для этого игроки должны назначить все свои рейтинги перед началом процедуры распределения.

Алгоритм работает за полиномиальное время, если вы хотите только одно максимальное распределение. Если вы хотите увидеть все возможные варианты, то время возрастет экспоненциально.

Чем большему количеству элементов игроки назначают истинные рейтинги, тем более сложный алгоритм будет находить максимальное EF распределение.

Интересно отметить, что, когда количество элементов увеличивается, вероятность полного назначения EF приближается к единице.

Плохая новость заключается в том, что алгоритм можно обмануть. Если вы лжете о своем рейтинге, то в конечном итоге это спровоцирует зависть. Тем не менее, как отмечают авторы, опасность заключается в том, что вы не будете с серьезностью подходить к решению задачи (так как распределение зависит от рейтинга другого игрока), то в конечном итоге окажетесь не в выигрышной позиции. Лучшая стратегия — играть честно и в конечном итоге получить не-жадное распределение.

«Во многих спорах, в том числе разводе и разделе имущества, только распределение, сопровождавшаяся получением примерно одинакового количества элементов будет восприниматься как справедливое. ВТ и AL предназначены именно для этого, особенно, когда они распределяют большую часть элементов, если не все из них. В то время как ВТ является образцом простоты, AL не намного сложнее применять, как было показано, что должно способствовать его принятию на практике как методики».

Так что в следующий раз, когда вы подадите на развод, не забудьте нанять помимо адвоката ещё и программиста.

Перевод статьи “An Envy-Free Algorithm”