Algorithims and Markets

算法和市场随着互联网的出现，市场的概念发生了范式转变--谷歌、雅虎、亚马逊、MSN和eBay等互联网公司定义并推出了全新的、非常成功的市场。这一点，以及以集中式或分布式方式运行这些市场的巨大计算能力的可用性，促使了对市场的算法研究。这是PI研究的主要焦点。PI的研究还涉及算法理论中的一些基本开放问题--确定度量Steiner树问题的双向割松弛的完整性缺口，研究由计数问题引起的设计问题的复杂性。市场算法方面的工作包括处理凹效用函数的情况，开发计算市场均衡的分布式模型和算法，为一些新市场获得符合算法要求的市场模型，以及在假设查询的随机到达模型的情况下开发Adword问题的算法。这项研究将有助于主要优先领域--科学与工程进步(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.