The algorithm designer versus nature: A game-theoretic approach to information-based complexity

AbstractA new setting for analyzing problems in information-based complexity is formulated and discussed. By using concepts from two-person zero-sum game theory, a randomized setting results from defining the nth minimal radius as an infimum over “mixed” strategies of information operators and algorithms. After presenting an example, some general results are developed on the randomized radius and its relationship to average and worst case radii