期待を最大化する確率グループの学生
与えられた $3n$ その人々 $i^{\text{th}}$ 人は確率でテストに合格することができます $p_i$、今あなたはそれらをに分割する必要があります $n$ 各グループが持っているグループ $3$人。1つのグループのスコアは等しい$1$ 少なくとも2人がテストに合格した場合、 $0$さもないと。合計スコアの期待値を最大化するために、どのようにグループ化しますか？
私はこの問題について少し考えましたが、直感的に2つの大きなグループにまとめることは理にかなっていると思います $p_i$ 小さい $p_i$。また、私は最適な配置で、任意の2つを交換することを考えました$p_i$異なるグループからの期待を下げる必要があります。2人の生徒を入れ替えたときの期待値の違いを数学的に書き出すことはできますが、明らかな結果は得られていないようです。壁にぶつかった。
回答
次の集合分割定式化を使用して、整数線形計画法を介して問題を解決できます。しましょう$S=\{1,\dots,3n\}$ 学生のセットになり、 $$T=\{(i,j,k)\in S\times S\times S: i < j < k\}$$学生のトリプルのセットになります。ために$(i,j,k)\in T$、バイナリ決定変数を許可します $x_{i,j,k}$ トリプルかどうかを示す $(i,j,k)$グループに割り当てられます。場合$x_{i,j,k}=1$、そのグループの合格確率は \begin{align} P_{i,j,k}&:=p_i p_j p_k+(1-p_i) p_j p_k+p_i (1-p_j) p_k+p_i p_j (1-p_k)\\ &=p_i p_j + p_i p_k + p_j p_k - 2 p_i p_j p_k. \end{align} 問題は最大化することです $$\sum_{(i,j,k)\in T} P_{i,j,k} x_{i,j,k} \tag1$$対象1 X_ {I、J、K}＆= && \テキスト：\ {\\ S \ \ {I、J、K \}でTで\（I、J、K）} {ALIGN} \和_開始{ために$s\in S$} \ tag2 \ end {align}目的関数$(1)$予想される合計スコアです。制約$(2)$ 各生徒を正確に1つのグループに割り当てます。
小さなもののための数値実験 $n$ 均一に分散 $p_i$グループごとに2つの大きな確率と1つの小さな確率の直感を確認します。実際、最小の確率は2つが最大で、次に最小で次の2つが最大であるというように表示されます。たとえば、学生のラベルが次の昇順で変更された場合$p_i$ （一般性を失うことなく）、そして $n=6$ グループを生成します $$\{\{1,17,18\},\{2,15,16\},\{3,13,14\},\{4,11,12\},\{5,9,10\},\{6,7,8\}\}.$$
更新：これは小さな反例です$n=2$。取る$p=(0,0,0.1,0.6,0.8,0.8)$。次にグループ$\{\{1,2,3\},\{4,5,6\}\}$ の期待スコアを生成します $0.832$、グループが $\{\{1,5,6\},\{2,3,4\}\}$ の期待スコアが小さくなります $0.7$。
問題を単純化する方法は次のとおりです。しましょう$p_i = x_i + 1/2$。次に、表現を最大化したい
\begin{align*} &\sum_{(i,j,k)\in T}p_ip_jp_k+(1-p_i)p_jp_k+p_i(1-p_j)p_k+p_ip_j(1-p_k)\\ =&\sum_{(i,j,k)\in T}\frac12+\frac12(x_i+x_j+x_k)-2x_ix_jx_k\\ =&N/2 +\frac12\sum_{i<3N}x_i-2\sum_{(i,j,k)\in T}x_ix_jx_k \end{align*}
最後の項のみがパーティションに依存します $T$。そのため、問題を単純化して、$T$ これは、の積の合計を最小化します $x$s3つの各グループ。
$$\sum_{(i,j,k)\in T}x_ix_jx_k$$