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

Алгоритм Биркгофа представляет собой алгоритм разложения бистохастическая матрица в выпуклую комбинацию матрицы перестановок. Это было опубликовано Гаррет Биркофф в 1946 г.^[1][2]:36 У него много приложений. Одно из таких приложений предназначено для решения проблемы справедливое случайное распределение: учитывая рандомизированное распределение предметов, алгоритм Биркгофа может разложить его на лотерею по детерминированному распределению.

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

А бистохастическая матрица (также называемый: двустохастический) представляет собой матрицу, в которой все элементы больше или равны 0, а сумма элементов в каждой строке и столбце равна 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}}}$$

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

$${\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}}}$$

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

Инструменты

А набор перестановок из п-к-п матрица Икс это набор п записи Икс содержащий ровно одну запись из каждой строки и каждого столбца. Теорема Денес Кёниг Говорит, что:^[3][2]:35

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

В граф положительности из п-к-п матрица Икс это двудольный граф с 2п вершины, в которых вершины на одной стороне п ряды и вершины на другой стороне - это п столбцы, и есть край между строкой и столбцом, если запись в этой строке и столбце положительна. Набор перестановок с положительными элементами эквивалентен идеальное соответствие в графе положительности. Идеальное соответствие в двудольном графе может быть найдено за полиномиальное время, например используя любой алгоритм для максимальное соответствие количества элементов. Knig Теорема эквивалентна следующему:

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

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

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

Алгоритм

Используя указанные выше инструменты, алгоритм Биркгофа работает следующим образом.^{[4]:приложение B}

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

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

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

Подбором z[я] на шаге 4 на каждой итерации хотя бы один элемент Икс становится 0. Следовательно, алгоритм должен завершиться не позднее, чем через п² шаги. Однако последний шаг должен одновременно сделать п элементов 0, поэтому алгоритм заканчивается не более чем через п² − п + 1 ступень.

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

Заявка на участие в ярмарке

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

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

Расширения

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

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

• Многогранник Биркгофа
• Разложение Биркгофа (значения)

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

1. Биркофф, Гарретт (1946), "Tres observaciones sobre el algebra lineal [Три наблюдения по линейной алгебре]", Univ. Nac. Тукуман. Ревиста А., 5: 147–151, МИСТЕР  0020547.
2. Ловас, Ласло; Пламмер, М. (1986), Теория соответствия, Анналы дискретной математики, 29, Северная Голландия, ISBN  0-444-87916-1, МИСТЕР  0859549
3. Кениг, Денес (1916), "Gráfok és alkalmazásuk aterminánsok és halmazok elméletére", Matematikai és Természettudományi Értesítő, 34: 104–119.
4. Азиз, Харис (2020). «Одновременное достижение справедливости ex-ante и ex-post». arXiv:2004.02554 [cs.GT ].
5. Джонсон, Дайан М .; Dulmage, A. L .; Мендельсон, Н. С. (1 сентября 1960 г.). «Об одном алгоритме Г. Биркгофа о двояко стохастических матрицах». Канадский математический бюллетень. 3 (3): 237–242. Дои:10.4153 / cmb-1960-029-5. ISSN  0008-4395.
6. Дюфосе, Фанни; Учар, Бора (май 2016 г.). "Заметки о разложении Биркгофа – фон Неймана дважды стохастических матриц" (PDF). Линейная алгебра и ее приложения. 497: 108–115. Дои:10.1016 / j.laa.2016.02.023.
7. Дюфосе, Фанни; Кая, Камер; Панайотас, Иоаннис; Учар, Бора (2018). «Дальнейшие заметки о разложении Биркгофа – фон Неймана дважды стохастических матриц» (PDF). Линейная алгебра и ее приложения. 554: 68–78. Дои:10.1016 / j.laa.2018.05.017. ISSN  0024-3795.
8. Ye, Феликс X.-F .; Ван, Юэ; Цянь, Хун (2016). «Стохастическая динамика: цепи Маркова и случайные преобразования». Дискретные и непрерывные динамические системы - серия B. 21 (7): 2337–2361. Дои:10.3934 / dcdsb.2016050.