you're reading...

SACT Friday seminar

Dear all,

This Friday’s talk will be given by Julian Mestre. There follows an abstract of his talk. Also, please contact me if you would like to give a talk any time in the future.

Title : Dueling Algorithms


I will present the paper "Dueling Algorithms" by Immorlica, Kalai, Lucier, Moitra, Postlewaite, and Tennenholtz, which will appear in the upcoming STOC. From the paper’s abstract:

We revisit classic algorithmic search and optimization problems from the perspective of competition. Rather than a single optimizer minimizing expected cost, we consider a zero-sum game in which an optimization problem is presented to two players, whose only goal is to outperform the opponent. Such games are typically exponentially large zero-sum games, but they often have a rich combinatorial structure. We provide general techniques by which such structure can be leveraged to find minmax-optimal and approximate minmax-optimal strategies. We give examples of ranking, hiring, compression, and binary search duels, among others. We give bounds on how often one can beat the classic optimization algorithms in such duels.

link: http://arxiv.org/abs/1101.2883

Ilia Zvedeniouk



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: