21.10.2003 Olli Niinivaara presentation:
GRAPHS AND COOPERATION IN GAMES
Roger B. Myerson
Mathematics of Operations Research, 2, 3, (1977), 225-229. Seminal paper:
1: The idea: Augment cooperative games with cooperation
structures represented as graphs
2: Notation
3: the Myerson value
Myerson's place:
Game-theoretic games
|
Cooperative games
|
Network games
|
Communication games
|
MYERSON'S FRAMEWORK
|
Coalitional games
(Jackson 2003)
Our example game we will mostly use (referred as eGame): N = {1, 2, 3}
v({1}) = v({2}) = v({3}) = 0
v({1,3}) = 6
v({2,3}) = 6
v({1,2}) = 12
v({1,2,3}) = 12
GR's (=all 8 g's) Myerson values for the game:
{empty set}  {1:2}      {1:3}      {2:3}
1          1          1          1
/            \
2  3      2  3      2  3      2---3
(0,0,0)    (6,6,0)    (3,0,3)    (0,3,3)
{1:2,1:3}  {1:2,2:3}  {1:3,2:3} {1:2,1:3,2:3}
1          1          1          1
/ \        /            \        / \
2  3      2---3      2---3      2---3
(7,4,1)    (4,7,1)    (3,3,6)    (5,5,2)
2. NOTATION
N = set of players
S = subset of S
link = an unordered pair of distinct members of N
n:m = m:n = link between n and m
g = graph on N = set of links
(1) Complete graph of all links:
gN = {n:m|n in N, m in M, n not m}
Note, that |gN| = |N|(|N|-1)/2
(2) The set of all graphs on N:
GR = {g|g belongs to gN}
Note, that |GR|N|| = 2^(|N|(|N|-1)/2),
making it one of the fastest growing phenomena one
will ever meet, for example |GR64| = 2^2016
(3) Given g in GR and S in N, a unique partition of S which groups players together iff they are connected in S by g:
S/g = {{i|i and j are connected in S by g}|j in S} Example:
N = {1,2,3,4,5}
g={1:2, 1:4, 2:4, 3:4}
{1,2,3}/g = {{1,2},{3}}
N/g = {{1,2,3,4},{5}}
3. ALLOCATION RULE
Let v be a game in characteristic form. That is, v is a function which maps each coalition S to a real number
v(S). Now we can describe the outcome of v depending on the cooperation structure by a function Y:
Y: GR -> (R1, R2, ... R|N|), where Ri is a real number.
(4) Efficiency:
for all g in GR, all S in N/g, sum  Yn(g) = v(S)
n in S
Example with eGame:
Y1(empty set) = v({1}) = 0
Y1({1:2}) + Y2({1:2}) = v({1,2}) = 12
Y3({1:2}) = v({3}) = 0
// definition (5), Stableness, deliberately omitted (6) Fairness (equal bargaining power):
for all g in GR, and for all n:m in g:cooperative
Yn(g)-Yn(g\n:m) = Ym(g) - Ym(g\n:m)
Example with eGame:
Y1({1:2,2:3}) - Y1({2:3}) = Y2({1:2,2:3}) - Y2({2:3})
Y2({1:2,2:3}) - Y2({1:2}) = Y3({1:2,2:3}) - Y3({1:2})
4. THE MYERSON VALUE
(7) Given a characteristic function game v and graph g,
v augmented with g:
for all S in N, (v/g)(S) =  Sum  v(T)
T in S/g
Examples with eGame:
(v/{1:3})({1,3}) = v({1,3}) = 6
(v/{1:2,2:3})({1,2,3}) = v({1,2,3}) = 12
THEOREM Given a characteristic function game v, there is
a *unique* allocation rule satisfying (4):Efficiency and
(6):Fairness. This allocation rule also satisfies:
Y(g)=Shapley(v/g), for all g in GR,
where Shapley() is the Shapley value operator.
Note, that v/gN = v => Y(gN) = Shapley(v). That is,
"the ordinary Shapley".
Examples with eGame:
Y1({1:3}) = 0 + 0 + 1/6*(6-0) + 1/3*(6-0) = 1+2 = 3
Y2({1:2,2:3}) = 0 + 1/6*(12-0) + 1/6*(6-0) + 1/3*(12-0)
= 2 + 1 + 4 = 7
Y1({1:2,1:3,2:3}) = Shapley1(v) = 5
Y2({1:2,1:3,2:3}) = Shapley2(v) = 5
Y3({1:2,1:3,2:3}) = Shapley3(v) = 2
Note, that Core of eGame is (6,6,0) but the Shapley value is (5,5,2). Myerson (value) gives one explanation:
"If both players 1 and 2 were to simultaneosly break
their links with 3, then both would benefit; but each would benefit even more if he continued to cooperate with player 3 while the other alone broke his link to
player 3."
5. DISCUSSION
Critique:
- No distinction between indirect and direct links
- No link costs or benefits
- Only bilateral links, vs. unilateral and multilateral
- Insensitive to alternative networks
- Fairness may become unfairness
(Solution: Step from communication games to network games, with value functions, etc.)
After all:
"The Myerson value is by far the most widely used
allocation rule for communication situations in the literature".
(van den Nouweland 2003)
Recommended reading:
An interview with Roger Myerson on Nash and Game Theory.
<home.uchicago.edu/~rmyerson/research/peraptis.pdf> References:
(Jackson 2003) Jackson, M., Allocation Rules for Network Games, 2003.
<www.hss.caltech.edu/~jacksonm/allonet.pdf>
(van den Nouweland 2003) van den Nouweland, A., Models of network formation in cooperative games, 2003.
<www.uoregon.edu/~annev/research/DWBook/
fulltext.pdf>

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。