Information Technology Reference
In-Depth Information
Case 3: i
∈
N
0
(
a
e
)
Since
i
is not included in
N
II
in phase II of the last round, using (
5.3
)wehave
f
i
(1,
a
e
f
i
(0,
a
e
u
i
(1,
a
−
i
)
s
ij
a
j
<
0
i
)
−
i
)
=
+
−
−
S
i
j
∈
N
+
\
N
where the inequality is due to the condition in line 10.
Next we show that
a
e
is Pareto-optimal. Suppose there exists
a
that is Pareto-
superior to
a
e
. It suffices to show that (i)
N
1
(
a
)
\
N
1
(
a
e
)
N
1
(
a
e
)
=
∅
and (ii)
\
N
1
(
a
)
N
1
(
a
)
\
N
1
(
a
e
)
=
∅
. We first show part (i). Suppose
=
∅
. Then for
∈
N
1
(
a
)
\
N
1
(
a
e
), we have
u
i
(
a
)
u
i
(
a
e
)
each
i
≥
=
0. Let
i
be the first user
N
1
(
a
)
\
N
1
(
a
e
) whose action is set to 0 during phase I of the last round,
among
¯
=
¯
≥
a
−
i
,wehave
and
a
be the profile right before
a
i
0 is performed. Since
a
−
i
+
j
∈
N
u
i
(1,
a
−
i
)
¯
s
ij
¯
≥
¯
≥
≥
u
i
(1,
a
−
i
)
a
j
u
i
(1,
a
−
i
)
0, which contradicts to the
S
i
+
\
N
condition in line 5.
Next we show part (ii). Suppose
N
1
(
a
e
)
\
N
1
(
a
)
=
∅
. Since we have shown
part i), we must have
a
<
a
e
. Then for each
i
∈
N
1
(
a
)
ↂ
N
1
(
a
e
), we have
u
i
(
a
)
u
i
(
a
e
). Since
u
i
(
a
)
u
i
(
a
e
) for each
i
∈
N
0
(
a
)
∩
N
0
(
a
e
), there must
≤
=
0
=
∈
N
1
(
a
e
)
\
N
1
(
a
) such that
u
i
(
a
e
)
< u
i
(
a
)
exist
i
=
0. Suppose
i
is included in
N
II
during phase II of some round. Let
a
be the profile right before
a
i
=
¯
1 is performed.
a
e
,wehave
u
i
(
u
i
(
a
e
)
<
0. Then it follows from 0
Since
a
¯
≤
a
)
¯
≤
≤
f
i
(1,
a
−
i
)
¯
−
+
j
∈
N
i
f
i
(0,
a
−
i
)
¯
=
u
i
(1,
a
−
i
)
¯
s
ij
¯
a
j
that there must exist
j
∈
N
such that
S
i
+
+
1, and therefore
a
j
∈
N
1
(
a
), we have
u
j
(
a
e
)
u
j
(
a
)
a
i
−
a
i
=
a
j
¯
=
=
1. If
j
−
≥
∈
N
1
(
a
e
)
\
N
1
(
a
) and
1
>
0, which is a contradiction. Therefore we must have
j
u
j
(
a
e
)
u
j
(
a
)
≤
=
0. Let
a
be the profile right before
a
j
ˆ
=
1 is performed. Since
a
)
< u
j
(
a
e
)
ˆ
j
is included before
i
,wehave
u
j
(
0. Then we can use the above
argument sequentially, until we find some
k
that leads to contradiction.
≤
Proof of Theorem
5.2
N
I
,
k
during the execution that computes
a
e
. For each
N
I
,
k
Let
be the set of users in
i
∈
N
I
,1
,wehave
u
i
(1,
a
−
i
)
s
ij
a
j
+
≥
u
i
(1,
a
−
i
)
+
s
ij
a
j
≥
0
.
S
i
S
i
j
∈
N
+
\
N
j
∈
N
+
\
N
ↆ
N
I
,1
. Similarly, we can show that for any
i
Therefore we must have
N
I
,1
∈
N
II
,1
\
N
I
,1
, we must have
i
∈
N
II
,1
. Using this argument sequentially, we can show
1
N
I
,
i
∪
N
II
,
i
ↆ∪
1
N
I
,
i
∪
N
II
,
i
for any
k
, and therefore
a
e
a
e
.
When a user becomes determined with action 1, the increment of social welfare of
determined users by changing its action from 0 to 1 is no less than the increment of its
social group utility derived from determined users, which is non-negative. Therefore
we can see that
v
(
a
e
)
i
i
that
∪
≤
=
=
v
(
a
e
).
≤
