Abstract
When goods are substitutes, auctions in which price clocks move monotonically can achieve efficient outcomes with computations that are (typically) pseudo-polynomial. However, while in such real economic problems as the FCC incentive auction, goods seem intuitively to be approximate substitutes, many steps in the clock auction computations are NP-complete. We introduce a metric on problems to describe nearness to substitutes and show that a properly devised clock auction can achieve near-efficiency when the distance is small.