# Computation of Equilibrium Prices

##### Ran Duan & Kurt Mehlhorn

## Computation of Equilibrium Prices

The balance between supply and demand takes place through pricing. For a particular good, the question of the equilibrium price is easy to resolve. Demand is a decreasing function of the price and supply is an increasing function of the price. Therefore, there is always an equilibrium price at which supply and demand balance out. But what happens in an economy with many goods, many suppliers, and many buyers?

#### The market models of Fisher and Walras

Already in the 19th century, Fisher (1890) and Walras (1875) introduced mathematical models for markets. Fisher’s model is as follows: There exist buyers and goods. Buyers have a certain budget and preference with respect to the goods; goods are available in a certain quantity. The preference states how much utility a buyer obtains from a given quantity of a particular good. In the simplest case of a linear preference, the utility is a linear function of the quantity. We further assume that goods have prices: a unit of good X has a price p(X). Then for each buyer and each good, there is an amount of utility per unit of money. Given a price of 2 Euro for a bottle of champagne and 1 Euro for a bottle of beer, for many buyers the utility per unit of money is higher for champagne than for beer. Fisher then postulates that each buyer buys only those goods that would, for them, maximize their utility per unit of money. Fisher asks whether there are always prices such that all of the buyers spend their entire budget and all of the goods are sold.

Walras’ model is a bit different: He does not assume that buyers have a certain amount of money right from the start. Rather, buyers are also sellers. They own goods and receive money only through the sale of goods. The question is again the same: Are there prices such that all of the buyers spend all of the money they have received by selling their goods, and are all of the goods sold?

In Fisher’s model, money has an intrinsic value; in Walras’ model it serves only to compare goods. Fisher’s model is a special case of Walras’.

#### Existence of equilibrium prices

It took until 1954 before the existence of equilibrium prices was mathematically stringently proven by Arrow and Debreu. Arrow and Debreu were awarded the Nobel Prize in Economics for that and for other achievements. Their proof is nevertheless purely a proof of existence and does not produce a method for calculating equilibrium prices.

#### Calculation of equilibrium prices

Can one efficiently calculate equilibrium prices? It took multiple decades before the answer was found for Walras’ model. First in 2007, K. Jain found an algorithm with polynomial runtime, although it was still not satisfactory because of their use of the ellipsoid method. In 2012, Ran Duan and Kurt Mehlhorn found a relatively simple combinatorial algorithm.

## Ran Duan

DEPT. 1 Algorithms and Complexity

Phone +49 681 9325-1009

Email duanran@mpi-inf.mpg.de

## Kurt Mehlhorn

DEPT. 1 Algorithms and Complexity

Phone +49 681 9325-1000

Email mehlhorn@mpi-inf.mpg.de