Choice and complexity (Q581191)

An attempt is made to propose a concept of limited rationality for choice functions based on computability theory in computer science. Starting with the observation that it is possible to construct a machine simulating strategies of each individual in society, one machine for each individual's preference structure, we identify internal states of this machine with strategies or strategic preferences. Inputs are possible actions of other agents in society, thus society is effectively operating as a social choice machine. The main result states that effective realization of choice functions is bound by the `complexity of computing machines'. Given a certain social choice machine, this complexity is simply the length of the shortest program which simulates this machine.