  We consider allocation of a resource to multiple interested users with a
constraint that if the resource is allocated to user $i$ then it can not be
allocated simultaneously to a predefined set of users $\cS_i$ . This scenario
arises in many practical systems that include wireless networks and constrained
queuing systems. It is known that socially optimal strategy-proof mechanism is
not only NP-hard, but it is also hard to approximate. This renders optimal
policy hard to use in practice. Here, we propose a computationally efficient
mechanism and prove it to be strategy proof. Using Monte Carlo simulations, we
show that the social utility of the proposed scheme is close to that of the
optimal. Further, we demonstrate how the proposed mechanism can be used for
fair and efficient short-term spectrum allocation in resource constrained large
wireless networks.
