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

Распределение по максимальному рангу (RM) — это правило справедливого распределения неделимых предметов. Предположим, нам нужно распределить некоторые предметы среди людей. Каждый человек может ранжировать предметы от лучшего к худшему. Правило RM гласит, что мы должны дать как можно большему количеству людей их лучший (#1) предмет. При этом мы должны дать как можно большему количеству людей их следующий лучший (#2) предмет и так далее.

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

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

Определение

Есть несколько предметов и несколько агентов. У каждого агента есть общий порядок по предметам. Агенты могут быть безразличны к некоторым предметам; для каждого агента мы можем разбить предметы на классы эквивалентности, содержащие предметы одинакового ранга. Например, если отношение предпочтений Алисы x > y,z > w , это означает, что первый выбор Алисы — x, который лучше для нее, чем все остальные предметы; второй выбор Алисы — y и z, которые одинаково хороши в ее глазах, но не так хороши, как x; и третий выбор Алисы — w, который она считает хуже, чем все остальные предметы.

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

Максимально ранговое распределение — это такое распределение, при котором вектор ранга максимален в лексикографическом порядке.

Пример

Три элемента, xy и z, необходимо разделить между тремя агентами, рейтинги которых следующие:

Алиса: х > у > я
Боб: х > у > z
Карл: у > х > я

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

В распределении ( x , z , y ) и Алиса, и Карл получают свой первый выбор, а Боб получает свой третий выбор. Таким образом, вектор ранга равен (2,0,1), что лексикографически выше, чем (1,1,1) — это дает большему количеству людей их первый выбор.

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

Алгоритмы

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

Позже был найден улучшенный алгоритм, который работает за время , где m — общая длина всех списков предпочтений (общее количество ребер в графе), а C — максимальный ранг элемента, используемого в сопоставлении RM (т. е. максимальное количество ненулевых элементов в оптимальном векторе ранга). ^[2] Алгоритм сводит задачу к сопоставлению с максимальной мощностью . Интуитивно мы хотели бы сначала найти сопоставление с максимальной мощностью, используя только ребра ранга 1; затем расширить это сопоставление до сопоставления с максимальной мощностью, используя только ребра рангов 1 и 2; затем расширить это сопоставление до сопоставления с максимальной мощностью, используя только ребра рангов 1, 2 и 3; и так далее. Проблема в том, что если мы выберем «неправильное» максимальное по мощности сопоставление для ранга 1, то мы можем пропустить оптимальное сопоставление для ранга 2. Алгоритм ^[2] решает эту проблему с помощью разложения Дульмейджа–Мендельсона , которое представляет собой разложение, использующее максимальное по мощности сопоставление, но не зависящее от выбранного сопоставления (разложение одинаково для каждого выбранного максимально возможного сопоставления). Он работает следующим образом. $O(m\cdot \min(n,C{\sqrt {n}}))$

Пусть G ₁ — подграф G , содержащий только ребра ранга 1 (наивысшего ранга).
Найдите паросочетание максимальной мощности в G ₁ и используйте его для нахождения разложения G ₁ на E ₁ , O ₁ и U ₁ .
Одним из свойств разложения является то, что каждое паросочетание максимальной мощности в G ₁ насыщает все вершины в O ₁ и U ₁ . Следовательно, в паросочетании максимального ранга все вершины в O ₁ и U ₁ смежны с ребром ранга 1. Поэтому мы можем удалить из графа все ребра с рангом 2 или выше, смежные с любой из этих вершин.
Другим свойством разложения является то, что любое паросочетание максимальной мощности в G ₁ содержит только ребра E ₁ -O ₁ и U ₁ -U _1. Следовательно, мы можем удалить все остальные ребра (ребра O ₁ -O ₁ и O ₁ -U ₁ ) из графа.
Добавить к G ₁ все ребра со следующим по рангу рангом. Если таких ребер нет, остановиться. Иначе вернуться к шагу 2.

Другое решение, использующее паросочетания максимального веса , достигает аналогичного времени выполнения: . ^[3] $O(m\cdot \min(n+C,C{\sqrt {n}}))$

Варианты

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

1. В RM-сопоставлении с максимальной мощностью цель состоит в том, чтобы среди всех различных RM-сопоставлений найти то, которое имеет максимальное количество сопоставлений.

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

Как RM-сопоставление с максимальной мощностью, так и честное сопоставление могут быть найдены путем сведения к сопоставлению с максимальным весом. ^[3]

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

Смотрите также

Ссылки

^ Ирвинг, Роберт В. (2003). Жадные совпадения . Университет Глазго. стр. Tr–2003–136. CiteSeerX 10.1.1.119.1747 .{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ ab Irving, Robert W.; Kavitha, Telikepalli ; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E. (1 октября 2006 г.). "Rank-maximal Matchings". ACM Trans. Algorithms . 2 (4): 602–610. doi :10.1145/1198513.1198520. ISSN 1549-6325.
^ ab Michail, Dimitrios (10 декабря 2007 г.). «Сокращение рангового максимального соответствия до максимального веса». Теоретическая информатика . 389 (1): 125–132. doi : 10.1016/j.tcs.2007.08.004 . ISSN 0304-3975.
^ Курт Мельхорн и Димитриос Михаил (2005). «Сетевые проблемы с неполиномиальными весами и их применение».
^ Палух, Катажина (22 мая 2013 г.). «Capacitated Rank-Maximal Matchings». Алгоритмы и сложность . Lecture Notes in Computer Science. Vol. 7878. Springer, Berlin, Heidelberg. pp. 324–335. doi :10.1007/978-3-642-38233-8_27. ISBN 978-3-642-38232-1.