Exchange Market Equilibrium and Auction Pricing

复杂性理论是高性能计算的基础。该理论的目标是制定衡量各种计算算法有效性的标准。术语“复杂性”指的是计算所需的资源量。在这个项目中，运行时间或算术运算的数量是您感兴趣的主要资源。线性规划一直是复杂性分析中的一个重要计算问题。由于线性规划算法的不懈研究，今天线性规划的求解速度比20年前快了一百万倍。现在，大大小小的企业都使用LP模型来控制制造库存、为商品定价、设计民用/通信网络以及规划投资。LP甚至成为本科生/研究生和MBA课程中的热门课程，促进了人类知识和科学教育。现在，许多其他重要的计算问题正在出现或重新出现。特别是，在互联网经济、信息网络、拍卖/游戏定价以及通过万维网实现的社会组织问题中出现的问题的模型、理论和算法方面的趋势越来越大。该项目的目的是进一步发展和扩展复杂性理论和有效方法来应对这些突发事件，由于它们在当今美国服务经济中的广泛应用，如贸易、拍卖、谈判和信息聚合，人们对更快、更准确地解决这些突发事件有着强烈的兴趣。具体地说，提出了以下研究目标和活动：交易所市场均衡：开展解决几个交易所市场价格均衡问题的算法和复杂性研究，包括纳什均衡，其中许多具有挑战性的问题是开放的，需要回答者；拍卖博弈机制设计：提出并分析了未定权益市场的凸平价买入拍卖定价机制，并建立了对一些不确定未来事件的预测模型；实时或动态定价：对实时或动态拍卖进行定价研究，例如关键字搜索中的创新拍卖市场，为互联网搜索业务销售广告。所提出的研究将加深我们对这些新出现的计算价格均衡问题的复杂性的理解，并可能解决是否采用高效算法的重要悬而未决的问题。研究活动因项目本身的性质而对社会产生影响：完善的市场交易体系和经济定价机制。在开发解决大规模博弈/均衡问题的有效算法方面的进展将对提高互联网/信息系统和在线/网络商业服务管理的效率具有重要意义。加强这方面的研究将有助于国家在产业竞争力、科学认识、技术创新和人类知识方面的利益。学生将参与这个项目，项目活动中的材料将被用来制作研究生水平的教材，并形成一门新课程的基础，该课程名为《均衡与优化》。

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''.