Information Technology Reference
In-Depth Information
physical graph
1.2
1.8
0.5
1
2
3
4
5
6
0.6
0.4
2.2
Fig. 5.2
Example of SO-PCG. The number beside a user is its cost. Using best response dynamics,
we have
u
6
=
2
−
2
.
2
<
0
ₒ
a
6
=
0
ₒ
u
3
=
0
−
0
.
5
<
0
ₒ
a
3
=
0
ₒ
N
1
={
1, 2, 4, 5
}
, which
is a SNE. It is also Pareto-superior to the other two SNEs:
N
1
={
4, 5
}
and
N
1
=
∅
, and hence is
the best SNE
5.3
Benchmark: Socially-Oblivious Pseudonym Change Game
As the benchmark, we start with a basic case of the PCG: the PCG for socially-
oblivious users (SO-PCG), i.e.,
s
ij
S
. In this case, each user is selfish
and the social group utility degenerates to the individual utility.
For SO-PCG, there can exist multiple SNEs
3
with different values of social welfare
(as illustrated in Fig.
5.2
). For system efficiency, it is desirable to achieve the “best”
SNE, which is the SNE that achieves the maximum social welfare among all SNEs. To
find this SNE, we can use best response dynamics as follows: with all users' actions
initially set to 1, each user asynchronously updates its action as its best response
action based on other users' actions (no two users update at the same time). We
illustrate how it works by an example in Fig.
5.2
. We use
e
ij
=
0,
∀
∈
N
to
denote the set of participating users. The next result formally states that best response
dynamics can find the best SNE.
Proposition 5.1
For SO-PCG, best response dynamics can converge to a SNE that
achieves the maximum social welfare among all SNEs.
The proof is given in Appendix. As the best SNE achieves the maximum system
efficiency among all SNEs, we will use the best SNE for SO-PCG as a benchmark
for the general case of the PCG: the PCG for socially-aware users (SA-PCG).
N
1
(
a
)
{
i
∈
N
|
a
i
=
1
}
5.4
Existence of SNE
We first establish the existence of SNE. Using (
5.1
) and (
5.2
), we have
f
i
(1,
a
−
i
)
−
f
i
(0,
a
−
i
)
3
For SO-PCG, an SNE is equivalent to a NE for a standard non-cooperative game. For consistency
of terminology, we still call it “SNE” in this case.
