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.
|Date of creation:||17 Jan 2011|
|Date of revision:|
|Contact details of provider:|| Postal: |
Web page: http://www.kellogg.northwestern.edu/research/math/
More information through EDIRC
|Order Information:|| Email: |
When requesting a correction, please mention this item's handle: RePEc:nwu:cmsems:1545. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Fran Walker)
If references are entirely missing, you can add them using this form.