On the efficiency and complexity of computational and economic processes

The dissertation consists of four parts.;In part 2, we study certain iterative algorithms for finding zeros of functions, with an emphasis on the global convergence property. The possibility of achieving global convergence is investigated in various settings and an impossibility as well as some possibility theorems are proved.;We address the price adjustment problem in part 3. We argue that the traditional models fail to satisfactorily model the invisible hand because of their exclusion of some important, relevant environmental information about the economies. By using the globally convergent algorithm constructed in part 2, we show that by estimating certain environmental information of the economies a globally as well as locally stable price adjustment process can be constructed for two-good economies.;In part 4, we extend Smale's work on the fast convergent initial points (i.e., the approximate zeros) for Newton's method to general locally quadractically convergent algorithms. We obtain a similar sufficient condition for the initial points to be fast convergent.;Part 1 is devoted to the efficiency and complexity problem of decentralized information systems, which include as special cases decentralized economic mechanisms and distributed computing networks. A lower bound is given for the dimension of the message space of a decentralized economic mechanism that realizes a given goal function of two-agent economies. This result is then extended to the general situation with any number of agents. A necessary condition is obtained for the existence of a decentralized economic mechanism with a message space of any given dimension for realizing a given goal function. By applying the lower bound result for the mechanism theory to Abelson's model of distributed computations, we obtain a lower bound for the information transfer which is different from that of Abelson and is sharper in many cases.