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.