Learning from Stochastically Revealed Preference

John Birge, Xiaocheng Li, Chunlin SunNeurIPS 2022 · OpenReview

Introduction

Most "revealed preference" models assume that every agent shares the same fixed utility function. This paper breaks that mold by introducing a stochastic framework where utility follows an unknown distribution, providing the first theoretical guarantees and algorithms to recover these distributions from noisy, real-world observations.

In economics, the "revealed preference" problem asks: if we see what someone buys given their budget and the prices of goods, can we figure out what they actually value? Traditionally, researchers assumed a "common utility"—that every agent in a dataset is trying to maximize the exact same internal score.

However, in the real world, people are heterogeneous. Two people with the same budget might buy different things because their preferences differ. If you try to fit a single utility function to these diverse choices, the math often breaks, leading to what the authors call the "empty intersection" problem. This paper tackles the challenge of learning the distribution of preferences rather than a single point, viewing it as a stochastic version of inverse linear optimization.

Methodology: Modeling Preference Distributions

The authors propose two distinct settings for how preferences might be distributed:

  1. The Gaussian Setting: They model utility using the von Mises-Fisher (vMF) distribution, which is essentially a Gaussian distribution wrapped around a unit sphere. Since the likelihood function for this model involves non-closed-form integrals, they use a Bayesian Posterior Sampling approach (specifically a Metropolis-Hastings algorithm) to estimate the mean direction and concentration of preferences.
Visualizing utility distributions and the empty intersection problem on a unit sphere.
  1. The $\delta$-Corruption Setting: Here, they assume most agents follow a "true" utility vector $u^*$, but a fraction ($\delta$) of the observations are arbitrarily corrupted or noisy. To solve this, they develop a $\gamma$-margin optimization objective—inspired by the "margins" used in Support Vector Machines—to find a utility vector consistent with the maximum number of observations. They solve this non-convex problem using Simulated Annealing.

Key Insights and Theoretical Guarantees

A significant insight from the paper is the proof of identifiability from actions. The authors demonstrate that observing only the optimal actions (the bundle of goods purchased) is sufficient to recover the parameters of the underlying utility distribution, provided the price and budget constraints are diverse enough.

Furthermore, the paper addresses the "Empty Intersection" challenge. In deterministic models, all observations must be consistent with one utility. In a stochastic setting, they aren't. The authors show that instead of looking for a single feasible point, we should look for where the posterior distribution of utilities concentrates. In the corrupted setting, the authors shift the goal from finding the exact $u^*$ to finding a $u$ that generalizes well to future unseen observations, providing a solid theoretical bridge between inverse optimization and machine learning.

Experimental Validation and Results

The paper relies on synthetic numerical simulations to validate its theoretical findings. They test their algorithms across three types of price ($a$) and budget ($b$) distributions: Uniform, Discrete, and Fixed-Price. The experiments scale the number of products ($n$) from 3 to 25 to test the "curse of dimensionality."

  • Theoretical Convergence: The authors prove that as the number of observations ($T$) grows, the learner’s estimate converges to the true distribution parameters at a rate of roughly $1/\sqrt{T}$.
  • High Accuracy in Low Dimensions: For problems with up to 10 products, the algorithms achieved predictive accuracies between 87% and 99.9%.
  • The Curse of Dimensionality: Performance drops significantly when the number of products reaches 25 (falling to ~55-68%). This suggests that while the theory holds, the computational challenge of sampling from high-dimensional spheres remains a significant hurdle.

Limitations and Future Work

The current Markov Chain Monte Carlo (MCMC) and Simulated Annealing approaches are computationally expensive. The authors note that more efficient sampling (like parallel computing) is needed for high-dimensional market analysis.

Additionally, the model currently assumes a single budget constraint. Real-world scenarios often involve multiple constraints (e.g., time, calories, and money), which the authors suggest as a promising direction for "stochastic inverse optimization." Finally, while the paper focuses on passive observations, a natural next step is active learning, where a learner strategically sets prices to learn customer preferences as quickly as possible.

Summary updated

Abstract

We study the learning problem of revealed preference in a stochastic setting: a learner observes the utility-maximizing actions of a set of agents whose utility follows some unknown distribution, and the learner aims to infer the distribution through the observations of actions. The problem can be viewed as a single-constraint special case of the inverse linear optimization problem. Existing works all assume that all the agents share one common utility which can easily be violated under practical contexts. In this paper, we consider two settings for the underlying utility distribution: a Gaussian setting where the customer utility follows the von Mises-Fisher distribution, and a $\delta$-corruption setting where the customer utility distribution concentrates on one fixed vector with high probability and is arbitrarily corrupted otherwise. We devise Bayesian approaches for parameter estimation and develop theoretical guarantees for the recovery of the true parameter. We illustrate the algorithm performance through numerical experiments.
BibTeX
@inproceedings{birge2022learning,
  author = {John Birge and Xiaocheng Li and Chunlin Sun},
  title = {{Learning from Stochastically Revealed Preference}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=fKXiO9sLubb},
}
Figure