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

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

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.