Result: On-line algorithms for market equilibria

Title:
On-line algorithms for market equilibria
Authors:
ANGELOPOULOS, Spyros, DAS SARMA, Atish, MAGEN, Avner, VIGLAS, Anastasios
Source:
COCOON 2005 : computing and combinatorics (Kunming, 16-29 August 2005)Lecture notes in computer science. :596-607
Publisher Information:
Berlin: Springer, 2005.
Publication Year:
2005
Physical Description:
print, 10 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Flots dans les réseaux. Problèmes combinatoires, Flows in networks. Combinatorial problems, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Recherche information. Graphe, Information retrieval. Graph, Algorithme déterministe, Deterministic algorithms, Algorithme randomisé, Randomized algorithm, Algoritmo aleatorizado, Analyse économique, Economic analysis, Análisis económico, Equilibre marché, Market equilibrium, Equilibrio mercado, Equilibre économique, Economic equilibrium, Equilibrio económico, Fixation prix, Pricing, Fijación precios, Marché, Markets, Mercado, Monnaie, Money, Moneda, Performance algorithme, Algorithm performance, Resultado algoritmo, Plan randomisé, Randomized design, Plan aleatorizado, Prix marché, Market price, Problème combinatoire, Combinatorial problem, Problema combinatorio
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
University of Waterloo, Canada
IIT Bombay, India
University of Toronto, United States
University of Sydney, Australia
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=17096447
Rights:
Copyright 2005 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Operational research. Management
Accession Number:
edscal.17096447
Database:
PASCAL Archive

Further Information

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.