On-Line Algorithms for Market Equilibria

摘要：

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 online, 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.

作者: Spyros Angelopoulos Atish Das Sarma Avner Magen Anastasios Viglas

作者单位: University of Waterloo IIT Bombay University of Toronto University of Sydney

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 596-607

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）