Matching Algorithms for the Adwords Problem
We are given a set of advertisers each of whom have a daily budget Bi . 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 i for ad request q is denoted as biq. We assume that the bids are small with respect to the daily budgets of the advertisers (i.e, for each i and q, biq << Bi). Moreover, each advertisement slot can be allocated to at most one advertiser and the advertiser is charged his bid from his budget. The objective is to maximize the amount of money received from the advertisers.
Assumptions
- For the optimal matching (used for calculating the competitive ratio), assume that everyone’s budget is completely used.
- 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.
Datasets
A small dataset called bidder_dataset.csv. This dataset contains information about the advertisers. There are four columns: advertiser Id, query that they bid on, bid value for that query, and their total budget (for all the queries). The total budget is only listed once at the beginning of each advertiser’s list. In addition, the file queries.txt contains the sequence of arrivals of the keywords that the advertisers will bid on. These queries will arrive online and a fresh auctioning would be made for each keyword in this list.
Project Requirements
For this project, your task is to implement the Greedy, MSVV, and Balance algorithms as described below. Your code should also calculate the revenue for the given keywords list (in that order) as well as calculate an estimation of competitive ratio. The competitive ratio is defined as the minimum of ALG/OPT where ALG is mean revenue of your algorithm over all possible input sequences and OPT is the optimal matching. To estimate the value of ALG, simply compute the revenue over 100 random permutations of the input sequence and calculate the mean value.
Algorithms
Greedy
For each query q
a) If all neighbors (bidding advertisers for q) have spent their full budgets, then continue
b) Else, match q to the neighbor with the highest bid
MSVV
Let xu be the fraction of advertiser's budget that has been spent and ψ(xu) = 1 − e^(xu−1) . For each query q
a) If all neighbors have spent their full budgets, then continue
b) Else, match q to the neighbor i that has the largest biq * ψ(xu) value.
Balance
For each query q
a) If all neighbors have spent their full budgets, then continue
b) Else, match q to the neighbor with the highest unspent budget.
How to run
python adwords.py <greedy|mssv|balance>
Results
Using python with random.seed(0) for shuffling queries, the following was obtained.
| Command | Revenue | Competitive Ratio |
|---|---|---|
| python adwords.py greedy | 16731.40 | 0.94 |
| python adwords.py mssv | 17671.00 | 0.99 |
| python adwords.py balance | 12320.20 | 0.69 |