SPECIAL TIME: 1:30 -- 2:30 pm,  Tuesday, Dec 9, 2008

PLACE: CSE 503  

SPEAKER: Nikhil Devanur
         Microsoft Research

TITLE: Online keyword matching under random permutations


ABSTRACT: 

We consider the problem of a search engine trying to assign a sequence
of search keywords to a set of competing bidders, each with a daily
spending limit.  The goal is to maximize the revenue generated by
these keyword sales, bearing in mind that, as some bidders may
eventually exceed their budget, not all keywords should be sold to the
highest bidder. We assume that the sequence of keywords (or
equivalently, of bids) is revealed on-line.  Our concern will be the
competitive ratio for this problem versus the off-line optimum.

We extend the current literature on this problem by considering the
setting where the keywords arrive in a random order.  In this setting
we are able to achieve a competitive ratio of $1-\epsilon$ under some
mild, but necessary, assumptions.  In contrast, it is already known
that when the keywords arrive in an adversarial order, the best
competitive ratio is bounded away from 1. Our algorithm is motivated
by PAC learning, and proceeds in two parts: a training phase, and an
exploitation phase.

Joint work with Tom Hayes, UNM.