From InterSciWiki

[edit] Singularity Theory and Complex Systems

One example of a complex system is the game theoretic interaction between economic agents. The most generic example of this is the classic n player game with utility maximizing agents. I consider it a compelx system because It contains:

• A large number of parts
• The parts are interdependent
• The parts are adaptive

Essentially the interdependence of a large number of adaptive agents is what I consider a classic example of social complexity. So it is of interest to be able to characterize the generic properties of equilibrium solution sets for an n player system. A paper by Amer Aladhadh and Donald Saari provides the generic properties of the solution sets provided by solution concepts.

The results show that equilibria such as Nash amongst many actors are generically isolated points. This means that changing the utility functions ever so slightly, there is a neighborhood around the old solution small enough not contain the old one.

More illuminating is the result that many types of constrained games generically have no Nash equilibria. This means that one can find some examples where they exist, but if you perturb the assumed functional assumptions ever so slightly, these equilibira disappear.

This idea where the number of actors will constrain the solution space further until it generically disappear. This method then offers an analytical method to classifying the complexity of problems by characterizing the dimension of the solution space.

The resutls give the dimension of both interior solution and corner solutions underlining the that increased compelixty of the porblem may reduce the dimension the space of interior equilibria or restrict the solution space to corner solutions.

[edit] P versus NP

One particular problem with the 3 SAT is filtering out redudnat linear constraints imposed by the number of logical conditions in the problem. I suspect that the reduction of the these equations into matricies, then using the balancedness condition used in cooperative game theory to weed out redundant linear constraints, may solve tha issue. If there was a singularity theory for that can handle the three SAT problem, one can show that the dimensions of the solution space is realted to seach time and that increased compelxity is the difference between p versus np. At the very least, singularity theory will give you the genenric properties of solutions and thereofore solution search time. I am responsible for all errors in the logic above, because it is mine alone, but if you wanted a great introduction to the 3 SAT and P versus NP, please see Chris Moore's excellent lecture on the institute for complexity 2008 Summer school.

[edit] Singularity Theory and Complex Systems

Amer Aladhadh 07:15, 9 August 2007 (PDT)