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

讨价还价和市场理论，博弈论和数理经济学中的关键理论，有一个严重的缺点-除了一些孤立的结果，它们基本上是非算法的。 随着互联网的出现，互联网公司如Google、Yahoo！亚马逊、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.