Abstract

When does it make sense to act randomly? A persuasive argument from Bayesian decision theory legitimizes randomization essentially only in tie-breaking situations. Rational behaviour in humans, non-human animals, and artificial agents, however, often seems indeterminate, even random. Moreover, rationales for randomized acts have been offered in a number of disciplines, including game theory, experimental design, and machine learning. A common way of accommodating some of these observations is by appeal to a decision-maker’s bounded computational resources. Making this suggestion both precise and compelling is surprisingly difficult. Toward this end, I propose two fundamental rationales for randomization, drawing upon diverse ideas and results from the wider theory of computation. The first unifies common intuitions in favour of randomization from the aforementioned disciplines. The second introduces a deep connection between randomization and memory: access to a randomizing device is provably helpful for an agent burdened with a finite memory. Aside from fit with ordinary intuitions about rational action, the two rationales also make sense of empirical observations in the biological world. Indeed, random behaviour emerges more or less where it should, according to the proposal.