An approximate algorithm for computing Fisher's market equilibrium under a simple case of piecewise-linear, concave utilities

スポンサーリンク

概要

• 論文の詳細を見る

• We give the first weakly polynomial time algorithm for computing an ε-approximate equilibrium for a simple case of piecewise-linear utilities case of Fisher's market model. Assume that set B of buyers and a set G of goods are given. Each buyer has an initial integral ei of money. The integral utility and budget for buyer i of good j are Uij and tij, respectively. Each buyer i is not allowed to spend more than budget tij for good j. For finding ε-approximate equilibrium, the algorithm runs in O(((m + n) log n/ε)(m + n log n)), where n = |B| + |G| and m is the number of pairs (i, j) for which Uij > 0. The algorithm is based on the previous best running time of O((n log n/ε)(m+n log n)) for linear utilities case without constraining condition for budgets, due to Orlin5).

• 2011-11-11

著者

• Hiroshi Imai

  Department Of Computer Science The University Of Tokyo

関連論文

• An approximate algorithm for computing Fisher's market equilibrium under a simple case of piecewise-linear, concave utilities

スポンサーリンク