True Costs of Cheap Labor Are Hard To Measure:
Edge Deletion and VCG Payments in Graphs
Authors: Edith Elkind
Abstract:
We address the problem of lowering the buyer's expected
payments in shortest path auctions, where the buyer's goal
is to purchase a path in a graph in which edges are owned by
selsh agents. We show that by deleting some of the edges
of the graph, one can reduce the total payment of the VCG
mechanism by a factor of(n). However, we prove that it
is NP-hard to nd the best subset of edges to delete, even
if the edge costs are small integers, or the graph has very
simple structure; in the former case, this problem is hard
to approximate, too. On the positive side, we describe a
pseudopolynomial time algorithm for series-parallel graphs
and xed edge costs. Also, we discuss the applicability of
this algorithm for the case of general (probabilistic) costs
and derive a general lower bound on the performance of
algorithms that are based on expected edge costs.