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.