CAREER: Optimal Mechanism Design without Monetary Transfers

点击翻译按钮获取中文摘要

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.