Algorithmic Mechanism Design

Algorithmic Mechanism Design

We consider algorithmic problems in a distributed setting where the
participants cannot be assumed to follow the algorithm but rather their
own self-interest. As such participants, termed agents, are capable of
manipulating the algorithm, the algorithm designer should ensure in
advance that the agents’ interests are best served by behaving correctly.
Following notions from the field of mechanism design, we suggest a
framework for studying such algorithms.
In this model the algorithmic solution is adorned with payments to
the participants and is termed a mechanism. The payments should be
carefully chosen as to motivate all participants to act as the algorithm
designer wishes. We apply the standard tools of mechanism design to
algorithmic problems and in particular to the shortest path problem.