Information Technology Reference
In-Depth Information
Suppose we add to
E
1
the edge (
v
x,b
,v
x,a
). This would allow the mechanism
to increase the flow in the following path by exactly 1:
s, v
e
,v
x,b
,v
x,a
,t
, resulting
in a flow
f
. The flow through
A
1
's edges is exactly the same as before, except
there is now a flow of 1 through (
v
x,b
,v
x,a
), so
v
1
(
f
)=
v
1
(
f
) + 1. Since the
payment to the mechanism is always less than 1, the total utility of
A
1
has
increased, so
E
1
was not an optimal choice for
A
1
to begin with.
Lemma 3.
If A
1
declares E
1
⊂
E
1
such that EC
G,E
1
=
E, the mechanism can
choose a flow f such that
|
f
|
=
|
E
|
.
Proof.
We can fill the capacities of all the edges between
L
0
and
L
1
,havingthe
vertices of
L
1
with a total incoming flow of
|
E
|
.Since
EC
G,E
1
=
E
,wealsohave
EC
G
,E
1
, and every vertex
v
e
i
in
L
1
is connected to at least
one vertex
v
x,b
in layer
L
2
that is connected (in turn) to
v
x,a
in layer
L
3
by an
edge
e
=
{
e
e
i
|
e
i
∈
E
}
E
1
. We choose the flow
f
(
v
e
i
,v
x,b
) = 1. We then continue the flow by
sending the incoming flow of vertex
v
x,b
to
v
x,a
,bychoosing
f
(
v
x,b
,v
x,a
)=
v
e
i
∈L
1
∈
f
(
v
e
i
,v
x,b
)
.
(8)
We can do this since the capacity of the edges between
L
2
and
L
3
is
|
E
|
,so
c
(
v
x,b
,v
x,a
)=
, and there is no danger of having a flow coming into a ver-
tex
v
x,b
higher than the total capacity of its outgoing edges. The flow is then
continued by sending all the incoming flow of vertex
v
x,a
to the target vertex:
f
(
v
x,a
,t
)=
f
(
v
x,b
,v
x,a
). Again, this is possible since the capacity of the edges
between
L
3
and
L
4
is
|
E
|
|
E
|
.
Therefore, the optimal subset of edges that
A
1
can declare,
E
1
⊂
E
1
, allows the
mechanism to achieve the maximal possible flow
f
∗
,ofsize
f
∗
|
|
=
|
E
|
.
Lemma 4.
The optimal subset of edges for A
1
, E
1
⊂
E
1
, gives A
1
a valuation
of v
1
(
f
∗
)=
|
E
|
.
Proof.
From Lemma 2 and Lemma 3 we know that if
A
1
declares
E
1
in the
optimal solution, the mechanism can choose a flow
f
such that
.By
Lemma 1 this is a maximal flow that maximizes the utility of
A
1
.Since
A
1
controls all the edges between
L
2
and
L
3
and has no other edges, we have a
total flow of
|
f
|
=
|
E
|
|
E
|
through
A
1
's edges.
As a private case of Lemma 4, we get that
A
1
can get a valuation of
by
declaring all of its edges, since
EC
G,E
1
=
E
.Thiscasegives
A
1
a utility of
|
|
E
|
E
|−
edges.
Lemma 4 shows that the optimal subset of edges for
A
1
,
E
1
c
|
E
1
|
, since we have declared
|
E
1
|
⊂
E
1
,gives
A
1
a valuation of
v
1
(
f
∗
)=
. However, to calculate
A
1
's utility in this case, we
must also know the payment that
A
1
gives the mechanism. This payment only
depends on the number of edges in
E
1
.
|
E
|
