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:
- 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.
- 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