Resource allocation, computational complexity, and market design

Abstract

With three experiments, we study the design of financial markets to help spread knowledge about solutions to the 0-1 Knapsack Problem (KP), a combinatorial resource allocation problem. To solve the KP, substantial cognitive effort is required; random sampling is ineffective and humans rarely resort to it. The theory of computational complexity motivates our experiment designs. Complete markets generate noisy prices and knowledge spreads poorly. Instead, one carefully chosen security per problem instance causes accurate pricing and effective knowledge dissemination. This contrasts with information aggregation experiments. There, values depend on solutions to probabilistic problems, which can be solved by random drawing.