**Theory-Experimental Seminar**

*Queen Mary University of London*

27-Mar-2023

seminar – 14:30

An agent needs to choose the best alternative drawn randomly with replacement from a menu of unknown composition. The agent is boundedly rational and employs an automaton decision rule: she has finitely many memory states, and, in each, she can inquire about some attribute of the currently drawn alternative and transition (possibly stochastically) either to another state or to a decision. Defining the complexity of a decision rule by the number of transitions, I study the minimal complexity of a decision rule that allows the agent to choose the best alternative from any menu with probability arbitrarily close to one. Agents in my model differ in their languages—collections of binary attributes used to describe alternatives. My first result shows that the tight lower bound on complexity among all languages is 3⌈log2(m)⌉, where m is the number of alternatives valued distinctly. My second result provides a linear upper bound. Finally, I call adaptive a language that facilitates additive utility representation with the smallest number of attributes. My third result shows that an adaptive language always admits the least complex decision rule that solves the choice problem. When (3/4) · 2n < m ≤ 2n for a natural n, a language admits the least complex decision rule if and only if it is adaptive. [/vc_column_text][/vc_column][/vc_row]