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

分布式实现：具有自利性的多智能体系统中的协同决策

• 批准号: 0534620
• 负责人: David Parkes
• 金额: $ 16.83万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-11-01 至 2007-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0534620&HistoricalAwards=false
• 关键词: Distributed; Implementation; Collaborative; Decision; Making

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.

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