Efficiently Learning from Revealed Preference
Preprint
Abstract
In this paper, we consider the revealed preferences problem from a learning perspective. Every day, a price vector and a budget is drawn from an unknown distribution, and a rational agent buys his most preferred bundle according to some unknown utility function, subject to the given prices and budget constraint. We wish not only to find a utility function which rationalizes a finite set of observations, but to produce a hypothesis valuation function which accurately predicts the behavior of the agent in the future. We give efficient algorithms with polynomial sample-complexity for agents with linear valuation functions, as well as for agents with linearly separable, concave valuation functions with bounded second derivative.Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- A random polynomial-time algorithm for approximating the volume of convex bodiesJournal of the ACM, 1991
- The Construction of Utility Functions from Expenditure DataInternational Economic Review, 1967
- THE EQUIVALENCE IN TWO DIMENSIONS OF THE STRONG AND WEAK AXIOMS OF REVEADED PREFERENCEMetroeconomica, 1965
- A Note on the Pure Theory of Consumer's BehaviourEconomica, 1938