AF: Small: Algorithmic and Game-Theoretic Issues in Bargaining and Markets

AF：小：讨价还价和市场中的算法和博弈论问题

• 批准号: 0914732
• 负责人: Vijay Vazirani
• 金额: $ 50万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-07-01 至 2013-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0914732&HistoricalAwards=false
• 关键词: AF; Small; Algorithmic; Game; Theoretic

The theories of bargaining and markets, key theories within game theory and mathematical economics, suffer from a serious shortcoming -- other than a few isolated results, they are essentially non-algorithmic. With the advent of the Internet, totally new and highly successful markets have been defined and launched by Internet companies such as Google, Yahoo!, Amazon, MSN and Ebay, and bargaining has emerged as a mechanism of choice in some Internet transactions, such as those made by priceline.com and iOffer.com. Motivated by these developments, much work has been done in the last decade on developing algorithms for markets and bargaining.This project will extend this work along several exciting directions: attacking open problems remaining in the efficient computation of market equilibria such as Fisher's model with piecewise-linear, concave utilities; extending bargaining algorithms to more general utility functions, such as piecewise-linear, concave utilities; developing an algorithm for the Adwords problem that achieves 1 - o(1) expected competitive ratio in the stochastic setting, and at the same time, a 1 - 1/e ratio in the worst case; developing models of bargaining that incorporate constraints such as timing or incentive compatibility, thus making them more suitable for use on the Internet; developing further our understanding of game-theoretic properties of bargaining and markets; and developing further the primal-dual paradigm for the combinatorial solution of nonlinear convex programs, in particular, in the setting of approximation algorithms.This project will increase our understanding of the interactions and complex interdependencies of information systems, markets and social systems. It will enable and support efficient massive distributed systems. This project will provide algorithms for and insights into the computational aspects of markets and transactions on the Internet, thereby helping make their operation more efficient. Hence, this project is expected to contribute advances in science and engineering, as well as to promote economic prosperity.

讨价还价和市场理论是博弈论和数理经济学中的关键理论，有一个严重的缺陷——除了一些孤立的结果之外，它们本质上是非算法的。 随着互联网的出现，谷歌、雅虎、亚马逊、MSN 和 Ebay 等互联网公司定义并推出了全新且非常成功的市场，讨价还价已成为某些互联网交易中的一种选择机制，例如由priceline.com 和iOffer.com 制作的。 在这些发展的推动下，过去十年在开发市场和讨价还价算法方面已经做了很多工作。该项目将沿着几个令人兴奋的方向扩展这项工作：解决市场均衡有效计算中剩余的开放问题，例如分段费希尔模型-线性、凹面公用设施；将讨价还价算法扩展到更通用的效用函数，例如分段线性、凹效用；开发一种针对 Adwords 问题的算法，在随机设置下实现 1 - o(1) 预期竞争比，同时在最坏情况下实现 1 - 1/e 比；开发包含时间或激励兼容性等限制的讨价还价模型，从而使其更适合在互联网上使用；进一步发展我们对讨价还价和市场的博弈论特性的理解；进一步发展非线性凸规划组合解的原对偶范式，特别是在近似算法的设置中。该项目将增进我们对信息系统、市场和社会系统之间的相互作用和复杂相互依赖关系的理解。它将启用并支持高效的大规模分布式系统。该项目将为互联网上的市场和交易的计算方面提供算法和见解，从而帮助提高其运营效率。因此，该项目有望促进科学和工程的进步，并促进经济繁荣。