The Economic Impact of Not Knowing Your Correlated Values

Abstract: Most economic models of markets assume agents know their values for potential outcomes.  This talk considers instead models in which agents only know a prior over their values and learn the instantiation of their values through actions taken in the context of the market. The bulk of the talk focuses on a classical online decision problem, where a decision-maker who is trying to maximize her value inspects a sequence of arriving items to learn their values (drawn from known distributions), and decides when to stop the process by taking the current item. The goal is to prove a "prophet inequality": that she can do approximately as well as a prophet with foreknowledge of all the values. In this talk, we investigate this problem when the values are allowed to be correlated. We consider a natural "linear" correlation structure that models many kinds of real-world search problems. A key challenge is that threshold-based algorithms, which are commonly used for prophet inequalities, no longer guarantee good performance. We relate this roadblock to another challenge: "augmenting" values of the arriving items slightly can destroy the performance of many algorithms. We leverage this intuition to prove bounds (matching-up-to-constant-factors) that decay gracefully with the amount of correlation of the arriving items.