Algorithims and Markets

算法和市场随着互联网的发展，市场的概念发生了范式转变--互联网公司如谷歌、雅虎、亚马逊、MSN和eBay。这一点，以及以集中或分布式方式运行这些市场的巨大计算能力的可用性，激发了对市场的算法研究。这是PI的主要研究重点。PI的研究还涉及算法理论中一些基本的开放问题的工作-确定度量Steiner树问题的双向切割松弛的完整性间隙，并研究由计数问题引起的设计问题的复杂性。市场算法的工作涉及处理凹效用函数的情况，开发用于计算市场均衡的分布式模型和算法，获得用于一些新市场的算法适用的市场模型，以及开发用于假设查询的随机到达模型的Adwords问题的算法。这项研究将有助于主要优先领域，在科学和工程（ASE）的进步，并将促进经济繁荣和充满活力的公民社会（ECS）。其更广泛的影响包括培训研究生和通过论文、课程、讲座和讲习班传播研究成果。

Algorithms and MarketsThe notion of a market has undergone a paradigm shift with the Internet -- totally new and highly successful markets have been defined and launched by Internet companies such as Google, Yahoo!, Amazon, MSN and Ebay. This, and the availability of massive computational power for running these markets in a centralized or distributed manner, has motivated an algorithmic study of markets. This is the primary focus of the PI's research.The PI's research also involves work on some fundamental open problems in the theory of algorithms -- determining the integrality gap of the bidirected cut relaxation for the metric Steiner tree problem and studying the complexity of design problems arising from counting problems.The work on algorithms for markets involves handling the case of concave utility functions, developing distributed models and algorithms for computing market equilibria, obtaining algorithmically-amenable market models for some of the new markets, and developing an algorithm for the Adwords problem assuming a stochastic arrival model for the queries. This research will contribute to the Primary Priority Area, Advances in Science and Engineering (ASE), and will promote Economic Prosperity and Vibrant Civil Society (ECS). Its broader impacts involve the training of graduate students and the dissemination of research results via papers, courses, lectures and workshops.