CAREER: Optimal Mechanism Design without Monetary Transfers

计算机科学、运筹学和经济学的核心目标之一是有效利用稀缺资源。例如，操作系统被设计成有效地利用计算机的内存和处理单元，而网络协议被设计成有效地利用网络的带宽。更广泛地说，关于算法设计和优化的长篇文献中，有很大一部分是由各种领域出现的资源分配问题推动的，从项目管理和企业管理到政府政策和市场设计。在多智能体系统中，实现有效的资源分配结果尤其具有挑战性，在多智能体系统中，一组自利的智能体为共享资源而竞争。例如，在大型计算机网络中，有多个用户竞争网络的共享计算资源，如带宽或对其服务器的访问。每个智能体的目标是最大化自己的效用，而设计者的目标是实现系统级的效率，尽管智能体的偏好是相互竞争的。如果没有精心设计的资源分配机制，现有资源将得不到充分利用，大量的社会效用将被浪费；因此，这些机制的设计必须达到最高标准。该项目的重点是设计多主体资源分配机制，该机制考虑到参与主体的偏好，并寻求在结果中最大限度地公平和提高效率。为了解决参与主体的相互竞争的激励问题，经济学中的机制设计领域提供了非常有用的工具。到目前为止，其中最有效的是使用货币支付：对资源的使用收费可以确保只有最需要它们的代理人才会有兴趣支付价格。然而，使用货币支付往往是不受欢迎的，甚至是不可行的，例如，出于伦理、法律或实际考虑，该机制需要避免货币转移。然而，绝大多数关于机制设计的文献都集中在货币支付的使用上，因此无货币机制并没有得到很好的理解。这个项目从设计者的角度考虑没有钱的机械设计的规范领域，目的是发展一个连贯的理论，说明在没有钱的情况下什么可以实现，什么不能实现。作为货币支付的替代品，无钱机制可以通过故意保留一些资源不分配来惩罚代理人(一种被称为“烧钱”的工具)。这样，改进的激励措施是以社会效用为代价的，为设计师引入了新的权衡，他们需要在激励措施和有效性之间取得平衡。这个项目关注的主要问题是：1)在缺乏资金的情况下，该机制可以为参与者提供什么激励，这些改进的激励需要多少社会效用成本？2)从算法的角度来看，考虑到这些机制可能面临的计算和信息限制，可以实现的最佳最坏情况近似保证是什么？该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

One of the goals that lie at the core of computer science, as well as operations research and economics, is the effective utilization of scarce resources. For example, operating systems are designed to effectively utilize a computer's memory and processing units, and network protocols are designed to effectively utilize a networks' bandwidth. More broadly, a large fraction of the long literature on algorithm design and optimization is motivated by resource-allocation problems that arise in a wide variety of domains, ranging from project management and business administration to government policy and market design. Achieving effective resource-allocation outcomes is particularly challenging in multiagent systems, where a set of self-interested agents compete for shared resources. For example, in large computer networks there are multiple users that compete for the network's shared computational resources, such as its bandwidth, or access to its servers. Each agent's goal is to maximize its own utility, and the goal of the designer is to achieve system-level efficiency despite the agents' competing preferences. Without carefully designed resource-allocation mechanisms, the available resources would be underutilized, and massive amounts of social utility would be wasted; thus, it is imperative that these mechanisms are designed to the highest standard. The focus of this project is on the design of multiagent resource-allocation mechanisms that take into consideration the preferences of the participating agents and seek to maximize fairness and efficiency in the resulting outcomes. To address the competing incentives of the participating agents, the field of mechanism design in economics has provided very useful tools. By far the most effective among them is the use of monetary payments: charging for the use of the resources can ensure that only the agents who need them the most would be interested in paying the price. However, the use of monetary payments is often undesired or even infeasible, e.g., due ethical, legal, or practical considerations, so the mechanism needs to eschew monetary transfers. However, the vast majority of the literature on mechanism design has focused on the use of monetary payments, so money-free mechanisms are not well-understood. This project considers canonical domains of mechanism design without money from the perspective of the designer, with the goal of developing a coherent theory regarding what can and cannot be achieved in the absence of money. As a substitute for monetary payments, money-free mechanisms can instead penalize the agents by intentionally keeping some of the resources unallocated (a tool known as "money-burning"). This way, the improved incentives come at a cost in social utility, introducing novel trade-offs for the designer who needs to strike a balance between incentives and effectiveness. The main questions that this project focuses on are: 1) What incentives can the mechanism provide to the participants in the absence of money, and what cost in social utility do these improved incentives require? 2) From an algorithmic perspective what are the best worst-case approximation guarantees that can be achieved given the computational and informational constraints that these mechanisms may face?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.