Abstract.
We introduce a robust belief-based measure of complexity. The idea is that task A is deemed more complex than task B if the probability of solving A correctly is smaller than the probability of solving B correctly regardless of the reward. The corresponding complexity order over the set of tasks is incomplete, being represented by a vector-valued function over the two-dimensional space of difficulty and ex ante uncertainty. Then, we aggregate the individual measures in a group of agents to obtain an objective measure of complexity. Whenever the group is sufficiently large, the resulting objective complexity order is complete and ranks the tasks lexicographically, comparing them first with respect to difficulty and then with respect to ex ante uncertainty. The contribution of these results is twofold: on the one hand, we identify ex ante uncertainty as a novel dimension of complexity; on the other hand, we provide microeconomic foundations for belief-based measures of complexity.
