Graph theory

In the previous article, we explained the basic principles of game theoryand, through a few examples, discovered how it can be used to implement the most cost-effective strategy in a situation where the ultimate gain depends on the moves made by other players.

In this second article we will find out what graph theory is and how it can be integrated into game theory. In addition, we will introduce another type of Nash equilibrium, namely Nash equilibria for mixed strategies.

Graphs can be used to schematize situations or processes and allow their analysis in quantitative and algorithmic terms.

Technically, a graph (or network) G is a pair(V, E) where Vis a finite set whose elements are called vertices or nodes and E is a subset whose elements, called arcs or sides, are pairs of objects inV.

For example, in the following image we see a graph with vertices V={A,B,C,D} and arcs E={(A,B), (B,A), (B,D), (D,B), (D,C), (C,D), (B,C), (C,B)}.

Adigraphis a graph that possesses at least one oriented arc, that is, an arc characterized by one direction that cannot be traveled in the opposite direction.

For example, by modifying the previous graph as follows we obtain a digraph with arcs E={(B,A), (B,D), (D,B), (D,C), (C,D), (B,C), (C,B)}.

Let us now introduce some practical examples to understand how graphs can be used in game theory.

Consider a situation in which there are two players and the first player, A, chooses a number between 1,2 and 3. The second participant, B, adds to the said number 1,2 or 3. A will do the same in the next round and so on until one of them gets to exclaim 31 winning.

Such a game can be represented by the following digraph:

Vertices are the natural numbers from 1 to 31, and arcs starting from vertex n enter those n+1, n+2 and n+3 if 1 ≤ n ≤ 28. From 29 come out arcs entering into 30 and 31, from 30 into 31 and from 31 none.

So, the player who succeeds in saying 27 has won because the next player will only be able to select vertices 28, 29, or 30, and in each of these cases, the first one will succeed in placing on 31.

We can then set a goal of getting to 27 and not 31. But at this point who will say23 will succeed in winning, and, applying the reasoning iteratively, we conclude that the nodes to be touched to win are X = {3, 7, 11,15, 19, 23,27, 31}.

We observe that:

In conclusion, analyzing the graph, we find that the goal is to always occupy the positions of X.

Suppose we want to demonstrate against a given action of a dictatorial government. Such an event will be beneficial only if the number of demonstrators is sufficiently large; on the other hand, if this does not happen we would face a very negative payoff since we might assume that, in such a case, the state will quell the demonstration violently.

Suppose each person decides to participate in the protest only if he or she knows that at least enough citizens will join it.

Suppose we have 4 citizens and represent the fact that citizen w knows the behavior of citizen u and vice versa by the presence of the (w,u) side. The figure next to a node indicates the minimum number of total protesters for that node to join the enterprise.

Consider the following situations:

We note that in case A the revolt will not take place because each of the participants has no way of knowing the behavior that the node not connected to it will adopt.

In case B, on the other hand, each among u, v and w will know that there are at least two other nodes that require at least three total participants and that in turn have this information. So the protest will take place, specifically u, v and w will be the protesters.

There are games in which the Nash equilibria we introduced in the previous article are not present, namely those based onpure strategies. A pure strategy in fact provides a complete description of how an individual plays a game. In particular, it determines what choice the player will make in any situation he or she might face.

Amixed strategyfor a player is a probability distribution over the set of pure strategies available to him. Each pure strategy P can be viewed as a special case of a mixed strategy that assigns probabilities equal to 1 to P and equal to 0 to all other pure strategies.

Thus we have twotypes of Nash equilibria: those for pure strategies, analyzed so far, occur when all players have only pure strategies at their disposal, otherwise we speak of Nash equilibria for mixed strategies.

Limiting ourselves to a two-participant game, a Nash equilibrium for mixed strategies is a pair of choices (which are now probabilities) such that each is the best answer to the other.

Let us introduce an example

Consider a game in which there is an attacker A and a defender D

The attacker can choose between attack strategies a1or a2 while the defender can defend against a1, and then apply strategy d1, or conversely defend against a2, and then apply strategy d2.

Suppose:

We summarize the game situation in the following table by indicating in each box: to the left of the comma the gain obtained by A and to the right of the comma the gain obtained by D.

In our example a1 and a2 are the pure strategies available to the attacker, while defending from a1 and defending from a2 those of the defender.

Since the two players would get sharply contrasting gains we might conclude that in these kinds of games (called strictly competitive games) there are no Nash equilibria.

If either player knew the behavior of the other then he could choose the strategy likely to maximize his own profit and inevitably minimize that of his opponent. Each of the players will therefore try to make their strategy unpredictable.

Let p be the probability that A chooses a1 and q the probability that D chooses d1.So far we only know that there is at least one equilibrium for mixed strategies but not what the actual values of p and q should be.

We use the principle that a mixed equilibrium arises when the probabilities used by each player cause his opponent to have no reason to prefer one of the two available options over the other.

If we assume that D has a probability q of playing d1 then we have that the possible gains for A are:

(0)(q) + (10)(1 – q) = 10 – 10q if he chose a1;

(5)(q) + (0)(1 – q) = 5q if he chose a2.

To make it indifferent for A to choose between a1 and a2 we impose 10-10q = 5q from which q = 2/3.

Now suppose that A has a probability p of enacting a1. The possible gains for D then are:

(0)(p) + (-5)(1 – p) = 5p – 5 if he chose d1

(-10)(p) + (0)(1 – p) = -10p if he chose d2

By imposing5p – 5 = -10p we get p = 1/3.

Thus we have that the only possible probability values that can appear in the equilibrium for the mixed strategy are p = 1/3 for the attacker and q = 2/3 for the defender.

Note also that the expected gain of A in the case where he chooses a1and D chooses d1 is 10/3 and that of D is -10/3.

This suggests a counterintuitive analysis: the probability of A making the strongest attack is one-third, i.e., in a continuous model, we could imagine that only one-third of the time A tries to attack with a1.

The answer is that if A always tried to attack with a1 then D would be persuaded to respond often with d1, which would reduce the payoff expected by A. On the other hand, consider that since p = 1/3 causes D to choose one of the two strategies without preference, and we have that when A uses that probability value, then, regardless ofD’s choices, it is assured of a payoff of 10/3.

Suppose two firms, F1 and F2, are planning to set up store in one of six cities located along six consecutive exits on a road. We can represent the layout of these cities using a six-node graph like the one in the figure below [2].

Suppose F1 can open his store in A, C or E while F2 in B, D or F. Once the stores open, customers in the various cities will shop in the center closest to them. Assume that each city has the same number of customers and that the stores’ earnings are directly proportional to the number of customers attracted. We easily obtain the earnings table below.

It can be verified that none of the players has a dominant strategy: for example, if F1 chose location A then F2’s strictly better response would be B, while if F1 chose E F2’s strictly better response would be D. Despite this we note that A is a strictly dominant strategy for F1, in fact in every situation where F1 has the option of choosing A, it will receive a strictly better payoff by choosing C. Similarly, F is a strictly dominated strategy for F2. Thus, we have that F1 will not choose A and F2 will not choose F.

We can disregard nodes F and A at this point, and from this we derive the following payoff table:

B and E become the new strictly dominated strategies for F2 and F1, respectively, and thus can be eliminated in turn. We reach the conclusion that F1 will choose C and F2 D.

This way of proceeding is called iterative cancellation of strictly dominated strategies. We also note that the pair (C,D) constitutes the only Nash equilibrium of the game and in fact this study methodology is also useful in finding Nash equilibria. We generalize the process just presented below.

Given an arbitrary number of n players we have that iterative deletion of strictly dominated strategies proceeds as follows:

It can be shown that the set of Nash equilibria of the original version of the game coincides with that of the final version thus obtained.

Consider a problem in which two players A and B may opt for strategy a or b with the following symmetrical gains:

In this case a is a weakly dominated strategy since in each case each player can only improve his gain by choosing b. Also note that (b,b) is a Nash equilibrium.

When we have weakly dominated strategies, it is not advisable to proceed with the deletion method, as this may destroy balances.

On the other hand, it is intuitive to think that no player would choose to go along with the (a,a) equilibrium composed of weakly dominated strategies if he has no way of predicting the other player’s behavior: why not use the (b,b) strategy, which in the worst case scenario does not affect the gain anyway?

In this article, we have seen how graph theory can be used in game theory by going into solving games that have yielded counterintuitive results. In the next article, we will delve into networks by going to study more complex situations that will allow us to analyze the propagation of strategies within a network.

2] D. Easley and J. Kleinberg, Networks, Crowds, andMarkets: Reasoning about a Highly Connected World, Cambridge UniversityPress, 2010.

[3] R.Gibbons, Game Theory, Bologna, Il Mulino, 2005.

[4] E. Martìn Novo and A. Mendez Alonso, Aplicaciones de la teoría de grafos a algunos juegos de estrategia, Suma number 64, Universidad Politécnica de Madrid,2004.

[8] P.Serafini, Graph and Game Theory, a.y. 2014-15 (revised: Nov. 282014).

[9] I. S. Stievano and M. Biey, Cascading behavior in networks, DET, Politecnico di Torino,2015.

[10] I. S. Stievano and M. Biey, Interactions within a network, DET, Politecnico di Torino,2015.

[11] I. S. Stievano, M. Biey, and F. Corinto, Complex networks and systems, DET, Politecnico diTorino, 2015.

[12] A. Ziggioto and A. Piana, Model of Lotka-Volterra, found at http://www.itismajo.it/matematica/Lezioni/Vecchi%20Documenti%20a.s.%202011-12/Modello%20of%20Lotka-Volterra.pdf accessed 5/15/2015.

[15]http://web.econ.unito.it/vannoni/docs/thgiochi.pdf accessed 14/05/2015.