Natural algorithms are processes that exist in nature and society, processes that do not appear to be explicitly designed or programmed. Typically, one infers the existence of such processes from the results that ensue (e.g. supply and demand balancing in an economic market) as opposed to an explicit presentation of the process (e.g. a procedure for price adjustment). Two questions arise: what are the processes (i.e. what steps do they undertake) and what are their capabilities and limitations? This project approaches the issue from a computational perspective.
The main focus will be on economic market equilibria, which can be characterized as prices that balance supply and demand. It is widely believed that economic markets tend to revert to equilibrium states following disturbances, and the issue studied here is when this might be possible. So the first question above amounts to asking what price adjustments might occur in markets to cause this to happen; the second question asks when, in fact, can these adjustments cause convergence to equilibrium, and if convergence can occur, how fast is it?
In prior work, a new way of incorporating time in the standard market models was proposed; this seems a necessity for modeling and analyzing price adjustment protocols. This project aims to develop that analysis in multiple dimensions, namely: (1) to account for discreteness of goods and money, (2) to handle dynamic environments, (3) to provide strategic explanations of participant behavior, (4) to incorporate production, (5) to analyze (some) environments in which the Weak Gross Substitutes assumption does not hold. Finally, the project will seek to develop analogous explanations and analyses for other self-governing systems, natural and otherwise, for example in biological systems and in network routing.
