EconStor >
Northwestern University >
Kellogg School of Management - Center for Mathematical Studies in Economics and Management Science, Northwestern University  >
Discussion Papers, Kellogg School of Management, Northwestern University >

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10419/59634
  

Full metadata record

DC FieldValueLanguage
dc.contributor.authorImmorlica, Nicoleen_US
dc.contributor.authorKalai, Adam Taumanen_US
dc.contributor.authorLucier, Brendanen_US
dc.contributor.authorMoitra, Ankuren_US
dc.contributor.authorPostlewaite, Andrewen_US
dc.contributor.authorTennenholtz, Mosheen_US
dc.date.accessioned2012-01-19en_US
dc.date.accessioned2012-07-12T12:33:41Z-
dc.date.available2012-07-12T12:33:41Z-
dc.date.issued2012en_US
dc.identifier.urihttp://hdl.handle.net/10419/59634-
dc.description.abstractWe 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.en_US
dc.language.isoengen_US
dc.publisherNorthwestern Univ., Kellogg Graduate School of Management, Center for Mathematical Studies in Economics and Management Science Evanstonen_US
dc.relation.ispartofseriesDiscussion Paper, Center for Mathematical Studies in Economics and Management Science 1545en_US
dc.subject.ddc330en_US
dc.titleDueling algorithmsen_US
dc.typeWorking Paperen_US
dc.identifier.ppn684639572en_US
dc.rightshttp://www.econstor.eu/dspace/Nutzungsbedingungenen_US
Appears in Collections:Discussion Papers, Kellogg School of Management, Northwestern University

Files in This Item:
File Description SizeFormat
684639572.pdf346.46 kBAdobe PDF
No. of Downloads: Counter Stats
Show simple item record
Download bibliographical data as: BibTeX

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