Graph games

Graph games is a formalism from game theory . In graph games, each player is a node of a graph . The nodes of the graph alias player have connections to other nodes. As with normal form games, every player has a lot of strategies . The payout of a player depends via a function on his strategy and the strategy of the players connected to him. In general, any game in normal form can be converted into a graph game. The size of the graph game is only smaller than that of the strategic game in certain games. The graphic form is of no advantage, especially for 2-person games. In general, finding Nash equilibria in graph games is NP-difficult . Advantages d. H. fewer connections arise when player payouts are not dependent on all players' strategies. There is even a polynomial time solution algorithm for graphs that consist of a single path or a single loop .

literature

• E. Elkind, LA Goldberg, PW Goldberg: Nash equilibria in graphical games on trees revisited. ACM Conference on Electronic Commerce, 2006, pp. 100-109.
• M. Kearns, M. Littman, S. Singh: Graphical models for game theory. Proceedings of UAI, 2001.