Markets as oracles
Can markets facilitate solving NP-hard problems?
We study how markets may help solve computationally hard problems (technically, NP-hard computational problems). Borrowing from the theory of oracles in computer science, we propose market designs that are more effective at distributing relevant information. We find that our designs significantly increase the likelihood of participants finding the solutions of such problems. Crucial information spreads among participants, yet this information does not directly reveal the solution.
Peter Bossaerts, Felix Fattinger, Carsten Murawski, Nitin Yadav