•two advertisers a and b
• a bids on query x, b bids on x and y
• both have budgets of 2
. query stream: xxyy
• optimal (offline): ?
• worst case greedy choice: ?
• worst case balance choice: ?

Optimal (offline): none of choice is optimal in case you are offline as it is an advertisement,

Worst case greedy choice: xxyy

Worst case BALANCE choice: xxyy

Explanation:

The above answer,

as maximum value can be x=4, y=2

hence, best greedy case= 4+4+4+4= 16 or

worst case can be: 2+2+2+2=8

worst case BALANCE choice: 12 ((16+8)/2=12)= xxyy=4+4+2+2=12

worst case greedy choice can be with at least 2 x and 2 y= 4+4+2+2=12 which is xxyy

Both worst case balance and greedy choice are the same, as the ,least greedy and balanced choice is as explained above, Remember for worst case greedy, we can select 2 x as  budget allows selection of 2 x out of 4 selections. 3 x will not be worst case, and we need to find the worst case, and balance in last case, and greedy in third case.  

Remember if we choose x, it is acquired by both A and B, and in case of y its only B. And hence the above answer.

And balance worst case is always same as worst case greedy choice, keep this always in mind. And this is clear as greediness is least when we are balanced.