# weighted subset exchange question

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?

• 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? – labxq Nov 27 '15 at 8:29
• 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, ... – Raphael Nov 27 '15 at 11:26

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