Abstract.
We introduce a robust belief-based measure of complexity. The idea is that task A is classified as more complex than task B if the probability of correctly solving A is smaller than the probability of correctly solving B, regardless of the reward. We provide a full characterization of the incomplete order over the set of tasks that this measure induces. This characterization allows us to identify the degree of (prior) uncertainty as a novel dimension of complexity, i.e., in order for task A to be more complex than task B, it does not suffice that A is more difficult than B; it should also not be the case that the agent has much more prior information about A than about B. Then, using a lab experiment, where we can exogenously control both difficulty and uncertainty, we corroborate our theoretical predictions. Thus, the recently surging use of expected accuracy as a good measure of complexity is well warranted, as long as accuracy is elicited for multiple different rewards using the strategy method.
