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




Custom Search