<p>Well, here's a possible solution:</p>

<p>The reduction will be from 3SAT.</p>

<p><strong>Input:</strong> $m$ DNF clauses $(\varphi_1,\ldots,\varphi_m)$ over $n$ variables $(x_1,\ldots,x_n)$.</p>

<p><strong>Reduction:</strong>
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$.</p>

<p>Create two sets of consumers:</p>

<p><strong>Set 1:</strong> 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:</p>

<p>$\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$</p>

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

<p><strong>Set 2:</strong> 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} &gt; \ell_{j2} &gt; \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$.</p>

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

CC BY-SA 3.0
2013-01-04T18:39:16.800Z
2013-01-04T18:39:16.800Z
JoelO
<p>While studying a problem in algorithmic game theory I got interested
in the complexity of the following optimization question:</p>
<h3>Problem</h3>
<p>Given:</p>
<ul>
<li>ground set <span class="math-container">$U = [n] = \{1,\ldots,n\}$</span> given by <span class="math-container">$n$</span>,</li>
<li><span class="math-container">$m$</span> rankings given as total orders <span class="math-container">$\langle S_i, \sigma_i \rangle$</span>
where <span class="math-container">$S_i \subseteq U$</span> (<span class="math-container">$1 \leq i \leq m$</span>),</li>
<li>weight vector for <span class="math-container">$U$</span> given by <span class="math-container">$w \in \mathbb{R}^n$</span>.</li>
</ul>
<p>Goal:
find a subset <span class="math-container">$L \subseteq U$</span> maximizing the following sum:
<span class="math-container">$$r(L) = \sum_{i \in [m],\  S_i \cap L \neq \emptyset} w(t_i(L))$$</span>
where <span class="math-container">$t_i(L)$</span> is the highest ranked item in <span class="math-container">$L\cap S_i$</span> according to
<span class="math-container">$\sigma_i$</span>.</p>
<p>I suspect that the problem is <span class="math-container">$\mathsf{NP}$</span>-hard. In fact the problem
seems to be hard even when all the <span class="math-container">$S_i$</span>'s are of size <span class="math-container">$2$</span>. However I
haven't been able to prove this.</p>
<h3>What I know</h3>
<p>It easy to see that the following restrictions make the problem easy:</p>
<ul>
<li>all of the weights are uniform: selecting all of the elements is
clearly optimal.</li>
<li>all of the rankings are complete rankings over <span class="math-container">$U$</span>: the best
solution is obtained by taking the element with the maximal weight.</li>
<li>the weights are just binary (<span class="math-container">$w \in \{0,1\}^n$</span>), then selecting all
of the <span class="math-container">$1$</span>-weighing elements is optimal.</li>
</ul>
<p>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 <span class="math-container">$\mathsf{NP}$</span>-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 <span class="math-container">$L$</span> 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
<span class="math-container">$\mathsf{NP}$</span>-hard problems like Subset-Sum, NAND-Circuit-SAT, etc. to
the decision version of this problem (is there a subset such that
<span class="math-container">$r(L) \geq k$</span>).</p>
<p>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.</p>
<h3>Question</h3>
<p>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 <span class="math-container">$\mathsf{NP}$</span>-hard? (if it is indeed hard).</p>

CC BY-SA 3.0
2013-01-03T18:05:36.397Z
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
<cc.complexity-theory><ds.algorithms><np-hardness><optimization>
NP-hardness of an optimization problem
JoelO
# NP-hardness of an optimization problem

(Asked by: username_0 on 2012-12-21)

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

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness, optimization
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_0 on 2013-01-04. Score: 8

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


---

