Birkhoffův algoritmus - Birkhoff algorithm - Wikipedia

Birkhoffův algoritmus je algoritmus pro rozložení a bistochastická matice do konvexní kombinace permutační matice. To bylo publikováno Garrett Birkhoff v roce 1946.[1][2]:36 Má mnoho aplikací. Jedna taková aplikace je pro problém spravedlivé náhodné přiřazení: vzhledem k náhodnému přidělení položek jej Birkhoffův algoritmus může rozložit na loterii o deterministických alokacích.

Terminologie

A bistochastická matice (také zvaný: dvojnásobně stochastický) je matice, ve které jsou všechny prvky větší nebo rovny 0 a součet prvků v každém řádku a sloupci je roven 1. Příkladem je následující matice 3 x 3:

A permutační matice je speciální případ bistochastické matice, ve kterém je každý prvek buď 0 nebo 1 (takže v každém řádku a každém sloupci je přesně jedna „1“). Příkladem je následující matice 3 x 3:
A Birkhoffův rozklad (také zvaný: Birkhoff-von-Neumannův rozklad) bistochastické matice je její prezentace jako součet permutačních matic s nezápornými váhami. Například výše uvedená matice může být prezentována jako následující součet:
Birkhoffův algoritmus přijímá jako vstup bistochastickou matici a vrací jako výstup Birkhoffův rozklad.

Nástroje

A permutační sada z n-podle-n matice X je sada n záznamy z X obsahující přesně jednu položku z každého řádku a z každého sloupce. Věta od Dénes Kőnig říká, že:[3][2]:35

Každá bistochastická matice má permutační sadu, ve které jsou všechny položky kladné.

The graf pozitivity z n-podle-n matice X je bipartitní graf s 2n vrcholy, ve kterých jsou vrcholy na jedné straně n řádky a vrcholy na druhé straně jsou n sloupce a mezi řádkem a sloupcem je hrana, pokud je položka v tomto řádku a sloupci kladná. Sada permutací s kladnými položkami je ekvivalentní a perfektní shoda v grafu pozitivity. Perfektní shodu v bipartitním grafu lze najít v polynomiálním čase, např. pomocí libovolného algoritmu pro maximální shoda mohutnosti. Kőnig Věta je ekvivalentní následujícímu:

Graf pozitivity jakékoli bistochastické matice připouští perfektní shodu.

Matice se nazývá zmenšen-bistochastický pokud jsou všechny prvky slabě pozitivní a součet každého řádku a sloupce se rovná C, kde C je nějaká pozitivní konstanta. Jinými slovy, je C krát bistochastická matice. Protože graf pozitivity není ovlivněn škálováním:

Graf pozitivity jakékoli matice se stupnicí-bistochastickou maticí připouští perfektní shodu.

Algoritmus

Pomocí výše uvedených nástrojů funguje Birkhoffův algoritmus následujícím způsobem.[4]:aplikace B.

  1. Nechat i = 1.
  2. Vytvořte graf pozitivity GX z X.
  3. Najděte perfektní shodu v GX, což odpovídá kladné permutaci nastavené v X.
  4. Nechat z[i]> 0 je nejmenší položka v sadě permutací.
  5. Nechat P[i] být permutační matice s 1 s v kladné permutační sadě.
  6. Nechť X: = X − z[i] P[i].
  7. Pokud X obsahuje nenulové prvky, Let i = i + 1 a vraťte se ke kroku 2.
  8. V opačném případě vraťte částku: z[1] P[1] + ... + z[2] P[2] + ... + z[i] P[i].

Algoritmus je správný, protože po kroku 6 součet v každém řádku a každém sloupci klesne o z[i]. Proto matice X zůstává šupinatý-bistochastický. Proto v kroku 3 vždy existuje perfektní shoda.

Složitost za běhu

Výběrem z[i] v kroku 4, v každé iteraci alespoň jeden prvek X se stane 0. Proto musí algoritmus skončit maximálně po n2 kroky. Poslední krok však musí být proveden současně n prvky 0, takže algoritmus končí maximálně po n2 − n + 1 kroky.

V roce 1960 Joshnson, Dulmage a Mendelsohn ukázali, že Birkhoffův algoritmus ve skutečnosti končí maximálně n2 − 2n + 2 kroky, které jsou obecně přísné (tj. V některých případech n2 − 2n + 2 permutační matice mohou být vyžadovány).[5]

Aplikace ve spravedlivém rozdělení

V spravedlivé náhodné přiřazení problém, existují n předměty a n lidé s různými preferencemi nad objekty. Je nutné dát předmět každé osobě. K dosažení spravedlnosti je alokace náhodná: pro každý pár (osoba, objekt) se vypočítá pravděpodobnost, takže součet pravděpodobností pro každou osobu a pro každý objekt je 1. pravděpodobnostně-sériový postup umí vypočítat pravděpodobnosti tak, že každý agent při pohledu na matici pravděpodobností upřednostňuje svůj řádek pravděpodobností před řádky všech ostatních lidí (tato vlastnost se nazývá závistlivost ). To vyvolává otázku, jak implementovat toto randomizované přidělování v praxi? Nelze pouze náhodně vybrat pro každý objekt zvlášť, protože to může mít za následek přidělení, ve kterém někteří lidé získají mnoho objektů, zatímco jiní žádné objekty.

Zde je Birkhoffův algoritmus užitečný. Matice pravděpodobností, vypočítaná pomocí pravděpodobnostně-sériového algoritmu, je bistochastická. Birkhoffův algoritmus jej může rozložit na konvexní kombinaci permutačních matic. Každá permutační matice představuje deterministické přiřazení, ve kterém každý agent obdrží přesně jeden objekt. Koeficient každé takové matice je interpretován jako pravděpodobnost; na základě vypočítaných pravděpodobností je možné náhodně vybrat jedno přiřazení a implementovat jej.

Rozšíření

Ukázalo se, že je problém spočítat Birkhoffův rozklad s minimálním počtem členů NP-tvrdé, ale některé heuristiky pro jeho výpočet jsou známy.[6][7] Tuto větu lze rozšířit pro obecnou stochastickou matici o deterministické přechodové matice.[8]

Viz také

Reference

  1. ^ Birkhoff, Garrett (1946), „Tres observaciones sobre el algebra lineal [Tři pozorování lineární algebry]“, Univ. Nac. Tucumán. Revista A., 5: 147–151, PAN  0020547.
  2. ^ A b Lovász, László; Plummer, M. D. (1986), Teorie shody, Annals of Discrete Mathematics, 29, Severní Holandsko, ISBN  0-444-87916-1, PAN  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). "Současné dosažení ex-ante a ex-post spravedlnosti". arXiv:2004.02554 [cs.GT ].
  5. ^ Johnson, Diane M .; Dulmage, A. L .; Mendelsohn, N. S. (1960-09-01). „Na algoritmu G. Birkhoffa týkajícího se nepochybně stochastických matic“. Kanadský matematický bulletin. 3 (3): 237–242. doi:10.4153 / cmb-1960-029-5. ISSN  0008-4395.
  6. ^ Dufossé, Fanny; Uçar, Bora (květen 2016). „Poznámky k Birkhoff – von Neumannovu rozkladu dvojnásobně stochastických matic“ (PDF). Lineární algebra a její aplikace. 497: 108–115. doi:10.1016 / j.laa.2016.02.023.
  7. ^ Dufossé, Fanny; Kaya, Kamer; Panagiotas, Ioannis; Uçar, Bora (2018). „Další poznámky k Birkhoff – von Neumannovu rozkladu dvojnásobně stochastických matic“ (PDF). Lineární algebra a její aplikace. 554: 68–78. doi:10.1016 / j.laa.2018.05.017. ISSN  0024-3795.
  8. ^ Ye, Felix X.-F .; Wang, Yue; Qian, Hong (2016). „Stochastická dynamika: Markovovy řetězce a náhodné transformace“. Diskrétní a spojité dynamické systémy - řada B.. 21 (7): 2337–2361. doi:10,3934 / dcdsb.2016050.