NP-hardness of an optimization problem

Question

While studying a problem in algorithmic game theory I got interested in the complexity of the following optimization question:

Problem

Given:

• 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 problem seems to be hard even when all the $S_i$'s are of size $2$. However I haven't been able to prove this.

What I know

It easy to see that the following restrictions make the problem easy:

• all of the weights are uniform: selecting all of the elements is clearly optimal.
• all of the rankings are complete rankings over $U$: the best solution is obtained by taking the element with the maximal weight.
• the weights are just binary ($w \in \{0,1\}^n$), then selecting all of the $1$-weighing elements is optimal.

However I haven't been able to find a polynomial time algorithm for the general case (for example using LP). On the other hand proving the problem to be $\mathsf{NP}$-hard doesn't look easy. The structure of the problem instances doesn't allow easy encoding of other problems. (Note that the hardness of the problem will come from using the same $L$ for all partial orders, however using the same weight vector for all of them makes proving hardness not straight forward). I have unsuccessfully tried reducing some $\mathsf{NP}$-hard problems like Subset-Sum, NAND-Circuit-SAT, etc. to the 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 of the problem, but I don't see any sufficient resemblance to any problem that I know of.

Question

Do 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).

Answer 1

Well, here's a possible solution:

The reduction will be from 3SAT.

Input: $m$ DNF clauses $(\varphi_1,\ldots,\varphi_m)$ over $n$ variables $(x_1,\ldots,x_n)$.

Reduction: Create a set of items composed of two items for every variable: $x_i, \overline x_i$, corresponding to a $True$ assignment to either the variable $x_i$ or its negation, plus one auxiliary item $t$. Let the price of all items $\{x_i,\overline x_i\}_{i=1,…,n}$ be $1$, and the price of $t$ be $1.5$.

Create two sets of consumers:

Set 1: Validity rankings: this set of consumers will encode the validity constraints on the assignments to $x_1,\ldots,x_n$. Namely, that exactly one out of every $\{x_i,\overline x_i\}$ is set to $True$ (i.e., taken by the algorithm). For every $i=1,\ldots,n$ create four partial rankings:

$\sigma_{i1}: x_i\succ t\\ \sigma_{i2}: \overline x_i \succ t \\ \sigma_{i3}: x_i \succ \overline x_i \\ \sigma_{i4}: x_i \succ \overline x_i$

Taking $t$ can never hurt, so we assume that it's always chosen. If both $x_i$ and $\overline x_i$ are selected, we get a payoff $4$. If none of them is selected, we get a payoff of $3$. If one of them is chosen, we get a payoff of $4.5$.

Set 2: Clause rankings. For each clause of the form $\varphi_j=\ell_{j1} \vee \ell_{i2} \vee \ell_{j3}$, we create a ranking: $\sigma_j: \ell_{j1} > \ell_{j2} > \ell_{j3}$. If $\varphi_j$ is satisfied, it means that at least one of the items corresponding to $\ell_{j1}, \ell_{j2}$, and $\ell_{j3}$ is selected, which gives an extra payoff of $1$ from ranking $\sigma_j$.

Now, the 3CNF formula is satisfiable if and only if there is a set of items that gives a payoff of $m+4.5n$.