BSF: 2012251: Algorithmic Game Theory meets Computational Learning Theory

该项目是美国-以色列计算机科学合作（USICCS）计划的一部分。 通过这个项目，NSF和美国-以色列两国科学基金会（BSF）共同支持美国和以色列研究人员之间的合作，该项目的目标是利用计算学习理论领域的思想和技术来产生算法，帮助用户或公司解决某些经济决策问题。 计算学习理论研究如何从数据中自动学习良好的预测规则，以及为了学习给定复杂度的规则本质上需要多少数据等问题。 在经济决策中，人们通常有一些数据（或最近的经验），必须从中推断出未来的行动方针。 该项目旨在将这两个领域结合起来，以产生更好的经济决策工具。该项目特别关注三个具有挑战性的问题，其中计算学习理论的想法似乎特别有前途。 第一个问题是，当顾客随着时间的推移而到达，并且有不同的需求时，每种产品的生产成本服从规模经济，那么就决定生产多少种给定的产品。 这种设置的目标是从少量的初始观察到能够致力于每种产品生产多少的接近最优的计划，以尽可能少的总成本满足未来的客户。 第二个问题是当潜在客户具有已知属性，但这些属性与他们的偏好之间的关系并不事先知道时的市场细分问题。 最后，最后一个问题的推断模型的投标人在拍卖时，只有拍卖的结果信息是可观察的。 这些问题都涉及具有挑战性的推理任务，计算学习理论的工具似乎非常适合。

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.