RESEARCH COLLOQUIUM ON COMPUTATIONAL SOCIAL SCIENCE/DATA SCIENCES – Robert Axtell – Learning Approximate Competitive Equilibria in Large Economies in Polynomial Time

When:
February 28, 2020 @ 3:00 pm – 4:00 pm
2020-02-28T15:00:00-05:00
2020-02-28T16:00:00-05:00
Where:
CENTER FOR SOCIAL COMPLEXITY SUITE, 3RD FLOOR, RESEARCH HALL
Cost:
Free
Contact:
Karen Underwood
7039939298

Research Colloquium on Computational Social Science/Data Science

Robert Axtell
Professor Computational Social Science Ph.D. Program
George Mason University

Learning Approximate Competitive Equilibria
in Large Economies in Polynomial Time

Friday, February 28, 3:00 p.m. – 4:00 p.m.
Center for Social Complexity Suite, 3rd Floor Research Hall

All are welcome to attend.

Abstract:
While the existence of competitive equilibria is guaranteed via fixed point theorems, the determination of prices that clear markets and balance individual budgets is well-known to be an intractable computational problem, technically in the complexity class PPAD. In contrast, approximating Pareto optimal allocations that are not budget-balanced is readily accomplished in polynomial time through local exchange processes, without first computing prices. Here we describe an iterative process of agent learning about competitive prices in which agents repeatedly engage in local exchange in stationary economic environments, progressively constraining the prices they pay toward the competitive ones. For small economies it is known that such processes can get stuck away from equilibria. In large economies we demonstrate ways to avoid getting stuck, leading to approximately competitive prices and allocations.