Learning Economic Parameters from Revealed Preferences

Maria Florina Balcan, Ruth Urner, Amit Daniely, Ruta Mehta, Vijay V. Vazirani

Research output: Contribution to journalArticlepeer-review


A recent line of work, starting with Beigman and Vohra [4] and Zadimoghaddam and Roth [30], has addressed the problem of learning a utility function from revealed preference data. The goal here is to make use of past data describing the purchases of a utility maximizing agent when faced with certain prices and budget constraints in order to produce a hypothesis function that can accurately forecast the future behavior of the agent. In this work we advance this line of work by providing sample complexity guarantees and efficient algorithms for a number of important classes. By drawing a connection to recent advances in multi-class learning, we provide a computationally efficient algorithm with tight sample complexity guarantees (˜(d/ε) for the case of d goods) for learning linear utility functions under a linear price model. This solves an open question in Zadimoghaddam and Roth [30]. Our technique yields numerous generalizations including the ability to learn other well-studied classes of utility functions, to deal with a misspecified model, and with non-linear prices.

Original languageEnglish (US)
Pages (from-to)338-353
Number of pages16
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
StatePublished - 2014
Externally publishedYes


  • Efficient algorithms
  • Linear
  • Query learning
  • Revealed preference
  • SPLC and Leontief utility functions
  • Statistical learning

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Learning Economic Parameters from Revealed Preferences'. Together they form a unique fingerprint.

Cite this