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

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

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.