Максимальный ранг распределения - Rank-maximal allocation

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

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

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

Определение

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

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

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

пример

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

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

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

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

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

Алгоритмы

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

Позже был найден улучшенный алгоритм, работающий во времени. ${\displaystyle O(m\cdot \min(n,C{\sqrt {n}}))}$, где м - общая длина всех списков предпочтений (общее количество ребер в графе), а C - это максимальный ранг элемента, используемого в сопоставлении RM (т.е. максимальное количество ненулевых элементов в оптимальном векторе рангов).^[2]

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

Варианты

У проблемы есть несколько вариантов.

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

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

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

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

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

• Справедливое назначение товара
• Стабильное соответствие
• Соответствие без зависти
• Приоритетное соответствие

Рекомендации

1. Ирвинг, Роберт В. (2003). Жадные соответствия. Университет Глазго. С. Тр – 2003–136. CiteSeerX  10.1.1.119.1747.
2. Ирвинг, Роберт В .; Кавита, Теликепалли; Мельхорн, Курт; Михаил, Димитриос; Палуч, Катажина Е. (1 октября 2006 г.). «Соответствия с максимальным рангом». ACM Trans. Алгоритмы. 2 (4): 602–610. Дои:10.1145/1198513.1198520. ISSN  1549-6325.
3. Михаил, Димитриос (10 декабря 2007 г.). «Снижение ранга-максимального соответствия весовому максимальному». Теоретическая информатика. 389 (1): 125–132. Дои:10.1016 / j.tcs.2007.08.004. ISSN  0304-3975.
4. Курт Мельхорн и Димитриос Михаил (2005). «Сетевые задачи с неполиномиальными весами и приложения».
5. Палуч, Катажина (22 мая 2013 г.). Максимальные ранговые соответствия. Алгоритмы и сложность. Конспект лекций по информатике. 7878. Шпрингер, Берлин, Гейдельберг. С. 324–335. Дои:10.1007/978-3-642-38233-8_27. ISBN  978-3-642-38232-1.