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
- expert at logic
- defending / attacking networks
- conflicts on multiple battlefields
- 2 PHDs
Dr. Thomasz Michalak
Game theory & Networks
Centrality in graphs
- Network :
- social networks
- biological network
Question : which node is important ?
How is importance measured ?
- which one connects components, etc…
- number of connections : nb of links of a given node
- closeness centrality :
- shortest path
- eigenvector centrality
- 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 ?
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”
- 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
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
Leave a comment