homework

Graphs Jan 14, 2016 • Götz Pfeiffer

Graphs and Social Networks Definitions and Basic Properties Definition. A (simple) graph is a pair , consisting of a (finite) set of objects, called nodes or vertices or points, and a subset of links or edges. Here, is the set of all -element subsets of . (The notation is motivated by the fact that if has elements then has elements.) Example. and (where is short for ).

A B

C

D

The example also illustrates a typical way how diagrams of graphs are drawn: nodes are represented by small circles, and edges by lines connecting the nodes. In this simple setting, two nodes are either connected or not (that is, there are no multiple links) and if node is connected to node , then it is also true that is connected to : the edges set up a symmetric relationship between nodes. If we want to express more complex real world relationships, we can make use of the more complex structure of directed graphs, where edges have directions (drawn as arrows), possibly pointing back to the node they came from (forming loops), or even with multiple edges between the same two nodes.

CS423: Networks Welcome Assignments

G = (X,E) X

E ⊆ ( ) X 2

( ) X 2

2 X

X n ( ) X 2 ( ) = n(n−1)

n 2

1 2

X = {A,B,C,D} E = {AB,BC,BD,CD} AB {A,B}

x y y x

Graphs are Relations Recall the following definitions. Definition. A relation from a set to a set is (nothing but) a subset of the Cartesian product . We say that is -related to whenever . If , we say that is a relation on . Such a relation can have one or more of the following properties.

• (R) is reflexive if for all ; • (S) is symmetric if implies for all ; • (T) is transitive if and imply that for all

; • (I) is irreflexive if for all ; • (A) is antisymmetric if and imply that for all

. A relation that is (RST, i.e., reflexive, symmetric and transitive) is called an equivalence relation, and it partitions the set into (mutually disjoint) parts, called equivalence classes. A relation that is (RAT) is called a partial order (such as the divides partial order on the natural numbers, or the contains relation between the subsets of a set). In view of these notions, we can now describe simple graphs and some as follows: A simple graph with node set is a symmetric, irreflexive relation on . A directed graph with node set is irreflexive if it has no loops. And it is antisymmetric if every edge has a unique direction. The article Counting Transitive Relations (in the Journal of Integer Sequences) contains a systematic account on the various types of relations that can be distinguished by these 5 properties, and a discussion of how to count them (up to equivalence) in case the underlying set is finite.

Example. The internet in December 1970. Nodes are computers, connected by a link if they can directly communicate with each other. At the time, only 13 computers participated in that network.

X Y R X×Y = {(x,y) : x ∈ X, y ∈ Y} x ∈ X R

y ∈ Y (x,y) ∈ R

Y = X X X

R (x,x) ∈ R x ∈ X R (x,y) ∈ R (y,x) ∈ R x,y ∈ X R (x,y) ∈ R (y,z) ∈ R (x,z) ∈ R

x,y,z ∈ X

R (x,x) ∉ R x ∈ X R (x,y) ∈ R (y,x) ∈ R x = y

x,y ∈ X

X

X X X

X

A graph can serve as a mathematical model of a network.

The following diagram contains the same information, without the distracting details of the US geography.

UCSB

SRI

UCLASTAN

UTAH

RAND

SDC

MIT

BBN

LINC

HARV

CARNFundamental Concepts: Paths and Connectivity A path in a graph is a sequence of nodes, linked by an edge if adjacent in the sequence. Example: MIT-BBN-RAN-UCLA is a path in the graph above. Such a graph can have repeated nodes. If it doesn’t, the path is called a simple path. The length of a path is the number of edges it involves (that is the number of

nodes, minus 1). At each vertex , there is a unique path of length zero, consisting only of that vertex . A cycle is a path of length at least 3 that is simple, except for the first and last nodes being the same. Example: SRI-STAN-UCLA-UCSB-SRI is a cycle in the graph above. Note that each edge (and node) of the 1970 Internet graph belongs to a cycle. This provides the other way around the cycle as an alternative route in case one of the edges should fail. Cycles in social networks are often a source of amusement, when discovered … Connectivity. A graph is connected if, for every pair of nodes, there is a path between them. (Communication and transportation networks tend to be connected, as this is their main purpose: to connect.) Components. If a graph is not connected, it naturally breaks into pieces, its connected components. The relation ‘there is a path from to on the node set of a graph is the transitive closure of the graph relation ‘there is an edge between and ’. It is reflexive (as each node is connected to itself by the zero length path starting and ending at ), symmetric (as a path from to can be used backwards as a path from to ), and transitive (as a path from to and a path from to together make up a path from to ), hence an equivalence relation. The connected components of the graph are the parts (equivalence classes) of the corresponding partition of . The Giant Component. Large, complex networks often have one giant component that contains a significant proportion of the nodes. Erdős and Rényi (1960) have found this to be almost certainly the case with a random graph on vertices with

edges.

x x

x y X x y

x x x y

y x x y y z x z

X

n n 2

CS423: Networks [email protected]

cs423 Network Science is the study of network representations of physical, biological, and social phenomena.

Example.

0 Comments CS423 Login 1 Share ⤤ Sort by Best

Start the discussion…

Be the first to comment.

Subscribe ✉ Add Disqus to your site Add Disqus Add d Privacy 🔒

Recommend 

CS423: Networks

Small Worlds and Triadic Closure Jan 21, 2016 • Götz Pfeiffer

Graph Theory and Social Networks Small Worlds Some social networks have become very accessible for systematic investigations, as they manifest themselves in a digital form on the internet. One such example of a social network that is accessible online is maintained by the American Mathematical Society (AMS) as part of MathSciNet, a database of mathematical research publications. This network is formed by a collaboration graph: its nodes are the mathematical researchers, and two researchers are connected by and edge whenever they have jointly authored a publication in the database. In this network, the Erdős number of a mathematician is their distance from the Erdős node. This number can be computed by Breadth First Search. The AMS offers this as a service on a dedicated collaboration diastance page. The hungarian mathematician Paul Erdős (1913-1996) is very well-known for his publication records, with more than 1500 publications, and more than 500 collaborators. It turns out, that most mathematicians have Erdős number of 4 or 5. In fact, experiments show that virtually all mathematicians are connected with each other in this network (in a big giant component), and that any two of them are rarely further than distance 6 apart. This is an instance of a phenomenon that has often been observed: social networks tend to have very short paths between arbitrary pairs of people. Such a network is called a small world network. In popular culture, the phenomenon is know as “six degrees of separation”. It goes at least back to experiments conducted in the 1960s by the Yale psychologist Stanley Milgram (who is better known for another experiment designed by him).

CS423: Networks Welcome Assignments

In a similar way, the co-star graph (with actors as nodes, and edges between two actors whenever they starred in a common film) as maintained by the IMDb, has been used to define the Bacon number of an actor as their distance to the American actor Kevin Bacon. The presence of short paths certainly has some relevance in relation to the potential speed of information (or diseases) travelling through the network.

Triadic Closure Networks evolve over time, edges come and go. Triadic closure is concerned with the presence of triangles in a network: if node A is connected to nodes B and C, is B connected to C? A set of nodes in a graph with the property that any two distinct nodes are joined by an edge is called a clique (in other words, a clique is a subset of the nodes such that the induced subgraph is complete). The graph below contains two cliques of four nodes each.

A clique of nodes has edges, e.g., a clique of nodes has edges. m ( ) = (m−1)

m 2

m 2

4

= 64⋅3 2

The clustering coefficient of a node A measures, how close the set of friends of comes to being a clique: if the induced subgraph on has edges, then the clustering coefficient of the node is defined as the fraction . This is a number between and . Triadic closure increases the clustering coefficient. In a social network, there are incentives for triadic closure to happen. If person A is friends with B and C, this provides opportunities for B and C to meet and become friends. On the other hand, B not being friends with C can be a source of stress for A, who has to attend to their friends separately. More generally, a lower clustering coefficient can mean that more work is required to maintain a circle of friends.

Bridges; local Bridges An edge AB is called a bridge if deleting the edge would cause A and B to lie in different connected components. (In other words, if the edge AB is a bridge then it is the only route from A to B). This notion might not be very useful for the study of social networks, as cycles and short paths make bridges very rare, or computationally expensive to detect. More interesting that the global notion of a bridge, is the local notion of a local brigde. An edge AB is a local bridge if , i.e., if and B$ have no friends in common. Deleting a local bridge AB increases the distance between A and B to at least 3. A local bridge is the conceptual opposite of triadic closure: an edge AB is a local bridge if and only it is not involved in any triangle. (Proof?)

F(A) A F(A) f

A f/( ) m 2

0 1

F(A)∩F(B) = ∅ A

CS423: Networks [email protected]

cs423 Network Science is the study of network representations of physical, biological, and social phenomena.

0 Comments CS423 Login 1 Share ⤤ Sort by Best

Start the discussion…

Be the first to comment.

Subscribe ✉ Add Disqus to your site Add Disqus Add d Privacy 🔒

Recommend 

CS423: Networks

Strong vs Weak Ties Jan 27, 2016 • Götz Pfeiffer

Graph Theory and Social Networks Strong and Weak Ties In many examples it is possible to distinguish between different levels of strength of the links of a network. Here, we are going to study networks with (only) two types of edges: strong ties (corresponding to close friends, say), and weak ties (corresponding to acquaintances). The assumption that triadic closure is more likely to happen in the presence of strong links can be formalized as the following Strong Triadic Closure Property.

Example. In the graph below, the strong edges have a label ( ) and the weak edges don’t. Each node of this graph satisfies the Strong Triadic Closure Property: whenever a node has two strongly tied neighbours, there is a tie (weak or strong) between those neighbours.

CS423: Networks Welcome Assignments

A node violates the Strong Triadic Closure Property if it has strong ties with two other nodes and , and there is no edge at all between and . A node satisfies the Strong Triadic Closure Property if it does not violate it.

A B C B C

A

s

Triadic closure establishes a connection between the local notion of link strength and the structural notion of local brigdes, as follows. Proposition. If a node in a network satisfies the Strong Triadic Closure Property and is involved in at least two strong ties, then any local bridge it is involved in must be a weak tie. In other words, assuming that all nodes in a network satisfy the Strong Triadic Closure Property and have sufficiently many strong ties, local bridges are necessarily weak ties. Proof. Suppose that node does satisfy the Strong Triadic Closure Property and is involved in at least two strong ties. For a contradiction, suppose the edge is a local bridge and a strong tie. As is a local bridge, nodes and have no friends in common. Let be another strong tie involving . Then the Strong Triadic Closure Property requires the existence of an edge , making a common friend of and , contradiction. Simplyfying assumptions (like the Strong Triadic Closure Property) are useful when they lead to statements that are robust in practice, in the sense that qualitative

A

A AB

AB A B AC A

BC C A B

conclusions still hold in approximate forms, even when the assumptions are slightly relaxed. The surprising strength of weak ties (as experienced in the case of information leading to a new job or other new opportunities typically coming from distant acquaintances) can be partially explained in this framework. Links connecting people to new sources of information tend to be local bridges of a certain “span”, which by the above are necessarily weak ties. The Stanford sociologist Mark Granovetter has pioneered the theoretical study of social networks along such lines in the 1970s. Today, digital communication networks allow for empirical verifications of theoretical predictions. The Twitter network, for example, has its users as nodes, and one can use its social network features to distinguish strong and weak ties. A weak tie corresponds to one user following another. A strong tie corresponds to at least two messages directly addressed at another user user. An empirical study of the social network with its strong and weak ties defined in this way, shows that people have vastly different numbers of followees (between none and more than 1000), and the number of strong ties tends to increase with the number of followees. However, as soon as the nuber of followees reaches 400, the number of strong ties seems to stabilize at around 50. It requires little effort to “follow” a large number of Twitter users. But it requires time and energy to maintain a strong tie relationship, and there are only so many hours in a day …

0 Comments CS423 Login 1 Share ⤤ Sort by Best

Start the discussion…

Be the first to comment.

Subscribe ✉ Add Disqus to your site Add Disqus Add d Privacy 🔒

Recommend 

CS423: Networks [email protected]

cs423 Network Science is the study of network representations of physical, biological, and social phenomena.

CS423: Networks

Graph Partitioning Jan 28, 2016 • Götz Pfeiffer

Graph Theory and Social Networks The Girvan-Newman Partitioning Algorithm

See the pdf slides

CS423: Networks Welcome Assignments

CS423: Networks [email protected]

cs423 Network Science is the study of network representations of physical, biological, and social phenomena.

1 Comment CS423 Login 1 Share ⤤ Sort by Best

Join the discussion…

• Reply •

Student • 11 days ago When calculating the betweenness values of edges in a graph, the book says to construct a breadth-first structure for each edge and then to 'sum up the flow values to get the betweenness values for each edge'. So, for instance, suppose there was a graph with 5 vertices. To find the betweenness value of an edge between node A and B, having done the 3-step procedure for each node, would it be correct to take the flow value on the edge between A and B (regardless of whether node A is above node B in the structure, or B is above A), for each of the 5 breadth-first structures (one for each node), add these up, and divide by 2? △ ▽

Subscribe ✉ Add Disqus to your site Add Disqus Add d Privacy 🔒

Recommend 

Share ›

CS423: Networks

Contexts Feb 3, 2016 • Götz Pfeiffer

Graph Theory and Social Networks When networks are used to model real life relationships, simplifying assumptions are made, leaving out aspects of the context in which for example a social network is embedded. Here we discuss such contextual aspects and how they might be taken care of.

Homophily Homophily (“love of the same”) is the tendency of individuals to associate and bond with similar ones. It has been observed to govern the structure of social networks. […]

Affiliation Networks An affiliation network allows us to add context to a network, by maintaining two distinct set of nodes, and , and links only connecting nodes in with nodes in

. Such a network is called a bipartite graph. Here, we use the set to represent people, and to represent foci, i.e., common interests, workplaces, etc. […]

Segregation The Schelling model: Suppose that people live on a grid, and that there are two types and . An interactive implementation of the Schelling model. Spatial Segregation happens even if no agent is actively seeking it.

CS423: Networks Welcome Assignments

X Y X Y X

Y

X O

CS423: Networks [email protected]

cs423 Network Science is the study of network representations of physical, biological, and social phenomena.

0 Comments CS423 Login 1 Share ⤤ Sort by Best

Start the discussion…

Be the first to comment.

Subscribe ✉ Add Disqus to your site Add Disqus Add d Privacy 🔒

Recommend 

CS423: Networks

Positive and Negative Links Feb 4, 2016 • Götz Pfeiffer

Graph Theory and Social Networks Usually, links represent friendly relationships. Here we discuss networks with edges labelled by and , where stands for friendly relationship, and for antagonism.

Structural Balance This is an example of a local condition that has an effect on the global structure of a network. Suppose that the network in question is a complete graph, with edges labelled or , and study triadic closure under these conditions. The triangles in this network have one of four possible types:

• All three edges are labelled : the nodes form a set of mutual friends, a constellation that can be considered stable.

• One edge labelled and two edges labelled : the nodes represent two friends with a common enemy, another constellation that is considered stable.

• Two edges labelled and one edge labelled : here one node has two friends that don’t like each other, an unstable constellation as there are incentives to either resolve the conflict and all be friends with each other, or to side with one friend against the other.

• All edges labelled : a set of mutual enemies is considered unstable, as again there is an incentive for two nodes to team up against the third.

On the basis of this classification, one can formulate the following Structural Balance Property.

CS423: Networks Welcome Assignments

+ − + −

+ −

+

+ −

+ −

−

An example of a network that is balanced in this sense is one where the node set consists of two parts, and , say, such that all nodes within are mutual friends, all nodes within are mutual friends, and there is mutual antagonism between the two sets. In fact, these are the only examples of balanced graphs.

Proof. Pick a node . Every other node will be either a friend or an enemy of . Let be and all its friends, and let be all of ’s enemies. Then clearly forms a partition of the node set. It remains to show that

• any two nodes in are friends (which they are as either one of the nodes is and the other is ’s friend by the definition of , or the two nodes are friends of , making them friends by structural balance),

• any tow nodes in are friends (which they are, both having as their enemy by the definition of and hence being friends by structural balance),

• every node in is an enemy of every node in (which they are, as the node in is either , and thus an enemy of every node in by the definition of , or the node in is a friend and the node in an enemy of , making them enemies as structural balance requires the third edge of a triangle with at least one positive and one negative edge to be negative.

Applications. In international relations it is often natural to assume that all nodes (nations, in this case) have an opinion ( or ) about one another. Structural balance can (sometimes) provide an explanation for the bahaviour of nations during international crises.

The edges between any 3 nodes are either all labelled , or exactly one is labelled .

+ +

X Y X Y

Balance Theorem (Harary 1953). If a labelled complete graph is balanced then the nodes can be divided into two groups, and (possibly empty), such that all links within , and within , are labelled , and all links between a node in and a node in are .

X Y X Y +

X Y −

A A X A Y A X,Y

X A A X

A

Y A Y

X Y X A Y Y

X Y A

+ −

Weaker Forms of Structural Balance The notion of structural balance is somewhat extreme, and in applications might not be present in its pure form. There are several ways to soften the requirements on structural balance. In a complete graph, for example, one might require only a certain proportion of the triangles to be balanced. Alternatively, one can relax the condition that every possible edge must be present, and study structural balance in non-complete networks. Here, we briefly study the following Weak Structural Balance Property on a complete graph:

The techniques of the proof of Harary’s Balance Theorem can be adjusted to characterize weakly balanced networks as follows.

No three nodes have exactly two negative edges between them (and one positive edge).

Weak Balance Theorem. If a complete labelled graph is weakly balanced, then then the nodes can be partitioned into groups , so that any two nodes within a group are friends, and any two nodes from different groups are enemies.

, ,…,X1 X2 Xk

CS423: Networks [email protected]

cs423 Network Science is the study of network representations of physical, biological, and social phenomena.

0 Comments CS423 Login 1 Share ⤤ Sort by Best

Start the discussion…

Be the first to comment.

Subscribe ✉ Add Disqus to your site Add Disqus Add d Privacy 🔒

Recommend 

CS423: Networks

Games Feb 10, 2016 • Götz Pfeiffer

Game Theory So far, we have been discussing the structure of interconnecting links. Now we are going to look at the interdependence in behavior of agents.

What is a game? Games, in this context are situations where the outcome of a person’s decisions depend also on choices made by people they interact with. This includes, for example, the question of how to defend against a penalty kick in a soccer match, the pricing of a new product in a competitive market, how to bid at an auction, or how to choose a route through a transportation network. Games have also been applied as models in evolutionary biology. A game needs the following ingredients. 1. Players (these are the decision makers) 2. Action (strategies, one set of options for each player) 3. Payoffs (to be maximised)

On this basis, one has the following formal definition. Definition. A finite -person normal form game is a triple , where

• is a (finite) set of players, • , and , for , is the finite set of actions for

player (we call an action profile), • is a profile of utility functions, and is the

utility function (payoff) for player .

CS423: Networks Welcome Assignments

n (N,A,u)

N = 1,2,…,n n

A = × ×⋯×A1 A2 An Ai i ∈ N i a = ( , ,…, ) ∈ Aa1 a2 an

u = ( , ,…, )u1 u2 un :A → ℝui i

For , there is a standard matrix representation of a -player game by a matrix whose

• rows correspond to the actions , • columns correspond to the actions , • cells contain the payoffs and .

Example. 2 students have both an exam and a joint presentation on the next day. Each student only has time to prepare for one, the exam, or the joint presentation. The outcomes can be predicted as follows. On the exam, each student will score 92% if prepared, and 80% if not. For the presentation, they will score 100% if both prepare for it, 92% if only one prepares for it, and 84% if none prepares for it. On average then, if both prepare for the presentation (and not for the exam), they both score . If both prepare for the exam (and not for the presentation), they both score . And if student 1 prepares the presentation, and student 2 studies for the exam, then, on average, student 1 will score and student 2 will score . Similar if student 1 studies for the exam and student 2 prepares the presentation. These outcomes (payoffs) can be summarized in a matrix, where the rows correspond to student 1’s options (P: prepare presentation, E: prepare for the exam), and the columns correspond to student 2’s options:

The game will now be analyzed under the following assumptions. • The utility functions include everything the players care about (so that, e.g.,

their partner’s score would be accounted for if they did care), • complete information: the payoff matrix is known to all players, • rationality: each player aims at maximizing their payoff, and they know how to

find an optimal strategy. Example (cont’d). If player 2 plays P, then player 1 maximises their payoff by playing E (as ). If player 2 plays E, then player 1 maximises their payoff again by playing E (as ). So regardless of what action player 2 is choosing, player 1 will yield a higher payoff if they choose option E. For the same reason, option E is preferrable for player 2.

n = 2 2

∈a1 A1 ∈a2 A2

( , )u1 a1 a2 ( , )u2 a1 a2

(100+80) = 901 2

(92+84) = 881 2

(92+80) = 861 2

(92+92) = 921 2

P

E

P

90,90

92,86

E

86,92

88,88

92 > 90 88 > 86

So both players most likely will opt for E, yielding a payoff of 88, despite the fact that there is an action profile (both opting for P) that would yield a higher payoff for both of them. This game is an example of a suitation, which in game theory is kown as the Prisoner’s Dilemma. Prisoner’s Dilemma. A prisoner’s dilemma is a -player game, where each player has two options, C and D, with payoffs as in the matrix

where . Concepts. In a game , for , it will be convenient to write for

, the product of all sets but , and for .

An action is a best response to if for all , and it is a strict best response to

if for all . An action is a [strictly] dominant strategy for player , if it is a [strict] best response to each . In a Prisoner’s Dilemma, each player has a strictly dominant strategy. A rational agent will always play a dominant strategy, if they have one. Even if only one player in a -player game has a dominant strategy, it is still possible to analyze the game, as in the following example. Example. There are two companies, C1 and C2, planning to introduce a new product into a market that is cleanly divided into a low-price segment and an upscale segment. Each company has two options, as to whether their product will be low-priced ( ) or upscale ( ). The sales are predicted on the basis of the follwing two assumptions.

• The low-priced segment accounts for 60% of the population, the upscale segment for the other 40%.

• Company 1, being the more popular of the two will attract 80% of the sales in case of direct competition, leaving only 20% to company 2.

This leads to the following payoff matrix (with rows corresponding to the options for company 1, and columns to company 2):

2

C

D

C

a,a

c,b

D

b,c

d,d

c > a > d > b

(N,A,u) i ∈ N A−i ×⋯× × ×…A1 Ai−1 Ai+1 An Aj Ai a−i

( ,…, , ,…, )a1 ai−1 ai+1 an

∈ai Ai ∈a−i A−i ( , ) ≥ ( , )ui ai a−i ui a

′ i a−i ∈a

′ i

Ai ∈a−i A−i ( , ) > ( , )ui ai a−i ui a

′ i a−i ≠a

′ i

ai

∈ai Ai i ∈ N ∈a−i A−i

2

L U

CS423: Networks [email protected]

cs423 Network Science is the study of network representations of physical, biological, and social phenomena.

Here, strategy is a strictly dominant strategy for company 1, which they will play as a rational agent. Consequently, company 2 will play strategy , as it is more profitable for them in this case.

0 Comments CS423 Login 1 Share ⤤ Sort by Best

Start the discussion…

Be the first to comment.

Subscribe ✉ Add Disqus to your site Add Disqus Add d Privacy 🔒

Recommend 

CS423: Networks

L

U

L

48,12

40,60

U

60,40

32,8 L

U

Nash Equilibrium Feb 11, 2016 • Götz Pfeiffer

Game Theory A Game of Three Clients There are games where no player has a dominant strategy. Example. Two companies want to make business with one of three clients , , or , under the following conditions.

• If the two companies approach the same client, this client will give half of its business to each of them.

• Company 1 is too small to do business on their own, if they approach a different client than company 2, their payoff will be 0.

• is a large client and will only do the business if both companies approach them, where as and are prepared to deal with company 2 alone.

• ’s big business has a value of 8, while and have business worth 2. All of this results in the following payoff matrix (with rows corresponding to the options for company 1, and columns to company 2).

In this game, neither company has a dominant strategy. In fact, each strategy is a strict best response to some strategy of the other company.

CS423: Networks Welcome Assignments

A B C

A B C

A B C

A

B

C

A

4,4

0,0

0,0

B

0,2

1,1

0,2

C

0,2

0,2

1,1

The Nash Equilibrium The following simple idea allows us to reason about games that have no dominant strategy. Definition (Equilibrium). An action profile is a Nash Equilibrium if, for each player , their action is a best response to . The idea here is that an action profile which is not an equilibrium provides an incentive for at least one player to move to a different strategy. In the preceding example, is an equilibrium, as for both players, strategy is a best response to the opponent playing . In fact it is the only equilibrium in that game. The profile is not an equilibrium as player 2’s best response to player 1 playing is , and not . Assuming that non-equilibrium strategies will not by played by rational agents, in the example both players will play , the unique equilibrium of this game.

Multiple Equilibria: Coordination Games The analysis of a game can be difficult if it has multiple equilibria. This typically happens with situations that require the players to coordinite. Example. Two students need to prepare a presentation for the next day. Unfortunately, they forgot to agree on the software to use, and for now cannot communicate. The options are either PowerPoint or BeamerLaTeX. The presentation will be good if both students use the same software in their preparation (payoff 1) and it will be bad if different systems are usd (payoff 0). This yields a payoff matrix of the following shape.

This game obviously has two equilibria, and , which cannot be distinguished from each other. Interestingly, the same payoff matrix can be used to model the question: Which side of the road should to oncoming cars use to pass each other safely? This question is usually answered by social conventions, conventions that everyone agrees with, but whcih could be different from country to country.

a = ( ,…, ) ∈ Aa1 an i ∈ N ai a−i

(A,A) A A

(B,B) B C B

A

P

B

P

1,1

0,0

B

0,0

1,1

(P,P) (B,B)

Variants of the coordination game are not that symmetric. Example. If both students generally prefer BeamerLaTeX for their presentations, and yield better results, the payoff for both choosing this software might be 2 for both. This results in an unbalanced payoff matrix.

Again, this game has two equilibria, but the higher payoff for the is not captured by the equilibrium concept. Example (Battle of the Sexes). A different lack of symmtry is displayed by a game, which in the literature is called the ‘Battle of the Sexes’. This game describes a situation where, for example, a couple want to go to the cinema, and they need to agree on which film to watch, considering that he would rather see and action movie, and she usually prefers a romantic drama … Assuming a payoff of 0 for not seeing the same film, a payoff of 2 for watching the preferred movie, and a payoff of 1 for watching what the partner prefers, one gets a payoff matrix as follows (with rows corresponding to her options and columns corresponding to his):

No Equilibrium: Attack-Defense Games At the other end of the spectrum, there are games that have no equilibrium at all. This typically happens if the player’s interests are in direct conflict. For example, if one player is an attacker and has a choice of two different attacking strategies, or , and the other player can choose defend against either or . The defender wins if they choose the same (matching) strategy as the attacker. Otherwise, in case of a mismatch the attacker attack successfully and wins. Example (Matching Pennies). Here, the two player have a penny each, and both choose theirs to either show heads or tails. Both pennies are revealed at the same time and if they show different sides, player 1 (the attacker) wins and gets to keep both pennies. If they match player 2 (the defender) wins and gets to keep both

P

B

P

1,1

0,0

B

0,0

2,2

(B,B)

A

R

A

1,2

0,0

R

0,0

2,1

A B A B

pennies. In terms of a payoff matrix this looks as follows (with rows corresponding to player 1, and columns to player 2):

This (zero sum) game clearly has no domonant strategies, and no equilibrium. In reality, the players of such a game would make it difficult to guess their strategies by choosing randomly. Suppose that player 2 chooses with a certain probability (and hence

with probability ). The payoffs for player 1 are then determined as follows. If player 1 chooses , they will get a payoff of with probability , and a payoff of with probability . In total, this yields a payoff of

, depending on the parameter chosen by player 2. Similarly, if player 1 chooses they will receive a payoff of

. If one of and was strictly bigger than the other, the rational player 1 would have a strict preference for exactly one of their options. However, player 2’s intention was it to choose the parameter so that player 1 becomes indifferent between the available options. The best bet for player 2 thus is to choose so that the two payoff values for player 1 become the same:

, that is . For similar reasons, the optimal strategy for player 1 is to choose wit probability

. Then in the strategy profile , the choices, by player 1 anr by player 2, are again best responses to each other, and the profile forms an equilibrium of mixed strategies, to be discussed next.

H

T

H

−1,+1

+1,−1

T

+1,−1

−1,+1

H q ∈ [0,1] T 1−q

H −1 q 1 (1−q)

(−1)q+(1)(1−q) = 1−2q q T

(1)q+(−1)(1−q) = 2q−1

1−2q 2q−1

q

q

1−2q = 2q−1 q = 1 2

H

p = 1 2

(p,q) p q

CS423: Networks [email protected]

cs423 Network Science is the study of network representations of physical, biological, and social phenomena.

0 Comments CS423 Login 1 Share ⤤ Sort by Best

Start the discussion…

Be the first to comment.

Subscribe ✉ Add Disqus to your site Add Disqus Add d Privacy 🔒

Recommend 

CS423: Networks

Mixed Strategies Feb 17, 2016 • Götz Pfeiffer

Game Theory Mixing We now allow randomization in the choice of strategies. In addition to pure strategies , this introduces mixed strategies. A mixed strategy for player is a probability distribution over the action set

, that is, a function , such that . In games with mixed strategies, the finite action sets are replaced by the infinite sets of strategies . A collection is called a strategy profile. For each player , there is an expected utility , defined as

where

We still say that, for player , strategy is a best response to the strategy profile of the other players, if for all . And we say that a profile is a Nash equilibrium if, for each

, strategy is a best response to . With mixed strategies the following award-winning result holds.

CS423: Networks Welcome Assignments

∈ai Ai

i ∈ N Ai : → [0,1]si Ai ( ) = 1∑ ∈ai Ai si ai

Ai = : → [0,1]Si si Ai

s = ( ,…, ) ∈ S = ×⋯×s1 sn S1 Sn

i ∈ N :S → ℝui (s) = (a)Pr(a|s),ui ∑

a∈A

ui

Pr(a|s) = ( ).∏ j∈N

sj aj

i ∈ N si s−i ( , ) ≥ ( , )ui si s−i ui s

′ i s−i ∈s

′ i

Si

s = ( ,…, ) ∈ Ss1 sn i ∈ N si s−i

Theorem (Nash 1950). Every finite game has a Nash equilibrium.

Computing Equilibria. A game may have both pure-strategy and mixed-strategy equilibria. In order to find all equilibria, one should therefore

• first check all the pure outcomes to see which, if any, form an equilibrium, • then look for profiles of mixed strategies, i.e., probability distributions over the

action sets, which are mutual best responses. In a -player, -strategy game this means to first check the cells of the payoff matrix, and then to look for mixing probabilities and that make the corresponding mixed strategies best responses to each other. These probabilities can be computed under the assumption that players will choose them in such a way that their opponent’s expected outcomes are the same for their two options. This gives one equation per player, to be solved for and . If both values thus obtained lie strictly between and , they determine a mixed-strategy equilibrium. Example (Battle of the Sexes.) In this game, with payoff matrix

we have already identified two pure-strategy equilibria: and . Suppose now that player 1 (the row player) uses a mixed stratey, where she chooses with probabilty (and with probability ). Then the expected payoff for player 2 is if he chooses , and if he chooses . So player 1 will pick so that , i.e., . Similarly, suppose that player 2 chooses with probability (and with probability ). Then the expected payoff for player 1 is if she chooses , and if she chooses . Player 2 will thus pick with

, that is .

Global Optimality. As we have seen, rational agents, acting in their own interest, can produce outcomes which are less than optimal on a global scale, as exemplified by the Prisoner’s Dilemma.

2 2 4 2×2 p q

p q 0 1

A

R

A

1,2

0,0

R

0,0

2,1

(A,A) (R,R)

A p R 1−p 2p+0(1−p) A 0p+1(1−p)

R p 2p = 1−p p = 1 3

A q R 1−q 1q+0(1−q) A 0q+2(1−q) R q

2 = 2−q q = 2 3

Several concepts for measuring what’s “good for society”, from a neutral or global perspective, have been suggested. Here, we briefly mention ‘Pareto optimality’ and ‘Social Optimality’. Both concepts apply to the exam-or-presentation game, we have studied before, with payoff matrix:

Pareto Optimality. A strategy profile is Pareto-optimal, if there is no other strategy profile , where all players receive playoffs at least as high, that is

for all , and at least one player receives a strictly higher payoff, that is for (at least) one . Pareto optimality is named after the Italian economist Vilfredo Pareto (1848-1923). If players choose a strategy profile that is not Pareto optimal, then there exists an alternative strategy profile, where at least one player is better off, and no player fares worse. However, if this alternative is not an equilibrium, at least one player would then want to switch to a different strategy, and thus present a risk to any agreement, the players might have to choose a Pareto optimum. The strategy in the exam-or-presentation example is not Pareto-optimal, whereas is. In the absence of a binding agreement, each individual player will prefer to switch to the ‘exam’ strategy. Note that the strategies and

are also Pareto-optimal, as there is no alternative strategy profile that makes everybody’s payoff at least as good. In this example, and in the Prisoner’s Dilemma, the unique Nash equilibrium is the only outcome that is not Pareto- optimal! Social optimality is an even stronger condition that is simpler to state. Social Optimality. A strategy profile is socially optimal (or a social welfare optimizer) if it maximizes , the sum of the players’ payoffs. Note that a socially optimal outcome is necessarily Pareto-optimal. In the exam-or-presentation game, strategy with a combined payoff of

is the unique social optimum. However, the combined payoffs of all the players might not always be a meaningful measure of a game’s outcome.

P

E

P

90,90

92,86

E

86,92

88,88

a ∈ A ∈ Aa′

( , ) ≥ ( , )ui a ′ i a′ −i

ui ai a−i i ∈ N

( , ) > ( , )ui a ′ i a′ −i

ui ai a−i i ∈ N

(E,E) (P,P)

(E,P) (P,E)

a ∈ A (a)∑i∈N ui

(P,P) 90+90 = 180

CS423: Networks [email protected]

cs423 Network Science is the study of network representations of physical, biological, and social phenomena.

0 Comments CS423 Login 1 Share ⤤ Sort by Best

Start the discussion…

Be the first to comment.

Subscribe ✉ Add Disqus to your site Add Disqus Add d Privacy 🔒

Recommend 

CS423: Networks

Evolutionary Game Theory Feb 18, 2016 • Götz Pfeiffer

Game Theory Evolutionary Strategies

Read chapter 7 of the book.

CS423: Networks Welcome Assignments

CS423: Networks [email protected]

cs423 Network Science is the study of network representations of physical, biological, and social phenomena.

0 Comments CS423 Login 1 Share ⤤ Sort by Best

Start the discussion…

Be the first to comment.

Subscribe ✉ Add Disqus to your site Add Disqus Add d Privacy 🔒

Recommend 

CS423: Networks