Frugal Path Mechanisms

We consider the problem of selecting a low-cost s - t path in a graph where the edge costs are a secret, known only to the various economic agents who own them. To solve this problem, Nisan and Ronen applied the celebrated Vickrey-Clarke-Groves (VCG) mechanism, which pays a premium to induce the edges so as to reveal their costs truthfully. We observe that this premium can be unacceptably high. There are simple instances where the mechanism pays Theta(n) times the actual cost of the path, even if there is an alternate path available that costs only (1 + epsilon) times as much. This inspires the frugal path problem, which is to design a mechanism that selects a path and induces truthful cost revelation, without paying such a high premium. This article contributes negative results on the frugal path problem. On two large classes of graphs, including those having three node-disjoint s - t paths, we prove that no reasonable mechanism can always avoid paying a high premium to induce truthtelling. In particular, we introduce a general class of min function mechanisms, and show that all min function mechanisms can be forced to overpay just as badly as VCG. Meanwhile, we prove that every truthful mechanism satisfying some reasonable properties is a min function mechanism. Our results generalize to the problem of hiring a team to complete a task, where the analog of a path in the graph is a subset of the agents constituting a team capable of completing the task.