Book contents
- Frontmatter
- Contents
- Foreword
- Preface
- Contributors
- I Computing in Games
- 1 Basic Solution Concepts and Computational Issues
- 2 The Complexity of Finding Nash Equilibria
- 3 Equilibrium Computation for Two-Player Games in Strategic and Extensive Form
- 4 Learning, Regret Minimization, and Equilibria
- 5 Combinatorial Algorithms for Market Equilibria
- 6 Computation of Market Equilibria by Convex Programming
- 7 Graphical Games
- 8 Cryptography and Game Theory
- II Algorithmic Mechanism Design
- III Quantifying the Inefficiency of Equilibria
- IV Additional Topics
- Index
5 - Combinatorial Algorithms for Market Equilibria
from I - Computing in Games
Published online by Cambridge University Press: 31 January 2011
- Frontmatter
- Contents
- Foreword
- Preface
- Contributors
- I Computing in Games
- 1 Basic Solution Concepts and Computational Issues
- 2 The Complexity of Finding Nash Equilibria
- 3 Equilibrium Computation for Two-Player Games in Strategic and Extensive Form
- 4 Learning, Regret Minimization, and Equilibria
- 5 Combinatorial Algorithms for Market Equilibria
- 6 Computation of Market Equilibria by Convex Programming
- 7 Graphical Games
- 8 Cryptography and Game Theory
- II Algorithmic Mechanism Design
- III Quantifying the Inefficiency of Equilibria
- IV Additional Topics
- Index
Summary
Abstract
Combinatorial polynomial time algorithms are presented for finding equilibrium prices and allocations for the linear utilities case of the Fisher and Arrow–Debreu models using the primal-dual schema and an auction-based approach, respectively. An intersting feature of the first algorithm is that it finds an optimal solution to a nonlinear convex program, the Eisenberg-Gale program.
Resource allocation markets in Kelly's model are also discussed and a strongly polynomial combinatorial algorithm is presented for one of them.
Introduction
Thinkers and philosophers have pondered over the notions of markets and money through the ages. The credit for initiating formal mathematical modeling and study of these notions is generally attributed to nineteenth-century economist Leon Walras (1874). The fact that Western economies are capitalistic had a lot to do with the over-whelming importance given to this study within mathematical economics – essentially, our most critical decision-making is relegated to pricing mechanisms. They largely determine the relative prices of goods and services, ensure that the economy is efficient, in that goods and services are made available to entities that produce items that are most in demand, and ensure a stable operation of the economy.
A central tenet in pricing mechanisms is that prices be such that demand equals supply; that is, the economy should operate at equilibrium. It is not surprising therefore that perhaps the most celebrated theorem within general equilibrium theory, the Arrow–Debreu Theorem, establishes precisely the existence of such prices under a very general model of the economy.
- Type
- Chapter
- Information
- Algorithmic Game Theory , pp. 103 - 134Publisher: Cambridge University PressPrint publication year: 2007
- 20
- Cited by