TY - GEN

T1 - Tatonnement in ongoing markets of complementary goods

AU - Cheung, Yun Kuen

AU - Cole, Richard

AU - Rastogi, Ashish

PY - 2012

Y1 - 2012

N2 - This paper continues the study, initiated by Cole and Fleischer in [Cole and Fleischer 2008], of the behavior of a tatonnement price update rule in Ongoing Fisher Markets. The prior work showed fast convergence toward an equilibrium when the goods satisfied the weak gross substitutes property and had bounded demand and income elasticities. The current work shows that fast convergence also occurs for the following type of markets: All pairs of goods are complements to each other, and the demand and income elasticities are suitably bounded. In particular, these conditions hold when all buyers in the market are equipped with CES utilities, where all the parameters ρ, one per buyer, satisfy -1 < ρ ≤ 0. In addition, we extend the above result to markets in which a mixture of complements and substitutes occur. This includes characterizing a class of nested CES utilities for which fast convergence holds. An interesting technical contribution, which may be of independent interest, is an amortized analysis for handling asynchronous events in settings in which there are a mix of continuous changes and discrete events.

AB - This paper continues the study, initiated by Cole and Fleischer in [Cole and Fleischer 2008], of the behavior of a tatonnement price update rule in Ongoing Fisher Markets. The prior work showed fast convergence toward an equilibrium when the goods satisfied the weak gross substitutes property and had bounded demand and income elasticities. The current work shows that fast convergence also occurs for the following type of markets: All pairs of goods are complements to each other, and the demand and income elasticities are suitably bounded. In particular, these conditions hold when all buyers in the market are equipped with CES utilities, where all the parameters ρ, one per buyer, satisfy -1 < ρ ≤ 0. In addition, we extend the above result to markets in which a mixture of complements and substitutes occur. This includes characterizing a class of nested CES utilities for which fast convergence holds. An interesting technical contribution, which may be of independent interest, is an amortized analysis for handling asynchronous events in settings in which there are a mix of continuous changes and discrete events.

KW - amortized analysis

KW - ongoing fisher market

KW - tatonnement

UR - http://www.scopus.com/inward/record.url?scp=84863535723&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863535723&partnerID=8YFLogxK

U2 - 10.1145/2229012.2229039

DO - 10.1145/2229012.2229039

M3 - Conference contribution

AN - SCOPUS:84863535723

SN - 9781450314152

T3 - Proceedings of the ACM Conference on Electronic Commerce

SP - 337

EP - 354

BT - EC '12 - Proceedings of the 13th ACM Conference on Electronic Commerce

T2 - 13th ACM Conference on Electronic Commerce, EC '12

Y2 - 4 June 2012 through 8 June 2012

ER -