I will begin by linking a previous post where I asked a general question for a stochastic setting which I describe below. It turns out that my "proof" for a restricted case had a mistake and there is a much simpler setting where showing hardness should be easier. Please let me know if I should amend the original question instead.
Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$. We will restrict $G$ to be a cycle where every vertex has degree $2$ (and $m = n$).
The challenge is to assign weights $w_e$ to each edge to maximize the objective function $E = \sum_{e = \{i,j\}} w_e \Pr[X_i + X_j \geq w_e]$ where $\Pr[X_i + X_j \geq w_e]$ denotes the probability that that the sum of values taken by vertex $i$ and $j$ is greater than $w_e$. The additional constraint is that the weights $w_e$ need to be sub-additive, i.e., for any two edges $e'$ and $e''$ that "cover" edge $e$ meaning $e'$ and $e''$ include the vertices that make $e$, it holds that $w_e \leq w_{e'} + w_{e''}$.
Observe that the deterministic version where $p_i = 1$ is trivial. Any suggestions on possible directions for hardness or PTIME algorithm would be very helpful!
