One may define a concept of an n-person game in which each player has a finite set of pure strategies and in which a definite set of payments to the n players corresponds to each n-tuple of pure strategies, one strategy being taken for each player. For mixed strategies, which are probability distributions over the pure strategies, the pay-off functions are the expectations of the players, thus becoming polylinear forms in the probabilities with which the various players play their various pure strategies.
Any n-tuple of strategies, one for each player, may be regarded as a point in the product space obtained by multiplying the n strategy spaces of the players. One such n-tuple counters another if the strategy of each player in the countering n-tuple yields the highest obtainable expectation for its player against the n − 1 strategies of the other players in the countered n-tuple. A self-countering n-tuple is called an equilibrium point.
The correspondence of each n-tuple with its set of countering n-tuples gives a one-to-many mapping of the product space into itself. From the definition of countering we see that the set of countering points of a point is convex. By using the continuity of the pay-off functions we see that the graph of the mapping is closed. The closedness is equivalent to saying: if P1, P2, … and Q1, Q2, …, Qn, … are sequences of points in the product space where Qn → Q, Pn → P and Qn counters Pn then Q counters P.
Since the graph is closed and since the image of each point under the mapping is convex, we infer from Kakutani’s theorem1 that the mapping has a fixed point (i.e., point contained in its image). Hence there is an equilibrium point.
In the two-person zero-sum case the “main theorem”2 and the existence of an equilibrium point are equivalent. In this case any two equilibrium points lead to the same expectations for the players, but this need not occur in general.
Communicated by S. Lefschetz, November 16, 1949
During decades the study of networks has been divided between the efforts of social scientists and natural scientists, two groups of scholars who often do not see eye to eye. In this review I present an effort to mutually translate the work conducted by scholars from both of these academic fronts hoping to continue to unify what has become a diverging body of literature. I argue that social and natural scientists fail to see eye to eye because they have diverging academic goals. Social scientists focus on explaining how context specific social and economic mechanisms drive the structure of networks and on how networks shape social and economic outcomes. By contrast, natural scientists focus primarily on modeling network characteristics that are independent of context, since their focus is to identify universal characteristics of systems instead of context specific mechanisms. In the following pages I discuss the differences between both of these literatures by summarizing the parallel theories advanced to explain link formation and the applications used by scholars in each field to justify their approach to network science. I conclude by providing an outlook on how these literatures can be further unified.
Highlights, Quotes, Annotations, & Marginalia
Social scientists focus on explaining how context specific social and economic mechanisms drive the structure of networks and on how networks shape social and economic outcomes. By contrast, natural scientists focus primarily on modeling network characteristics that are independent of context, since their focus is to identify universal characteristics of systems instead of context specific mechanisms. ❧
August 25, 2018 at 10:18PM
Science and Complexity (Weaver 1948); explained the three eras that according to him defined the history of science. These were the era of simplicity, disorganized complexity, and organized complexity. In the eyes of Weaver what separated these three eras was the development of mathematical tools allowing scholars to describe systems of increasing complexity. ❧
August 25, 2018 at 10:19PM
Problems of disorganized complexity are problems that can be described using averages and distributions, and that do not depend on the identity of the elements involved in a system, or their precise patterns of interactions. A classic example of a problem of disorganized complexity is the statistical mechanics of Ludwig Boltzmann, James-Clerk Maxwell, and Willard Gibbs, which focuses on the properties of gases. ❧
August 25, 2018 at 10:20PM
Soon after Weaver’s paper, biologists like Francois Jacob (Jacob and Monod 1961), (Jacob et al. 1963) and Stuart Kaufmann (Kauffman 1969), developed the idea of regulatory networks. Mathematicians like Paul Erdos and Alfred Renyi, advanced graph theory (Erdős and Rényi 1960) while Benoit Mandelbrot worked on Fractals (Mandelbrot and Van Ness 1968), (Mandelbrot 1982). Economists like Thomas Schelling (Schelling 1960) and Wasily Leontief (Leontief 1936), (Leontief 1936), respectively explored self-organization and input-output networks. Sociologists, like Harrison White (Lorrain and White 1971) and Mark Granovetter (Granovetter 1985), explored social networks, while psychologists like Stanley Milgram (Travers and Milgram 1969) explored the now famous small world problem. ❧
Some excellent references
August 25, 2018 at 10:24PM
First, I will focus in these larger groups because reviews that transcend the boundary between the social and natural sciences are rare, but I believe them to be valuable. One such review is Borgatti et al. (2009), which compares the network science of natural and social sciences arriving at a similar conclusion to the one I arrived. ❧
August 25, 2018 at 10:27PM
Links are the essence of networks. So I will start this review by comparing the mechanisms used by natural and social scientists to explain link formation. ❧
August 25, 2018 at 10:32PM
When connecting the people that acted in the same movie, natural scientists do not differentiate between people in leading or supporting roles. ❧
But they should because it’s not often the case that these are relevant unless they are represented by the same agent or agency.
August 25, 2018 at 10:51PM
For instance, in the study of mobile phone networks, the frequency and length of interactions has often been used as measures of link weight (Onnela et al. 2007), (Hidalgo and Rodriguez-Sickert 1008), (Miritello et al. 2011). ❧
And they probably shouldn’t because typically different levels of people are making these decisions. Studio brass and producers typically have more to say about the lead roles and don’t care as much about the smaller ones which are overseen by casting directors or sometimes the producers. The only person who has oversight of all of them is the director, and even then they may quit caring at some point.
August 25, 2018 at 10:52PM
Social scientists explain link formation through two families of mechanisms; one that finds it roots in sociology and the other one in economics. The sociological approach assumes that link formation is connected to the characteristics of individuals and their context. Chief examples of the sociological approach include what I will call the big three sociological link-formation hypotheses. These are: shared social foci, triadic closure, and homophily. ❧
August 25, 2018 at 10:55PM
The social foci hypothesis predicts that links are more likely to form among individuals who, for example, are classmates, co-workers, or go to the same gym (they share a social foci). The triadic closure hypothesis predicts that links are more likely to form among individuals that share “friends” or acquaintances. Finally, the homophily hypothesis predicts that links are more likely to form among individuals who share social characteristics, such as tastes, cultural background, or physical appearance (Lazarsfeld and Merton 1954), (McPherson et al. 2001). ❧
definitions of social foci, triadic closure, and homophily within network science.
August 26, 2018 at 11:39AM
Yet, strategic games look for equilibrium in the formation and dissolution of ties in the context of the game theory advanced first by (Von Neumann et al. 2007), and later by (Nash 1950). ❧
August 25, 2018 at 10:58PM
Preferential attachment is the idea that connectivity begets connectivity. ❧
August 25, 2018 at 10:59PM
Preferential attachment is an idea advanced originally by the statisticians John Willis and Udny Yule in (Willis and Yule 1922), but has been rediscovered numerous times during the twentieth century. ❧
August 25, 2018 at 11:00PM
Rediscoveries of this idea in the twentieth century include the work of (Simon 1955) (who did cite Yule), (Merton 1968), (Price 1976) (who studied citation networks), and (Barabási and Albert 1999), who published the modern reference for this model, which is now widely known as the Barabasi-Albert model. ❧
August 25, 2018 at 11:01PM
preferential attachment. In the eyes of the social sciences, however, understanding which of all of these hypotheses drives the formation of the network is what one needs to explore. ❧
For example what drives attachment of political candidates?
August 26, 2018 at 08:15AM
Finally it is worth noting that trust, through the theory of social capital, has been connected with long-term economic growth—even though these results are based on regressions using extremely sparse datasets. ❧
And this is an example of how Trump is hurting the economy.
August 26, 2018 at 08:33AM
Nevertheless, the evidence suggests that social capital and social institutions are significant predictors of economic growth, after controlling for the effects of human capital and initial levels of income (Knack and Keefer 1997), (Knack 2002).4 So trust is a relevant dimension of social interactions that has been connected to individual dyads, network formation, labor markets, and even economic growth. ❧
August 26, 2018 at 08:35AM
Social scientist, on the other hand, have focused on what ties are more likely to bring in new information, which are primarily weak ties (Granovetter 1973), and on why weak ties bring new information (because they bridge structural holes (Burt 2001), (Burt 2005)). ❧
August 26, 2018 at 09:45AM
heterogeneous networks have been found to be effective promoters of the evolution of cooperation, since there are advantages to being a cooperator when you are a hub, and hubs tend to stabilize networks in equilibriums where levels of cooperation are high (Ohtsuki et al. 2006), (Pacheco et al. 2006), (Lieberman et al. 2005), (Santos and Pacheco 2005). ❧
August 26, 2018 at 09:49AM
These results, however, have also been challenged by human experiments finding no such effect (Gracia-Lázaro et al. 2012). The study of cooperation in networks has also been performed in dynamic settings, where individuals are allowed to cut ties (Wang et al. 2012), promoting cooperation, and are faced with different levels of knowledge about the reputation of peers in their network (Gallo and Yan 2015). Moreover, cooperating behavior has seen to spread when people change the networks where they participate in (Fowler and Christakis 2010). ❧
August 26, 2018 at 09:50AM
Representative Tom Rooney, a Florida Republican, talks about the Russia investigation, gun control and his decision not to run for re-election.
This gives me some interesting ideas about how things might be fixed via game theory. In some sense it may also help if we all (both parties) had a common enemy to fight against. During the Cold War it was Communism we fought against which helped us be on the same side, and as a result we were more united. Now with nothing to “fight against” we’re fighting each other.
This is one of the most interesting episodes of this podcast I’ve come across yet.Syndicated copies to:
What computers teach us about getting along. From an office at Carnegie Mellon, my colleague John Miller and I had evolved a computer program with a taste for genocide.
This article reminds me that I need to go back to reading Fukuyama’s two volume series (Origins of Political Order) and apply more math to it as a model. I can see some interesting evolution of political structures spread throughout the modern world and still want a more concrete answer for the jumps between them. I suspect that some of our world problems are between more advanced political economies and less advanced (more tribalistic ones — read Middle Eastern as well as some third world nations) which are working on different life-ways. Are there punctuated equilibrium between the political structures of economies like the graph in this paper? What becomes the tipping point that pushes one from one region to the next?
I also feel a bit like our current political climate has changed so significantly in the past 20 years that it’s possible we (America) may be regressing.
Check out this referenced paper:
🔖 Barasz, M., et al. Robust cooperation in the Prisoner’s Dilemma: Program equilibrium via provability logic. arXiv 1401.5577 (2014).
SFI and Arizona State University soon will offer the world’s first comprehensive online master’s degree in complexity science. It will be the Institute’s first graduate degree program, a vision that dates to SFI’s founding. “With technology, a growing recognition of the value of online education, widespread acceptance of complexity science, and in partnership with ASU, we are now able to offer the world a degree in the field we helped invent,” says SFI President David Krakauer, “and it will be taught by the very people who built it into a legitimate domain of scholarship.”
A Course in Game Theory presents the main ideas of game theory at a level suitable for graduate students and advanced undergraduates, emphasizing the theory's foundations and interpretations of its basic concepts. The authors provide precise definitions and full proofs of results, sacrificing generalities and limiting the scope of the material in order to do so. The text is organized in four parts: strategic games, extensive games with perfect information, extensive games with imperfect information, and coalitional games. It includes over 100 exercises.
Tangentially suggested after reading In Game Theory, No Clear Path to Equilibrium by Erica Klarreich (Quanta Magazine)
Free, personal copy is downloadable in .pdf format with registration here.
Syndicated copies to:
(.pdf download) Subjectivity and correlation, though formally related, are conceptually distinct and independent issues. We start by discussing subjectivity. A mixed strategy in a game involves the selection of a pure strategy by means of a random device. It has usually been assumed that the random device is a coin flip, the spin of a roulette wheel, or something similar; in brief, an ‘objective’ device, one for which everybody agrees on the numerical values of the probabilities involved. Rather oddly, in spite of the long history of the theory of subjective probability, nobody seems to have examined the consequences of basing mixed strategies on ‘subjective’ random devices, i.e. devices on the probabilities of whose outcomes people may disagree (such as horse races, elections, etc.).
Suggested by In Game Theory, No Clear Path to Equilibrium by Erica Klarreich (Quanta Magazine)Syndicated copies to:
For a constant ϵ, we prove a poly(N) lower bound on the (randomized) communication complexity of ϵ-Nash equilibrium in two-player NxN games. For n-player binary-action games we prove an exp(n) lower bound for the (randomized) communication complexity of (ϵ,ϵ)-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least (1−ϵ)-fraction of the players are ϵ-best replying.
Suggested by In Game Theory, No Clear Path to Equilibrium by Erica Klarreich (Quanta Magazine)Syndicated copies to:
John Nash’s notion of equilibrium is ubiquitous in economic theory, but a new study shows that it is often impossible to reach efficiently.
There’s a couple of interesting sounding papers in here that I want to dig up and read. There are some great results that sound like they are crying out for better generalization and classification. Perhaps some overlap with information theory and complexity?
To some extent I also find myself wondering about repeated play as a possible random walk versus larger “jumps” in potential game play and the effects this may have on the “evolution” of a solution by play instead of a simpler closed mathematical solution.Syndicated copies to:
John Baez, one of the organizers of the workshop, is also going through them and adding some interesting background and links on his Azimuth blog as well for those who are looking for additional details and depth
Additonal resources from the Workshop:
- NIMBios Workshop page
- Participants list
- Workshop Agenda [.pdf download]
- Information and Entropy WordPress site
- YouTube playlist of videos
- Storify archive from the workshop
If Leonard Riggio, Barnes & Noble's chairman, joins Liberty Media's proposed buyout of his company, the board needs to decide how to handle his 30 percent stake before shareholders vote on the deal.
This story from the New York Times’ Dealbook is a good quick read on some of the details and machinations of the Barnes & Noble buyout. Perhaps additional analysis on it from a game theoretical viewpoint would yield new insight?