DIMACS Research Experience for Undergraduates

**Name:** Ben Sowell

**Email:** sowellb at carleton dot edu

**Home Institution:** Carleton College

**Advisor:** S. Muthu Muthukrishnan

**Co-Advisors:** Graham Cormode, Christian Sohler

As search engines such as Yahoo and Google continue to grow, they have developed increasingly sophisticated advertising models. In many cases, advertisers specify a maximum daily budget and a set of keywords that they wish to bid on, and then an automated auction is performed to determine which ads should be displayed for a given user query. The problem we are interested in (sometimes called the "AdWords problem") is to maximize the revenue while respecting the daily budget of each advertiser.

This problem can be modelled as an on-line bipartite graph matching
problem. Given a set of keywords searches and a set of advertisers, we
want to match advertisers to keywords to maximize the total revenue
without exceeding any advertiser's daily budget or individual
bids. This problem is called *on-line* because the assignments
must be made immediately when each keyword is received. We can
describe a similar *off-line* problem where we don't assign the
matching until we have received all of the queries. One way of
evaluating the on-line algorithm is to look at the competative ratio
of revenue generated by the on-line algorithm to that generated by an optimal off-line algorithm.

In their paper "AdWords and Generalized On-line Matching," Aranyak Mehta et. al. present a deterministic algorithm that achieves a competative ratio of 1 - 1/*e*. My task will be to understand and implement this algorithm and to use it to test a number potential modifications.

I've finished a much modified version of the auction simulation program. It supports second price bidding, multiple slots, and constant and variable graphs.

I've added several other naive algorithms to my program. It can now choose bidders based on the algorithm from the paper, the maximum bid, the maximum budget left, and the minimum budget left. I've also created a version that runs all of these algorithms simultaneously for testing and data collection. The source code is available for AuctionHeuristic.c, AuctionParallel.c

I've finished implementing the online algorithm from "Adwords and Generalized On-line Matching." The source code is available in either C or Java.

My initial REU presentation is also available for download: (Keynote)(PowerPoint)(pdf)

Bala Kalyansundaram and Kirk R. Pruhs. An optimal deterministic algorithm for online b-matching. *Theoretical Computer Science*, 233(1-2):319-325, 2000.

R.M. Karp, U.V. Vazirani, and V.V. Vazirani. An optimal algorithm for online bipartite matching. In *Proceedings of the 22nd Annual ACM Symposium on Theory of Computing*, 1990.

A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani. Adwords and generalized
online matching. In *Proceedings of the 46th IEEE Symposium on Foundations
of Computer Science*, 2005.