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

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

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.