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.