Dueling Algorithms

Details Dueling Algorithms Dueling Algorithms

2011-01-14

arxiv.org/abs/1101.2883v1

Computer Science

Computer Science and Game Theory

26 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Dueling Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dueling Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dueling Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-227499