Распределение предметов без зависти (EF) — это проблема справедливого распределения предметов , в которой критерием справедливости является отсутствие зависти — каждый агент должен получить набор, который, по его мнению, не хуже, чем набор любого другого агента. [1] : 296–297
Поскольку элементы неделимы, назначение EF может не существовать. Самый простой случай — это когда есть один предмет и как минимум два агента: если предмет присвоить одному агенту, другой позавидует.
Один из способов добиться справедливости — использовать денежные переводы; см. Справедливое распределение предметов и денег . Когда денежные переводы не разрешены или нежелательны, существуют алгоритмы распределения, обеспечивающие различные виды послаблений.
Процедура подрезки находит полное распределение EF для двух агентов тогда и только тогда, когда такое распределение существует. Он требует, чтобы агенты ранжировали наборы предметов, но не требует информации о кардинальной полезности. Он работает всякий раз, когда отношения предпочтений агентов строго монотонны, но не требует допущения, что они являются адаптивными предпочтениями . В худшем случае агентам, возможно, придется ранжировать все возможные пакеты, поэтому время выполнения может быть экспоненциальным по количеству элементов.
Обычно людям проще ранжировать отдельные элементы, чем ранжировать пакеты. Предполагая, что у всех агентов есть адаптивные предпочтения , можно повысить ранжирование элементов до частичного ранжирования пакетов. Например, если ранжирование элементов равно w>x>y>z, то отзывчивость подразумевает, что {w,x}>{y,z} и {w,y}>{x,z}, но ничего не подразумевает. об отношении между {w,z} и {x,y}, между {x} и {y,z} и т. д.
Bouveret, Endriss и Lang [2] изучают алгоритмические вопросы нахождения распределения NEF/PEF с дополнительным условием эффективности, в частности, полнотой или NPE или PPE. В общем, PEF легко вычисляется, в то время как NEF сложно вычисляется.