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




Custom Search