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!