ICAR Research Data Repository for Knowledge Management
DSpace at IIT Bombay
View Archive InfoMetadata
| Field | Value |
| Title | On-line algorithms for market equilibria |
| Names |
ANGELOPOULOS, S
DAS SARMA, A MAGEN, A VIGLAS, A |
| Date Issued | 2005 (iso8601) |
| Abstract | 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. |
| Genre | Article; Proceedings Paper |
| Identifier | COMPUTING AND COMBINATORICS, PROCEEDINGS,3595,596-607 |