Problem: We are given a set of advertisers each of whom has a daily budget π΅π. When a user performs a query, an ad request is placed online and a group of advertisers can then bid for that advertisement slot. The bid of advertiser π for an ad request π is denoted as πππ. We assume that the bids are small with respect to the daily budgets of the advertisers (i.e., for each π and π, πππβͺ π΅π). Moreover, each advertisement slot can be allocated to at most one advertiser and the advertiser is charged his bid from his/her budget. The objective is to maximize the amount of money received from the advertisers.
For this project, we make the following simplifying assumptions:
- For the optimal matching (used for calculating the competitive ratio), we will assume everyoneβs budget is completely used. (optimal revenue = the sum of budgets of all advertisers)
- The bid values are fixed (unlike in the real world where advertisers normally compete by incrementing their bid by 1 cent).
- Each ad request has just one advertisement slot to display.