Algoritmo de Birkhoff

El algoritmo de Birkhoff (también llamado algoritmo de Birkhoff-von-Neumann ) es un algoritmo para descomponer una matriz bistocástica en una combinación convexa de matrices de permutación . Fue publicado por Garrett Birkhoff en 1946. ^{[1] [2] : 36} Tiene muchas aplicaciones. Una de esas aplicaciones es para el problema de la asignación aleatoria justa : dada una asignación aleatoria de elementos, el algoritmo de Birkhoff puede descomponerla en una lotería de asignaciones deterministas.

Terminología

Una matriz bistocástica (también llamada: doblemente estocástica ) es una matriz en la que todos los elementos son mayores o iguales a 0 y la suma de los elementos en cada fila y columna es igual a 1. Un ejemplo es la siguiente matriz de 3 por 3: Una matriz de permutación es un caso especial de una matriz bistocástica, en la que cada elemento es 0 o 1 (por lo que hay exactamente un "1" en cada fila y cada columna). Un ejemplo es la siguiente matriz de 3 por 3: Una descomposición de Birkhoff (también llamada: descomposición de Birkhoff-von-Neumann ) de una matriz bistocástica es una presentación de esta como una suma de matrices de permutación con pesos no negativos. Por ejemplo, la matriz anterior se puede presentar como la siguiente suma: El algoritmo de Birkhoff recibe como entrada una matriz bistocástica y devuelve como salida una descomposición de Birkhoff. $${\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}}}$$

Herramientas

Un conjunto de permutaciones de una matriz X de n por n es un conjunto de n entradas de X que contiene exactamente una entrada de cada fila y de cada columna. Un teorema de Dénes Kőnig dice que: ^{[3] [2] : 35}

Cada matriz bistocástica tiene un conjunto de permutaciones en el que todas las entradas son positivas.

El gráfico de positividad de una matriz n por n X es un gráfico bipartito con 2 n vértices, en el que los vértices de un lado son n filas y los vértices del otro lado son las n columnas, y hay una arista entre una fila y una columna si y solo si la entrada en esa fila y columna es positiva. Un conjunto de permutaciones con entradas positivas es equivalente a una coincidencia perfecta en el gráfico de positividad. Una coincidencia perfecta en un gráfico bipartito se puede encontrar en tiempo polinomial, por ejemplo, utilizando cualquier algoritmo para la coincidencia de cardinalidad máxima . El teorema de Kőnig es equivalente a lo siguiente:

El gráfico de positividad de cualquier matriz bistocástica admite un emparejamiento perfecto.

Una matriz se denomina bistocástica escalada si todos sus elementos no son negativos y la suma de cada fila y columna es igual a c , donde c es una constante positiva. En otras palabras, es c multiplicado por una matriz bistocástica. Dado que el gráfico de positividad no se ve afectado por la escala:

El gráfico de positividad de cualquier matriz bistocástica escalada admite un emparejamiento perfecto.

Algoritmo

El algoritmo de Birkhoff es un algoritmo voraz : busca con avidez las coincidencias perfectas y las elimina de la coincidencia fraccionaria. Funciona de la siguiente manera. ^{[4] : ap.B}

1. Sea i = 1.
2. Construya la gráfica de positividad G _X de X .
3. Encuentre una coincidencia perfecta en G _X , correspondiente a un conjunto de permutaciones positivas en X .
4. Sea z [ i ] > 0 la entrada más pequeña en el conjunto de permutación.
5. Sea P [ i ] una matriz de permutación con 1 en el conjunto de permutación positiva.
6. Sea X := X − z [ i ] P [ i ].
7. Si X contiene elementos distintos de cero, sea i = i + 1 y volvamos al paso 2.
8. De lo contrario, devuelve la suma: z [1] P [1] + ... + z [2] P [2] + ... + z [ i ] P [ i ].

El algoritmo es correcto porque, después del paso 6, la suma en cada fila y cada columna disminuye en z [ i ]. Por lo tanto, la matriz X permanece escalada-bistocástica. Por lo tanto, en el paso 3, siempre existe una correspondencia perfecta.

Complejidad en tiempo de ejecución

Mediante la selección de z [ i ] en el paso 4, en cada iteración al menos un elemento de X se convierte en 0. Por lo tanto, el algoritmo debe terminar después de como máximo n ² pasos. Sin embargo, el último paso debe convertir simultáneamente n elementos en 0, por lo que el algoritmo termina después de como máximo n ² − n + 1 pasos, lo que implica . ${\displaystyle O(n^{2})}$

En 1960, Joshnson, Dulmage y Mendelsohn demostraron que el algoritmo de Birkhoff en realidad termina después de como máximo n ² − 2 n + 2 pasos, lo cual es estricto en general (es decir, en algunos casos pueden requerirse matrices de permutación n ² − 2 n + 2). ^[5]

Aplicación en división justa

En el problema de asignación aleatoria justa , hay n objetos y n personas con diferentes preferencias sobre los objetos. Se requiere dar un objeto a cada persona. Para lograr la equidad, la asignación es aleatoria: para cada par (persona, objeto), se calcula una probabilidad, de modo que la suma de probabilidades para cada persona y para cada objeto sea 1. El procedimiento probabilístico-serial puede calcular las probabilidades de modo que cada agente, mirando la matriz de probabilidades, prefiera su fila de probabilidades sobre las filas de todas las demás personas (esta propiedad se llama ausencia de envidia ). Esto plantea la pregunta de cómo implementar esta asignación aleatoria en la práctica. Uno no puede simplemente aleatorizar para cada objeto por separado, ya que esto puede dar como resultado asignaciones en las que algunas personas obtienen muchos objetos mientras que otras no obtienen ninguno.

En este caso, resulta de utilidad el algoritmo de Birkhoff. La matriz de probabilidades calculada por el algoritmo probabilístico serial es bistocástica. El algoritmo de Birkhoff puede descomponerla en una combinación convexa de matrices de permutación. Cada matriz de permutación representa una asignación determinista, en la que cada agente recibe exactamente un objeto. El coeficiente de cada una de estas matrices se interpreta como una probabilidad; en función de las probabilidades calculadas, es posible elegir una asignación al azar e implementarla.

Extensiones

Se ha demostrado que el problema de calcular la descomposición de Birkhoff con el número mínimo de términos es NP-difícil , pero se conocen algunas heurísticas para calcularlo. ^{[6] [7]} Este teorema se puede extender para la matriz estocástica general con matrices de transición deterministas. ^[8]

Budish, Che, Kojima y Milgrom ^[9] generalizan el algoritmo de Birkhoff a matrices no cuadradas , con algunas restricciones en las asignaciones factibles. También presentan un algoritmo de descomposición que minimiza la varianza en los valores esperados.

Vazirani ^[10] generaliza el algoritmo de Birkhoff a gráficos no bipartitos .

Valls et al. ^[11] demostraron que es posible obtener una descomposición aproximada con permutaciones . ${\displaystyle \epsilon }$ ${\displaystyle O(\log(1/\epsilon ^{2}))}$

Véase también

• Politopo de Birkhoff
• Descomposición de Birkhoff (desambiguación)
• Lema de Gordan : establece que ciertos conjuntos de vectores pueden ser generados por un subconjunto finito.

Referencias

1. Birkhoff, Garrett (1946), "Tres observaciones sobre el álgebra lineal", Univ. Nac. Tucumán. Revista A. , 5 : 147–151, SEÑOR  0020547.
2. Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, Sr.  0859549
3. Kőnig, Dénes (1916), "Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére", Matematikai és Természettudományi Értesítő , 34 : 104-119.
4. Aziz, Haris (2020). "Lograr simultáneamente la equidad ex ante y ex post". arXiv : 2004.02554 [cs.GT].
5. Johnson, Diane M.; Dulmage, AL; Mendelsohn, NS (1960-09-01). "Sobre un algoritmo de G. Birkhoff concerniente a matrices doblemente estocásticas". Canadian Mathematical Bulletin . 3 (3): 237–242. doi : 10.4153/cmb-1960-029-5 . ISSN  0008-4395.
6. Dufossé, Fanny; Uçar, Bora (mayo de 2016). "Notas sobre la descomposición de Birkhoff–von Neumann de matrices doblemente estocásticas" (PDF) . Álgebra lineal y sus aplicaciones . 497 : 108–115. doi : 10.1016/j.laa.2016.02.023 .
7. Dufossé, Fanny; Kaya, Kamer; Panagiotas, Ioannis; Uçar, Bora (2018). "Notas adicionales sobre la descomposición de Birkhoff–von Neumann de matrices doblemente estocásticas" (PDF) . Álgebra lineal y sus aplicaciones . 554 : 68–78. doi :10.1016/j.laa.2018.05.017. ISSN  0024-3795. S2CID  240083300.
8. Ye, Felix X.-F.; Wang, Yue; Qian, Hong (2016). "Dinámica estocástica: cadenas de Markov y transformaciones aleatorias". Sistemas dinámicos discretos y continuos - Serie B . 21 (7): 2337–2361. doi : 10.3934/dcdsb.2016050 .
9. Budish, Eric; Che, Yeon-Koo; Kojima, Fuhito; Milgrom, Paul (1 de abril de 2013). "Diseño de mecanismos de asignación aleatoria: teoría y aplicaciones". American Economic Review . 103 (2): 585–623. CiteSeerX 10.1.1.649.5582 . doi :10.1257/aer.103.2.585. ISSN  0002-8282. 
10. Vazirani, Vijay V. (14 de octubre de 2020). "Una extensión del teorema de Birkhoff-von Neumann a grafos no bipartitos". arXiv : 2010.05984 [cs.DS].
11. Valls, Victor; Iosifidis, Georgios; Tassiulas, Leandros (diciembre de 2021). "Revisión de la descomposición de Birkhoff: programación dispersa para conmutadores de circuitos de alta velocidad" (PDF) . Transacciones IEEE/ACM sobre redes . 29 : 2399–2412. doi :10.1109/TNET.2021.3088327.