Конкурентные рыночные механизмы в задачах справедливого распределения неделимых товаров

Данная работа посвящена анализу применимости методов из теории справедливого распределения делимых благ к задачам с неделимыми благами. Цель справедливого распределения – это достижение ситуации, когда каждый из участников доволен полученной долей с учетом своих индивидуальных предпочтений. Алгоритмы справедливого распределения важны тем, что могут использоваться в реальной жизни, например, при разделении имущества в бракоразводном процессе. Целью работы стал анализ одного из существующих методов распределения делимых ресурсов, т.н. конкурентное равновесие с равными доходами (Competitive Equilibrium with Equal Incomes, CEEI) и характеризация ситуации, в которых данный метод будет давать решение, применимое для задачи неделимых товаров. Назовем дележ совершенным, если для любого агента доля каждого полученного им блага принимает значения 1 или 0, т.е. агент либо получает это благо целиком, либо не получает совсем. Такие дележи можно отождествить с дележами в задачах с неделимыми благами. При помощи компьютерного моделирования находится вероятность того, что метод CEEI дает совершенный дележ. Важность подобной ситуации определяется тем, что поиск дележей с хорошими свойствами в случае неделимых благ представляет сложную задачу: при решении может возникать зависть между агентами, а также алгоритмы часто вычислительно неэффективны. При использовании метода CEEI поиск решения осуществляется за малое число операций, а дележ обладает такими важными свойствами как эффективность и отсутствие зависти. Компьютерная реализация алгоритма и расчет вероятности получения совершенного дележа с помощью метода Монте-Карло показали, что множество задач с неделимыми благами, для которых вышеупомянутый метод дает решение, представляет собой значительную долю от всех задач. Причем, если дополнительно известно, что в задаче предпочтения агентов различны в достаточной степени, а число благ велико, то вероятность того, что данный алгоритм решит задачу дележа близко к 1.