alunos do grupo de probabilidade para maximizar a expectativa
Dado $3n$ pessoas que o $i^{\text{th}}$ pessoa pode passar em um teste com probabilidade $p_i$, agora você deve dividi-los para $n$ grupos que cada grupo tem $3$pessoas. A pontuação de um grupo é igual a$1$ se pelo menos duas pessoas passarem no teste, $0$de outra forma. Para maximizar a expectativa de pontuação total, como você os agrupa?
Pensei um pouco sobre esse problema e acho que intuitivamente faz sentido agrupar dois grandes $p_i$ com um pequeno $p_i$. Além disso, pensei no arranjo ideal, trocando quaisquer dois$p_i$de grupos diferentes deve diminuir a expectativa. Posso escrever matematicamente a diferença na expectativa ao trocar dois dos alunos, mas não parece dar nenhum resultado óbvio. Eu bati em uma parede.
Respostas
Você pode resolver o problema por meio da programação linear inteira usando a seguinte formulação de particionamento de conjunto. Deixei$S=\{1,\dots,3n\}$ seja o conjunto de alunos, e deixe $$T=\{(i,j,k)\in S\times S\times S: i < j < k\}$$ser o conjunto de triplos de alunos. Para$(i,j,k)\in T$, deixe a variável de decisão binária $x_{i,j,k}$ indicar se triplo $(i,j,k)$é atribuído a um grupo. E se$x_{i,j,k}=1$, a probabilidade de aprovação para esse grupo é \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} O problema é maximizar $$\sum_{(i,j,k)\in T} P_{i,j,k} x_{i,j,k} \tag1$$sujeito a \ begin {align} \ sum _ {(i, j, k) \ in T: \\ s \ in \ {i, j, k \}} x_ {i, j, k} & = 1 && \ text {para$s\in S$} \ tag2 \ end {align} A função objetivo$(1)$é a pontuação total esperada. Limitação$(2)$ atribui cada aluno a exatamente um grupo.
Experimentação numérica para pequenos $n$ e uniformemente distribuído $p_i$confirma sua intuição de duas grandes e uma pequena probabilidade por grupo. Na verdade, a menor probabilidade aparece com as duas maiores, a próxima menor com as duas próximas maiores e assim por diante. Por exemplo, se os alunos forem rotulados novamente em ordem crescente de$p_i$ (sem perda de generalidade), então $n=6$ grupos de rendimentos $$\{\{1,17,18\},\{2,15,16\},\{3,13,14\},\{4,11,12\},\{5,9,10\},\{6,7,8\}\}.$$
Atualização : aqui está um pequeno contra-exemplo com$n=2$. Levar$p=(0,0,0.1,0.6,0.8,0.8)$. Então grupos$\{\{1,2,3\},\{4,5,6\}\}$ produzir uma pontuação esperada de $0.832$, enquanto grupos $\{\{1,5,6\},\{2,3,4\}\}$ produzir uma pontuação esperada menor de $0.7$.
Esta é uma maneira de simplificar o problema. Deixei$p_i = x_i + 1/2$. Então, queremos maximizar a expressão
\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*}
em que apenas o último termo depende da partição $T$. Portanto, simplificamos o problema para encontrar o$T$ que minimiza a soma dos produtos do $x$s em cada grupo de três.
$$\sum_{(i,j,k)\in T}x_ix_jx_k$$