search
Best answer before the buzzer
It is the era when search must run under a hard clock: a robot deciding its next move as the world shifts, a game engine with seconds per turn, a control system that must act now with what it has found. A search that returns only when it finds the optimum is useless if the deadline arrives first. Design an anytime algorithm — one that always has a valid answer ready, improves it as long as time allows, and hands back the best-so-far the instant it is interrupted, ideally with a bound on how far from optimal that answer might be. Get it wrong and the agent blows the deadline, or returns a crude guess it never refined — anytime search is where bounded rationality meets a ticking clock.
Who this problem belongs to
The two figures whose methods fit it best, out of 68 in contention.
Simon coined 'bounded rationality' and 'satisficing' (from the late 1950s onward, crystallized in Models of Man, 1957), the foundational claim that real agents cannot optimize exhaustively under real time and cognitive constraints and must instead settle for a good-enough answer available when a decision is needed — precisely what this problem asks an anytime algorithm to do computationally. With Newell he treated problem solving as heuristic search that could be interrupted, and their chess-complexity work (1958) explicitly worried about the clock as much as the tree size. His framework is the philosophical foundation that later researchers (Russell and Wefald, most directly) formalized into concrete anytime algorithms and metareasoning theory. He supplied the concept of bounded rationality; the specific algorithmic machinery of interruptible search came slightly after him.
Russell, with Eric Wefald, wrote 'Do the Right Thing: Studies in Limited Rationality' (1991) and a series of papers formally developing anytime algorithms and metareasoning — computation that decides, in real time, when further deliberation is worth its cost versus acting now with the current best answer, and that always has a valid, improvable answer ready if interrupted. This is close to a direct, technical match for the problem as stated: it is the formal theory of bounded optimality that operationalizes Herbert Simon's bounded rationality into concrete algorithms with provable properties about time-quality tradeoffs. His later career, including AI: A Modern Approach and work on provably beneficial AI, kept resource-bounded reasoning as a recurring theme rather than a one-off contribution, making him arguably the single most direct match for this specific problem.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
68 figures are scored on this problem. Draw it in a battle to see where you land.