バーコフアルゴリズム
行列を操作するためのツール

バーコフのアルゴリズム（バーコフ・フォン・ノイマン・アルゴリズムとも呼ばれる）は、双確率行列を順列行列の凸結合に分解するアルゴリズムである。 1946年にギャレット・バーコフによって発表された。[1] [2] : 36 多くの応用がある。例えば、公平なランダム割り当ての問題への応用が挙げられる。ランダムに割り当てられたアイテムをバーコフのアルゴリズムで処理すれば、それを決定論的な割り当てに基づく抽選に分解することができる。

用語

双確率行列（二重確率行列とも呼ばれる）は、すべての要素が 0 以上で、各行および各列の要素の合計が 1 になる行列です。例として、次の 3 行 3 行列があります。 順列行列は双確率行列の特殊なケースで、各要素は 0 または 1 のいずれかです（したがって、各行および各列に 1 つの "1" が存在します）。例として、次の 3 行 3 行列があります。 双確率行列 の バーコフ分解（バーコフ・フォン・ノイマン分解とも呼ばれる）は、双確率行列を非負の重みを持つ順列行列の合計として表したものです。たとえば、上記の行列は次の合計として表すことができます。 バーコフのアルゴリズムは、入力として双確率行列を受け取り、出力としてバーコフ分解を返します。 （ 0.2 0.3 0.5 0.6 0.2 0.2 0.2 0.5 0.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 0 0 0 1 1 0 0 ） {\displaystyle {\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}} 0.2 （ 0 1 0 0 0 1 1 0 0 ） + 0.2 （ 1 0 0 0 1 0 0 0 1 ） + 0.1 （ 0 1 0 1 0 0 0 0 1 ） + 0.5 （ 0 0 1 1 0 0 0 1 0 ） {\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}}

ツール

n行n列の行列Xの順列集合 とは、 Xの各行と各列からそれぞれ1つずつの要素を含むn個の要素の集合である。デーネス・ケーニヒの定理によれば、次のようになる。 [3] [2] : 35 

すべての双確率行列には、すべてのエントリが正である順列セットがあります。

n行n列の行列Xの正値グラフは、 2 n 個の頂点を持つ二部グラフであり、一方の頂点はn行、もう一方の頂点はn列である。ある行とある列の要素が正値である場合、その行と列の間には辺が存在する。正値の要素を持つ順列集合は、正値グラフにおける完全マッチングと同等である。二部グラフにおける完全マッチングは、例えば最大基数マッチングのための任意のアルゴリズムを用いて、多項式時間で見つけることができる。ケーニッヒの定理は、以下と同等である。

任意の双確率行列の正値グラフは完全なマッチングを許容します。

すべての要素が非負で、各行と各列の和がc （cは正の定数）に等しい場合、その行列はスケーリング双確率行列と呼ばれます。言い換えれば、双確率行列の c 倍です。正値グラフはスケーリングの影響を受けないため、次のようになります。

任意のスケール双確率行列の正値グラフは完全なマッチングを許容します。

アルゴリズム

バーコフのアルゴリズムは貪欲アルゴリズムである。貪欲に完全マッチングを見つけ、それを部分マッチングから除去する。その動作は以下の通りである。[4] : app.B 

  1. i = 1とします。
  2. Xの 正値グラフG Xを構築します。
  3. X内の正の順列集合に対応する、G 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では常に完全マッチングが存在する。

実行時の複雑さ

ステップ4におけるz [ i ]の選択により、各反復においてXの少なくとも1つの要素が0になります。したがって、アルゴリズムは最大でn 2ステップで終了する必要があります。しかし、最後のステップではn個の要素を同時に0にする必要があるため、アルゴリズムは最大でn 2 − n + 1ステップで終了し、これは次式を意味します。 お （ n 2 ） {\displaystyle O(n^{2})}

1960年にジョンソン、ダルメージ、メンデルソンはバーコフのアルゴリズムは実際には最大でn2−2n +2ステップで終了することを示し、これは一般的に厳密である（つまり、場合によってはn2−2n + 2の順列行列が必要になる可能性がある）。[5]

公平な分割への応用

公平なランダム割り当て問題では、 n 個のオブジェクトと、オブジェクトに対する好みが異なるn人の人々が存在します。各人にオブジェクトを 1 つ与える必要があります。公平性を実現するために、割り当てはランダム化されます。つまり、各 (人、オブジェクト) ペアに対して、各人および各オブジェクトの確率の合計が 1 になるように確率が計算されます。確率シリアル手順では、各エージェントが確率のマトリックスを見て、自分の確率の行を他のすべての人の行よりも好むように確率を計算できます (この特性は、envy-freenessと呼ばれます)。これにより、このランダム割り当てを実際にどのように実装するかという疑問が生じます。オブジェクトごとに個別にランダム化するだけでは不十分です。そうすると、一部の人々は多くのオブジェクトを取得し、他の人々はオブジェクトをまったく取得しないという割り当てになる可能性があるからです。

ここでバーコフのアルゴリズムが役立ちます。確率逐次アルゴリズムによって計算される確率行列は双確率的です。バーコフのアルゴリズムは、これを順列行列の凸結合に分解できます。各順列行列は、各エージェントが正確に1つのオブジェクトを受け取る決定論的な割り当てを表します。各行列の係数は確率として解釈され、計算された確率に基づいて、ランダムに1つの割り当てを選択し、それを実行することができます。

拡張機能

バーコフ分解を最小の項数で計算する問題はNP困難であることが示されているが、それを計算するためのいくつかのヒューリスティックスが知られている。[6] [7]この定理は、決定論的遷移行列を持つ一般確率行列に拡張することができる。[8]

Budish、Che、Kojima、Milgrom [9]は、バーコフのアルゴリズムを非正方行列に一般化し、実行可能な割り当てにいくつかの制約を課しています。また、期待値の分散を最小化する分解アルゴリズムも提示しています。

Vazirani [10] はBirkhoffのアルゴリズムを非二部グラフに一般化した。

Vallsら[11]は、順列化によって 近似分解が得られることを示した。 ϵ {\displaystyle \epsilon } お （ ログ ⁡ （ 1 / ϵ 2 ） ） {\displaystyle O(\log(1/\epsilon ^{2}))}

参照

参考文献

  1. ^ Birkhoff、Garrett (1946)、「Tres observaciones sobre el algebra lineal [線形代数に関する 3 つの観察]」、Univ.ナック。トゥクマン。レヴィスタ A.、5 : 147–151、MR  0020547。
  2. ^ ab ロヴァース、ラースロー;プラマー医学博士(1986 年)、『マッチング理論』、『離散数学年報』、第 1 巻。 29、北オランダ、ISBN 0-444-87916-1、MR  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. ^ アジズ、ハリス（2020年）「事前公平性と事後公平性の同時達成」arXiv：2004.02554 [cs.GT]。
  5. ^ ジョンソン, ダイアン・M.; ダルメージ, AL; メンデルソン, NS (1960-09-01). 「二重確率行列に関するG. バーコフのアルゴリズムについて」.カナダ数学速報. 3 (3): 237– 242. doi : 10.4153/cmb-1960-029-5 . ISSN  0008-4395.
  6. ^ Dufossé, Fanny; Uçar, Bora (2016年5月). 「二重確率行列のバーコフ–フォン・ノイマン分解に関する注記」(PDF) .線形代数とその応用. 497 : 108–115 . doi : 10.1016/j.laa.2016.02.023 .
  7. ^ Dufossé, Fanny; Kaya, Kamer; Panagiotas, Ioannis; Uçar, Bora (2018). 「二重確率行列のバーコフ–フォン・ノイマン分解に関する追加ノート」(PDF) .線形代数とその応用. 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). 「確率的ダイナミクス：マルコフ連鎖とランダム変換」.離散および連続動的システム - シリーズB. 21 ( 7): 2337– 2361. doi : 10.3934/dcdsb.2016050 .
  9. ^ Budish, Eric; Che, Yeon-Koo; Kojima, Fuhito; Milgrom, Paul (2013-04-01). 「ランダム配分メカニズムの設計：理論と応用」. 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. (2020-10-14). 「バーコフ-フォン・ノイマン定理の非二部グラフへの拡張」. arXiv : 2010.05984 [cs.DS].
  11. ^ Valls, Victor; Iosifidis, Georgios; Tassiulas, Leandros (2021年12月). 「Birkhoffの分解の再考：高速回線スイッチのためのスパーススケジューリング」. IEEE/ACM Transactions on Networking . 29 (6): 2399– 2412. arXiv : 2011.02752 . Bibcode :2021ITNet..29.2399V. doi :10.1109/TNET.2021.3088327.
「https://en.wikipedia.org/w/index.php?title=バーコフアルゴリズム&oldid=1318525881」より取得