Information Technology Reference
In-Depth Information
rule we use is simple: each agent pays the mechanism a constant of
c
for each
edge it declares it owns. Let
E
i
⊂
E
i
be the subset of edges an agent declares it
owns. Then
p
i
(
E
i
)=
c
E
i
|
. To make sure the mechanism is individual rational,
the payment
p
i
should give the agent a utility of 0 when the agent's valuation
of the given flow is less than
c
|
|
E
i
|
. Thus, the payment rule is: if
v
i
(
f
∗
)
>c
|
E
i
|
,otherwise
p
i
=
v
i
(
f
∗
).
Assume that
A
i
knows
E
j
for all
j
E
i
|
then
p
i
=
c
|
=
i
. It can easily calculate the utility it
would get by truthfully declaring all its edges. How hard is it for
i
to find a
subset of edges it could declare to the mechanism so as to gain a higher utility?
First, note that the question itself is under-constrained. Even given
E
j
for all
j
,
including
i
, there may be several maximal flows; the mechanism is free to choose
any of them. However, we will show that even if
A
i
can decide
which
maximal
flow the mechanism chooses, it would still remain an NP-hard problem for that
agent to find a better subset of edges.
We now define the problem of
finding
the optimal manipulation in the self-
interested network flow domain.
FLOW-EDGE-SUBSET: We are given a layered graph flow network, with the
capacity function
c
:
E
IR ,
E
−i
the declared edges of the other agents, and
E
i
,
the set of our edges. We are also given the constant
c
of the payment, and we know
that if we declare that we have
k
edges, our payment to the mechanism would
be
p
i
=
ck
. We assume the mechanism prefers a maximal flow that maximizes
our
utility: if we report a subset of edges
E
i
⊂
→
E
i
the mechanism would choose
the maximal flow
f
∗
to be the flow that maximizes
e∈E
f
∗
,i
f
(
e
)fromamong
all the possible maximal flows. We are also given a constant
k
, the target utility
for
A
i
. We are asked if there is a subset of
A
i
's edges
E
i
⊂ E
i
, such that the
maximal flow chosen by the mechanism,
f
∗
(
E
1
, ..., E
i−
1
,E
i
,E
i
+1
, ..., E
I
)gives
A
i
a utility of at least
k
:
u
i
(
f
∗
,p
i
)=
v
i
(
f
∗
)
E
i
|≥
−
p
i
=
f
(
e
)
−
c
|
k.
(7)
e∈E
f
∗
,i
5.1 NP-Completeness of FLOW-EDGE-SUBSET
First, we note that FLOW-EDGE-SUBSET is in NP, because given a subset of
edges
E
i
⊂ E
i
we can easily compute the maximal flow. We show that FLOW-
EDGE-SUBSET is NP-complete by reducing a general VERTEX-COVER prob-
lem to a FLOW-EDGE-SUBSET problem. The reduction shows that FLOW-
EDGE-SUBSET is NP-complete even if the inputs are restricted to problems
where there are only two agents, and the graph has only 5 layers.
VERTEX-COVER: We are given a graph
G
=
<V,E>
and a constant
n
and
are asked if there is a subset of
n
vertices
V
⊂
V
|
V,
|
=
n
that covers all the
V
.
The reduction is done as follows. From the VERTEX-COVER input, we build
inputs for the FLOW-EDGE-SUBSET problem. Given the original VERTEX-
COVER graph
G
, we build a layer graph
G
. All the inputs to FLOW-EDGE-
SUBSET are built with this layer graph
G
, and in all of them there are two
V
edges
∀
(
u,v
)
∈E
either u
∈
or v
∈