Information Technology Reference
In-Depth Information
to be edges representing a set of vertices that covers all the edges in
G
;itwould
choose
E
1
such that
E
=
EC
G,E
1
.
However,
A
1
also realizes it must give the mechanism payments for declaring
his edges. Since he pays a constant
c
per each edge he declares,
A
1
would want
to minimize the number of edges he declares. This conflicts with
A
1
's wish to
choose
E
1
so that
E
=
EC
G,E
1
, since fewer vertices cover fewer edges.
By choosing a low enough payment constant
c
,wemakesurethat
A
1
's top
priority is to cover all the edges in
G
. It is only his second priority to minimize
the number of edges he declares. Thus,
A
1
actually wishes to choose
E
1
so that
the set of vertices
E
1
represents is the minimal vertex cover of
G
.
The following sections formally prove the intuitive claims above.
5.4
Properties of the Constructed Inputs
Lemma 1.
If G had
|
E
|
edges, then in the generated network flow graph, A
1
's
valuation cannot exceed
|
E
|
.IfA
1
can get a valuation of
|
E
|
, its utility is in the
range
|
E
|−
1
≤
u
1
(
f
)
≤|
E
|
.
Proof.
The maximal flow cannot exceed
edges
between
L
0
and
L
1
, each with a capacity of 1. All of
A
1
's edges are between
L
2
and
L
3
, so the maximal flow through them also cannot exceed
|
E
|
, because there are only
|
E
|
|
E
|
.Thus,
A
1
's valuation of any flow
f
,
v
1
(
f
), cannot exceed
|
E
|
.
A
1
's utility when a flow
E
1
|
f
is chosen is
u
1
(
f, p
1
)=
v
1
(
f
)
−
p
1
=
v
1
(
f
)
−
c
|
. Due to the choice of
c
,
1
|V |
+
|E|
E
1
|·
p
1
=
|
<
1, so 0
≤
p
i
≤
1.
Let
E
1
⊂
E
1
be the subset of edges that
A
1
chooses to declare. We denote
EC
G,E
1
=
{
e
i
∈
E
|
e
i
=(
v
x
,v
y
) and at least one of the following holds:
E
1
E
1
}
(
v
v
x
,b
,v
v
x
,a
)
∈
or
(
v
v
y
,b
,v
v
y
,a
)
∈
. Similarly, we denote
EC
G
,E
1
=
{
e
e
i
|
e
i
∈
. Intuitively, we identify the edge
e
e
i
with the edge
e
i
in the original
graph. We identify the edge (
v
v
x
,b
,v
v
x
,a
)
EC
G
}
∈
E
1
with
vertex v
x
in the original
graph
G
, and a subset of edges
E
1
V
in
G
. Such a set of vertices in
G
covers a subset of the edges in it.
EC
G
is the
set of edges covered by these vertices
V
E
1
,and
EC
G
⊂
E
1
with a subset of vertices
V
E
1
⊂
is the set of edges in
G
corresponding to the covered edges.
Lemma 2.
Let E
1
⊂
E
1
be an optimal choice of edges for A
1
to declare. Then
EC
G,E
1
=
E.
Proof.
Let
E
1
be an optimal choice of
A
1
's edges,
f
be the flow chosen by the
mechanism in this case, and
EC
G,E
1
be the subset of
E
, as explained above.
Assume by negation that there
is
some
e
=(
x, y
)
EC
G,E
1
.
There cannot be any flow on
e
e
in
G
, since having such a flow
f
(
s, v
e
)
>
0
would require having either flow
f
(
v
e
,v
x,b
)
>
0or
f
(
v
e
,v
y,b
)
>
0, since
v
e
is
connected only to these two vertices. However, this would require having either
aflow
f
(
v
x,b
,v
x,a
)
>
0or
f
(
v
y,b
,v
y,a
)
>
0, both of which cannot occur, since
e/
∈
E
that
e/
∈
E
1
. Thus, there cannot be
any flow on
e
e
, and the maximal flow between
L
0
and
L
1
cannot exceed
E
1
,and(
v
y,b
,v
y,a
)
/
∈
EC
G,E
1
,and(
v
x,b
,v
x,a
)
/
∈
∈
|
E
|−
1.