Information Technology Reference
In-Depth Information
•
Phase I of 1st round:
u
1
=
1
−
1
.
2
<
0
ₒ
a
1
=
0;
u
5
=
1
−
1
.
5
<
0
ₒ
a
5
=
0;
u
4
=
0
−
1
.
2
<
0
ₒ
a
4
=
0
ₒ
u
3
=
2
−
2
.
5
<
0
ₒ
a
3
=
0;
u
7
=
2
−
2
.
2
<
0
ₒ
a
7
=
0
ₒ
u
8
=
0
−
0
.
8
<
0
ₒ
a
8
=
0;
u
2
=
1
−
0
.
6
>
0;
u
6
=
1
−
0
.
8
>
0;
N
I
={
2, 6
}
.
•
Phase II of 1st round:
u
5
+
s
56
=
1
−
1
.
5
+
0
.
6
>
0
ₒ
a
5
=
1
ₒ
u
1
+
s
12
=
1
−
1
.
2
+
0
.
5
>
0
ₒ
a
1
=
1;
u
3
+
s
32
=
1
−
2
.
5
+
0
.
8
<
0;
u
7
+
s
76
=
1
−
2
.
2
+
0
.
5
<
0;
u
4
=
0
−
1
.
2
<
0;
u
8
=
0
−
0
.
8
<
0;
N
II
={
1, 5
}
.
•
Phase I of 2nd round:
u
4
=
0
−
1
.
2
<
0
ₒ
a
4
=
0
ₒ
u
3
+
s
32
=
2
−
2
.
5
+
0
.
8
>
0;
u
7
+
s
76
=
2
−
2
.
2
+
0
.
5
>
0;
u
8
=
1
−
0
.
8
>
0;
N
I
={
3, 7, 8
}
.
•
Phase II of 2nd round:
u
4
+
s
43
+
s
48
=
0
−
1
.
2
+
0
.
6
+
0
.
8
>
0
ₒ
a
4
=
1;
N
II
={
4
}
.
Since the size of the set of undetermined users
is upper bounded by
n
, the com-
putational complexity of either phase I or phase II of a round is bounded by
O
(
n
2
).
Since at least one user is determined during a round, the algorithm must terminate
within
n
rounds. Therefore, the running time of the algorithm is bounded by
O
(
n
3
).
In Sect.
5.6
, numerical results will demonstrate that the computational complexity of
Algorithm 2 increases almost quadratically with the number of users. In Sect.
5.5.2
,
we will discuss a distributed version of Algorithm 2.
N
(
a
1
,
For SA-PCG, the strategy profile
a
e
=
···
,
a
n
)
computed by
Theorem 5.1
Algorithm 2 is a Pareto-optimal SNE.
The proof is given in Appendix. As the SNE computed by Algorithm 2 is Pareto-
optimal, it is desirable for system efficiency. Next we show that its social welfare is
no less than that of the best SNE for SO-PCG. To this end, we first show that the
Pareto-optimal SNE is monotonically “increasing” with respect to social tie levels.
For SA-PCG, when social tie levels increase (i.e., s
ij
Theorem 5.2
≥
s
ij
,
∀
i
,
j
∈
), the corresponding Pareto-optimal SNE
a
e
satisfies that
a
e
and v
(
a
e
)
N
≥
a
e
≥
v
(
a
e
)
.
The proof is given in Appendix. Intuitively, with stronger social ties to other users,
a user is more likely to participate in favor of its social group utility, even at the cost of
reducing its individual utility. Theorem
5.2
confirms this intuition: as social ties get
stronger, more users participate at the Pareto-optimal SNE. Furthermore, the social
welfare achieved at the Pareto-optimal SNE is also increasing.
When Algorithm 2 is used for SO-PCG, we can see that it works exactly the same
as the best response dynamics used to find the best SNE for SO-PCG, and therefore
they find the same profile. Based on this observation, using Theorem
5.2
,wehave
the following result.
Corollary 5.1
The social welfare of the Pareto-optimal SNE for SA-PCG is no less
than that of the best SNE for SO-PCG.
Corollary
5.1
guarantees that the social welfare of the Pareto-optimal SNE is
no less than the benchmark SNE for SO-PCG. In Sect.
5.6
, numerical results will
demonstrate that the Pareto-optimal SNE is efficient, with a performance gain up to
20 % over the benchmark.