September 04, 2009
Market Reductions
Last month, Ye Du defended his dissertation in Computer Science at the University of Michigan. His thesis included several interesting contributions at the boundary of economic and computational theory, for example regarding the complexity of equilibrium computations, connecting game theory and general equilibrium.
One particular result I found interesting was a reduction from Markov chains to Cobb-Douglas exchange economies. That is, Ye showed that any Markov chain could be mapped to a set of consumers with Cobb-Douglas utility functions, such that the steady-state probabilities of the chain correspond to competitive equilibrium prices in the economy. This result can be applied in a standard way to solve Markov chains by computing economic equilibria, though there seems little advantage to this. More intriguing is the potential that the economic interpretation may lend to applications of Markov chains. In his thesis, Ye notes the use of Markov chains in PageRank and similar algorithms, and suggests that variations on the Cobb-Douglas economy (i.e., different classes of utility functions) could define a broad family of ranking algorithms.
To be frank, one reason the market reduction piqued my interest was that Dave Pennock and I did something analogous in a 1996 UAI paper, where we reduce Bayesian networks to production economies. (Though Bayes nets are more general than Markov chains, Ye Du's reduction is technically superior for the latter case.)
Market reductions like these provide answers to the question "What can a market compute?", and we might hope also yield insights on the source problem for the reduction. Are there other examples of market reductions? A catalog might be useful.
Posted by wellman at 09:22 PM | Comments (0) | TrackBack (0)
August 08, 2009
Threads of Research on Generic CDA Strategies
Research on trading strategy for generic continuous double auctions (CDAs) seems to take place on four parallel and minimally interacting threads. By "generic CDA", I mean models of two-sided continuous trading of an abstract good, as distinct from strategies for predicting movements in financial markets.
1. Auction Theory. The static or one-shot double auction is well-characterized in auction-theoretic terms. Work on the dynamic case is much more rare and less successful. The pinnacle of this work as far as I can tell is a 1987 paper by Robert Wilson, which is heroic and insightful but does not reach definitive conclusions.
2. Artificial Trading Agents. Given the limited success of game-theoretic treatments, researchers have encoded strategies computationally in artificial trading agents, and evaluated them in simulation. Prominent efforts in this category includes work by Gjerstad, Cliff, Tesauro, and others. Julian Schvartzman and I have one of the latest contributions on this thread.
3. Agent-Based Finance. There is a substantial literature that also simulates heuristic agent strategies, but with the aim of analyzing global properties of market dynamics (e.g., reproducing qualitative phenomena from financial markets), rather than identifying superior strategies. Blake LeBaron is a major representative researcher in this area, and has written a fairly recent survey.
4. Market Microstructure. The finance literature addresses trading strategy, primarily from the perspective of market makers or liquidity providers. Their models differ from those above, in that the traders do not have fundamental private value for the abstract good.
Threads #2 and #3 share some common heritage in the Santa Fe Double Auction Tournament of 1990, and some strategies proposed in one thread are used in the other. In my recent work I am attempting to connect #1 and #2 by performing game-theoretic analysis of trading agents. Thread #4 seems the most isolated, though in principle its results should be quite relevant to the other threads, and vice versa.
So the question is: what are the most promising approaches for unifying these threads? Or is there some reason (beyond differences of their primary academic communities) they should develop independently?
Posted by wellman at 11:50 AM | Comments (0) | TrackBack (0)
