  We present algorithms for implementing local spectrum redistribution in
wireless networks using a mechanism design approach. For example, in single-hop
request scheduling, secondary users are modeled as rational agents that have
private utility when getting assigned a channel for successful transmission. We
present a rather simple algorithmic technique that allows to turn existing and
future approximation algorithms and heuristics into truthful mechanisms for a
large variety of networking problems. In contrast to previous work, our
approach works for virtually all known interference models in the literature,
including the physical model of interference based on SINR. It allows to
address single-hop and multi-hop scheduling, routing, and even more general
assignment and allocation problems. Our mechanisms are randomized and represent
the first universally-truthful mechanisms for these problems with rigorous
worst-case guarantees on the solution quality. In this way, our mechanisms can
be used to obtain guaranteed solution quality even with risk-averse or
risk-seeking bidders, for which existing approaches fail.
