! Exercise 8.4.3: Show how to modify Example 8.9 by changing the bids and/or

budgets to make the competitive ratio come out as close to0 as you like.

\

Example 8.9: Suppose there are two advertisers A1 and A2, and one querv q. The bids on q and budgets are: Bidder Bid |Budget 110 100 10 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. D