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




Custom Search