Справедливые дележи с делимыми и неделимыми пунктами

NRU Higher School of Economics , 2009. No. 05.

Рубчинский А. А.

Рассмотрена задача справедливого дележа при наличии как делимых, так и неделимых пунктов. Формально описано множество всех дележей; показано, что множество справедливых (в определении Брамса и Тэйлора) дележей, в отличие от случая только делимых пунктов, существует не всегда. Найдены необходимые и достаточные условия существования пропорциональных и равноценных дележей. Введены три взаимосвязанных модификации понятия справедливого дележа – максиминно, равномерно и равноценно справедливые дележи. Предложен вычислительно эффективный алгоритм нахождения всех этих дележей. Алгоритм включает многократное решение целочисленных задач типа задачи о рюкзаке в качестве одного из основных шагов. Утверждения статьи проиллюстрированы разнообразными примерами.

Ключевые слова: пропорциональные дележи, справедливые дележи