# NP-hardness of an optimization problem

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

• I think your solution is correct and if you use a similar trick for the clauses, you can even restrict every Si to 2 elements. – domotorp Jan 3 '13 at 18:05

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$.