シャープレー＝フォークマン補題

シャープレー＝フォークマン補題（シャープレー＝フォークマンほだい、英: Shapley–Folkman lemma）は、ベクトル空間における集合のミンコフスキー加法（英語版）を記述する凸幾何学（英語版）における結果である。この補題は直感的には「和を取る集合の数がベクトル空間の次元を超える場合、そのミンコフスキー和はおおよそ凸になる」と理解できる^[1][2]。名称は数学者のロイド・シャープレーとジョン・フォークマン（英語版）に由来するが、初めて発表したのは経済学者のロス・スター（英語版）である。

シャープレー＝フォークマン補題は4つの集合のミンコフスキー加法によって図示されている。右側の4つの非凸集合のミンコフスキー和の凸包内の「＋」記号は、左側の集合からの4つの「＋」記号の和であり、そのうち2つは非凸集合内の点、残り2つは凸包内の点である。凸包はピンク色に塗られており、元の集合には赤い点が2つずつ含まれている^[1]。

関連する結果として、この近似がどの程度正確かについてより精緻な記述を与えるものがある。例えば、シャープレー＝フォークマン定理は、ミンコフスキー和の任意の点とその凸包との距離に対する上界を与える。この上界はシャープレー＝フォークマン＝スター定理（またはスターの系）によってさらに鋭くなる^[3]。

シャープレー＝フォークマン補題は経済学、数理最適化、確率論に応用がある^[3]。経済学においては、凸選好について証明された結果を非凸選好に拡張するために用いることができる。最適化理論においては、多くの関数の和として表される最小化問題が成功裏に解ける理由を説明するために用いられる^[4][5]。確率論においては、確率幾何学（英語版）における大数の法則を証明するために用いられる^[6]。

例

集合は、それに属する任意の2点を結ぶ線分がその集合の部分集合である場合、凸集合であるという。充実した単位円板${\displaystyle \bullet }$は凸集合であるが、単位円${\displaystyle \circ }$はそうではない。なぜなら、2つの異なる点${\displaystyle \oslash }$を結ぶ線分が円の部分集合ではないからである^[7]。集合${\displaystyle Q}$の凸包は、${\displaystyle Q}$を含む最小の凸集合である^[8]。

ミンコフスキー加法とは、複数の集合の元からそれぞれ1つずつ選び、その和を取った集合を作る操作である^[9]。例えば、0と1からなる集合をそれ自身に加えると、0、1、2からなる集合が得られる： $${\displaystyle {0,1}+{0,1}={0+0,0+1,1+0,1+1}={0,1,2}}$$ この整数部分集合${\displaystyle {0,1,2}}$は実数の区間${\displaystyle [0,2]}$に含まれ、これがその凸包である。シャープレー＝フォークマン補題は、${\displaystyle [0,2]}$の任意の点が${\displaystyle {0,1}}$の元と${\displaystyle [0,1]}$の元の和として表せることを示唆する。すなわち、${\displaystyle {0,1}}$のミンコフスキー和の凸包を得るには、加数のうち1つだけをその凸包に置き換えればよい^[10]。

非凸集合${\displaystyle {0,1}}$とその凸包${\displaystyle [0,1]}$とのハウスドルフ距離は${\displaystyle {\tfrac {1}{2}}}$であり、この距離は非凸集合${\displaystyle {0,1,2}}$とその凸包${\displaystyle [0,2]}$でも同じである。両方の場合で、凸包には${\displaystyle {\tfrac {1}{2}}}$のように非凸集合の元から距離${\displaystyle {\tfrac {1}{2}}}$の点が含まれる。この例では、ミンコフスキー加法は和とその凸包との距離を減少させない。しかし、和を算術平均に置き換え、和をその項数で割ることによりスケーリングすると、スケーリングされたミンコフスキー和とその凸包との距離は減少する。例えば、平均ミンコフスキー和 $${\displaystyle {\frac {1}{2}}\left(\{0,1\}+\{0,1\}\right)=\left\{0,{\tfrac {1}{2}},1\right\}}$$ とその凸包${\displaystyle [0,1]}$との距離は${\displaystyle {\tfrac {1}{4}}}$であり、これは加数${\displaystyle {0,1}}$とその凸包${\displaystyle [0,1]}$との距離${\displaystyle {\tfrac {1}{2}}}$の半分である。より多くの集合を加えるにつれて、その和の平均は凸包を「埋めていき」、平均とその凸包との最大距離は加数が増えるにつれてゼロに近づく。この距離の減少は、シャープレー＝フォークマン補題の帰結として、シャープレー＝フォークマン定理およびシャープレー＝フォークマン＝スター定理によってより形式的に述べられる^[10]。