Duality in Multi-Commodity Market Computations
The first part of the paper is very technical and written for people with
a computer science and economics background,with special interest in mathematics.
The section on any-time algorithms is however more easily read.
Ins earch for general equilibrium in multi-commodity markets, price-oriented
schemes are normally used.That is,a set of prices(one price for each
commodity) is updated until supply meets demand for each commodity.It is
well known that in a two-commodity market resource-oriented schemes are
conceivable. In this paper we demonstrate the duality between price-and
resource-oriented schemes in the general multi-commodity case. We also discuss
important properties of the two approaches.
In resource-oriented schemes the resource constraint, which says that
supply must equal demand, is always fulfilled, implying that at anytime
the auctioneer can provide a feasible allocation. This is not the case
in price-oriented schemes outside market equilibrium. In this paper we
introduce an ovelany-time algorithm,PROPORTION,
for the price-oriented scheme as well, that allows the auctioneer to deliver
a suitable allocation at some deadline(possibly unknown in advance)also
before market equilibrium is reached.We also show how the findings for
the any-time algorithms can enable more efficient price-oriented markets.
The entire paper in PDF format.
The slides from the presentation in PDF format.