On the approximability of the range assignment problem on radio networks in presence of selfish agents

We investigate the existence of payment schemes which induce the stations to follow the decisions of a network manager in computing a range assignment, that is, truthful mechanisms for the range assignment problem. We provide both positive and negative results on the existence of truthful VCG-based mechanisms for this NP-hard problem. We prove that (i) in general, every polynomial-time truthful VCG-based mechanism computes a solution of cost far-off the optimum, unless P=NP and (ii) there exists a polynomial-time truthful VCG-based mechanism achieving constant approximation for practically relevant, still NP-hard versions, i.e., the metric and the well-spread case.