What I would have done is divided out the number of slots on a state-by-state basis (proportional to population, say) and had an auction in each state.

I'm not convinced there would be a huge demand for H-1b visas if companies couldn't underpay them relative to people with green cards or citizenship. Certainly on the margins there are companies that are looking for specialized skills, but for the most part the industry likes high H-1b caps because they depress wages.