Birkhoff algoritm

Birkhoffs algoritm (även kallad Birkhoff-von-Neumann-algoritmen ) är en algoritm för att sönderdela en bistokastisk matris till en konvex kombination av permutationsmatriser . Den publicerades av Garrett Birkhoff 1946. Den har många tillämpningar. En sådan applikation är för problemet med rättvis slumpmässig tilldelning : givet en randomiserad tilldelning av objekt kan Birkhoffs algoritm bryta ner den i ett lotteri om deterministiska tilldelningar.

Terminologi

En bistokastisk matris (även kallad: dubbelstokastisk ) är en matris där alla element är större än eller lika med 0 och summan av elementen i varje rad och kolumn är lika med 1. Ett exempel är följande 3-av-3-matris :

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

En permutationsmatris är ett specialfall av en bistokastisk matris, där varje element är antingen 0 eller 1 (så det finns exakt en "1" i varje rad och varje kolumn). Ett exempel är följande 3-av-3-matris:

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

En Birkhoff-nedbrytning (även kallad: Birkhoff-von-Neumann-nedbrytning ) av en bistokastisk matris är en presentation av den som en summa av permutationsmatriser med icke-negativa vikter. Till exempel kan ovanstående matris presenteras som följande summa:

$$0.2{\begin{pmatrix}0&1&0\\0&0&1\\1&0&0}\}{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}}$$

Birkhoffs algoritm tar emot som indata en bistokastisk matris och returnerar som utdata en Birkhoff-sönderdelning.

Verktyg

En permutationsuppsättning av en n -by- n matris X är en uppsättning av n poster av X som innehåller exakt en post från varje rad och från varje kolumn. En teorem av Dénes Kőnig säger att:

Varje bistokastisk matris har en permutationsuppsättning där alla poster är positiva.

Positivitetsgrafen för en n -by- n matris X är en tvådelad graf med 2 n hörn, där hörnen på ena sidan är n rader och hörnen på den andra sidan är de n kolumnerna , och det finns en kant mellan en rad och en kolumn om posten på den raden och kolumnen är positiv. En permutationsuppsättning med positiva poster motsvarar en perfekt matchning i positivitetsgrafen. En perfekt matchning i en tvådelad graf kan hittas i polynomtid, t.ex. genom att använda valfri algoritm för maximal kardinalitetsmatchning . Kőnigs sats motsvarar följande:

Positivitetsgrafen för vilken bistokastisk matris som helst medger en perfekt matchning.

En matris kallas skalad-bistokastisk om alla element är svagt positiva, och summan av varje rad och kolumn är lika med c , där c är någon positiv konstant. Det är med andra ord c gånger en bistokastisk matris. Eftersom positivitetsgrafen inte påverkas av skalning:

Positivitetsgrafen för en skalad bistokastisk matris medger en perfekt matchning.

Algoritm

Birkhoffs algoritm är en girig algoritm : den hittar girigt perfekta matchningar och tar bort dem från bråkmatchningen. Det fungerar enligt följande.

1. Låt jag = 1.
2. Konstruera positivitetsgrafen G _X av X .
3. Hitta en perfekt matchning i G _X , motsvarande en positiv permutationsmängd i X .
4. Låt z [ i ] > 0 vara den minsta posten i permutationsmängden.
5. Låt P [ i ] vara en permutationsmatris med 1 i den positiva permutationsmängden.
6. Låt X := X − z [ i ] P [ i ].
7. Om X innehåller element som inte är noll, Låt i = i + 1 och gå tillbaka till steg 2.
8. Annars returnerar du summan: z [1] P [1] + ... + z [2] P [2] + ... + z [ i ] P [ i ].

Algoritmen är korrekt eftersom, efter steg 6, summan i varje rad och varje kolumn sjunker med z [ i ]. Därför förblir matrisen X skalad-bistokastisk. Därför, i steg 3, finns alltid en perfekt matchning.

Körtidskomplexitet

Genom valet av z [ i ] i steg 4, i varje iteration blir minst ett element av X 0. Därför måste algoritmen avslutas efter högst n ² steg. Men det sista steget måste samtidigt göra n element 0, så algoritmen slutar efter högst n ² − n + 1 steg, vilket innebär $O(n^{2})$ .

1960 visade Joshnson, Dulmage och Mendelsohn att Birkhoffs algoritm faktiskt slutar efter högst n ² − 2 n + 2 steg, vilket är snävt i allmänhet (det vill säga i vissa fall kan n ² − 2 n + 2 permutationsmatriser krävas ).

Ansökan i rättvis delning

I det rättvisa slumpmässiga uppdragsproblemet finns det n objekt och n personer med olika preferenser över objekten. Det krävs att ge ett föremål till varje person. För att uppnå rättvisa är tilldelningen randomiserad: för varje (person, objekt) par beräknas en sannolikhet, så att summan av sannolikheter för varje person och för varje objekt är 1. Den probabilistiska-seriella proceduren kan beräkna sannolikheterna så att varje agent, som tittar på sannolikhetsmatrisen, föredrar sin rad av sannolikheter framför raderna av alla andra människor (denna egenskap kallas avundsfrihet) . Detta väcker frågan om hur man i praktiken genomför denna randomiserade tilldelning? Man kan inte bara randomisera för varje objekt separat, eftersom detta kan resultera i allokationer där vissa personer får många objekt medan andra inte får några objekt.

Här är Birkhoffs algoritm användbar. Sannolikhetsmatrisen, beräknad av den probabilistiska-seriella algoritmen, är bistokastisk. Birkhoffs algoritm kan sönderdela den i en konvex kombination av permutationsmatriser. Varje permutationsmatris representerar en deterministisk tilldelning, där varje agent får exakt ett objekt. Koefficienten för varje sådan matris tolkas som en sannolikhet; baserat på de beräknade sannolikheterna är det möjligt att välja ett uppdrag slumpmässigt och implementera det.

Tillägg

Problemet med att beräkna Birkhoff-nedbrytningen med det minsta antalet termer har visat sig vara NP-hårt , men vissa heuristik för att beräkna det är kända. Detta teorem kan utökas för den allmänna stokastiska matrisen med deterministiska övergångsmatriser.

Budish, Che, Kojima och Milgrom generaliserar Birkhoffs algoritm till icke-kvadratiska matriser , med vissa begränsningar för de genomförbara tilldelningarna. De presenterar också en nedbrytningsalgoritm som minimerar variansen i förväntade värden.

Vazirani generaliserar Birkhoffs algoritm till icke-tvådelade grafer .

Se även

• Birkhoff polytop
• Birkhoffs nedbrytning (disambiguation)
• Gordans lemma - säger att vissa uppsättningar av vektorer kan genereras av en ändlig delmängd.