COMPUTATIONAL SOCIAL SCIENCE

**Friday, February 18 1:30-2:30 p.m**

**Location: Science and Tech I, Room 242**

Title: Some Open Mathematical Problems in Computational Social Science

Robert Axtell, Computational Social Science, George Mason University

Abstract: In multi-agent systems (MAS) social science a large number of software agents interact socially, producing patterns and structure at the population level. Despite having complete knowledge of individual agent states and behaviors, it is usually difficult or impossible to analytically derive macro-patterns, except in certain simple cases. I shall give four examples where mathematicians have waded into this field and increased our understanding, but where outstanding open problems remain. Specifically:

1. One of the first models of this type was Schelling's segregation model (1969), an abstract representation of housing location decisions on a 2D landscape. Recently an exact, asymptotic solution for this problem has appeared in 1D. I will summarize this and comment on the likelihood of extending it to two dimensions.

2. The spontaneous formation of 'flocking' behaviors among mobile agents has been well know for over 20 years in two dimensions. Recently S. Smale and co-workers have formulated the general problem in 3D and proven various theorems related to the dynamics of flocks, with detailed results for 2 agents in one dimension. I will review this work.

3. The existence of Walrasian equilibria in the theory of general economic equilibrium is proved via the Brouwer fixed-point theorem, and constructively computed using a variant of Sperner's lemma from graph theory. Recently it has been shown that such problems are essentially NP-complete. However, MAS models of markets are guaranteed to produce equilibria in polynomial time. The relevance of these results to the P = NP problem will be conjectured.

4. If sufficient time I will conclude by mentioning some problems in agent-based financial market models having to do with the spontaneous formation of 'ecologies' of trading strategies and their co-evolution.