<p>We would need some suggestions for the proof of NP-hardness of an optimization problem.</p>

<p><strong>The problem</strong></p>

<p>$$ 
\max_{x_{a,s}} 
\sum_s \sum_a x_{a,s} q_a \lambda_s \prod_{s' &lt; s} \prod_{a' \neq a} (1 + x_{a',s'} (c_{a'}-1) ) 
$$</p>

<p>\begin{align}
\sum_{s \in S} x_{a,s} \leq 1 &amp; \quad \forall a \in A \\
\sum_{a \in A} x_{a,s} \leq 1 &amp; \quad \forall s \in S \\
x_{a,s} \in \{0,1\} &amp;  \quad  \forall a \in A, s \in S
\end{align}</p>

<p>The parameters have the following structure: </p>

<p>\begin{align*}
c_a  \in [0,1]     &amp; \quad  \forall a \in A\\
\lambda_s \in [0,1]   &amp; \quad \forall s \in S\\
\lambda_s &gt;\lambda_{s'}  &amp; \quad \forall s,s' \in S:s&lt;s'\\
q_{a} \in[0,+\infty)   &amp; \quad  \forall a \in A
\end{align*}</p>

<p><strong>In words</strong>: the problem requires one to assign the elements of $A$ to the elements of $S$ such that the value of each assignment is determined as follows</p>

<ul>
<li>if an element $a$ is assigned to $s=1$, then the value of the assignment of this element is: $q_{a}\lambda_1$;</li>
<li>if an element $a$ is assigned to $s=2$, then the value of the assignment of this element is: $q_{a}\lambda_2 c_{a'}$ where $a'$ is assigned to $s=1$;</li>
<li>if an element $a$ is assigned to $s=3$, then the value of the assignment of this element is: $q_{a}\lambda_3 c_{a'} c_{a''}$ where $a'$ is assigned to $s=1$ and $a''$ is assigned to $s=2$;</li>
<li>and so on.</li>
</ul>

<p>The total value of the assignment is given by the sum of the values of all the element assignments. So, with $|S|=3$, the total value is: $q_{a}\lambda_1 +q_{a}\lambda_2 c_{a'} + q_{a}\lambda_3 c_{a'} c_{a''}$.</p>

<p>The problem is easy (but we do not know whether it is hard in general) when:</p>

<ul>
<li><p>$\lambda_s = 1$: the algorithm is based on dynamic programming starting from the last $s$ and going backward to the first</p></li>
<li><p>$c_a=1$: the algorithm is simple, being a greedy optimizer.</p></li>
</ul>

<p><strong>Question</strong>: any idea on how to find a reduction for proving the NP-hardness of the problem?</p>

CC BY-SA 3.0
2013-09-18T17:13:44.113Z
Why is your objective so complicated? Is this the standard assignment problem?
Austin Buchanan
CC BY-SA 3.0
2013-09-19T08:15:25.487Z
No, our problem is not the standard assignment problem. The difference between a 2IAP (2-index assignment problem) and our problem is precisely in the objective function. In the former case the objective function is linear, in the latter it is not.
Guev
CC BY-SA 3.0
2013-09-19T14:40:16.580Z
You have written a nonlinear objective, but maybe it can be rewritten as linear by substituting in new parameters. Can you describe where this objective came from?
Austin Buchanan
CC BY-SA 3.0
2013-09-19T19:19:32.810Z
We have a set of objects $A$ that has to be allocated into an ordered set of positions $S$. We assume a user to scan the positions from the first to the last. Once the user gets a position, the probability that he stops depends on the position (probability \lambda_s) and on the specific object a allocated in such position (probability $c_a$).
Guev
CC BY-SA 3.0
2013-09-19T20:55:12.733Z
Can you give motivation for your problem?
Austin Buchanan
CC BY-SA 3.0
2013-09-20T11:54:55.347Z
A situation like this one is, for example, typical in sponsored search auctions. The aim of the problem is to allocate in the best way, the one maximizing the social welfare, ads $A$ into slots $S$ (positions in a web page). Each slot has a probability to be seen by the user ($\lambda_s$). Moreover, with the cascade model (A Cascade Model for Externalities in Sponsored Search, Kempe and Mahdian) each ad is associated to another probability ($c_a$), that is the probability the user will continue to see the following slots, after having seen a given ad $a$.
Guev
<cc.complexity-theory><np-hardness>
NP-hardness of a winner determination auction
Guev
# NP-hardness of a winner determination auction

(Asked by: username_0 on 2013-09-18)

We would need some suggestions for the proof of NP-hardness of an optimization problem.

**The problem**

$$
\max\_{x\_{a,s}}
\sum\_s \sum\_a x\_{a,s} q\_a \lambda\_s \prod\_{s' < s} \prod\_{a' \neq a} (1 + x\_{a',s'} (c\_{a'}-1) )
$$

\begin{align}
\sum\_{s \in S} x\_{a,s} \leq 1 & \quad \forall a \in A \\
\sum\_{a \in A} x\_{a,s} \leq 1 & \quad \forall s \in S \\
x\_{a,s} \in \{0,1\} & \quad \forall a \in A, s \in S
\end{align}

The parameters have the following structure:

\begin{align\*}
c\_a \in [0,1] & \quad \forall a \in A\\
\lambda\_s \in [0,1] & \quad \forall s \in S\\
\lambda\_s >\lambda\_{s'} & \quad \forall s,s' \in S:s

**In words**: the problem requires one to assign the elements of $A$ to the elements of $S$ such that the value of each assignment is determined as follows

* if an element $a$ is assigned to $s=1$, then the value of the assignment of this element is: $q\_{a}\lambda\_1$;
* if an element $a$ is assigned to $s=2$, then the value of the assignment of this element is: $q\_{a}\lambda\_2 c\_{a'}$ where $a'$ is assigned to $s=1$;
* if an element $a$ is assigned to $s=3$, then the value of the assignment of this element is: $q\_{a}\lambda\_3 c\_{a'} c\_{a''}$ where $a'$ is assigned to $s=1$ and $a''$ is assigned to $s=2$;
* and so on.

The total value of the assignment is given by the sum of the values of all the element assignments. So, with $|S|=3$, the total value is: $q\_{a}\lambda\_1 +q\_{a}\lambda\_2 c\_{a'} + q\_{a}\lambda\_3 c\_{a'} c\_{a''}$.

The problem is easy (but we do not know whether it is hard in general) when:

* $\lambda\_s = 1$: the algorithm is based on dynamic programming starting from the last $s$ and going backward to the first
* $c\_a=1$: the algorithm is simple, being a greedy optimizer.

**Question**: any idea on how to find a reduction for proving the NP-hardness of the problem?

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_1**: Why is your objective so complicated? Is this the standard assignment problem?  
> **username_0**: No, our problem is not the standard assignment problem. The difference between a 2IAP (2-index assignment problem) and our problem is precisely in the objective function. In the former case the objective function is linear, in the latter it is not.  
> **username_1**: You have written a nonlinear objective, but maybe it can be rewritten as linear by substituting in new parameters. Can you describe where this objective came from?  
> **username_0**: We have a set of objects $A$ that has to be allocated into an ordered set of positions $S$. We assume a user to scan the positions from the first to the last. Once the user gets a position, the probability that he stops depends on the position (probability \lambda_s) and on the specific object a allocated in such position (probability $c_a$).  
> **username_1**: Can you give motivation for your problem?  
> **username_0**: A situation like this one is, for example, typical in sponsored search auctions. The aim of the problem is to allocate in the best way, the one maximizing the social welfare, ads $A$ into slots $S$ (positions in a web page). Each slot has a probability to be seen by the user ($\lambda_s$). Moreover, with the cascade model (A Cascade Model for Externalities in Sponsored Search, Kempe and Mahdian) each ad is associated to another probability ($c_a$), that is the probability the user will continue to see the following slots, after having seen a given ad $a$.  

---

## 0 answers

