Since their budget is much larger than each individual incentive, isn't the greedy solution within epsilon of the optimal assignment? I.e. sort by v/c descending and take while sum(c) < B.
Type A: coupon a1 has cost 1, value 2. coupon a2 has cost 2, value 3.99.
Type B: coupon b1 has cost 1, value 1.
We have 100 people of Type A and 100 people of Type B. The total budget is 200.
The optimal solution is to pick all Type A people, coupon a2, for a value of 399.
Greedy picks all Type A people, coupon a1, and then all Type B people, coupon b1, for a value of 300.
1. You're right, a counter example for greedy (with 2 appox) looks something like: c1=.5+eps, v1=1, c2=.5, v2=.5+eps, B=2.