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.
