Record Details

On-line algorithms for market equilibria

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title On-line algorithms for market equilibria
 
Creator ANGELOPOULOS, S
DAS SARMA, A
MAGEN, A
VIGLAS, A
 
Description We consider a variation of the classical problem of finding prices which guarantee equilibrium in linear markets consisting of divisible goods and agents with money. Specifically, we consider on-line algorithms for this problem in which goods are considered on-line, and each good is assigned an irrevocable price. Since exact equilibria will not be found in such a setting, we appeal to the concept of approximate equilibrium defined in previous studies of the problem, to characterize the quality of our solutions. We consider both deterministic and randomized algorithms for finding approximate equilibria. We prove a tight bound on the performance of deterministic algorithms, and show that under certain natural conditions, randomized algorithms lead to market prices which are closer to equilibrium.
 
Publisher SPRINGER-VERLAG BERLIN
 
Date 2011-10-23T18:01:35Z
2011-12-15T09:11:16Z
2011-10-23T18:01:35Z
2011-12-15T09:11:16Z
2005
 
Type Article; Proceedings Paper
 
Identifier COMPUTING AND COMBINATORICS, PROCEEDINGS,3595,596-607
3-540-28061-8
0302-9743
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15196
http://hdl.handle.net/100/1963
 
Source 11th Annual International Conference on Computing and Combinatorics (COCOON 2005),Kunming, PEOPLES R CHINA,AUG 16-29, 2005
 
Language English