Algorithims and Markets

算法和市场

• 批准号: 0728640
• 负责人: Vijay Vazirani
• 金额: $ 30万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728640&HistoricalAwards=false
• 关键词: Algorithims; Markets

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.

算法和市场随着互联网的发展，市场的概念已经发生了范式转变——谷歌、雅虎、亚马逊、MSN 和 Ebay 等互联网公司定义并推出了全新且非常成功的市场。这一点，以及以集中或分布式方式运行这些市场的大量计算能力的可用性，激发了对市场的算法研究。这是 PI 研究的主要焦点。PI 的研究还涉及算法理论中一些基本的开放问题的工作——确定度量 Steiner 树问题的双向剪切松弛的完整性差距以及研究设计问题的复杂性市场算法的工作涉及处理凹效用函数的情况，开发计算市场均衡的分布式模型和算法，获得一些新市场的算法上适用的市场模型，以及开发一种算法AdWords 问题假设查询采用随机到达模型。这项研究将为首要优先领域——科学与工程进展（ASE）做出贡献，并将促进经济繁荣和充满活力的公民社会（ECS）。其更广泛的影响包括研究生培训以及通过论文、课程、讲座和研讨会传播研究成果。