2
$\begingroup$

I was given the following problem called the barter economy problem: Given a set of $n$ people $\{p_1, \ldots, p_n\}$ and a set of $m$ distinct objects $\{a_1, \ldots, a_m\}$, where each object $a_j$ is owned by exactly one person, and each person $p_i$ has a valuation function $v_i$ such that $v_i(a_j)$ is a non-negative integer representing how much object $a_j$ is worth to person $p_i$, determine whether there is a trade between any two people $p_i$ and $p_j$ with subsets of objects $A_i$ and $A_j$ they currently own, such that: The total valuation for $p_i$ of objects in $A_j$, $\sum_{a \in A_j} v_i(a)$, is greater than the total valuation for $p_i$ of objects in $A_i$, $\sum_{a \in A_i} v_i(a)$, and The total valuation for $p_j$ of objects in $A_i$, $\sum_{a \in A_i} v_j(a)$, is greater than the total valuation for $p_j$ of objects in $A_j$, $\sum_{a \in A_j} v_j(a)$. Basically, each of the two people, according to their own valuation function, values the objects they would receive from the trade strictly more than they value the items they're offering up. Note that the objects each people offer can be a subset of the objects they own. I want to prove that this problem is NP-complete.

It is simple to prove this problem is in NP. What's challenging is finding a known np-complete problem to reduce to it. My initial idea was the subset sum problem: for every element $x$ in the set $S$, create a corresponding object $a_x$ who's value is $v_i(a_x) = v_j(a_x) = x$, then give $p_i$ all the items and $p_j$ none of the items, and somehow assign a $T$ such that the 'yes' answers and 'no' answers to the problems are in correspondance. Is this the path I should continue to try to work down, or might anyone be able to suggest a better, more applicable problem to try to reduce from instead? I feel I'm not on the correct path, because an instance of barter economy involves a collection of people for whom we want to determine if a two-person trade exists, not just two people for whom we want to determine a trade exists, if i'm explaining that distinction clearly

$\endgroup$

1 Answer 1

1
$\begingroup$

You can reduce from subset-sum as follows: given a set of $n$ positive integers $x_1, \dots, x_n$ and a positive integer target $T$, consider an instance with $2$ people $p_1, p_n$ and $n+1$ objects $a_1, \dots, a_{n+1}$. Objects $a_1, \dots, a_n$ are owned by $p_1$ while $a_{n+1}$ is owned by $p_2$. The valuations are as follows: $v_1(a_i) = v_2(a_i) = x_i$ for $i=1, \dots, n$, $v_1(a_{n+1}) = T + 1$, and $v_2(a_{n+1}) = T-1$.

If there is a set of indices $S \subseteq \{1, \dots, n\}$ such that $\sum_{i \in S} x_i = T$, then we can trade $A_1 = \{ a_i \mid i \in S\}$ with $A_2 = \{ a_{n+1} \}$. Indeed: $$ \sum_{a \in A_1} v_2(a) = \sum_{i \in S} x_i = T > T-1 = v_2(a_{n+1}) = \sum_{a \in A_2} v_2(a), $$ and $$ \sum_{a \in A_2} v_1(a) = v_1(a_{n+1}) = T + 1 > T = \sum_{i \in S}x_i =\sum_{a \in A_1} v_1(a). $$

Conversely, if there is a trade $A_1$, $A_2$ such that $\sum_{a \in A_1} v_2(a) > \sum_{a \in A_2} v_2(a)$ and $\sum_{a \in A_2} v_1(a) > \sum_{a \in A_1} v_1(a)$, then we cannot have $A_2 = \emptyset$ and hence $A_2 = \{a_{n+1}\}$. Let $S = \{ i \mid a_i \in A_1\}$. The above conditions imply: $$ \sum_{i \in S} x_i = \sum_{a \in A_1} v_2(a) > \sum_{a \in A_2} v_2(a) = v_2(a_{n+1}) = T - 1, $$ and $$ T + 1 = v_1(a_{n+1}) = \sum_{a \in A_2} v_1(a) > \sum_{a \in A_1} v_1(a) = \sum_{i \in S} x_i. $$ Combining the above two inequalities we get $$ T + 1 > \sum_{i \in S} x_i > T - 1, $$ and since each $x_i$ is an integer, we must have $\sum_{i \in S} x_i = T$,

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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