Information Technology Reference
In-Depth Information
Appendix
For convenience, let
N
II
,
k
denote the set of users that become determined
in phase I and phase II of round
k
in Algorithm 2, respectively. Let
N
I
,
k
and
N
0
(
a
)
{
i
∈
N
|
a
i
=
0
}
denote the set of users with action 0 under profile
a
.
Proof of Proposition
5.1
Since SO-PCG is a special case of SA-PCG, Property 5.1 also applies to the individual
utility function
u
i
. Therefore, due to Property 5.1, a user who changes its strategy
from 1 to 0 will not change it back to 1. As a result, best response dynamics always
terminates and results in a profile
a
o
that is a SNE.
Next we show that
a
o
achieves the maximum social welfare among all SNEs. It
suffices to show that
a
o
is Pareto-superior to any other SNE. To this end, we first
show that a profile
a
is not a SNE if
N
1
(
a
)
\
N
1
(
a
o
)
. Suppose such
a
is a
=
∅
∈
N
1
(
a
)
\
N
1
(
a
o
) be the first user among
N
1
(
a
)
\
N
1
(
a
o
) whose action
SNE. Let
i
a
be the profile right before that change. Since
a
≤ ¯
¯
is changed to 0, and
a
,wehave
u
i
(0,
a
i
−
u
i
(
a
)
≤
¯
=
) due to that 0 is the best response strategy. This shows
that
a
is not a SNE. Therefore, for any SNE
a
other than
a
o
, we must have
a
<
a
o
.
Then for each
i
∈
N
1
(
a
), we have
u
i
(
a
)
u
i
(
a
)
<
0
u
i
(
a
o
). For each
i
∈
N
0
(
a
), since
a
o
≤
is
a SNE, we have
u
i
(
a
)
u
i
(0,
a
o
u
i
(
a
o
). Therefore
a
o
=
0
=
−
i
)
≤
is Pareto-superior
to
a
. Thus we show that
a
o
is the best SNE.
Proof of Theorem
5.1
We first show that
a
e
is a SNE. We consider three cases of a user
i
as follows.
∈
N
1
(
a
e
) and
i
Case 1
:
i
∈
N
I
,
k
Let
a
be the profile right after phase I during which
i
remains in
N
I
. Since
a
e
a
, using (
5.3
)wehave
≥
f
i
(1,
a
e
f
i
(0,
a
e
u
i
(1,
a
−
i
)
s
ij
a
j
−
i
)
−
−
i
)
≥
+
≥
0
S
i
j
∈
N
+
\
N
where the second inequality is due to the condition in line 5.
Case 2: i
∈
N
1
(
a
e
) and
i
∈
N
II
,
k
Let
a
be the profile right after
i
becomes determined in phase II. Since
a
e
a
,
≥
using (
5.3
)wehave
f
i
(1,
a
e
f
i
(0,
a
e
u
i
(1,
a
−
i
)
s
ij
a
j
i
)
−
i
)
≥
+
≥
0
−
−
S
i
j
∈
N
+
\
N
where the second inequality is due to the condition in line 10.
