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

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

Бистохастическая матрица (также называемая: дважды стохастическая ) — это матрица, в которой все элементы больше или равны 0, а сумма элементов в каждой строке и столбце равна 1. Примером может служить следующая матрица 3 на 3: Матрица перестановок — это особый случай бистохастической матрицы, в которой каждый элемент равен 0 или 1 (то есть в каждой строке и каждом столбце есть ровно одна «1»). Примером может служить следующая матрица 3 на 3: Разложение Биркгофа ( также называемое: разложение Биркгофа-фон-Неймана ) бистохастической матрицы — это представление ее в виде суммы матриц перестановок с неотрицательными весами. Например, указанную выше матрицу можно представить в виде следующей суммы: Алгоритм Биркгофа получает в качестве входных данных бистохастическую матрицу и возвращает в качестве выходных данных разложение Биркгофа.$${\displaystyle {\begin{pmatrix}0.2&0.3&0.5\\0.6&0.2&0.2\\0.2&0.5&0.3\end{pmatrix}}}$$$${\displaystyle {\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}}$$$${\displaystyle 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}}}$$

Набор перестановок матрицы X размером n на n — это набор из n элементов матрицы X , содержащий ровно один элемент из каждой строки и из каждого столбца. Теорема Денеша Кёнига гласит, что: ^{[3] [2] : 35}

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

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

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

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

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

Алгоритм Биркгофа — жадный алгоритм : он жадно находит идеальные паросочетания и удаляет их из дробного паросочетания. Он работает следующим образом. ^{[4] : app.B}

1. Пусть i = 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 шагов, что подразумевает .${\displaystyle O(n^{2})}$

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

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

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

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

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

Вазирани ^[10] обобщает алгоритм Биркгофа на недвудольные графы .

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

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