Distributed Implementation: Collaborative Decision-Making in Multi-Agent Systems with Self-Interest

这是分布式实现领域的一个研究项目，其目标是促进自利的代理之间的协作，但不需要集中计算，也不需要直接披露私人信息。这概括了本质上集中的机制设计，使其与许多分布式系统更相关。其目的是，分布式实现将促进分布式人工智能(DAI)中的协作问题求解方法与计算机制设计中处理自利的方法的集成。人们经常认为，协作系统是参与者具有某种内在利他主义的系统。但事实上，具有内在私利的参与者之间也可以促进合作。例如，虽然团队中的参与者可能共享高级别的共同目标，但每个人可能更喜欢让其他人执行任务。仔细的设计可以提供适当的激励，以促进许多领域的协作行为，包括：在工作人员团队中自动分配任务(例如，在机场或医院)；协作网络协议(例如，对等路由、网格计算)；以及电子商务领域(例如，用于物流自动化，如船队采购和托运人与承运人之间的调度)。该项目将显著扩展分布式实施的理论和实践，超越总体原则，进入特定(建设性)协议的设计和分析。它将解决的一个基本问题是具有自利参与者的分布式顺序决策。许多系统是动态的，因此，研究如何将最新的方法应用于分布式环境中具有中央机制的顺序决策似乎很重要。本研究将研究分布式(但间歇式)约束优化问题，采用DAI已有的算法方法，使其符合自身利益。它还将考虑计算成本高昂的环境，这会引发新的紧张局势。最后，将理论扩展到具有更丰富的代理行为的多代理系统，包括服从、自利、错误和恶意代理的混合。这将使该理论在实际系统中更加相关。分布式实现的进步将在许多领域产生直接影响。对于网格计算、对等网络和自组织网络等分布式计算系统，该研究可以促进系统内的优化和协调决策(例如，如何分配资源、存储内容、路由分组)，而不需要一些可信的第三方。对于电子商务，它可以在公共场所使用无线设备的移动用户之间实现动态定价交易，例如在商场、校园和球类比赛中。更广泛地说，分布式实施可以促进公司和其他组织内部的协作，例如为机场和医院等动态和复杂领域的员工提供自动任务分配。研究计划的一个重要组成部分是，在计算机科学和经济学的交界处，继续将这些想法融入本科生和研究生课程。

This is a research project in the field of distributed implementation, in which the goal is to facilitate collaboration between self-interested agents but without centralized computation and without the direct revelation of private information. This generalizes mechanism design, which is inherently centralized, in a way that makes it more relevant for many distributed systems. The intention is that distributed implementation will facilitate the integration of methods for cooperative problem solving in Distributed Artificial Intelligence (DAI) with the methods to handle self-interest in computational mechanism design. One often imagines that collaborative systems are those for which the participants have some intrinsic altruism. But in fact, collaboration can also be promoted between participants with intrinsic self-interest. For instance, while participants in a team may share high-level common goals, each individual may prefer that others perform tasks. Careful design can provide appropriate incentives to promote collaborative behavior in many domains, including: automated task allocation amongst a team of workers (e.g. at an airport or a hospital); for collaborative network protocols (e.g. peer-to-peer routing, grid computing); and also in e-commerce domains (e.g. for the automation of logistics such as fleet procurement and scheduling between shippers and carriers).This project will significantly extend both the theory and practice of distributed implementation, moving beyond overarching principles to the design and analysis of specific (constructive) protocols. One fundamental problem that it will address is that of distributed sequential decision making with self-interested participants. Many systems are dynamic, and as such it seems important to study how to apply recent methods in sequential decision making with a central mechanism in our distributed context. This research will study the problem of distributed (but episodic) constrained optimization, adapting existing algorithmic methods from DAI in order to make them work with self-interest. It will also consider settings in which computation is costly, which raises new tensions. Finally, it will expand the theory to address multi-agent systems with richer agent behaviors, including mixtures of obedient, self-interested, faulty and malicious agents. This will make the theory even more relevant in practical systems.Advances in distributed implementation will have a direct impact in a number of areas. For distributed computational systems such as grid computing, peer-to-peer, and ad hoc networks, this research can promote optimal and coordinated decision making (for instance on how to allocate resources, store content, route packets) within the system and without requiring some trusted third-party. For e-commerce, it can enable trading with dynamic pricing amongst mobile users with wireless devices in public spaces, such as in shopping malls, on campuses and at ball games. More broadly, distributed implementation can promote collaboration within firms and other organizations, for instance providing automated task allocation to workers in dynamic and complex domains such as airports and hospitals. An important component of the research plan involves the continued integration of these ideas into both undergraduate and graduate curricula at the interface between computer science and economics.