Information Technology Reference
In-Depth Information
Algorithm2
ComputeaPareto-optimalSNEforSA-PCG
1:
N ₐ N
;
2:
repeat
3:
// Phase I
;
4:
a
ₐ
(
1
, ··· ,
1
)
,
N
I
ₐ N
;
5:
while
∃
i
∈ N
suchthat
u
i
(
1
,
a
−
i
)+
∑
j
∈N
S
i
+
\N
s
ij
a
j
<
0
do
6:
a
i
ₐ
0,
N
I
ₐ N
I
\{
i
}
;
7:
endwhile
8:
;
// Phase II
9:
N ₐ N \N
I
,
N
II
ₐ
∅
;
10:
while
∃
i
∈ N
suc
hth
at
u
i
(
1
,
a
−
i
)+
∑
j
∈N
S
i
+
\N
s
ij
a
j
≥
0
do
11:
a
i
ₐ
1,
N ₐ N \{
i
}
,
N
II
ₐ N
II
∪{
i
}
;
12:
endwhile
13:
until
N
I
∪N
II
=
∅
;
14:
return
a
e
ₐ
a
;
Fig. 5.4
Example to illustrate
how Algorithm 2 works: The
number next to a user is its
cost; the number beside a
social edge is its social tie
level
physical graph
1.2
0.6
2.5
1.2
1
2
3
4
5
6
7
8
0.8
1.5
0.8
2.2
social graph
0.5
0.8
0.6
1
2
3
4
0.2
0.3
0.3
0.8
5
6
7
8
0.6
0.5
0.2
undetermined user's action is changed from 1 to 0 if that improves its social group
utility derived from the determined users, i.e.,
f
i
(1,
a
−
i
)
f
i
(0,
a
−
i
)
−
=
u
i
(1,
a
−
i
)
+
s
ij
a
j
<
0
S
i
j
∈
N
+
\
N
until no such user exists. Then the undetermined users whose actions remain 1
become determined and their actions are fixed to 1. In phase II, with all undetermined
users' actions initially set to 0, an undetermined user becomes determined and its
action is fixed to 1 if that improves its social group utility derived from the determined
users, until no such user exists. The algorithm terminates when no undetermined user
becomes determined during either phase I or phase II of a round.
We use the example in Fig.
5.4
to illustrate how to compute a SNE using
Algorithm 2 and outline the steps as follows.
