CAREER: Incentives, Fairness, and Efficiency without Monetary Transfers

该奖项的全部或部分资金来自《2021年美国救援计划法案》(公法117-2)。互联网和数据可获得性的巨大增长改变了算法设计，以及整个计算机科学。从计算资源和广告空间，到食品捐赠、贷款、肾脏和疫苗，算法越来越多地被用来决定如何分配稀缺的资源。与传统的优化不同，这些算法的输入必须从战略代理那里征求，这些代理对算法的输出具有自己的私人偏好。而且，从云中的资源分配和频谱拍卖到重大体育赛事(如奥运会)的锦标赛，众所周知，这些战略实体将尽最大可能优化自己的利益，同时仍“遵循规则”，导致不可预测的最终结果。同时，与传统的优化不同，在许多这样的现代应用中，系统设计者还必须考虑他们的系统在参与者之间是否公平。经济学的经典工作，以及计算机科学和经济学交叉领域的广泛工作，为设计不受战略操纵的算法以及平衡公平和效率的算法提供了丰富的工具包。该项目旨在通过针对几个基本的开放问题来推进和发展这一理论，重点放在不允许货币转移的领域。该项目还计划设计、开发和部署一个以拟议的理论研究为基础的系统，该系统通过使当地抗击饥饿的非营利组织能够以更有效的方式分配其捐赠的食物来服务于当地社区。该项目将把理论的覆盖范围扩大到当前理解存在重大差距的领域，通过以下三个互补的推动力针对几个关键的理论问题。(1)没有钱的机制设计基础。该项目着眼于这一领域的基本问题，目标是开发工具，为若干范例设计真实的机制：可分割和不可分割的物品、静态和动态环境、最坏情况和贝叶斯目标。(2)机制设计不完全理性。在一些重要领域，防范完全理性、预期效用最大化的参与者过于谨慎。这个项目提出并探索了对不完全理性进行建模的几种可能性。(3)表现力不强的机制设计。例如，由于主体的认知限制，得出复杂的效用函数通常是不可行的。该项目探索了在没有钱的情况下机制设计的表现力和启发性之间的权衡。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2).The Internet and the vast increase in the availability of data have transformed algorithm design, as well as computer science in general. From computational resources and advertising space, to food donations, loans, kidneys, and vaccines, algorithms are increasingly being used to decide how scarce resources are allocated. As opposed to traditional optimization, the input to these algorithms must be solicited from strategic agents, with their own, private preferences over the algorithm's output. And, from resource allocation in the cloud and spectrum auctions to tournaments in major sporting events (such as the Olympics), it is well-understood that these strategic entities will behave to optimize their own benefit to the extent possible while still “following the rules,” leading to unpredictable final outcomes. At the same time, unlike traditional optimization, in many of these modern applications, system designers must also consider whether their system is equitable among its participants. Classic work in Economics, as well as extensive work in the intersection of Computer Science and Economics, provides a rich toolkit for designing algorithms that are immune to strategic manipulations as well as algorithms that balance fairness and efficiency. This project aims to advance and develop this theory with a focus on domains where monetary transfers are not allowed, by taking aim at several fundamental open questions. The project also contains plans to design, develop, and deploy a system that is based on the proposed theoretical research and that serves the local community by enabling local non-profit organizations that fight hunger to allocate their food donations in a more efficient manner.The project will expand the reach of theory into areas where there is a major gap in current understanding, by taking aim at several key theoretical questions in the following three complementary thrusts. (1) Foundations of mechanism design without money. The project takes aim at fundamental questions in this space, with the goal of developing tools for designing truthful mechanisms for a number of paradigms: divisible and indivisible goods, static and dynamic environments, worst-case and Bayesian objectives. (2) Mechanism design with imperfect rationality. There are important domains in which protecting against fully rational, expected utility-maximizing participants is overly cautious. This project puts forward and explores several possibilities for modeling imperfect rationality. (3) Mechanism design with imperfect expressivity. Eliciting complex utility functions is often infeasible, e.g., because of agents' cognitive limitations. The project explores the trade-off between expressiveness and ease of elicitation in mechanism design without money.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.