Algorithmic mechanism design

We consider algorithmic problems in a distributed setting where the partici pants cannot be assumed to follow the algorithm but rather their own self-i nterest. As such participants, termed agents, are capable of manipulating t he algorithm, the algorithm designer should ensure in advance that the agen ts' interests are best served by behaving correctly. Following notions from the field of mechanism design, we suggest a framework for studying such al gorithms. Our main technical contribution concerns the study of a represent ative task scheduling problem for which the standard mechanism design tools do not suffice. (C) 2001 Academic Press.