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.