Please use this identifier to cite or link to this item: http://hdl.handle.net/10419/59634
Authors: 
Immorlica, Nicole
Kalai, Adam Tauman
Lucier, Brendan
Moitra, Ankur
Postlewaite, Andrew
Tennenholtz, Moshe
Year of Publication: 
2012
Series/Report no.: 
Discussion Paper, Center for Mathematical Studies in Economics and Management Science 1545
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.
Document Type: 
Working Paper

Files in This Item:
File
Size
346.46 kB





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.