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.
Search WWH ::




Custom Search