Алгоритм Биркгофа

Алгоритм Биркгофа (также называемый алгоритмом Биркгофа-фон-Неймана ) — это алгоритм разложения бистохастической матрицы в выпуклую комбинацию матриц перестановок . Он был опубликован Гарретом Биркгофом в 1946 году. У него много приложений. Одним из таких приложений является задача справедливого случайного распределения : учитывая рандомизированное распределение элементов, алгоритм Биркгофа может разложить его на лотерею с детерминированным распределением.

Терминология

Бистохастическая матрица (также называемая дважды стохастической ) — это матрица, в которой все элементы больше или равны 0, а сумма элементов в каждой строке и столбце равна 1. Примером является следующая матрица 3х3. :

$${\begin{pmatrix}0.2&0.3&0.5\\0.6&0.2&0.2\\0.2&0.5&0.3\end{pmatrix}}$$

Матрица перестановок — это частный случай бистохастической матрицы, в которой каждый элемент равен 0 или 1 (поэтому в каждой строке и каждом столбце находится ровно одна «1»). Примером является следующая матрица 3х3:

$${\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}$$

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

$$0.2{\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}+0.2{\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}+0.1{\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}+0.5{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}$$

Алгоритм Биркгофа получает на вход бистохастические матрицы и возвращает на выходе разложение Биркгофа.

Инструменты

Набор перестановок матрицы n размера n X x — это набор из n элементов матрицы X, содержащий ровно по одному элементу из каждой строки и каждого столбца. Теорема Денеша Кенига гласит, что:

Каждая бистохастическая матрица имеет набор перестановок, в котором все элементы положительны.

Граф положительности матрицы nxn размером , в строк, а X представляет собой двудольный граф с 2n вершинами котором вершины с одной стороны представляют собой n вершины с другой стороны — n столбцов, и существует ребро между строку и столбец тогда и только тогда, когда запись в этой строке и столбце положительна. Набор перестановок с положительными элементами эквивалентен идеальному паросочетанию в графе положительности. Идеальное паросочетание в двудольном графе можно найти за полиномиальное время, например, используя любой алгоритм сопоставления максимальной мощности . Теорема Кенига эквивалентна следующему:

Граф положительности любой бистохастической матрицы допускает идеальное сопоставление.

Матрица называется масштабно-бистохастической, если все ее элементы неотрицательны, а сумма каждой строки и столбца равна c , где c — некоторая положительная константа. Другими словами, это в c раз бистохастическая матрица. Поскольку на график положительности масштабирование не влияет:

Граф положительности любой масштабно-бистохастической матрицы допускает идеальное сопоставление.

Алгоритм

Алгоритм Биркгофа — жадный алгоритм : он жадно находит идеальные совпадения и удаляет их из дробного сопоставления. Это работает следующим образом.

1. Пусть я = 1.
2. Постройте граф положительности G _X для X .
3. Найдите идеальное паросочетание в G _X , соответствующее положительному множеству перестановок в X .
4. Пусть z [ i ] > 0 будет наименьшим элементом в наборе перестановок.
5. Пусть P [ i ] будет матрицей перестановок с 1 в положительном наборе перестановок.
6. Пусть X := X − z [ i ] P [ i ].
7. Если X содержит ненулевые элементы, пусть i = i + 1 и возвращаемся к шагу 2.
8. В противном случае верните сумму: z [1] P [1] + ... + z [2] P [2] + ... + z [ i ] P [ i ].

Алгоритм правильный, поскольку после шага 6 сумма в каждой строке и каждом столбце уменьшается на z [ i ]. Следовательно, матрица X остается масштабно-бистохастической. Следовательно, на шаге 3 всегда существует идеальное паросочетание.

Сложность во время выполнения

При выборе z [ i ] на шаге 4 на каждой итерации хотя бы один элемент X становится равным 0. Следовательно, алгоритм должен завершиться не более чем через n ² шаги. Однако последний шаг должен одновременно сделать n элементов равными 0, поэтому алгоритм завершается не более чем через n ² − n + 1 шагов, что означает $O(n^{2})$.

В 1960 году Джошнсон, Дулмейдж и Мендельсон показали, что алгоритм Биркгофа фактически завершается через не более n ² − 2 n + 2 шагов, что в общем случае является трудным (т. е. в некоторых случаях n ² − 2 n + 2 матриц перестановок).

Заявление в ярмарочный отдел

В задаче о честном случайном назначении имеется n объектов и n людей с разными предпочтениями по отношению к этим объектам. Каждому человеку требуется вручить предмет. Для достижения справедливости распределение рандомизировано: для каждой пары (человек, объект) рассчитывается вероятность, такая, что сумма вероятностей для каждого человека и для каждого объекта равна 1. Вероятностно-последовательная процедура может вычислить вероятности так, что каждый агент, глядя на матрицу вероятностей, предпочитает свой ряд вероятностей строкам всех остальных людей (это свойство называется свободой от зависти ). Возникает вопрос, как реализовать такое рандомизированное распределение на практике? Нельзя просто рандомизировать каждый объект отдельно, поскольку это может привести к распределению, при котором некоторые люди получат много объектов, а другие не получат объектов.

Здесь пригодится алгоритм Биркгофа. Матрица вероятностей, рассчитанная вероятностно-последовательным алгоритмом, является бистохастической. Алгоритм Биркгофа может разложить его на выпуклую комбинацию матриц перестановок. Каждая матрица перестановок представляет собой детерминированное назначение, при котором каждый агент получает ровно один объект. Коэффициент каждой такой матрицы интерпретируется как вероятность; на основе рассчитанных вероятностей можно случайным образом выбрать одно задание и реализовать его.

Расширения

задача вычисления разложения Биркгофа с минимальным количеством членов Было показано, что является NP-трудной , но известны некоторые эвристики для ее вычисления. Эту теорему можно распространить на общую стохастическую матрицу с детерминированными матрицами перехода.

Будиш, Че, Кодзима и Милгром обобщить алгоритм Биркгофа на неквадратные матрицы с некоторыми ограничениями на допустимые назначения. Они также представляют алгоритм декомпозиции, который минимизирует отклонение ожидаемых значений.

Министр обобщает алгоритм Биркгофа на недвудольные графы .

Валлс и др. показало, что можно получить $\epsilon$- приближенное разложение с $O(\log(1/\epsilon ^{2}))$ перестановки.

См. также

• Многогранник Биркгофа
• Разложение Биркгофа (значения)
• Лемма Гордана - утверждает, что определенные наборы векторов могут быть порождены конечным подмножеством.