Paul Resnick (presnick) wrote,
Paul Resnick
presnick

Michael Kearns on network models for game theory and economics

I just attended a fascinating seminar by Michael Kearns, an AI researcher at UPenn. In recent work on combinatorial auctions and allocation of network resources there has been a convergence of computer science theorists and economic theorists. Kearns (and some others) are bringing to that mix the AI focus on the properties of alternative representations in terms of the reasoning that they facilitate.

Kearns' basic idea is to impose some structure on game theoretic models involving large numbers of players. In Nash equilibrium models, suppose that each agent's payoffs depend on the actions of only a few of the other agents. That leads to a graph representation (players are nodes; directed edge if another player's action affects this player's payoffs) from which it is possible to more efficiently compute the Nash equilibria. In correlated equilibria, suppose that each player's strategy is independent of most other players' strategies, contingent on the choices of just a few players. Those players can be connected with edges, but you still might have sparse graph that allows for certain computations to happen more quickly. In Arrow-Debreu general equilibrium models, suppose that only local exchanges are possible, and define a new form of equilibrium that requires all the local markets to be in equilibrium. The final idea builds on that to make use of recent work in mathematical foundations of random and not-so-random graphs to generate plausible local exchange structures.

This stuff is far enough from what I work on these days that it's fun to go to a well-presented summary of recent trends, but not to read all the individual papers or hear a talk on just one result. Kearns is a terrific presenter, so this was great!
Comments for this post were disabled by the author