Максимальное по рангу распределение

Максимальное по рангу распределение (МР, англ. Rank-maximal (RM) allocation) — это правило для справедливого дележа неделимых предметов. Предположим, что нам нужно распределить несколько предметов между некоторым количеством людей. Каждый человек может упорядочить предметы от лучших к худшим. МР-правило говорит, что мы должны дать как можно большему количеству людей лучший предмет (№1 в списке). Затем мы должны дать как можно большему количеству людей второй по значимости предмет (№2 в списке), и так далее.

В специальном случае, в котором каждое лицо должно получить один предмет (например, если «предметами» являются некоторые действия, и каждое действие должен выполнить один человек), задача называется паросочетанием максимального ранга или жадным паросочетанием.

Идея похожа на идею разрезания торта согласно полезности, где целью является максимизация суммы полезностей всех участников. Однако правило полезности работает с кардиналистскими (количествеными) функциями полезности, в то время как МР-правило работает с ординалистскими полезностями (ранжированием).

Определения

Имеется несколько предметов и несколько агентов. Каждый агент имеет линейное упорядочение предметов. Агенты могут не различать по ценности некоторые предметы. Для каждого агента мы можем разбить предметы на классы эквивалентности, которые содержат предметы одного ранга. Например, если отношением предпочтения Алисы является x > y, z > w, это означает, что для Алисы лучшим выбором служит x, который лучше всех остальных предметов. Затем Алиса предпочитает y и z, которые в её глазах имеют одинаковую ценность, но не настолько ценны, как x. На последнем месте у Алисы стоит w, который она считает худшим из всех предметов.

Для любого распределения предметов агентам мы строим его ранговый вектор следующим образом. Элемент №1 в векторе равен общему числу предметов, которые стоят на первом месте для владельцев, элемент №2 равен общему числу предметов, которые для владельцев стоят на втором месте, и так далее.

Распределение максимального ранга — это распределение, в котором ранговый вектор максимален (в лексикографическом порядке).

Пример

Три предмета, x, y и z, следует разделить между тремя агентами, ранжирование у которых следующее:

• Алиса: x > y > z
• Боб: x > y > z
• Карл: y > x > z

В распределении (x, y, z) Алиса получает первый элемент (x), Боб получает второй элемент (y), а Карл получает третий элемент (z). Ранговый вектор равен тогда (1,1,1).

В распределении (x,z,y), Алиса и Карл получают предметы с первого места, а Боб получает предмет, который для него стоит на 3-м месте. Ранговый вектор тогда равен (2,0,1), который лексикографически больше вектора (1,1,1) – он даёт большему числу людей их выбор 1-го места.

Легко проверить, что никакое распределение не даёт лексикографически больший ранговый вектор. Следовательно, распределение (x,z,y) максимально по рангу. Аналогично, распределение (z,x,y) максимально по рангу – оно даёт тот же самый ранговый вектор (2,0,1).

Алгоритмы

МР-паросочетания первым изучал Роберт Ирвинг, который называл их жадными паросочетаниями. Он предложил алгоритм, который находит МР-паросочетание за время $O(n^{2}c^{3})$, где n — число агентов, а c — наибольшая длина списка предпочтений агента.

Позднее был найден алгоритм, который работает за время $O(m\cdot \min(n,C{\sqrt {n}}))$, где m — полная длина всех списков предпочтения (полное число рёбер в графе), а C — максимальный ранг предмета, использованного в МР-паросочетнании (то есть максимальное число ненулевых элементов в оптимальном векторе рангов).

Отличное от этого решение с помощью паросочетания максимального веса достигает похожего времени работы — $O(m\cdot \min(n+C,C{\sqrt {n}}))$.

Варианты

Задача имеет несколько вариантов.

1. В МР-паросочетании максимальной кардинальности целью является поиск среди всех различных МР-паросочетаний паросочетание с максимальным числом сочетаний.

2. В справедливом паросочетании целью является поиск паросочетания максимальной кардинальности, которое использует минимальное число рёбер ранга r, затем минимальное число рёбер ранга r−1 и так далее.

Как максимальное по размеру МР-паросочетание, так и справедливое паросочетание, могут быть найдены путём сведение к паросочетанию максимального веса.

3. В задаче емкостного МР-паросочетания каждый агент имеет верхнюю ёмкость, которая определяет верхнюю границу общего числа предметов, которые можно передать агенту. Каждый предмет имеет верхнюю квоту, определяющую верхнюю границу числа различных агентов, которым предмет может быть передан. Задачу исследовали Мелхорн и Михаил, которые предложили алгоритм со временем работы $O(Cnm\log(n^{2}/m)\log(n))$. Существует улучшенный алгоритм со временем работы $O(m\cdot \min(B,C{\sqrt {B}}))$, где B — минимум сумм квот агентов и сумм квот предметов. Он основывается на расширении декомпозиции Галаи — Эдмондса многорёберных паросочетний .

См. также

• Справедливое распределение объектов
• Задача о марьяже
• Паросочетание без зависти