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

A 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.