Information Technology Reference
In-Depth Information
physical graph
social graph
1.
5
1.5
0.8
1
2
1
2
0.8
Fig. 5.3
Using best response dynamics, we have
f
1
(1, 1)
−
f
1
(0, 1)
=
1
−
1
.
5
+
0
.
8
>
0,
f
2
(1, 1)
−
f
2
(1, 0)
=
1
−
1
.
5
+
0
.
8
>
0, and hence
N
1
={
1, 2
}
is a SNE. However, it is not Pareto-optimal,
since it is Pareto inferior to
N
1
=
∅
as
u
1
(0, 0)
=
u
2
(0, 0)
=
0
>
1
−
1
.
5
=
u
1
(1, 1)
=
u
2
(1, 1).
Furthermore, its social welfare is less than that of
N
1
=
∅
as
v
(1, 1)
=−
1
<
0
=
v
(0, 0), where
N
1
= ∅
is also a SNE for SO-PCG
Observe that problem (
5.5
) is an integer quadratic programming, which is difficult to
solve in general
4
. Since the PCG for fully altruistic users is a special case of SA-PCG,
it is also difficult to compute the best SNE for SA-PCG. Based on this observation,
our objective below is to efficiently compute a SNE with desirable system efficiency.
To compute a SNE of SA-PCG, a naive approach is to use best response dynamics
in a similar way as with SO-PCG: with all users' actions initially set to 1, each user
asynchronously updates its action as its best response action based on other users'
actions. Due to Property 5.1, a user who changes its strategy from 1 to 0 will never
change it back to 1, and thus the best response dynamics always converges to a SNE.
However, it has drawbacks as illustrated by an example in Fig.
5.3
: the SNE may
not be Pareto-optimal and its social welfare may be worse than that of a SNE for
SO-PCG. Thus motivated, our objective below is to efficiently find a SNE such that
(1) it is Pareto-optimal and (2) its social welfare is no less than that of the best SNE
for SO-PCG, which is the benchmark.
5.5.1
Algorithm Design
To this end, we design an algorithm as described in Algorithm 2. The main idea
of the algorithm is to greedily determine users' strategies, depending on the social
group utility derived from
the users whose strategies have been determined
(referred
as “determined users”), denoted by
f
i
(
a
i
,
a
−
i
)
u
i
(
a
i
,
a
−
i
)
+
s
ij
u
j
(
a
i
,
a
−
i
)
S
i
j
∈
N
+
\
N
N
where
denotes the set of users whose strategies have not been determined (referred
as “undetermined users”). An undetermined user's action is fixed once it becomes
determined.
Specifically, the algorithm proceeds in rounds and each round consists of phase
I and phase II. In phase I, with all undetermined users' actions initially set to 1, an
4
We conjecture that problem (
5.5
) is an NP-hard problem.
