Exploration in Markets under Local Congestion-based Pricing

The role of markets in aggregating diverse information held by market participants is well-understood in the economics literature. However, the extent to which natural market mechanisms actively drive exploration and learning amongst myopic market participants is understood to a much lesser extent. This paper attempts to shed light on this question. The market mechanism we consider is local congestion-based pricing, in which the prices for matching to entities in various information states (ratings, skill levels, etc.) are defined depending on the local availability levels of entities in those states. While such a pricing mechanism may internalize the (negative) congestion externality induced by the matchings, the question is whether it internalizes their (positive) exploration externality -- indeed, matchings with entities in information states with poor rewards may have to be encouraged if it increases entity flow into information states with higher rewards and low availability, implying that optimal prices may have to depend on global availability levels.We define a new concept of a local market equilibrium (LME), which is the equilibrium point of local congestion-based pricing dynamics in these markets, to investigate this question. A matching rule and a set of prices corresponding to the states constitute an LME if the matching rule is (1) a utility-maximizing response to the price-adjusted payoffs, and (2) self-sustaining, i.e., the match rate at any state is at most the inflow of entities in that state that result from the matching rule. We prove that (a) the LME always exists, (b) it is polynomial-time computable, (c) the set of LME is convex and compact, and (d) the LME is always unique in non-degenerate settings (state rewards are distinct and non-zero). We then show two contrasting results of high practical relevance: (1) for any market instance where the quality of new entities is worse on average relative to the outside option, the unique LME corresponds to complete market failure, and (2) for broad classes of market instances with certain natural transition and reward structures, the unique LME corresponds to system optimality, implying that local congestion-based pricing may effectively solve the problem of incentivizing exploration in these markets. We support our theoretical findings with extensive simulations and discuss various open questions and the implications of our results to market design