While studying a problem in algorithmic game theory I got interestedin the complexity of the following optimization question:ProblemGiven:  ground set $U = [n] = \{1,\ldots,n\}$ given by $n$,$m$ rankings given as total orders $\langle S_i, \sigma_i \rangle$where $S_i \subseteq U$ ($1 \leq i \leq m$),weight vector for $U$ given by $w \in \mathbb{R}^n$.Goal:find a subset $L \subseteq U$ maximizing the following sum:$$r(L) = \sum_{i \in [m],\  S_i \cap L \neq \emptyset} w(t_i(L))$$where $t_i(L)$ is the highest ranked item in $L\cap S_i$ according to$\sigma_i$.I suspect that the problem is $\mathsf{NP}$-hard. In fact the problemseems to be hard even when all the $S_i$'s are of size $2$. However Ihaven't been able to prove this.What I knowIt easy to see that the following restrictions make the problem easy:all of the weights are uniform: selecting all of the elements isclearly optimal.all of the rankings are complete rankings over $U$: the bestsolution is obtained by taking the element with the maximal weight.the weights are just binary ($w \in \{0,1\}^n$), then selecting allof the $1$-weighing elements is optimal.However I haven't been able to find a polynomial time algorithm forthe general case (for example using LP).On the other hand proving the problem to be $\mathsf{NP}$-hard doesn'tlook easy. The structure of the problem instances doesn't allow easyencoding of other problems. (Note that the hardness of the problemwill come from using the same $L$ for all partial orders, howeverusing the same weight vector for all of them makes proving hardnessnot straight forward). I have unsuccessfully tried reducing some$\mathsf{NP}$-hard problems like Subset-Sum, NAND-Circuit-SAT, etc. tothe decision version of this problem (is there a subset such that$r(L) \geq k$).A matching IP can be constructed quiet easily for a given instance ofthe problem, but I don't see any sufficient resemblance to any problemthat I know of.QuestionDo you know the complexity of this problem?Are there any references studying the complexity of similar optimization problems?How would you prove that this optimization problem is $\mathsf{NP}$-hard? (if it is indeed hard).
NP-hardness of an optimization problem
cc.complexity theory;ds.algorithms;np hardness;optimization