I like the spot price idea (in the comments http://groups.google.com/group/google-appengine/msg/fe9a05c6...). It's similar to adwords' automatic auction for how close to the top your ad is, with the same benefits of getting the best market price (for buyers and sellers) of a limited resource. If no one else is using it, it could become close to free.

It also casts the other users as the opponent, instead of google.