BSF: 2012251: Algorithmic Game Theory meets Computational Learning Theory

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

This project is funded as part of the United States-Israel Collaboration in Computer Science (USICCS) program. Through this program, NSF and the United States - Israel Binational Science Foundation (BSF) jointly support collaborations among US-based researchers and Israel-based researchers. The goal of this project is to use ideas and techniques developed in the field of Computational Learning Theory to produce algorithms that can aid users or firms in solving certain economic decision-making problems. Computational Learning Theory studies how one can automatically learn good prediction rules from data, as well as questions such as how much data is intrinsically needed in order to learn rules of a given complexity. In economic decision-making, one often has some amount of data (or recent experience) and must extrapolate from this a course of action for the future. This project aims to bring these two areas together in order to produce improved economic decision-making tools. This project focuses specifically on three challenging problems for which ideas from Computational Learning Theory appear to be especially promising. The first concerns the decision of how many of each of a given suite of products to produce when customers are arriving over time and have disjunctive needs, and the production costs for each product obey economies of scale. The goal in this setting is from a small amount of initial observation to be able to commit to a near-optimal plan for how much of each product to produce, to satisfy future customers at the least possible total cost. The second concerns the problems of market segmentation when the potential customers have known attributes but the relation of these attributes to their preferences is not known up front. Finally, the last concerns the problem of inferring a model for bidders in an auction when only the outcome information of the auction is observable. These problems all involve challenging inference tasks for which tools from Computational Learning Theory appear to be well suited.