студенты группы вероятности, чтобы максимизировать ожидания

Question

Данный $3n$ люди, которые $i^{\text{th}}$ человек может пройти тест с вероятностью $p_i$, теперь вам нужно разделить их на $n$ группы, которые есть в каждой группе $3$люди. Оценка одной группы равна$1$ если хотя бы два человека сдали тест, $0$в противном случае. Как вы их сгруппируете, чтобы получить максимальное количество баллов?

Я немного подумал над этой проблемой и интуитивно думаю, что имеет смысл сгруппировать два больших $p_i$ с небольшим $p_i$. Также подумал об оптимальном расположении, поменяв местами любые два$p_i$от разных групп должны снизить ожидания. Я могу математически описать разницу в ожидании при обмене местами двух учеников, но это не дает очевидного результата. Я врезался в стену.

Answer 1

Вы можете решить эту проблему с помощью целочисленного линейного программирования, используя следующую формулировку разделения набора. Позволять$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$$при условии \ begin {align} \ sum _ {(i, j, k) \ in T: \\ s \ in \ {i, j, k \}} x_ {i, j, k} & = 1 && \ text {для$s\in S$} \ tag2 \ end {align} Целевая функция$(1)$ожидаемый общий балл. Ограничение$(2)$ распределяет каждого ученика ровно в одну группу.

Численные эксперименты для малых $n$ и равномерно распределены $p_i$подтверждает вашу интуицию о двух больших и одной малой вероятности на группу. Фактически, наименьшая вероятность появляется с двумя наибольшими, следующая наименьшая - с двумя следующими наибольшими и так далее. Например, если студентов помечают в порядке возрастания$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$.

Answer 2

Вот способ упростить задачу. Позволять$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$s в каждой группе по три человека.

$$\sum_{(i,j,k)\in T}x_ix_jx_k$$