AF: Small: New Directions for Simplicity versus Optimality in Mechanism Design

AF：小：机构设计中简单性与最优性的新方向

• 批准号: 2008006
• 负责人: Shuchi Chawla
• 金额: $ 50万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2022-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008006&HistoricalAwards=false
• 关键词: AF; Small; New; Directions; Simplicity

This project aims to develop new algorithmic techniques for designing market mechanisms that faithfully model consumer behavior and other real-world constraints. This work lies within the purview of algorithmic mechanism design, which deals with the optimization of economic systems wherein many parties with conflicting objectives compete for possession of resources. Insights from this area apply to the design of all kinds of markets – big or small, brick-and-mortar or electronic – and play an increasingly important role in the rise of new electronic marketplaces such as online advertising, the cloud market, the rideshare industry, crowdsourcing marketplaces, etc. The project focuses on the objectives of maximizing the seller's revenue or the economic efficiency of the allocation. For each of these objectives, the goal is to develop solutions that are simple to implement, broadly applicable, and near optimal.The first part of this project will focus on the revenue-maximization objective under a so-called buy-many constraint. This natural constraint requires that the seller cannot limit the number of times a buyer can interact with the mechanism, and is satisfied in most real-world contexts. Imposing this constraint imparts a nice structure to the optimal mechanism, and should thereby allow for much better approximations in the absence of any further assumptions than previously known. The second part of this project will develop algorithms for efficient resource allocation in online settings where buyers arrive in the market over time and allocation decisions must be made without knowing future demand. The goal is to develop simple pricing-based allocation mechanisms that nevertheless achieve near-optimal performance. The third part of this project will consider settings where buyers are uncertain about their current or future values, and will study the effectiveness of pricing strategies such as refunds, free trials, and overuse fees as vehicles for lessening the risk faced by the buyer.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该项目旨在开发新的算法技术，用于设计忠实地模拟消费者行为和其他现实世界约束的市场机制。这项工作属于算法机制设计的范围，它涉及经济系统的优化，其中许多具有冲突目标的各方争夺资源。该领域的见解适用于各种市场的设计-无论是大型还是小型，实体还是电子-并在新的电子市场的兴起中发挥着越来越重要的作用，如在线广告，云市场，拼车行业，众包市场等。该项目专注于最大化卖方收入或分配经济效率的目标。对于这些目标中的每一个，我们的目标都是开发易于实现、广泛适用和接近最优的解决方案。本项目的第一部分将关注所谓的多买约束下的收入最大化目标。这种自然约束要求卖方不能限制买方可以与该机制交互的次数，并且在大多数现实环境中都得到了满足。施加这个约束赋予了最优机制一个很好的结构，因此在没有任何进一步假设的情况下，应该允许比以前已知的更好的近似。该项目的第二部分将开发在线环境中高效资源分配的算法，其中买家随着时间的推移进入市场，并且必须在不知道未来需求的情况下做出分配决策。我们的目标是开发简单的定价为基础的分配机制，但实现接近最佳的性能。本项目的第三部分将考虑买家对当前或未来价值不确定的情况，并将研究退款、免费试用和过度使用费等定价策略作为降低买家面临的风险的手段的有效性。该奖项反映了NSF的法定使命，通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Online Learning for Min Sum Set Cover and Pandora's Box

在线学习 Min Sum Set Cover 和潘多拉魔盒

• 发表时间: 2022
• 期刊: International Conference on Machine Learning
• 作者: Evangelia Gergatsouli;Christos Tzamos
• 通讯作者: Christos Tzamos

Pricing ordered items

为订购的商品定价

• DOI: 10.1145/3519935.3520065
• 发表时间: 2022
• 期刊: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Chawla, Shuchi;Rezvan, Rojin;Teng, Yifeng;Tzamos, Christos
• 通讯作者: Tzamos, Christos