Home > Downloads




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.

Abstract

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.