A beautiful history of Game Theory and Graph Theory: how they were connected and developed
Over the course flow, I have been reflecting on the connection of game theory and graph theory, and how both concepts all be linked to the theme of our theme Networks. We may get some insights from the definition: “Graph theory is the study of network structure, while game theory provides models of individual behavior in settings where outcomes depend on the behavior of others.” [1] It occurs to me that these theories perfectly combine with each other to produce richer models of behaviors on networks.
In our textbook, there is a great example showing this combination: the Medieval trade routes. Just as it is described: “physical networks constrain the patterns of interaction, giving certain participants an intrinsic economic advantage based on their network position.”[1]
According to the knowledge from class, we can know that there may be mechanism behind the above reasoning. If I take Barcelona as starting point and Paris as the destination and we only consider time-consumption, we can see there are two ways. One is road trip via Bordeaux, and the other is sailing trip via Valencia, Palma, Cadiz, Lisbon, and Southampton. Road trip is obviously the dominant strategy for many merchants as it is the most time-saving strategy, which leaves sailing not the first choice for many merchants. (There are still some merchants who intendedly want to drop by Valencia, Palma… to sell their goods) Under such circumstances, we can ideally develop networks of strong and weak ties between cities based on their location, thus further influencing their economic conditions. We can gain a basic insight into how graph theory and game are interdependent and perfectly combined in analyzing real-world situations from the above analysis.
With the intuition to dive more into such a beautiful combination, I searched for related primary sources and found how in history these two concepts developed respectively and finally converged to each other. In Tom Siegfried’s book A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature, Chapter 7-8 (Page 139-147), I went into the history of these two great theories in history and envisioned their convergence. Among Nash’s early achievements, game theory was briefly popular among some mathematicians and Cold War analysts. But it remained obscure until the 1970s when evolutionary biologists began applying it to their work. In the 1980s economists began to adopt game theory. Since then it has found an ever expanding repertoire of applications among a wide range of scientific disciplines. Nash won 1994 Nobel Economics Prize for contributing greatly to this theory and later application in many aspects.
In the process of applying game theory into greater scope, a man named Kevin Bacon (not Francis Bacon) brought these two concepts together. It was also Bacon’s effort that paved the way for the renaissance of graph theory, turning it from a obscure, unorganized hypothesis into a systematic theory. Kevin Bacon’s ubiquity in film caught attention of active students who launched research project of how Bacon was linked to other actor. And out of those 770,269 in the database, 770,187 (almost 99.99 percent) are linked to Bacon in six steps or fewer—nearly all, in other words, are less than six degrees of separation from Bacon. This finding not only further consolidated the “six degrees of separation” by Stanley Milgram in the 1960s but also linked games, societal situations, and graph theory together. It provided the insight that real-life situations, the rise of civilization, and the evolution of culture and society are much more complicated than penalty kicks (mixed strategies) we have discussed in class. Bacon made statistical analysis return to society.
All in all, we can see how greatly graph theory and game theory combines, and how Bacon linked these obscured concepts together to make them converge.
Source:
[1]: Networks, Crowds, and Markets: Reasoning about a Highly Connected World; David Easley, Jon Kleinberg: PP 11-13, , June 10, 2010
[2]:A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature, Chapter 7-8, Tom Siegfried :PP 139-147, July 2006