BSF: 2012251: Algorithmic Game Theory meets Computational Learning Theory

BSF：2012251：算法博弈论与计算学习理论的结合

• 批准号: 1331175
• 负责人: Avrim Blum
• 金额: $ 3.29万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-10-01 至 2018-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1331175&HistoricalAwards=false
• 关键词: BSF; 2012251; Algorithmic; Game; Theory

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.

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

项目成果

From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games

从战场到选举：Blotto 和审计游戏的制胜策略

• 发表时间: 2018
• 期刊: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018
• 作者: Behnezhad, Soheil;Blum, Avrim;Derakhshan, Mahsa;HajiAghayi, MohammadTaghi;Mahdian, Mohammad;Papadimitriou, Christos;Rivest, Ronald;Seddighin, Saeed;Stark, Philip
• 通讯作者: Stark, Philip

Collaborative PAC Learning

• 发表时间: 2017-12
• 作者: Avrim Blum;Nika Haghtalab;Ariel D. Procaccia;Mingda Qiao

Efficient PAC Learning from the Crowd

• 发表时间: 2017-03
• 期刊: ArXiv
• 作者: Pranjal Awasthi;Avrim Blum;Nika Haghtalab;Y. Mansour

On Price versus Quality

关于价格与质量

• 发表时间: 2018
• 期刊: ITCS 2018
• 作者: Blum, Avrim;Mansour, Yishay
• 通讯作者: Mansour, Yishay

Opting Into Optimal Matchings

选择最佳匹配

• DOI: 10.1137/1.9781611974782.155
• 发表时间: 2017
• 期刊: SIAM: ACM-SIAM Symposium on Discrete Algorithms (SODA17
• 作者: Blum, Avrim;Caragiannis, Ioannis;Haghtalab, Nika;Procaccia, Ariel D.;Procaccia, Eviatar B.;Vaish, Rohit
• 通讯作者: Vaish, Rohit