Complexity theory is the foundation of high-performance computing. The goal of the theory is to develop criteria for measuring effectiveness of various computational algorithms. The term ''complexity'' refers to the amount of resources required by a computation. In this project, running time or number of arithmetic operations is the major resource of interest. Linear programming (LP) has been an important computational problem in complexity analysis. Due to the relentless research effort in LP algorithms, a linear program can be solved today one million times faster than it was done twenty years ago. Businesses, large and small, now use LP models to control manufacture inventories, price commodities, design civil/communication networks, and plan investments. LP even becomes a popular subject taught in under/graduate and MBA curriculums, advancing human knowledge and promoting science education. Now many other important computational problems are emerging or reemerging. In particular, there has been a growing trend in models, theories, and algorithms on problems arisen in Internet economics, information network, auction/game pricing, as well as social organization issues enabled through World Wide Web. The aim of the project is to further develop and extend complexity theories and efficient methods to responding these emergencies, where there is strong interest in solving them faster and more accurate due to their wide applications in today's US service economy, such as trade, auction, negotiation, and information aggregation. More specifically, the following research objectives and activities are proposed: Exchange market equilibrium: develop the algorithmic and complexity research on solving several exchange market price equilibrium problems, including the Nash equilibrium, where many challenging questions are open and need answerers; Auction-game mechanism design: propose and analyze a convex pari-mutuel call auction pricing mechanism for contingent claim markets and to develop a forecast model for some uncertain future events; Real-time or dynamic pricing: conduct research for pricing real-time or dynamic auctions, such as innovative auction markets in key-word search to sell advertisements for Internet search business.
The proposed research will deepen our understanding of complexities of these emerging computational price equilibrium problems and possibly resolve important open questions on whether or not they admit high efficient algorithms. The research activities have an influence on society by the project's very nature: improved market trading systems and economic pricing mechanism. Progress in the areas of developing efficient algorithms for solving large-scale game/equilibrium problems will be of great significance in improving the efficiency of Internet/information systems and on-line/network business service management. Strengthening research in this area will contribute to the national interest in industrial competitiveness, scientific understanding, technology innovation, and human knowledge. Students will participate in the project, and materials from the project activities will be used to create teaching materials at a graduate level and form the basis of a new course on ''Equilibrium and Optimization''.
