In a barter economy, people trade goods and services directly, without money as an interme...

In a barter economy, people trade goods and services directly, without money as an intermediate step in the process. Trades happen when each party views the set of goods they're getting as more valuable than the set of goods they're giving in return. Historically, societies tend to move from barter-based to money-based economies; thus various online systems that have been experimenting with barter can be viewed as intentional attempts to regress to this earlier form of economic interaction. In doing this, they ve rediscovered some of the inherent difficulties with barter relative to money-based systems. One such difficulty is the complexity of identifying opportunities for trading, even when these opportunities exist.

To model this complexity, we need a notion that each person assigns a value to each object in the world, indicating how much this object would be worth to them. Thus we assume there is a set of n people p1,…,pn, and a set of m distinct objects a1,..., am. Each object is owned by one of the people. Now each person pt has a valuation function vi, defined so that vi(aj) is a nonnegative number that specifies how much object aj is worth to pi– the larger the number, the more valuable the object is to the person. Note that everyone assigns a valuation to each object, including the ones they don t currently possess, and different people can assign very different valuations to the same object.

A two-person trade is possible in a system like this when there are people Pi and pj, and subsets of objects At and Aj possessed by pt and pj, respectively, so that each person would prefer the objects in the subset they don t currently have. More precisely,

• pi's total valuation for the objects in Aj exceeds his or her total valuation for the objects in Ai, and

• pj s total valuation for the objects in Ai exceeds his or her total valuation for the objects in Aj.

(Note that Ai doesn t have to be all the objects possessed by pi (and likewise for Aj); Ai and Aj can be arbitrary subsets of their possessions that meet these criteria.)

Suppose you are given an instance of a barter economy, specified by the above data on people s valuations for objects. (To prevent problems with representing real numbers, we ll assume that each person s valuation for each object is a natural number.) Prove that the problem of determining whether a two-person trade is possible is NP-complete.