Patent ID: 7647281

Claim:
A computer-readable medium having computer-readable instructions embedded therein which, when executed by a computer, cause the computer to implement a method for facilitating determination of equilibrium values for a market system, the method for facilitating determination of equilibrium values for the market system comprising: receiving a number of types of goods m, a number of buyers (n+1), an initial amount of each good that each buyer possesses, and a utility function for each of buyers i=1, . . . , n, for the market system; applying a polynomial-time approximation method to the received data to generate an approximate equilibrium price vector for the market system, the polynomial-time approximation method comprising: initializing with an arbitrary first price vector p; setting a variable, D, to represent a maximum deficiency for the first price vector p; constructing an instance, M p , of the market system, wherein constructing the instance, M p , of the market system comprises: providing m types of goods and (n+1) buyers; setting, for i=1, . . . , n, a utility of buyer i for the goods as to be calculated from the corresponding utility function; establishing the budget of buyers i=1, . . . , n, according to: e 1 := ∑ j = 1 m ⁢ ⁢ p j ⁢ w j i , e i := ∑ j = 1 m ⁢ ⁢ p j ⁢ w j i , wherein e i is the budget of buyer i, p j is the price of good j in the first price vector, and w j i is equal to an initial amount of good j that buyer i possesses; setting, for i=(n+1), a utility of buyer i for each of goods j=1, . . . , m, as equal to p j ; and establishing the budget of buyer i=(n+1) as e (n+1) :=D; executing a DPSV algorithm on the instance, M p , starting from the first price vector p and increasing prices until equilibrium is reached, and outputting a second price vector (p′) via execution of the DPSV algorithm; setting a budget e i ′ for each buyer i with respect to the second price vector (p′) according to: e i ′ := ∑ j = 1 m ⁢ ⁢ p j ′ ⁢ w j i ; determining if a budget ratio (e i ′/e i ) for each buyer i satisfies a budget ratio constraint of: e i ′ / e i ⁢ < _ ⁢ 1 + ɛ , wherein ε represents a desired amount of approximation; identifying the second price vector (p′) when the budget ratio constraint is satisfied for every buyer i as the approximate equilibrium price vector for the market system; and iterating the polynomial-time approximation method with the first price vector p set equal to the second price vector (p′), instead of an arbitrary price vector, when the budget ratio constraint is unsatisfied, until the budget ratio constraint is satisfied; outputting the approximate equilibrium price vector to a computer monitor display; and setting prices based on the approximate equilibrium price vector.