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.networkcentrality.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 :
 centrality of a node depends only of the part of the graph it belongs to
 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 ?
 13 7 4 ⟶ the third go away, or the second and the third
 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
 zerosum 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
Leave a comment