Reference no: EM131583696

Question: Show how to modify Example by changing the bids and/or budgets to make the competitive ratio come out as close to 0 as you like.

Example: Suppose there are two advertisers A1 and A2, and one query q. The bids on q and budgets are:

Bidder       Bid         Budget

A₁             1            110

A₂             10          100

If there are 10 occurrences of q, the optimum off-line algorithm will assign them all to A2 and gain revenue 100. However, because A1's budget is larger, Balance will assign all ten queries to A1 for a revenue of 10. In fact, one can extend this idea easily to show that for situations like this one, there is no competitive ratio higher than 0 that holds for the Balance Algorithm.