Theory-Experimental Seminar

Evgenii Safonov

Queen Mary University of London

27-Mar-2023

seminar – 14:30

Abstract

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]

Leave Comment

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

clear formSubmit

This site uses Akismet to reduce spam. Learn how your comment data is processed.