Computing using Samples: Theoretical Guarantees with the Direct Learning Approach

Machine learning algorithms in the field of economics and game theory usually involve computing an intermediate valuation function from data samples and using this approximate function to compute desired solution concepts. This approach has several problems ranging from a high sample complexity to a lack of provable guarantees about the final solution. In order to avoid these problems, we explore a new method to learn solution concepts from data: instead of learning an intermediate valuation function, we learn the solution concept directly from the samples. This approach provides an alternative way to approximately learn solution concepts using fewer samples. In addition to this, from our study of using this approach to learn market equilibria, we find that, in a lot of settings, it is easier to prove efficiency and fairness guarantees about the learned solutions.

Authors

• Vignesh Viswanathan University of Massachusetts Amherst

Keywords

• Theoretical Machine Learning
• Computational Economics
• Game
• Theory