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