Graph theory and game theory

Question

are there any areas of game theory which are studied by graph theoy? Do you know some good source on that?

Answer 1

In short, yes, but the applications of graph theory may not be as pure as you're looking for. Below are a sampling of micro-economics (which is all basically just applied game theory) that uses graph theory:

Network Economics Network economics is a hot field in econ at the moment, and it basically studies decentralized networks of agents rather than one 'centralized' (think Walrasian Auctioneer-esque) market.

Kranton Minehart 2001 is a good example of this. Deals with a general model of exchange in decentralized markets. Basically a direct application of Hall's Theorem.

Evolutionary Game Theory A lot of the work in evolutionary games came down to considering how large populations of myopic agents play over time. Many of these models rely on limiting the history of remembered play by agents to some finite number of 'records'. This effectively makes the overarching model of repeated play akin to a Markov Process on finitely many vertices, and thus relies on some graph theoretic reasoning.

Young 1993 is my favorite example of this. There is both a non-probabilistic graph theoretic proof about the convergence of the established process to repeated Nash equilibrium if the best reply graph of agents is weakly acyclic. Later, the Markov connection is exploited with some new graph theoretic proofs in the end. A gorgeous paper. (An interesting connection to how some graph theoretic stuff may be generalized, the requirement of weak acyclicity of best replies in the above can be seen as an analogous requirement to the property of supermodularity seen here; in effect, both serve to prevent cycles).

Cascades/Contagion Really a subset of the network economics topic, there's a lot of interest in how signals/events generally propagate through networks. A nice example of this is Acemoglu, Ozdaglar, Tahbaz-Salehi 2010.

Network Games This is, I suspect, what you most expected when asking the question. There is a branch of game theory that explicitly deals with games that have some sort of graphical structure. Kun, Powers and Reyzin 2013 is an example that discusses the relation between pure-strategy Nash equilibria in network games of anti-coordination and graph coloring problems.

Hope this is helpful!

Answer 2

I'm not sure exactly which flavor of research you're asking for, so this might not be what you wanted.

The mechanism design for kidney exchange literature uses and proves a number of graph-theoretical results. See e.g. (these papers can be found on the authors' websites, I am not sure if I can link directly to them, however).

Dynamic Matching via Weighted Myopia with Application to Kidney Exchange. By Dickerson et. al.

Maximum weight cycle packing in directed graphs, with application to kidney exchange programs By Biro et. al.

Mix and Match: A Strategyproof Mechanism for Multi-Hospital Kidney Exchange. By Itai Ashlagi et. al.

You can find other similar results by following references in these papers.