AF: Small: Next Steps for Weitzman’s Pandora's Box Problem in Mechanism Design

今天的许多经济互动都发生在平台上：买卖物品、租车或租房、找工作等等。这个项目研究了平台上良好的市场设计背后的经济和算法原则。参与者面临的挑战是，在不浪费太多时间和精力的情况下，从备选方案中寻找最佳选择。平台应该利用算法原理，使他们能够解决不确定性下的决策问题。同时，参与者也会受到他人战略选择的影响。一些参与者的目标相互矛盾，比如想买同样的东西。其他人则有互补的目标，比如一个雇主想雇佣一个好员工。为了帮助参与者实现他们的目标——找到合适的配对对象，节省金钱和时间——市场必须同时具有良好的算法和经济基础。该项目将研究机制的设计，例如拍卖或匹配市场，当存在昂贵的替代方案隐藏信息时。它考虑了战略环境中的分配和匹配问题——例如，将工人与雇主匹配起来。参与者最初不确定替代方案的价值。他们必须付出努力或付出代价来搜索和研究备选方案，在选择过程中发现自己的偏好。为了进行良好的分配或匹配，平台必须协调战略代理，谨慎地使用资源来收集信息。这类问题的一个经典算法模型被称为潘多拉盒子问题，它是由Weitzman在1979年定义的。该项目将研究潘多拉盒子问题新变体的算法解决方案，以及如何将这些解决方案转化为拍卖等机制。该项目将使用博弈论来研究社会福利——为系统用户创造的总价值的衡量标准。社会福利平衡了做出正确选择所产生的价值与收集信息所花费的成本。目标是设计具有近似最优社会福利的机制，即使代理采取战略行动。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Many of today's economic interactions take place on platforms: buying and selling items, renting a ride or a room, finding jobs, and more. This project investigates economic and algorithmic principles underlying good marketplace design on platforms. Participants face a challenge of searching through alternatives for the best choice, while not wasting too much time and effort on the search. The platform should use algorithmic principles to enable them to solve this problem of decision-making under uncertainty. Meanwhile, participants are impacted by others' strategic choices. Some participants have conflicting goals, such as wanting to buy the same item. Others have complementary goals, such as an employer who wants to hire a good employee. To help the participants achieve their goals -- finding good matches, saving money, and saving time -- a marketplace must be designed with both good algorithmic and economic foundations.This project will study design of mechanisms, such as an auctions or matching marketplaces, when there is costly hidden information about the alternatives. It considers allocation and matching problems -- for example, matching workers to employers -- in strategic environments. Participants are initially uncertain about the value of the alternatives. They must expend effort or incur costs to search and study the alternatives, discovering their preferences as they go. To make good allocations or matches, the platform must coordinate strategic agents to prudently spend resources to gather information. A classic algorithmic model for such problems is called the Pandora's Box problem, which was defined by Weitzman in 1979. This project will investigate algorithmic solutions to new variants of the Pandora's Box problem and how to translate such solutions into mechanisms such as auctions. The project will use game theory to study the social welfare -- a measure of total value created for users of the system. The social welfare balances the value generated by making good choices against the costs expended to gather information. The goal is to design mechanisms with approximately optimal social welfare, even when agents act strategically.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.