確率計画法では、相関ギャップは、確率変数が相関している場合のコストと、確率変数が独立している場合のコストとの間の最悪の比率です。[ 1 ]
例として、[ 1 ] : 6次の最適化問題を考えてみましょう。教師は授業に出席するかどうかを知りたいと考えています。生徒はn人います。各生徒について、授業に出席する確率は 1/ nです。少なくとも 1 人の生徒が出席する場合、教師は出席しなければならず、コストは 1 です。生徒が一人も出席しない場合、教師は家にいることができ、コストは 0 です。教師の目標はコストを最小化することです。これは、制約条件が事前にわかっておらず、その確率のみがわかっているため、確率計画問題です。ここで、生徒間の相関関係については 2 つのケースがあります。
- ケース1：生徒同士は無相関である：各生徒は確率でコインを投げて授業に出席するかどうかを決める
他のものとは独立して。この場合の予想コストは
。 - ケース2：生徒は相関関係にある：1人の生徒がランダムに選ばれて授業に出席し、他の生徒は家にいる。各生徒が出席する確率は依然としてしかし、現在のコストは 1です。
相関ギャップはケース2のコストをケース1のコストで割ったもので、
。
[ 1 ]いくつかのケースで相関ギャップが有界であることを証明します。たとえば、コスト関数が劣モジュラ集合関数（上記の例のように）、相関ギャップは最大で（つまり、上記の例は最悪のケースです。）
相関ギャップの上限は、相関を無視することによって生じる損失の上限を意味します。たとえば、劣モジュラコスト関数を持つ確率計画問題を考えてみましょう。変数の周辺確率はわかっていますが、それらが相関しているかどうかはわかりません。相関を無視して、変数が独立しているかのように問題を解くと、得られる解は
最適解への近似値。
アプリケーション
相関ギャップは、ベイズ最適オークションの代わりにベイズ最適価格設定を使用した場合の収益損失を制限するために使用されました。[ 2 ]
参考文献
- 1 2 3 Agrawal, Shipra; Ding, Yichuan; Saberi, Amin; Ye, Yinyu (2010). "相関ロバスト確率最適化". Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms . p. 1087. arXiv : 0902.1792 . doi : 10.1137/1.9781611973075.88 . ISBN 978-0-89871-701-3。
- ↑ Yan, Qiqi (2011). "相関ギャップによるメカニズム設計".第22回ACM-SIAM離散アルゴリズムシンポジウム論文集. p. 710. arXiv : 1008.1843 . doi : 10.1137/1.9781611973082.56 . ISBN 978-0-89871-993-2。
