  With spectrum auctions as our prime motivation, in this paper we analyze
combinatorial auctions where agents' valuations exhibit complementarities.
Assuming that the agents only value bundles of size at most $k$ and also
assuming that we can assess prices, we present a mechanism that is efficient,
approximately envy-free, asymptotically strategy-proof and that has
polynomial-time complexity. Modifying an iterative rounding procedure from
assignment problems, we use the primal and dual optimal solutions to the linear
programming relaxation of the auction problem to construct a lottery for the
allocations and to assess the prices to bundles. The allocations in the lottery
over-allocate goods by at most $k-1$ units, and the dual prices are shown to be
(approximately) envy-free irrespective of the allocation chosen. We conclude
with a detailed numerical investigation of a specific spectrum allocation
problem.
