How big are the bids relative to the budget and what response options do you have? You could try a throttle back on the bidding rate or discount your bid amounts as you get closer to the limit:

A) Knowing that you've got N servers and a general rate M of requests, and a typical time of T between bids and win notifications, a quick statistical calculation will tell you approximately how many other bids you can expect the other servers to submit before you know if you've won the current offer.

Reduce your odds of bidding accordingly. EG: if the expected amount of wins is x2.0 what the current budget will allow for, then decline to bid with 0.5 chance.

B) Set up a table of "Budget remaining" vs "Discount demanded". For example, if you're down to $40 out of the $100 initial budget, then reduce your bid amount by 5%. If you get down to $20 out of $100, then reduce bid amounts by 10%. $10/$100 => reduce bid by 20%.

The idea here being that you will reduce the number of bids you win as you get close to the limit, while at the same time getting more profit from the bids you do happen to win.

Comment onRe: A distributed design challenge