Information Technology Reference
In-Depth Information
agents, and we are asked about the utility of
A
1
. In all of these inputs we have
thesamesetof
A
1
's edges
E
1
, the same list of declared edges of the other agent,
and the same payment constant,
c
. This payment constant is chosen such that
the payment from
A
1
to the mechanism is always less than 1, even if
A
1
declares
all its edges.
The only difference between the inputs is the target utility
k
. These inputs
are constructed such that
A
1
has
is the number of vertices
in
G
. The inputs are constructed so that the maximal utility
A
1
can achieve
is obtained by declaring some set of edges,
E
1
, and in this case,
A
1
's utility is
u
1
(
E
1
)=
v
1
(
E
1
)
|
V
|
edges, where
|
V
|
p
1
(
E
1
)=
E
1
|
−
|
E
|−
c
|
,where
|
E
|
is the number of edges in the
E
1
|
VERTEX-COVER graph
G
,and
is the number of vertices in the
minimal
vertex-cover
of
G
. We abuse notation a bit here, and denote
u
1
(
E
1
)and
v
1
(
E
1
)
as the utility and valuation
A
1
has when declaring the
E
1
subset of edges, since
the declared edges of all the other agents are known. Thus the flow chosen by
the mechanism only depends on
A
1
's chosen subset of edges,
E
1
.
|
5.2
The Process of the Reduction
Since the payment from
A
1
to the mechanism is always a multiple of
c
,we
can easily check how many vertices are used in the minimal vertex-cover of
G
.
We construct
G
from
G
, and use FLOW-EDGE-SUBSET to check if we can
achieve a utility of at least
|
E
|−|
V
|
c
, then check the possibility of achieving
|
2)
c
, and so on. The answer would initially
be 'yes', since due to the construction,
A
1
can achieve a utility of
E
|−
(
|
V
|−
1)
c
,then
|
E
|−
(
|
V
|−
c
by
declaring all its edges.
A
1
can decide to declare any number of edges between 0
and
|
E
|−|
V
|
. The questions are asked regarding higher and higher requested utilities,
so eventually, for some
x
|
V
|
∈
IN
,
0
≤
x
≤|
V
|
,theanswerfor
|
E
|−
xc
would be
'no'. We would then know the best utility that
A
1
can achieve is
(
x
+1)
c
,
and thus the minimal vertex-cover of
G
is of size
x
+ 1. This process involves
running FLOW-EDGE-SUBSET
|
E
|−
times, so if FLOW-EDGE-SUBSET can be
done in polynomial time, then this process can also be performed in polynomial
time.
|
V
|
5.3
Constructing the FLOW-EDGE-SUBSET Inputs
We now describe how the inputs for FLOW-EDGE-SUBSET are constructed
from the VERTEX-COVER input. We build a 5-layer network flow graph,
G
.
The
L
0
layer contains the single source vertex
s
,andthe
L
4
layer contains the
single target vertex
t
.Layer
L
1
contains a vertex
v
e
i
for each edge
e
i
E
in
the original VERTEX-COVER graph. Layer
L
2
contains a vertex
v
i,b
for each
vertex
v
i
∈
∈
V
in the original VERTEX-COVER graph. Layer
L
3
contains a single
vertex
v
i,a
for each vertex
v
i
∈
V
in the original VERTEX-COVER graph.
The edges between the layers are constructed as follows. The source vertex
s
is connected to all the vertices in
L
1
, and then we mark the edge (
s, v
e
i
)as
e
e
i
. Every vertex
v
e
i
in
L
1
is connected to exactly two vertices in
L
2
.Ifedge
e
i
∈
E
in
G
connects vertices
v
i
and
v
j
in it, then
v
e
i
is connected to
v
v
i
,b
and
