# Conférence Varsovie 1 : Game Theory

Oskar Skibski :

• Discrete math expert
• works with Makoto Yokoo
• expert at cooperative game theory

• Cooperaive Game theory
• Games on networks
• Analysis of voting power

Marcin Dziubinski

• expert at logic
• defending / attacking networks
• conflicts on multiple battlefields
• 2 PHDs

Dr. Thomasz Michalak

http://www.network-centrality.com

# Game theory & Networks

## Centrality in graphs

Network :

undirected graph

e.g :

• Neurons
• social networks
• biological network
• etc…

Question : which node is important ?

How is importance measured ?

• connectivity
• which one connects components, etc…
• number of connections : nb of links of a given node
• closeness centrality :
• betweenness centrality

• shortest path
• eigenvector centrality
• pagerank
• etc …

Try to use axiomatic approach to guess which node is the most central.

• from simple rules one can determine the most suited node.

Axioms of centrality :

1. centrality of a node depends only of the part of the graph it belongs to
2. normalization :
• at the center of a star ⟶ more important

Impact of a single edge : same impact on centrality for the nodes connected ?

No ⟶ if Obama and I are friends, it means more for me than for Obama.

Axiom 1 : adding an edge doesn’t decrease centrality of anyone.

⟶ degree is winning

Axiom 2 : adding an edge in a connected graph doesn’t change the sum of centralities.

⟶ attachment is winning

Where is game theory ?

Ex :

in a Parliament, each party has a given nb of seats.

For a party to win, it’s got to have a nb of votes > a given quota

A little party may have more power than two big ones confronting each other, because it can choose which one to collaborate with.

# Social Network Analysis of Terrorist Networks

What is cooperative game theory ?

You have a group of agents, who are to perform a task.

How to divide the pay of the grand coalition between all of the agents between the agents ?

• proportionally according to each contribution of each agent individually
• equally between the agents

Stability : how to divide this payoff so that nobody wants to go away ?

⟶ such a division is called “the core”

Ex :

• individual : 5
• two : 12
• three : 24

How to divide 24 ?

1. 13 7 4 ⟶ the third go away, or the second and the third
2. 10 7 7 ⟶ not fair for the second and the third

Shapley value : how do you measure the contribution of each agent to the game ?

Axiom 1 : the “null” should have a 0 payoff

Axiom 2 : symmetric payoff

Axiom 3 : you should exactly what you have ⟶ efficiency

Axiom 4 : the payoff should be additive for completely independent games.

Shapley value of a given agent :

for each permutation of agents, you compute the marginal contribution of this agent for the part before him, and then we take the average.

### Application for analysis of terrorist network

Game Theory :

Group centrality : we no longer consider single nodes (like in Graph Theory), but cliques.

## Colonel Blotto game : Conflicts on multiple battlefields

Ex :

shops on a line : how to attract customers ?

Simpler models : how to distribute resources ?

Conflicts on multiple battlefields :

• applications to warfare
• security games
• politics : campaigns
• catch criminals
Colonel Blotto game :

a competitive game : each player wants to win

• 2 players : $A$ and $B$
• $A$ is the strongest
• how to allocate their units across the battlefields ?

• 1 point for each battlefield where a player has more units
• 0 point where there’s a tie
• -1 where a player a less units

They can randomize allocations.

Exs : paper - scissors - rock : you can’t predict what the other will do

This is a

zero-sum game :

one wins ⟹ the other loses (the total score is zero).

What is the min score that the stronger player can secure (called “value of the game”).

For $a=b$, $n≥3$ (number of battlefields): it is necessary to randomize.

Symmetric strategy :

invariant under permutation of battlefields

Tags:

Updated: