Information Technology Reference
In-Depth Information
5.5
Proof of the Reduction
We now prove the validity of the reduction, by showing that the the maximal
utility
A
1
can achieve in the constructed network flow graph is determined by
the size of the minimal vertex cover in the original graph.
Theorem 1.
The size of the minimal vertex-cover of G is k if and only if the
maximal utility of A
1
in the constructed inputs to FLOW-EDGE-SUBSET is
|
E
|−
kc.
Proof.
Assume the maximal utility
A
1
can achieve is
kc
. Due to Lemma 4,
in order to obtain this optimal utility
A
1
has to declare
E
1
|
E
|−
⊂
E
1
, a subset
E
1
|
of edges with size
|
=
k
. Consider the set
V
E
1
=
{
v
x
∈
V
|
(
v
x,a
,v
x,b
)
∈
E
1
}
. From Lemma 2 we have
EC
G,E
1
=
E
, so this set is a vertex-cover of
G
.Itssizeis
=
k
,sincethepayment
A
1
made to the mechanism is
kc
. Assume by negation that this is not the
minimal
vertex-cover of
G
.Then
there exists a vertex cover
VC
|
V
E
1
|
VC
|
=
k
.Consider
with a smaller size of
|
VC
}
E
VC
=
{
(
v
x,b
,v
x,a
)
∈
E
1
|
v
x
∈
. This is a subset of
A
1
's edges that (by
definition of
EC
G,X
),
EC
G,E
VC
=
E
.Thus,
v
1
(
E
VC
)=
|
E
|
. However, since
VC
|
=
k
<k
=
|
|
V
E
1
|
, the payment from
A
1
to the mechanism for declaring
is only
p
1
(
E
VC
)=
k
<k
. Thus the utility of
A
1
when using
E
VC
E
VC
is
kc
=
u
1
(
E
1
), and we
would have a subset of edges giving a better utility than the optimal solution.
On the other hand, if we have a vertex-cover
VC
for
G
with size
k
c>
u
1
(
E
VC
)=
v
1
(
E
VC
)
−
p
1
(
E
VC
)=
|
E
|−
|
E
|−
|
VC
|
=
k
,
consider
E
VC
=
. Again, this is a subset of
A
1
's
edges that (by definition of
EC
G,X
)makes
EC
G,E
VC
=
E
.Thus,
v
1
(
E
VC
)=
|
{
(
v
x,b
,v
x,a
)
∈
E
1
|
v
x
∈
VC
}
E
|
. The utility of
A
1
when using
E
VC
is
u
1
(
E
VC
)=
v
1
(
E
VC
)
−
p
1
(
E
VC
)=
|
kc
is achievable.
It remains to show that this is the
maximal
utility achievable. Suppose, by
negation, that we have a choice of edges
E
1
E
|−
kc
, so a utility of
|
E
|−
⊂
E
1
that gives
A
1
a higher util-
ity. The valuation of
E
1
must also be
v
1
(
E
1
)=
, since a higher valuation
is not possible, and a lower valuation would result in a utility that is below
u
1
(
E
VC
) (since the payment to the mechanism is less than 1). This means that
the payment for
E
1
|
E
|
E
1
|
is less than the payment for
E
VC
,or
|
<
|
E
VC
|
.As
,
E
1
must be a set such that
explained above, in order to achieve a utility of
|
E
|
E
1
}
EC
G,E
1
=
E
,so
V
E
1
=
{
v
x
∈
V
|
(
v
x,b
,v
x,a
)
∈
must be a vertex-cover of
E
1
|
G
. However, since
, this would be a vertex-cover of a size
smaller than the size of the minimal vertex-cover.
|
V
E
1
|
=
|
<
|
E
VC
|
Due to Theorem 1, the process of the reduction as described above is valid, and
FLOW-EDGE-SUBSET is NP-complete.
6
Conclusions and Future Directions
We have presented a mechanism for the distributed network flow problem with
self-interested agents. With a proper choice of the payment constant
c
, find-
ing a beneficial manipulation is an NP-complete problem. If most instances of