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.