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