[2015 Spring, Complex System Seminar] Game theory

Definition of “Game Theory”

  • “… the study of mathematical models of conflict and cooperation between intelligent rational decison-makers.”([1])
  • originated as sub-fields of microeconomics and applied mathematics

Definition of “Game”

  • “In the language of game theory, a game refers to any social situation involving two or more individuals. The individuals involved in a game may be called the players.”([1])
  • Assumption on players
  • rational: A player is called as being rational, if he/she makes decisions consistently in pursuit of his own objectives(, which is maximization of his utility frequently).
  • intelligent: A player is called as being intelligent, if he/she knows everything that we know about the game and he can make any inferences about the situation that we can make.

Applications of Game Theory

  • Industrial organization (and their behaviors): analyzing cooperations(e.g. cartel) and competitions between firms
  • Auction theory: in terms of auctioneer and auction participants. e.g. Google auction, Yahoo auction, Soderby`s, ebay and so on.
  • Contract theory: Employer vs. Employee / Consumer vs. Producer
  • Evolutionary biology
  • Political science: international relationship, political parties
  • Public policy: Tragedy of commons, welfare policy design

List of Games

Why Do People Cooperate?

1. Kinship selection

  • When the sacrificing behavior of an agent can contribute to the spreading of its genes more than the cost for itself, it would choose to do. ([2], [3])

2. Indirect reciprocity

  • If each player decides whether to help someone or not based on the recipient’s image accumulated through previous altruistic behaviors, altruistic behavior becomes dominant. ([4])

3. Direct reciprocity

  • Repeated PD game
  • Tit-For-Tat: Select the previous strategy of your partner ([5])
  • win-stay, lose-shift: If your previous strategy was dominant toward the one of your partner, keep it. Otherwise, change it. ([6])

4. Costly signaling([7])

  • Group members have a personal characteristic, which we will call quality, that can either be high or low.
  • Each individual has occasion to enter into a profitable alliance (e.g. mating or political coalition) with any one of the other group members.

5. Altruistic punishment ([8])

  • If individuals can punish free riders in their group, although the punishment is costly and yields no material gain to the punisher, the cooperation flourishes.

6. Evolution of Social Network ([9])

– If cooperator pay the required cost, all his neighbors in a network would get benefit.
– In every turn, one randomly chosen player become dead.
– The tendency of new player for that position is decided depending on the sum of accumulated benefits of all neighbors.

7. Static Network ([10])

– If a social network is static, cooperative strategy becomes more stable.
– “We find that people cooperate at high stable levels, as long as the benefits created by cooperation are larger than the number of neighbors in the network.”


[1] Myerson, Roger B. Game theory. Harvard university press, 2013.
[2] http://en.wikipedia.org/wiki/Kin_selection
[3] Hamilton, William D. “The genetical evolution of social behaviour. II.” Journal of theoretical biology 7.1 (1964): 17-52.
[4] Nowak, Martin A., and Karl Sigmund. “Evolution of indirect reciprocity by image scoring.” Nature 393.6685 (1998): 573-577.
[5] Axelrod, Robert, and William D. Hamilton. “The evolution of cooperation.” Science 211.4489 (1981): 1390-1396.
[6] Nowak, Martin, and Karl Sigmund. “A strategy of win-stay, lose-shift that outperforms tit-for-tat in the Prisoner’s Dilemma game.” Nature 364.6432 (1993): 56-58.
[7] Gintis, Herbert, Eric Alden Smith, and Samuel Bowles. “Costly signaling and cooperation.” Journal of theoretical biology 213.1 (2001): 103-119.
[8] Fehr, Ernst, and Simon Gächter. “Altruistic punishment in humans.” Nature 415.6868 (2002): 137-140.
[9] Ohtsuki, Hisashi, et al. “A simple rule for the evolution of cooperation on graphs and social networks.” Nature 441.7092 (2006): 502-505.
[10] Rand, David G., et al. “Static network structure can stabilize human cooperation.” Proceedings of the National Academy of Sciences 111.48 (2014): 17093-17098.

[2015 Spring, Complex System Seminar] Game theory

[2015 Spring, Complex System Seminar] Go Viral!

Social Influence

1. Experimental Study of Inequality and Unpredictability in an Artificial Cultural Market ([1])

  • Method
    • Authors created an artificial music market and recruited 14,341 participants (mostly teenagers) and provide them unknown musics from unknown bands. After listening the songs they chose, they are asked to rate the quality of the songs and to decide whether to download or not.
    • Participants are assigned into two groups randomly.
    • Independent: Only names of the bands and their songs are provided as an information.
    • Social Influence: Not only above information, but also download counts of each song by others are known. This social influence group is separated into 8 subgroups, in which each subgroup is evolved independently each other.
    • This experiment are operated two times, which are different in the visualizing way of download counts.
    • In experiment 1, the download counts of 48 songs are shown in 16*3 grid, in a random order.
    • In experiment 2, the counts are shown in one column in a descending order.
  • Result
    • Gini coefficient of Exp. 2 > Gini coefficient of Exp. 1 > Gini coefficient of Independent Group
    • Unpredictability of Exp. 2 > Unpredictability of Exp. 1 > Unpredictability of Independent Group (Unpredictability: avg. difference in market share of a song in 8 different worlds)
    • Market share in Exp 1. looks linearly correlated with market share in Independent group, while that in Exp 2. looks exponentially correlated with that in Independent group.
  • Personal opinion
    • If it traces the dynamic processes to become top-ranked for some most popular songs, it would be also interesting. (Finding phase transition moments and conditions.)

2. Complex Contagions and the Weakness of Long Ties ([2])

  • Related works
    • Two different meanings of tie strength according to Granovetter
    • relational: strong tie means close friend, family, while weak tie means an acqaintance.
    • structural: strong tie means having higher ability to facilitate diffusion, cohesion, and integration of its social network by linking others.
    • Granovetter’s insight is that a weak tie in relation can be a strong tie in structure by doing a job as shortcuts in small-world network.
    • Threshold model in contagion process (by Granovetter and Schelling)
    • Mechanisms of Complex Contagion
    1. Strategic complementarity: When the (social or economic) cost for adoptation decreases as the number of adopted people around increases.
    2. Credibility: Some innovations (or information) become reliable enough to adopt when my credible neighbors already adopted them.
    3. Legitimacy: The number of close friends who participated matters to recognize the event or social movement legitimate.
    4. Emotional Contagion

3. A 61-million-person experiment in social influence and political mobilization ([3])

  • Question: Can political behaviour spread through an online social network?
  • Effect of message to encourage voting

    • Dividing all Facebook users over 18 years in the US into 3 groups: social message group, informational message group, and control group
    • Social message group (N = 60,055,176) vs. Informational message group (N = 611,044): Different in whether show the profile pictures of 6 friends in a message.
    • Not only using self-reported voting (“I Voted” in the message), they also used the examination of public voting records.
  • Effect of strong ties

    • Validating that Facebook friends with more interactions are likely to be closer friends.
    • Then, based on this interaction counts, they compared the effect on voting behavior measured in 3 different ways, depending on the closeness.
    • Followings are their explanation.
    • “Figure 2 shows that the observed per-friend treatment effects increase as tie-strength increases. All of the observed treatment effects fall outside the null distribution for expressed vote (Fig. 2b), suggesting that they are significantly different from chance outcomes. For validated vote (Fig. 2c), the observed treatment effect is near zero for weak ties, but it spikes upwards and falls outside the null distribution for the top two deciles. This suggests that strong ties are important for the spread of real-world voting behaviour. Finally, the treatment effect for polling place search gradually increases (Fig. 2d), with several of the effects falling outside the 95% confidence interval of the null distribution.”
    • However, if you see the graph, the mean changes in probability to vote look same and only the variances become larger as the amount of interaction is bigger. (It might be because the number of close friends are much smaller than that of just frieds?)

4. Structural diversity in social contagion ([4])


  • Contagion of joining Facebook through friends’ invitation e-mails
  • Data: corpus of 54 million invitation e-mails
  • Question: “How does an individual’s probability of accepting an invitation depend on the structure of his or her contact neighborhood?”
  • Result: Acceptance probability is related to the number of connected components in the contact neighborhood (existing users who have an e-mail account of a user in common). That is, more components, higher probability to accept

[1] – M.J. Salganik et al., Experimental Study of Inequality and Unpredictability in an Artificial Cultural Market, Science 311, 854 (2006).
[2] – D. Centola and M. Macy, Complex Contagions and the Weakness of Long Ties, AJS 113, 702 (2007).
[3] – R.M. Bond et al., A 61-million-person experiment in social influence and political mobilization, Nature 489, 295 (2012).
[4] – Ugander, Johan, et al. “Structural diversity in social contagion.” Proceedings of the National Academy of Sciences (2012): 201116502.

[2015 Spring, Complex System Seminar] Go Viral!

Useful Links about Large-Scale Network Analysis

MapReduce and Hadoop


Useful Links about Large-Scale Network Analysis

[2015 Spring, Complex System Seminar] Creativity and Innovation in Scaling of Cities

Brief Review

Basically, the exponential relationship between the object’s size and the amount of its interactions or interaction results is addressed from biology, known as allometric scaling problem (1, 2). After some explanatory models for this allometric scaling phenomena (2, 3), social science researchers have tried to apply these biological characteristics into urbanization process and its result(4, 5, 6, 7).

The scaling results show that different urban features which are not related to each other have also exponential scalings with the size of city over various cities worldwide. In particular, the scaling exponents of urban features, which represent the levels of linearity, are shown to be different depending on the characteristics of the features. For example, quantities related to material infrastructure, such as the number of gas station, the length of electrical cables are characterized as sublinear(exponent value is smaller than 1.), while those about related to social currenice, sucah as information, innovation or wealth are characterized as superlinear(exponent value is bigger than 1.)(6).

To explain the process that this urban scaling result is emerged, Luís M. A. Bettencourt constructed a model assuming four characteristics of urban behavior: mixing population, incremental growth of infrastructure network, bounded human effort, proportional socio-economic output to local interactions(7).


The Linearity of Residuals

As shown in Fig. 1, the amount of residuals also has a relationship with the size of crimes (thus, also with the size of cities). That means, the data may have a problem of [heteroscedacity]. According to Wikipedia,

“(…) regression analysis using heteroscedastic data will still provide an unbiased estimate for the relationship between the predictor variable and the outcome, but standard errors and therefore inferences obtained from data analysis are suspect. Biased standard errors lead to biased inference, so results of hypothesis tests are possibly wrong.” (8)

If it is true, can we say more than “Bigger the city is, more the crimes are.”? Furthermore, what should we care when we apply existing regression methods on log-scaled values?

Overemphasis on Population

Assume that there are some set of quantities named A, B, and C. If A has a linear relationship with B, and B has a linear relationship with C, B is highly likely to have a linear relationship with C either. In this situation, the three linear relationships between A, B, and C themselves cannot explain any underlying causalities among them.

By the way, as far as I understand, some explanations in urban scaling implictly claim that the city size – generally measured by its population – is the main factor to cause the quantitative differences. For example, Luis Bettencourt mentioned that

“On average, as city size increases, per capita socio-economic quantities such as wages, GDP, number of patents produced and number of educational and research institutions all increase by approximately 15% more than the expected linear growth.”(5)

However, does it sound also natural that higher average wages of a specific city makes people to move into the city so the city gets bigger? Similarly, we can say that higher level of educational, informational environments or higher profits of companies made the city bigger by gravitating people nearby to move in. Furthermore, the multiple positive feedbacks between combinations of various urban features result in the growth of city.


1 – West, Geoffrey B., James H. Brown, and Brian J. Enquist. “A general model for the origin of allometric scaling laws in biology.” Science 276.5309 (1997): 122-126.

2 – West, Geoffrey B., James H. Brown, and Brian J. Enquist. “The fourth dimension of life: fractal geometry and allometric scaling of organisms.” science 284.5420 (1999): 1677-1679.

3 – West, Geoffrey B., James H. Brown, and Brian J. Enquist. “A general model for the structure and allometry of plant vascular systems.” Nature 400.6745 (1999): 664-667.

4 – Batty, Michael. “The size, scale, and shape of cities.” science 319.5864 (2008): 769-771.

5 – Bettencourt, Luis, and Geoffrey West. “A unified theory of urban living.” Nature 467.7318 (2010): 912-913.

6 – Bettencourt, Luís MA, et al. “Growth, innovation, scaling, and the pace of life in cities.” Proceedings of the national academy of sciences 104.17 (2007): 7301-7306.

7 – Bettencourt, Luís MA. “The origins of scaling in cities.” science 340.6139 (2013): 1438-1441.

8 – “Heteroscedasticity”, Wikipedia.org

[2015 Spring, Complex System Seminar] Creativity and Innovation in Scaling of Cities