Assume there is a set {1,...,n} of person. For each person i, a set $A_i$ of items are available for exchange. A is the set of all items. The value of item j to person i is $v_{ij}$ and assume all values are positive integers. The question is, does there exist a pair of person who can both make profit by exchanging some of their items in $A_i$.Formally:$\exists$ i and i' and $S_i\subseteq A_i$ and $S_{i'}\subseteq A_{i'}$ such that $\sum_{j\in S_i} v_{i'j}>\sum_{j\in S_{i'}} v_{i'j}$ and $\sum_{j\in S_{i'}} v_{ij}>\sum_{j\in S_{i}} v_{ij}$ I'm not sure whether this question is NP-Complete or there exists a polynomial-time algorithm?

  • $\begingroup$ Since the number of subsets of $A_i$ is exponential so I guess it should be NP-Complete but i don't know how to make a reduction from what kind of NP-Complete problem. Maybe from knapsack or something else? Any suggestion? $\endgroup$ – labxq Nov 27 '15 at 8:29
  • 1
    $\begingroup$ Oh no, no, nonono. That's not an argument at all. Sorting has a super-exponential search space, yet it can be solved in $O(n \log n)$ time. There are many other such problems: SSSPP, APSPP, CFG parsing, ... $\endgroup$ – Raphael Nov 27 '15 at 11:26

It looks like your question can be written formally

$\exists i,j\in\{1,..,n\}\:\exists S\subseteq A_i\:\exists T\subseteq A_j : (\sum_{y\in T}v_{i,y}>\sum_{x\in S}v_{i,x})\land (\sum_{x\in S}v_{j,x}>\sum_{y\in T}v_{j,y})$

If the above is true, then persons $i$ and $j$ benefit from swapping items from $S$ and $T$.

This is hard to decide. Here is an idea for a reduction. We simplify things by assuming there are only two persons $P_1$ and $P_2$, that $P_1$ has just coins and banknotes in $A_1$, that $P_2$ has just $A_2=\{x\}$ and that they would both profit if $P_1$ can buy item $x$ at price $V$ from $P_2$. This is because $v_{1,x}-1=V=v_{2,x}+1$, i.e., $P_1$ thinks that by paying $V$ for $x$ he wins $1$, while $P_2$ thinks he wins $1$ by selling $x$. They will trade iff $P_1$ can find some coins and notes in his $A_1$ that add up to $V$ exactly (we assumes that $P_2$ only has $A_2=\{x\}$ so he cannot make any change). NB: the coins and notes are items $c\in A$ with $v_{1,c}=v_{2,c}$, their face value is the same for both persons.

  • $\begingroup$ Thank you for your comment, x and y should be a set, I have made my question more formal. $\endgroup$ – labxq Nov 27 '15 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.